I never ran into the part 1 issue with the cycles due to being too lazy to look for any smart solution. I am reasonably sure my input has the same issue. Everyone’s probably has. In part 1 you only need t check the state not do anything about it, and so I did that and nothing more.
uu.sort_by(|a, b| {
let mut order = Ordering::Equal;
if let Some(ah) = priorities.get(&a) {
if ah.contains(&b) {
order = Ordering::Less;
}
}
if let Some(bh) = priorities.get(&b) {
if bh.contains(&a) {
order = Ordering::Greater;
}
}
order
});
I agree; I’d be very surprised if that particular thing is only sometimes present.
Perl doesn’t have sets. Obviously anything you can do with a set you can do with a hash (dict, map), just ignore the values. But oh boy I miss them when I’ve been writing in a set-ful language and have to go back to Perl.
That was fun. I’m kinda surprised my approach didn’t get completely invalidated by part2 because I expected the usual “okay, now do it at a much higher magnitude”.
Part 2:
The sample showed only single re-orderings, but I didn’t know if the actual input data would require multiple re-arrangements, so I did an iterative approach and just swapped pages with their precedent, iteratively, until the pages were in sufficient order.
I considered doing a more holistic “sort the whole thing” but was afraid that the middle term may be ambiguous if you took that approach
Day 6 part one was pretty easy. Again using my classes from last two years to easily traverse the matrix giving directions as I go. This is me profiting from making classes that fit a lot of the AoC puzzles well. I like it when my code… tells a story? This is the beauty of object orientation (sometimes)
I am giving up on part 2 of this stupid thing.
I was going to have a restful week-end and I am not.
I can’t even do the brute force solution -.- and I spend about 6 hours on this today. My equals and hashcode work. I checked. This same algorithm works for part 1:
List<Coordinates> steps = new ArrayList<>();
while (warehouse.isInTheMatrix(guard)) {
//getValue now returns default value if the coordinates are outside of the matrix
if (warehouse.getValue(guard.moveToNext(),-1) == OBSTACLE) {
guard.setFacing(guard.getFacing().turnRight());
}
//where has the guard been:
steps.add(guard);
guard = guard.moveToNext();
if(steps.contains(guard)){
throw new IllegalStateException("Cycle detected");
}
}
My friend spottet this and I also saw on reddit, I saw that I had broken something i previously fixed: keep turning until there is no obstacle, only then move.
Someone on mastodon pointed out that I needed to make sure that the spot had not previously been visited when playing an obstacle. I wasn’t starting the guard at the OG starting point for each cycle check.
My brute force solution for part 2 is not as brute force as I thought it was. I have two optimisations in it:
only check for cycles on obstacles because that is where they happen and the checking in the set is far more expensive than traversing the matrix. This is a speedup of factor 50 or so 400ms vs 26seconds. This one I did more or less on purpose
do not start the guard at the beginning but only just at the step where the obstacle is placed. I have no idea how much that does as I said traversal is cheap. but for later cycles a lot more obstacles will be tested so I assume this also provides quite a bit of speedup. I did this “accidentally”
The latter really stumped me and kept me from a solution. I was sure I was brute forcing when I was not.
And for Day 7… part 1 very straightforward, switching to Long now from Integer (yeah, java makes Integer more comfortable and the default) … I implemented both solving from the first element or from the last element. My partner insisted that it would be faster solving from the first element. I don’t think it matters and my brain insisted backwards was the way to go.
Part 2: I am solving the test input for the new operator no problem. Unit tests discovered a single (irrelevant) mistake but the result I am getting (and I am testing for Long overflow but we’re a good 3 factors away from that today) a result that is “too low”… so I am missing a concatenation edge case for the that I just can’t figure out. I think today I try to be smarter than yesterday and take a break.
Away for the weekend, but Rust integers are explicitly sized: there have been times when the main code change from part 1 to 2 was replacing u32 with u64.
Part 2… reddit actually helped with memes. The hybris that I thought I could use math … but now I solved both parts both with math and without, forward and backward, including some BigInteger / Long.MAX_VALUE checks because you never know…
took longer (38.8 seconds instead of 37.2 seconds) (with unnecessary terminal output because I could)
gave a different result?
One optimization I did make while working on part2 that I didn’t bother with on part1 was to check if the first value was larger than the test value, since the operators provided only make numbers bigger and never smaller; so as I worked left-to-right iteratively, I discarded any branches that were already too large
~ Day 8 ~
Part 1: fiddly. I wrote a “mirror” function for coordinates.
Part 2: ?!? I am not sure I am reading the problem description right. This is a discreet coordinate system. “on a line” must mean either vertical, horizontal or diagonal… everything else is not going to work correct?
Had to go to reddit to understand the problem description of part 2…and I still don’t.
Had AI Assistant explain it to me and nothing about this makes sense anymore.
I think even though this is early days… I am noping out of this one.
part 1: dy = b.y - a.y; dx = b.x - a.x; n1 = (a.x - dx, a.y - dy); n2 = (b.x + dx, b.y + dy) so simple, why bother with equation for the line of two points
part 2:
Sure is. A competition I tried to work on decades ago had a problem that could be attacked naively. I set that running, and after a week it was still going. I thought of a better way, coded that up, and saw that it was running, then started to think about optimisation. I was interrupted by the answer, which had only taken a few minutes.
That’s usually my strategy AoC. Write the naïve approach and then work on optimizations/alternate approaches up until one of the previous attempts returns a result.
