« Snow Days, With and Without Snow | Main | Glass Houses »

January 03, 2009

Solving Brain Ticklers with PowerShell

I'm a member of Tau Beta Pi, the engineering honor society, and I receive their quarterly magazine The Bent. Each issue they have a "Brain Ticklers" section where they post 5 questions plus a bonus questions and a "computer bonus" question, where it is expected you will need to write a program to solve it.

I occasionally take a stab at some of the problems, but this time I noticed that a few of them seemed amenable to solving with PowerShell scripts, so I gave it a shot.

The first one was:

"Find the smallest positive integer such that, if you place a 4 in front of it, you get a number that is exactly four times as large as you get if you place a 4 at the end of the number." [credited to The Numerology of Dr. Matrix by Martin Gardner, a book I think we owned when I was a kid]

I realize this could be tackled by solving a series of equations of the form:

40 + x = (10x + 4) * 4
400 + x = (10x + 4) * 4
4000 + x = (10x + 4) * 4

until you found one where x was an integer, but instead I wrote the following script which found it quickly:

$i = 0
do {
  $i++
} until ($i + (4 * ([Math]::Pow(10,$i.ToString().Length))) -eq (($i*10+4)*4))
write-host "The number is" $i

The second problem was the computer bonus:

"Fermat, in about 1650, asked for all solutions in positive integers for x^2 + 2 = y^3. It turns out that x = 5, y = 3 is the only solution. Now consider x^2 - 15 = y^3. One solution in positive integers is x = 4, y = 1. Find all other solutions." [this came from a TBP member named Don A. Dechman]

I figured I would limit myself to answers where y^3 fit safely into a 64-bit number, so my script was:

for ([Int64]$y = -2 ; $y -lt 2000000; $y++) {
  [Int64]$y3p15 = ($y*$y*$y)+15
  Int64]$x = [Math]::Sqrt($y3p15)
  if ($x*$x -eq $y3p15) {
    write-host "x =" $x ", y =" $y
  }
}

I assume the solutions this came up with are all the possible ones, that is, there is no answer where y needs 23 bits of storage. The reason it squares the square root is because [Math]::Sqrt returns a double, so I am checking that the square root is an integer; I'm also crossing my fingers that I didn't get tripped up in some rounding errors there.

The last problem I scripted was this somewhat complicated scenario:

"Al has two 12-hour clocks that, when fully wound, will run for nearly eight days. Both clocks were keeping different times, with each being wrong by a different exact number of minutes per day, although less than one hour each. Al took his clocks to the local clock mender, who works only from 9:30 a.m. to 5 p.m. Monday through Friday. He immediately wound both clocks fully and set them to the correct time, a whole number of minutes after the hour, and put them on the shelf for observation.

The following Monday, as he went to take down the clocks to start working on them, they started to strike eight o'clock simultaneously. This occurred some hours and minutes past the correct time. What day and exact time did the clock mender set them originally?" [credited to Puzzles, Mathematical Diversions, and Brainteasters by Erwin Brecher]

I really had no idea how to solve this, so I decided to do it by brute force--try every possible combination of winding times (between 9:30 and 5 the previous week), minutes-per-day error in the first clock, minutes-per-day error in the second clock, and times the following Monday when both clocks hit eight o'clock at an exact minute. When I tried this it just took too darn long to run, so I had to optimize it by figuring out how often the first clock, for a given minutes-per-day error between -59 and +59, would hit an exact minute at the same instant as a real exact minute (for example, a clock that is 59 minutes per day slow will only intersect with a real minute once per day, but one that is 58 minutes slow will intersect with a real minute twice per day, one that is 56 minutes slow will intersect with a real minute 8 times a day, and one that is 48 minutes slow will intersect with a real minute every half hour. It has to do with the relative prime factoriality thinguminess of the daily error compare to the number 1440, the number of minutes in a day).

So after spending more than an hour kludge-ing something together, I came up with the following:

