On Day 17 we need to write Tetris simulator. It is pretty cool task. It took me back to my highschool years when I wanted to be a game developer and Tetris was the first game I wrote as practice.
The one in the puzzle is a bit different. We have 5 different blocks:
####
.#.
###
.#.
..#
..#
###
#
#
#
#
##
##
And we also have the input file that looks like this:
>>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>
Those are the moves that will be applied to falling blocks in each cycle. So in each cycle current block is moving left or right one unit (if it can) and then one unit down (again if it can). We start from the first block on the list and when it settles down on the bottom we move to the next. If we ran out of blocks the list starts from the beginning. The same goes for left/right movements. When we ran out of moves we start from the beginning.
Now the actual task is to simulate 2022 blocks dropping and then output the height of tower of blocks.
I just implemented the actual Tetris simulator. Here is my code:
data = File.read("17.txt", chomp: true).split("")
ROCKS = [
[
[true, true, true, true]
],
[
[false, true, false],
[true, true, true],
[false, true, false]
],
[
[true, true, true],
[false, false, true],
[false, false, true]
],
[
[true],
[true],
[true],
[true]
],
[
[true, true],
[true, true]
]
]
class Rock
def initialize(index, x, y)
@index = index
@x = x
@y = y
rock = ROCKS[index]
points = []
rock.each_with_index do |row, y|
row.each_with_index do |elem, x|
if elem
points.push([x, y])
end
end
end
@points = points
end
def height
ROCKS[@index].size
end
def width
ROCKS[@index][0].size
end
def points
@points.map do |point|
[@x + point[0], @y + point[1]]
end
end
def push_left
@x -= 1
end
def push_right
@x += 1
end
def push_down
@y -= 1
end
def offseted_points(offset_x, offset_y)
@points.map do |point|
[@x + point[0] + offset_x, @y + point[1] + offset_y]
end
end
end
class Map
def initialize
@width = 7
@height = 0
@map = []
@height.times do |y|
@width.times do |x|
@map[y] = Array.new(@width, ".")
end
end
end
def height
@height
end
def set(x, y, value)
@map[y][x] = value
end
def extend_height(rows)
rows.times do
@map.push(Array.new(@width, "."))
@height += 1
end
end
def render
if @current_rock
@current_rock.points.each do |(x, y)|
set(x, y, "@")
end
end
@height.times do |y|
row = "#{(@height - y - 1).to_s.rjust(4)} |"
@width.times do |x|
row += @map[@height - y - 1][x]
end
row += "|"
puts row
end
row = " +"
(@width).times do
row += "-"
end
row += "+"
puts row
if @current_rock
@current_rock.points.each do |(x, y)|
set(x, y, ".")
end
end
end
def top_full_row
(@height - 5).downto(0) do |y|
row = Array.new(@width, false)
@map[y].each_with_index { |elem, x| row[x] = true if elem == "#" }
@map[y + 1].each_with_index { |elem, x| row[x] = true if elem == "#" }
@map[y + 2].each_with_index { |elem, x| row[x] = true if elem == "#" }
@map[y + 3].each_with_index { |elem, x| row[x] = true if elem == "#" }
if row.all? { |elem| elem }
return y + 1
end
end
return nil
end
def collide?(points)
points.any? do |(x, y)|
x < 0 || x > (@width - 1) || y < 0 || y > (@height - 1) || @map[y][x] == "#"
end
end
def add_rock(index)
rock_height = ROCKS[index].size
required_height = top_rock + 3 + rock_height
if required_height > @height
extend_height(required_height - @height)
end
@current_rock = Rock.new(index, 2, top_rock + 3)
end
def push_left
return unless @current_rock
offseted_points = @current_rock.offseted_points(-1, 0)
if !collide?(offseted_points)
@current_rock.push_left
end
end
def push_right
return unless @current_rock
offseted_points = @current_rock.offseted_points(1, 0)
if !collide?(offseted_points)
@current_rock.push_right
end
end
def push_down
return unless @current_rock
offseted_points = @current_rock.offseted_points(0, -1)
if collide?(offseted_points)
@current_rock.points.each do |(x, y)|
set(x, y, "#")
end
@current_rock = nil
return false
else
@current_rock.push_down
return true
end
end
def top_rock
(@height - 1).downto(0) do |y|
if @map[y].any? { |elem| elem == "#" }
return y + 1
end
end
return 0
end
def result
top_rock
end
end
rock_index = 0
move_index = 0
x = 2
y = 1
rocks = x * 20 + y * 15
map = Map.new
2022.times do
map.add_rock(rock_index)
while true
if data[move_index] == "<"
map.push_left
elsif data[move_index] == ">"
map.push_right
end
move_index = (move_index + 1) % data.size
break unless map.push_down
end
rock_index = (rock_index + 1) % ROCKS.size
end
puts map.result
And here is how the bottom of my tower looks like for test input:
100 |....##.|
99 |....##.|
98 |....#..|
97 |..#.#..|
96 |..#.#..|
95 |#####..|
94 |..###..|
93 |...#...|
92 |..####.|
91 |..###..|
90 |..###..|
89 |..####.|
88 |....###|
87 |.#...#.|
86 |.#####.|
85 |.#..#..|
84 |.#..#..|
83 |.##.##.|
82 |.##.##.|
81 |..####.|
80 |.###...|
79 |..#....|
78 |.####..|
77 |....##.|
76 |....##.|
75 |....#..|
74 |..#.#..|
73 |..#.#..|
72 |#####..|
71 |..###..|
70 |...#...|
69 |..####.|
68 |..###..|
67 |..###..|
66 |..####.|
65 |....###|
64 |.#...#.|
63 |.#####.|
62 |.#..#..|
61 |.#..#..|
60 |.##.##.|
59 |.##.##.|
58 |..####.|
57 |.###...|
56 |..#....|
55 |.####..|
54 |....##.|
53 |....##.|
52 |....#..|
51 |..#.#..|
50 |..#.#..|
49 |#####..|
48 |..###..|
47 |...#...|
46 |..####.|
45 |..###..|
44 |..###..|
43 |..####.|
42 |....###|
41 |.#...#.|
40 |.#####.|
39 |.#..#..|
38 |.#..#..|
37 |.##.##.|
36 |.##.##.|
35 |..####.|
34 |.###...|
33 |..#....|
32 |.####..|
31 |....##.|
30 |....##.|
29 |....#..|
28 |..#.#..|
27 |..#.#..|
26 |#####..|
25 |..###..|
24 |...#...|
23 |..####.|
22 |..###..|
21 |..###..|
20 |..####.|
19 |....###|
18 |.#...#.|
17 |.#####.|
16 |.#..#..|
15 |.#..#..|
14 |.##.##.|
13 |.##.##.|
12 |..####.|
11 |.###...|
10 |..#....|
9 |.####..|
8 |....##.|
7 |....##.|
6 |....#..|
5 |..#.#..|
4 |..#.#..|
3 |#####..|
2 |..###..|
1 |...#...|
0 |..####.|
+-------+
Part B raises difficulty significantly. We need to output the height of the tower after dropping 1000000000000 blocks!
Simulating this will take a lot of time, so we need to find another way. If you look at the actual at the game board I pasted above you can see that certain configurations at certain intervals. You can see the same blocks at height 31, 54, 77 and 100. The different is the same and it is 23 blocks.
So it must be the same for the actual input. We need to implement some code to detect this pattern. We can start with some additional method for our map:
def top16
numbers = []
(top_rock - 1).downto([top_rock - 16, 0].max) do |y|
number = []
@width.times do |x|
number.push(@map[y][x] == "." ? 0 : 1)
end
number = number.join
numbers.push(number.to_i(2))
end
numbers
end
This method will return top 16 lines and convert it to numbers. Empty space is considered as 0 and block is considered as 1. We can then convert it to decimal number. So in the end we will have an array of 16 integers.
Then we can change our simulator to look for patterns:
def tetris(blocks)
rock_index = 0
move_index = 0
x = 2
y = 1
rocks = x * 20 + y * 15
map = Map.new
cache = {}
heights = {}
blocks.times do |i|
map.add_rock(rock_index)
current_top_rock = map.top_rock
while true
if @data[move_index] == "<"
map.push_left
elsif @data[move_index] == ">"
map.push_right
end
move_index = (move_index + 1) % @data.size
break unless map.push_down
end
cache[map.top16] ||= []
cache[map.top16].push([i + 1, map.top_rock])
rock_index = (rock_index + 1) % ROCKS.size
end
indexes = cache[cache.keys.last]
diff = indexes[1][0] - indexes[0][0]
multiplier = indexes[1][1] - indexes[0][1]
cache.each do |top, indexes|
next if indexes.size == 1
heights[indexes[0][0]] = indexes[0][1]
end
[map.result, diff, multiplier, heights]
end
So now after each block drops we are adding the block number and current height to our cache. Key to our cache is this array of top 16 blocks converted to integers. So each key of our cache should tell us after which block we got the same configuration and what was it’s height.
This top 16 block can look like this [30, 52, 52, 60, 40, 60, 40, 120, 19, 19, 18, 18, 30, 56, 16, 30] and example cached values like this [[1996, 3044], [3726, 5691], [5456, 8338], [7186, 10985], [8916, 13632]]. First number is block number and second one is the height. If we subtract the same values from adjacent indexes we will get this [[1730, 2647], [1730, 2647], [1730, 2647], [1730, 2647]]. This means that after we see all possible combinations they start to repeat every 1730 blocks. And the height increases by 2647 blocks.
The below part of code is also caching the heights of the first appearances of certain patterns.
cache.each do |top, indexes|
next if indexes.size == 1
heights[indexes[0][0]] = indexes[0][1]
end
Now having all those above information we can figure out what will be the height after one billion blocks:
def predict_height(blocks, diff, multiplier, heights)
modulo = blocks % diff
modulo += diff unless heights[modulo]
base = heights[modulo]
base + ((blocks - modulo) / diff) * multiplier
end
height, diff, multiplier, heights = tetris(10_000)
puts predict_height(1_000_000_000_000, diff, multiplier, heights)
Here is the full code:
@data = File.read("17.txt").strip.split("")
ROCKS = [
[
[true, true, true, true]
],
[
[false, true, false],
[true, true, true],
[false, true, false]
],
[
[true, true, true],
[false, false, true],
[false, false, true]
],
[
[true],
[true],
[true],
[true]
],
[
[true, true],
[true, true]
]
]
MAX = 100
class Rock
attr_reader :index
def initialize(index, x, y)
@index = index
@x = x
@y = y
rock = ROCKS[index]
points = []
rock.each_with_index do |row, y|
row.each_with_index do |elem, x|
if elem
points.push([x, y])
end
end
end
@points = points
end
def height
ROCKS[@index].size
end
def width
ROCKS[@index][0].size
end
def points
@points.map do |point|
[@x + point[0], @y + point[1]]
end
end
def push_left
@x -= 1
end
def push_right
@x += 1
end
def push_down
@y -= 1
end
def offseted_points(offset_x, offset_y)
@points.map do |point|
[@x + point[0] + offset_x, @y + point[1] + offset_y]
end
end
end
class Map
def initialize
@width = 7
@height = 0
@shrinked = 0
@map = []
@height.times do |y|
@width.times do |x|
@map[y] = Array.new(@width, ".")
end
end
end
def height
@height
end
def set(x, y, value)
@map[y][x] = value
end
def extend_height(rows)
rows.times do
@map.push(Array.new(@width, "."))
@height += 1
end
end
def render
if @current_rock
@current_rock.points.each do |(x, y)|
set(x, y, "@")
end
end
@height.times do |y|
row = "#{(@height - y - 1).to_s.rjust(4)} |"
@width.times do |x|
row += @map[@height - y - 1][x]
end
row += "|"
puts row
end
row = " +"
(@width).times do
row += "-"
end
row += "+"
puts row
if @current_rock
@current_rock.points.each do |(x, y)|
set(x, y, ".")
end
end
end
def top16
numbers = []
(top_rock - 1).downto([top_rock - 16, 0].max) do |y|
number = []
@width.times do |x|
number.push(@map[y][x] == "." ? 0 : 1)
end
number = number.join
numbers.push(number.to_i(2))
end
numbers
end
def collide?(points)
points.any? do |(x, y)|
x < 0 || x > (@width - 1) || y < 0 || y > (@height - 1) || @map[y][x] == "#"
end
end
def add_rock(index)
rock_height = ROCKS[index].size
required_height = top_rock + 3 + rock_height
if required_height > @height
extend_height(required_height - @height)
end
@current_rock = Rock.new(index, 2, top_rock + 3)
end
def push_left
return unless @current_rock
offseted_points = @current_rock.offseted_points(-1, 0)
if !collide?(offseted_points)
@current_rock.push_left
end
end
def push_right
return unless @current_rock
offseted_points = @current_rock.offseted_points(1, 0)
if !collide?(offseted_points)
@current_rock.push_right
end
end
def push_down
return unless @current_rock
offseted_points = @current_rock.offseted_points(0, -1)
if collide?(offseted_points)
@current_rock.points.each do |(x, y)|
set(x, y, "#")
end
@current_rock = nil
return false
else
@current_rock.push_down
return true
end
end
def top_rock
(@height - 1).downto(0) do |y|
if @map[y].any? { |elem| elem == "#" }
return y + 1
end
end
return 0
end
def result
top_rock
end
end
def tetris(blocks)
rock_index = 0
move_index = 0
x = 2
y = 1
rocks = x * 20 + y * 15
map = Map.new
cache = {}
heights = {}
blocks.times do |i|
map.add_rock(rock_index)
current_top_rock = map.top_rock
while true
if @data[move_index] == "<"
map.push_left
elsif @data[move_index] == ">"
map.push_right
end
move_index = (move_index + 1) % @data.size
break unless map.push_down
end
cache[map.top16] ||= []
cache[map.top16].push([i + 1, map.top_rock])
rock_index = (rock_index + 1) % ROCKS.size
end
indexes = cache[cache.keys.last]
diff = indexes[1][0] - indexes[0][0]
multiplier = indexes[1][1] - indexes[0][1]
cache.each do |top, indexes|
next if indexes.size == 1
heights[indexes[0][0]] = indexes[0][1]
end
[map.result, diff, multiplier, heights]
end
def predict_height(blocks, diff, multiplier, heights)
modulo = blocks % diff
modulo += diff unless heights[modulo]
base = heights[modulo]
base + ((blocks - modulo) / diff) * multiplier
end
height, diff, multiplier, heights = tetris(10_000)
puts predict_height(1_000_000_000_000, diff, multiplier, heights)