# Advent of Code 2022, Day 17: Pyroclastic Flow

## Part A

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

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

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

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|

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

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

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|

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)
``````