Advent of Code - puzzle solutions

This is my repo with code solutions for the amazing Advent of Code challenge.

All code is written in TypeScript.

Note that you can't run the programs, because the input files are missing.
The Advent of Code owner asked participants to not republish them, as they are copyrighted by him. It is his work, so he decides that and we should comply.

So, if you want to run the puzzles, you need to download the input files yourself, and put then in the input directory, like this:

./input/2015/01.input.txt
./input/2015/02.input.txt
./input/2015/02.test1.txt

Setup/install/run

Clone this repo, then do:

npm install

To make a puzzle template for a new day:

npm run makeDay {year} {day}

To run a puzzle program, do:

npm run day {year} {day}

To run the whole year of puzzles:

npm run year {year}

Reports will be pushed into the report directory.

Puzzle status

year	status	comment	report
2015	SOLVED	Optimized, all but md5 puzzles run under 1 second	reports/2015.md
2016	IN PROGRESS	stuck on 22 (hard disk move)
2017	IN PROGRESS	ongoing on 20
2018	IN PROGRESS	ongoing on 14
2019	TODO
2020	TODO
2021	IN PROGRESS	ongoing on 20
2022	DONE	Unoptimized, Needs fix after 16
2023	ALMOST DONE	Unoptimized, needs cleaning, do last puzzles
2024	ONGOING

Puzzle options options:

key	type	description
config.title	string, optional	puzzle title
config.comment	string, optional	puzzle comments
config.status	'done', 'inprogress'	puzzle status
config.difficulty	1 to 5	puzzle difficulty
config.tags	string[], optional	puzzle tags (recursive, pathfinding, md5, etc)
config.year	string, mandatory	chooses the year
config.day	string, mandatory	chooses the day
logLevel	string	sets log level (info, debug, etc) default: info
mode	string?	if there is another solution (fastest, easiest, etc) default: normal
ui	object	UI stuff default: { show: false }
ui.show	boolean	show or not the UI
ui.end	boolean?	show the UI in he end
ui.during	boolean?	show the UI in iterations
ui.wait:	number?	wait for X milliseconds between iterations
ui.keypress	boolean?	wait for keypress
test	Test?, Test[]?	runs tests
test.id	string	tied to the test input file name
test.params	any	additional params
test.answers	any	object with part1 and/or part2 answers. It decides if parts should run or be skipped.
prod	Prod?	runs final
prod.params	any	additional params
prod.answers	any	object with part1 and/or part2 answers. It decides if parts should run or be skipped.
params	any	params

List of tags used:

• dijkstra
• recursion
• a*
• permutation
• md5
• combination
• breath first
• path finding

Proposal for:

• STATUS: unsolved, solved
• SPEED: slow, fast
• CODE: clean (optimized), dirty (unoptimized)

Coding guidelines

Typing

• do type everything. Avoid any type. reuse types such as Point, Dimension, World, they help.
• If possible, avoid Record and use Map. Set are also useful sometimes instead of Array

Coding names

• Be as declarative as possible, use function names to describe the steps Some functions names: solveFor, deepFirst, breathFirst, dijkstra

Coding style

• try to separate part1 and part2, while avoiding unnecessary array walks for each part.

Dependencies

• Avoid lodash, use native JS
• libraries allowed: ** js-combinatronics (for permutation / combination) ** spark-mp5 (md5 generation)

Regex

• Prefer match with /g than matchAll, as in

  "abcabfgabsefd".match(/ab/) => ['ab', index: 0, input: 'abcabfgabsefd', groups: undefined]
  "abcabfgabsefd".match(/ab/g) => ['ab', 'ab', 'ab']
  "123123123".match(/ab/) => null
  

Algorithms Overview

Path finding algorithms

Table summary:

