2007 August | Polymath Programmer

Never question the age of a woman

August 24, 2007 By Vincent

I’ve always had the impression that no one should ask about the age of a woman. In fact, no gentleman would be caught dead contemplating the very act itself. Anyway, a childhood song rose out of my submerged memories recently and it goes like this:

How old is she, Billy Boy, Billy Boy?
How old is she, charming Billy?
Three times six and four times seven,
Twenty eight and eleven.
She’s a young thing and cannot leave her mother.

The issue isn’t with how the song is sung. I was in primary school then (about 11 years old), and one of my more expressive classmates pointed out to the music teacher the improbability of the truthfulness of the lyrics. He proceeded to prove his point:

Three times six and four times seven,
Twenty eight and eleven.

Became
(3 * 6) + (4 * 7) + (28) + (11)

Which comes up to a grand total of *drum roll* 85!!

Being 11 years old then, 85 years old was like, ancient. Still, 85 years old wasn’t unusual. My cheeky classmate then asked, “How can 85 years be a young thing?”

My music teacher was speechless.

Filed Under: Curiosita Tagged With: billy-boy, childhood-memory, music

Complete Super Mario 64 in 15:24

August 23, 2007 By Vincent

I, am awestruck. I’ve just witnessed this person breeze through a Super Mario game in just 15 minutes and 24 seconds. Unbelievable.

Filed Under: Offtopic Tagged With: super-mario, video-game

Tackling problems with indefinite answers

August 23, 2007 By Vincent

In your programming career, have you ever faced a problem where there’s more than one answer? Or that you don’t even know if there is a right answer? Let me tell you one of mine.

Recently, one of my colleagues came to me for advice on a validation condition he faced. It turned out to be mathematical in nature. Wow! Anyway, in his database he stored number_of_days, month and prorated_fee. The stored data contains records of the results of prorating calculations.

What is prorating? Say a customer was charged a monthly fee for a service, and the customer had just signed up for the monthly service near the end of June. And he had the service for only 5 days, June has 30 days, and the monthly fee is $20. Prorating means he’d be charged 5 / 30 * $20 = $3.33. You will have noticed that prorating often has inexact results because the calculated values are rounded to 2 decimal places.

Back to my colleague’s problem. Suppose that the records from the database looked like this

days  month  prorated
5     30     3.33
8     30     5.33

I’ve translated the month into the number of days in that month for easier visualisation.

The problem was, given those records, could he prove that the prorated fee was calculated from the same monthly fee?

For this example, the monthly fee used was $20, so the results match. What he needed from me was, was there a way to programatically determine if there was a correct original monthly fee?

My initial instinctive answer was no, because all precision of the calculation was lost when the final value was rounded. Then he said, he’s not looking for precision. He just wanted to know if there was a possibility that the records were calculated using the same monthly fee. Aaahhhh, now we’re talking. So I told him to give me some time to work out an equation or something. Then I went to work.

Mathematically formulating the problem, I got:
Given d, m and p, where
d is the number of days in service
m is the number of days of that month in service
p is the calculated prorated value
find f, the original monthly fee, such that abs(fd/m - p) < 0.005

The equation is fd/m = p', where p' is the exact calculated value. Then p' is rounded to p.

The abs(fd/m - p) < 0.005 condition was because of the rounding. The difference between the calculated value and the stored value must be less than 0.005 for the rounding to be correct. And the error margin is 0.005 because 2 decimal place rounding means the value to be rounded is less than half of 0.01.

Rewriting the condition, we get
-0.005 < fd/m - p < 0.005
=> -0.005m < fd - pm < 0.005m
=> -0.005m + pm < fd < 0.005m + pm
=> (p - 0.005)m/d < f < (p + 0.005)m/d [d is always positive, so division is fine]

Substituting our first record's values into the inequality, we get
(3.33 - 0.005)(30)/(5) < f < (3.33 + 0.005)(30)/(5)
=> 19.95 < f < 20.01

Substituting our second record's values into the inequality, we get
(5.33 - 0.005)(30)/(8) < f < (5.33 + 0.005)(30)/(8)
=> 19.96875 < f < 20.00625

Now if there were more records, we'd continue substituting, and we'll end up with a lot of inequality ranges. So what's the solution to the problem? If there was an f such that it satisfies all the inequalities, then the prorated values could have been calculated from the same monthly fee.

I went back to my colleague and told him that even if the inequalities could be solved, he might still have a range of values that could have contained the original monthly fee. So there's still no exact answer. He said that was fine. He rephrased his objective, that he wanted to know if the records from the database could have been calculated from the same monthly fee within reasonable limits.

Ohhh. Ok. I told him if he could find a range of values of f satisfying the set of inequalities from above, and that there was a value in that range with at most 2 decimal places, then he's done.

Example, a range of (19.956, 20.00) would be valid, because the original value could be 19.96 or 19.97.
But a range of (19.956, 19.959) would be invalid, because there were no values that had at most 2 decimal places. The reason for this was that the original monthly fee was at most 2 decimal places.

So, how do we find that range of values of f satisfying all the inequalities?

Let L be the set of the left hand values of the inequalities. Let R be the set of right hand values of the inequalities. Then there's a range of values of f satisfying the inequalities if and only if the maximum value in L is less than or equal to the minimum value in R. Stated mathematically,

max(L) <= min(R)

I gave him the piece of paper where I scribbled my notes, and he copied some of the important formulae. What about determining the solution programmatically? What, are you kidding? I wracked my brain for a mathematical solution, distilled it into understandable logic steps. How to implement this was up to him... *grin*

Filed Under: Work Stuff Tagged With: indefinite-answers, math, reformulate-billing-problem

Have you proven a hunch before?

August 22, 2007 By Vincent

It was one of those morning math lectures. The lecture theatre was unusually quiet, and the only sounds I heard were those of my fellow students’ pens, scratching feverishly across the surface of their note pads. The professor happened to mention that no one’s ever proven the existence of infinite twin primes.

A prime number is a positive integer which is divisible by only 1 and itself. Examples are 2, 3, 5, 7 and 11.

Twin primes are prime numbers that differ by 2. Examples are (3, 5) and (11, 13).

Anyway, after that lesson, I was wracking my brain to find the proof (I felt challenged by the impossibility), and I started making up lists of numbers and adding them up. I’ve already convinced myself that all primes are odd, except for 2, so I focused on odd numbers. To my surprise, I found an interesting relationship in sums of odd integers.

I was adding the odd numbers starting from 1. So I got
1 + 3 = 4
1 + 3 + 5 = 9
1 + 3 + 5 + 7 = 16
1 + 3 + 5 + 7 + 9 = 25

As I got further into the sums, I realised that the sums are square numbers! Ok, so it’s not Nobel Prize material, but hey, I was in freshman year then, so this was pretty cool. Then I got swamped by homework, and I didn’t give this any more thought.

Some time later, my mind was freer and the idea came back with a vengeance. So I thought, “Can I prove it?”. My math lessons included a lot of proving problems, and I was naive then, so I hadn’t yet developed a healthy fear of the Terrifying Triple: show, prove and justify.

So I finally put some effort into it. The sequence looks like an arithmetic series, so I applied the formula for sums of arithmetic series.
S(n) = n[2a + (n - 1)d] / 2
where n is the number of terms, a is the first term, d is the difference between consecutive terms and S(n) is the sum of the first n terms.

The first term a is 1, d is 2 and I substituted the values into the formula:
S(n) = n[2 + (n - 1)2] / 2
= n[2 + 2n - 2] / 2
= 2n² / 2
= n²

That wasn’t much of an exercise. The point is, have you ever tried to prove a hunch before?

There was this incident where one of our production programs failed. I tried debugging the program, analysing the code and took the whole morning poring over every line, and still couldn’t pinpoint the error.

My colleague came in, took a look at the program code, got an “Aha!” moment, and gave me this priceless advice, “Increase array size“.

Well, I’m not totally without results, since I figured that it was due to an insufficient array size. I was simply trying to pinpoint the exact place where I should increase the size. My colleague’s next piece of enlightening advice, “It doesn’t matter. Increase ‘em all.“.

I was at my wit’s end, and I had backlogs of emails and requests coming in, so I gave in. I simply increased the array sizes of all the affected array variables, compiled it and tested it. It worked! I pursued the proving of a hunch too far and too long.

As a perfectionist programmer, this moment of weakness rankled my principles. I’ve since learned that sometimes, I have to let go of some ideals, and use the extra energy for other more constructive purposes.

Have you ever had to give up some of your ideals too?

Filed Under: Curiosita Tagged With: arithmetic-series, hunches, ideals, odd-numbers, twin-primes

MathSpeeder – Firing neurons and nimbling fingers

August 21, 2007 By Vincent

Alright, it’s been kinda boring lately… so I’ve decided to whip up a picker-upper that will rejuvenate your brain and excite you again. You’ll be churning out flawless code in no time after this.

Enter the MathSpeeder.

MathSpeeder is a console program that fires a series of math questions. Your job is to answer all of them correctly. Oh yeah, you’ll be timed too. Ain’t that cool? Here’s the source code:

const int cnNumberOfQuestions = 10;
string response = string.Empty;
Console.WriteLine("MathSpeeder - Firing neurons and nimbling fingers");
Console.WriteLine("There are {0} math questions", cnNumberOfQuestions);
Console.Write("Ready to play (y/n)? ");
response = Console.ReadLine().ToLower();
Console.WriteLine();
if (response.Equals("y"))
{
    int operand1, operand2, result, answer;
    int score;
    Random rand = new Random();
    score = 0;
    DateTime start, end;
    start = DateTime.Now;
    int i;
    for (i = 0; i < cnNumberOfQuestions; ++i)
    {
        operand1 = rand.Next(1000);
        operand2 = rand.Next(1000);
        result = operand1 + operand2;
        response = string.Format("Q{0}", i + 1).PadLeft(3);
        Console.Write("{0}: {1} + {2} = ", response, operand1, operand2);
        response = Console.ReadLine().Trim();

        try
        {
            answer = Convert.ToInt32(response);
            if (answer == result)
            {
                ++score;
                Console.WriteLine("     Correct!\n");
            }
            else
            {
                Console.WriteLine("     Wrong!\n");
            }
        }
        catch
        {
            Console.WriteLine("     Wrong!\n");
        }
    }
    end = DateTime.Now;
    TimeSpan ts = end - start;
    Console.WriteLine("You got {0} correct answers out of {1} questions", score, cnNumberOfQuestions);
    Console.WriteLine("Total time taken: {0,0:f2} seconds", ts.TotalSeconds);
    Console.WriteLine("Average time per question: {0,0:f2} seconds", ts.TotalSeconds / (double)cnNumberOfQuestions);
}
else
{
    Console.WriteLine("Challenge the MathSpeeder next time then!");
}

Console.WriteLine();
Console.WriteLine("End of program");
Console.ReadLine();