|go ahead... be a heretic|
Spending Time on Saving Time [golf]by eyepopslikeamosquito (Canon)
|on Apr 01, 2012 at 07:14 UTC||Need Help??|
While goofing off the other day, idly browsing the classic 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 hybrid approach wins.
In this node, I'll focus on the lookup table approach.
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:
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:
To more precisely clarify the required behavior of a passing entry, see the test program provided 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 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:
Here are the three basic sequences required in this golf:
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:
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:
which matches the required number of trailing newlines for each clock face mark.
In this little sub-golf, replacing ($i<6)+($i&&$i<5) 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:
where --$| is the famous magical flip-flop. Can you find a shorter formula?
Can we do better via a lookup table? Well, noticing that the sequence changes from 102020202010 to 122221000000 when placed in index order, we can exploit empty values for the last six values like so:
where XX above is a string with ord values 169, 6. So good ol' vec looks like a winner here, weighing in at only 12 strokes! Generally, the vec 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.
Sub-problem 2: The Dreaded Ordering
To analyze this sub-problem as a separate, standalone golf, run the following test program:
which matches the dreaded ordering. Notice that this formula exploits that an uninitialized Perl variable, namely $x above, starts out with an empty value (undef).
As before, we can replace $_%2 with the $|-- magical flip-flop to produce an alternative 10-stroker:
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:
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 vec encoding of the previous section, because the dreaded ordering values have a wider range, 0..11. So a vec lookup table solution for the dreaded ordering looks like this:
where XXXXXX 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:
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 vec 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:
where XXXXXX is a string with ord values 120, 253, 125, 72, 1, 65 produces:
Notice that the lookup string solutions to all three sub-problems use a very similar vec 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.
The two best on-the-fly solutions found in my original analysis were a 101 stroke magic formula solution:
and a 102 stroke "baby cart" magic printf string solution:
Can we improve on these two via a lookup table? Yes!
The first obvious attempt is to combine the vec 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:
where AAAAAAAAAAAAAAAAAA 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 for keyword.
Here's an alternative that's just one stroke longer:
One more longer still is:
where BBBBBBBBBBBBBBBBBBB 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 vec.
Next, we can try using two separate vec's for the leading spaces and trailing newlines respectively, combined with our winning dreaded ordering formula:
where CCCCCC is a six character string with ord values 120, 253, 125, 72, 1, 65 and EEE is a string with ord values 0, 144, 106. 101 strokes. Using our map generator turns out to be one stroke longer:
where FF 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:
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:
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 index function! And thus avoid having to generate it. Let's see how that might look:
where GGGGGGGGGGGGGGGGGGGGGG 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.
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:
where DDDDDDDDDDDD is a twelve character string with ord values 8, 21, 37, 54, 70, 83, 92, 75, 56, 38, 23, 13 and FF is a string with ord values 169, 6. That reduces this approach from 103 down to 100 strokes.
As discussed above and in 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.