Friday, July 15, 2011

Ruby magic

I learned ruby for my internet programming class a year or two ago. I built a pretty cool rails app, and generally liked the features, but never really came back to it. I definitely developed some holy-envy for some of the dynamic features and magic that it has.

In the Utah Software Craftsmanship Group last week, we decided to make our next book we read Seven languages in seven weeks. The first chapter in that book is Ruby, so I was super excited to dig in and learn more of the nitty-gritty. Somebody pointed out Ruby koans as a great way to learn ruby, and I must absolutely agree. In the first three files alone, I have learned tons of the intricacies of the language, but also been a bit confused on some others.

For example: this here was quite confusing until I did some research on stackoverflow.

array = [:peanut, :butter, :and, :jelly]
array[0,2]  => [:peanut, :butter] #OK!
array[2,0]  => [] #OK!
array[2,20] => [:and, :jelly] #OK!
array[4]    => nil #OK!
array[5,0]  => nil  #Looks good
array[4,0]  => [] #WTF??!?!?. 

as lines 6 and 7 are both out of bounds, it was dang confusing as to why they would be different. Luckily I'm not the first to have this question. Stackoverflow quickly answered my worries and helped make (a little) sense out of it. If you consider the index as the spaces between elements, array[4,0] starts just after the last element, but has nothing after it, while array[5,0] has no elements before or after it. Still not sure if I agree with that decision, but it makes some sense.

My favorite bit so far though is this:

firstName, lastName = ["John","Smith"]
firstName, lastName = lastName, firstName

I've always known about these compound assignments, and I rather like them when they are not abused horribly. I always thought though that it was sugar for:

firstName, lastName = lastName, firstName

#is same as

firstName = lastName
lastName = firstName

But that is not so. It does more magic than that because without caching the results the name would become "Smith, Smith", not "Smith, John". To really get the in place swapping effect something like this is required:

temp1 = lastName
temp2 = firstName
firstName = temp1
lastName = temp2

Obviously the language designers anticipated this use, and put a generous sprinkling of magic in. I could do more experiments in putting stronger side-effects in the right hand expressions, as now I am a bit curious if it is as simple as my last snippet, or if there is even more magic going on. Maybe I'll do that in the future.

Bottom line is: Ruby is fun. I'm learning a lot.

Tuesday, May 3, 2011

Metaprogramming in Piet

I have always loved the Piet programming "language". It allows for the encoding of programs into a colorful image that resembles abstract art. It is the perfect mating of my love for coding and my love for epileptic fit inducing colors.

Quite a while ago I had the idea to implement a BrainF**k interpreter in Piet. I got halfway through a prototype before it got too complicated and I lost interest in the project for a while. Fast-Forward a few months and I find that it has now been done, no less than three times. I thought it would be a really cool way to show off the power of the Piet language. Seeing as that has now been done, I need to up my ante a bit.

What other crazy, esoteric language could I implement? What better choice than Piet itself? I can't think of one. I realized that npiet, the standard Piet interpreter, can handle ppm files with absolutely no problem. That essentially allows me to interact with images as strings of text, without having to muck about with decoding and encoding difficult image formats (although that is technically possible). In order to get to the point of a Piet interpreter written in Piet I need some more tools first, so I don't rip my brains out. Hopefully I can reach that lofty goal someday.

One discovery that helped me a lot was this blog post about QuickPiet. It is a language to create and debug algorithms on the Piet stack without having to worry about the spatial complications of actually laying out an image. I made a quick Piet interpreter, and made a few additions of my own, like modifying the way the goto command works. It is definitely possible to programatically transform a QuickPiet program into a working image, but I found the result looks mechanical, and is generally less artsy and less fun.
I decided a first step in exploring Piet meta-programming would be to try and write a Piet program that generates another Piet program. I decided to make a program that will accept any string as input, and output a Piet program that will also output that string. Rather worthless, I know, but valuable as a proof that it is possible.

So I coded it up in quick piet until I was fairly confident that it worked. The good thing about quick piet is that is removes all of the space and layout constraints that the image requires, and lets you just worry about the algorithms. So I had about 600 lines of quick piet that appears to work. I wrote a normalization engine to separate it into distinct labels, make all implicit jumps explicit, and generally clean it up. I took the normalized output, and a graph of which blocks lead to which other blocks, and I proceeded to lay it all out by hand (starting over twice when I got waay too lost to continue), and finally I got this little masterpiece:

