[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[QUIZ] Pen and Paper (#90

James Gray

8/11/2006 12:59:00 PM

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rub...

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Eric DUMINIL

Some classmates and I used to play a lot of pen and paper games while sitting
in the last row of the classroom. My favorite game was this one.

We had to fill a 5x5 board as fast as possible with numbers from 1 to 25,
beginning at a random position and then going from one square to another:

- jumping over 2 squares when traveling horizontally or vertically
- jumping over 1 square when traveling diagonally.

Here is an example with numbers from 1 to 14 (it would be impossible to keep on
filling the board, since 1, 13, and 8 are blocking the way):

-------------------
| . 1 4 . 14|
| 10 . . 11 6|
| 3 . 8 2 .|
| . 12 5 . 13|
| 9 . . . 7|
-------------------

Here is a completed 5x5 board:

-------------------
| 14 1 8 25 2|
| 6 23 16 5 22|
| 18 10 13 19 9|
| 15 4 7 24 3|
| 12 20 17 11 21|
-------------------

Though this game is impossible with 2x2, 3x3 or 4x4 boards, it appears that NxN
boards can be filled when N>4 (or n=1). For example, 6x6:

-----------------------
| 33 21 10 32 35 11|
| 16 26 5 13 25 6|
| 9 31 34 22 30 1|
| 4 20 17 27 36 12|
| 15 23 8 14 24 7|
| 18 28 3 19 29 2|
-----------------------

7x7:

---------------------------
| 46 33 26 8 32 35 9|
| 17 14 5 37 15 6 38|
| 27 22 47 34 25 48 31|
| 45 42 16 7 43 36 10|
| 18 13 4 21 12 3 39|
| 28 23 44 29 24 49 30|
| 1 41 19 2 40 20 11|
---------------------------

Here comes the quiz!

- Write a ruby script that fills a board (with a given NxN size)
as fast as possible
- Try to fill the biggest board you can with this script, in a
reasonable amount of time (let's say 48 hours minus scripting time)

You get extra points for:

- Finding more about this game (name, origin, related articles)
- Filling a 5x5 board with only pen and paper
- Filling a bigger board with only pen and paper
- Finding the worst attempt possible for a given size. For example,
getting stuck after 10 steps on a 5x5 board is pretty bad:

-------------------
| . 6 3 . 7|
| . . 9 . .|
| 4 1 . 5 2|
| . . . . 8|
| . . 10 . .|
-------------------

- Filling a board with a cycle pattern, i.e. where you can jump from
the last square to the first square:

-------------------
| 22 10 7 23 11|
| 14 19 4 1 16|
| 8 24 12 9 6|
| 21 2 15 20 3|
| 13 18 5 25 17|
-------------------

-----------------------
| 16 9 27 17 8 28|
| 35 12 6 30 13 23|
| 26 18 15 10 19 2|
| 5 31 34 22 7 29|
| 36 11 25 1 14 24|
| 33 21 4 32 20 3|
-----------------------

I can't wait to look at your solutions!

I daresay that brute-forcing won't help you much (it took me 98,268,583 attempts
and 4 days on a decent computer to fill a 10x10 board) but I don't know many
other ways to fill a board.

Have fun with this quiz.
44 Answers

James Gray

8/11/2006 6:40:00 PM

0

On Aug 11, 2006, at 7:58 AM, Ruby Quiz wrote:

> - Try to fill the biggest board you can with this script, in a
> reasonable amount of time (let's say 48 hours minus scripting time)

$ time ruby grid_fill.rb -s 6
-------------------------------
| 15 8 26 16 7 27 |
| 34 11 5 29 12 22 |
| 25 17 14 9 18 1 |
| 4 30 33 21 6 28 |
| 35 10 24 36 13 23 |
| 32 20 3 31 19 2 |
-------------------------------

real 0m0.037s
user 0m0.026s
sys 0m0.010s
$ time ruby grid_fill.rb -s 6
-------------------------------
| 28 21 3 29 20 4 |
| 11 24 18 6 25 35 |
| 2 30 27 22 31 14 |
| 17 7 10 34 19 5 |
| 12 23 1 13 26 36 |
| 9 33 16 8 32 15 |
-------------------------------

real 0m0.037s
user 0m0.026s
sys 0m0.010s
$ time ruby grid_fill.rb -s 6
-------------------------------
| 19 12 30 20 11 31 |
| 2 15 9 33 16 26 |
| 29 21 18 13 22 5 |
| 8 34 1 25 10 32 |
| 3 14 28 4 17 27 |
| 36 24 7 35 23 6 |
-------------------------------

real 0m0.037s
user 0m0.026s
sys 0m0.010s

:)

James Edward Gray II

Mat Schaffer

8/11/2006 7:42:00 PM

0


On Aug 11, 2006, at 2:39 PM, James Edward Gray II wrote:

> On Aug 11, 2006, at 7:58 AM, Ruby Quiz wrote:
>
>> - Try to fill the biggest board you can with this script, in a
>> reasonable amount of time (let's say 48 hours minus scripting
>> time)
>
> [snip: lots of fast filled boards]

Do you by any chance have a background in artificial intelligence?
That's really impressive how quickly you cranked out a solution to a
problem I can't yet see a decent strategy for. Hats off to you, my
friend.
-Mat

James Gray

8/11/2006 7:48:00 PM

0

On Aug 11, 2006, at 2:42 PM, Mat Schaffer wrote:

>
> On Aug 11, 2006, at 2:39 PM, James Edward Gray II wrote:
>
>> On Aug 11, 2006, at 7:58 AM, Ruby Quiz wrote:
>>
>>> - Try to fill the biggest board you can with this script, in a
>>> reasonable amount of time (let's say 48 hours minus scripting
>>> time)
>>
>> [snip: lots of fast filled boards]
>
> Do you by any chance have a background in artificial intelligence?
> That's really impressive how quickly you cranked out a solution to
> a problem I can't yet see a decent strategy for. Hats off to you,
> my friend.

I bet you are going to be very surprised when I post my pathetic
little toy. If it's good at anything it's cheating... ;)

James Edward Gray II

Mat Schaffer

8/11/2006 8:10:00 PM

0


On Aug 11, 2006, at 3:48 PM, James Edward Gray II wrote:

> On Aug 11, 2006, at 2:42 PM, Mat Schaffer wrote:
>
>>
>> On Aug 11, 2006, at 2:39 PM, James Edward Gray II wrote:
>>
>>> On Aug 11, 2006, at 7:58 AM, Ruby Quiz wrote:
>>>
>>>> - Try to fill the biggest board you can with this script, in a
>>>> reasonable amount of time (let's say 48 hours minus scripting
>>>> time)
>>>
>>> [snip: lots of fast filled boards]
>>
>> Do you by any chance have a background in artificial
>> intelligence? That's really impressive how quickly you cranked
>> out a solution to a problem I can't yet see a decent strategy
>> for. Hats off to you, my friend.
>
> I bet you are going to be very surprised when I post my pathetic
> little toy. If it's good at anything it's cheating... ;)

