Ancestors

Written by gerikson@awful.systems on 2024-12-23 at 13:21

Advent of Code 2024 - the home stretch - it's been an aMAZEing year

https://awful.systems/post/3123248

=> More informations about this toot | More toots from gerikson@awful.systems

Written by zogwarg@awful.systems on 2024-12-23 at 16:02

23!

SpoilerificGot 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

=> More informations about this toot | More toots from zogwarg@awful.systems

Toot

Written by Architeuthis@awful.systems on 2024-12-24 at 00:29

23-2Leaving something to run for 20-30 minutes and actually getting a valid and correct result: new positive feeling unlocked.

Now to find out how I was actually supposed to solve it.

=> More informations about this toot | More toots from Architeuthis@awful.systems

Descendants