Apparently posting it caused enough load to take down my pict-rs server, sorry about that.
Ended up oversleeping somewhat, so I did the first part on the way to work using flood fills over a global visited set, and now that work's over I've sat down to expand that solution to do corner counting for part two as well.
C#
char[] map = new char[0];
(int X, int Y) size = (0, 0);
public void Input(IEnumerable<string> lines)
{
map = string.Concat(lines).ToCharArray();
size = (lines.First().Length, lines.Count());
}
Dictionary<HashSet<(int,int)>,int> areas = new Dictionary<HashSet<(int,int)>,int>();
public void PreCalc()
{
HashSet<(int, int)> visited = new HashSet<(int, int)>();
for (int y = 0; y < size.Y; ++y)
for (int x = 0; x < size.X; ++x)
{
var at = (x, y);
if (visited.Contains(at))
continue;
var area = Flood((x, y), visited);
areas[area.Area] = area.Perim;
}
}
public void Part1()
{
int sum = areas.Select(kv => kv.Key.Count * kv.Value).Sum();
Console.WriteLine($"Fencing total: {sum}");
}
public void Part2()
{
int sum = areas.Select(kv => kv.Key.Count * countCorners(kv.Key)).Sum();
Console.WriteLine($"Fencing total: {sum}");
}
readonly (int dX, int dY)[] links = new[] { (1, 0), (0, 1), (-1, 0), (0, -1) };
(HashSet<(int,int)> Area, int Perim) Flood((int X, int Y) from, HashSet<(int X, int Y)> visited)
{
char at = map[from.Y * size.X + from.X];
(HashSet<(int,int)> Area, int Perim) ret = (new HashSet<(int,int)>(), 0);
visited.Add(from);
ret.Area.Add(from);
foreach (var link in links)
{
(int X, int Y) newAt = (from.X + link.dX, from.Y + link.dY);
char offset ;
if (newAt.X < 0 || newAt.X >= size.X || newAt.Y < 0 || newAt.Y >= size.Y)
offset = '\0';
else
offset = map[newAt.Y * size.X + newAt.X];
if (offset == at)
{
if (visited.Contains(newAt))
continue;
var nextArea = Flood(newAt, visited);
ret.Area.UnionWith(nextArea.Area);
ret.Perim += nextArea.Perim;
}
else
{
ret.Perim += 1;
}
}
return ret;
}
readonly (int dX, int dY)[] cornerPoints = new[] { (0, 0), (1, 0), (1, 1), (0, 1) };
readonly int[] diagonalValues = new[] { (2 << 0) + (2 << 2), (2 << 1) + (2 << 3) };
int countCorners(HashSet<(int X, int Y)> points)
{
int corners = 0;
var bounds = findBounds(points);
for (int y = bounds.minY - 1; y < bounds.maxY + 1; ++y)
for (int x = bounds.minX - 1; x < bounds.maxX + 1; ++x)
{
var atPoint = cornerPoints.Select(c => points.Contains((x + c.dX, y + c.dY)));
var before = corners;
if (atPoint.Where(c => c).Count() % 2 == 1)
corners++;
else if (diagonalValues.Contains(atPoint.Select((c, i) => c ? (2 << i) : 0).Sum()))
corners += 2;
}
return corners;
}
(int minX, int minY, int maxX, int maxY) findBounds(HashSet<(int X, int Y)> points)
{
(int minX, int minY, int maxX, int maxY) ret = (int.MaxValue, int.MaxValue, int.MinValue, int.MinValue);
foreach (var point in points)
{
ret.minX = Math.Min(ret.minX, point.X);
ret.minY = Math.Min(ret.minY, point.Y);
ret.maxX = Math.Max(ret.maxX, point.X);
ret.maxY = Math.Max(ret.maxY, point.Y);
}
return ret;
}
Well, there's the ALFIS project
And now we get into the days where caching really is king. My first attempt didn't go so well, I tried to handle the full list result as one cache step, instead of individually caching the result of calculating each stone per step.
I think my original attempt is still calculating at home, but I finished up this much better version on the trip to work.
All hail public transport.
C#
List<long> stones = new List<long>();
public void Input(IEnumerable<string> lines)
{
stones = string.Concat(lines).Split(' ').Select(v => long.Parse(v)).ToList();
}
public void Part1()
{
var expanded = TryExpand(stones, 25);
Console.WriteLine($"Stones: {expanded}");
}
public void Part2()
{
var expanded = TryExpand(stones, 75);
Console.WriteLine($"Stones: {expanded}");
}
public long TryExpand(IEnumerable<long> stones, int steps)
{
if (steps == 0)
return stones.Count();
return stones.Select(s => TryExpand(s, steps)).Sum();
}
Dictionary<(long, int), long> cache = new Dictionary<(long, int), long>();
public long TryExpand(long stone, int steps)
{
var key = (stone, steps);
if (cache.ContainsKey(key))
return cache[key];
var result = TryExpand(Blink(stone), steps - 1);
cache[key] = result;
return result;
}
public IEnumerable<long> Blink(long stone)
{
if (stone == 0)
{
yield return 1;
yield break;
}
var str = stone.ToString();
if (str.Length % 2 == 0)
{
yield return long.Parse(str[..(str.Length / 2)]);
yield return long.Parse(str[(str.Length / 2)..]);
yield break;
}
yield return stone * 2024;
}
Nice to have a really simple one for a change, both my day 1 and 2 solutions worked on their very first attempts.
I rewrote the code to combine the two though, since the implementations were almost identical for both solutions, and also to replace the recursion with a search list instead.
C#
int[] heights = new int[0];
(int, int) size = (0, 0);
public void Input(IEnumerable<string> lines)
{
size = (lines.First().Length, lines.Count());
heights = string.Concat(lines).Select(c => int.Parse(c.ToString())).ToArray();
}
int trails = 0, trailheads = 0;
public void PreCalc()
{
for (int y = 0; y < size.Item2; ++y)
for (int x = 0; x < size.Item1; ++x)
if (heights[y * size.Item1 + x] == 0)
{
var unique = new HashSet<(int, int)>();
trails += CountTrails((x, y), unique);
trailheads += unique.Count;
}
}
public void Part1()
{
Console.WriteLine($"Trailheads: {trailheads}");
}
public void Part2()
{
Console.WriteLine($"Trails: {trails}");
}
int CountTrails((int, int) from, HashSet<(int,int)> unique)
{
int found = 0;
List<(int,int)> toSearch = new List<(int, int)>();
toSearch.Add(from);
while (toSearch.Any())
{
var cur = toSearch.First();
toSearch.RemoveAt(0);
int height = heights[cur.Item2 * size.Item1 + cur.Item1];
for (int y = -1; y <= 1; ++y)
for (int x = -1; x <= 1; ++x)
{
if ((y != 0 && x != 0) || (y == 0 && x == 0))
continue;
var newAt = (cur.Item1 + x, cur.Item2 + y);
if (newAt.Item1 < 0 || newAt.Item1 >= size.Item1 || newAt.Item2 < 0 || newAt.Item2 >= size.Item2)
continue;
int newHeight = heights[newAt.Item2 * size.Item1 + newAt.Item1];
if (newHeight - height != 1)
continue;
if (newHeight == 9)
{
unique.Add(newAt);
found++;
continue;
}
toSearch.Add(newAt);
}
}
return found;
}
Was really blanking on how to do this one nicely, so a bunch of stacked loops it is...
Also ended up writing two separate solutions for the first and second part, since I couldn't get acceptable performance otherwise. Still takes half a second on my machine, mainly on the second part.
This is technically the second implementation, the first one took minutes to calculate, so I wasn't really okay with stamping it as my solution-of-choice.
Can definitely still be improved, but I've been poking and prodding at this code for hours on end now, so it's long past time to let it sit for a while and see if I get any better ideas later.
C#
int[] layout = new int[0];
public void Input(IEnumerable<string> lines)
{
layout = string.Join("", lines).ToCharArray().Select(c => int.Parse(c.ToString())).ToArray();
}
public void Part1()
{
ushort?[] blocks = BuildBlockmap().ToArray();
var it = 0;
for (var i = blocks.Length - 1; i > it; i--)
{
if (blocks[i] == null)
continue;
while (it < blocks.Length && blocks[it] != null)
++it;
if (it >= blocks.Length)
break;
(blocks[it], blocks[i]) = (blocks[i], null);
}
long checksum = 0;
foreach (var part in blocks.OfType<ushort>().Select((b, i) => i * b))
checksum += part;
Console.WriteLine($"Checksum: {checksum}");
}
public void Part2()
{
var sparse = BuildSparsemap().ToList();
for (var i = sparse.Count - 1; i >= 0; i--)
{
if (sparse[i].Item1 == null)
continue;
for (var j = 0; j < i; ++j)
{
if (sparse[j].Item1 != null)
continue;
if (sparse[i].Item2 > sparse[j].Item2)
continue;
var size = sparse[j].Item2;
size -= sparse[i].Item2;
(sparse[j], sparse[i]) = (sparse[i], (null, sparse[i].Item2));
if (i + 1 < sparse.Count && sparse[i + 1].Item1 == null)
{
sparse[i] = (null, (ushort)(sparse[i].Item2 + sparse[i + 1].Item2));
sparse.RemoveAt(i + 1);
}
if (sparse[i - 1].Item1 == null)
{
sparse[i - 1] = (null, (ushort)(sparse[i - 1].Item2 + sparse[i].Item2));
sparse.RemoveAt(i);
}
if (size > 0)
sparse.Insert(j + 1, (null, size));
j = i + 1;
}
}
int ind = 0;
long checksum = 0;
foreach (var (val, cnt) in sparse)
for (var i = 0; i < cnt; ++i)
{
checksum += (val ?? 0) * ind;
++ind;
}
Console.WriteLine($"Checksum: {checksum}");
}
IEnumerable<ushort?> BuildBlockmap()
{
ushort blockit = 0;
bool block = true;
foreach (var value in layout)
{
for (int i = 0; i < value; ++i)
yield return block ? blockit : null;
if (block)
blockit++;
block = !block;
}
}
IEnumerable<(ushort?, ushort)> BuildSparsemap()
{
ushort blockit = 0;
bool block = true;
foreach (var value in layout)
{
if (block)
yield return (blockit++, (ushort)value);
else
yield return (null, (ushort)value);
block = !block;
}
}
And I of course misread and wasted a bunch of time debugging the second part, entirely missed the fact that antinodes occurred on top of the emanating antennae as well...
C#
public static class LINQExt
{
public static IEnumerable<(T,T)> PermutatePairs<T>(this IEnumerable<T> source) {
return source.SelectMany(k => source.Where(v => !v?.Equals(k) ?? false).Select(v => (k, v)));
}
}
struct Antenna
{
public int X, Y;
public char Frequency;
}
List<Antenna> antennae = new List<Antenna>();
int width, height;
public void Input(IEnumerable<string> lines)
{
char[] map = string.Join("", lines).ToCharArray();
width = lines.First().Length;
height = lines.Count();
for (int y = 0; y < height; ++y)
for (int x = 0; x < width; ++x)
{
char at = map[y * width + x];
if (at == '.')
continue;
antennae.Add(new Antenna{ X = x, Y = y, Frequency = at });
}
}
public void Part1()
{
HashSet<(int, int)> antinodes = new HashSet<(int, int)>();
foreach (var antinode in antennae.GroupBy(k => k.Frequency).SelectMany(g => g.PermutatePairs()).SelectMany(v => GetOpposing(v.Item1, v.Item2)).Where(InRange))
antinodes.Add(antinode);
Console.WriteLine($"Unique antinodes: {antinodes.Count}");
}
public void Part2()
{
HashSet<(int, int)> antinodes = new HashSet<(int, int)>();
foreach (var antennaePair in antennae.GroupBy(k => k.Frequency).SelectMany(g => g.PermutatePairs()))
{
// Iterate separately, to make the handling of bound exit easier
foreach (var antinode in GetAllOpposing(antennaePair.Item1, antennaePair.Item2).TakeWhile(InRange))
antinodes.Add(antinode);
foreach (var antinode in GetAllOpposing(antennaePair.Item2, antennaePair.Item1).TakeWhile(InRange))
antinodes.Add(antinode);
}
Console.WriteLine($"Unique antinodes: {antinodes.Count}");
}
bool InRange((int, int) point) {
return point.Item1 >= 0 && point.Item1 < width && point.Item2 >= 0 && point.Item2 < height;
}
(int, int)[] GetOpposing(Antenna a, Antenna b) {
return new[] { (a.X + (a.X - b.X), a.Y + (a.Y - b.Y)), (b.X + (b.X - a.X), b.Y + (b.Y - a.Y)) };
}
IEnumerable<(int, int)> GetAllOpposing(Antenna a, Antenna b) {
(int, int) diff = (a.X - b.X, a.Y - b.Y);
(int, int) at = (a.X, a.Y);
yield return at;
while (true)
{
at.Item1 += diff.Item1;
at.Item2 += diff.Item2;
yield return at;
}
}
That is true, I've evidently not had enough coffee yet this morning.
Made a couple of attempts to munge the input data into some kind of binary search tree, lost some time to that, then threw my hands into the air and did a more naรฏve sort-of breadth-first search instead. Which turned out to be better for part 2 anyway.
Also, maths. Runs in just over a hundred milliseconds when using AsParallel, around half a second without.
::: spoiler C#
List<(long, int[])> data = new List<(long, int[])>();
public void Input(IEnumerable<string> lines)
{
foreach (var line in lines)
{
var parts = line.Split(':', StringSplitOptions.TrimEntries);
data.Add((long.Parse(parts.First()), parts.Last().Split(' ').Select(int.Parse).ToArray()));
}
}
public void Part1()
{
var correct = data.Where(kv => CalcPart(kv.Item1, kv.Item2)).Select(kv => kv.Item1).Sum();
Console.WriteLine($"Correct: {correct}");
}
public void Part2()
{
var correct = data.AsParallel().Where(kv => CalcPart2(kv.Item1, kv.Item2)).Select(kv => kv.Item1).Sum();
Console.WriteLine($"Correct: {correct}");
}
public bool CalcPart(long res, Span<int> num, long carried = 0)
{
var next = num[0];
if (num.Length == 1)
return res == carried + next || res == carried * next;
return CalcPart(res, num.Slice(1), carried + next) || CalcPart(res, num.Slice(1), carried * next);
}
public bool CalcPart2(long res, Span<int> num, long carried = 0)
{
var next = num[0];
// Get the 10 logarithm for the next number, expand the carried value by 10^<next 10log + 1>, add the two together
// For 123 || 45
// 45 โ 10log(45) + 1 == 2
// 123 * 10^2 + 45 == 12345
long combined = carried * (long)Math.Pow(10, Math.Floor(Math.Log10(next) + 1)) + next;
if (num.Length == 1)
return res == carried + next || res == carried * next || res == combined;
return CalcPart2(res, num.Slice(1), carried + next) || CalcPart2(res, num.Slice(1), carried * next) || CalcPart2(res, num.Slice(1), combined);
}
Not a big fan of this one, felt far too much like brute force for my liking.
At least it works with AsParallel...
C#
public struct Point : IEquatable<Point>
{
public int X { get; set; }
public int Y { get; set; }
public Point(int x = 0, int y = 0) {
X = x;
Y = y;
}
public static Point operator+(Point l, Point r) {
return new Point(l.X + r.X, l.Y + r.Y);
}
public bool Equals(Point other) {
return X == other.X && Y == other.Y;
}
}
Point size = new Point(0, 0);
HashSet<Point> obstructions = new HashSet<Point>();
Point guard = new Point(0, 0);
enum Direction
{
Up = 0,
Right,
Down,
Left
}
public void Input(IEnumerable<string> lines)
{
size = new Point(lines.First().Length, lines.Count());
char[] map = string.Join("", lines).ToCharArray();
for (int y = 0; y < size.Y; ++y)
for (int x = 0; x < size.X; ++x)
{
int pos = y * size.X + x;
char at = map[pos];
if (at == '#')
obstructions.Add(new Point(x, y));
else if (at == '^')
guard = new Point(x, y);
}
}
List<Point> path = new List<Point>();
public void PreCalc()
{
path = WalkArea().path.Distinct().ToList();
}
public void Part1()
{
Console.WriteLine($"Visited {path.Count} points");
}
public void Part2()
{
int loopPoints = path.AsParallel().Where(p => !p.Equals(guard) && WalkArea(p).loop).Count();
Console.WriteLine($"Valid loop points: {loopPoints}");
}
(IEnumerable<Point> path, bool loop) WalkArea(Point? obstruction = null)
{
HashSet<(Point, Direction)> loopDetect = new HashSet<(Point, Direction)>();
Point at = guard;
Direction dir = Direction.Up;
while (true)
{
if (!loopDetect.Add((at, dir)))
return (loopDetect.Select(p => p.Item1), true);
Point next = at;
switch(dir)
{
case Direction.Up: next += new Point(0, -1); break;
case Direction.Right: next += new Point(1, 0); break;
case Direction.Down: next += new Point(0, 1); break;
case Direction.Left: next += new Point(-1, 0); break;
}
if (next.X < 0 || next.Y < 0 || next.X >= size.X || next.Y >= size.Y)
break;
else if (obstructions.Contains(next) || (obstruction?.Equals(next) ?? false))
dir = (Direction)(((int)dir + 1) % 4);
else
at = next;
}
return (loopDetect.Select(p => p.Item1), false);
}
Well, this one ended up with a surprisingly easy part 2 with how I wrote it.
Not the most computationally optimal code, but since they're still cheap enough to run in milliseconds I'm not overly bothered.
C#
class OrderComparer : IComparer<int>
{
Dictionary<int, List<int>> ordering;
public OrderComparer(Dictionary<int, List<int>> ordering) {
this.ordering = ordering;
}
public int Compare(int x, int y)
{
if (ordering.ContainsKey(x) && ordering[x].Contains(y))
return -1;
return 1;
}
}
Dictionary<int, List<int>> ordering = new Dictionary<int, List<int>>();
int[][] updates = new int[0][];
public void Input(IEnumerable<string> lines)
{
foreach (var pair in lines.TakeWhile(l => l.Contains('|')).Select(l => l.Split('|').Select(w => int.Parse(w))))
{
if (!ordering.ContainsKey(pair.First()))
ordering[pair.First()] = new List<int>();
ordering[pair.First()].Add(pair.Last());
}
updates = lines.SkipWhile(s => s.Contains('|') || string.IsNullOrWhiteSpace(s)).Select(l => l.Split(',').Select(w => int.Parse(w)).ToArray()).ToArray();
}
public void Part1()
{
int correct = 0;
var comparer = new OrderComparer(ordering);
foreach (var update in updates)
{
var ordered = update.Order(comparer);
if (update.SequenceEqual(ordered))
correct += ordered.Skip(ordered.Count() / 2).First();
}
Console.WriteLine($"Sum: {correct}");
}
public void Part2()
{
int incorrect = 0;
var comparer = new OrderComparer(ordering);
foreach (var update in updates)
{
var ordered = update.Order(comparer);
if (!update.SequenceEqual(ordered))
incorrect += ordered.Skip(ordered.Count() / 2).First();
}
Console.WriteLine($"Sum: {incorrect}");
}
Eurofighter Typhoon