zogwarg

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)

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

Massive time gains with parallelization + optimized next function (2x speedup) by doing the 3 xor operation in "one operation", Maybe I prefer the grids ^^:

#!/usr/bin/env jq -n -f

#────────────────── Big-endian to_bits ───────────────────#
def to_bits:
  if . == 0 then [0] else { a: ., b: [] } | until (.a == 0;
      .a /= 2 |
      if .a == (.a|floor) then .b += [0]
                          else .b += [1] end | .a |= floor
  ) | .b end;
#────────────────── Big-endian from_bits ────────────────────────#
def from_bits: [ range(length) as $i | .[$i] * pow(2; $i) ] | add;

( # Get index that contribute to next xor operation.
  def xor_index(a;b): [a, b] | transpose | map(add);
  [ range(24) | [.] ]
  | xor_index([range(6) | [-1]] + .[0:18] ; .[0:24])
  | xor_index(.[5:29] ; .[0:24])
  | xor_index([range(11) | [-1]] + .[0:13]; .[0:24])
  | map(
      sort | . as $indices | map(
        select( . as $i |
          $i >= 0 and ($indices|indices($i)|length) % 2 == 1
        )
      )
    )
) as $next_ind |

# Optimized Next, doing XOR of indices simultaneously a 2x speedup #
def next: . as $in | $next_ind | map( [ $in[.[]] // 0 ] | add % 2 );

#  Still slow, because of from_bits  #
def to_price($p): $p | from_bits % 10;

# Option to run in parallel using xargs, Eg:
#
# seq 0 9 | \
# xargs -P 10 -n 1 -I {} bash -c './2024/jq/22-b.jq input.txt \
# --argjson s 10 --argjson i {} > out-{}.json'
# cat out-*.json | ./2024/jq/22-b.jq --argjson group true
# rm out-*.json
#
# Speedup from naive ~50m -> ~1m
def parallel: if $ARGS.named.s and $ARGS.named.i  then
   select(.key % $ARGS.named.s == $ARGS.named.i)  else . end;

#════════════════════════════ X-GROUP ═══════════════════════════════#
if $ARGS.named.group then

# Group results from parallel run #
reduce inputs as $dic ({}; reduce (
      $dic|to_entries[]
  ) as {key: $k, value: $v} (.; .[$k] += $v )
)

else

#════════════════════════════ X-BATCH ═══════════════════════════════#
reduce (
  [ inputs ] | to_entries[] | parallel
) as { value: $in } ({};  debug($in) |
  reduce range(2000) as $_ (
    .curr = ($in|to_bits) | .p = to_price(.curr) | .d = [];
    .curr |= next | to_price(.curr) as $p
    | .d = (.d+[$p-.p])[-4:]  | .p = $p # Four differences to price
    | if .a["\($in)"]["\(.d)"]|not then # Record first price
         .a["\($in)"]["\(.d)"] = $p end # For input x 4_diff
  )
)

# Summarize expected bananas per 4_diff sequence #
| [ .a[] | to_entries[] ]
| group_by(.key)
| map({key: .[0].key, value: ([.[].value]|add)})
| from_entries

end |

#═══════════════════════════ X-FINALLY ══════════════════════════════#
if $ARGS.named.s | not then

#     Output maximum expexted bananas      #
to_entries | max_by(.value) | debug | .value

end

#!/usr/bin/env jq -n -rR -f

#─────────── Big-endian to_bits and from_bits ────────────#
def to_bits:
  if . == 0 then [0] else { a: ., b: [] } | until (.a == 0;
      .a /= 2 |
      if .a == (.a|floor) then .b += [0]
                          else .b += [1] end | .a |= floor
  ) | .b end;
def from_bits:
  { a: 0, b: ., l: length, i: 0 } | until (.i == .l;
    .a += .b[.i] * pow(2;.i) | .i += 1
  ) | .a;
#──────────── Big-endian xor returns integer ─────────────#
def xor(a;b): [a, b] | transpose | map(add%2) | from_bits ;

[ inputs | scan("\\d+") | tonumber ] | .[3:] |= [.]
| . as [$A,$B,$C,$pgrm] |


# Assert  #
if  [first(
        range(8) as $x |
        range(8) as $y |
        range(8) as $_ |
        [
          [2,4],  # B = A mod 8            # Zi
          [1,$x], # B = B xor x            # = A[i*3:][0:3] xor x
          [7,5],  # C = A << B (w/ B < 8)  # = A(i*3;3) xor x
          [1,$y], # B = B xor y            # Out[i]
          [0,3],  # A << 3                 # = A(i*3+Zi;3) xor y
          [4,$_], # B = B xor C            #               xor Zi
          [5,5],  # Output B mod 8         #
          [3,0]   # Loop while A > 0       # A(i*3;3) = Out[i]
        ] | select(flatten == $pgrm)       #         xor A(i*3+Zi;3)
      )] == []                             #         xor constant
then "Reverse-engineering doesn't neccessarily apply!" | halt_error
 end |

#  When minimizing higher bits first, which should always produce   #
# the final part of the program, we can recursively add lower bits  #
#          Since they are always stricly dependent on a             #
#                  xor of Output x high bits                        #

def run($A):
  # $A is now always a bit array                    #
  #                 ┌──i is our shift offset for A  #
  { p: 0, $A,$B,$C, i: 0} | until ($pgrm[.p] == null;

    $pgrm[.p:.p+2] as [$op, $x]       | # Op & literal operand
    [0,1,2,3,.A,.B,.C,null][$x] as $y | # Op &  combo  operand

    # From analysis all XOR operations can be limited to 3 bits  #
    # Op == 2 B is only read from A                              #
    # Op == 5 Output is only from B (mod should not be required) #
      if $op == 0 then .i += $y
    elif $op == 1 then .B = xor(.B|to_bits[0:3]; $x|to_bits[0:3])
    elif $op == 2
     and $x == 4  then .B = (.A[.i:.i+3] | from_bits)
    elif $op == 3
     and (.A[.i:]|from_bits) != 0
                  then .p = ($x - 2)
    elif $op == 3 then .
    elif $op == 4 then .B = xor(.B|to_bits[0:3]; .C|to_bits[0:3])
    elif $op == 5 then .out += [ $y % 8 ]
    elif $op == 6 then .B = (.A[.i+$y:][0:3] | from_bits)
    elif $op == 7 then .C = (.A[.i+$y:][0:3] | from_bits)
    else "Unexpected op and x: \({$op,$x})" | halt_error
    end | .p += 2
  ) | .out;

[ { A: [], i: 0 } | recurse (
    #  Keep all candidate A that produce the end of the program,  #
    #  since not all will have valid low-bits for earlier parts.  #
    .A = ([0,1]|combinations(6)) + .A | # Prepend all 6bit combos #
    select(run(.A) == $pgrm[-.i*2-2:] ) # Match pgrm from end 2x2 #
    | .i += 1
    # Keep only the full program matches, and convert back to int #
  ) | select(.i == ($pgrm|length/2)) | .A | from_bits
]

| min # From all valid self-replicating intputs output the lowest #