$ gem install pen_and_paper --remote
Attempting remote installation of 'pen_and_paper'
ERROR: While executing gem ... (Gem::GemNotFoundException)
Could not find pen_and_paper (> 0) in the repository

Okay, well at least it wasn't THAT sort of cheating :) Can't wait to
see it!
-Mat

Elliot Temple

8/11/2006 8:25:00 PM

0


On Aug 11, 2006, at 12:48 PM, James Edward Gray II wrote:

> On Aug 11, 2006, at 2:42 PM, Mat Schaffer wrote:
>
>>
>> On Aug 11, 2006, at 2:39 PM, James Edward Gray II wrote:
>>
>>> On Aug 11, 2006, at 7:58 AM, Ruby Quiz wrote:
>>>
>>>> - Try to fill the biggest board you can with this script, in a
>>>> reasonable amount of time (let's say 48 hours minus scripting
>>>> time)
>>>
>>> [snip: lots of fast filled boards]
>>
>> Do you by any chance have a background in artificial
>> intelligence? That's really impressive how quickly you cranked
>> out a solution to a problem I can't yet see a decent strategy
>> for. Hats off to you, my friend.
>
> I bet you are going to be very surprised when I post my pathetic
> little toy. If it's good at anything it's cheating... ;)

I've done a similar problem before, years ago called a Knight's Tour.
You move a knight around a chess board and try to visit each square
once. I've seen someone do it live, blindfolded which was pretty
cool. Here's a brief English description of one technique I used.

MINOR SPOILER WARNING

