One has super cow powers, the other one doesn’t.
Just another Swedish programming sysadmin person.
Coffee is always the answer.
And beware my spaghet.
One has super cow powers, the other one doesn’t.
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.
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;
}
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.
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.
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.
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…
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.
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
…
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.
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}");
}
I tried to think of some clever LINQ to do this one, but was blanking entirely.
So naïve search it is.
string wordsearch = "";
int width;
int height;
public void Input(IEnumerable<string> lines)
{
wordsearch = string.Join("", lines);
height = lines.Count();
width = lines.First().Length;
}
public void Part1()
{
int words = 0;
for (int y = 0; y < height; y++)
for (int x = 0; x < width; x++)
words += SearchFrom(x, y);
Console.WriteLine($"Words: {words}");
}
public void Part2()
{
int words = 0;
for (int y = 1; y < height - 1; y++)
for (int x = 1; x < width - 1; x++)
words += SearchCross(x, y);
Console.WriteLine($"Crosses: {words}");
}
public int SearchFrom(int x, int y)
{
char at = wordsearch[y * width + x];
if (at != 'X')
return 0;
int words = 0;
for (int ydir = -1; ydir <= 1; ++ydir)
for (int xdir = -1; xdir <= 1; ++xdir)
{
if (xdir == 0 && ydir == 0)
continue;
if (SearchWord(x, y, xdir, ydir))
words++;
}
return words;
}
private readonly string word = "XMAS";
public bool SearchWord(int x, int y, int xdir, int ydir)
{
int wordit = 0;
while (true)
{
char at = wordsearch[y * width + x];
if (at != word[wordit])
return false;
if (wordit == word.Length - 1)
return true;
wordit++;
x += xdir;
y += ydir;
if (x < 0 || y < 0 || x >= width || y >= height)
return false;
}
}
public int SearchCross(int x, int y)
{
if (x == 0 || y == 0 || x == width - 1 || y == width - 1)
return 0;
char at = wordsearch[y * width + x];
if (at != 'A')
return 0;
int found = 0;
for (int ydir = -1; ydir <= 1; ++ydir)
for (int xdir = -1; xdir <= 1; ++xdir)
{
if (xdir == 0 || ydir == 0)
continue;
if (wordsearch[(y + ydir) * width + (x + xdir)] != 'M')
continue;
if (wordsearch[(y - ydir) * width + (x - xdir)] != 'S')
continue;
found++;
}
if (found == 2)
return 1;
return 0;
}
I started poking at doing a proper lexer/parser, but then I thought about how early in AoC it is and how low the chance is that the second part will require proper parsing.
So therefore; hello regex my old friend, I’ve come to talk with you again.
List<string> instructions = new List<string>();
public void Input(IEnumerable<string> lines)
{
foreach (var line in lines)
instructions.AddRange(Regex.Matches(line, @"mul\(\d+,\d+\)|do\(\)|don't\(\)").Select(m => m.Value));
}
public void Part1()
{
var sum = instructions.Select(mul => Regex.Match(mul, @"(\d+),(\d+)").Groups.Values.Skip(1).Select(g => int.Parse(g.Value))).Select(cc => cc.Aggregate(1, (acc, val) => acc * val)).Sum();
Console.WriteLine($"Sum: {sum}");
}
public void Part2()
{
bool enabled = true;
long sum = 0;
foreach(var inst in instructions)
{
if (inst.StartsWith("don't"))
enabled = false;
else if (inst.StartsWith("do"))
enabled = true;
else if (enabled)
sum += Regex.Match(inst, @"(\d+),(\d+)").Groups.Values.Skip(1).Select(g => int.Parse(g.Value)).Aggregate(1, (acc, val) => acc * val);
}
Console.WriteLine($"Sum: {sum}");
}
Remember to join the !advent_of_code@programming.dev community while you’re at it
I just do the Swedish accent thing and pronounce it forge-yo (like in yo-yo, not the greeting proclamation)
And it’s still entirely unrelated to my point, since SUSE will remain the trademark in question regardless of what’s actually contained in OpenSUSE.
But yes, the free/open-source spins of things tend to have somewhat differing content compared to the commercial offering, usually for licensing or support reasons.
E.g. CentOS (when it still was a real thing)/AlmaLinux/etc supporting hardware that regular RHEL has dropped support for, while also not distributing core RedHat components like the subscription manager.
Not at all what my point was. There’s indeed plenty of Open-something (or Libre-something) projects under the sun, but no free/open spins of commercial projects named simply “Open<Trademarked company name / commercial offering>”.
To be fair, OpenSUSE is the only project with a name like that, so it makes some sense that they’d want it changed.
There’s no OpenRedHat, no OpenNovell, no OpenLinspire, etc.
Well, Flatpak always builds the aliases, so as long as the <installation>/exports/bin
folder is in $PATH
there’s no need to symlink.
If you’re talking specifically about having symlinks with some arbitrary name that you prefer, then that’s something you’ll have to do yourself, the Flatpak applications only provide their canonical name after all.
You could probably do something like that with inotify and a simple script though, just point it at the exports/bin
folders for the installations that you care about, and set up your own mapping between canonical names and whatever names you prefer.
In regards to sandboxing, it only gets as far in the way as you ask it to. For applications that you’re not planning on putting on FlatHub anyway you can be just as open as you want to be, i.e. just adding /
- or host
as it’s called - as read-write to the app. (OpenMW still does that as we had some issues with the data extraction for original Morrowind install media)
If you do want to sandbox though, users are able to poke just as many holes as they want - or add their own restrictions atop whatever sandboxing you set up for the application. Flatpak itself has the flatpak override
tool for this, or there’s graphical UIs like flatseal and the KDE control center module…
Currently working to move away from Nextcloud myself, it’s PHP nature causes IO storms when it tries to check if it needs to reload any code for incoming requests.