2D Arrays

Cervantes · **Posted:** Fri Aug 05, 2005 7:19 pm

I'm having difficulty working with 2D arrays in Ruby.

Ruby:

grid = [5, 5] #I'm just guessing at the syntax here
5.times do |j|
5.times do |k|
grid [j, k] = j * k
end
end
=> 5
grid.display
0481216=>nil
grid [0, 4]
=> [0, 4, 8, 12]
grid [4, 0]
=> []

Would someone kindly shed some light on what is going on here, and how to use 2D arrays properly? Smile

Thanks

wtd · **Posted:** Fri Aug 05, 2005 7:38 pm

There's no such thing as a two dimensional array in Ruby. An array can hold any kind of object, including other arrays, so you just have an array of arrays.

code:

grid = Array.new(5) do | j |
Array.new(5) do | k |
j * k
end
end

I think that does what you want.

Then to access, (3, 2):

code:

puts grid[3][2]

Cervantes · **Posted:** Fri Aug 05, 2005 7:44 pm

Intriguing Smile

Thanks wtd! That works just fine.

wtd · **Posted:** Fri Aug 05, 2005 10:34 pm

Embrace the power of blocks. Smile

wtd · **Posted:** Fri Aug 05, 2005 10:40 pm

Or in "I hate whitespace" mode...

code:

grid=Array.new(5){|j|Array.new(5){|k|j*k}}

Cervantes · **Posted:** Sat Aug 06, 2005 7:01 am

Using my newfound knowledge of the make-shift 2D array, I tried to convert the N-Queen's solver into Ruby. I failed:

Ruby:

class NQueensSolver

def initialize
@N = 3
@solutions = 0
@grid = Array.new(@N) do |x|
Array.new(@N) do |y|
false
end
end
end

def display
@N.times do |x|
@N.times do |y|
if @grid [x] [y]
print "1"
else
print "0"
end
end
puts ""
end
end

def clearSpot (x, y)
@N.times do |i|
if @grid[i] [y] == true
return false
elsif x + i <= @N - 1 and y + i <= @N - 1 and @grid[x + i] [ y + i]
return false
elsif x - i >= 0 and y + i <= @N - 1 and @grid[x - i] [ y + i]
return false
elsif x + i <= @N - 1 and y - i >= 0 and @grid[x + i] [ y - i]
return false
elsif x - i >= 0 and y - i >= 0 and @grid[x - i] [ y - i]
return false
end
end
return true
end

def displaySolutions
"Number of solutions found on a #{@N} by #{@N} grid: #{@solutions}"
end

def solve(col)
if col >= @N - 1
return 0
end if
@N.times do |i|
if clearSpot(col, i) == true
@grid[col] [i] = true
if col == @N
@solutions += 1
end
end
solve(col + 1)
@grid[col][i] = false
end
end

end

puts NQueensSolver.new.solve(0).displaySolutions

When run, this program says:

Quote:

n_queens.rb:52in 'solve': stack level too deep (SystemStackError)

Then if goes through "from this method, from that method" a lot of times, then it says 1038 levels later, and lists the last three methods that it traced.
I can't understand why this isn't working, especially since I've got @N set to a measily 3! A 3x3 grid should be very simple to solve. I've lifted this code from zylum's NQueen's solver in Turing, which does work. Here's his code:

Turing:

setscreen ("offscreenonly,graphics:500;500,nobuttonbar")

const N := 8
const gridSize := maxx div (N + 2)
var grid : array 1 .. N, 1 .. N of boolean
var solutions : int := 0
colorback (grey)

fcn clearSpot (i, j : int) : boolean
for k : 1 .. N
if grid (k, j) then
result false
elsif i + k <= N and j + k <= N and grid (i + k, j + k) then
result false
elsif i - k > 0 and j - k > 0 and grid (i - k, j - k) then
result false
elsif i + k <= N and j - k > 0 and grid (i + k, j - k) then
result false
elsif i - k > 0 and j + k <= N and grid (i - k, j + k) then
result false
end if
end for
result true
end clearSpot

proc drawGrid
drawfillbox (0, 0, maxx, maxy, grey)
for i : 1 .. N
for j : 1 .. N
if grid (i, j) then
drawfillbox (i * gridSize, j * gridSize, i * gridSize + gridSize, j * gridSize + gridSize, black)
else
drawfillbox (i * gridSize, j * gridSize, i * gridSize + gridSize, j * gridSize + gridSize, white)
end if
drawbox (i * gridSize, j * gridSize, i * gridSize + gridSize, j * gridSize + gridSize, black)
end for
end for
end drawGrid

proc Solve (col : int)
if col > N then
return
end if
for i : 1 .. N
if clearSpot (col, i) then
grid (col, i) := true
if col = N then
solutions += 1
%/* <- take out '%' to comment this block (may need to hit F2)
drawGrid
put "SOLUTION!!! (", solutions, ")"
View.Update
cls
Input.Pause
%*/
end if
%/* <- take out '%' to comment this block (may need to hit F2)
cls
drawGrid
View.Update
delay (250)
%*/
Solve (col + 1)
grid (col, i) := false
end if
end for
end Solve

