copy pasting the rules from last year’s thread:
Rules: no spoilers.
The other rules are made up aswe go along.
Share code by link to a forge, home page, pastebin (Eric Wastl has one here) or code section in a comment.
I can’t sleep, so here’s 1-1 and 1-2, unfortunately I couldn’t think of any silly solutions this time, so it’s straightforward instead:
spoiler
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>
#include <iterator>
int main() {
std::multiset<int> l, r;
int a, b;
while (std::cin >> a >> b) {
l.insert(a); r.insert(b);
}
std::vector<int> delta;
std::transform(l.begin(), l.end(), r.begin(), std::back_inserter(delta),
[](int x, int y) { return std::abs(x-y); }
);
std::cout << std::accumulate(delta.begin(), delta.end(), 0) << std::endl;
}
spoiler
#include <iostream>
#include <numeric>
#include <set>
int main() {
std::multiset<int> l, r;
int a, b;
while (std::cin >> a >> b) {
l.insert(a); r.insert(b);
}
std::cout << std::accumulate(l.begin(), l.end(), 0, [&r](int acc, int x) {
return acc + x * r.count(x);
}) << std::endl;
}
2-1: I have quickly run out of hecks to give. This is the sort of problem that gives prolog programmers feelings of smug superiority.
spoiler
#include <string>
#include <iostream>
#include <sstream>
int main() {
int safe = 0;
std::string s;
while (std::getline(std::cin, s)) {
std::istringstream iss(s);
int a, b, c;
if (!(iss >> a >> b)) {
safe++; continue;
}
if (a == b || std::abs(a-b) > 3) continue;
bool increasing = b > a;
while (iss >> c) {
if (b == c || std::abs(b-c) > 3) goto structuredprogrammingisfornerds;
switch (increasing) {
case false:
if (c < b) { b = c; continue; }
goto structuredprogrammingisfornerds;
case true:
if(c > b) { b = c; continue; }
goto structuredprogrammingisfornerds;
}
}
safe++;
structuredprogrammingisfornerds:;
}
std::cout << safe << std::endl;
}
As usual the second part has punished me for my cowboy code, so I’ll have to take a different more annoying tack (maybe tomorrow). Or you know I could just double down on the haphazard approach…
I decided to double down on 2-2, since bad code is one of life’s little pleasures. Where we’re going we won’t need big-oh notation
spoiler
#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <iterator>
template <typename It>
bool seemslegit(It begin, It end) {
if (std::distance(begin, end) == 1) {
return true;
}
int a = *begin++;
int b = *begin++;
if (a == b || std::abs(a-b) > 3) return false;;
bool increasing = b > a;
while (begin != end) {
int c = *begin++;
if (b == c || std::abs(b-c) > 3) return false;;
switch (increasing) {
case false:
if (c < b) { b = c; continue; }
return false;
case true:
if(c > b) { b = c; continue; }
return false;
}
}
return true;
}
template <typename It>
void debug(It begin, It end) {
bool legit = seemslegit(begin, end);
while (begin != end) {
std::cout << *begin++ << " ";
}
//std::cout << ": " << std::boolalpha << legit << std::endl;
}
int main() {
int safe = 0;
std::string s;
while (std::getline(std::cin, s)) {
std::istringstream iss(s);
std::vector<int> report((std::istream_iterator<int>(iss)),
std::istream_iterator<int>());
debug(report.begin(), report.end());
if (seemslegit(report.begin(), report.end())) {
safe++;
std::cout << "\n\n";
continue;
}
for (int i = 0; i < report.size(); ++i) {
auto report2 = report;
auto it = report2.erase(report2.begin()+i);
debug(report2.begin(), report2.end());
if (seemslegit(report2.begin(), report2.end())) {
safe++;
break;
}
}
std::cout << "\n\n";
}
std::cout << safe << std::endl;
}
Commentary
Doing this “efficiently” should be possible. since you only need ~2-ish look-back you should be able to score reports in O(n) time. One complication is you might get the direction wrong, need to consider that erasing one of the first two elements could change the direction. But that requires thinking, and shoving all the permutations into a function with ungodly amounts of copying does not.
re: 2-2
yeah that’s what I ended up thinking. Just try the brute force and if it’s too slow, maybe I’ll try be smarter about it.
Day 5 - Print Queue
day 5
urgh this took me much longer than it should have… part 1 was easy enough but then I got tied up in knots with part 2. Finally I just sorto-bogo-sorted it all into shape
Perl: https://github.com/gustafe/aoc2024/blob/main/d05-Print-Queue.pl
Recheck array size: 98
All rechecks passed after 5938 passes
Duration: 00h00m00s (634.007 ms)
tl;dr: Day 5 was most perfectly fine code thrown out for me, because I ran face first into eliminating imaginary edge cases instead of starting out simple.
5-1 commentary
I went straight into a rabbit hole of doing graph traversal to find all implicit rules (i.e. 1|2, 2|3, 3|4 imply 1|3, 1|4, 2|4) so I could validate updates by making sure all consequent pairs appear in the expanded ruleset. Basically I would depth first search a tree with page numbers for nodes and rules for edges, to get all branches and recombine them to get the full ruleset.
So ideally 1|2, 2|3, 3|4 -> 1|2|3|4 -> 1|2, 2|3, 3|4, 1|3, 1|4, 2|4
Except I forgot the last part and just returned the branch elements pairwise in sequence, which is just the original rules, which I noticed accidentally after the fact since I was getting correct results, because apparently it was completely unnecessary and I was just overthinking myself into several corners at the same time.
5-2 commentary and some code
The obvious cornerstone was the comparison function to reorder the invalid updates, this is what I came up with:
let comparerFactory (ruleset: (int*int) list) :int -> int -> int =
let leftIndex =
ruleset
|> List.groupBy fst
|> List.map (fun (key,grp)-> key, grp |> List.map snd)
|> Map.ofList
fun page1 page2 ->
match (leftIndex |> Map.tryFind page1) with
| Some afterSet when afterSet |> List.contains page2 -> -1
| _ -> 1
The memoization pattern is for caching an index of rules grouped by the before page, so I can sort according to where each part of the comparison appears. I started out with having a second index where the key was the ‘after’ page of the rule which I would check if the page didn’t appear on the left side of any rule, but it turned out I could just return the opposite case, so again unnecessary.
Got stuck forever on 2-2 because of an edge case that only showed up in 7/1000 reports, ended up just brute forcing it, just ran the fitness function after removing one element at a time sequentially.
Then solved 3.x in like minutes because I could be worse at regex, posting code mostly because no-one else posted F# yet.
edited to fix spoiler header formatting
3-2 in F#
"./input.actual"
|> System.IO.File.ReadAllText
|> fun source ->
System.Text.RegularExpressions.Regex.Matches(source, @"don't\(\)|do\(\)|mul\((\d+),(\d+)\)")
|> Seq.fold
(fun (acc, enabled) m ->
match m.Value with
| "don't()" -> acc, false
| "do()" -> acc, true
| mul when enabled && mul.StartsWith("mul") ->
let (x, y) = int m.Groups.[1].Value, int m.Groups.[2].Value
acc + x * y, enabled
| _ -> acc, enabled )
(0, true)
|> fst
|> printfn "The sum of all valid multiplications with respect to do() and don't() is %A"
comments
Not much to say, the regex grabs all relevant strings and the folding function propagates a flag that flips according to do/don’t and an accumulator that is increased when a mul() is encountered and parsed.
It’s that time of the year again. Last year was tough for me, i got laid off in the middle of dec and it kinda killed the vibe. I’ll see how long I keep up this year. My historical backlog is growing but I’ve made peace with it.
Day 3
3-2
I expect much wailing and gnashing of teeth regarding the parsing, which of course is utterly trivial if you know a bit if regex.
I got bit by the input being more than one line. Embarrasing.
I wonder if any input starts with a “don’t()” or if it’s too early for Erik to pull such trickery.
