RPCFN: Mazes - 5

²⁷/Dec 2009 By Satish Talim

beginners rpcfn ruby

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 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.

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.

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.
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:

Your name:
Country of Residence:
GIST URL of your Solution (i.e. Ruby code) with explanation and / or test cases:
Code works with Ruby 1.8 / 1.9 / Both:
Email address (will not be published):
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.

Acknowledgements

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

Dmytro Shteflyuk, Ukraine
Oleksandr Manzyuk, Ukraine
Rajesh Kumar, USA
Aleksey Gureiev, Australia
Stu Henry, USA
Douglas Barbosa Alexandre, Brazil
Gimi Liang, China
Aldric Giacomoni, USA
Othmane Benkirane, Morocco
Paul Smith, England
Marc Seeger, Germany
Marc Minneman, USA
Tim Rand, USA
Amr N Tamimi, Palestine
Ian Stewart, USA
Toni Tuominen, Finland – declared winner (randomly selected)
Alexander Klink, Germany
Paul McKibbin, U.K.
Srikanth P Shreenivas, India
Suraj Dhakankar, India
Thomas Marek, Germany
Rainer Thiel, New Zealand – declared winner (randomly selected)
Guillaume Petit, France
Paul Damer, USA
Dmitriy Nagirnyak, Australia
Christian Knappskog, Norway
René Scheibe, Germany
Pranav Singh, Canada
Yuri Omelchuk, Ukraine
Benoit Daloze, Belgium
Himansu Desai, USA
Raoul Felix, Portugal – declared winner (second best solution)
Javier Blanco Gutiérrez, Spain
Brad O’Connor, Australia
Leonardo Bessa, Brazil
Radek Kotlarek, Ireland
Krzysztof Kotlarek, Poland
James Daniels, USA
Philippe Antras, France
Bill Kayser, USA
Jean-Christophe Cyr, Canada
Patrick McKenzie, Japan – declared winner (best solution)
Paul Gallagher, Singapore
Clément Julliard, France – declared winner (randomly selected)

Just for Fun

Satoshi Asakawa, Japan
Alpha Chen, USA
Juan Villanelo, Chile
Dominik Masur, Germany
Tamas Szabo, Australia
Cary Swoveland, Canada

The Winners

Winners

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

Patrick McKenzie from Japan (his Ruby Challenge solution) – the person with the best and most creative Ruby solution. He wins a printed copy of the book “Refactoring in Ruby” from InformIT and a free 10 GB account for a year from Backup My App.
Raoul Felix from Portugal (his Ruby Challenge solution) – the person with an equally good and best packaged (it has extra tests, fixtures, the code is easy to read and well structured) Ruby solution. He wins any one of PeepCode’s Ruby on Rails screencasts.
Clément Julliard from France (his Ruby Challenge solution), Rainer Thiel from New Zealand (his Ruby Challenge solution), and Toni Tuominen from Finland (his Ruby Challenge solution) – selected randomly amongst the remaining working Ruby solutions. They win any one of Pragmatic’s The Ruby Object Model and Metaprogramming screencasts.
All the participants in this challenge (except Patrick McKenzie who gets a free 10 GB account for a year) will get a free 5 GB account for 6 months from Backup My App.

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.

Tags// peter cooper, programming, rpcfn, ruby, ruby programming challenge for newbies, the ruby programming language,

Ruby Learning

Not Just Ruby Any More!