$ninethirtyam = (9 * 60) + 30
$fivepm = (17 * 60)
$eightpm = (20 * 60)
$eight = (8 * 60)
$minutesinday = (24 * 60)
[double]$minutesindaydouble = $minutesinday
$minutesinhalfday = $minutesinday / 2
$nextmondayopen = (7 * $minutesinday) + $ninethirtyam
$nextmondayclose = $nextmondayopen + $fivepm - $ninethirtyam
$clockmultiples = new-object int[] 120
for ($clockerr = -59; $clockerr -le 59; $clockerr++) {
  if ($clockerr -eq 0) { continue }
  [double]$clockrate = [double]($minutesinday+$clockerr) / $minutesindaydouble
  for ($realminutes = 1 ; $realminutes -le $minutesinday; $realminutes++) {
    [double]$clockminutes = [double]$realminutes * $clockrate
     if ([int]($clockminutes)*100000 -eq [int]($clockminutes*100000)) {
       break;
    }
  }
  $clockmultiples[$clockerr+60] = $realminutes
}
for ($days = 0; $days -le 4; $days++) {
  for ($time = $ninethirtyam; $time -le $fivepm; $time++) {
    $windtime = ($days*$minutesinday) + $time
    for ($clock1err = -59; $clock1err -le 59; $clock1err++) {
      if ($clock1err -eq 0) { continue }
      [double]$clock1rate = [double]($minutesinday+$clock1err) / $minutesindaydouble
      $multiple = $clockmultiples[$clock1err+60]
      $realtime = -(($nextmondayopen - 1 - $windtime) % $multiple) + $multiple + $nextmondayopen - 1
      for ( ; $realtime -le $nextmondayclose; $realtime += $multiple) {
        $clock1time = $windtime + [int]([double]($realtime-$windtime) * $clock1rate)
        for ($clock2err = -59; $clock2err -le 59; $clock2err++) {
          if (($clock2err -eq 0) -or ($clock2err -eq $clock1err)) { continue }
          [double]$clock2rate = [double]($minutesinday+$clock2err) / $minutesindaydouble
          $clock1display = $clock1time % $minutesinhalfday
          [double]$clock2timedouble = [double]$windtime + ([double]($realtime-$windtime) * $clock2rate)
          if ([int]([Math]::Round($clock2timedouble)*100000) -eq [int]($clock2timedouble*100000)) {
            $clock2display = [int]$clock2timedouble % $minutesinhalfday
            if (($clock1display -eq $eight) -and ($clock2display -eq $eight)) {
              write-host $windtime $realtime $clock1time $clock1err $clock2timedouble $clock2err
            }
          }
        }
      }
    }
  }
}

This is too ugly to fully explain here, but a couple of things:

  • Time is measured in minutes, starting at midnight on Monday of the first week.
  • The $clockmultiples array stores, at entry N+60, the number of minutes it takes a clock with a minutes-per-day error of N to intersect with a correct clock on a minute boundary.
  • In the innermost for loop, $realtime starts at the earliest time that the first clock will intersect with a real minute between 9:30 a.m. and 5 p.m. on the following Monday, and each loop iteration it increments to the next such time (that is, it increments by the appropriate entry in the $clockmultiples array).
  • The whole "multiply by 100000 when comparing" thing is because I was hitting some situations where a double and the corresponding int were not comparing equal when they should have been.

I don't doubt that there are ways to improve this algorithm by leaps and bounds; this is so clunky that you might say it contradicts my claim that you achieve good performance by messing up your design (but this is a very extreme example, keep in mind, so I stand by my linked-to argument; and since I only had to run it once in my life, and had the time to spare, there was no particular benefit achieved by further optimization once I had got the running time down below late March, which is the answer submission deadline). I let this monstrosity churn away overnight; I estimate it took seven or eight hours. And it did, miraculously, after all those different winding times and clock errors and all that, kick out one and only one answer.

(Or to be precise, it came up with two answers, that had the same winding and striking times but with the clock 1 and clock 2 daily errors reversed--but you know what I mean. Which makes me realize, now, that I could start the $clock2err loop at $clock1err+1, rather than -59, and cut out half the cycles. Oh well).

Posted by AdamBa at January 3, 2009 10:15 PM

Comments

10,256 for first question I believe.

Posted by: Peter at January 22, 2009 08:30 AM

Came up with this equation,

x = (1/39)[4(10^d) - 16]

where d is an integer and d > 0, which represents the number of digits in x.

For d = 5 we obtain the answer for x = 10246

Posted by: Pete at January 22, 2009 06:03 PM