zogwarg

joined 2 years ago
[–] [email protected] 2 points 12 hours ago

And done! well I had fun.

[–] [email protected] 3 points 1 day ago* (last edited 1 day ago) (1 children)

24! - Crossed Wires - Leaderboard time 01h01m13s (and a close personal time of 01h09m51s)

SpoilersI 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)

[–] [email protected] 2 points 2 days ago (3 children)

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

[–] [email protected] 1 points 2 days ago

That's still mostly what it is ^^, though I'd say it's more "awk+sed" for JSON.

[–] [email protected] 2 points 3 days ago* (last edited 3 days ago) (2 children)

Hacky Manual parallelization22-b.jq

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

[–] [email protected] 1 points 3 days ago (5 children)

22!

spoilers!Well it’s not a grid! My chosen language does not have bitwise operators so it’s a bit slow. Have to resort to manual parallelization.

[–] [email protected] 3 points 1 week ago* (last edited 1 week ago)

EDIT: I have a sneaking suspicion that the computer will need to be re-used since the combo-operand 7 does not occur and is "reserved".

re p2Also did this by hand to get my precious gold star, but then actually went back and implemented it Some JQ extension required:

#!/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 #

[–] [email protected] 2 points 1 week ago

Re: p2Definitely a bit tedious, I had to "play" a whole session to spot bugs that I had. It took me far longer than average. I had buggy dissepearing boxes because of update order, I would reccomend a basic test case of pushing a line/pyramid of boxes in every direction.

[–] [email protected] 1 points 1 week ago (1 children)

Updated ReasoningOk it probably works because it isn't bang center but a bit up of center, most other steps most be half half noise vertically, and the reason it doesn;t minimize on an earlier horizontal step (where every step is mostly half half), is because the middle points on the trunk, that don't contribute to the overall product therefore minimizing it even lower.

[–] [email protected] 3 points 1 week ago (5 children)

Day 14, got very lucky on this one, but too tired to think about why part 2 still worked.

spoiler

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

#     Board size     # Our list of robots positions and speed #
[101,103] as [$W,$H] | [ inputs | [scan("-?\\d+")|tonumber] ] |

#     Making the assumption that the easter egg occurs when   #
#           When the quandrant product is minimized           #
def sig:
  reduce .[] as [$x,$y] ([];
    if $x < ($W/2|floor) and $y < ($H/2|floor) then
      .[0] += 1
    elif $x < ($W/2|floor) and $y > ($H/2|floor) then
      .[1] += 1
    elif $x > ($W/2|floor) and $y < ($H/2|floor) then
      .[2] += 1
    elif $x > ($W/2|floor) and $y > ($H/2|floor) then
      .[3] += 1
    end
  ) | .[0] * .[1] * .[2] * .[3];

#           Only checking for up to W * H seconds             #
#   There might be more clever things to do, to first check   #
#       vertical and horizontal alignement separately         #
reduce range($W*$H) as $s ({ b: ., bmin: ., min: sig, smin: 0};
  .b |= (map(.[2:4] as $v | .[0:2] |= (
    [.,[$W,$H],$v] | transpose | map(add) 
    | .[0] %= $W | .[1] %= $H
  ))) 
  | (.b|sig) as $sig |
  if $sig < .min then
    .min = $sig | .bmin = .b | .smin = $s 
  end | debug($s)
)

| debug(
  #    Contrary to original hypothesis that the easter egg    #
  #  happens in one of the quandrants, it occurs almost bang  #
  # in the center, but this is still somehow the min product  #       
  reduce .bmin[] as [$x,$y] ([range($H)| [range($W)| " "]];
    .[$y][$x] = "█"
  ) |
  .[] | add
)

| .smin + 1 # Our easter egg step

And a bonus tree:

[–] [email protected] 3 points 1 week ago* (last edited 1 week ago) (1 children)

I liked day 13, a bit easy but in the right way.

Edit:

SpoilersAlthough saying "minimum" was a bit evil when all of the systems had exactly 1 solution (not necessarily in ℕ^2), I wonder if it's puzzle trickiness, anti-LLM (and unfortunate non comp-sci souls) trickiness or if the puzzle was maybe scaled down from a version where there are more solutions.

[–] [email protected] 3 points 2 weeks ago* (last edited 2 weeks ago) (1 children)

re:followupIf you somehow wanted your whole final array it would also require over 1 Peta byte ^^, memoization definetely reccomended.

 

Need to let loose a primal scream without collecting footnotes first? Have a sneer percolating in your system but not enough time/energy to make a whole post about it? Go forth and be mid: Welcome to the Stubsack, your first port of call for learning fresh Awful you’ll near-instantly regret.

Any awful.systems sub may be subsneered in this subthread, techtakes or no.

If your sneer seems higher quality than you thought, feel free to cut’n’paste it into its own post — there’s no quota for posting and the bar really isn’t that high.

The post Xitter web has spawned soo many “esoteric” right wing freaks, but there’s no appropriate sneer-space for them. I’m talking redscare-ish, reality challenged “culture critics” who write about everything but understand nothing. I’m talking about reply-guys who make the same 6 tweets about the same 3 subjects. They’re inescapable at this point, yet I don’t see them mocked (as much as they should be)

Like, there was one dude a while back who insisted that women couldn’t be surgeons because they didn’t believe in the moon or in stars? I think each and every one of these guys is uniquely fucked up and if I can’t escape them, I would love to sneer at them.

(Semi-obligatory thanks to @dgerard for starting this)

view more: next ›