Solutions are organized as separate branches in the repository, not as subfolders within a single branch.
New methods
CountByandAggregateByhave been introduced. These methods make it possible to aggregate state by key without needing to allocate intermediate groupings viaGroupBy.— https://learn.microsoft.com/en-us/dotnet/core/whats-new/dotnet-9/libraries#linq
var countByNumber = rightNumbers.CountBy(it => it).ToFrozenDictionary();Tried the Math.BigMul API for the first time.
long SingleSimilarityScore(int number) =>
Math.BigMul(number, countByNumber.GetValueOrDefault(number, 0));The .NET SDK (version 7 and later) includes a source generator that recognizes the
GeneratedRegexAttributeattribute on a partial method that returnsRegex.— https://learn.microsoft.com/en-us/dotnet/standard/base-types/regular-expression-source-generators
private static Regex MulRegex => s_regex ??= CreateRegex();
[GeneratedRegex(@"mul\((\d{1,3}),(\d{1,3})\)",
RegexOptions.Compiled | RegexOptions.CultureInvariant)]
private static partial Regex CreateRegex();var matches = MulRegex.Matches(line);The whole input can contain cycles. But updates seem to be DAGs, otherwise there is no solution. It looks like the second part of the puzzle can be solved just by sorting pages within updates with a partial and non-transitive comparer for particular inputs. But in general you need a topological sorting of the pages.
var outNeighborsMap = edges.ToLookup(it => it.Tail, it => it.Head)
.ToFrozenDictionary(it => it.Key, it => it.ToFrozenSet());
...
List<int> Sort(IReadOnlyList<int> pages)
{
List<int> sortedPages = [];
var inducedOutNeighborsMap = pages.ToFrozenDictionary(
it => it, it => outNeighborsMap.GetValueOrDefault(it, []).Intersect(pages).ToFrozenSet());
var graph = ReadOnlyAdjacencyGraph<int>.FromFrozenSets(inducedOutNeighborsMap);
var handler = CreateDfsHandler(graph);
handler.FinishVertex += (_, v) => sortedPages.Add(v);
EagerDfs<int, FrozenSet<int>.Enumerator>.Traverse(graph, pages, handler);
sortedPages.Reverse();
return sortedPages;
}Here I used a type inference trick, since the actual types of the handler and the graph are very complicated.
private static DfsHandler<int, Endpoints<int>, TGraph> CreateDfsHandler<TGraph>(TGraph _) => new();Tried the API for Vector128<int> to rotate the direction (x, y) ↦ (y, −x):
using V = Vector128<int>;
...
private static V Rotate(V direction)
{
var temp = Vector128.Shuffle(direction, Vector128.Create(1, 0, 2, 3));
return temp * Vector128.Create(1, -1, 1, 1);
}Used depth-first search.
internal readonly record struct Equation(long TestValue, int[] Numbers) { … }
internal readonly record struct Node(long RunningTotalInclusive, int Index);
…
private static bool CanBeTrue(Equation equation)
{
Node source = new(equation.Numbers[0], 0);
Graph graph = new(equation);
var nodes = EnumerableDfs<Node>.EnumerateVertices(graph, source);
int lastIndexInclusive = equation.Numbers.Length - 1;
return nodes.Any(it => it.RunningTotalInclusive == equation.TestValue && it.Index == lastIndexInclusive);
}feature/08-resonant-collinearity
An antinode occurs at any grid position exactly in line with at least two antennas of the same frequency, regardless of distance.
It's not clear whether we should divide the direction vector on the GCD of its components to get the step vector.
The basic data structure for this puzzle is a double-ended queue of block spans.
internal readonly record struct BlockSpan(int Id, int Start, int Length)
{
internal bool IsFile => Id >= 0;
internal bool IsFree => Id < 0;
}Depth-first search and dynamic programming. The only trick is to share the cache per trailhead, not per pair (trailhead, destination). To achieve this, I traversed the topographic map forwards to find the trail ends for each trailhead, then backwards during the “dynamic” part.
Dynamic programming using the cache with the Node as the key.
internal readonly record struct Node(long Stone, int RemainingBlinks);The most difficult part is dealing with the perimeter. From the following graph definition, I filter all bound edges that "stick out" for each region (connected component).
public IEnumerator<V> EnumerateOutNeighbors(V vertex)
{
if (!_grid.TryGetValue(vertex, out char kind) || kind != _kind)
yield break;
foreach (var direction in Helpers.Directions)
yield return vertex + direction; // No bound checks here!
}Then I build a meta-graph whose nodes are such bound edges pointing out of regions. And a side of a region is a connected component in such a meta-graph.
To solve a system of linear equations I use Cramers's rule.
A fancy way of calculating the determinant:
using V = Vector128<long>;
…
private static long Det(V left, V right)
{
var rightReordered = Vector128.Shuffle(right, Vector128.Create(1, 0));
var product = left * rightReordered;
return Vector128.Sum(Vector128.Create(1, -1) * product);
}I optimize the score, where the score is the number of robots with two other robots in their Von Neumann neighborhood.
The other idea was to optimize the score, defined as the information entropy of the robots' positions:
I ustilized ImmutableHashSet<V> for box positions to simplify the simulation.
The trick is to define a graph that operates not on tiles of the map, but instead on nodes, where the node is a pair (tile, direction). Each node then has three candidate edges: move, turn left, turn right. These edges are weighted, so we can apply Dijkstra's algorithm.
For the second part, I define a reversed graph, and traverse from E to S.
Then I count the nodes, for which the sum of their distances from the path endpoints is the known score.
feature/17-chronospatial-computer
Tracing the program reveals that it is a simple loop with a single break. Each 3-bit value at the output depends on at most 10 bits of the current value of register A. This observation allows us to narrow our search using the backtracking technique instead of brute force.
Breadth-first search for pathfinding, and binary search to determine the first byte that will cut off the path to the exit.
I solved it without using a trie, just dynamic programming on offsets within the design sequence.
No need to traverse the modified graphs with “tunnels”. The racetrack has no branches. We can prebuild the distance map and the path. Then, for each position on the track, we enumerate its Von Neumann neighborhood as candidates for the end positions of the cheats, and compare the new Manhattan distance with the one stored in the fair distance map.
Let's look at an execution trace from an example.
<vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>A
v<<A>>^A<A>AvA<^AA>A<vAAA>^A
<A^A>^^AvvvA
029A
For clarity, I have aligned all the button presses on the current level with the A keystrokes on the previous level.
<vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>A
v << A >> ^ A < A > A v A < ^ AA > A < v AAA > ^ A
< A ^ A > ^^ A vvv A
0 2 9 A
We measure the distance between the buttons on the keypad in terms of the number of button presses on the directional keypad of the previous level. It turns out that the shortest path in such a metric is never a zigzag, but always a corner: └ or ┐, ┌ or ┘. But which one? When you need to wrap around the gap on the keypad, you have only one option. Otherwise, the preferred order for each diagonal direction is
↘:v>(is better than>v)↖:<^(is better than^<)↙:<v(is better thanv<)↗:^>(is better than>^)
I used the MoreLINQ library for a sliding window of five elements.
The Bron–Kerbosch algorithm for finding the maximal clique in an undirected graph.
We need to find out which implicit rules are violated by which components of the malfunctioning adder.
- Each z-wire (except the last one) must be connected to an XOR gate.
- Each OR gate must have its inputs connected to AND gates.
- Each XOR gate must be connected to an x, y, or z-wire.
- Each XOR gate whose output is a z-wire (except
z01) must not have an input from an AND gate.