Summary
See Part 1
Instead of doing the single tilt north, a “cycle” rolls the rocks
north-west-south-east. Run the pattern through 1000000000 cycles and then
calculate the “load” value in the north wall.
I took the easy route in Part 1, by rotating, and I don’t think this idea will
scale to a billion times. Instead, I’m going to rewrite it into states and use
more of an object oriented way of solving this problem.
This starts with making two interfaces for the two main objects in the matrix
1
2
3
4
5
6
7
8
9
10
11
|
export interface barricade {
id: number,
x: number,
y: number,
}
export interface rollable {
id: number,
x: number,
y: number,
}
|
And the general board state is going to be
1
2
3
4
5
6
7
8
9
10
|
export interface matrix_state {
size: number,
rollables: rollable[],
b_rows: barricade[][],
b_cols: barricade[][],
b_hit: {[id: number]: number},
ends_hit: number[],
}
|
I’ve decided to pre-group all the barricades by row/col, that way I don’t have
to loop through a list of all barricades every time I need check if there
is one in the way, I can fetch them by index.
b_hit will store barricades, by id, and the amount of rollable rocks that have
hit it during a tilt. ends_hit is the same thought, stores the amount of
rollable rocks that have hit the edge, by index, in the current tilt.
Importing
To make my life easier I wrote a helper function to first initialize the
barricade rows / cols.
1
2
3
4
5
6
7
|
function init_barricade_static_array(size: number): barricade[][]{
let tmp: barricade[][] = [];
for (let i = 0; i < size; i++){
tmp.push([]);
};
return tmp;
}
|
Initializing the data is as easy as looping through the data and pushing the
objects into the correct array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
function load_matrix_state(data: string[]): matrix_state{
const size = data.length;
let b_count: number = 0; // for IDs
let b_rows: barricade[][] = init_barricade_static_array(size);
let b_cols: barricade[][] = init_barricade_static_array(size);
let b_hit: {[id: number]: number} = {};
let ends_hit: number[] = [];
let r_count: number = 0; // for IDs
let rollables: rollable[] = [];
for (let y = 0; y < size; y++){
for (let x = 0; x < size; x++){
if (data[y][x] == '#'){
const b: barricade = {
id: b_count,
x: x,
y: y,
};
b_hit[b_count] = 0;
b_rows[y].push(b);
b_cols[x].push(b);
b_count++;
}else if (data[y][x] == 'O'){
rollables.push({
id: r_count,
y: y,
x: x,
});
r_count++;
}
};
// init the ends_hit array
ends_hit.push(0);
};
return {
'size': size,
'rollables': rollables,
'b_rows': b_rows,
'b_cols': b_cols,
'b_hit': b_hit,
'ends_hit': ends_hit,
};
}
|
Tilting
With everything nicely packaged into a matrix_state, I look at tilting; North is
first. Because rollable rocks are now detached from the matrix itself, I can
loop that list directly and I change their y location in relation to the
barricades
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
function tilt_north(data: matrix_state): matrix_state{
data.rollables.forEach((ele) => {
let barricades: barricade[] = data.b_cols[ele.x]
.filter((i) => i.y < ele.y)
.reverse(); // largest first
if (barricades.length){
// item will hit a barricade
ele.y = barricades[0].y + 1 + data.b_hit[barricades[0].id];
data.b_hit[barricades[0].id]++;
}else{
// no barricades in the way
ele.y = data.ends_hit[ele.x];
data.ends_hit[ele.x] += 1;
};
});
data = clear_hits(data);
return data;
}
|
We fetch the barricades in the col we need and then filter out any that are
south of our current rollable. I reversed this filtered list, so index 0 will
always be the barricade hit. A simple barricade-hit-y + 1 gets the new y
position for the rollable. I take note that a rollable hit this barricade so
that if another one does there won’t be two on top of each other.
at the end I clear all the hit data, barricade and edges using this helper
function:
1
2
3
4
5
6
7
8
9
|
function clear_hits(data: matrix_state){
for (let i = 0; i < data.size; i++){
data.ends_hit[i] = 0;
};
Object.keys(data.b_hit).forEach((key) => {
data.b_hit[key] = 0;
});
return data;
}
|
My thought process that it would be a lot easier to pre-initialize the hit
variables and clear them every time, instead of creating them for each tilt.
Though, it might be better to initialize them for each tilt.
Tilting south is a copy of north, but it doesn’t reverse the barricade list and
instead of adding to y positions when an barricade is hit it subtracts.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
function tilt_south(data: matrix_state): matrix_state{
data.rollables.forEach((ele) => {
let barricades: barricade[] = data.b_cols[ele.x]
.filter((i) => i.y > ele.y);
if (barricades.length){
// item will hit a barricade
ele.y = barricades[0].y - (1 + data.b_hit[barricades[0].id]);
data.b_hit[barricades[0].id]++;
}else{
// no barricades in the way
ele.y = data.size - 1 - data.ends_hit[ele.x];
data.ends_hit[ele.x] += 1;
};
});
data = clear_hits(data);
return data;
}
|
Tilting west and east are basically copies of north and south, but change the x
position and grabs barricades by rows instead of columns.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
function tilt_west(data: matrix_state): matrix_state{
data.rollables.forEach((ele) => {
let barricades: barricade[] = data.b_rows[ele.y]
.filter((i) => i.x < ele.x)
.reverse(); // largest first
if (barricades.length){
// item will hit a barricade
ele.x = barricades[0].x + 1 + data.b_hit[barricades[0].id];
data.b_hit[barricades[0].id]++;
}else{
// no barricades in the way
ele.x = data.ends_hit[ele.y];
data.ends_hit[ele.y] += 1;
};
});
data = clear_hits(data);
return data;
}
function tilt_east(data: matrix_state): matrix_state{
data.rollables.forEach((ele) => {
let barricades: barricade[] = data.b_rows[ele.y]
.filter((i) => i.x > ele.x);
if (barricades.length){
// item will hit a barricade
ele.x = barricades[0].x - (1 + data.b_hit[barricades[0].id]);
data.b_hit[barricades[0].id]++;
}else{
// no barricades in the way
ele.x = data.size - 1 - data.ends_hit[ele.y];
data.ends_hit[ele.y] += 1;
};
});
data = clear_hits(data);
return data;
}
|
To combine this into a single function call, I wrote this:
1
2
3
4
5
6
7
|
function tilt_cycle(data: matrix_state): matrix_state{
const funcs: Function[] = [tilt_north, tilt_west, tilt_south, tilt_east];
funcs.forEach((call, index) => {
data = call(data);
});
return data;
}
|
Calculating Sum
Now that the data is in a different format I needed to rewrite how to calculate
the load on the north wall from rollable objects. I though subtracting the
matrix size and the rollable’s y position was the way to go
1
2
3
4
5
6
7
|
function get_sum(data: matrix_state): number{
let sum: number = 0;
data.rollables.forEach((ele) => {
sum += data.size - ele.y;
});
return sum;
}
|
Visualizing
To validate that my function above work as expected I wrote a function to revert
barricade and rollable items back into their matrix format.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
function visualize_data(data: matrix_state): string[][]{
let board: string[][] = [];
for (let y = 0; y < data.size; y++){
let row: string[] = [];
for (let x = 0; x < data.size; x++){
if (
data.b_rows[y].filter((ele) => ele.x == x).length
){
row.push('#');
}else if (
data.rollables.filter((ele) => ele.x === x && ele.y === y).length
){
row.push('O');
}else{
row.push('.');
}
};
board.push(row);
};
return board;
}
function output_visualize_data(data: matrix_state): void{
visualize_data(data).forEach((row) => {
console.log(row.join(''));
});
}
|
Pattern Matching
After validating I start to run the literal billion cycles. I quickly learned
that what I had wasn’t going to cut it.
My first attempt to pattern match was using a dictionary
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
interface saved_state {
string: string,
// before: after,
}
let saved_states: saved_state[] = {};
for (let i = 0; i < a_literal_billion; i++){
before = JSON.stringify(data.rollables);
if (saved_states.indexOf(before) != -1){
data.rollables = JSON.parse(saved_states[before]);
}else{
data = tilt_cycle(data);
saved_states[before] = JSON.stringify(data.rollables);
}
}
|
This did not work. Patterns were never found in the main input, yet they
were found in the example input.
My solution was to revert the matrix state back into the text format, and
this is the point where I think doing an object oriented idea was the wrong way
to go.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
function visualize_data(data: matrix_state): string[][]{
let board: string[][] = [];
for (let y = 0; y < data.size; y++){
let row: string[] = [];
for (let x = 0; x < data.size; x++){
if (
data.b_rows[y].filter((ele) => ele.x == x).length
){
row.push('#');
}else if (
data.rollables.filter((ele) => ele.x === x && ele.y === y).length
){
row.push('O');
}else{
row.push('.');
}
};
board.push(row)
};
return board
}
function compile_data(data: matrix_state): string{
let tmp: string = '';
visualize_data(data).forEach((row) => {
tmp += row.join('') + '\n';
})
return tmp;
}
|
While this is finding matches, it still wasn’t enough to do the billion
calculations in a reasonable time.
The Trick
Instead of storing patterns and “skipping” those during a traditionally loop,
the trick is to find where & how long the first cycle is and “jump” as close to
the end as possible.
To illustrate this:
const length_to_loop: number = 1000;
const cycle_length: number = 23;
const loops_actually_required: number = 1000 % 23;
console.log(loops_required); // 11
Knowing the end state of the cycle and the length of the cycle we can essentially
“jump” to 989 and loop the 11 required to find the answer.
Implementing
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
function load_rollables(compiled_data: string){
const tmp_data: matrix_state = load_matrix_state(compiled_data.split('\n'));
return tmp_data.rollables;
}
const cycles_to_run: number = 1000000000;
// to hold patterns
let cache = new Map();
let loop_count: number = 0;
let cycle_size: number = 0;
let cycle_start: string;
// find the cycle
for (let i = 0; i < cycles_to_run; i++){
const start: string = compile_data(data);
const result = cache.get(start);
if (result){
// found in cache
if (start == cycle_start){
// 1 full loop, take note of ending and exit
loop_count = i;
break;
}
if (cycle_size === 0){
// init the start
cycle_start = start;
}
// load data
data.rollables = load_rollables(result);
cycle_size++;
}else{
// tilt data
data = tilt_cycle(data);
if (cycle_size === 0){
// cache results
cache.set(start, compile_data(data));
}
}
}
// loop the rest of the required amount
for (let i = 0; i < (cycles_to_run - loop_count) % cycle_size ; i++){
data = tilt_cycle(data);
};
console.log(`Sum => ${get_sum(data)}`);
|
Conclusion
This was tough! I got stuck on the pattern matching so a long time, I’m
still not 100% sure why the JSON.stringify wasn’t working. Hopefully day 15 is
a little more relaxed!