That program will read all input until it receives a two quotation marks. It will then generate a valid Piet program (as a PPm image) that will in turn output all of the text between the quotation marks. So if I give it the input "Hello, World!", It will give me the following as a result:
Which will of course output "Hello, World!".
It seems to be pretty highly scalable, although a bit slow. For instance, here is a program that generates the declaration of independence:
And here is a real gem. This one outputs a piet program that will in turn output "Hello, World". I would try and wrap it one more level deeper, but I'm afraid the universe might explode if I do so. The image size is something like 55000x116, so it doesn't render very well in a blog. If you want to download it it is here.

Saturday, August 14, 2010

Monkey IslandTM Optimality Part 3

Last week I quite easily found an optimal path through the first part of Monkey IslandTM 2. Moving on the second episode, I ran into difficulties.

First off, the map is much expanded. I now have three islands available to me, so the search space has gotten much larger. The map, with my (somewhat arbitrary) travel costs now looks like this:

Furthermore, there are a ton more objectives:

If you color them by Island, you see this:

My hopes of an easy solution were dashed when I looked at this last graph and found a chain that required six island changes to get through the graph. Hopefully we can stick fairly close to that.

I entered all of the objectives into my system as quickly as I could and hit some problems:

  1. It ran slow.
  2. It ran reaaaallly slow.

The first act ran in a matter of seconds, but the second one, with the increased complexity seemed to take forever. I got lazy in implementing the search. To choose a node to explore I was resorting the list of possibilities on every iteration. This caused the search to slow down the further it got into it, and once there were about 16,000 nodes under consideration it pretty much stopped cold.