for i : 1 .. N
for j : 1 .. N
grid (i, j) := false
end for
end for

Solve (1)
put "Solutions: ", solutions, " Time: ", Time.Elapsed / 1000
View.Update

Also, are there any other ways I can shorten/simplify my program? I was wondering about this bit:

Ruby:

if @grid [x] [y]
print "1"
else
print "0"
end

Since if statements can return a value, I was looking to do something like this:

Ruby:

print
if @grid [x] [y]
"1"
else
"0"
end

But that is printing "nil" instead of 1's and 0's.

Once again, thanks in advance!

zylum · **Posted:** Sat Aug 06, 2005 7:21 am

one mistake i see:

code:

def solve(col)
if col >= @N - 1
return 0
end if
@N.times do |i|
if clearSpot(col, i) == true
@grid[col] [i] = true
if col == @N
@solutions += 1
end
end
solve(col + 1)
@grid[col][i] = false
end
end

you should not call solve(col + 1) unless you have successfully placed a peice in the current column. it should be:

code:

def solve(col)
if col >= @N - 1
return 0
end if
@N.times do |i|
if clearSpot(col, i) == true
@grid[col] [i] = true
if col == @N
@solutions += 1
end
solve(col + 1)
@grid[col][i] = false
end
end
end

also, there are no solutions for 3x3 board, so that may cause some issues as well although i doubt it.

Cervantes · **Posted:** Sat Aug 06, 2005 10:47 am

Thanks for pointing that out zylum. Unfortunately, I've still got some problems, though that fixes the stack overflow. Laughing

The next error wrote:

n_queens.rb:33:in 'clearSpot': undefined method '[]' for nil:NilClass (NoMethodError)

Then it lists about 20 levels of methods.
I don't understand where the nil is coming in. If I have an array

Ruby:

my_arr = Array.new(5) { |j| j }

then calling

Ruby:

my_arr [6]

yields nil. But I don't see why I should be encountering nil, because my checks should be within the bounds of the array. Right now I've switched from using "and" to "&&". Is "&&" similar to as it is in Java? That is, if an if statement is set up like this

code:

if condition1 && condition2

and condition1 fails, will condition2 even be checked? I hope not.

Thoughts? Thanks once again.

wtd · **Posted:** Sat Aug 06, 2005 2:30 pm

Ruby's arrays are indexed starting at zero, not one.

Cervantes · **Posted:** Sat Aug 06, 2005 3:48 pm

I know. That's why you see a bunch of minus one after @N in my code. That's also why I start the solve at column 0, and why I check if x - i or y - i is >= 0, not 1. Aah, I just discovered I forgot to subtract one from @N in my check for victory. That doesn't make any difference though. That just changes the number of solutions found, which, so far, has been none.

wtd · **Posted:** Sat Aug 06, 2005 4:25 pm

Can you please post your current code, exactly as you're using it? Smile

Cervantes · **Posted:** Sat Aug 06, 2005 5:04 pm

Sure.

Ruby:

class NQueensSolver

def initialize
@N = 4
@solutions = 0
@grid = Array.new(@N) do |x|
Array.new(@N) do |y|
false
end
end
end

def display
@N.times do |x|
@N.times do |y|
print @output =
if @grid [x] [y]
"1"
else
"0"
end
end
puts ""
end
end

def clearSpot (x, y)
@N.times do |i|
if @grid[i] [y]
return false
elsif x + i <= @N - 1 && y + i <= @N - 1 && @grid[x + i] [ y + i]
return false
elsif x - i >= 0 && y + i <= @N - 1 && @grid[x - i] [ y + i]
return false
elsif x + i <= @N - 1 && y - i >= 0 && @grid[x + i] [ y - i]
return false
elsif x - i >= 0 && y - i >= 0 && @grid[x - i] [ y - i]
return false
end
end
return true
end

def displaySolutions
"Number of solutions found on a #{@N} by #{@N} grid: #{@solutions}"
end

def solve(col)
if col >= @N - 1
return 0
end if
@N.times do |i|
if clearSpot(col, i)
@grid[col] [i] = true
if col == @N - 1
@solutions += 1
end
solve(col + 1)
@grid[col] [i] = false
end
end
end

end

NQueensSolver.new.solve(0).displaySolutions

wtd · **Posted:** Sat Aug 06, 2005 5:39 pm

code:

elsif x - i >= 0 && y + i <= @N - 1 && @grid[x - i] [ y + i]

Something's happening here. I don't think your bounds checking is sufficient, though my head hurts too much right now to rewrite it.

Cervantes · **Posted:** Sat Aug 06, 2005 7:07 pm

I just did a check and the && works as in Java. If the first condition is false then the second condition will not be checked. Since this rules the possibility of checking outside the grid's bounds, I'm stunped as well.

wtd · **Posted:** Sat Aug 06, 2005 7:27 pm

Are you certain? In each of those checks it looks like you're only checking one boundary. For instance:

code:

x - 1 >= 0

Only checks the lower boundary.

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members