Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Abbott's Revenge

 
Garrett Rowe
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
  • 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
  • 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
  • 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.
 
Steve Fahlbusch
Bartender
Posts: 605
7
Mac OS X Python
  • Mark post as helpful
  • send pies
  • 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
 
Gabriel Claramunt
Ranch Hand
Posts: 375
Monad Scala
  • Mark post as helpful
  • send pies
  • 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.
 
Piet Verdriet
Ranch Hand
Posts: 266
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for posting this fun puzzle! For those interested, here's how I solved it:
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic