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.
22!
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.
Also 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 #
Definitely 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.
Ok 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.
Day 14, got very lucky on this one, but too tired to think about why part 2 still worked.
#!/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:
I liked day 13, a bit easy but in the right way.
Edit:
Although 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.
If you somehow wanted your whole final array it would also required over 1 Peta byte ^^, memoization definetely reccomended.
Day 11
Some hacking required to make JQ work on part 2 for this one.
#!/usr/bin/env jq -n -f
last(limit(1+25;
[inputs] | recurse(map(
if . == 0 then 1 elif (tostring | length%2 == 1) then .*2024 else
tostring | .[:length/2], .[length/2:] | tonumber
end
))
)|length)
#!/usr/bin/env jq -n -f
reduce (inputs|[.,0]) as [$n,$d] ({}; debug({$n,$d,result}) |
def next($n;$d): # Get next # n: number, d: depth #
if $d == 75 then 1
elif $n == 0 then [1 ,($d+1)]
elif ($n|tostring|length%2) == 1 then [($n * 2024),($d+1)]
else # Two new numbers when number of digits is even #
$n|tostring| .[0:length/2], .[length/2:] | [tonumber,$d+1]
end;
# Push onto call stack #
.call = [[$n,$d,[next($n;$d)]], "break"] |
last(label $out | foreach range(1e9) as $_ (.;
# until/while will blow up recursion #
# Using last-foreach-break pattern #
if .call[0] == "break" then break $out
elif
all( # If all next calls are memoized #
.call[0][2][] as $next
| .memo["\($next)"] or ($next|type=="number"); .
)
then
.memo["\(.call[0][0:2])"] = ([ # #
.call[0][2][] as $next # Memoize result #
| .memo["\($next)"] // $next # #
] | add ) | .call = .call[1:] # Pop call stack #
else
# Push non-memoized results onto call stack #
reduce .call[0][2][] as [$n,$d] (.;
.call = [[$n,$d, [next($n;$d)]]] + .call
)
end
))
# Output final sum from items at depth 0
| .result = .result + .memo["\([$n,0])"]
) | .result
I remember being quite ticked off by her takes about free will, and specifically severly misrepresenting compatibilism and calling philosphers stupid for coming up with the idea.
One look day 9 and I had to leave it until after work (puzzles unlock at 2PM for me), it wasn’t THAT hard, but I had to leave it until later.
Day 8
Al lot of grid index shuffling these past few days! Not too difficult yet though, will this year be gentler or much harsher later?
#!/usr/bin/env jq -n -R -f
[ inputs / "" ] | [.,.[0]|length] as [$H,$W] |
#----- In bound selectors -----#
def x: select(. >= 0 and . < $W);
def y: select(. >= 0 and . < $H);
reduce (
[
to_entries[] | .key as $y | .value |
to_entries[] | .key as $x | .value |
[ [$x,$y],. ] | select(last!=".")
] | group_by(last)[] # Every antenna pair #
| combinations(2) | select(first < last)
) as [[[$ax,$ay]],[[$bx,$by]]] ({};
# Assign linear anti-nodes #
.[ range(-$H;$H) as $i | "\(
[($ax+$i*($ax-$bx)|x), ($ay+$i*($ay-$by)|y)] | select(length==2)
)"] = true
) | length
Day 3 well suited to JQ
#!/usr/bin/env jq -n -R -f
reduce (
inputs | scan("do\\(\\)|don't\\(\\)|mul\\(\\d+,\\d+\\)")
| [[scan("(do(n't)?)")[0]], [ scan("\\d+") | tonumber]]
) as [[$do], [$a,$b]] (
{ do: true, s: 0 };
if $do == "do" then .do = true
elif $do then .do = false
elif .do then .s = .s + $a * $b end
) | .s
I think that particular talking point also serves an exculpatory purpose: “If it was only a razor-thin victory I might understand being angry with me, but see it’s a decisive victory. He has the mandate of heaven of the people (this is a Trumpian victory! not a Democrat failure!) ! It would be wrong not to congratulate him!”
It’s also incredibly misleading, maybe it was possible to “completely” re-write the UI back in 2005—never mind that most of the value would come from, the underlying geographic data being mostly correct and mostly correctly labeled—there is no way in hell that the same would achievable in 2024. (Also the notion it would take any coder 2 * 1000 / (365 * 5/7) =
7 years to achieve a comparable result is proposterous)
As long as no-one ever bakes—pluginlessly—LLMs into vanilla vim
(or into normal nano
) I won’t despair too much.
Not surprised, still very disappointed, I feel sick.
Why hasn’t he attempted to make a robotic owl yet? Poser…
To be “fair” kubernetes api only supports strongly validated/typed YAML-ish input…, it won’t let you put non-string values in string locations. And in reality at the HTTP api layer—at least for kubectl—json is used. (Which also means you cant’ do the more weird occult YAML things that JSON wouldn’t let you)
You have to blame the deep-nestedness of k8s resources for unreadability…
I was also a Elon skeptic back-then, but I’ll admit I did get a kick out of the “don’t panic” dashboard.
But golly does he read H2G2 completely wrong (transcript):
I think and it highlighted an important point which is that a lot of times the question is harder than the answer. And if you can properly phrase the question, then the answer is the easy part. So, to the degree that we can better understand the universe, then we can better know what questions to ask. Then whatever the question is that most approximates: what’s the meaning of life? That’s the question we can ultimately get closer to understanding. And so I thought to the degree that we can expand the scope and scale of consciousness and knowledge, then that would be a good thing.
It’s backwards! It misses the joke! It took thousands of years and they got a nonsensical answer before any question! It took a thousand more and they got a nonsensical—incompatible—question! It has been theorized that should someone understand the universe it would be replaced by something more complicated! It has also been theorized this has already happened! Also regarding scale of knowledge, Trin Tragula definetly showed that the One thing you can’t afford to have in this universe, is a sense of perspective!
Surely his reading comprehension isn’t actually this bad, and he only got a bad meme-cliffnotes version of the radio-series/books/movies!?!
Hacky Manual parallelization
22-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