• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Abbott's Revenge

 
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
One cool resource I've found for interesting programming questions is The online-judge problem set archive. Although Java support for the online submission portion of the site leaves a lot to be desired, (currently only Java 1.2 is supported with very limited support for java.io.* operations), there are plenty of problems that span a whole range of difficulties. The problem I'm currently pounding my head against is problem #816 Abbott's Revenge. This problem combines a slew of programming goodies, from parsing a domain-specific language, to finding a good abstraction of the problem (my current headache), to discovering a good algorithm to solve the maze. I figured it might be fun to discuss one or several of the interesting facets of this problem here.

To the mods: I'm not sure if its OK to post problems from this site here, but I figured since these weren't active contest problems, but more like individual programming brain teasers it might not be a problem. There are no prizes associated with solving the problems as far as I'm aware, just the general feeling of accomplishment. If it is an issue, just let me know and I'll cease and desist.
 
Garrett Rowe
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
More fun interactive mazes designed by Robert Abbott can be found here.
 
Garrett Rowe
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
As far as the problem abstraction goes, this is what I'm currently thinking.

Maybe I'll use this as a jumping-off point and see where it leads me, although I'm sure the TDD guys will say I'm getting way ahead of myself. I just not as comfortable with their style yet.
 
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Garrett,

On monday saw your post at work and as soon as i got home had to spend a few minutes banging this out in python - it's a great classic problem with a twist.

How goes it for you?

Just for my own interest. Did you use a forwards or backwards evaluation approach to solving the path (did backwards myself)? And as to enumerating the solution domain did you use a depth first search or breadth first search (since it seems to want a minimal solution, i did the BFS and punted at the first solution).

thanks for the link
 
Ranch Hand
Posts: 376
Scala Monad
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Very interesting... It hook me up immediately!
Seems "easy" to solve : create a directed graph where the nodes represents the "hallways" and the arcs the "turns" connecting them (Yes, is somehow the "complement" of the maze's draw). Then, with Dijktra's algorithm should be a piece of cake (and is DFS)
Too lazy to code it right now, later I'll do it as an excuse to practice Ruby.
 
Ranch Hand
Posts: 266
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for posting this fun puzzle! For those interested, here's how I solved it:
 
reply
    Bookmark Topic Watch Topic
  • New Topic