One simple technique that helped get decent results was to keep track
of how many still-open squares are connected to each square. Then
when choosing what square to visit next, choose the square with the
lowest number of open, connected squares. Corners are only connected
to two others squares at the start (for the knight's tour). This
makes sure if you move adjacent to a corner, you'll move to the
corner next, which helps avoid being struck (it's not strictly always
necessary because you could end in a corner). I can't remember if it
ever had incomplete runs using just the open square scoring technique
or not.

-- Elliot Temple
http://www.cur...

Suraj Kurapati

8/11/2006 8:40:00 PM

0

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

James Edward Gray II wrote:
> On Aug 11, 2006, at 7:58 AM, Ruby Quiz wrote:
>
>> - Try to fill the biggest board you can with this script, in a
>> reasonable amount of time (let's say 48 hours minus scripting time)
>
[timings for 6x6 square snipped]

Here's what I get, although I'm sure we have different hardware. :)

[sun@yantram j0 s0 ~/src/ruby_quiz]
612$ time ruby -w 90.rb 10
- -----------------------------------------------------
| 17 62 28 18 65 60 48 95 89 79 |
| 6 20 39 7 86 40 75 87 97 76 |
| 27 9 66 61 47 67 88 78 98 91 |
| 16 63 29 19 64 59 49 94 90 80 |
| 5 21 38 8 85 41 74 84 96 77 |
| 26 10 33 23 46 68 53 43 99 92 |
| 15 1 30 12 35 58 50 70 55 81 |
| 4 22 37 3 32 42 73 83 52 72 |
| 25 11 34 24 45 69 54 44 100 93 |
| 14 2 31 13 36 57 51 71 56 82 |
- -----------------------------------------------------

real 0m0.011s
user 0m0.007s
sys 0m0.002s
[sun@yantram j0 s0 ~/src/ruby_quiz]
613$ time ruby -w 90.rb 10
- -----------------------------------------------------
| 30 21 8 31 22 54 73 47 87 74 |
| 14 37 93 15 38 94 81 60 95 82 |
| 7 69 46 53 70 45 1 75 88 98 |
| 29 20 9 32 23 55 72 48 84 61 |
| 13 36 92 16 39 91 80 59 96 83 |
| 6 68 41 52 71 44 2 76 89 99 |
| 28 19 10 33 24 56 65 49 85 62 |
| 12 35 26 17 40 51 79 58 97 78 |
| 5 67 42 4 66 43 3 77 90 100 |
| 27 18 11 34 25 57 64 50 86 63 |
- -----------------------------------------------------

real 0m0.011s
user 0m0.009s
sys 0m0.000s
[sun@yantram j0 s0 ~/src/ruby_quiz]
614$ time ruby -w 90.rb 10
- -----------------------------------------------------
| 61 19 46 30 20 100 73 64 88 83 |
| 12 36 59 13 37 66 93 81 67 94 |
| 45 29 62 44 74 63 87 75 97 84 |
| 60 18 47 31 21 48 72 65 89 82 |
| 11 35 58 14 38 57 92 80 68 95 |
| 6 28 1 43 25 52 40 76 98 85 |
| 3 17 8 32 22 49 71 54 90 78 |
| 10 34 5 15 39 56 24 51 69 96 |
| 7 27 2 42 26 53 41 77 99 86 |
| 4 16 9 33 23 50 70 55 91 79 |
- -----------------------------------------------------

real 0m0.011s
user 0m0.009s
sys 0m0.000s

:)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)

iD8DBQFE3OsCmV9O7RYnKMcRAnSuAKCJY/JP8i+HSzYFzNSGzcBxkevRygCfQ7jk
BmjqVksuBLsjAJr2cZwRoIw=
=iLJD
-----END PGP SIGNATURE-----

Trans

8/11/2006 9:18:00 PM

0


Ruby Quiz wrote:
> The three rules of Ruby Quiz:
>
> 1. Please do not post any solutions or spoiler discussion for this quiz until
> 48 hours have passed from the time on this message.
>
> 2. Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rub...
>
> 3. Enjoy!
>
> Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
> on Ruby Talk follow the discussion. Please reply to the original quiz message,
> if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
> by Eric DUMINIL
>
> Some classmates and I used to play a lot of pen and paper games while sitting
> in the last row of the classroom. My favorite game was this one.
>
> We had to fill a 5x5 board as fast as possible with numbers from 1 to 25,
> beginning at a random position and then going from one square to another:
>
> - jumping over 2 squares when traveling horizontally or vertically
> - jumping over 1 square when traveling diagonally.
>
> Here is an example with numbers from 1 to 14 (it would be impossible to keep on
> filling the board, since 1, 13, and 8 are blocking the way):
>
> -------------------
> | . 1 4 . 14|
> | 10 . . 11 6|
> | 3 . 8 2 .|
> | . 12 5 . 13|
> | 9 . . . 7|
> -------------------
>
> Here is a completed 5x5 board:
>
> -------------------
> | 14 1 8 25 2|
> | 6 23 16 5 22|
> | 18 10 13 19 9|
> | 15 4 7 24 3|
> | 12 20 17 11 21|
> -------------------
>

