Super2048 (Google apac Test Problem)

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] right
a[0][2] up
a[0][0] down
a[2][0] <- a[1][0]
a[2][1] <- a[1][1]
a[2][2] <- a[1][2]
"""
#Note that the +1 (m

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

StackExchange Code Review Q#90983, answer score: 2