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 }

Philippe Antras January 17, 2010 at 1:34 am

Solution (#42):

Philippe Antras, France
Original: https://gist.github.com/b6a7ebd8f92130724950
Forked: https://gist.github.com/75aa855c21eab664e906
Works with Ruby 1.8

Reply

Jeff Savin January 20, 2010 at 7:39 am

Nice and short solution that passed all of my tests. Good job.

Reply

Bill Kayser January 17, 2010 at 7:53 am

Solution (#43):

Bill Kayser, USA
Original: https://gist.github.com/0f0146f78530295e02c1
Forked: https://gist.github.com/a3b0e40e180f0db874bb
Code works with both Ruby 1.8 and 1.9

Reply

Jeff Savin January 20, 2010 at 7:38 am

A fun solution using a virus metaphor. Although this solution was on the verbose side, it was a great attempt at “providing a literate, prosy presentation.” Just look at this code snippet:
def steps
infect the cell at a
while we have more? new_infections do
spread a new_infection
more cowbell!
end
if the maze is infected? at b then return the generation at b else return 0 end
end

Looks more like pseudo code, but this is Ruby for you. Thanks for the entry. Unique. :)

Reply

Bill Kayser January 21, 2010 at 9:34 pm

Thanks for the nice remarks, Jeff, Paul and Tamas (liked your solution as well!).

Congratulations to the winners, and thanks for a fun contest.

Reply

Paul January 20, 2010 at 8:29 am

brilliant
+1

Reply

Tamas Szabo January 21, 2010 at 7:38 am

I just love this.
Similar to mine, but more elegant.

Reply

Jean-Christophe Cyr January 17, 2010 at 11:47 pm

Solution (#44):

Jean-Christophe Cyr, Canada
Original: https://gist.github.com/76f2f8e76321ff7fc5a9
Forked:
Works with both Ruby 1.8 and 1.9

Reply

Jeff Savin January 20, 2010 at 7:38 am

Nice entry. A bit on the wordy side, but produced great results, quickly solving all tests thrown at it.

Reply

Patrick McKenzie January 18, 2010 at 1:57 pm

Solution (#45):

Patrick McKenzie, Japan
Original: http://gist.github.com/279891
Forked: http://gist.github.com/279979
Tested in 1.8, should work in 1.9 too but untested.
Brief description of algorithm: The code is well-commented but basically it uses regular expressions and gsub to breadth first search the maze. I’m mostly aiming for humor value rather than practical utility.
Thanks, this was a fun diversion. Thanks for running the contest.

Reply

Jeff Savin January 20, 2010 at 7:37 am

Patrick actually created a complete regex solution in fun, stating he is too lazy working with arrays. The solution may or may not be efficient, I don’t know, I didn’t test speed. However, the code ended up being on the shorter side and worked perfectly. I couldn’t get it to fail. Nice job.

Reply

Paul January 18, 2010 at 5:13 pm

Solution (#46):

Paul Gallagher, Singapore
Original: https://gist.github.com/953e1b02a61a5bb42605
Forked: https://gist.github.com/fd33bb34c6132160e9f2
Code should work with both 1.8 and 1.9, but only tested in 1.8

Reply

Jeff Savin January 20, 2010 at 7:37 am

Short solution, but failed a couple of my tests. MAZE7 where two valid solutions are given. Not only did entry pick the longer way to go, but the number of steps were wrong. And, MAZE8, where there was no valid endpoint and, hmm, somehow we got an answer anyway.

MAZE7 = %{##############
#A #
######## ## ##
#B #
##############}
Yielded:
Maze 7:
true
23 (should be 16)

MAZE8 = %{##############
#A #
########### ##
#C #
##############}
Yielded:
Maze 8:
true (should be false)
22 (should be 0)

Reply

Paul January 20, 2010 at 8:22 am

yeah, I took the instructions literally.. Peter Cooper: “There’s only one solution for the mazes in the test suite.”
.. so the solution is explicitly only for mazes with 0 or 1 solutions. It’s also not ensuring that the maze is valid or well formed.
So while this would be horror a production code, I enjoyed just writing the “straightforward” algorithm in the raw to pass the test suite provided;-)

Reply

Jeff Savin January 20, 2010 at 10:50 am

Well, you did a great job. I did like your entry. I always create a few extra trickier test cases just to add a little stress to the program code. :) Thanks for your entry.

Reply

Clément Julliard January 18, 2010 at 11:35 pm

Solution (#47):

Clément Julliard, France
Here is my solution to this challenge. I didn’t tried to do the shortest, or the fastest ; but the easiest to read, and to understand. I added a small display method to show what is my programm doing, in real time. We can really see the exploration of the maze :) I’m using Ruby 1.8 : it’s working. But I didn’t tried with 1.9.
Original : https://gist.github.com/e0ae014d0eb67f5d5ad7
Forked: https://gist.github.com/c92e6ca45764b4883294

Reply

Jeff Savin January 20, 2010 at 7:36 am

This 16-year old student did a great job submitting an entry that passed all my tests. My suggestions would be to add more commenting to the code (instead of nothing at all) and that would help with the readability. Nice job.

Reply

Satoshi Asakawa January 19, 2010 at 11:37 am

Solution (#48):

Satoshi Asakawa, Japan
Submitting for fun.
http://github.com/gautamrege/RPCFN5solutions/tree/master/ashbb/

Reply

ashbb January 20, 2010 at 11:50 am

Hi!
This is a tiny Shoes app. Let’s enjoy Ruby and Shoes! :-D

Reply

Jeff Savin January 20, 2010 at 9:42 pm

Satoshi,

I loved it. It was fun to watch and see a graphical display of the mazes being solved. Very nice work. Someday, you gotta teach me Shoes. :)

Reply

Tamas Szabo January 20, 2010 at 5:20 pm

I can’t believe I missed the deadline by one day.
Today morning I woke up with the false assumption that the deadline is midnight today, so I knocked up a solution quickly.

I just wanted to submit now when I noticed that there are already solutions out there :).

Anyways, I submit the URL (outside of the competition) if anyone is interested.

I used a Labworker, Mouse, Cheese metaphor. Mouse can breed pups, mark cells by peeing on them, sniff for cheese, marked cells and sniff around for possible paths.
Not short, but had fun anyways.

Tamas Szabo
Australia
URL: git://gist.github.com/281801.git
Code works with 1.8.7 and 1.9.1

All The Best,

Tamas

Reply

Tamas Szabo January 20, 2010 at 8:35 pm
Jeff Savin January 21, 2010 at 7:16 am

Haha, Tamas. Very fun code to read. Definitely unique. Yours is one of four, that I can remember which took Peter’s call to silliness to heart. Nice job. I tried testing, but use 1.8.6 and failed:
Maze.rb:212:in `each_line’: no block given (LocalJumpError)

Too bad you were a day late, its obvious you put some thought into this, even if you did crank it out last minute.

Reply

Tamas Szabo January 21, 2010 at 9:12 am

It was fun to write and I’m happy someone finds in fun to read as well despite of the fact that it isn’t as clean I usually like my code to be.

I’ve started to learn Ruby recently, so I have the luxury of using 1.9 features (ie. Enumerator#with_index which has been backported only to 1.8.7 but not to 1.8.6)
Your last test would throw an exception in Maze.new, because it isn’t a valid maze.

I don’t mind that I was late, if I checked the date properly yesterday I wouldn’t have coded up the solution at all and it would make me sad to know that my mice aren’t living, sniffing, breeding, and marking their territories out there :D

Reply

Aurélien Bottazini January 20, 2010 at 8:05 pm

Jeff, is it possible to have your test suite?

I missed the deadline (thinking it was tonight) and I would like to test my solution against your additional mazes :).

Reply

Jeff Savin January 21, 2010 at 7:07 am

Sure, no problem. The only real different ones are the last two, where there are two routes to take (solution should pick the shortest) and no endpoint defined.

http://www.pastie.org/787591

Reply

Cary Swoveland January 21, 2010 at 4:50 am

My solution to (both parts of) RPCFN: Mazes (#5) is at:
https://gist.github.com/cc05a835683f4af10a91

Actually, it’s not really a solution, as I hadn’t finished debugging, but decided to submit it anyway, in hopes of getting some useful suggestions.

I live in beautiful Vancouver, Canada. I’m using Ruby 1.8.7, on a Mac. My email is cary@swoveland.com.

I’m retired, learning Ruby (then Rails) just for fun. Maybe I’ll find something useful to do with it when I’m up to speed. My other hobbies are woodworking and photography.

Reply

Leave a Comment

{ 35 trackbacks }

Previous post:

Next post: