[QUIZ] Pen and Paper (#90)

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

  1. Ruby Quiz

    Ruby Quiz Guest

    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
    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.
    Ruby Quiz, Aug 11, 2006
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. Ruby Quiz

    Mat Schaffer Guest

    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
    #3
  4. 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
    #4
  5. Ruby Quiz

    Mat Schaffer Guest

    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
    #5
  6. 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
    #6
  7. -----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
    #7
  8. Ruby Quiz

    Trans Guest

    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
    > 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.
    Trans, Aug 11, 2006
    #8
  9. 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
    #9
  10. 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
    #10
  11. 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
    #11
  12. 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
    #12
  13. 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
    #13
  14. 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
    #14
  15. Ruby Quiz

    Trans Guest

    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
    #15
  16. 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
    #16
  17. ---------------------------------
    | 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
    #17
  18. 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
    #18
  19. 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
    #19
  20. 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. :D

    James Edward Gray II
    James Edward Gray II, Aug 12, 2006
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Manuel Graune

    python as pen and paper substitute

    Manuel Graune, Apr 6, 2010, in forum: Python
    Replies:
    18
    Views:
    459
    Manuel Graune
    Apr 10, 2010
  2. Ian Collins
    Replies:
    17
    Views:
    597
    Francesco S. Carta
    Aug 3, 2010
  3. David Tran
    Replies:
    6
    Views:
    167
    Morton Goldberg
    Aug 17, 2006
  4. Rick DeNatale
    Replies:
    2
    Views:
    266
    Daniel Martin
    Aug 16, 2006
  5. Ruby Quiz

    [SUMMARY] Pen and Paper (#90)

    Ruby Quiz, Aug 17, 2006, in forum: Ruby
    Replies:
    6
    Views:
    150
    Morton Goldberg
    Aug 18, 2006
Loading...

Share This Page