# Super2048 (Google apac Test Problem)

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

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

merge->right
a <- a
a <- a
a <- a

merge-> up
a <- a
a <- a
a <- a

merge-> down
a <- a
a <- a
a <- a
"""
#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.to_i,  info
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

• Ruby has Array#transpose method, that with .map(&:reverse) is enough for any rotation. gist.github.com/Nakilon/10571155 May 17, 2015 at 15:55
• @Nakilon :( someone should have told me earlier. May 17, 2015 at 16:54
• @user3467349 Here's a more readable implementation - actually two different implementations - of matrix rotation that monkeypatches Array. May 17, 2015 at 18:01
• @Flambino Yes I didn't know there was a built in transpose =/ May 17, 2015 at 18:17

### 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.to_i,  info


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

• Reject, unshift is a very nice touch. I'm not sure I agree with though you'll have to call #to_i on siz afterward. imho you should format your input correctly in one place. I guess siz, move = gets.chomp.split; siz = siz.to_i would wok. May 18, 2015 at 23:05
• @user3467349 True it depends on the context. In my code, I only used the size input value in one place, so I read it as a string, but called size.to_i.times... to use it. I didn't alter the size variable itself after reading it: It remained a string. My 2nd choice would be your original code just using #first and #last rather than  and . But I'd avoid doing something like size = <some string>; size = size.to_i. I generally don't like altering a variable's type after the fact (unless it's something like x ||= <default value>) May 18, 2015 at 23:25
• Also I know you aren't a big fan of indexing directly but why not something like: def merge!(row) (row.size-1).times do |i| if row[i] == row[i+1] row[i] *=2; row[i+1] = 0; end end row.reject(&:zero?) end for the merge method, a recursive call seems kind of unnecessary there. And in this case the indexing is easier to read I think. May 18, 2015 at 23:35
• @user3467349 That'd certainly work, and since it's a neat solution, I'd be fine with it (though I'd still try to come up with an alternative, just because). I thought something along the same lines, but was (too) fixated on trying to avoid using raw indices. Which, I admit, is probably a bit too zealous of me. But most often I've found code to be more elegant when not playing around with indices, so I try to look for such solutions. But, but, sometimes it's just more straightforward to get off the high horse :) May 18, 2015 at 23:41