Re: The golf course looks great, my swing feels good, I like my chances (Part VI)

[eyepopslikeamosquito]

A few weeks after posting this node, I noticed that Korea's leading golfer, "leonid", had jumped from 118 strokes to 111 strokes, thus snatching the Ruby lead from flagitious and me.

To respond to this provocation, I began by staring at my 112 stroker:

r=*$<;'XXXXXXXXXXXX'.each_byte{|i|$><<"%#{327%i/9}c"%
'ohmx'[1>>(i-r.to_i)%12^2&2<<i%12-r[3,2].to_i/5]+$/*(i/85)}

The most obvious candidate for improvement here is the ungainly expression in 'ohmx'[expr], namely:

1>>(i-r.to_i)%12^2&2<<i%12-r[3,2].to_i/5

which can be clarified somewhat by writing as:

1>>(i-h)%12^2&2<<i%12-m

where h represents hours (0..23) and m minutes (0..11). How to shorten?

Though relying on inspiration in cases like these might work on a good day, a more dependable approach is to write a program to search for shorter solutions. Accordingly, I wrote the following Ruby brute force searcher:

# Search for Ruby solutions by building expressions from the sym
# and numsymop arrays below, then evaluating them (via eval).
#              0, 11,   1, 10,   2,  9,   3,  8,   4,  7,   5,   6
i_arr    = [ 120, 47, 253, 22, 194, 21, 183, 44, 196, 55, 125, 246 ]
sym      = [ '*', '/', '%', '+', '-', '>>', '<<', '&', '^', '|' ]
numsymop = (-12..12).to_a
numsymop.unshift('i'); numsymop.unshift('-i'); numsymop.unshift('~i')
numsymop.unshift('m'); numsymop.unshift('-m'); numsymop.unshift('~m')
for op2 in numsymop
  for s2 in sym
    $stderr.print "#{op2} #{s2}\n"
    for op3 in numsymop
      for s3 in sym
        for op4 in numsymop
          for s4 in sym
            for op5 in numsymop
              expr = op2.to_s + s2 + op3.to_s + s3 + op4.to_s + s4 + o
+p5.to_s
              i = 120; m = 0    # (d = 0)
              c_expr = "i=#{i};m=#{m};" + expr
              veq1 = -4242
              begin
                veq1 = eval(c_expr)
              rescue
              end
              next if veq1 == -4242
              i = 47; m = 11   # (d = 11)
              c_expr = "i=#{i};m=#{m};" + expr
              veq2 = -4242
              begin
                veq2 = eval(c_expr)
              rescue
              end
              next if veq2 == -4242
              next if veq1 != veq2
              i = 120; m = 11   # (d = 0)
              c_expr = "i=#{i};m=#{m};" + expr
              vneq1 = -4242
              begin
                vneq1 = eval(c_expr)
              rescue
              end
              next if vneq1 == -4242
              next if vneq1 == veq1
              i = 47; m = 10   # (d = 11)
              c_expr = "i=#{i};m=#{m};" + expr
              vneq2 = -4242
              begin
                vneq2 = eval(c_expr)
              rescue
              end
              next if vneq2 == -4242
              next if vneq1 != vneq2
              good = 1
              for i in i_arr
                d = i % 12
                m = d
                c_expr = "i=#{i};m=#{m};" + expr
                veq2 = -4242
                begin
                  veq2 = eval(c_expr)
                rescue
                end
                if veq2 == -4242
                  good = 0
                  break
                end
                if veq1 != veq2
                  good = 0
                  break
                end
              end
              next if good == 0
              for i in i_arr
                d = i % 12
                for m in 0..11
                  next if m == d
                  c_expr = "i=#{i};m=#{m};" + expr
                  vneq2 = -4242
                  begin
                    vneq2 = eval(c_expr)
                  rescue
                  end
                  if vneq2 == -4242
                    good = 0
                    break
                  end
                  if vneq1 != vneq2
                    good = 0
                    break
                  end
                end
                break if good == 0
              end
              next if good == 0
              print "woohoo: #{expr}: veq=#{veq1} vneq=#{vneq1}\n"
              $stdout.flush
            end
          end
        end
      end
    end
  end
end

As an aside, writing "eval" search programs like these seems to be a good way to unearth bugs in dusty corners of a language; at least, I had to remove '**' from the sym array above to workaround various random crashes and hangs of the Ruby interpreter.

Anyway, after dutifully chugging away for several hours, the above program did find a lucky hit, namely:

woohoo: ~m%i%12/11: veq=1 vneq=0

Further simple variations of this search program found new solutions for the "hours" portion of the expression also, such as:

(i-h)%12/~i

Combining these two new expressions enabled me to shorten the overall expression as shown below:

1>>(i-h)%12^2&2<<i%12-m     # original
(i-h)%12/~i^~m%i%12/11      # new and improved

and thus match leonid's 111 strokes via:

r=*$<;'XXXXXXXXXXXX'.each_byte{|i|$><<"%#{327%i/9}c"%
'hxmo'[(i-r.to_i)%12/~i^~r[3,2].to_i/5%i%12/11]+$/*(i/85)}

Of course, I have no idea if this is the same one stroke improvement that leonid found. If not, and he reads this post, I expect shortly to watch him move ahead to 110 strokes. :)

My main point is that relying on inspiration alone, I doubt I would ever have thought of this new shortened solution. That is, writing and running little search programs like these is part and parcel of being a serious golfer.

Update: Some time later, I discovered an easier way to get to 111 by changing the way hours and minutes are extracted from stdin, as shown below:

r=*$<; r r[3,2]       # original
gets;~/:/; $_ $'      # new

By way of explanation, note that the Ruby gets function automatically sets $_. And, like Perl, ~/:/ automatically sets $'. Unlike Perl though, ~/:/ returns the (zero-based) index of the match. In this game therefore, ~/:/ always returns two (the index of : in, for example, 12:34).

At first glance, the new method looks like a step backwards because it consumes one more stroke than the original. As is often the case in golf though, a tactical trick is available to shorten it. By pure luck, you see, the original 2&2<<i%12-m expression contains two twos! So we can replace one of them with the return value of ~/:/ thus transforming the new approach from one stroke longer to one stroke shorter:

gets;'XXXXXXXXXXXX'.each_byte{|i|$><<"%#{327%i/9}c"%'ohmx'[1>>(i-$_.to
+_i)%12^~/:/&2<<i%12-$'.to_i/5]+$/*(i/85)}

Alas, this new tactical trick cannot be similarly applied to my shortened ~m%i%12/11 expression because, unluckily, it does not contain a two.

Python Update

Inspired by this new Ruby magic formula, I was later able to shave a stroke from my 127-stroke Python solution by shortening the last part of the magic formula from:

(i-int(r[:2]))%-12/42

to:

(i-int(r[:2]))%-12/i

This (cheating) 126-stroke Python "solution" is not correct for all possible inputs but has a good chance of passing the (poor) set of test data provided for this game. To clarify, I chose 42 in the original magic formula for artistic effect only; any number greater than eleven will do. Replacing 42 with i therefore works for eleven of the twelve string ord values, namely 48, 23, 85, 22, 86, 87, 20, 88, 31, 77, 78 ... but fails for the single ord value that is less than eleven, namely the 9 that forms the string's sixth character.

Hallvabo was kind enough to send me his two best solutions to this game. Here is his (second-placed) 128 stroke Python entry:

_=raw_input()
for c in'XXXXXXXXXXXX':n=ord(c);print 3459%n/9*' '+'ohmx'[n%13==int(_[
+:2])%12::2][n%13==int(_[3:])/5]+n%3*'\n',

where XXXXXXXXXXXX above is a string with ord values 130, 180, 92, 75, 197, 48, 185, 138, 134, 228, 148, 188. And here is an alternate hallvabo 128-stroker:

_=raw_input()
for c in'XXXXXXXXXXXX':n=ord(c);print 247%n/7*' '+'ohmx'[n%12==int(_[:
+2])%12::2][n%12==int(_[3:])/5]+n/72*'\n',

where XXXXXXXXXXXX above is a string with ord values 72, 71, 205, 34, 158, 9, 147, 20, 160, 43, 101, 186. Note that both these solutions require a leading 3-character BOM (0xef, 0xbb, 0xbf). Note too that hallvabo employed his favourite "slice and dice" trick once again, just as he did in 99 Bottles of Beer.

It never occurred to me to use "slice and dice" in this game. As it turns out, the two different techniques produce similar lengths, as indicated below:

[(i%12==int(r[3:])/5)^(i-int(r[:2]))%-12/42]
[-(i%12==int(r[3:])/5)^1>>(i-int(r[:2]))%12]
[i%12==int(r[3:])/5::2][i%12==int(r[:2])%12]
[i%12==int(r[3:])/5::2][1>>(i-int(r[:2]))%12]

[eyepopslikeamosquito]

While I'm still able to remember, I list below the other new (albeit unsuccessful) Ruby solutions I found while searching for the elusive 111 stroker. It's possible I've missed something and one of these attempts might be transformed from a loser into a winner.

The following solutions are all of a similar form to the original 111 stroker, namely:

r=*$<;'XXXXXXXXXXXX'.each_byte{|i|$><<"%#{327%i/9}c"%
'hxmo'[(i-r.to_i)%12/~i^~r[3,2].to_i/5%i%12/11]+$/*(i/85)}

where XXXXXXXXXXXX above is a string with ord values 120, 47, 253, 22, 194, 21, 183, 44, 196, 55, 125, 246. For clarity below, I show only the 'hxmo'[expr] expressions:

'hxmo'[(i-r.to_i)%12/~i^~r[3,2].to_i/5%i%12/11]
'ohmx'[1>>(i-r.to_i)%12^2&2<<i%12-r[3,2].to_i/5]
'hxmo'[(i-r.to_i)%12/-i^0**(i%12^r[3,2].to_i/5)]
'mxho'[1>>(i-r.to_i)%12^(i%12^r[3,2].to_i/5)/-i]
'mxho'[(r[3,2].to_i/5-i)%12/-i^1>>(r.to_i-i)%12]
'hxmo'[(i-r.to_i)%12/-i^1>>(2*r[3]+r[4]/53-i)%12]
'mxho'[(2*r[3]+r[4]/53-i)%12/-i^1>>(i-r.to_i)%12]
'ohmx'[1>>(i-r.to_i)%12^(i%12==r[3,2].to_i/5).id]

And here are some other random attempts:

r=*$<;'XXXXXXXXXXXX'.each_byte{|i|printf"%*c"+$/*(i/85),
327%i/9,'hxmo'[(i-r.to_i)%12/~i^~r[3,2].to_i/5%i%12/11]}

r=*$<;'XXXXXXXXXXXX'.each_byte{|i|$><<" "*(318%i/9)+
'hxmo'[(i-r.to_i)%12/~i^~r[3,2].to_i/5%i%12/11,1]+$/*(i/85)}

/:/!~gets;'XXXXXXXXXXXX'.each_byte{|i|$><<"%#{327%i/9}c"%
'hxmo'[(i-$_.to_i)%12/~i^~$'.to_i/5%i%12/11]+$/*(i/85)}

r=*$<;$><<"%#{327%J/9}c"%'hxmo'[~r[3,2].to_i/5%J%12/11^
(J-r.to_i)%12/~J]+$/*(J/85)while J='ohXXXXXXXXXXXX'[$.+=1]

r=*$<;loop{i="hmXXXXXXXXXXXX"[$.+=1];$><<"%#{327%i/9}c"%
'hxmo'[(i-r.to_i)%12/~i^~r[3,2].to_i/5%i%12/11]+$/*(i/85)}

r=*$<;'XXXXXXXXXXXX'.each_byte{|i|$><<"%*c"%[327%i/9,
(i%12==r.to_i%12??x:?o)&(i%12==r[3,2].to_i/5??}:?o)]+$/*(i/85)}

gets=~/:/;'XXXXXXXXXXXX'.each_byte{|i|print" "*(318%i/9),
(111+(i%12==$_.to_i%12?9:0)&111+(i%12==$'.to_i/5?14:0)).chr,$/*(i/85)}

Note that in the solutions above using 318 rather than 327, the XXXXXXXXXXXX string is a string with ord values: 120, 47, 253, 22, 194, 9, 183, 44, 196, 55, 125, 246.