Name	weighted graph	visits all paths?	guarantees shortest?	heuristics	comments
DFS	no	no	no	no	only if you want to find any path
BFS	no	yes	yes	no	not for weighted graphs
Dijkstra	yes	yes	yes	no	can be slow on big graphs
A*	yes	yes	yes	yes	can be faster than Dijkstra if heuristic is good
Greedy	-	no	no	yes	not good as shortest is not guaranteed
Bellman-Ford	yes, negatives	yes	yes	no	Dijkstra for weights with negative values
UCS	yes	yes	yes	no	Dijkstra-ish

Floyd-Warshall

Dijkstra’s Algorithm

• Dijkstra’s algorithm finds the shortest path from a start node to all other nodes in a weighted graph.
• It explores all possible paths systematically, always expanding the least-cost node first, and guarantees the shortest path.
• It does not use heuristics, so it works on any graph but can be slow for large graphs.

A* Algorithm

• A* improves upon Dijkstra’s algorithm by using a heuristic function to estimate the distance to the goal.
• It combines this estimate with the actual cost to the current node, allowing it to focus on promising paths.
• This makes A* faster than Dijkstra’s for many problems, but its performance depends on the quality of the heuristic.

Breadth-First Search (BFS)

• BFS explores all nodes at the current depth before moving to the next level.
• It is unweighted and guarantees the shortest path in graphs where all edges have the same weight.
• It is NOT suitable for weighted graphs.

Depth-First Search (DFS)

• DFS explores as far as possible along each path before backtracking.
• It does not guarantee the shortest path and is not optimal for pathfinding but can be useful for exploring or checking graph connectivity.

Greedy Best-First Search

• Greedy Best-First Search uses only the heuristic to choose which node to expand next.
• It focuses on the direction of the goal but does not guarantee the shortest path and can get stuck in suboptimal routes.

Bellman-Ford Algorithm

• Bellman-Ford finds the shortest path from a start node to all other nodes, even with negative edge weights.
• It is slower than Dijkstra’s but works in situations where Dijkstra’s cannot, such as graphs with negative weights.

Floyd-Warshall Algorithm

• Floyd-Warshall calculates shortest paths between all pairs of nodes in a graph.
• It is suitable for small, dense graphs but is computationally expensive and not used for single-source pathfinding.

Uniform-Cost Search (UCS)

• UCS is similar to Dijkstra’s algorithm but focuses only on finding the shortest path to a specific goal node.
• It expands the least-cost node first and guarantees the shortest path, making it optimal but slower than A* for large graphs.

IDEAS

• introduce PointObj, where {row: number, col: number}

Guidelines

X or Y? Rows and Columns?

row goes vertical, col goes horizontal unless it is specified otherwise in the instructions, x and y should be avoided, but if not, x IS ROW, y IS COLUMN, therefore NOT EQUIVALENT to X/Y charts NOT HTML positions.

when printing world, world matrixes are also row and colum

row 0, col 0, x 0, y 0	row 0, col 1, x 0, y 1	row 0, col 2, x 0, y 2	row 0, col 3, x 0, y 3
row 1, col 0, x 1, y 0	row 1, col 1, x 1, y 1	row 1, col 2, x 1, y 2	row 1, col 3, x 1, y 3
row 2, col 0, x 2, y 0	row 2, col 1, x 2, y 1	row 2, col 2, x 2, y 2	row 2, col 3, x 2, y 3
row 3, col 0, x 3, y 0	row 3, col 1, x 3, y 1	row 3, col 2, x 2, y 2	row 3, col 3, x 3, y 3

• move away from [number, number, number, string] or something, use objects so all is more readable

• speed is good, readability is even better

• rethink renaming Point to Location. Location implies coordinates, Point is something that has location but also extra stuff

• dimension: to object where I have Height, width to better signal that the first value is for number of rows, other one is for number of colums

• Get the terminology ready:

• • path: succession of steps. Should it be changed?
• • head: latest step

• better describe the differences between BFS, DFS, Dijkstra, A* and why each should have: ** visited cache ** sort by distance / heuristic / etc

• what about pop() instead of splice(-1)[0]