Oct 20, 2026, 3:51 AMThe instruction set consists of a function that divides A by two, and a bunch of XOR ops. There's a jump function that jumps if A is nonzero. Implication: A is like a sort of logarithmic counter; the program whittles away dividing repeatedly by two until A hits zero. It's very clear the number of output digits scales linearly with the number of digits in A.
This means a linear scan is out. After running a pretty long time, my output has 8 digits. My target string has 16.
Oct 20, 2026, 3:56 AMSo even if I'm more efficient and am not waiting on STDOUT, I can't (shouldn't?) count up to 16 digits by hand.
However, I'm *mostly* sure I can do something like a binary search. The XORs mean the output isn't smoothly increasing, but it's increasing on average, so a binary search will get me into the neighborhood, and maybe that'll identify a block of, I dunno, a thousand or a hundred "A" values that I can linearly scan and find my result.
…tomorrow.
Oct 20, 2026, 6:21 AM…okay. I am *completely certain* the correct answer is somewhere between 35,184,372,088,831 and 281,474,976,710,656, noninclusive.
Oct 20, 2026, 6:27 AMI'm laying in bed. I think about how the values in the input/output lists are all in the range 0-7, and wonder if the AOC taskmaster wants us to be thinking of them as an octal number.
I think about "comparing" lists. I realize I don't know which end to compare from. I make a decision. I get up and start doing a *manual* binary search. Why not?
I quickly find the numbers don't behave the way I hoped. Most numbers I pick turn into long strings of 4s, for some reason.
But.
Oct 20, 2026, 6:30 AMTreating my "goal" string as an octal number and looking at it in different bases revealed nothing interesting.
A regular binary search really gets me nowhere. I think: Wait, isn't this math bitwise/logarithmic? I try doing a "binary" search picking midpoints with 10^((log10(a)+log10(b))/2). [block 1 in image above]
That goes better, but not good enough. I quickly get two *broad* endpoints of my range, but can't reduce it further. [block 2 in image above]
But then—
Oct 20, 2026, 6:34 AM[block 3 in image above] I try looking at my input numbers in octal. I *immediately* realize that the number of printed "digits" in the output is exactly equal to the number of digits in my "A register" number represented as base 8. Hence: My answer will be n where
octal 1000000000000000 <= n < octal 7777777777777777. 15 digits.
This is the first concretely useful thing I've worked out so far.
Oct 20, 2026, 6:39 AMI'm unsure what to do next. I still think I need to do some kind of directed search, but maybe instead of thinking about magnitude I measure bit similarity and toggle bits one by one. I imagine implementing this in JS and making 48 checkboxes for input bits I can play with. I imagine my linear scan emitting a Unicode bitmap.
I have until 6 PM tomorrow to meet my one-week deadline.
I worry I'm going to have to *read* the program and figure out what it's *actually doing*.
Oct 20, 2026, 6:52 AMThere's something in the "sinyax" docs titled "Libraries.Utils.Octal". I don't find this in `pack query`, and it isn't in prelude. What is this, and how do I obtain it? It would speed up the thing I think I have to do next.
Oct 20, 2026, 7:18 AMOkay. Here's the commented "decomp" of the program I'm executing.
This is… not so bad. The only particularly "chaotic" step is 2. Critically, all of this math works on only one "octal" digit at a time. Each output "digit" is dependent on a single octal input digit, plus one other, *higher-magnitude* 3-bit slice cmhosen chaotically on step 2.
This means, I think, if I start with the most-significant digit and work "right", each output digit will "lock" and not change again.
![Register A: [THIS IS THE NUMBER I'M TRYING TO FIND]
Register B: 0
Register C: 0
Program:
0 2,4 B = A % 8
1 1,1 B = B xor 1
2 7,5 C = A / (1 << B)
3 1,5 B = B xor 5 [0b101]
4 4,1 B = B xor C
5 5,5 output( B )
6 0,3 A = A / 8
7 3,0 if ( A > 0 ) goto 0](https://files.mastodon.social/media_attachments/files/117/471/964/112/070/436/original/7181ab73b03d7a10.png)
Oct 20, 2026, 7:20 AMThere's a word for this. In cryptanalysis/security. There's a word for a very old type of attack where you're trying to guess a password, but you figure out you can get a confirmation if the first character of the password is correct, so if there are 26 choices for N characters the complexity to guess it is 26*N instead of 26^N. What the heck is that called. The term stopped being used in the 00s because nobody serious has made this mistake since the 1980s.
Oct 20, 2026, 9:29 AMUpdate: Asfgfhsfhdhdf
Oct 20, 2026, 1:38 PMPadding Oracle Attack. That's the term I was looking for. Although rereading the Wikipedia page it looks like I may have been confused about the term, and it may just be an *example* of this attack class rather than a *term* for this attack class.
Oct 20, 2026, 2:13 PMSo here's what I did. I changed my linear scan so instead of just counting up from 0, it takes a list of numbers from STDIN. This allowed me to make a file containing a batch of numbers I want to check all at once (which I filter through perl -e 'while (<>) { last unless /\d/; $_ = oct($_); print "$_\n"; }', since I never figured out how to access the documented octal support library in Idris). This lets me test every leftmost digit, every one-right-of-leftmost digit, etc…
Oct 20, 2026, 2:17 PM…I can test as many candidate numbers as I want at once and see the results in bulk. I do this to (see images above) find the correct digit one octal at a time left to right, each octal input digit matching one more digit in the output list.
This works great until my number suddenly "forks". On the 8th (1-indexed) digit, either 1 or 5 produces a matching result. So after that point, instead of testing 8 at a go I'm testing 16, simultaneously testing "world 1" and "world 5".
Oct 20, 2026, 2:20 PMThis isn't so bad either except the forking *continues*; I'm quickly testing 3 parallel worlds, then one dies off. I basically manage until I hit digit 14 of 16, which turns out to have **six** different next options. I sort of do my best from there and eventually find a number: 165523097481149 (octal 4550533133267675).
It's wrong. It's too high. There are apparently multiple correct solutions, and AOC guy (so says the problem solution) wants the *lowest*. Which I fumbled.
Oct 20, 2026, 2:22 PMNow that I've done the process by hand, though, I have a pretty good understanding of what it looks like, so now I'm in a much better position to automate this process, with the automation presumably not making whatever mistake my fallable human brain made to miss the true-lowest possibility.
I now believe I *could* finish this puzzle by my self-imposed deadline, but maybe I won't, since I got 1.5 hours of sleep last night and I'm leaving to go to the doctor. Uh… now.
Oct 20, 2026, 9:08 PMOkay. I have the architecture for the search program that will find my "part 2" solution clearly in mind, I am certain it will work, I have the "type-driven development" scaffold of it written down in a file, and this is just me commemorating that I *could have* finished this in the next ~2 hours before I hit the one week anniversary of this thread but I decided it was more important to lay down and sleep.
Oct 21, 2026, 12:23 AMAlright. Idris question. Do you just have like… a for loop. Hiding in this language somewhere. Yes I know how to do a loop with recursion. But you've already *got* monads/"do" and sometimes it's just true that the most semantically efficient way to communicate something is "for i in 1 to 8" or whatever. You seem to have range() . I think so anyway. I've thought I found things in the stdlib before and been wrong. https://idris2docs.sinyax.net/data/papers/docs/Data.Enumerate.html#Data.Enumerate.Enumerator
You didn't document "if" so maye you didn't document "for"
Oct 21, 2026, 1:16 AMIf this were scheme or ocaml I'm pretty sure I could do what i'm doing with zip or other pointfree combinators but unfortunately Idris's most Haskell-like quality is the documentation believes that giving the type of a function is sufficient for a reader to understand what it is the arguments do
Oct 21, 2026, 1:55 PMCurrently drowning in a never-ending chain of writing basic "case" or "if" statements and getting unintelligible errors like "expected =>" on a => or "expected end of expression". Trying to not run to Mastodon for help on every one. Did encounter one thing that seems so actionable I'm considering filing it:
Why are members of the sequence "0..7" not Fin 8?
![let new = for [0..7] (\i => shiftL (the Bits64 1) (cast i))
"cast i" is highlighted saying that i (0..7) is an integer and "cast i" needs a Fin 64](https://files.mastodon.social/media_attachments/files/117/479/226/319/701/575/original/3558a17cd05a3caf.png)
@mcc really
Oct 20, 2026, 6:27 AM@joeswills Yes. I'm certain.
@mcc so how will you find out the answer
Oct 20, 2026, 6:30 AM@joeswills Not sure yet
@mcc smile 😊
@mcc I don't recall the term, but it has cropped up more recently than that. One of the original BLE pairing methods was vulnerable to this sort of incremental attack.
Oct 20, 2026, 7:37 AM@swetland Tremendous
@mcc TVTropes calls this the Password Slot Machine
https://tvtropes.org/pmwiki/pmwiki.php/Main/PasswordSlotMachine
@mcc I think it's a "crib"
Looks like you work with the program 2,4,1,1,7,5,1,5,4,1,5,5,0,3,3,0 for which 0o4550533133267675 actually is a solution.
But AOC (https://adventofcode.com/2024/day/17/input) uses the program 2,4,1,2,7,5,1,7,4,4,0,3,5,5,3,0
Oct 20, 2026, 3:55 PM@hcschuetz first off, I'd appreciate answers being behind spoiler tags!
Second off every AOC participant gets individualized inputs specifically to prevent answer sharing like this.
@mcc
I hope my previous post didn't spoiler too much. After all you already had this number.
And thanks for the hint about individualized inputs. Wasn't aware of this.
@mcc there's a for and for_ function in the prelude. the difference is that for_ doesn't care about the output from traversing the data structure (returns m () for a monad m) but for does (like map with side effects). probably for_ is what you want. https://idris2docs.sinyax.net/data/prelude/docs/Prelude.Interfaces.html#Prelude.Interfaces.for_
also you can do range comprehensions [ 1 .. 8 ] to get a range list: https://idris2.readthedocs.io/en/latest/tutorial/typesfuns.html#list-comprehensions
so it should be something like,
for_ [ 1 .. 8 ] $ \i => do
... something with i ...
Oct 21, 2026, 2:29 AM@typeswitch hey that rules, thank you
Oct 21, 2026, 3:13 AM@mcc @typeswitch there's a meme in Haskell, "it's always `traverse`", because `traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)` is useful for a lot of different things with the right choices of `f` and `t`. (in this case `f = IO`, `t = List`, and `for_ xs f = void (traverse f xs)`)
Oct 21, 2026, 3:22 AM@zmz @typeswitch gonna be honest i'd never encountered traverse before this project but i got *really* excited when i started to understand it. i'm still not sure i understand it
@mcc because i doesn't know anything about what list was given, all it knows is that it's an Integer
you probably want
allFins 8 for all the numbers in Fin 8iterateN to apply (fun x => shiftL x FZ) on l eight times and collect the intermediate results in a list@mcc maybe using https://idris2docs.sinyax.net/data/prelude/docs/Prelude.Interfaces.html#Prelude.Interfaces.for like for [1..8] (\i => ...)
(the list comprehension syntax is noted here https://idris2.readthedocs.io/en/latest/tutorial/typesfuns.html#list-comprehensions although it's unclear whether the endpoints are inclusive lol)
@mcc as it happens that page is also where if is documented
Oct 21, 2026, 3:10 AM@ionchy thank you much
@mcc because I am catching up on my feed a day late, I had to check the timestamp to see if this keysmash was still about the problem you were working on or if it was about private key = 4
either way I'm counting this thread as dramatic irony for real life
Oct 21, 2026, 1:21 PM@InfiniteNutshell Ironically I actually could have finished this last night within my deadline but I was too busy updating my servers for PHP and "4"
@mcc I was going to say padding oracle, but then that didn't sound quite right... Some sort of oracle... or side-channel if it's timing based?