File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Programming Diversions and the fly likes Abbott's Revenge Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Abbott Watch "Abbott New topic

Abbott's Revenge

Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
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* 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.

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
More fun interactive mazes designed by Robert Abbott can be found here.
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
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

Joined: Sep 18, 2000
Posts: 601


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

Joined: May 26, 2007
Posts: 375

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.

Software Surgeon
Piet Verdriet
Ranch Hand

Joined: Feb 25, 2006
Posts: 266
Thanks for posting this fun puzzle! For those interested, here's how I solved it:
I agree. Here's the link:
subject: Abbott's Revenge
jQuery in Action, 3rd edition