RPCFN: Japanese Mosaic Problem (#14)

by Joseph Wilk on October 1, 2010

Ruby Programming Challenge For Newbies

RPCFN: Japanese Mosaic Problem (#14)

By Joseph Wilk

About Joseph Wilk

Joseph Wilk Joseph Wilk is a member of the core development team for Cucumber. He has been developing for the web for over 10 years in both big and small companies and as an entrepreneur. After stints working with Java and Python he finally found Ruby. He now spends his time in-between eating Cucumbers working at Songkick.com. Having more fun than is healthy working as a Software Gardener building web systems, working on open source projects and giving talks around the world about testing. He suffers from test obsession and has given up hope of any treatment.

Joseph Wilk has this to say about the challenge:

The Japanese Mosaic problem is a logic puzzle based on a grid with the cells potentially containing numbers ranging 0 to 9. The numbers reflect for a cell how many of its neighbours and itself are shaded in. The fun aspect of these problems is once solved you end up with some pretty ASCII art. You’re challenge is to write an algorithm to solve any mosaic puzzle. The challenge provides the opportunity to explore data structures to represent the problem space and looking at how we can navigate the structure in search of a solution. There are lots of opportunities to also think about the efficiency in searching for a solution. A Cucumber feature has already been written for you with lots of scenarios exploring through examples the rules of the Japanese Mosaic problem. If you are not familiar with Cucumber checkout http://cukes.info/. This Cucumber feature is both your specification and your executable tests. You’re mission is to get all the Scenarios passing. There are many ways to solve the problem and I look forward to seeing how people tackle these in the different languages. Good luck and safe Cuking.

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

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

The Ruby Challenge

RPCFN

The Challenge

All the instructions and the code to get you started are in a Github repository: http://github.com/josephwilk/japanese-mosaic-logic-puzzle

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 31st Oct. 2010 (Indian Standard Time). No new solutions will be accepted from 1st Nov. onwards.
  • On 1st Nov. 2010 all the solutions will be thrown open for everyone to see and comment upon.
  • The winning entries will be announced on this blog in the first week of Nov. 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

Special thanks to:

  • Joseph Wilk.
  • GitHub, for giving us access to a private repository on GitHub to store all the submitted solutions.
  • The RubyLearning team.

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

In the competition

  • Manuel Korfmann

The Winner

Winners

Congratulations to the winner of this Ruby Challenge. He is:

  • Manuel Korfmann who was the only submitter and winner of this final challenge.

Previous Challenge

RPCFN: Economics 101 (#13) by Dr. Bruce Scharlau.

Note: All the previous challenges, sponsors and winners can be seen on the Ruby Programming Challenge for Newbies page.

Technorati Tags: , , , ,

Posted by Joseph Wilk

{ 7 comments… read them below or add one }

Himansu Desai October 14, 2010 at 8:11 pm

Hello – I have questions on the ’0′ constraint. It seems one algorithm can easily solve all situations except this odd one. Can we assume that ’0′ constraint can similarly cancel out a ’3′ or ’4′ constraint if there is a conflict? Is the correct solution the one the most number of cells to have a number that matches the filled surrounding cells. What if neighboring ’0′ cancels out a portion of the neighbors of a ’2′ or ’3′ but not all? Should the solution then remove the partial set of cells that fit the ’2′ or ’3′?. Thanks!

Reply

Joseph Wilk October 15, 2010 at 12:21 pm

A 0 constraint cancels out any neighbouring constraints to the 0 cell. That is the only thing a 0 does.
|x|x|x|
|x|0|x|
|x|x|x|

Sorry I don’t quite understand the other parts of your question. Perhaps you could give an example to illustrate.

Reply

Josh Cheek November 26, 2010 at 8:42 am

“A 0 constraint cancels out any neighbouring constraints to the 0 cell. That is the only thing a 0 does.”

So
|0|1| |

Would solve to
| | | |

Rather than
| | |x|

Because the zero wiped out the 1 constraint, even though it is possible to meet both constraints?

—–

Also, zero is the only constraint that can alter its neighbours constraints? There can never be a
|4|3|
|3|3|
Because the four and the threes conflict?

Reply

Joseph Wilk October 16, 2010 at 8:41 am

0 constraints wipe out any constraints that are in its neighbouring cells.

I don’t completely understand the other parts of your question. Perhaps you could give some examples?

Thanks

Reply

Himansu Desai October 16, 2010 at 10:51 pm

Thanks. I can work with that definition – always (completely) wipe out all neighbors’ constraints. Another possibility is to treat the ’0′ constraint like any other numeric constraint. Below are a couple of examples where the ’2′ does not get completely wiped out, while still satisfying the numbers (fully in the 1st example and partially in the 2nd one). Just trying to make sure the algorithm is as generic as needed for the rules. Thanks so much.

|0| | | | | |#|
|2| |3| | | |#|
| | | | |#|#| |

|0| | | | | | |
|2| |0| | | | |
| | | | |#| | |

Reply

Manuel Korfmann October 25, 2010 at 6:07 pm

Manuel Korfmann
manu@korfmann.info
Germany

Code works with Ruby 1.9.

http://github.com/mkorfmann/fill-a-pix-challenge-by-Joseph-Wilk

I am a student, who likes to hack after homework :) .

Best regards

Reply

Benoit Daloze November 3, 2010 at 8:37 am

Your name: Benoit Daloze
Country of Residence: Belgium
Category: Just for Fun
GIST URL of your Solution (i.e. Ruby code) with explanation and / or test cases: http://github.com/eregon/japanese-mosaic-logic-puzzle
Code works with Ruby 1.8 / 1.9 / Both: 1.9.2
Email address (will not be published): eregontp@gmail.com
Brief description of what you do (will not be published):

I use a three-state cells system, managed in a Mosaic (grid), tracking Cell changes while running the 3 algorithms.
If the algorithms cannot solve it, brute-force is used on the unknown cells.

The code use and redefine many operators, to make it short and expressive.

Reply

Leave a Comment

{ 14 trackbacks }

Previous post:

Next post: