RPCFN: Mazes (#5)

by Satish Talim on December 27, 2009

RubyLearning wishes all its readers and their friends and families a happy, healthy 2010. Thanks to everyone for the support and encouragement this year. It’s been a fun and rewarding year and we do appreciate all that you contribute to this site.

Ruby Programming Challenge For Newbies

RPCFN: Mazes (#5)

By Peter Cooper

About Peter Cooper

Peter CooperPeter Cooper (twitter) is the editor and curator of several Ruby sites including Ruby Inside, Rails Inside, and RubyFlow. They develop software that manages clinical research trials and associated data. They primarily code with Ruby on Rails. His background is in web development, mostly in Perl until ~2005 when he made the switch to Ruby.

Peter has this to say about the challenge:

RPCFN is designed to make you good at turning mental concepts into working Ruby code. If you can do that, the programming world is your oyster, and challenges like those presented with RPCFN are a great first (or second!) step. If I have any advice about how to approach the challenges, remember to keep it fun at all times, and if your solution isn’t working out, take a few steps back and be prepared to knock over your sandcastle and try a different approach. A common mistake in programming is to keep digging the same hole even deeper rather than finding a better place to dig :-) Try lots of holes instead; Ruby makes it easy.

Sponsors

This monthly programming challenge is co-sponsored by Backup My App, InformIT and Thoughtworks.

Backup My App

Backup My App is an automatic backup service for Ruby on Rails applications. You simply install the plugin to your Rails application and they handle the rest of the process. They store backup history for several weeks and you can restore any of them automatically. Try out their 1 GB plan for free. Backup My App has co-sponsored this challenge and is proud to make this contribution to the Ruby community.

InformIT

InformIT is the online presence of the family of information technology publishers and brands of Pearson, the world’s largest educational publisher. InformIT is home to the leading technology publishing imprints Addison-Wesley Professional, Cisco Press, Exam Cram, IBM Press, Prentice Hall Professional, QUE, and Sams. They also offer products geared towards the professional business audience from their publishing partners FT Press and Wharton School Publishing. Here you will gain access to trusted and quality content and resources from the authors, creators, innovators, and leaders of technology and business. Whether you’re looking for a book on a new technology, a helpful article, timely newsletters or access to the Safari Books Online digital library, InformIT has a solution for you.

Thoughtworks

ThoughtWorks kick-started the Agile business era with pioneering software delivery practices and world-leading open source software. Today, clients approach them to solve their toughest business problems, and they deliver some of the world’s most sophisticated custom applications. Their products division, ThoughtWorks Studios, was established in 2006 to make cutting-edge software development tools currently including Mingle (project collaboration), Cruise (continuous integration) and Twist (functional testing). Founded in 1993, ThoughtWorks is headquartered in Chicago, and has offices in Australia, Canada, China, Hong Kong, India, Sweden, United Kingdom and United States.

Prizes

  • The participant with the best Ruby solution (if there is a tie between answers, then the one who posted first will be the winner) will be awarded a printed copy of the book “Refactoring in Ruby” from InformIT and a free 10 GB account for a year from Backup My App.
  • One other participants with an equally good Ruby solution will be awarded any one of PeepCode’s Ruby on Rails screencasts.
  • From the remaining working Ruby solutions, three participants would be selected randomly and each one would be awarded any one of Pragmatic’s The Ruby Object Model and Metaprogramming screencasts.
  • All the participants in this challenge (except the participant with the best Ruby solution) will get a free 5 GB account for 6 months from Backup My App.

The five persons who win, can’t win again in the next immediate challenge but can still participate.

The Ruby Challenge

RPCFN

Introduction

Mazes are known to have challenged humans from as far back as the 5th century BC. There are many types of maze, but typically you need to find your way from a start point to an end point.

In this Ruby challenge, you will need to develop a class that can be used to solve mazes. Mazes will be provided as a string showing a graphical representation of the maze’s layout. Spaces are navigable, while # (pound) symbols are used to denote walls. In this challenge the letter “A” is used to mark the start point, and “B” the end point. Here’s an example of a maze contained within a string:

MAZE1 = %{#####################################
# #   #     #A        #     #       #
# # # # # # ####### # ### # ####### #
# # #   # #         #     # #       #
# ##### # ################# # #######
#     # #       #   #     # #   #   #
##### ##### ### ### # ### # # # # # #
#   #     #   # #   #  B# # # #   # #
# # ##### ##### # # ### # # ####### #
# #     # #   # # #   # # # #       #
# ### ### # # # # ##### # # # ##### #
#   #       #   #       #     #     #
#####################################}

The prior maze would be loaded into a Maze object like so:

Maze.new(MAZE1)

The Challenge

There are two parts to the challenge: you can choose to do one or both, depending on your skill level or how much time you have available.

  1. Implement a Maze#solvable? method that returns true/false depending on whether it’s possible to navigate the maze from point A to point B.
  2. Implement a Maze#steps method that returns an integer of the least number of “steps” one would have to take within the maze to get from point A to point B. “Steps” can only be taken up, down, left or right. No diagonals.

There are a number of ways to “solve” mazes but there’s a wide scope for you to be as straightforward or as clever as you like with this challenge (tip: I’d love to see some clever/silly solutions!). Your “solvable?” and “steps” methods could share algorithms or you might come up with alternate ways to be more efficient in each case. Good luck!

Note: Use the test suite to ensure your code interfaces in the right way. The test suite demonstrates how your class will be called and used.

The Test Suite

Your Maze class should be in maze.rb for the following test suite to work :-)

require 'test/unit'
require 'maze'

MAZE1 = %{#####################################
# #   #     #A        #     #       #
# # # # # # ####### # ### # ####### #
# # #   # #         #     # #       #
# ##### # ################# # #######
#     # #       #   #     # #   #   #
##### ##### ### ### # ### # # # # # #
#   #     #   # #   #  B# # # #   # #
# # ##### ##### # # ### # # ####### #
# #     # #   # # #   # # # #       #
# ### ### # # # # ##### # # # ##### #
#   #       #   #       #     #     #
#####################################}
# Maze 1 should SUCCEED

MAZE2 = %{#####################################
# #       #             #     #     #
# ### ### # ########### ### # ##### #
# #   # #   #   #   #   #   #       #
# # ###A##### # # # # ### ###########
#   #   #     #   # # #   #         #
####### # ### ####### # ### ####### #
#       # #   #       # #       #   #
# ####### # # # ####### # ##### # # #
#       # # # #   #       #   # # # #
# ##### # # ##### ######### # ### # #
#     #   #                 #     #B#
#####################################}
# Maze 2 should SUCCEED

MAZE3 = %{#####################################
# #   #           #                 #
# ### # ####### # # # ############# #
#   #   #     # #   # #     #     # #
### ##### ### ####### # ##### ### # #
# #       # #  A  #   #       #   # #
# ######### ##### # ####### ### ### #
#               ###       # # # #   #
# ### ### ####### ####### # # # # ###
# # # #   #     #B#   #   # # #   # #
# # # ##### ### # # # # ### # ##### #
#   #         #     #   #           #
#####################################}
# Maze 3 should FAIL


class MazeTest < Test::Unit::TestCase
  def test_good_mazes
    assert_equal true, Maze.new(MAZE1).solvable?
    assert_equal true, Maze.new(MAZE2).solvable?
  end

  def test_bad_mazes
    assert_equal false, Maze.new(MAZE3).solvable?
  end

  def test_maze_steps
    assert_equal 44, Maze.new(MAZE1).steps
    assert_equal 75, Maze.new(MAZE2).steps
    assert_equal 0, Maze.new(MAZE3).steps
  end
end

Requirements

This has to be a pure Ruby script, using only the Ruby Standard Libraries (meaning, no external Gems). You do not need to build a gem for this. Pure Ruby code is all that is needed.

How to Enter the Challenge

Read the Challenge Rules. By participating in this challenge, you agree to be bound by these Challenge Rules. It’s free and registration is optional. You can enter the challenge just by posting the following as a comment to this blog post:

  1. Your name:
  2. Country of Residence:
  3. GIST URL of your Solution (i.e. Ruby code) with explanation and / or test cases:
  4. Code works with Ruby 1.8 / 1.9 / Both:
  5. Email address (will not be published):
  6. Brief description of what you do (will not be published):

Note:

  • As soon as we receive your GIST URL, we will fork your submission. This means that your solution is frozen and accepted. Please be sure that is the solution you want, as it is now recorded in time and is the version that will be evaluated.
  • All solutions posted would be hidden to allow participants to come up with their own solutions.
  • You should post your entries before midnight of 19th Jan. 2010 (Indian Standard Time). No new solutions will be accepted from 20th Jan. onwards.
  • On 20th Jan. 2010 all the solutions will be thrown open for everyone to see and comment upon.
  • The winning entries will be announced on this blog before end of Jan. 2010. The winners will be sent their prizes by email.

More details on the RPCFN?

Please refer to the RPCFN FAQ for answers to the following questions:

Donations

RPCFN is entirely financed by RubyLearning and sometimes sponsors, so if you enjoy solving Ruby problems and would like to give something back by helping with the running costs then any donations are gratefully received.

Click here to lend your support to: Support RubyLearning With Some Love and make a donation at www.pledgie.com !

Acknowledgements

Josh Software Pvt. Ltd.

Special thanks to:

  • Peter Cooper.
  • Sponsors Backup My App, InformIT and Thoughtworks.
  • Josh Software Pvt. Ltd. an upcoming Rails start-up in Pune, India for giving us access to a private repository on GitHub to store all the submitted solutions.
  • The RubyLearning team, namely Jeff Savin (Canada), Mareike Hybsier (Germany), Michael Kohl (Austria), Peter Crawford (Italy) and Satoshi Asakawa (Japan).

Questions?

Contact Satish Talim at satish [dot] talim [at] gmail.com OR if you have any doubts / questions about the challenge (the current problem statement), please post them as comments to this post and the author will reply asap.

The Participants

There are two categories of participants. Some are vying for the prizes and some are participating for the fun of it.

In the competition

  1. Dmytro Shteflyuk, Ukraine
  2. Oleksandr Manzyuk, Ukraine
  3. Rajesh Kumar, USA
  4. Aleksey Gureiev, Australia
  5. Stu Henry, USA
  6. Douglas Barbosa Alexandre, Brazil
  7. Gimi Liang, China
  8. Aldric Giacomoni, USA
  9. Othmane Benkirane, Morocco
  10. Paul Smith, England
  11. Marc Seeger, Germany
  12. Marc Minneman, USA
  13. Tim Rand, USA
  14. Amr N Tamimi, Palestine
  15. Ian Stewart, USA
  16. Toni Tuominen, Finland – declared winner (randomly selected)
  17. Alexander Klink, Germany
  18. Paul McKibbin, U.K.
  19. Srikanth P Shreenivas, India
  20. Suraj Dhakankar, India
  21. Thomas Marek, Germany
  22. Rainer Thiel, New Zealand – declared winner (randomly selected)
  23. Guillaume Petit, France
  24. Paul Damer, USA
  25. Dmitriy Nagirnyak, Australia
  26. Christian Knappskog, Norway
  27. René Scheibe, Germany
  28. Pranav Singh, Canada
  29. Yuri Omelchuk, Ukraine
  30. Benoit Daloze, Belgium
  31. Himansu Desai, USA
  32. Raoul Felix, Portugal – declared winner (second best solution)
  33. Javier Blanco Gutiérrez, Spain
  34. Brad O’Connor, Australia
  35. Leonardo Bessa, Brazil
  36. Radek Kotlarek, Ireland
  37. Krzysztof Kotlarek, Poland
  38. James Daniels, USA
  39. Philippe Antras, France
  40. Bill Kayser, USA
  41. Jean-Christophe Cyr, Canada
  42. Patrick McKenzie, Japan – declared winner (best solution)
  43. Paul Gallagher, Singapore
  44. Clément Julliard, France – declared winner (randomly selected)

Just for Fun

  1. Satoshi Asakawa, Japan
  2. Alpha Chen, USA
  3. Juan Villanelo, Chile
  4. Dominik Masur, Germany
  5. Tamas Szabo, Australia
  6. Cary Swoveland, Canada

The Winners

Winners

Congratulations to the winners of this Ruby Challenge. They are:

Previous Challenge

RPCFN: Ruby**Fun (#4) by Michael Kohl.

Update

  • This challenge is now closed. Peter Cooper has a working solution to this problem. This is not a “perfect” or the sole “correct” solution, but just one way of doing it.
  • The (#6) challenge by John Trupiano, USA is scheduled for 1st Feb. 2010.

Technorati Tags: , , , , ,

Posted by Satish Talim

{ 158 comments… read them below or add one }

Rhyhann December 27, 2009 at 3:19 pm

This is an *awesome* challenge for every newbie. Thank you very much, Peter Cooper and all the RPCFN team!

Reply

Amr N Tamimi December 27, 2009 at 5:23 pm

AWESOME!!!!

Reply

Dmytro Shteflyuk December 27, 2009 at 6:21 pm

Solution (#1):

Dmytro Shteflyuk, Ukraine
Original: https://gist.github.com/fc0d1e2b23287ec1f682
Forked: https://gist.github.com/aa58f6b7450915f14549
Code works with Ruby 1.8

Reply

Jeff Savin January 20, 2010 at 7:15 am

Dmytro used the “classic painting algorithm” to solve the maze and did a good job. Every test passed with flying colors.

Reply

Oleksandr Manzyuk December 27, 2009 at 10:55 pm

Solution (#2):

Oleksandr Manzyuk, Ukraine
Original: https://gist.github.com/4bec4e877f8024746a29
Forked: https://gist.github.com/bdd72dea1648d41eaab6
Works with: Ruby 1.9
Brief description: Finding the least number of steps one would have to take within the maze to get from point A to point B can be interpreted as a problem of finding the distance between 2 vertices in a certain graph, for which Dijkstra’s algorithm can be used. For more details, see the code, which is extensively documented. I assumed that a maze is rectangular and is surrounded by a solid wall.

Reply

Jeff Savin January 20, 2010 at 7:16 am

Interesting implementation of Djikstra’s algorithm to solve Maze. Very well commented. Passed all given tests, but in 1.8.6 I get undefined method ‘chars’ and therefore didn’t test more extensively. Nice job.

Reply

Peter Crawford January 21, 2010 at 7:51 am

Original approach, well commented.

Reply

Mareike Hybsier January 21, 2010 at 9:53 am

Very clean code, perfectly commented.

Reply

Oleksandr Manzyuk January 21, 2010 at 7:22 pm

Thanks people! It was fun.

Reply

Rajesh Kumar December 28, 2009 at 1:18 am

Solution (#3):

Rajesh Kumar, USA
Original: https://gist.github.com/b8fd187e9f3b506277e1
Forked: https://gist.github.com/4b871813a90542682d40
Code works with Ruby 1.8.7

Reply

Jeff Savin January 20, 2010 at 7:17 am

Code passed all given tests. In Ruby 1.8.6 I get undefined method ‘each_char’ and therefore couldn’t run it through the ringers on my test cases. A bit of a longer example and not the easiest to follow, but solution appears to do the job.

Reply

Rajesh Kumar January 20, 2010 at 10:53 am

Thanks Jeff for having a look! I was curious what are these ringers? :)

Also I am running snow leopard, so have ruby 1.8.7, after googling i found that if you require ‘jcode’, each_char might work.

Reply

Rajesh Kumar January 20, 2010 at 1:11 pm

One more thing. I don’t know if my approach was unique, this is what i did

I do breadth first search from both A and B, one step at a time. Analytically this is better that a simple breadth first search :
suppose the average number of neighboring nodes is avg, and the distance between A and B is dist. Then for my algorithm the cost is 2*((dist/2)**avg) instead of dist**avg

Reply

Jeff Savin January 20, 2010 at 9:17 pm

Hi Rajesh. There were 47 entries and a number of unique solutions, but also a number that used the same algorithm. There were definitely quite a few that used the breadth first search, but I can’t be certain if any took your approach. Nice thinking. :)

Jeff Savin January 20, 2010 at 9:14 pm

Hi Rajesh,

Yes, I later learned that adding require ‘jcode’ seems to fix that issue. I didn’t figure this out till about halfway through the applicants. I did go back and with that require line, I ran your program against my tests (ringers, lol). Five smaller mazes, each with a little twist, including one with two solutions to see if the program takes the shorter or longer path, and one with an endpoint called C instead of B.

Your solution passed all tests, but the final, with the C endpoint choked it up with: n `position’: undefined method `/’ for nil:NilClass (NoMethodError).

Hope that helps.

Reply

Alpha Chen December 28, 2009 at 3:26 pm

Solution (#4):

Alpha Chen, USA
Original: http://gist.github.com/264533
Forked: http://gist.github.com/264615
Submitted just for fun

Reply

Jeff Savin January 20, 2010 at 7:18 am

Not the easiest to read or follow, no comments, one-letter variables, but man, what a short, fast and accurate solution.

Reply

Peter Crawford January 21, 2010 at 7:50 am

Deeply magically short!

Reply

Aleksey Gureiev December 28, 2009 at 6:22 pm

Solution (#5):

Aleksey Gureiev, Australia
Original: http://gist.github.com/264663
Forked: http://gist.github.com/265072
Code works with Ruby 1.8 and 1.9
Approaching the task from another end — filling all white spaces that are dead-ends (3 or more walls around) with walls continuously until there’s a clear path (good maze) or there’s no empty spaces left (bad maze). Counting steps comes down to counting empty spaces plus one. Hope you like it. :)

Reply

Jeff Savin January 20, 2010 at 7:19 am

I like Aleksey’s approach. It’s logical. He fills all white spaces that are dead-ends with a wall until all that’s left is the clear path. As far as the implementation, well done Aleksey. Thirty-three lines of code and every test I threw at the program was solved perfectly.

Reply

Oleksandr Manzyuk January 20, 2010 at 5:12 pm

I am just curious: what if there are more than one path from A to B? Try to throw in this simple maze:

MAZE = %{#####
#A #
# # #
# B#
#####}

Maze.new(MAZE).steps yields 8, which is wrong. Or am I missing something?

Reply

Jeff Savin January 20, 2010 at 9:26 pm

Nice catch Oleksandr. My tests did include a Maze with two solutions for this very reason, to see if the program would take the longer or shorter path. Aleksey’s here, does take the longer path, somehow I missed that when I ran the test the first time. Thanks.

Reply

r4ito December 29, 2009 at 12:42 am

Solution (#6):

Juan Villanelo, Chile
Original: https://gist.github.com/31623c03ac38045b13bd
Forked: https://gist.github.com/6b52607175f0195b25c9
Works with Ruby 1.9
Submitted Just for Fun

Reply

Peter Cooper January 20, 2010 at 8:19 am

This ONLY works in Ruby 1.9. It fails verrry slowly in 1.8 :-)

Reply

Jeff Savin January 20, 2010 at 8:20 am

Using 1.8.6, and just for fun, so won’t even test it. :) Thanks for the heads up.

Reply

Stu Henry December 29, 2009 at 3:39 am

Solution (#7):

Stu Henry, USA
Original: https://gist.github.com/1c1a72946369994ad2e1
Forked: https://gist.github.com/115edc261940ed8f364e
Tested with Ruby 1.8

Reply

Jeff Savin January 20, 2010 at 7:20 am

This Napa Valley Winemaker went above and beyond by adding a method to show the solution to the maze. While not the shortest solution, even taking into account the extra code needed for showing the answer, it works just fine and passed all tests. Nice job!!!

Reply

Douglas Alexandre December 29, 2009 at 4:48 am

Solution (#8):

Douglas Barbosa Alexandre, Brazil
Original: https://gist.github.com/2c0ba92dd48f691540c9
Forked: https://gist.github.com/0d1857e961c2705ff4aa
Code works with Ruby 1.8
My Ruby implementation of this algorithm http://www.cs.bu.edu/teaching/alg/maze/

Reply

Jeff Savin January 20, 2010 at 7:21 am

Nice approach. Very modular, everything in short, one-line methods. Sometimes makes hard to see what’s going on, but in this case, I think it worked well. I found code to be very readable and well-organized. Passed all my tests.

Reply

Gimi Liang December 29, 2009 at 8:56 am

Solution (#9):

Gimi Liang, China
Original: http://gist.github.com/265135
Forked: http://gist.github.com/265145
(tested with Ruby 1.8.7 and Ruby 1.9.1)

Reply

Jeff Savin January 20, 2010 at 7:22 am

1.8.6 gave the following:
each_line’: no block given (LocalJumpError)

Passed all given tests according to Satoshi Asakawa. Code was well commented and while not the shortest solution, was easy to follow. Good job.

Reply

Aldric Giacomoni December 29, 2009 at 6:59 pm

Solution (#10):

Aldric Giacomoni, USA
Original: http://gist.github.com/265322
Forked: http://gist.github.com/265764
This solution has some random behavior. Depending on when you run it, it may or may not pass your tests. I promise. I like it that way. :)

Reply

Jeff Savin January 20, 2010 at 7:22 am

In Ruby 1.8.6 got:
get_paths_from’: undefined method `shuffle’ for # (NoMethodError)
Passed all given tests according to Satoshi Asakawa.

When I say code was commented well, in this case, so well it made me laugh!! Aldric’s comments were my favorite so far. :) Nice job overall.

Reply

Aldric Giacomoni January 21, 2010 at 1:57 am

Ah yes.. Ruby 1.8.6 does not have Array#shuffle, does it? I haven’t touched 1.8.6 in a long time!
I am glad you liked the comments! I think they are incredibly unhelpful unless you understand the code ;-)

Reply

Rhyhann December 29, 2009 at 7:03 pm

Solution (#11):

Othmane Benkirane, Morocco
Original: http://gist.github.com/265319
Forked: http://gist.github.com/265765
Code works with Ruby 1.9 only
In response to Peter Cooper’s tip: It would have been a lot sillier (and harder) if you asked to draw the path on the maze (with ‘-’ and ‘|’) after finding the steps number!

Reply

Jeff Savin January 20, 2010 at 7:23 am

As Othmane says, “Code works with Ruby 1.9 only.” It crashes in 1.8.6 for sure. Othmane is a regular in these contests and I’m thrilled with this high school student’s entries, always looking forward to how he takes on each challenge. The code is well documented, which helps, because I found the code itself to be a bit hard to read, but maybe that’s just me. According to Satoshi Asakawa, it passed all tests which earns a “Good Job.”

Reply

Paul Smith December 30, 2009 at 5:02 am

Solution (#12):

Paul Smith, England
Original: https://gist.github.com/d0cdc257885888e24187
Forked: https://gist.github.com/4940512af8fb06114467
Code works with Ruby 1.9

Reply

Peter Cooper January 20, 2010 at 8:18 am

Did not pass tests in 1.8 or 1.9 due to lack of steps, as noted by Satoshi Asakawa. Considering this disqualified as I don’t see a typo or something to uncover in the code to resolve this.

Reply

Paul Smith January 21, 2010 at 3:49 pm

OK, bit harsh comment though, after all the challenge does say

There are two parts to the challenge: you can choose to do one or both, depending on your skill level or how much time you have available.

I chose to only answer solveable.

Would have been nice to recieve something of a review of what I did write, but never mind.

Reply

Marc Seeger December 30, 2009 at 6:23 am

Solution (#13):

Marc Seeger, Germany
Original: https://gist.github.com/1a40b12a2c17b9d81c98
Forked: https://gist.github.com/caa8255903f4f75b4e51
Code works with Ruby definately 1.9, probably 1.8 ;)
I iterate though all the possibles moves from the starting position. The algorithm only looks at moves that lead to a position we haven’t been at so far. For each new position, we’ll look (recursively) for possible moves again. We quit once we find the exit marked “B” or once we run out of possible moves.
The algorithm tries to look at the moves that would result in a shorter arial distance to the maze-exit first.
Also: there is a movie mode :)

Reply

Jeff Savin January 20, 2010 at 7:25 am

Yet another way to solve the challenge with a bit of recursion thrown in. Passed all my tests. Very code-verbose, however, but well-commented.

Reply

Peter Cooper January 20, 2010 at 8:17 am

A bit too verbose and not a particularly interesting solution. Nonetheless, it’s well commented and formatted and easy to understand.

Reply

Marc Minneman December 31, 2009 at 3:27 am

Solution (#14):

Marc Minneman, USA
Original: https://gist.github.com/739fd769b49f218e6516
Forked: https://gist.github.com/8d2cf9b6020d148bf61e
I stored the maze as a 2D array and implemented a simple breadth-first search to determine if it was solvable and the least number of steps.
Code works with Ruby 1.9 (not tested on 1.8)

Reply

Jeff Savin January 20, 2010 at 7:25 am

Code works in 1.9 but not 1.8.6. Passes all tests. What I love about this contest is there are so many ways to solve the problem. Marc uses a Breadth-First Search Algorithm, his code is well-commented, and he went over and above with the testing. Good job.

Reply

Tim Rand December 31, 2009 at 6:21 am

Solution (#15):

Tim Rand, USA
Original: https://gist.github.com/f60daae7a0d7764a8437
Forked: https://gist.github.com/466effbc629060be634c
Code works with Ruby 1.8 and 1.9
The algorithm I used is based on following all potential paths in a coordinated way and recording the number of steps required to find the end. Only the sites of progress from the previous cycle are processed in each new cycle. Synchronized stepwise progress of all possible paths guarantees shortest-step solution. I added a way to print out the progress with each cycle, with uncommenting a single line of code–since it is fun to see how the algorithm progresses.

The test.rb file supplied in the quiz web page can be run on the gist file as long as the following require line is updated:
require ‘timrand’

Thanks. Fun Quiz.

Reply

Jeff Savin January 20, 2010 at 7:26 am

Nice solution. Passed all tests, even the one where I leave off the end point. Tim’s program correctly returns a false, calling it unsolvable. I also liked the feature to see step by step how the program finds the correct path. The code was well commented.

Reply

Amr N Tamimi December 31, 2009 at 6:44 am

Solution (#16):

Amr N Tamimi, Palestine
Original: https://gist.github.com/bc692c3b8d2ba1aba090
Forked: https://gist.github.com/0dd1b7f6ec9ae1cb7649
Ruby version: I guess both
“I solved the maze by my real love: Ruby…”

Reply

Jeff Savin January 20, 2010 at 7:27 am

Initially crashed in 1.8.6 due to undefined method: ‘each_char.’ After doing some research, I added require ‘jcode’ and all was well.

Solution itself was very different looking, but passed all tests quite nicely. Only one comment (# expect the worst), lol, and the code wasn’t necessarily the easiest to read. Perhaps some more insight via better commenting would’ve been helpful.

Reply

Amr N Tamimi January 20, 2010 at 1:26 pm

yes, I tested it on 1.8.7 as 1.8 test!

well, I worked on the code to be a unique solution!
and for comments, sorry, maybe for the next time…
hard, but fast! and there are more extra codes.. because I submit my test file!

the gist was edited
https://gist.github.com/bc692c3b8d2ba1aba090
.
.
def solvable?
steps > 0
end
.
.

Reply

Jeff Savin January 20, 2010 at 9:20 pm

Hey. You passed each and every test, nice job and keep it up. Look forward to your submission on the next contest, which is coming really soon!

Reply

Peter Cooper January 20, 2010 at 8:15 am

Fast but not particularly attractive or easy to read code-wise.

Reply

Amr N Tamimi January 20, 2010 at 1:29 pm

-1 for hard-code!

Reply

Ian Stewart December 31, 2009 at 9:01 pm

Solution (#17):

Ian Stewart, USA
Original: https://gist.github.com/f6a766a40fe4bb947b97
Forked: https://gist.github.com/0c1561d3a6d69026e47b
Written and Tested on Ruby 1.87

Reply

Jeff Savin January 20, 2010 at 7:27 am

Ian took Peter’s encouragement for trying clever and/or silly solutions to heart. Great piece of work including a near-sighted sorcerer, maze minions, and cloned wizards. The code itself worked brilliantly and was easy to read. Loved it.

Reply

Dominik Masur December 31, 2009 at 9:38 pm

Solution (#18):

Dominik Masur, Germany
Original: https://gist.github.com/914c97dbab36d76dd095
Forked: https://gist.github.com/14f9291fd49e9cadc015
Code works with Ruby 1.8

Reply

Jeff Savin January 20, 2010 at 7:28 am

Had to add require ‘jcode’ to work in 1.8.6 due to the useage of ‘each_char’. Code passed all my tests, with the exception of one where I don’t include an endpoint. Then it dies with:
in `is_position?’: undefined method `x’ for nil:NilClass (NoMethodError)

The code seemed a little cumbersome but generally does the trick.

Reply

Satish Talim January 20, 2010 at 9:17 am

Your registered email id with RubyLearning is not working. Emails sent to you bounce back.

Reply

Toni Tuominen January 1, 2010 at 7:39 pm

Solution (#19):

Toni Tuominen, Finland
Original: https://gist.github.com/ad109a625a832df38c22
Forked: https://gist.github.com/b868e9633eb6b608e324
Tested with ruby 1.8.6.

Reply

Jeff Savin January 20, 2010 at 7:28 am

Longest entry thus far with a total of three Classes written for this solution. Passed all tests except one where I didn’t define an endpoint. Lots and lots of code.

Reply

Peter Cooper January 20, 2010 at 8:07 am

This is a particularly over-engineered solution (which is why it runs slow) but the architecture is interesting nonetheless. The inclusion of tests is also positive. This solution might deserve a mention though would not win.

Reply

Alexander Klink January 2, 2010 at 6:21 pm

Solution (#20):

Alexander Klink, Germany
Original: http://gist.github.com/267487
Forked: http://gist.github.com/269084
Code works with both Ruby 1.8 and 1.9

Reply

Jeff Savin January 20, 2010 at 7:29 am

Couldn’t get to work in 1.8.6. got error:
in `initialize’: undefined method `lines’ for # (NoMethodError)

A pretty lengthy solution with three separate classes. Passed all of the tests according to Satoshi Asakawa.

Reply

Paul McKibbin January 2, 2010 at 7:57 pm

Solution (#21):

Paul McKibbin, U.K.
Original: https://gist.github.com/ce3d83b63bfce2b87976
Forked: https://gist.github.com/a2f10b59142097f55e50
Tested with 1.8 only. Should work with both, but untested in 1.9

Reply

Jeff Savin January 20, 2010 at 7:29 am

One of the nice shorter solutions. Comments throughout. Passed each and every test. Great job!

Reply

Paul McKibbin January 21, 2010 at 3:04 pm

Thanks a bunch. This was my first entry into the quizzes, and I enjoyed it thoroughly.

Reply

James Daniels January 3, 2010 at 1:46 pm

What is the expected behavior if we go “out of bounds” without a wall blocking the way?

QUESTIONABLE_MAZE => “###\nA#B\n###”

Reply

Peter Cooper January 5, 2010 at 11:01 am

For this relatively entry level challenge, such a maze would not be considered valid. You could simply fail or say the maze is not solvable if you’re able to detect this issue but it’s not expected.

Reply

Suraj Dhakankar January 5, 2010 at 10:42 pm

I did not understand Daniels Point of view
if the maze is like
###
A#B
###
then as there are no free spaces in the maze the point B is not reachable and hence steps should return 0.
What is “out of bounds”?

Reply

Peter Cooper January 6, 2010 at 8:14 am

You are correct. The maze is invalid (no walls all the way around) and there is no route. Out of bounds means outside of the maze, but that’s not practical here.

Reply

Srikanth P Shreenivas January 3, 2010 at 2:16 pm

Solution (#22):

Srikanth P Shreenivas, India
Original: https://gist.github.com/44029eb6d7ca253d8b52
Forked: https://gist.github.com/aed39f868b9f70aef74c
Code works with both Ruby 1.8 and 1.9

Reply

Jeff Savin January 20, 2010 at 7:30 am

Yet another nice solution. Readable code and comments and passed all tests.

Reply

René Scheibe January 4, 2010 at 9:31 pm

The procedure of participating is not 100% clear to me.

All the comments left here are private per default (to hide the gist url) and then made public by January 21th? But there are already some visible comments. Maybe the section “How to Enter the Challenge” needs a little rephrasing.

Reply

Satish Talim January 5, 2010 at 6:51 am

The visible comments are normally related to clarifications / queries wrt the challenge. You are right – the comments that mention the solution to the challenge, are hidden.

Your suggestions on rephrasing the “How to Enter the Challenge” are most welcome.

Reply

Suraj Dhakankar January 4, 2010 at 10:36 pm

Solution (#23):

Suraj Dhakankar, India
Original: https://gist.github.com/41ca3bc07718dbddfe9b
Forked: https://gist.github.com/6387a243e150b2f5fa70
Assumptions made:
1. The input to the class maze would be a string of characters.
2. each row of the maze is delimited by only one newline character.
3. all the rows of the maze has equal number of blocks (m X n matrix of characters)
Logic Explanation:
Start from Source Block
In the first step check all adjacent blocks to the start block and see if it has Destination block
If destination not found in first step then go to second step where it would check all the adjacent blocks to the “Free space blocks” checked in the first step
Repeat the process and return the step at which destination block is found.
In the ruby code number of steps is kept in track by putting nil element in the array after each step.
Code Tested with 1.8.6 should work with 1.9 also

Reply

Jeff Savin January 20, 2010 at 7:31 am

I can’t but help to be AMAZED at this 20 line solution. By far the shortest I’ve seen. Solved each test I through at it perfectly and quickly. NICE!!!

Reply

Suraj Dhakankar January 22, 2010 at 11:59 pm

Thanks Jeff for the feedback…

It was fun working on the solution for Maze problem.
This is my second code written in Ruby first one being the previous challenge i.e. RPCFN4. :)

I would be more interested if there are any comments or feedback on the ruby code written, as I am new to this language and want to improve my knowledge.

Thanks once again.

Reply

Aldric Giacomoni January 5, 2010 at 1:55 am

One thing I wonder.. This is really close to one of the Ruby Quizzes (but that one was about maze generation), and it also seems very close to the previous RPCFN which required a shortest-path algorithm… :-)
I do look forward to seeing how goofy solutions to this problem can be.

Reply

Peter Cooper January 5, 2010 at 11:02 am

@Aldric: Yeah, I noticed that once I started Googling, but I’d already written most of the challenge by the time.. lol :-) Hopefully, though, this can expose the idea to people who might not have been involved with the Ruby Quizzes.

Reply

Thomas Marek January 5, 2010 at 1:23 pm

Solution (#24):

Thomas Marek, Germany
Original: https://gist.github.com/7e0a7976359039a551c6
Forked: https://gist.github.com/57a0c243071bacb643a9
Code works with Ruby: 1.8 (1.9 not tested)

Reply

Jeff Savin January 20, 2010 at 7:31 am

While solution passed all initial tests, I gave it a simple maze with two solutions that caused it to choke with a `find_end_point’: stack level too deep (SystemStackError).

Maze was defined as:
MAZE7 = %{##############
#A #
######## ## ##
#B #
##############}

Reply

Rainer January 5, 2010 at 2:58 pm

Solution (#25):

Rainer Thiel, New Zealand
Original: https://gist.github.com/10a56ac76450cb6657f4
Forked: https://gist.github.com/37198dbfbe2dbfe11263
Tested with Ruby 1.9
Hi Peter, here’s my solution. I haven’t done the Ruby quizzes, but i did attempt RPCFN3 though it failed the tests :-(
When i wrote the code for that challenge, i certainly had reuse in mind, and your maze challenge has provided my with an excellent use case to demonstrate reusability of the classes i wrote then.
Hope that’s ok.

Reply

Jeff Savin January 20, 2010 at 7:33 am

I liked Rainer’s code re-use. His solution was unique in that he took the same classes he wrote for RPCFN3 (Find the Shortest Circuit) and used them to solve this maze challenge. He passed all tests according to Satoshi Asakawa, but I was unable to throw any of my additional tests because code didn’t work in 1.8.6.

Reply

Guillaume Petit January 5, 2010 at 11:32 pm

Solution (#26):

Guillaume Petit, France
Original: git@gist.github.com:101e212061e7b8de0ac0.git
Forked: https://gist.github.com/7508c4517292e2478eb2
And I used ruby 1.8.7 to run it!
Hi there ! Great idea your challenge, hope we will see some interesting things :-)

Reply

Jeff Savin January 20, 2010 at 7:36 am

Guillaume submits a nice solution that passed each and every one of my tests. Well commented and readable. I liked it. :)

Reply

Paul Damer January 6, 2010 at 1:47 am

Solution (#27):

Paul Damer, USA
Original: https://gist.github.com/2aac4aad98ca1f6cde4e
Forked: https://gist.github.com/5a409f67a71de7a987f6
Code works with Ruby 1.9 (needs look behind in regexps)

Reply

Jeff Savin January 20, 2010 at 7:40 am

Using 1.8.6 so unable to throw any additional tests at this solution. However, according to Satoshi Asakawa, passes all tests. Paul’s solution is yet another unique entry utilizing a fair amount of regex in the initialization.

Reply

Dmitriy Nagirnyak January 6, 2010 at 10:12 am

Solution (#28):

Dmitriy Nagirnayk, Australia
Original: https://gist.github.com/8c0971e5745506b8e59e
Forked: https://gist.github.com/a3a4fdc8d8e0ee36aaa3
Code works with Ruby: 1.8 (should also work with 1.9)

Reply

Jeff Savin January 20, 2010 at 7:41 am

Nice entry, passed all my tests except the one where I don’t give it an endpoint. Program chokes to death and sputters:
`throw’: uncaught throw `No start and/or end positions provided on the maze’ (NameError)

Reply

Peter Cooper January 20, 2010 at 8:06 am

A bit too verbose – not a winner for me, but well commented.

Reply

Christian Knappskog January 7, 2010 at 2:04 am

Solution (#29):

Christian Knappskog, Norway
Original: https://gist.github.com/c14a6cca2f782e2b4c3c
Forked: https://gist.github.com/c3a0943570ba15b80ccb

Reply

Satoshi Asakawa January 20, 2010 at 7:42 am

The original solution failed with both Ruby 1.8.6 and 1.9.1. But after replacing `each` to `each_line` at line 40. It worked very well with Ruby 1.9.1.

Reply

Jeff Savin January 20, 2010 at 7:43 am

Couldn’t test in 1.8.6. A more verbose solution but as Satoshi Asakawa said, passed each test with the modifications made.

Reply

René Scheibe January 7, 2010 at 11:49 pm

Solution (#30):

René Scheibe, Germany
Original: https://gist.github.com/b0ae0287babce5c2aaf7
Forked: https://gist.github.com/f4b244738a109e4342dc
Code works with: Ruby 1.9.1 and JRuby 1.4

Reply

Jeff Savin January 20, 2010 at 7:44 am

Rene mentions that his solution requires the ordered hash of 1.9.1. However, when I tested it in 1.8.6, it didn’t fail, but produced all results as unsolvable with 0 steps. Hmmmm.

Reply

René Scheibe January 20, 2010 at 12:52 pm

As I have noted, the code requires Ruby 1.9.1 and JRuby 1.4. The cause is mentioned in the README: “It also assumes that the “each” method takes notice of new elements that are added during the enumeration.” Otherwise you see exactly the results you described. This is because the each method only takes the original hash (with the only the START point in it).

Please give it a try with the mentioned Ruby version. I really aimed to use this ordered hash Ruby feature.

Reply

Pranav Singh January 8, 2010 at 9:12 am

Solution (#31):

Pranav Singh, Canada
Original: https://gist.github.com/91c586cbb0201e8ffc73
Forked: https://gist.github.com/bf943806ce5af0f7f934
Works on both 1.8 and 1.9.
I represented the maze as an array. Then, starting from the location of A, I looked if I can go in the 4 directions ( current location -+1 and +- maze width). I would repeat the same process at each step, until a path would return positive; meaning a path from A to B exists.

Reply

Jeff Savin January 20, 2010 at 7:45 am

I ran the unit test and got the following error.
1) Error:
test_maze_steps(MazeTest):
NoMethodError: undefined method `steps’ for #
test_maze.rb:122:in `test_maze_steps

Oh, there is no `steps` method.

Reply

Peter Cooper January 20, 2010 at 8:04 am

Doesn’t work. Not judging. Hardly any code.

Reply

Yuri Omelchuk January 8, 2010 at 4:49 pm

Solution (#32):

Yuri Omelchuk, Ukraine
Original: http://gist.github.com/272000
Forked: http://gist.github.com/272640
Tested with Ruby 1.8.7
The idea was to use shortest-path algorithm which would help to solve both tasks – determine if the maze is solvable and number of steps to go from A to B. Actually, it would not only allow to get above answers but also find a full path coordinates

Reply

Jeff Savin January 20, 2010 at 7:46 am

Only died on test where I didn’t give it an endpoint:
Maze.rb:178:in `neighbor_cells’: undefined method `>’ for 0..4:Range (NoMethodError)

Otherwise, passed all tests.

Reply

Peter Cooper January 20, 2010 at 8:03 am

Pedestrian solution.

Reply

Benoit Daloze January 9, 2010 at 3:31 am

Solution (#33):

Benoit Daloze, Belgium
Original: https://gist.github.com/596d3344392086d3f18b
Forked: https://gist.github.com/f1deb6e0caf3ac8f5db2
Code work with both (needs -Ku flag on 1.8)

Reply

Jeff Savin January 20, 2010 at 7:47 am

Djikstra’s algorithm again. Shortest path may be found, but the code is nowhere near short. ;)

Reply

Peter Cooper January 20, 2010 at 8:03 am

Really, really long, and not an original solution in terms of the others. However, very interesting use of unicode in the source and comments are interesting.

Reply

Benoit Daloze January 20, 2010 at 2:44 pm

Well, it’s is long because it implements 2 ways of solving mazes as I wrote in the source.

The Djikstra’s algorithm is not very interesting here, it is just fast.

My real algorithm is get_path_to_arrival, who work with a Tree, and is still reasonable in Time.

After posting this, I wrote another way for making a Tree: instead of new object, I just extend them to be Tree, that’s quite useful and avoid problem of equality.

Reply

Cary Swoveland January 9, 2010 at 5:02 am

Part 2 of the challenge stipulates, ““Steps” can only be taken up, down, left or right. No diagonals.” Does this step definition apply to Part 1 as well?

Reply

Peter Cooper January 9, 2010 at 5:53 am

Yes. No diagonals in any case.

Reply

Himansu Desai January 11, 2010 at 12:03 pm

Solution (#34):

Himansu Desai, USA
Original: https://gist.github.com/e879847f5060f92eb82d
Forked: https://gist.github.com/988d4b4666a74de1771c
Ruby Version: Tested with 1.8.7

Reply

Jeff Savin January 20, 2010 at 7:48 am

This entry failed on one of my tests where I give it a very simple maze with two solutions. Maze is defined as:

MAZE7 = %{##############
#A #
######## ## ##
#B #
##############}

Output was:
Maze 7:
true
22

Perhaps the code is optimized for most exercise as it took the longer route. ;)

Reply

Peter Cooper January 20, 2010 at 8:02 am

Very long, not keen on the style of this approach, but it works.

Reply

Raoul Felix January 12, 2010 at 5:50 am

Solution (#35):

Raoul Felix, Portugal
Original: https://gist.github.com/89e456ff8097cb08f8fb
Forked: https://gist.github.com/349d7ec9de274c37b161
Code tested with Ruby 1.8

Reply

Jeff Savin January 20, 2010 at 7:48 am

Yes, yes, another interesting solution. Very nice to read the reasoning behind the code, lots of comments. Used a set of stacks to save on memory and CPU utilization. Passed all tests but died on the last one where I don’t define a finish point:

Maze.rb:245:in `find_start_and_finish’: Start/Finish not properly specified (RuntimeError)

Reply

Peter Cooper January 20, 2010 at 8:01 am

Nice use of a stack – worth looking into further.

Reply

Raoul Felix January 20, 2010 at 11:38 pm

Thanks for the feedback Jeff and Peter!

@Jeff, Oops – I completely forgot to remove that exception I raise in the find_start_and_finish method and change the code to return 0 what that happens. Oh well :)

I initially implemented a Depth-First search algorithm (the 1st version I submitted), but that didn’t guarantee finding the shortest path, so I changed it into a breadth-first algo. It also returns the exact path that was taken from A to B, which is then used to display the maze with the path filled with dots (#solved_map).

Reply

Anonymous January 13, 2010 at 1:33 am

Solution (#36):

Javier Blanco Gutiérrez, Spain
Original: http://gist.github.com/275470
Forked: http://gist.github.com/275890
Code works with both Ruby versions

Reply

Jeff Savin January 20, 2010 at 7:49 am

One of the shorter solutions and nicely commented. Passed all tests except one where I give it a simple maze with two solutions as mentioned in some of the previous entries. The longer solution was chosen.

Reply

Brad O'Connor January 13, 2010 at 10:46 am

Solution (#37):

Brad O’Connor, Australia
Original: http://gist.github.com/275954
Forked: http://gist.github.com/276892
Only works with Ruby 1.9
This was a considerable challenge for me at my level of coding experience. The Maze#solvable? method was fairly quick and easy to get working but it took me a lot of effort to get Maze#steps up and running. I suspect I have gone the hard way about solving it but I’m very pleased with what I have produced. I’ve done my best to comment the code to explain my thought process. Any suggestions about how to cut down some of the code length would be greatly appreciated (there is a lot of fairly repetitive looking code in this that I suspect could be consolidated into something prettier).
The amount I learned about Ruby in producing this has been phenomenal! Thanks again for organising all of this.
I also added in a few ArgumentErrors for fun (if you can call that fun).

Reply

Jeff Savin January 20, 2010 at 7:50 am

As mentioned, I was unable to test as I’m running 1.8.6. According to Satoshi Asakawa, all tests passed. Nice effort, and as you said, there was a lot of code used. Nice commenting though. Glad you had fun, ArgumentErrors or not, and even more glad you learned from this exercise. Keep it up.

Reply

Peter Cooper January 20, 2010 at 1:03 pm

Glad you enjoyed it!

Yeah, the code length was what I was coming to comment on. Not necessarily the length, though, but the width. This is very “wide” code – as in, your lines are long. You’re packing a lot of stuff into most of the lines when, perhaps, it’d work better spread out. You don’t always need to try and get blocks on to a single line :-)

Reply

leobessa January 15, 2010 at 12:10 am

Solution (#38):

Leonardo Bessa, Brazil
Original: https://gist.github.com/c430ff419e2e795a72c4
Forked: https://gist.github.com/ccf21f017f616fa547e9
Code works with Ruby 1.8 and 1.9.
I used the breadth-first search (BFS).

Reply

Jeff Savin January 20, 2010 at 7:53 am

Short solution using breadth-first search. I was unable to run using 1.8.6:
Maze.rb:77:in `initialize’: undefined method `lines’ for # (NoMethodError)

Reply

Radek Kotlarek January 15, 2010 at 4:48 am

Solution (#39):

Radek Kotlarek, Ireland
Original: https://gist.github.com/aed593af1b299d761bd1
Forked: https://gist.github.com/80eaa8fd0c7e28c99996
Code works with Ruby 1.8 and 1.9

Reply

Jeff Savin January 20, 2010 at 7:54 am

Not to keen on the fact that this entry required specifying the number of rows and columns. I tried my additional tests and kept getting:
Maze.rb:84:in `initialize’: Maze must have 14 columns and 5 rows (RuntimeError). That was after I changed the constants to 14 and 5 respectively to try and accommodate my additional mazes.

Reply

Rhyhann January 15, 2010 at 11:42 pm

RPCFN is great, but one challenge per month is far from enough… would it be possible to have one challenge every two weeks, at least ? That would be great.

Reply

Satish Talim January 16, 2010 at 6:13 am

Rhyhann, I understand your enthusiasm and frustration. We started off the first two challenges (24th Sept. and 8th Oct.) every 2 weeks but decided to make it monthly after that.

The reason? Problem setting and evaluation is being done by a group of volunteers and they find it very difficult to spare time and properly evaluate all the solutions, after their regular jobs / business.

Reply

Krzysztof Kotlarek January 16, 2010 at 2:57 am

Solution (#40):

Krzysztof Kotlarek, Poland
Original: https://gist.github.com/016ba8ddc594a083bf1a
Forked: https://gist.github.com/539cb97178f44374bd58
Algorithm use queue to solve problem.

Reply

Jeff Savin January 20, 2010 at 7:54 am

Unable to test in 1.8.6. Received:
Maze.rb:150:in `work_with_queue’: undefined method `count’ for [51, 0]:Array (NoMethodError)

According to Satoshi Asakawa, passed all tests.

Reply

Rohit Arondekar January 16, 2010 at 8:53 am

Different solutions can yield different number of steps in which case the test for number of steps will fail. Is that acceptable or do we have to get the same number of steps?

Reply

Peter Cooper January 16, 2010 at 9:47 am

There’s only one solution for the mazes in the test suite. However, if you want to make it more complete, it needs to be the lowest number of steps.

Reply

James Daniels January 16, 2010 at 11:39 am

Solution (#41):

James Daniels, USA
Original: http://gist.github.com/278696
Forked: http://gist.github.com/279169
Tested with both 1.8.7 and 1.9.1

Reply

Jeff Savin January 20, 2010 at 7:55 am

Couldn’t run in 1.8.6. Received:
Maze.rb:110:in `solution’: undefined method `count’ for [[13, 1]]:Array (NoMethodError)

Passed all tests according to Satoshi.

Reply

Leave a Comment

{ 35 trackbacks }

Previous post:

Next post: