Newbie doubts about the quiz

[marcelo_a]

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

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

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

Curiosity Blog – Elliot Temple

[marcelo_a]

Marcelo A. wrote:

At each place of the board, I’ll probably put the number that is

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

[marcelo_a]

On Aug 15, 2006, at 4:34 PM, Morton G. 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 G. II

[marcelo_a]

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

[marcelo_a]

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

On Aug 15, 2006, at 3:49 PM, Marcelo A. 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 T.'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 G. II

[marcelo_a]

On Aug 15, 2006, at 5:51 PM, James Edward G. II wrote:

On Aug 15, 2006, at 4:34 PM, Morton G. 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

[marcelo_a]

Marcelo A. 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!

[marcelo_a]

quoth the Morton G.:

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. 55 was reasonable,
66
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
implement a
way to score each potential move’s /potential moves/ and go with the one
with
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
random/brute force solutions are doing. It seems this is called a
“Warnsdorff
heuristic” though I wouldn’t have known this but for Sander L.'s post.

Of course other’s solutions have implemented this better than mine as
they are
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.

Regards, Morton

-d

[marcelo_a]

quoth the Daniel W.:

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

-d

[marcelo_a]

quoth the darren kirby:

rubyquiz.org

Check that, it is really:

rubyquiz.com

My bad,
-d

[marcelo_a]

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.

[marcelo_a]

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.

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

---

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

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

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

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

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

cheers

Simon

[marcelo_a]

“Marcelo A.” [email protected] 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

[marcelo_a]

“Kroeger, Simon (ext)” [email protected] writes:

class << my_array
I don’t know if this is really the right way, but the
OP was asking for a super-cool Ruby-esque way, right?

Well, yeah, but in the context of the problem what you need is a
two-dimensional array:

n = (ARGV.first||‘6’).to_i
my_array = Array.new(n) {
inner = Array.new(n) {0}
class << inner
def [] index
return nil if index < 0
super
end
end
inner
}
class << my_array
def [] index
return [] if index < 0
ret = super
return [] if ret == nil
ret
end
end

I could compress three lines there into “super or []”, but I don’t
know if the OP wants to maybe use “true” and “false” as values in his
array.

Once you do this, you properly get nil for all of:

my_array[0][-1]
my_array[-1][0]
my_array[n][0]
my_array[0][n]

Now, can someone build this into a generic n-dim array class without
using all these singleton classes?

[marcelo_a]

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.