perlmeditation eyepopslikeamosquito While goofing off the other day, idly browsing the classic [id://811919|Saving Time golf game], I realized some important analysis was missing. I'd been obsessed with magic formulae back then and hadn't properly investigated a lookup table approach. In most golf games you see, there is an ongoing battle between two competing approaches, namely a formula (often magic) and a lookup table (usually a string). Sometimes a [id://768354|hybrid approach] wins. In this node, I'll focus on the lookup table approach. The Problem To refresh your memory, the program in this game must draw an analogue clock face using the 24 hour digital time provided on stdin. The format of the input time is HH:MM followed by a single newline. An input time of 21:35, for example, is displayed as: <CODE> o o o o o h o o o m o o </CODE> If the hour and minute happen to fall on the same mark, they must be drawn with an 'x'. For example, 01:06 is rendered as: <CODE> o o x o o o o o o o o o </CODE> To more precisely clarify the required behavior of a passing entry, see the test program provided [id://785052|here]. Printing the Clock Face on the Fly In this node, I'll focus on printing the clock face on the fly. Though a two-dimensional array seems to produce the shortest solutions, that approach has already been analyzed to death [id://811919|previously]. Moreover, I find drawing the clock face on the fly morbidly fascinating for some reason, perhaps because the 0, 11, 1, 10, 2, 9, 3, 8, 4, 7, 5, 6 sequence is so annoying. As you can see below, there is no avoiding this dreaded sequence if you wish to print the clock face on the fly: <CODE> 0 11 1 10 2 9 3 8 4 7 5 6 </CODE> Here are the three basic sequences required in this golf: <table border="1"> <tr><th>Index</th><th>dreaded ordering</th><th>leading spaces</th><th>trailing newlines</th></tr> <tr><td>0</td><td>0</td><td>8</td><td>1</td></tr> <tr><td>1</td><td>11</td><td>4</td><td>0</td></tr> <tr><td>2</td><td>1</td><td>7</td><td>2</td></tr> <tr><td>3</td><td>10</td><td>1</td><td>0</td></tr> <tr><td>4</td><td>2</td><td>13</td><td>2</td></tr> <tr><td>5</td><td>9</td><td>0</td><td>0</td></tr> <tr><td>6</td><td>3</td><td>15</td><td>2</td></tr> <tr><td>7</td><td>8</td><td>1</td><td>0</td></tr> <tr><td>8</td><td>4</td><td>13</td><td>2</td></tr> <tr><td>9</td><td>7</td><td>4</td><td>0</td></tr> <tr><td>10</td><td>5</td><td>7</td><td>1</td></tr> <tr><td>11</td><td>6</td><td>8</td><td>0+</td></tr> </table> Notice that generating the dreaded ordering, the number of leading spaces, and the number of trailing newlines may be thought of as three separate sub-problems. Indeed, it is common in any complex golf to analyze smaller sub-problems separately before plugging them in to form a complete solution. Divide and conquer. Sub-problem 1: Trailing Newlines I trust the picture below clarifies the required number of trailing newlines to be printed after each clock face mark: <CODE> 1 0 2 0 2 0 2 0 2 0 1 0 </CODE> Note that the last zero above, corresponding to clock face mark six, can be any value greater than or equal to zero because all trailing newlines after the clock face is drawn are ignored. To analyze this sub-problem as a separate, standalone golf, simply run the following test program: <CODE> for my $i ( map {$_,11-$_} 0..5 ) { $x = ($i<6)+($i&&$i<5); printf "%2d: %d\n", $i, 0+$x; } </CODE> producing: <CODE> 0: 1 11: 0 1: 2 10: 0 2: 2 9: 0 3: 2 8: 0 4: 2 7: 0 5: 1 6: 0 </CODE> which matches the required number of trailing newlines for each clock face mark. In this little sub-golf, replacing <C>($i<6)+($i&&$i<5)</C> above with another (shorter) expression would enable you to take the lead. We can easily shorten the formula above by two strokes from 17 to 15 by eliminating one set of parens: <CODE> 12345678901234567 ($i<6)+($i&&$i<5) --$|+($i&&$i<5) --$|+($i<5)-!$i </CODE> where <C>--$|</C> is the famous [id://778841|magical flip-flop]. Can you find a shorter formula? Can we do better via a lookup table? Well, noticing that the sequence changes from <C>102020202010</C> to <C>122221000000</C> when placed in index order, we can exploit empty values for the last six values like so: <CODE> 123456789012345678 substr 122221,$i,1 (1,2,2,2,2,1)[$i] (1,(2)x4,1)[$i] vec'XX',$i,2 </CODE> where <C>XX</C> above is a string with ord values 169, 6. So good ol' <C>vec</C> looks like a winner here, weighing in at only 12 strokes! Generally, the <C>vec</C> function is too often overlooked in golf games, perhaps because it is little used outside of golf. So it seems that a lookup table defeats a formula in this sub-golf ... unless you can find a shorter formula, that is. In the spirit of TMTOWTDI, I would be interested to see different, even if longer, approaches to producing this sequence. <readmore> Sub-problem 2: The Dreaded Ordering To analyze this sub-problem as a separate, standalone golf, run the following test program: <CODE> for ( 0..11 ) { printf "%2d: %2d\n", $_, 0+$x; $x = 11-$x+$_%2; } </CODE> producing: <CODE> 0: 0 1: 11 2: 1 3: 10 4: 2 5: 9 6: 3 7: 8 8: 4 9: 7 10: 5 11: 6 </CODE> which matches the dreaded ordering. Notice that this formula exploits that an uninitialized Perl variable, namely <C>$x</C> above, starts out with an empty value (undef). As before, we can replace <C>$_%2</C> with the <C>$|--</C> [id://778841|magical flip-flop] to produce an alternative 10-stroker: <CODE> 1234567890 11-$x+$_%2 11-$x+$|-- </CODE> I can't find anything shorter though. Can you? Formula versus lookup table is an over-simplification in that sometimes you can generate a sequence. For example, the map below: <CODE> 12345678901234567 map{$_,11-$_}0..5 </CODE> generates the dreaded ordering. Though longer, this sequence generation is still competitive in this game because it allows other shortenings elsewhere in a complete solution, as we shall see later. What about a lookup table? Unfortunately, we need four bits, rather than just two for the trailing newline <C>vec</C> encoding of the previous section, because the dreaded ordering values have a wider range, 0..11. So a <C>vec</C> lookup table solution for the dreaded ordering looks like this: <CODE> 1234567890123456 vec'XXXXXX',$i,4 </CODE> where <C>XXXXXX</C> is a string with ord values 176, 161, 146, 131, 116, 101 ... which is six strokes longer than the formula. So this time the formula defeats the lookup string. One all. Sub-problem 3: Leading Spaces The on-the-fly leading space sequence of 8, 4, 7, 1, 13, 0, 15, 1, 13, 4, 7, 8 as in: <CODE> 8 4 7 1 13 0 15 1 13 4 7 8 </CODE> is all over the shop. So much so that I couldn't even begin to contemplate a short formula to produce it. As before though, a <C>vec</C> lookup string can do it easily because, luckily, all the leading space values happen to be less than 16 and so (just) fit into four bits. That is, running: <CODE> for my $i ( map {$_,11-$_} 0..5 ) { $x = vec'XXXXXX',$i,4; printf "%2d: %2d\n", $i, 0+$x; } </CODE> where <C>XXXXXX</C> is a string with ord values 120, 253, 125, 72, 1, 65 produces: <CODE> 0: 8 11: 4 1: 7 10: 1 2: 13 9: 0 3: 15 8: 1 4: 13 7: 4 5: 7 6: 8 </CODE> Notice that the lookup string solutions to all three sub-problems use a very similar <C>vec</C> construction, so it may be possible to combine them in the full solution. Golfers should always be on the lookout for any uniformity that might be exploited. Complete Solutions The two best on-the-fly solutions found in [id://811919|my original analysis] were a 101 stroke magic formula solution: <CODE> print$"x(318%$_/9),(($_-$`)%12?o:x)&($_%12^$'/5?o:'}'),$/x($_/85)for unpack<>!~/:/.C12,'XXXXXXXXXXXX' </CODE> and a 102 stroke "baby cart" magic printf string solution: <CODE> printf"%@{[.1*vec'XXXXXXXXXXXX',$_,8]}s",($_^$`%12?g:p)&($_^$'/5?g:u)|"H "for map{$_,11-$_}<>!~/:/..5 </CODE> Can we improve on these two via a lookup table? Yes! The first obvious attempt is to combine the <C>vec</C> solutions from sub-problems one, two and three above. When you do that, uniformly encoding 4 bits per value, you get to 100 strokes right away: <CODE> sub k{$k=vec'AAAAAAAAAAAAAAAAAA',$i++,4}print$/x k,$"x k,(k^$`%12?o:x)&($k^$'/5?o:"}")for<>!~/:/..11 </CODE> where <C>AAAAAAAAAAAAAAAAAA</C> is an eighteen character string with ord values 128, 16, 180, 112, 33, 161, 208, 34, 144, 240, 35, 129, 208, 36, 116, 112, 21, 104. Notice that we switched from trailing newlines to leading newlines to save one stroke, namely a space before the <C>for</C> keyword. Here's an alternative that's just one stroke longer: <CODE> print+($/x($k=vec'AAAAAAAAAAAAAAAAAA',$_,4),$"x$k,($k^$`%12?o:x)&($k^$'/5?o:"}"))[$_%3]for<>!~/:/..35 </CODE> One more longer still is: <CODE> map{$k=vec'BBBBBBBBBBBBBBBBBBB',$_,4;print$_%3?($"^='*')x$k:($k^$`%12?o:x)&($k^$'/5?o:"}")}<>=~/:/..36 </CODE> where <C>BBBBBBBBBBBBBBBBBBB</C> is a 19 character string with ord values 0, 8, 65, 11, 23, 18, 10, 45, 2, 9, 63, 18, 8, 77, 66, 7, 87, 129, 6. It's possible I've overlooked a shorter way to avoid multiple calls of <C>vec</C>. Next, we can try using two separate <C>vec</C>'s for the leading spaces and trailing newlines respectively, combined with our winning dreaded ordering formula: <CODE> print$"x(vec'CCCCCC',$z,4),($`%12^$z?o:x)&($'/5^$z?o:"}"),$/x(vec'EEE',$z=11-$z+$|--,2)for<>!~/:/..11 </CODE> where <C>CCCCCC</C> is a six character string with ord values 120, 253, 125, 72, 1, 65 and <C>EEE</C> is a string with ord values 0, 144, 106. 101 strokes. Using our <C>map</C> generator turns out to be one stroke longer: <CODE> print$"x(vec'CCCCCC',$_,4),($`%12^$_?o:x)&($'/5^$_?o:"}"),$/x(vec'FF',$_,2)for map{$_,11-$_}<>!~/:/..5 </CODE> where <C>FF</C> is a string with ord values 169, 6. Treating the Clock Face as a Long String There is yet another promising approach to this game: treat the clock face as a single long string. If you do that, the character positions in the string of each clock face mark are shown below: <CODE> 8 14 22 26 40 43 59 63 77 84 92 102 </CODE> with newlines at character positions: 9, 23, 24, 41, 42, 60, 61, 78, 79, 93. By ignoring newlines, we can reduce the string length to less than 100, the character positions now being: <CODE> 8 13 21 23 37 38 54 56 70 75 83 92 </CODE> How does that help? Well, if you place the clock face mark character positions in a lookup string in just the right order, you can derive the dreaded ordering from the return value of the Perl <C>index</C> function! And thus avoid having to generate it. Let's see how that might look: <CODE> print+($`%12^($x=index'GGGGGGGGGGGGGGGGGGGGGG',chr)?~$x?$x<12?o:$/:$":x)&($'/5^$x?o:"}")for<>!~/:/..102 </CODE> where <C>GGGGGGGGGGGGGGGGGGGGGG</C> is a 22 character string with ord values 8, 22, 40, 59, 77, 92, 102, 84, 63, 43, 26, 14, 9, 23, 24, 41, 42, 60, 61, 78, 79, 93. Note that the first twelve values in the string are the (ordered) clock face mark positions while the next ten are the position of each newline. This algorithm simply iterates through the 103 character clock face string, one character at a time, emitting a space, a newline, or a clock face mark (o, m, h, or x) at each character position. By a fluky coincidence, this program happens to be 103 characters in length, identical in size to the clock face string it draws! :) The bitwise string operations used in this solution are a bit tricky. Hopefully, the table below will help convince you they are all ok. In particular, note that SPACE (ord 32) has an especially lucky power of two bit pattern; bitwise and'ing any of the letters with it produces a SPACE. <table border="1"> <tr><th>letter</th><th>ord</th><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th></tr> <tr><td>newline</td><td>10</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr> <tr><td>space</td><td>32</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr> <tr><td>h</td><td>104</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td></tr> <tr><td>m</td><td>109</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td></tr> <tr><td>o</td><td>111</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td></tr> <tr><td>x</td><td>120</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td></tr> <tr><td>}</td><td>125</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>1</td></tr> </table> By the way, this character by character approach is especially well-suited to PHP (which does not have a string multiply operator) because it does not require any string multiplication. The idea for this solution was shown to me by leading PHP golfer ToastyX. Elegant though this solution is, using 22 characters for the lookup string is a bit extravagant. Can we shorten it somehow? We can in Perl simply by dropping the newlines from the lookup string and reverting to generating them via string multiply: <CODE> print~($x=index'DDDDDDDDDDDD',chr)?($`%12^$x?g:p)&($'/5^$x?g:u)|H.$/x(vec'FF',$x,2):$"for<>!~/:/..92 </CODE> where <C>DDDDDDDDDDDD</C> is a twelve character string with ord values 8, 21, 37, 54, 70, 83, 92, 75, 56, 38, 23, 13 and <C>FF</C> is a string with ord values 169, 6. That reduces this approach from 103 down to 100 strokes. Summary As discussed above and in [id://811919|my previous analysis], there are at least ten different ways to solve this problem in around 100 strokes. To me, that shows that this was a very well designed golf. Kudos to Arpad Ray for composing it. Also interesting is that from over 100 entries, only three golfers managed to get below 110 strokes, indicating that this was one of the more difficult golfs. References <ul> <li> [id://759963] <li> [id://761053] <li> [id://762180] <li> [id://763105] <li> [id://811919] <li> [id://814900] <li> [id://816630] <li> [id://785052] <li> [id://903641] </ul> <ul> <li> <a href="http://www.jakevoytko.com/blog/2008/08/25/code-golf-my-thought-process-on-saving-time/">jakevoytko Python Saving Time blog</a> <li> <a href="http://blachan.com/blog/code-golf-saving-time/">Abdulla Arif PHP Saving Time blog</a> <li> <a href="http://dinomite.net/2008/code-golf-saving-time/">Drew Stephens Perl Saving Time blog</a> <li> <a href="http://thingsithoughtidsharewithyou.blogspot.com/2009/07/some-code-golf.html">Tobias Lofgren Perl Saving Time blog</a> <li> <a href="http://codegolf.stackexchange.com/questions/3679/codegolf-com-saving-time">stackexchange saving time question</a> </ul> </readmore>