Once I swapped out my crappy list for a proper priority queue, I got much better search speed, but still was far from a solution. After 15 minutes of running and almost 7 million nodes considered, I got an OutOfMemory exception, because I was storing a list of nodes I had already considered to avoid repetition. I got to implement one of the cooler data structures I know of (the Directed Acyclic Word Graph, and finally I received a solution.

This is guaranteed to be optimal if my map weights make any sense, and if I did not overly constrain the search by the way I entered in the objectives. To the best of my knowledge this is a fairly good path. I will let you know how it goes once I play through it completely.

Here it is:

  1. Get Parrot Chow
  2. Go to BoatPhatt
  3. Go to Wharf
  4. Get Arrested(Automatic)
  5. Pull Mattress
  6. Get Stick
  7. Get Bone
  8. Get Key
  9. Unlock Cell
  10. Get Gorilla Envelope
  11. Get Manilla Envelope
  12. Open Gorilla
  13. Open Manilla
  14. Go to Wharf
  15. Go to RouletteAlley
  16. Watch Roulette
  17. Go to Wharf
  18. Follow dude
  19. Open Peephole
  20. Get winning Number
  21. Go to Wharf
  22. Go to RouletteAlley
  23. Win Cash
  24. Go to Wharf
  25. Go to SecretAlley
  26. Get Number
  27. Go to Wharf
  28. Go to RouletteAlley
  29. Win Invitation
  30. Go to Wharf
  31. Go to Library
  32. Get Lens
  33. Remember Hex Book(r-recipes)
  34. Remember Shipwrecks(d-disasters)
  35. Check Out Books
  36. Go to Wharf
  37. Go to BoatPhatt
  38. Go to BoatBooty
  39. Go to Ville
  40. Get leaflet from Kate
  41. Go to CostumeShop
  42. Get Costume
  43. Go to Ville
  44. Go to Shop
  45. Buy Saw
  46. Buy Horn
  47. Buy Sign
  48. Talk to pawn owner about trades
  49. Use chow on hook
  50. Get Mirror
  51. Go to Ville
  52. Go to MarleyMansion
  53. Present Costume and Invitation
  54. Go to MarleyBack
  55. Push Trash Can
  56. Run around to kitchen
  57. Get Fish
  58. Run around to front
  59. Get Map Piece
  60. Go outside
  61. Sweet Talk Elaine
  62. Go to MarleyLounge
  63. Go to MarleyMansion
  64. Chase Map Piece
  65. Get Dog
  66. Go to MarleyLounge
  67. Go to MarleyUpstairs
  68. Get Oar
  69. Go to MarleyLounge
  70. Go to MarleyMansion
  71. Go to BigTree
  72. Attempt to climb tree
  73. Get broken oar
  74. Go to BoatBooty
  75. Go to BoatScabb
  76. Go to Bridge
  77. Go to carpenter
  78. Give oar to carpenter
  79. Go to Bar
  80. Use banana on metronome
  81. Get blue and yellow drinks
  82. Pick up monkey
  83. Go to Wally
  84. Give lens to wally
  85. Go to Cleaners
  86. Saw Pegleg
  87. Go to Carpenter
  88. Get Hammer
  89. Get Nails
  90. Go to BoatScabb
  91. Go to BoatPhatt
  92. Go to Wharf
  93. Put leaflet on wanted poster
  94. Get near-grog from envelope
  95. Free Kate
  96. Go to Wharf
  97. Go to Pier
  98. Challenge Fisherman
  99. Give fish and Win
  100. Go to Wharf
  101. Go to BoatPhatt
  102. Go to BoatBooty
  103. Go to Ville
  104. Go to Spit
  105. Switch Flags
  106. Win Spitting Contest
  107. Go to Ville
  108. Go to Shop
  109. Trade plaque
  110. Go to Ville
  111. Read coordinates for mad monkey
  112. Charter ship and get masthead
  113. Go to Stans
  114. Nail Stan in coffin
  115. Get Crypt key
  116. Go to Ville
  117. Go to Shop
  118. Trade masthead for map
  119. Go to Ville
  120. Go to Cliff
  121. Fish Up Map
  122. Go to Ville
  123. Go to BigTree
  124. Climb Tree
  125. Get Telescope
  126. Use Dog to find map
  127. Go to BoatBooty
  128. Go to BoatPhatt
  129. Go to Mansion
  130. Go to MansionLobby
  131. Trick Guard
  132. Go to GovernersRoom
  133. Swap Books
  134. Go to MansionLobby
  135. Go to Mansion
  136. Go to Waterfall
  137. Go to WaterfallTop
  138. Use monkey wrench on valve
  139. Go to Waterfall
  140. Go to Cottage
  141. Cheat at drinking contest
  142. Open Window
  143. Put mirror in frame
  144. Put telescope in statue
  145. Push correct brick
  146. Get Map Piece
  147. Go to Wharf
  148. Go to BoatPhatt
  149. Go to BoatScabb
  150. Go to Cemetery
  151. Use Key in Crypt
  152. Go to Crypt
  153. Read Pirate quotes
  154. Open Coffin
  155. Get Ashes
  156. Go to Cemetery
  157. Go to Swamp
  158. Go to VoodooShack
  159. Pick up ash2Life Jar
  160. Talk to voodooLady and give book
  161. Go to Swamp
  162. Go to Cemetery
  163. Go to Crypt
  164. Use ash2Life on ashes
  165. Go to Cemetery
  166. Go to Beach
  167. Go to WeenieHut
  168. Use key at weenie hut
  169. Turn Off Gas
  170. Go to Beach
  171. Go to Cemetery
  172. Go to Crypt
  173. Revive rapp and get mapp
  174. Go to Cemetery
  175. Go to Bridge
  176. Go to Wally
  177. Give 4 pieces to Wally

This path has 7 island changes in it, which is not too shabby. The "speed guide" I used to construct my objectives graph changed islands 8 times, so I may be on to something. I completed this part of the quest in only 46 minutes, bringing my total to this point up to just 58 minutes.

Saturday, August 7, 2010

Optimal According to What?

Last time, I introduced the problem of finding an optimal path through Monkey IslandTM 2. If there's one thing I learned in College, it is that "optimal" can mean many things, and it is often best to specify specifically what you wish to optimize. In this case I wish to minimize the time spent traveling from screen to screen. I especially don't want to go to the larger map screens very often, and I most definitely do not want to move between islands any more than is absolutely necessary.

In order to more precisely define what I wish to optimize, consider the following simple score system:

  • It costs one point to complete any objective.
  • To travel from one location to another adjacent location costs some number of points greater than or equal to one.
Using this system, and trying to minimize score, the absolute lowest cost would be if all objectives were in the same location and I don't have to move at all. My score would then simply be the number of objectives. Any traveling you do on top of that acts as a penalty and brings your score up.

The first thing I needed is a discretization of the world to give values to the penalties you accrue for traveling. I painstakingly mapped out the world, and applied some serious guestimating to come up with this graph for the first act's locations:

This is not perfect by any means, but I feel it is a good approximation of the required times to move from place to place. It at least gives us some values to use while performing our search. Tweaking the criteria could potentially help us finish faster, but we'll just assume this is good enough for now.

The next thing I need to solve this problem is a list of the required objectives. This was created painstakingly by consulting a walkthrough and adding each step as an objective, making careful notes of all prerequisite objectives, and the locations where they occur. Once I have all this information I am ready to make a search.

I chose to implement a simple A* search because it is good for this job, and it has code readily available on wikipedia.

A search state can be identified as a location and a list of objectives that have already been completed. The cost function is calculated as described above (travel costs + objective costs), and the heuristic function is simply the number of uncompleted objectives. On each step I can either complete all available objectives at my current location, or if there are no available objectives, move to an adjacent location to my current one.

Using this method I am guaranteed optimality (according to my cost function above), and I get a fairly nice path:

  1. Get shovel
  2. Go to BarKitchen
  3. Get knife
  4. Go to Wally
  5. Get monocle
  6. Get paper
  7. Go to Cleaners
  8. Get bucket
  9. Go to Bar
  10. Talk to bartender about business
  11. Get spit with paper
  12. Go to Bridge
  13. Go to Beach
  14. Get stick
  15. Go to Swamp
  16. Get swampy water in bucket
  17. Go to Cemetery
  18. Go to CemeteryHill
  19. Dig up grave
  20. Go to Cemetery
  21. Go to Bridge
  22. Go to Hotel
  23. Use knife on rope
  24. Get cheese squiggles
  25. Go to LargosRoom
  26. Get Toupee
  27. Rig door with bucket of mud
  28. Go to Hotel
  29. Go to Cleaners
  30. Watch largo at dry cleaner
  31. Go to Hotel
  32. Go to LargosRoom
  33. Get Laundy ticket
  34. Go to Hotel
  35. Go to Cleaners
  36. Get Largo's Laundry
  37. Go to Bridge
  38. Go to Swamp
  39. Go to VoodooShack
  40. Get string
  41. Talk to voodoo lady about doll
  42. Give spit
  43. Give clothes
  44. Give toupee
  45. Give bone
  46. Go to Swamp
  47. Go to Bridge
  48. Go to Cleaners
  49. Open box
  50. Use stick and string with box
  51. Put cheese squiggle in box
  52. Pull string (wait for rat)
  53. Open box get rat
  54. Go to BarKitchen
  55. Put rat in soup
  56. Go to Bar
  57. Get a job (order stew)
  58. Go to Hotel
  59. Go to LargosRoom
  60. Stab largo
  61. Go to Swamp
  62. Go to BoatScabb
  63. Give Monocle and charter ship

This was calculated in around 15 seconds on a non-special computer, and it was completed in just over 13 minutes, with distractions. I can't see any way to improve on this path.

The next step will be to put in all the objectives for the next act (which has a considerably more complicated objectives graph) and see how it does. Wish me luck.

Friday, August 6, 2010

Optimal Path for Monkey IslandTM

You may or may not be aware that LucasArts has recently re-released the first two episodes in the Monkey IslandTM series. The special editions are complete renovations of the originals, with new graphics and voice-overs, but are otherwise identical. You can even switch back and forth between the original graphics and the new ones at any time with a single key-press, and it is absolutely seamless.

If you have enjoyed the series in the past, you would definitely enjoy the refreshed version. The graphics are smooth, and the experience is like what you remember. If you have never played, or heard of Monkey IslandTM, then shame on you. Get the special edition and play through it with the old graphics first.

One new thing that was added to Monkey IslandTM 2 was a set of Steam achievements. One of the harder ones to get is to complete the game in under three hours. I did not make it really even close on my first play-through, because I was trying to enjoy the game. Now, though, it's business time. This game is really quite large. There is a good deal of sailing from island to island, and the nerdmonger in me is constantly asking me to figure out a way to minimize all that.

Sure, I could easily do it all from memory in under 3 hours now, but that's no fun. I have enough deep cs background that I should be able to solve a simple problem like this fairly easily, shouldn't I? Is it harder than I thought? Its just a traveling salesman problem, isn't it?

Here's a teaser - A graph of all necessary objectives to complete Chapter One: The Largo Embargo:

Locations are not shown there, but I am trying to complete all objectives while minimizing time spent walking.

Stay tuned for the thrilling continuation.