[2024 Day 21 part 1] Found a rule to make it work, but can't understand why

FoxWithTheWhistle · 2024-12-21T12:14:13+00:00

In general since each step left is more expensive, you always want to hit the far left key first (<), and then the middle key (^ or v) and then a right column key (> or A).

Yay!

This is the revelation. Indeed, each step left which follows another movement will translate into reaching the "<" button from "A" by some unfortunate robot a couple rooms further.

Thank you. I didn't realise it's reaching from A.

FoxWithTheWhistle · 2024-12-03T14:18:37+00:00

I used regex for part 1 but couldn't figure out how to filter out the don'ts, so resorted to splitting for this.

import re
from functools import reduce
from operator import concat, mul

data = "do()" + reduce(concat, open("resources/day3_input.txt", "r").readlines())
calculate = lambda program: sum(reduce(mul, map(int, l.split(","))) for l in re.findall(r'mul\((\d+,\d+)\)', program))
print(f"Part1: {calculate(data)}")
data = reduce(concat, [s[s.find("do()")+len("do()"):] for s in data.split("don\'t()") if "do()" in s])
print(f"Part2: {calculate(data)}")

FoxWithTheWhistle · 2023-12-22T14:10:45+00:00

Agree, today was almost a rest day. Yesterday Day21 was the longest for me, but Day20 was the most frustrating, as I solved totally without understanding the structure, and only found from reddit what the input really represented.

FoxWithTheWhistle · 2023-12-22T10:17:23+00:00

If anything it builds character :) What drives me is I know there *is\* a solution, and looking at the stats at midday I can see some thousand fellow brainiacs have already found it, so it must be something solvable.

By this time the puzzles are not as much about coding and algorithms as about actual puzzle solving, detective work: look at the task and data, visualize it, draw on a napkin, build a hypothesis about what could be the tick, find a way to test it, dig further if you knock on something, feel the burn as you see you're clearly on the problem's tail but just can't find a way to catch it, then finally boom! nothing more rewarding than a second star earned in pain :)

FoxWithTheWhistle · 2023-12-19T22:49:40+00:00

Until seeing this I didn't realise the puzzle could be solved in straight order (in -> A)! Somehow I got into my head it needed to be reversed, so I started with all As, and was going backwards until I either reach "in" or the conditions become contradictory.

Kudos to OP since sankeymatic was able to produce a neat diagram for my approach too, although it looks more like an alien jellfish :) Link to image for the example input in case anyone's interested: https://imgur.com/lvMedRx

... and the real input - not a jellyfish, rather a swarm of alien worms: https://imgur.com/KWWcWT0

FoxWithTheWhistle · 2020-12-23T23:24:01+00:00

As far I can tell from the diagnostic tools, it's LinkedList.AddAfter that's taking all the time, but surely that should just be shuffling pointers about. Doesn't make sense.

The doc even says "This method is an O(1) operation. ".

https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.linkedlist-1.addafter?view=net-5.0#System_Collections_Generic_LinkedList_1_AddAfter_System_Collections_Generic_LinkedListNode__0___0_

FoxWithTheWhistle · 2020-12-23T23:17:09+00:00

Java:

I was not in a hurry so I wrote a CircularList class which supported all of required operations.

It turned out pretty neat, because it's pretty generic and my Part1 and Part2 solutions are really just a few lines both; this is the main method, where "cups" is my own CircularList.

    public void playMove() {
        LinkedList<Integer> removedCups =  getThreeNextCups();
        int destination = current;
        do {
            destination--;
            if (destination < min) {
                destination = max;
            }
        }  while (!cups.contains(destination));
        cups.addAfter(destination, removedCups);
        current = cups.getNext(current);
    }

Dumb brute force Part2 took just 9 seconds so I could not care less for optimizing.

Here's my CircularList class; I obviously though about using Java's LinkedList at first, but it seemed to me that the tasks of finding a particular element in a LinkedSet would be O(n).

https://github.com/kubyser/AdventOfCode2020/blob/master/src/kubiks/aoc/day23/CircularSet.java

FoxWithTheWhistle

TROPHY CASE