That is true, I've evidently not had enough coffee yet this morning.
ace
joined 2 years ago
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}");
}
I tried to think of some clever LINQ to do this one, but was blanking entirely.
So naΓ―ve search it is.
C#
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.
C#
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}");
}
Of course I ended up with a off-by-one error for the second part, so things took a bit longer than they really should've.
But either way, behold, messy C#:
C#
int[][] reports = new int[0][];
public void Input(IEnumerable<string> lines)
{
reports = lines.Select(l => l.Split(' ').Select(p => int.Parse(p)).ToArray()).ToArray();
}
public void Part1()
{
int safeCount = reports.Where(report => CheckReport(report)).Count();
Console.WriteLine($"Safe: {safeCount}");
}
public void Part2()
{
int safeCount = reports.Where(report => {
if (CheckReport(report))
return true;
for (int i = 0; i < report.Length; ++i)
if (CheckReport(report.Where((_, j) => j != i)))
return true;
return false;
}).Count();
Console.WriteLine($"Safe: {safeCount}");
}
bool CheckReport(IEnumerable<int> report)
{
var diffs = report.SkipLast(1).Zip(report.Skip(1)).Select(v => v.Second - v.First);
return diffs.All(v => Math.Abs(v) <= 3) && (diffs.All(v => v > 0) || diffs.All(v => v < 0));
}
Not going to push hard on these first days (fever being a reason), so I slept in quite a bit before looking at the problem.
C#
List<int> _LeftList = new List<int>();
List<int> _RightList = new List<int>();
// Fed via File.ReadLines(...).Select(l => l.Trim())
public void Input(IEnumerable<string> lines)
{
foreach (var line in lines)
{
var split = line.Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(s => int.Parse(s));
_LeftList.Add(split.First());
_RightList.Add(split.Last());
}
}
public void Part1()
{
Console.WriteLine($"Sum: {_LeftList.Order().Zip(_RightList.Order()).Select(v => Math.Abs(v.First - v.Second)).Sum()}");
}
public void Part2()
{
Console.WriteLine($"Sum: {_LeftList.Select(l => _RightList.Where(i => i == l).Count() * l).Sum()}");
}
I just do the Swedish accent thing and pronounce it forge-yo (like in yo-yo, not the greeting proclamation)
Well, this has certainly caused quite a bit of drama from all sides.
I'm curious about the earlier audit of libolm which happened many years back (and by a reputable company), it feels like it should've found any potentially exploitable issues after all - including timing attacks.
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#