An overview of interesting thoughts and observations during my completion of the 2022 Advent of Code challenges.
Introduction
Advent of Code is an advent calendar of coding problems that can each be solved in under a day. I am working through these problems now and will update this article with explanations of my solutions and reflections of them, including interesting techniques used and potential improvements.
Tooling
Over the course of working on these challenges, I developed a few quality of life enhancements to help myself be more productive. These include a challenge runner that allows you to run the code for any challenge using a single command, a library of helper functions that help with more easily reading in the challenge input data, and a TypeScript build system.
Challenge Runner
The challenge runner gives you a list of days to choose from, and runs the code for that days challenge upon selection. Simply run the following npm script:
1
npm run aoc
It automatically checks for sub-folders in the source directory, and uses dynamic imports to import the module for that day and run it. Each days module simply has to export a run function that the runner can call. It uses the inquirer package to provide a prompt for which day to run.
Challenge Runner Code:
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
import { readdirSync } from 'fs';
import inquirer from 'inquirer';
import path from 'path';
const challenges = readdirSync(path.resolve('./src'), { withFileTypes: true })
.filter((dirent) => dirent.isDirectory())
.map((dirent) => dirent.name);
const questions = [
{
type: 'list',
name: 'day',
message: 'Choose a challenge day to run',
choices: challenges,
filter(val) {
return val;
},
},
];
inquirer.prompt(questions).then(({ day }) => {
import(`./${day}/index.js`).then((module) => {
module.run();
});
});
export {};
Helper Functions
The src/helpers.js file contains a couple helper functions that help to read the challenge input data easier.
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
import { readFileSync } from 'fs';
import { EOL } from 'os';
import path from 'path';
/**
* Read entire file contents as string
* @param {string} path
* @returns {string} file contents
*/
function readFileAsString(path) {
return readFileSync(path).toString();
}
/**
* Read file contents as an array of strings,
* each containing a single line
* @param {string} path
* @returns {string[]} file contents
*/
function readFileAsLines(path) {
return readFileAsString(path).split(EOL);
}
function readInputForChallenge(challenge) {
return readFileAsLines(path.resolve(`src/${challenge}/input.txt`));
}
function deepCopy(array) {
return array.map((val) => {
if (Array.isArray(val)) {
return deepCopy(val);
}
return val;
});
}
export { readFileAsLines, readFileAsString, readInputForChallenge, deepCopy };
TypeScript Build System
I wanted to add TypeScript support to this project, so before starting on Day 5, I added a build system that would support TypeScript or vanilla javascript. Here’s how I installed and configured that.
Installation
Install TypeScript:
1
npm i -D typescript
This installs typescript as a dev dependency for the project. I also installed typescript globally to allow me to use the tsc command from anywhere, using npm i -g typescript
Install types for nodejs:
1
npm i -D @types/node
Install default tsconfig for Node 20:
1
npm i -D @tsconfig/node20
Install copyfiles and rimraf packages (used in build process):
1
npm i -D copyfiles rimraf
Configuration
Generate default tsconfig:
tsc --init
There are a few things that need added to the default tsconfig file:
"allowJs": trueNeeded in order to support the previous challenges that are all written in javascript, this makes the compiler copy all javascript files to the build directory."sourceMap": trueThis option is needed to enable realtime debugging of typescript files in VSCode - see TypeScript debugging with Visual Studio Code"outDir": "./build"change output directory tobuild
For everything else, the defaults from @tsconfig/node20 are sufficient:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
{
"$schema": "https://json.schemastore.org/tsconfig",
"display": "Node 20",
"_version": "20.1.0",
"compilerOptions": {
"lib": ["es2023"],
"module": "node16",
"target": "es2022",
"strict": true,
"esModuleInterop": true,
"skipLibCheck": true,
"forceConsistentCasingInFileNames": true,
"moduleResolution": "node16"
}
}
Build Process
I then had to update my project npm scripts to include the typescript build process:
package.json
1
2
3
4
5
6
7
8
9
...
"scripts": {
"aoc": "npm run build && node build/index.js",
"copyInput": "copyfiles -u 1 src/**/input.txt build",
"debug": "npm run build && node --inspect build/index.js",
"build": "rimraf ./build && tsc && npm run copyInput",
"test": "echo \"Error: no test specified\" && exit 1"
},
...
I added the npm run build step before the node execution in the aoc and debug scripts. Then for the build script, I run rimraf ./build to delete the existing build directory, tsc to run the typescript compiler, and npm run copyInput to copy the input files from src to build
Day 1
Day 1 asks us to calculate information about the calorie count of food items carried by a number of elves. Each elf is carrying some number of items, each with a different calorie count. The data is provided as a list of calorie counts, with blank lines indicating that the next set of numbers are for a new elf:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
This list represents the Calories of the food carried by five Elves:
- The first Elf is carrying food with 1000, 2000, and 3000 Calories, a total of 6000 Calories.
- The second Elf is carrying one food item with 4000 Calories.
- The third Elf is carrying food with 5000 and 6000 Calories, a total of 11000 Calories.
- The fourth Elf is carrying food with 7000, 8000, and 9000 Calories, a total of 24000 Calories.
- The fifth Elf is carrying one food item with 10000 Calories.
</br/> In case the Elves get hungry and need extra snacks, they need to know which Elf to ask: they'd like to know how many Calories are being carried by the Elf carrying the most Calories. In the example above, this is 24000 (carried by the fourth Elf).
Part 1
Part 1 asks us to find the elf with the most calories, and find the total number of calories carried by that elf.
Part 2
Part 2 asks us to find the top three elves carrying the most calories, and to provide the total calorie count of these three elves combined.
Solution
The first step is to read in the data, and loop through each line, adding up the calorie counts along the way. I use an array called elfCalorieCounts to store the calorie count for each elf, and currentElfIndex to track which elf we are on. If a line is blank, we increment the currentElfIndex. If the line contains a number, we parse it to an integer, and add it to the value of elfCalorieCounts[currentElfIndex]
To get the answer for part one, I use Math.max(...elfCalorieCounts);. This uses the Array spread operator to pass each value in the elfCalorieCounts array as an individual argument. This gives us the answer to the first question.
To get the answer for part 2, I sort the elfCalorieCounts array in descending order using using Array.sort. Then I use the Array.slice method to get just the first three values from the sorted array. Then finally, I use the Array.reduce method to sum these three values.
Code for Day 1:
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
/**
* https://adventofcode.com/2022/day/1/answer
*/
import { readInputForChallenge } from '../helpers.js';
function run() {
// read data
const lines = readInputForChallenge('01');
let elfCalorieCounts = [0];
let currentElfIndex = 0;
for (const line of lines) {
if (line === '') {
currentElfIndex++;
elfCalorieCounts[currentElfIndex] = 0;
} else {
elfCalorieCounts[currentElfIndex] += parseInt(line);
}
}
// part one
const maxElfCalorieCount = Math.max(...elfCalorieCounts);
const elfWithMaxCalories = elfCalorieCounts.indexOf(maxElfCalorieCount);
console.log(
`Elf number ${elfWithMaxCalories} has the most calories, with ${maxElfCalorieCount}`
);
// part two
elfCalorieCounts.sort((a, b) => b - a);
const topThreeElfCalorieCounts = elfCalorieCounts.slice(0, 3);
const topThreeElfTotalCalories = topThreeElfCalorieCounts.reduce(
(prev, curr) => prev + curr
);
console.log(topThreeElfCalorieCounts);
console.log(topThreeElfTotalCalories);
}
export { run };
Reflection
There are a few interesting techniques used in this solution:
- Spread operator - used to expand the array into it’s component elements, since Math.max only accepts one or more numerical arguments, not an array.
- Math.max - Used to determine the max value in a list of numbers.
- Array.sort - Used to sort the array in descending order
- Array.slice - Used to extract the first three values from the sorted array
- Array.reduce - Used to add up the individual values and return a single number
Day 2
Day 2 is about a rock paper scissors strategy guide. We are given input containing pairs of letters, one letter corresponding to the opponents move, and one letter corresponding to our move. The input looks like this:
1
2
3
A Y
B X
C Z
Appreciative of your help yesterday, one Elf gives you an encrypted strategy guide (your puzzle input) that they say will be sure to help you win. "The first column is what your opponent is going to play: A for Rock, B for Paper, and C for Scissors. The second column--" Suddenly, the Elf is called away to help with someone's tent.
The second column, you reason, must be what you should play in response: X for Rock, Y for Paper, and Z for Scissors. Winning every time would be suspicious, so the responses must have been carefully chosen.
Each round is assigned a score, based on your choice and the outcome of the round:
The score for a single round is the score for the shape you selected (1 for Rock, 2 for Paper, and 3 for Scissors) plus the score for the outcome of the round (0 if you lost, 3 if the round was a draw, and 6 if you won).
Part 1
Part one asks us to treat the second column as an indication of what to play, determine what the outcome would be, and calculate the total score after all round have been played using the scoring guide above.
Part 2
Part two asks us to treat the second column as an indication of the desired result of the match, and to determine the final score after all rounds using this new strategy.
X means you need to lose, Y means you need to end the round in a draw, and Z means you need to win.
Solution
For this puzzle, I took a more object oriented approach, creating a class Choice that represents one of the three possible choices (rock, paper, scissors), and has a method called result that takes a Choice parameter and will return the results of a match played with that choice (win, lose, draw). I used a few enum-like objects to help calculate the point values.
For part two, I added a function getNeededChoiceForDesiredResult that takes in the opponents Choice and the desired result, and then returns the Choice object that I should choose to get the desired outcome. I then use this choice to determine the outcome of the match and calculate the results the same way as part one. This function is pretty cleverly written in my opinion. It creates an array of each possible choice, and then uses the Array.filter method to filter out the choices that would result in the incorrect result.
Code for Day 2
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
import { readInputForChallenge } from '../helpers.js';
class Choice {
/**
* Create a new `Choice` object from a string
* @param {'A' | 'B' | 'C' | 'X' | 'Y' | 'Z'} s choice string
*/
constructor(s) {
if (s === 'A' || s === 'X') {
this.choice = 'rock';
} else if (s === 'B' || s === 'Y') {
this.choice = 'paper';
} else if (s === 'C' || s === 'Z') {
this.choice = 'scissors';
} else {
throw new Error('invalid choice string: ' + s);
}
}
/**
* Returns a string that tells the result of a match against the `other` choice
* @param {Choice} other The other Choice to determine the result against
* @returns {'win'|'lose'|'draw'}
*/
result = function (other) {
if (this.choice === other.choice) {
return 'draw';
} else {
switch (this.choice) {
case 'rock':
if (other.choice === 'scissors') {
return 'win';
} else {
return 'lose';
}
case 'paper':
if (other.choice === 'rock') {
return 'win';
} else {
return 'lose';
}
case 'scissors':
if (other.choice === 'paper') {
return 'win';
} else {
return 'lose';
}
default:
// should never happen unless self.choice is modified from outside this object
throw new Error('self.choice is invalid: ' + self.choice);
}
}
};
}
/**
* Determine what choice you should make to have the desired outcome
* against a given choice
* @param {Choice} other The opponents choice
* @param {'win'|'lose'|'draw'} desiredResult The desired result
* @returns {Choice} the choice you should play to get desired result against `other`
*/
function getNeededChoiceForDesiredResult(other, desiredResult) {
const possibleChoices = [new Choice('A'), new Choice('B'), new Choice('C')];
const neededChoice = possibleChoices.filter((possibleChoice) => {
return possibleChoice.result(other) === desiredResult;
})[0];
return neededChoice;
}
const RESULT_VALUE = {
win: 6,
draw: 3,
lose: 0,
};
const CHOICE_VALUE = {
rock: 1,
paper: 2,
scissors: 3,
};
const DESIRED_RESULTS = {
X: 'lose',
Y: 'draw',
Z: 'win',
};
function run() {
const lines = readInputForChallenge('02');
let roundCount = 0;
let idealScore = 0;
let actualScore = 0;
for (let line of lines) {
roundCount++;
let roundScore = 0;
// create choice objects
const choiceStrings = line.split(' ');
const opponentsChoice = new Choice(choiceStrings[0]);
const myChoice = new Choice(choiceStrings[1]);
//
const desiredResult = DESIRED_RESULTS[choiceStrings[1]];
const actualChoice = getNeededChoiceForDesiredResult(
opponentsChoice,
desiredResult
);
// determine ideal results
const idealResult = myChoice.result(opponentsChoice);
idealScore += RESULT_VALUE[idealResult];
roundScore += RESULT_VALUE[idealResult];
idealScore += CHOICE_VALUE[myChoice.choice];
roundScore += CHOICE_VALUE[myChoice.choice];
// determine actual results
const actualResult = actualChoice.result(opponentsChoice);
actualScore += RESULT_VALUE[actualResult];
actualScore += CHOICE_VALUE[actualChoice.choice];
}
console.log(`Ideal score (problem 1): ${idealScore}`);
console.log(`Actual score (problem 2): ${actualScore}`);
}
export { run };
Reflection
For this solution I am pretty happy with how my code came out and some of the techniques used, but there are a few improvements I would make. I think going OOP on this challenge was a good idea and worked out well, and using the pseudo-enum types helped my code to be more readable in the end.
To make this code more robust, I would probably decouple the Choice constructor from the different choice strings (A, B, C, X, Y, Z) - it violates the single responsibility principle, since the choice object doesn’t need to know about the encoding details of the problems input. Instead I might use another function or enum to map the input strings to a single set of choice strings (rock, paper, scissors), allowing the class to be used in other contexts as well.
I would also probably modify the result function to not use a switch statement, as I think in this case it makes the code less readable, and longer than it needs to be. There might be some clever array function that could do this in many less lines, but for the use case I think just using cleaner if/else statements would be fine.
For performance improvement, I would also make the possibleChoices array in the getNeededChoiceForDesiredResult method a constant outside the method rather than creating it on every invocation, since the filter method does not modify the original array. It could be argued that this is a case of premature optimization, but I think it would qualify more as just better design overall, as it does not take away from readability or maintainability in pursuit of performance gains.
Interesting techniques:
- Array.filter
- Enums (kind of) - Though JavaScript does not have support for enums, I used normal objects in an enum-like way. In the future I might try to use the class based approach discussed on the article linked here for more robustness.
Day 3
Day 3 is all about strings, loops, and nested loops, and though it’s not required, my solution utilizes recursion as well. It asks us to examine a list of strings. Each string represents a rucksack, and is split in half into two compartments.
Sample input:
1
2
3
4
5
6
vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw
Each character of the input string represents a unique item (case-sensitive), and each item has a priority:
To help prioritize item rearrangement, every item type can be converted to a priority: - Lowercase item types a through z have priorities 1 through 26. - Uppercase item types A through Z have priorities 27 through 52.
Part 1
Part one asks us to check each rucksack for the item shared between the two compartments, calculate it’s priority, and then calculate the total priority for all such items.
Part 2
Part two asks us to look at all the rucksacks in groups of three, find the item shared among all three rucksacks (known as the badge), and compute the total priority for all of the badge items.
Solution
This solution utilizes more of a functional style than the previous challenge. The heart of this solution is the getSharedItems function, which utilizes a recursive algorithm to find all the items (characters) shared by any given list of packs (strings). This algorithm works as follows:
- Given a list of packs, use Array.shift to get the first two packs (pack1 and pack2).
- Create an empty string sharedItems
- For each item in pack1
- For each item in pack2
- If the items match, concatenate them to sharedItems
- If they don’t, just move on
- For each item in pack2
- Using Array.unshift, add sharedItems to the start of the packs array.
- If packs only has one element left, return sharedItems
- Otherwise, call this method again with the new list of packs. This will continue until no more packs remain.
For part one, we just need to loop through each input line, split the rucksack into two evenly sized packs using the String.substring method, and get the shared items among each pack. Then we use the getPriority method to compute the items priority and add it to the total.
For part two we do the same thing, but instead we use a for loop where the update clause adds 3 to the index, and uses 3 rucksacks as input to the getSharedItems method instead of splitting one rucksack into 3 compartments
Code for Day 3
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import { readInputForChallenge } from '../helpers.js';
function getPriority(item) {
const charCode = item.charCodeAt(0);
if (charCode > 96) {
// lowercase
return charCode - 96;
} else {
// uppercase
return charCode - 64 + 26;
}
}
/**
* Get a string containing all the shared characters (items) among a set of strings (packs)
* @param {string[]} packs Return the shared items among all of the provided packs
* @returns {string} string with all the items shared in each pack. Empty string if none shared
*/
function getSharedItems(packs) {
// if only one pack provided, return it, or we will get errors when trying to compare with pack 2.
if (packs.length < 2) {
return packs[0];
}
// get first two packs from the list
let pack1 = packs.shift();
let pack2 = packs.shift();
// find shared items among these two packs
let sharedItems = '';
for (let i = 0; i < pack1.length; i++) {
for (let j = 0; j < pack2.length; j++) {
if (pack1[i] === pack2[j]) {
if (sharedItems.indexOf(pack1[i]) < 0) {
sharedItems += pack1[i];
}
}
}
}
// add shared items to beginning of the list of packs
if (packs.unshift(sharedItems) === 1) {
// if the shared list is the only pack remaining, return it.
return sharedItems;
} else {
// if there are still multiple packs remaining, recursively call this method until all packs have been searched.
return getSharedItems(packs);
}
}
function run() {
const lines = readInputForChallenge('03');
// part 1
let totalPriority = 0;
for (const line of lines) {
// split into packs
let sackSize = line.length;
let packSize = sackSize / 2;
let pack1 = line.substring(0, packSize);
let pack2 = line.substring(packSize);
// find matching item
const matchingItem = getSharedItems([pack1, pack2]);
// get value of item
totalPriority += getPriority(matchingItem);
}
console.log(totalPriority);
// part 2
let groupPriority = 0;
for (let i = 0; i < lines.length; i = i + 3) {
const groupLines = lines.slice(i, i + 3);
const sharedItem = getSharedItems(groupLines);
groupPriority += getPriority(sharedItem);
}
console.log(groupPriority);
}
export { run };
Reflection
For this solution, I designed my code with much more robustness in mind. For example, the getSharedItems method is designed with the following properties:
- Will not fail if
packsparameter only contains one item, instead it will jst return that item, as the shared characters among one string are simply the string itself. - Can handle any number of input strings, instead of just the two and three that are required for the specific problem.
- Can handle cases where there are more than one character shared among the strings, even though this problem only has cases where there is a single string.
Also, I would like to talk about the getPriority method here which utilizes the ASCII character codes to easily convert a character into it’s priority value. To do this, it uses the String.charCodeAt method to get the ascii code for the item, and then does some math on that code to convert it to the priority values provided in the problem.
Interesting techniques:
- Recursion - A technique where a method calls itself over and over until a desired result is achieved
- Array.shift and Array.unshift - The versions of Array.pop and Array.push that work on the beginning of the array rather than the end. Honestly this solution could have used either one and worked exactly the same, and maybe there are some performance benefits to using pop/push, but this is purely speculative on my part.
- String.substring - used to get part of a string by specifying a start and end index
- String.charCodeAt / ASCII codes
Day 4
Day 4 is all about numerical ranges, and in my opinion was pretty easy to solve. The input is a list of pairs of ranges, and we are asked to answer questions that compare the pairs of ranges with each other.
Sample input:
1
2
3
4
5
6
2-4,6-8
2-3,4-5
5-7,7-9
2-8,3-7
6-6,4-6
2-6,4-8
Part 1
This part asks us to determine which pairs of ranges have one range fully contained within the other.
Part 2
This part asks us to determine which paris of ranges overlap one another.
Solution
My first thought was to see if there is a Range class that provided these functions already, but the only Range class is a browser class having to do with DOM nodes. SO I created my own, calling it NumRange, since Range is already taken. The class has two methods:
contains- Determines whether this range fully contains anotheroverlaps- Determines whether this range fully or partially overlaps another.
With this class, solving both parts is as simple as parsing the pairs of ranges on each line, and testing each pair with each of these methods.
Code for Day 4
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import { readInputForChallenge } from '../helpers.js';
class NumRange {
/**
* Represents a range of numbers, inclusive
* @param {Number} start the starting number of the range
* @param {Number} end the ending number of the range
*/
constructor(start, end) {
this.start = start;
this.end = end;
}
/**
* Test if this range fully contains `other` range.
* @param {NumRange} other the range to compare against
* @returns `true` if this range fully contains the `other` range
*/
contains = function (other) {
return this.start <= other.start && this.end >= other.end;
};
/**
* Test if any part of this range overlaps `other` range.
* @param {NumRange} other the range to compare against
* @returns `true` if this range overlaps the other range at all.
*/
overlaps = function (other) {
return (
(this.start <= other.end && this.end >= other.end) ||
(this.end >= other.start && this.start <= other.end)
);
};
toString = function () {
return `Range(${this.start}, ${this.end})`;
};
}
/**
* Parse a string in the format #-# (where # represents any number of digits)
* into a `NumRange` object.
* @param {String} str string containing two ranges to parse
* @returns {NumRange} a tuple containing each of the ranges
*/
function parseRangeString(str) {
const numStrings = str.split('-');
const start = parseInt(numStrings[0]);
const end = parseInt(numStrings[1]);
return new NumRange(start, end);
}
/**
* Parse all of the initial input data for this problem
* @returns {[[NumRange, NumRange]]} array of tuples containing pairs of ranges
*/
function parseInput() {
const lines = readInputForChallenge('04');
let pairs = [];
for (let line of lines) {
const ranges = line.split(',');
const range1 = parseRangeString(ranges[0]);
const range2 = parseRangeString(ranges[1]);
pairs.push([range1, range2]);
}
return pairs;
}
/**
* Main run function
*/
function run() {
const pairs = parseInput();
let fullyContainedCount = 0;
let overlapCount = 0;
for (let pair of pairs) {
const [first, second] = pair;
// part 1, get number of pairs which one fully contains the other
if (first.contains(second) || second.contains(first)) {
fullyContainedCount++;
}
//part 2, get number of pairs which partially overlap
if (first.overlaps(second)) {
overlapCount++;
}
}
console.log(`fullyContainedCount: ${fullyContainedCount}`);
console.log(`overlapCount: ${overlapCount}`);
}
export { run };
Reflection
In this challenge, I took a lesson from my reflection on Day 2 an made sure to decouple the NumRange constructor from any string parsing. There’s not a whole lot new to talk about in this challenge that hasn’t already been covered in the previous days, so I’ll leave it at this.
Day 5
Day 5 involves more string parsing, multi-dimensional arrays, data structures like Stack, and understanding the difference between value types and reference types. This was also my first challenge where I implemented TypeScript (see Typescript Build System).
This challenge asks us to read in the initial state of a list of stacks, each of which contains some number of crates. Then we are to read in a list of moves telling us to move x amount of crates from one stack to another. The sample input looks like this (the real input has 9 stacks, so that’s what my code is designed to handle):
1
2
3
4
5
6
7
8
9
[D]
[N] [C]
[Z] [M] [P]
1 2 3
move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2
Part 1
Part one asks us to process the moves one crate at a time and then give the top crate from each stack.
Part 2
Part two asks us to process the moves by moving all the crates all at once and then give the top crate from each stack.
Solution
For this solution, the first step is to parse the input. For this, I used a state machine style loop, which utilizes PARSE and MANIPULATE states to determine which kind of parsing to do for each line. We start by parsing the contents of each stack from the first set of lines. When we find a blank line we switch the mode to MANIPULATE. This mode parses each line into a Move object that holds the number of crates to move, and which stacks to move them from and to.
The next step is to perform the list of moves for each of the different stacking methods. We first have to make a copy of the stacks and moves variables, since these are passed by reference to the processing functions to be modified from within the function, rather than returning a value.
function processMovesSingle(stacks: StackArray, moves: Array<Move>)- This function uses a while loop to loop through each of the
moves. Each move, we create aforloop that runsmove.counttimes. Each iteration of this loop pops the first value off of the source stack, and pushes it onto the destination stack. function processMovesMultiple(stacks: StackArray, moves: Array<Move>)- This is the version that will move all crates at once in a single stack, rather than individually like the previous. For each move, instead of doing a for loop to pop multiple items off of the source stack, we use
array.slice()to cutmove.countitems off the end of the source stack and add them to the end of the destination stack.
Code for Day 5
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
import { readInputForChallenge } from '../helpers.js';
declare type StackArray = Array<Array<string>>;
enum Mode {
PARSE,
MANIPULATE,
}
class Move {
constructor(count: number, from: number, to: number) {
this.count = count;
this.from = from;
this.to = to;
}
count: number;
from: number;
to: number;
}
function parseInput(stacks: StackArray, moves: Array<Move>) {
const lines = readInputForChallenge('05');
let mode = Mode.PARSE;
for (let line of lines) {
// check for empty line, signals end of parsing, start of manipulating
if (line === '') {
mode = Mode.MANIPULATE;
continue;
}
// read initial state of stacks
if (mode === Mode.PARSE) {
//if the line has a 1, skip it, it's the label line and we don't care
if (line[1] === '1') {
continue;
}
// get each 4 character substring of line to parse
for (let stackIndex = 0; stackIndex < 9; stackIndex++) {
// get contents of crate from substring
const sub = line.substring(stackIndex * 4, (stackIndex + 1) * 4);
const crateContents = sub[1];
// add contents to bottom of stack if it is not blank
if (crateContents !== ' ') {
stacks[stackIndex].unshift(crateContents);
}
}
} else {
const parts = line.split(' ');
const count = parseInt(parts[1]);
const from = parseInt(parts[3]) - 1;
const to = parseInt(parts[5]) - 1;
moves.push(new Move(count, from, to));
}
}
}
function processMovesSingle(stacks: StackArray, moves: Array<Move>) {
let move: Move | undefined;
while ((move = moves.shift())) {
for (let i = 0; i < move.count; i++) {
const crate = stacks[move.from].pop();
if (crate) {
stacks[move.to].push(crate);
}
}
}
}
function processMovesMultiple(stacks: StackArray, moves: Array<Move>) {
let move: Move | undefined;
while ((move = moves.shift())) {
const splitIndex = stacks[move.from].length - move.count;
// copy crates off top of from stack
let crates = stacks[move.from].slice(splitIndex);
// remove crates from top of from stack
stacks[move.from] = stacks[move.from].slice(0, splitIndex);
// add crates to top of to crate
stacks[move.to].push(...crates);
}
}
/**
* Get all the top crates from `stacks`
* @param stacks
* @returns String containing the top crate of each stack in `stacks`
*/
function getTopLayer(stacks: StackArray) {
return stacks.reduce(
(res, curr) => res + (curr.at(-1) ? curr.at(-1) : ''),
''
);
}
/**
* Copy a 2D array
* @param stacks 2D array to copy
* @returns copied array
*/
function copy2D(stacks: StackArray): StackArray {
return stacks.map((stack) => [...stack]);
}
function run() {
//initialize stacks with 9 empty arrays
let stacks: StackArray = [];
let stacksMultiple: StackArray;
let moves: Array<Move> = [];
for (let i = 0; i < 9; i++) {
stacks[i] = [];
}
//parse input and copy for part 2
parseInput(stacks, moves);
// can't do shallow copy for stacks because sub-arrays still have same ref
stacksMultiple = copy2D(stacks);
// part 1
processMovesSingle(stacks, [...moves]); // using spread to create shallow copy
let topLayer = getTopLayer(stacks);
console.log(`Part 1: ${topLayer}`);
// part 2
processMovesMultiple(stacksMultiple, [...moves]); // using spread to create shallow copy
topLayer = getTopLayer(stacksMultiple);
console.log(`Part 2: ${topLayer}`);
}
export { run };
Reflection
This challenge was good for brushing up on value/reference types, shallow vs deep copying, and one of the basic data structures.
One thing that could improve robustness in real world applications is to make the stack parsing implementation support any number of stacks, rather than the 9 it is currently hard-coded for. This hypothetical implementation might read each line into a buffer until it reaches the line with the stack labels ( 1 2 3 ...), get the number of stacks from this line, and then go back through the buffer to read in the values of the stacks.
Interesting techniques
- Pass-by-reference - For my parsing and processing functions, I pass objects by reference and use side-effects of those functions instead of returning values directly from them.
- Shallow copy - to shallow copy a single dimensional array, you can use the spread operator:
[...array] - Deep copy - However, for multidimensional arrays, you can’t do this, as the nested arrays will still reference the same objects, even though the top-level array has a new reference. To do this, I wrote a simple function that copies a 2D array using a combination of map and the spread operator:
1 2 3
function copy2D(stacks: StackArray): StackArray { return stacks.map((stack) => [...stack]); }
- Deep(er) copy - I also created another
deepCopyfunction in myhelpersmodule that can copy any dimension of array using recursion:1 2 3 4 5 6 7 8
function deepCopy(array) { return array.map((val) => { if (Array.isArray(val)) { return deepCopy(val); } return val; }); }
- Stack - The basic data structure which has the methods
pushandpopwhich add and remove an item from the top of the stack respectively. There is no native stack implementation, but the native Array has both thepushandpopmethods built in. I felt like rolling my own Stack implementation was overkill for this project, and I don’t want to include any external dependencies in the solutions to these challenges, so I used the native array for my Stacks. The only downside to this is that some of the other Stack methods likepeekare not present in native javacsript arrays, so I had to use theArray.at(-1)method to peek the last value of the array - seegetTopLayerfunction for example.