[QUIZ] Newbie doubts about the quiz

Discussion in 'Ruby' started by Marcelo Alvim, Aug 15, 2006.

  1. Hey, People.

    I'm a newbie, as the subject implies, and some questions about Ruby
    raised when I was trying to solve this quiz.

    I'm not trying to create a very fast solution, I'm only trying to
    learn mor of the language. So I'm trying a simple depth-first search
    approach.

    I'm going to have this two-dimensional array representing the board.
    At each place of the board, I'll probably put the number that is
    currently on that place.

    The problem, now, is that I chose not to assume the board as a torus,
    but as a flat square. So, I'm doing that simple math going from one
    square to the next: if it's an horizontal move, I add 3 or -3 to X;
    if it's vertical, apply the same to Y; if it's the diagonal, add 2 or
    -2 to both of them. Well, you already know that. Unfortunately, Ruby's
    behavior of wrapping arrays over using their negative indices, which I
    like very much on most cases, is kind of annoying now, since I want to
    invalidate access to negative indices.

    So, I thought of some approaches for "solving" this problem of mine,
    and would like to know your opinions:

    1) I could create a class that extends Array, or encapsulates one, and
    define the #[] and #[]= methods. Then those methods would check the
    negative indices and return nil if they were negative.

    2) I could alias_method those methods for the actual Array classe and
    override the original ones, also checking indices inside (Though I
    think if I use this approach in anything but my simple quiz solution,
    I would have to return the Array class back to normal afterwards).

    3) I could check indices on my code everytime I need, outside of any
    Array class.

    4) You guys could teach me a super-cool Ruby-esque way to do that that
    I can't even think about right now.

    Thanks for your patience,
    Alvim.
     
    Marcelo Alvim, Aug 15, 2006
    #1
    1. Advertising

  2. On Aug 15, 2006, at 1:49 PM, Marcelo Alvim wrote:

    > Hey, People.
    >
    > I'm a newbie, as the subject implies, and some questions about Ruby
    > raised when I was trying to solve this quiz.
    >
    > I'm not trying to create a very fast solution, I'm only trying to
    > learn mor of the language. So I'm trying a simple depth-first search
    > approach.
    >
    > I'm going to have this two-dimensional array representing the board.
    > At each place of the board, I'll probably put the number that is
    > currently on that place.
    >
    > The problem, now, is that I chose not to assume the board as a torus,
    > but as a flat square. So, I'm doing that simple math going from one
    > square to the next: if it's an horizontal move, I add 3 or -3 to X;
    > if it's vertical, apply the same to Y; if it's the diagonal, add 2 or
    > -2 to both of them. Well, you already know that. Unfortunately, Ruby's
    > behavior of wrapping arrays over using their negative indices, which I
    > like very much on most cases, is kind of annoying now, since I want to
    > invalidate access to negative indices.


    one way to do it is take the current position and add/subtract the
    changes, and save that in a variable. don't do an array access yet.
    now you can use some if statements to check the values are OK before
    continuing. that's what i did.

    -- Elliot Temple
    http://www.curi.us/blog/
     
    Elliot Temple, Aug 15, 2006
    #2
    1. Advertising

  3. Marcelo Alvim wrote:
    > Hey, People.
    >
    > I'm a newbie, as the subject implies, and some questions about Ruby
    > raised when I was trying to solve this quiz.
    >
    > I'm not trying to create a very fast solution, I'm only trying to
    > learn mor of the language. So I'm trying a simple depth-first search
    > approach.
    >
    > I'm going to have this two-dimensional array representing the board.
    > At each place of the board, I'll probably put the number that is
    > currently on that place.
    >
    > The problem, now, is that I chose not to assume the board as a torus,
    > but as a flat square. So, I'm doing that simple math going from one
    > square to the next: if it's an horizontal move, I add 3 or -3 to X;
    > if it's vertical, apply the same to Y; if it's the diagonal, add 2 or
    > -2 to both of them. Well, you already know that. Unfortunately, Ruby's
    > behavior of wrapping arrays over using their negative indices, which I
    > like very much on most cases, is kind of annoying now, since I want to
    > invalidate access to negative indices.
    >
    > So, I thought of some approaches for "solving" this problem of mine,
    > and would like to know your opinions:
    >
    > 1) I could create a class that extends Array, or encapsulates one, and
    > define the #[] and #[]= methods. Then those methods would check the
    > negative indices and return nil if they were negative.
    >
    > 2) I could alias_method those methods for the actual Array classe and
    > override the original ones, also checking indices inside (Though I
    > think if I use this approach in anything but my simple quiz solution,
    > I would have to return the Array class back to normal afterwards).
    >
    > 3) I could check indices on my code everytime I need, outside of any
    > Array class.
    >
    > 4) You guys could teach me a super-cool Ruby-esque way to do that that
    > I can't even think about right now.
    >
    > Thanks for your patience,
    > Alvim.


    Or, you could initialize the array with some string (I used '.' in mine,
    to match the quiz) and then check for nil.

    -Justin
     
    Justin Collins, Aug 15, 2006
    #3
  4. Well, you might look at the solution I posted earlier today for
    hints. It's not all that good, but I happened to take an approach
    very similar to what you outline here. It works, but just barely. My
    experience with it is that a simple depth-first search is too slow
    for grids bigger than 6 x 6 (which is pathetic considering some of
    huge grids solved by posted solutions).

    Regards, Morton

    On Aug 15, 2006, at 4:49 PM, Marcelo Alvim wrote:

    > Hey, People.
    >
    > I'm a newbie, as the subject implies, and some questions about Ruby
    > raised when I was trying to solve this quiz.
    >
    > I'm not trying to create a very fast solution, I'm only trying to
    > learn mor of the language. So I'm trying a simple depth-first search
    > approach.
    >
    > I'm going to have this two-dimensional array representing the board.
    > At each place of the board, I'll probably put the number that is
    > currently on that place.
    >
    > The problem, now, is that I chose not to assume the board as a torus,
    > but as a flat square. So, I'm doing that simple math going from one
    > square to the next: if it's an horizontal move, I add 3 or -3 to X;
    > if it's vertical, apply the same to Y; if it's the diagonal, add 2 or
    > -2 to both of them. Well, you already know that. Unfortunately, Ruby's
    > behavior of wrapping arrays over using their negative indices, which I
    > like very much on most cases, is kind of annoying now, since I want to
    > invalidate access to negative indices.
    >
    > So, I thought of some approaches for "solving" this problem of mine,
    > and would like to know your opinions:
    >
    > 1) I could create a class that extends Array, or encapsulates one, and
    > define the #[] and #[]= methods. Then those methods would check the
    > negative indices and return nil if they were negative.
    >
    > 2) I could alias_method those methods for the actual Array classe and
    > override the original ones, also checking indices inside (Though I
    > think if I use this approach in anything but my simple quiz solution,
    > I would have to return the Array class back to normal afterwards).
    >
    > 3) I could check indices on my code everytime I need, outside of any
    > Array class.
    >
    > 4) You guys could teach me a super-cool Ruby-esque way to do that that
    > I can't even think about right now.
    >
    > Thanks for your patience,
    > Alvim.
    >
     
    Morton Goldberg, Aug 15, 2006
    #4
  5. On Aug 15, 2006, at 4:34 PM, Morton Goldberg wrote:

    > Well, you might look at the solution I posted earlier today for
    > hints. It's not all that good, but I happened to take an approach
    > very similar to what you outline here. It works, but just barely.
    > My experience with it is that a simple depth-first search is too
    > slow for grids bigger than 6 x 6 (which is pathetic considering
    > some of huge grids solved by posted solutions).


    I'm uncomfortable with the word "pathetic" here.

    Remember that we have all level of people who like to play with the
    quizzes. If someone only manages to get a slow solution together,
    that's still a solution! Even better, they gained enough
    understanding of the problem, that they can then look to the summary
    and other solutions for tricks they might try next time.

    If you have fun, challenge yourself a little, and even learn
    something, the quiz is a big win I say.

    I wouldn't think, "Wow, my solution sucks." Instead, I would think,
    "OK, that's tougher than it looks. Let me go see how these guys made
    it go so fast..." ;)

    James Edward Gray II
     
    James Edward Gray II, Aug 15, 2006
    #5
  6. > > Well, you might look at the solution I posted earlier today for
    > > hints. It's not all that good, but I happened to take an approach
    > > very similar to what you outline here. It works, but just barely.
    > > My experience with it is that a simple depth-first search is too
    > > slow for grids bigger than 6 x 6 (which is pathetic considering
    > > some of huge grids solved by posted solutions).

    >
    > I'm uncomfortable with the word "pathetic" here.
    >
    > Remember that we have all level of people who like to play with the
    > quizzes. If someone only manages to get a slow solution together,
    > that's still a solution! Even better, they gained enough
    > understanding of the problem, that they can then look to the summary
    > and other solutions for tricks they might try next time.
    >
    > If you have fun, challenge yourself a little, and even learn
    > something, the quiz is a big win I say.
    >
    > I wouldn't think, "Wow, my solution sucks." Instead, I would think,
    > "OK, that's tougher than it looks. Let me go see how these guys made
    > it go so fast..." ;)


    Yeah, that's exactly how I think, and I bet that's even how Morton thinks. :)

    I am really trying only to learn more about the language, and I'm
    DEFINITELY taking a look at other people's solutions in order to learn
    their approaches.

    By the way, thanks a lot to all of you for the help!

    Cheers,
    Alvim.
     
    Marcelo Alvim, Aug 15, 2006
    #6
  7. On Aug 15, 2006, at 3:49 PM, Marcelo Alvim wrote:

    > 1) I could create a class that extends Array, or encapsulates one, and
    > define the #[] and #[]= methods. Then those methods would check the
    > negative indices and return nil if they were negative.


    I think this solution would work out fine. Others have given you
    great ideas as well.

    Here's a validation method used in David Tran's solution to verify
    that the indices selected are good:

    def valid(x, y)
    x >= 0 && x < @size && y >= 0 && y < @size && !@board[x][y]
    end

    See how it ensures they are between 0 and @size? It also checks that
    the @board is nil at x, y.

    Hope that helps.

    James Edward Gray II
     
    James Edward Gray II, Aug 15, 2006
    #7
  8. Marcelo Alvim

    darren kirby Guest

    --nextPart3642194.UFVOC9M0qZ
    Content-Type: text/plain;
    charset="iso-8859-1"
    Content-Transfer-Encoding: quoted-printable
    Content-Disposition: inline

    quoth the Morton Goldberg:
    > Well, you might look at the solution I posted earlier today for
    > hints. It's not all that good, but I happened to take an approach
    > very similar to what you outline here. It works, but just barely. My
    > experience with it is that a simple depth-first search is too slow
    > for grids bigger than 6 x 6 (which is pathetic considering some of
    > huge grids solved by posted solutions).


    This is exactly the problem my first solution had. 5*5 was reasonable, 6*6=
    =20
    took over a minute, and I gave up on 7*7 after ~30 minutes.

    I finally realized ( thanks to other solutions posted) that if you implemen=
    t a=20
    way to score each potential move's /potential moves/ and go with the one wi=
    th=20
    the least amount it makes the solution _waaay_ faster (almost like magic).

    As far as I can tell this is what pretty much every solution other than=20
    random/brute force solutions are doing. It seems this is called a "Warnsdor=
    ff=20
    heuristic" though I wouldn't have known this but for Sander Land's post.

    Of course other's solutions have implemented this better than mine as they =
    are=20
    still several orders of magnitude faster than my second solution.

    I tried optimizing a bit this morning but wasn't able to improve it at all.=
    =20

    > Regards, Morton
    >


    =2Dd
    =2D-=20
    darren kirby :: Part of the problem since 1976 :: http://badcomputer.org
    "...the number of UNIX installations has grown to 10, with more expected..."
    =2D Dennis Ritchie and Ken Thompson, June 1972

    --nextPart3642194.UFVOC9M0qZ
    Content-Type: application/pgp-signature

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

    iD8DBQBE4ke1wPD5Cr/3CJgRAl9JAJ9pqUxif1whx8yWSozRQjUdK23RrQCgttBd
    LZgOEZmDVApdGcP9ULvOSeU=
    =4XuW
    -----END PGP SIGNATURE-----

    --nextPart3642194.UFVOC9M0qZ--
     
    darren kirby, Aug 15, 2006
    #8
  9. On Aug 15, 2006, at 5:51 PM, James Edward Gray II wrote:

    > On Aug 15, 2006, at 4:34 PM, Morton Goldberg wrote:
    >
    >> Well, you might look at the solution I posted earlier today for
    >> hints. It's not all that good, but I happened to take an approach
    >> very similar to what you outline here. It works, but just barely.
    >> My experience with it is that a simple depth-first search is too
    >> slow for grids bigger than 6 x 6 (which is pathetic considering
    >> some of huge grids solved by posted solutions).

    >
    > I'm uncomfortable with the word "pathetic" here.


    Pathetic is as pathetic behaves. :) And perhaps I should have put the
    smiley after my original use of "pathetic". Because I meant it in a
    self-deprecating, jokey way, it never occurred to me that I would
    upset anyone.

    I'm not ashamed of my solution. If I were, I wouldn't have posted it.
    But performance is not one of virtues, and there is no sense in
    pretending otherwise. It does, I believe, have the merit of
    simplicity, and I'm vain enough to think it's kind of pretty, code-
    wise, which I why I commended it to the OP.

    > Remember that we have all level of people who like to play with the
    > quizzes. If someone only manages to get a slow solution together,
    > that's still a solution! Even better, they gained enough
    > understanding of the problem, that they can then look to the
    > summary and other solutions for tricks they might try next time.
    >
    > If you have fun, challenge yourself a little, and even learn
    > something, the quiz is a big win I say.


    Oh, I had fun. And the fun's not over. I expect to learn a lot when I
    read the other solutions. There a good chance I'll steal a few ideas
    and rewrite my code so it can handle big grids. It was an interesting
    problem. From the amount of discussion and the number of solutions
    posted, I would say that of lot people thought so.

    > I wouldn't think, "Wow, my solution sucks." Instead, I would
    > think, "OK, that's tougher than it looks. Let me go see how these
    > guys made it go so fast..." ;)


    I have no difficulty thinking both those things at the same time. And
    two impossible thing before breakfast :)

    Regards, Morton
     
    Morton Goldberg, Aug 16, 2006
    #9
  10. Marcelo Alvim

    Daniel Waite Guest

    Re: Newbie doubts about the quiz

    Marcelo Alvim wrote:
    > I'm a newbie, as the subject implies, and some questions about Ruby
    > raised when I was trying to solve this quiz.


    What quiz are you referring to? I want to try! :)

    --
    Posted via http://www.ruby-forum.com/.
     
    Daniel Waite, Aug 16, 2006
    #10
  11. Marcelo Alvim

    darren kirby Guest

    Re: Newbie doubts about the quiz

    --nextPart11129414.Ihl5FnOKaf
    Content-Type: text/plain;
    charset="utf-8"
    Content-Transfer-Encoding: quoted-printable
    Content-Disposition: inline

    quoth the Daniel Waite:
    > Marcelo Alvim wrote:
    > > I'm a newbie, as the subject implies, and some questions about Ruby
    > > raised when I was trying to solve this quiz.

    >
    > What quiz are you referring to? I want to try! :)


    Number 90 :: Pen and Paper.

    Search the archives or hit: rubyquiz.org

    =2Dd
    =2D-=20
    darren kirby :: Part of the problem since 1976 :: http://badcomputer.org
    "...the number of UNIX installations has grown to 10, with more expected..."
    =2D Dennis Ritchie and Ken Thompson, June 1972

    --nextPart11129414.Ihl5FnOKaf
    Content-Type: application/pgp-signature

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

    iD8DBQBE4m3LwPD5Cr/3CJgRAlTIAKDgIRiLB+VFWds0itQM0T9Q4o+IlQCg6bLm
    TRHMr109t6xPQ/uxAKBUfSY=
    =0R4q
    -----END PGP SIGNATURE-----

    --nextPart11129414.Ihl5FnOKaf--
     
    darren kirby, Aug 16, 2006
    #11
  12. Marcelo Alvim

    Matthew Moss Guest

    > 4) You guys could teach me a super-cool Ruby-esque way to do that that
    > I can't even think about right now.


    I haven't submitted a solution... I started working on one, but just
    haven't had time to complete it. But I did start with something like
    this:

    class Coord
    attr_reader :x, :y

    def initialize(x, y)
    @x, @y = x, y
    end

    def valid(n) # returns true if coord fits on an n-square board
    (0...n).include?(@x) and (0...n).include?(@y)
    end

    def to_s
    "(#{@x}, #{@y})"
    end

    def adjacents
    [ Coord.new(@x, @y - 3),
    Coord.new(@x, @y + 3),
    Coord.new(@x - 3, @y),
    Coord.new(@x + 3, @y),
    Coord.new(@x - 2, @y - 2),
    Coord.new(@x - 2, @y + 2),
    Coord.new(@x + 2, @y - 2),
    Coord.new(@x + 2, @y + 2)
    ]
    end
    end

    Then, let's say you randomly start at (1, 3). You can get started like:

    c = Coord.new(1, 3)
    c.adjacents.each { |d| puts d if d.valid(5) }

    Not terribly efficient, but you know what they say... Vi is at the
    heart of evil... I mean, premature optimization is terribly
    effective... Wait a sec... That's not right.
     
    Matthew Moss, Aug 16, 2006
    #12
  13. Marcelo Alvim

    darren kirby Guest

    Re: Newbie doubts about the quiz

    --nextPart1189583.VvbbpNS647
    Content-Type: text/plain;
    charset="iso-8859-6"
    Content-Transfer-Encoding: quoted-printable
    Content-Disposition: inline

    quoth the darren kirby:
    > rubyquiz.org


    Check that, it is really:

    rubyquiz.com

    My bad,
    =2Dd
    =2D-=20
    darren kirby :: Part of the problem since 1976 :: http://badcomputer.org
    "...the number of UNIX installations has grown to 10, with more expected..."
    =2D Dennis Ritchie and Ken Thompson, June 1972

    --nextPart1189583.VvbbpNS647
    Content-Type: application/pgp-signature

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

    iD8DBQBE4nvXwPD5Cr/3CJgRArpRAKChHYtCiDwmez5JyKhds4cgXbtSMgCfQG1H
    DBEefZAMUbWA3wdbzfj5mgs=
    =suBY
    -----END PGP SIGNATURE-----

    --nextPart1189583.VvbbpNS647--
     
    darren kirby, Aug 16, 2006
    #13
  14. "Marcelo Alvim" <> writes:

    > 4) You guys could teach me a super-cool Ruby-esque way to do that that
    > I can't even think about right now.


    Note that what I did to solve this was at each step to copy the cells
    in the neighborhood of the current cell to a 13 by 13 array so that
    the current cell is the middle. This then frees me from thinking
    about wraparound or bounds checking while computing which move to make
    next.

    Of course, this is only possible if you have a fast way to copy a
    rectangular chunk of one two-dimensional array to another. Since I
    was using NArray, I had that.

    http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/208295
     
    Daniel Martin, Aug 16, 2006
    #14
  15. =20

    > From: Daniel Martin [mailto:]=20
    > Sent: Wednesday, August 16, 2006 4:21 AM
    >=20
    > "Marcelo Alvim" <> writes:
    >=20
    > > 4) You guys could teach me a super-cool Ruby-esque way to=20

    > do that that
    > > I can't even think about right now.

    >=20
    > Note that what I did to solve this was at each step to copy the cells
    > in the neighborhood of the current cell to a 13 by 13 array so that
    > the current cell is the middle. This then frees me from thinking
    > about wraparound or bounds checking while computing which move to make
    > next.
    >=20
    > Of course, this is only possible if you have a fast way to copy a
    > rectangular chunk of one two-dimensional array to another. Since I
    > was using NArray, I had that.


    You know I like NArray, but perhaps there is an even=20
    cooler way this time :)

    -----------------------------------------------
    my_array =3D [1, 2, 3]
    another_one =3D [1, 2, 3]

    p my_array[-1] #=3D> 3 grmpf...
    p another_one[-1] #=3D> 3 yeah, what else?

    class << my_array
    def [] index
    return nil if index < 0
    super
    end
    end

    p my_array[-1] #=3D> nil, hehe, nice!
    p another_one[-1] #=3D> 3 woot, woot
    -----------------------------------------------

    I don't know if this is really the right way, but the=20
    OP was asking for a super-cool Ruby-esque way, right?

    cheers

    Simon
     
    Kroeger, Simon (ext), Aug 16, 2006
    #15
  16. > You know I like NArray, but perhaps there is an even
    > cooler way this time :)
    >
    > # [super-cool Ruby-esque way of doing what I wanted snipped]


    Yeah, I KNEW there should be something. :)

    And thanks, all, for all your answers, it was really enlightening to
    read all of them!

    Cheers,
    Alvim.
     
    Marcelo Alvim, Aug 16, 2006
    #16
    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. Edgar A. Rodriguez

    Newbie with some doubts.

    Edgar A. Rodriguez, Jan 5, 2006, in forum: Python
    Replies:
    13
    Views:
    436
    Peter Maas
    Jan 12, 2006
  2. Ruby Quiz

    [QUIZ] Animal Quiz (#15)

    Ruby Quiz, Jan 14, 2005, in forum: Ruby
    Replies:
    11
    Views:
    427
    James Edward Gray II
    Jan 18, 2005
  3. David Tran
    Replies:
    9
    Views:
    247
    David Tran
    Jan 21, 2005
  4. Ruby Quiz

    [QUIZ] 1-800-THE-QUIZ (#20)

    Ruby Quiz, Feb 18, 2005, in forum: Ruby
    Replies:
    15
    Views:
    353
    gabriele renzi
    Feb 24, 2005
  5. Daniel Moore
    Replies:
    10
    Views:
    335
    James Gray
    Jan 31, 2009
Loading...

Share This Page