[QUIZ] Newbie doubts about the quiz

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

2

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

···

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.

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

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.

5

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

···

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.

6

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! :slight_smile:

···

--
Posted via http://www.ruby-forum.com/\.

7

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.

8

"Marcelo Alvim" <malvim@gmail.com> 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

9

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..." :wink:

James Edward Gray II

···

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

10

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://badcomputer.org
"...the number of UNIX installations has grown to 10, with more expected..."
- Dennis Ritchie and Ken Thompson, June 1972

11

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! :slight_smile:

Number 90 :: Pen and Paper.

Search the archives or hit: rubyquiz.org

-d

···

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

12

From: Daniel Martin [mailto:martin@snowplow.org]
Sent: Wednesday, August 16, 2006 4:21 AM

"Marcelo Alvim" <malvim@gmail.com> 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.

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

···

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

13

> 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..." :wink:

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

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.

14

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. :slight_smile: 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..." :wink:

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

Regards, Morton

···

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

On Aug 15, 2006, at 4:34 PM, Morton Goldberg wrote:

15

quoth the darren kirby:

rubyquiz.org

Check that, it is really:

rubyquiz.com

My bad,
-d

···

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

16

"Kroeger, Simon (ext)" <simon.kroeger.ext@siemens.com> writes:

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

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

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?

17

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

# [super-cool Ruby-esque way of doing what I wanted snipped]

Yeah, I KNEW there should be something. :slight_smile:

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

Cheers,
Alvim.