How to detect vertical and horizontal lines in a 2d Array?

#1

I’ve been fiddling around with a little Sratch Ticket game but not entirely sure how to detect lines.
Crystal Playground

The part where I’m stuck at is in the check_winners method. I am not sure how to detect if a horizontal or vertical line is matched. For example:

         2   5  8  10
Prize 10 [0, 0, 1, 0]
Prize 20 [1, 1, 1, 1]
Prize 45 [1, 0, 1, 1]
Prize 50 [0, 0, 1, 0]

Prize 20 and 8 would be the winners.

class Board
  property rows = 4
  property columns = 4
  property board = Array(Array(Int32)).new
  property prizes = {10, 20, 45, 50, 70, 90}
  property prizes_top = {2, 5, 8, 10}
  
  def initialize()
    @board = create_matrix(rows, columns)
    
    print_board
    check_winners
  end
  
  
  def check_winners
    puts "Winners:"
    
    
    board.each_with_index do |c, column_i|
      c.each_with_index do |r, row_i|
        value = c[r]
        if value == 1 # we matched something on the board!
        	# However.. not sure how to keep track of the values here to detect
        	# If a player has matched 1 all vertically or horizontally?
      	end
      end
    end
  end
  
  def print_board
    puts "         #{prizes_top[0]}   #{prizes_top[1]}  #{prizes_top[2]}  #{prizes_top[3]}"
    
 	board.each_with_index do |c, i|
      puts "Prize #{prizes[i]} #{c}" 
  	end
    puts "----------------------------------"
  end

  def create_matrix(rows, columns)
  	array = Array(Array(Int32)).new
  	columns.times do |i|
    	array << fill_array(rows)
  	end
  	array
  end

  
  def fill_array(a)
    temp = Array(Int32).new
    a.times do
    	temp << rand(0..1)
    end
    temp
  end
end


Board.new
0 Likes

#2
    win_first_column = true
    columns.times do |c_i|
      win_first_column = false if board[c_i][0] == 0 # first column 
    end
    
    puts win_first_column

This only checks the first vertical column. I think I’m getting closer?

0 Likes

#3

Here’s how I would do that: https://carc.in/#/r/6khk

require "spec"
require "bit_array"

struct Grid
  Size = 4
  property board : StaticArray(BitArray, Size)

  def initialize(@board); end

  def column_is_all_true?(column_number)
    raise "board doesn't have that column" if column_number >= Size
    board.all? { |row| row[column_number] } # (if the all rows is true at the given column number)
  end
  
  def row_is_all_true?(row_number)
    raise "board doesn't have that row" if row_number >= Size
    board[row_number].all? { |column| column } # if every column in this row is true
  end
end

falsey_row = BitArray.new 4
falsey_row.toggle 1
truthy_row = BitArray.new 4, initial: true
grid = Grid.new StaticArray[
  falsey_row,
  truthy_row,
  falsey_row,
  falsey_row
]

describe Grid do
  it "finds the all-true column" do
    grid.column_is_all_true?(1).should be_true
  end
  it "rejects a column that is not all true" do
    grid.column_is_all_true?(0).should be_false
  end
  it "finds the all-true row" do
    grid.row_is_all_true?(1).should be_true
  end
  it "rejects a row that is not all true" do
    grid.row_is_all_true?(2).should be_false
  end
end

Thanks for the fun challenge this morning :slight_smile:

Edit: note that if the Size value isn’t a compile-time constant you need to use Array not StaticArray and if the values are larger than base two then obviously each row would be a StaticArray or Array of a type large enough to hold the data.

1 Like

#4

@scott

Just curious, where is the

Finished in 155 microseconds
4 examples, 0 failures, 0 errors, 0 pending 

Text coming from?

edit: Oh, nvm, comes from require “spec”, just commented it out and it’s gone.

I will have to read more about Static and BitArray’s. Are they more performant than regular Arrays that use Int32 values? Instead of Int32 value types, they are “bits”? If I got that right.

https://crystal-lang.org/api/0.27.2/StaticArray.html
“fixed-size”, I guess that means immutable. So this wouldn’t really be used for an inventory matrix, where player’s can move items around, but for a board game with a fixed set of values to check rows and columns with… would be fine.

I think I am understanding it better

0 Likes

#5

@girng sorry I didn’t see this sooner

StaticArray is an Array whose size is known at compile time (that is, it’s a constant value). It is much more efficient to know the size at compile time than to have to check or store that information as a variable. Just because the size is of a fixed/static value doesn’t mean that the values in the array are immutable.

A BitArray is an array of boolean values. Because computers can only index one byte at a time, a Bool type actually takes up a byte of space despite only representing a bit of data. If you are storing a list of true and false values, you should prefer BitArray over Array(Bool) or even StaticArray(Bool, Size) due to performance.

That said, if their use is appropriate, using a BitArray or StaticArray will be roughly equivalent to using an Array(Bool) or an array whose size is known at compile-time, respectively.

As far as the output, yes, I used specs to “describe” the way my code behaved, sorry if that wasn’t clear.

1 Like

#6

So for your board game example, if you have a board of a size that is known at compile time, then you could use a StaticArray. If you wanted to give the user a setting or command-line argument where they could adjust the size of the board, you’d want to use an Array.

0 Likes

#7

But in general, always use an Array unless you have a serious bottleneck or something. You’ll make your program much more complex if you don’t use Array. In 99.9% of programs you don’t need to know or care about static array or bit array.

1 Like

#8

I see. Very cool. I actually always thought the lowest value we could go for an Array is 1_i8.

In fact, the scratch ticket I am inspired by is the Loteria Ticket here:

So, I would need to use something higher than a BitArray for this case, because there are going to be different items to match on the board. I should have mentioned that in my OP, my apologies! But then again, now I know about Static and BitArray’s, TIL!

Thanks!

0 Likes