2·
21 hours ago23!
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
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)