I know I'm stupid and all that, but I'm not sure there's enough
explination here for someone who's never played this game before. Could
you explain the rules of game a little better.

Thanks,
T.

Elliot Temple

8/11/2006 9:38:00 PM

0


On Aug 11, 2006, at 1:40 PM, Suraj N. Kurapati wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> James Edward Gray II wrote:
>> On Aug 11, 2006, at 7:58 AM, Ruby Quiz wrote:
>>
>>> - Try to fill the biggest board you can with this script, in a
>>> reasonable amount of time (let's say 48 hours minus
>>> scripting time)
>>
> [timings for 6x6 square snipped]
>
> Here's what I get, although I'm sure we have different hardware. :)

<timings snipped>

Mine did 50x50 in

real 0m0.516s
user 0m0.473s
sys 0m0.013s

on it's third attempt. it fails sometimes (i guess i could have it
loop and keep trying until it gets a good run). i haven't written
printing out a pretty board though (using pp is no good over about
15x15, at least with the defaults)

i tried 500x500 a few times and it failed them all. 500x500 should be
easy though, for a smarter algorithm. you could treat it like a bunch
of smaller games with a requirement that you end near a certain edge.

-- Elliot Temple
http://www.cur...

Justin Collins

8/11/2006 10:53:00 PM

0

Elliot Temple wrote:
>
> On Aug 11, 2006, at 1:40 PM, Suraj N. Kurapati wrote:
>
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> James Edward Gray II wrote:
>>> On Aug 11, 2006, at 7:58 AM, Ruby Quiz wrote:
>>>
>>>> - Try to fill the biggest board you can with this script, in a
>>>> reasonable amount of time (let's say 48 hours minus scripting
>>>> time)
>>>
>> [timings for 6x6 square snipped]
>>
>> Here's what I get, although I'm sure we have different hardware. :)
>
> <timings snipped>
>
> Mine did 50x50 in
>
> real 0m0.516s
> user 0m0.473s
> sys 0m0.013s
>
> on it's third attempt. it fails sometimes (i guess i could have it
> loop and keep trying until it gets a good run). i haven't written
> printing out a pretty board though (using pp is no good over about
> 15x15, at least with the defaults)
>
> i tried 500x500 a few times and it failed them all. 500x500 should be
> easy though, for a smarter algorithm. you could treat it like a bunch
> of smaller games with a requirement that you end near a certain edge.
>
> -- Elliot Temple
> http://www.cur...
[justin@cheese ruby]$ time -p ruby penpaper.rb 10 > /dev/null
real 0.02
user 0.01
sys 0.00
[justin@cheese ruby]$ time -p ruby penpaper.rb 50 > /dev/null
real 1.85
user 1.85
sys 0.00
[justin@cheese ruby]$ time -p ruby penpaper.rb 100 > /dev/null
real 18.27
user 18.25
sys 0.00
[justin@cheese ruby]$ time -p ruby penpaper.rb 200 > /dev/null
real 21.32
user 21.31
sys 0.00
[justin@cheese ruby]$ time -p ruby penpaper.rb 300 > /dev/null
real 564.41
user 564.39
sys 0.01

I'm not sure I like where those times are going... :)
My script keeps trying until it finds a solution, so keep that in mind
for the timings above.

-Justin

Suraj Kurapati

8/11/2006 11:21:00 PM

0

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Trans wrote:
> Could you explain the rules of game a little better.

1. Grab a pen and piece of paper.

2. Draw a 5x5 grid (or table or matrix or whatever you like
to call it).

3. Pick a cell or slot, whichever one you like, in the grid.

4. Write the number "1" in that chosen cell.

5. Starting from the cell you just marked (with the number "
1"), travel to a different cell by following these rules:

a. jump over 2 cells when traveling horizontally or
vertically

b. jump over 1 cell when traveling diagonally

6. Once you have traveled to the new cell, mark it with the
number "2".

7. Starting from the cell you just marked (with the number "
2"), travel to a different cell by following the rules a.
and b. shown above.

8. Once you have traveled to the new cell, mark it with the
number "3".

See the pattern? Now you need to travel from the one you
just marked (with the number "3") to a new cell (which you
will mark with the number "4"). Continue this process until
you have marked all cells in the grid (the last cell will be
marked with the number "25" for a 5x5 grid).

Hope that helps.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)

iD8DBQFE3RCxmV9O7RYnKMcRArNPAJ4/O6aT5q7bAsoPxW/3BR+Vq67SFACeM2GS
kZxiWDHlj5vhODZUgI9b8lg=
=Kpuu
-----END PGP SIGNATURE-----