[QUIZ] Newbie doubts about the quiz

[Marcelo Alvim]

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.

 

[Elliot Temple]

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/

 

[Justin Collins]

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

 

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

Regards, Morton

 

[James Edward Gray II]

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

 

[Marcelo Alvim]

Well, you might look at the solution I posted earlier today for

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.

 

[James Edward Gray II]

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

 

[darren kirby]

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

 

[Morton Goldberg]

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

 

[Daniel Waite]

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!

 

[darren kirby]

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

quoth the Daniel Waite:

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

 

[Matthew Moss]

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.

 

[darren kirby]

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

 

[Daniel Martin]

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

 

[Kroeger, Simon (ext)]

=20

From: Daniel Martin [mailto:[email protected]]=20
Sent: Wednesday, August 16, 2006 4:21 AM
=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

 

[Marcelo Alvim]

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.