# [QUIZ] Pen and Paper (#90)

Discussion in 'Ruby' started by Ruby Quiz, Aug 11, 2006.

1. ### Ruby QuizGuest

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.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
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:

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

Ruby Quiz, Aug 11, 2006

2. ### James Edward Gray IIGuest

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

James Edward Gray II, Aug 11, 2006

3. ### Mat SchafferGuest

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

Mat Schaffer, Aug 11, 2006
4. ### James Edward Gray IIGuest

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

James Edward Gray II, Aug 11, 2006
5. ### Mat SchafferGuest

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

Mat Schaffer, Aug 11, 2006
6. ### Elliot TempleGuest

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.curi.us/blog/

Elliot Temple, Aug 11, 2006
7. ### Suraj N. KurapatiGuest

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

Suraj N. Kurapati, Aug 11, 2006
8. ### TransGuest

Re: Pen and Paper (#90)

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.rubyquiz.com/
>
> 3. Enjoy!
>
> Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
> 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.

Trans, Aug 11, 2006
9. ### Elliot TempleGuest

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.curi.us/blog/

Elliot Temple, Aug 11, 2006
10. ### Justin CollinsGuest

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.curi.us/blog/

[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

Justin Collins, Aug 11, 2006
11. ### Suraj N. KurapatiGuest

Re: Pen and Paper (#90)

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

Suraj N. Kurapati, Aug 12, 2006
12. ### Elliot TempleGuest

On Aug 11, 2006, at 3:52 PM, Justin Collins wrote:

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

ok i came up with a new approach. it doesn't have failed runs
anymore. it has a minor restriction on what it can do. i didn't do
anything to optimize it.

cg5:~/cs/rb/ruby quizzes >time ruby 90cheat.rb 500

real 0m0.650s
user 0m0.586s
sys 0m0.026s
cg5:~/cs/rb/ruby quizzes >time ruby 90cheat.rb 2000

real 0m41.895s
user 0m36.671s
sys 0m0.719s
cg5:~/cs/rb/ruby quizzes >time ruby 90cheat.rb 5000

real 9m26.551s
user 8m11.184s
sys 0m10.997s

-- Elliot Temple
http://www.curi.us/blog/

Elliot Temple, Aug 12, 2006
13. ### Justin CollinsGuest

Elliot Temple wrote:
> ok i came up with a new approach. it doesn't have failed runs anymore.
> it has a minor restriction on what it can do. i didn't do anything to
> optimize it.
>
> cg5:~/cs/rb/ruby quizzes >time ruby 90cheat.rb 500
>
> real 0m0.650s
> user 0m0.586s
> sys 0m0.026s
> cg5:~/cs/rb/ruby quizzes >time ruby 90cheat.rb 2000
>
> real 0m41.895s
> user 0m36.671s
> sys 0m0.719s
> cg5:~/cs/rb/ruby quizzes >time ruby 90cheat.rb 5000
>
> real 9m26.551s
> user 8m11.184s
> sys 0m10.997s
>
>
> -- Elliot Temple
> http://www.curi.us/blog/

Hmm, I was going to post some new times, but those blow mine away. I'm
still stuck on the nondeterministic approach...looks like you guys are
finding actual methods of solving the game.

Nice!

-Justin

Justin Collins, Aug 12, 2006
14. ### James Edward Gray IIGuest

Re: Pen and Paper (#90)

On Aug 11, 2006, at 6:21 PM, Suraj N. Kurapati wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Trans wrote:
>> Could you explain the rules of game a little better.

This is a great answer. Let me just add one minor point...

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

If you cannot make a move at any point (using either of the two move
rules), the game is lost.

James Edward Gray II

James Edward Gray II, Aug 12, 2006
15. ### TransGuest

Re: Pen and Paper (#90)

Suraj N. Kurapati wrote:
> -----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).

Ah. okay. Consecutive order. That's what I was missing. Thanks Suraj.

T.

Trans, Aug 12, 2006
16. ### Elliot TempleGuest

I changed something and got:

cg5:~/cs/rb/ruby quizzes >time ruby 90cheat.rb 4000

real 0m37.412s
user 0m31.385s
sys 0m1.846s
cg5:~/cs/rb/ruby quizzes >time ruby 90cheat.rb 10000

real 10m56.151s
user 9m8.446s
sys 0m30.292s

For 10,000 i saw in Activity Monitor it claimed to be using 1.7 gigs
of real ram, and another 1.7 of virtual at some point near-ish the end.

Elliot

Elliot Temple, Aug 12, 2006
17. ### Morton GoldbergGuest

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

It took a while for the penny to drop. My question is: how did you
find the _first_ 6 x 6 solution and long did _that_ take?

Regards, Morton

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)

>
> \$ 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
>

Morton Goldberg, Aug 12, 2006
18. ### James Edward Gray IIGuest

On Aug 12, 2006, at 2:22 PM, Morton Goldberg wrote:

> ---------------------------------
> | 1 30 12 2 29 13 |
> | 20 33 27 15 34 8 |
> | 11 3 36 31 4 23 |
> | 26 16 19 7 28 14 |
> | 21 32 10 22 35 9 |
> | 18 6 25 17 5 24 |
> ---------------------------------
>
> It took a while for the penny to drop. My question is: how did you
> find the _first_ 6 x 6 solution and long did _that_ take?

'Bout 10 seconds (James time, not computer time). Did you read the
quiz?

James Edward Gray II

James Edward Gray II, Aug 12, 2006
19. ### Morton GoldbergGuest

You mean your first solution was cut and paste from the quiz posting?
That's really cheating!
That's what I did, too, but I was naive enough to believe you wrote a
script that generated at least one solution.

Regards, Morton

On Aug 12, 2006, at 3:33 PM, James Edward Gray II wrote:

> On Aug 12, 2006, at 2:22 PM, Morton Goldberg wrote:
>
>> ---------------------------------
>> | 1 30 12 2 29 13 |
>> | 20 33 27 15 34 8 |
>> | 11 3 36 31 4 23 |
>> | 26 16 19 7 28 14 |
>> | 21 32 10 22 35 9 |
>> | 18 6 25 17 5 24 |
>> ---------------------------------
>>
>> It took a while for the penny to drop. My question is: how did you
>> find the _first_ 6 x 6 solution and [how] long did _that_ take?

>
> 'Bout 10 seconds (James time, not computer time). Did you read the
> quiz?
>
> James Edward Gray II

Morton Goldberg, Aug 12, 2006
20. ### James Edward Gray IIGuest

On Aug 12, 2006, at 3:53 PM, Morton Goldberg wrote:

> You mean your first solution was cut and paste from the quiz
> posting? That's really cheating!
> That's what I did, too

You're cracking me up.

In all fairness, I really would love to go back and add the solver,
but I am very, very busy this weekend. We will see if I can
steal the time.

I bet we're about to see some solvers tomorrow though...

> but I was naive enough to believe you wrote a script that generated
> at least one solution.

The quiz said to build a solution that goes as fast as possible.
Then it gave me an idea for a hell of a shortcut. I couldn't
resist.

James Edward Gray II

James Edward Gray II, Aug 12, 2006