[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[QUIZ] Newbie doubts about the quiz

Marcelo Alvim

8/15/2006 8:50:00 PM

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

Elliot Temple

8/15/2006 8:54:00 PM

0


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

Justin Collins

8/15/2006 8:57:00 PM

0

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

Morton Goldberg

8/15/2006 9:34:00 PM

0

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

James Gray

8/15/2006 9:51:00 PM

0

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

Marcelo Alvim

8/15/2006 10:02:00 PM

0

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

James Gray

8/15/2006 10:05:00 PM

0

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

darren kirby

8/15/2006 10:17:00 PM

0

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
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 Land'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
--
darren kirby :: Part of the problem since 1976 :: http://badco...
"...the number of UNIX installations has grown to 10, with more expected..."
- Dennis Ritchie and Ken Thompson, June 1972

Morton Goldberg

8/15/2006 11:05:00 PM

0

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

Daniel Waite

8/16/2006 12:43:00 AM

0

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

darren kirby

8/16/2006 12:59:00 AM

0

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

-d
--
darren kirby :: Part of the problem since 1976 :: http://badco...
"...the number of UNIX installations has grown to 10, with more expected..."
- Dennis Ritchie and Ken Thompson, June 1972