Super2048 (Google apac Test Problem)

Question

This is my second try at writing Ruby. Stylistic feedback is very much appreciated.

The problem:

2048 is played on a simple 4 x 4 grid with tiles that slide smoothly when a player moves them. For each movement, the player can choose to move all tiles in 4 directions, left, right, up, and down, as far as possible at the same time. If two tiles of the same number collide while moving, they will merge into a tile with the total value of the two tiles that collided. In one movement, one newly created tile can not be merged again and always is merged with the tile next to it along the moving direction first. E.g. if the three "2" are in a row "2 2 2" and the player choose to move left, it will become "4 2 0", the most left 2 "2" are merged.

The solution for Super2048 should produce the correct 2048 movement for any N-sized board (all boards are square).

Example Input:

1
4 right
2 0 2 4
2 0 4 2
2 2 4 8
2 2 4 4

Example Output:

Case #1:
0 0 4 4
0 2 4 2
0 4 4 8
0 0 4 8

The Algorithm - first we need identify the rules by which the board movement is made -- it seems that:

• Tiles move as far as possible along empty spaces
• If they collide (equal value) they merge
• Tiles fill in spaces created by merged tiles

Therefore my board_move! code looks like this:

def board_move!(board, move) 
    #move empties 
    move_rows!(board, move)
    #merge all eligible
    merge_rows!(board, move)
    #move into squares emptied by merge
    move_rows!(board, move)
end

It's notable that movement behaves the same in any direction, so if the algorithm could just rotate the board that would be enough. Unlike Python's Numpy - Ruby doesn't give N-dimensional arrays or a convenient rotate method. Here is an outline for the behaviour that the merge_rows! and move_rows! should produce:

"""
merge->left
a[0][0] <- a[0][1] 
a[1][0] <- a[1][1]
a[2][0] <- a[2][1]

merge->right 
a[0][2] <- a[0][1] 
a[1][2] <- a[1][1]
a[2][2] <- a[2][1] 

merge-> up
a[0][0] <- a[1][0]
a[0][1] <- a[1][1]
a[0][2] <- a[1][2]

merge-> down
a[2][0] <- a[1][0] 
a[2][1] <- a[1][1] 
a[2][2] <- a[1][2] 
"""
#Note that the +1 (merging and moving rows) need to have an index 1 less than size to not run out of bounds
#While the slots being merged in each row get the entire index

Therefore it should be enough to have an inner and an outer iterator and a constant for the +1. Here is the merge_rows! method. I didn't really like using the switch, but I think it's not possible to have a pointer to the iterators (i, j) so we re-assign on each loop. In terms of code optimization it should actually only assign a and b once at the top, reassign the outer index only every outer-loop and the inner-index every inner loop. I used a single switch to keep it readable - but some advice on how to have a both compact code and not reassign variables that stay constant would be very welcome (I'm not very happy with it atm).

def merge_rows!(board, move) 
    siz = board.size
    (siz-1).times do |i|
        (siz).times do |j|
            #puts "#{i} #{j}"
            case move 
                when "up"
                    a=1; b=0; x=i; y=j;
                when "down"
                    a=-1; b=0; x=siz-(i+1); y=j;
                when "left"
                    a=0; b=1; x=j; y=i;
                when "right"
                    a=0; b=-1; x=j; y=siz-(i+1);
            end
            #merge tiles of equal numbers
            if board[x][y] == board[x+a][y+b]
                board[x][y] *= 2
                board[x+a][y+b] = 0 
            end
        end
    end
end

Here is the move_rows! method. A notable difference from merge_rows! is that while rows can only merge once, a row can move up to board.size-1 times.

def move_rows!(board, move)   
    #This relocates each slot by up to one row
    def _move_rows!(board, move, start)
        siz = board.size
        (siz-1-start).times do |i| 
            (siz).times do |j|
                #puts "#{i} #{j}"
                case move 
                    when "up"
                        a=1; b=0; x=i; y=j;
                    when "down"
                        a=-1; b=0; x=siz-(i+1); y=j;
                    when "left"
                        a=0; b=1; x=j; y=i;
                    when "right"
                        a=0; b=-1; x=j; y=siz-(i+1);
                end
                #move tiles into empty spaces
                if board[x][y] == 0 
                    board[x][y] = board[x+a][y+b]
                    board[x+a][y+b] = 0
                end
            end
        end
    end
    #We need to move to the first row up to siz-1 times, to the 2nd up to siz-2 times etc...
    #So we can pass a start distance to skip attempting to move rows more than necessary
    (board.size-1).times do |iter|
            _move_rows!(board, move, iter)  
    end
end

An alternative simplification for the above would be making the if statements for merge and move callable functions and passing them to a single board_row_action method.

That just leaves printing the board and parsing stdin:

#Correct problem format
def output_board(board, case_num) 
    puts "Case ##{case_num}:"
    board.each { |row| puts "#{row.join(' ')}" }
end

num_cases = gets.chomp.to_i
num_cases.times do |num|
    info = gets.chomp.split
    siz, move = info[0].to_i,  info[1]
    board = []
    siz.times do
        line = gets.chomp.split.map(&:to_i)
        board.push(line) 
    end
    board_move!(board, move) 
    output_board(board, num+1)
end

Answer 1

Style notes:

• I've said it before, but the Ruby convention is 2 spaces of indentation :)

• Also a repeat: Prefer methods like #first and #last for array access when possible. Or use array destructuring. E.g. this:

  info = gets.chomp.split
  siz, move = info[0].to_i,  info[1]
  

  can be written as:

  siz, move = gets.chomp.split
  

  though you'll have to call #to_i on siz when you need it. By the way, it'd be nicer to just call it size - there's no reason to drop a single letter.

• And prefer functional approaches, when possible. For instance, this:

  board = []
  siz.times do
      line = gets.chomp.split.map(&:to_i)
      board.push(line) 
  end
  

  becomes:

  board = siz.times.map { gets.chomp.split.map(&:to_i) }
  

Code notes:

The thing about rotating 2D arrays has been covered in the comments. That's probably the big-ticket item here, since using that will let you avoid a bunch of index arithmetic.

I'm not a fan of the nested method. It works, but it's not a terribly common construction. You could move the inner method out, or you could convert it to a proc. The latter has the benefit of closures, meaning you'd only have to pass it its start parameter - board and move are already in-scope. Such a proc would do all its work with side-effects, though.

Your move-merge-move strategy might instead be expressed as reject-merge-pad. I.e. we can reject all the zeros, and just merge what remains, then pad the result with new zeros. Given the row [0, 2, 0, 2] we can start by reducing it to [2, 2], instead of trying to maintain its size.

Finally, there's the merging itself. I played around with a bunch of things (using #each_cons with variations on map/reduce, using a Tile class to allow tiles to be passed by reference, tried some stuff with Enumerator instances...), but in the end, I went with this:

def merge(row)
  return [] if row.empty?
  head, *tail = row
  if head == tail.first
    [head * 2] + merge(tail.drop(1))
  else
    [head] + merge(tail)
  end
end

Its input is a row/column of tiles with the zeros stripped away, and from that it - with some recursion - returns the merged result, again without zeros.

Combined with the array rotation, it seems to do the trick, and it seems fast. Haven't tried timing it, though.

In all, I ended up with this. I aimed for a functional approach, always returning new arrays instead of modifying existing ones in-place.

# Monkeypatch for Array
class Array
  def spin(times = 1)
    case times % 4
    when 1, -3
      transpose.map(&:reverse)
    when 2, -2
      reverse.map(&:reverse)
    when 3, -1
      map(&:reverse).transpose
    else
      self.dup # rotate 360; no change
    end
  end
end

# Lookup table of how to rotate the board before merging
ROTATIONS = { "right" => 0, "up" => 1, "left" => 2, "down" => 3 }.freeze

def move(board, direction)
  size = board.count
  rotation = ROTATIONS[direction]
  board.spin(rotation).map do |row|              # rotate then map
    merged = merge(row.reject(&:zero?))          # merge non-zero tiles
    merged.unshift(0) while merged.count < size  # pad row back to size
    merged
  end.spin(-rotation)                            # rotate back again
end

def merge(row)
  return [] if row.empty?
  head, *tail = row
  if head == tail.first
    [head * 2] + merge(tail.drop(1))
  else
    [head] + merge(tail)
  end
end

def print_board(board)
  puts board.map { |row| row.join(" ") }.join("\n")
end

cases = gets.chomp.to_i
cases.times do |n|
  size, direction = gets.chomp.split(" ")
  board = size.to_i.times.map { gets.chomp.split.map(&:to_i) }
  result = move(board, direction)
  puts "Case #{n + 1}:"
  print_board(result)
end