current difficulties
- Day 21 - Keypad Conundrum: 01h01m23s
- Day 17 - Chronospatial Computer: 44m39s
- Day 15 - Warehouse Woes: 30m00s
- Day 12 - Garden Groups: 17m42s
- Day 20 - Race Condition: 15m58s
- Day 14 - Restroom Redoubt: 15m48s
- Day 09 - Disk Fragmenter: 14m05s
- Day 16 - Reindeer Maze: 13m47s
- Day 22 - Monkey Market: 12m15s
- Day 13 - Claw Contraption: 11m04s
- Day 06 - Guard Gallivant: 08m53s
- Day 08 - Resonant Collinearity: 07m12s
- Day 11 - Plutonian Pebbles: 06m24s
- Day 18 - RAM Run: 05m55s
- Day 04 - Ceres Search: 05m41s
- Day 23 - LAN Party: 05m07s
- Day 02 - Red Nosed Reports: 04m42s
- Day 10 - Hoof It: 04m14s
- Day 07 - Bridge Repair: 03m47s
- Day 05 - Print Queue: 03m43s
- Day 03 - Mull It Over: 03m22s
- Day 19 - Linen Layout: 03m16s
- Day 01 - Historian Hysteria: 02m31s
24! - Crossed Wires - Leaderboard time 01h01m13s (and a close personnal time of 01h09m51s)
Spoilers
I liked this one! It was faster the solve part 2 semi-manually before doing it “programmaticly”, which feels fun.
Way too many lines follow (but gives the option to finding swaps “manually”):
#!/usr/bin/env jq -n -crR -f ( # If solving manually input need --arg swaps # Expected format --arg swaps 'n01-n02,n03-n04' # Trigger start with --arg swaps '0-0' if $ARGS.named.swaps then $ARGS.named.swaps | split(",") | map(split("-") | {(.[0]):.[1]}, {(.[1]):.[0]}) | add else {} end ) as $swaps | [ inputs | select(test("->")) / " " | del(.[3]) ] as $gates | [ # Defining Target Adder Circuit # def pad: "0\(.)"[-2:]; ( [ "x00", "AND", "y00", "c00" ], [ "x00", "XOR", "y00", "z00" ], ( (range(1;45)|pad) as $i | [ "x\($i)", "AND", "y\($i)", "c\($i)" ], [ "x\($i)", "XOR", "y\($i)", "a\($i)" ] ) ), ( ["a01", "AND", "c00", "e01"], ["a01", "XOR", "c00", "z01"], ( (range(2;45) | [. , . -1 | pad]) as [$i,$j] | ["a\($i)", "AND", "s\($j)", "e\($i)"], ["a\($i)", "XOR", "s\($j)", "z\($i)"] ) ), ( ( (range(1;44)|pad) as $i | ["c\($i)", "OR", "e\($i)", "s\($i)"] ), ["c44", "OR", "e44", "z45"] ) ] as $target_circuit | ( # Re-order xi XOR yi wires so that xi comes first # $gates | map(if .[0][0:1] == "y" then [.[2],.[1],.[0],.[3]] end) ) as $gates | # Find swaps, mode=0 is automatic, mode>0 is manual # def find_swaps($gates; $swaps; $mode): $gates as $old | # Swap output wires # ( $gates | map(.[3] |= ($swaps[.] // .)) ) as $gates | # First level: 'x0i AND y0i -> c0i' and 'x0i XOR y0i -> a0i' # # Get candidate wire dict F, with reverse dict R # ( [ $gates[] | select(.[0][0:1] == "x" ) | select(.[0:2] != ["x00", "XOR"] ) | if .[1] == "AND" then { "\(.[3])": "c\(.[0][1:])" } elif .[1] == "XOR" then { "\(.[3])": "a\(.[0][1:])" } else "Unexpected firt level op" | halt_error end ] | add ) as $F | ($F | with_entries({key:.value,value:.key})) as $R | # Replace input and output wires with candidates # ( [ $gates[] | map($F[.] // .) | if .[2] | test("c\\d") then [ .[2],.[1],.[0],.[3] ] end | if .[2] | test("a\\d") then [ .[2],.[1],.[0],.[3] ] end ] # Makes sure that when possible a0i comes 1st, then c0i # ) as $gates | # Second level: use info rich 'c0i OR e0i -> s0i' gates # # Get candidate wire dict S, with reverse dict T # ( [ $gates[] | select((.[0] | test("c\\d")) and .[1] == "OR" ) | {"\(.[2])": "e\(.[0][1:])"}, {"\(.[3])": "s\(.[0][1:])"} ] | add | with_entries(select(.key[0:1] != "z")) ) as $S | ($S | with_entries({key:.value,value:.key})) as $T | ( # Replace input and output wires with candidates # [ $gates[] | map($S[.] // .) ] | sort_by(.[0][0:1]!="x",.) ) as $gates | # Ensure "canonical" order # [ # Diff - our input gates only $gates - $target_circuit | .[] | [ . , map($R[.] // $T[.] // .) ] ] as $g | [ # Diff + target circuit only $target_circuit - $gates | .[] | [ . , map($R[.] // $T[.] // .) ] ] as $c | if $mode > 0 then # Manual mode print current difference # debug("gates", $g[], "target_circuit", $c[]) | if $gates == $target_circuit then $swaps | keys | join(",") # Output successful swaps # else "Difference remaining with target circuit!" | halt_error end else # Automatic mode, recursion end # if $gates == $target_circuit then $swaps | keys | join(",") # Output successful swaps # else [ first( # First case when only output wire is different first( [$g,$c|map(last)] | combinations | select(first[0:3] == last[0:3]) | map(last) | select(all(.[]; test("e\\d")|not)) | select(.[0] != .[1]) | { (.[0]): .[1], (.[1]): .[0] } ), # "Only" case where candidate a0i and c0i are in an # incorrect input location. # Might be more than one for other inputs. first( [ $g[] | select( ((.[0][0] | test("a\\d")) and .[0][1] == "OR") or ((.[0][0] | test("c\\d")) and .[0][1] == "XOR") ) | map(first) ] | if length != 2 then "More a0i-c0i swaps required" | halt_error end | map(last) | select(.[0] != .[1]) | { (.[0]): .[1], (.[1]): .[0] } ) ) ] as [$pair] | if $pair | not then "Unexpected pair match failure!" | halt_error else find_swaps($old; $pair+$swaps; 0) end end end ; find_swaps($gates;$swaps;$swaps|length)
22
uh
pretty straightforward. At least it’s not a grid!
21!
Finally managed to beat this one into submission.
P1
I created this disgusting mess of a recursive search that happened to work. This problem was really hard to think about due to the levels of indirection. It was also hard because of a bug I introduced into my code that would have been easy to debug with more print statements, but hubris.
P2
Recursive solution from P1 was too slow, once I was at 7 robots it was taking minutes to run the code. It didn’t take long to realise that you don’t really care about where the robots other than the keypad robot and the one controlling the keypad robot are since the boundary of each state needs all the previous robots to be on the A button. So with memoisation, you can calculate all the shortest paths for a given robot to each of the directional inputs in constant time, so O(kn) all up where n is the number of robots (25) and k is the complexity of searching for a path over 5 or 11 nodes.
What helped was looking at the penultimate robot’s button choices when moving the keypad robot. After the first one or two levels, the transitions settle into the table in the appendix. I will not explain the code.
appendix
(P(0, 1), P(0, 1)): [], (P(0, 1), P(0, 2)): [btn.r], (P(0, 1), P(1, 0)): [btn.d, btn.l], (P(0, 1), P(1, 1)): [btn.d], (P(0, 1), P(1, 2)): [btn.d, btn.r], (P(0, 2), P(0, 1)): [btn.l], (P(0, 2), P(0, 2)): [], (P(0, 2), P(1, 0)): [btn.d, btn.l, btn.l], (P(0, 2), P(1, 1)): [btn.l, btn.d], (P(0, 2), P(1, 2)): [btn.d], (P(1, 0), P(0, 1)): [btn.r, btn.u], (P(1, 0), P(0, 2)): [btn.r, btn.r, btn.u], (P(1, 0), P(1, 0)): [], (P(1, 0), P(1, 1)): [btn.r], (P(1, 0), P(1, 2)): [btn.r, btn.r], (P(1, 1), P(0, 1)): [btn.u], (P(1, 1), P(0, 2)): [btn.u, btn.r], (P(1, 1), P(1, 0)): [btn.l], (P(1, 1), P(1, 1)): [], (P(1, 1), P(1, 2)): [btn.r], (P(1, 2), P(0, 1)): [btn.l, btn.u], (P(1, 2), P(0, 2)): [btn.u], (P(1, 2), P(1, 0)): [btn.l, btn.l], (P(1, 2), P(1, 1)): [btn.l], (P(1, 2), P(1, 2)): [],
23!
Spoilerific
Got lucky on the max clique in part 2, my solution only works if there are at least 2 nodes in the clique, that only have the clique members as common neighbours.
Ended up reading wikipedia to lift one the Bron-Kerbosch methods:
#!/usr/bin/env jq -n -rR -f reduce ( inputs / "-" # Build connections dictionary # ) as [$a,$b] ({}; .[$a] += [$b] | .[$b] += [$a]) | . as $conn | # Allow Loose max clique check # if $ARGS.named.loose == true then # Only works if there is at least one pair in the max clique # # That only have the clique members in common. # [ # For pairs of connected nodes # ( $conn | keys[] ) as $a | $conn[$a][] as $b | select($a < $b) | # Get the list of nodes in common # [$a,$b] + ($conn[$a] - ($conn[$a]-$conn[$b])) | unique ] # From largest size find the first where all the nodes in common # # are interconnected -> all(connections ⋂ shared == shared) # | sort_by(-length) | first ( .[] | select( . as $cb | [ $cb[] as $c | ( [$c] + $conn[$c] | sort ) | ( . - ( . - $cb) ) | length ] | unique | length == 1 ) ) else # Do strict max clique check # # Example of loose failure: # 0-1 0-2 0-3 0-4 0-5 1-2 1-3 1-4 1-5 # 2-3 2-4 2-5 3-4 3-5 4-5 a-0 a-1 a-2 # a-3 b-2 b-3 b-4 b-5 c-0 c-1 c-4 c-5 def bron_kerbosch1($R; $P; $X; $cliques): if ($P|length) == 0 and ($X|length) == 0 then if ($R|length) > 2 then {cliques: ($cliques + [$R|sort])} end else reduce $P[] as $v ({$R,$P,$X,$cliques}; .cliques = bron_kerbosch1( .R - [$v] + [$v] ; # R ∪ {v} .P - (.P - $conn[$v]); # P ∩ neighbours(v) .X - (.X - $conn[$v]); # X ∩ neighbours(v) .cliques ) .cliques | .P = (.P - [$v]) | # P ∖ {v} .X = (.X - [$v] + [$v]) # X ∪ {v} ) end ; bron_kerbosch1([];$conn|keys;[];[]).cliques | max_by(length) end | join(",") # Output password
23-2
Leaving something to run for 20-30 minutes expecting nothing and actually getting a valid and correct result: new positive feeling unlocked.
Now to find out how I was ideally supposed to solve it.
day 23
this is one of those days when it’s all about the right term to google right