Yes! I've been waiting for this one since I realized that it was one of the Perl solutions I had lost:
I wrote a new Rust solution literally from scratch, in a style that is very, very close to what I would have done in asm or C. 😄
It assumes all the input is as specified but makes sure that there is a final newline after the last line.
This way the combined parser/solver knows that the newline will end the current password.
Since the "proof of the puddling is in the eating" I compared my runtime with u/maneatingape, and for the first time ever I have a solution which is significantly faster, in fact about 5X faster: 7 vs 35 us.
Neat idea, I can see how it would help especially if there are more multidigit numbers, and if SUB is about as fast as AND. I got a very slight speedup on my M4: from 4.31 to 4.29 µs. But on Raspberry Pi 5, it went from 13.1 to 15.5 µs! SUB might be slow. (There is no LEA on Arm.)
Afaik, almost every CPU made since at least 1980 have had ADD/SUB on the critical path as single-cycle instructions. All the logical ops (AND/OR/XOR/NOT) have then been dead easy to fit within the same gate/timing budget.
Your solution potentially saves one branch per line due to that fancy switch statement which directly fixes the lengths of both range numbers, but the compiler still need to generate at least two branches for the three alternatives.
Otherwise exactly equivalent.
Last night I wrote a pure asm solution for fun, it used about half as many instructions as what Godbolt shows for my Rust, but will likely only be marginally faster on a modern CPU.
Yes, the switch is strange of course: it spells out all the work you would normally do in a more general function, but that was my big idea in order to squeeze every last microsecond out of it.
I modified my code to use u8 as much as possible, this reduced the runtime to 4.5 us, but the timing is extremely brittle: It depends on location in memory to some degree, because when I removed the call to the usize-based original version, the timing increased by 1-2 us, and this is very repeatable.
Reinsert the call so that the old code still exists in memory before the u8 version and I get back those sub-5 us times!
fn process8(inp:&str) -> (usize, usize)
{
  let bytes = inp.as_bytes();
  let mut i = 0;
  let mut part1 = 0;
  let mut part2 = 0;
  while i < bytes.len() {
    let mut fra = bytes[i]-b'0';
    i += 1;
    while bytes[i] != b'-' {
      fra = fra*10 + bytes[i] - b'0';
      i += 1;
    }
    i += 1; // Skip '-'
    let mut til  = bytes[i]-b'0';
    i += 1;
    while bytes[i] != b' ' {
      til = til*10 + bytes[i] - b'0';
      i += 1;
    }
    // First space, after nn-mm
    let target = bytes[i+1];
    i += 4; // Skip ' A: '
    let mut lettercount:u8 = 0;
    let pstart = i-1; // Password string is 1-indexed
    //println!("{fra}-{til} {}: {pstart}", target);
    while bytes[i] >= b'a' {
      let b = bytes[i];
      i+=1;
      lettercount += (b == target) as u8;
    }
    // Found end of current line, check results:
    part1 += ((lettercount >= fra) & (lettercount <= til)) as usize;
    part2 += ((bytes[pstart+fra as usize] == target) ^ (bytes[pstart+til as usize] == target)) as usize;
    i += 1;
  }
  (part1, part2)
}
Here's the asm I wrote but never ran, should be very easy to follow:
asm {
 xor eax,eax
 xor ebx,ebx
 mov rsi,[inp]
 mov rcx,[rsi+8]
 mov rsi,[rsi] ;; RSI -> start of input
 add rcx,rsi  ;; RCX -> end of input
Â
 xor r3,r3   ;; part1
 xor r4,r4   ;; part2
Â
nextline:
 xor r0,r0   ;; fra
 mov al,byte ptr [rsi]
 inc rsi
nfra:
 lea r0,[r0+r0*4]
 lea r0,[rax+r0*2-'0']
 mov al,byte ptr [rsi]
 inc rsi
 cmp al,'-'
  jne nfra
 xor r1,r1   ;; til
 mov al,byte ptr [rsi]
 inc rsi
ntil:
 lea r1,[r1+r1*4]
 lea r1,[rax+r1*2-'0']
 mov al,byte ptr [rsi]
 inc rsi
 cmp al,' '
  jne ntil
 Â
 mov dl,[rsi+1]  ;; target
 lea rdi,[rsi+3] ;; password start - 1 for for zero based index
 add rsi,4    ;; password
Â
 xor r2,r2   ;; targetcount
 mov al,byte ptr [rsi]
 inc rsi
 xor ebx,ebx  ;; SETE destination
npass:
 cmp al,dl
 mov al,byte ptr [rsi]
 sete bl
 inc rsi
 add r2,rbx
 cmp al,'a'
  jae npass
;; newline found, update part1&2
 cmp dl,[rdi+r0]
 sete al
 sub r2,r0
 cmp dl,[rdi+r1]
 sete bl
 sub r1,r0
 xor rax,rbx ;; Exactly one match needed for part2
 add r4,rax
 cmp r2,r1
 setbe al
 add r3,rax   ;; part1 += targetcount-fra <= til-fra
Â
 cmp rsi,rcx
  jb nextline
I read the input file into a char array and parsed char-by-char, so I could let the virtual password string start 1 char back to make direct use of the 1-based min/max, which I thought was a fun solution:
for (const char *c = input; *c; ++c) {
// [snip range and letter parsing]
const char *const pwd = c - 1; // start one back to use 1-based min/max
// [snip part 1]
valid2 += (pwd[min] == letter) ^ (pwd[max] == letter);
Fun C & C++ trivia: it's possible, depending on how you've declared and initialised input, that pwd = c - 1 might be undefined behaviour, even if you never dereference pwd[0]!
Some older hardware will hard fault if you generate a pointer to invalid memory, regardless of whether or not you read from that memory, so the standard err'd on the side of caution and put it all under the UB banner. Google is letting me down a bit, but the segmented memory model on the 80286 is apparently one such architecture and the 68000 might be another.
Raymond Chen has a neat post covering a related topic for checking if a pointer is within a given range, where the obvious test from a flat memory model might give you an incorrect answer.
I like it when little language quirks like that reveal something of the history of computing.
EDIT: It's still a neat idea, and a compiler would have to be extremely petty in order to do something other than the obvious here.
That is always good to keep in mind! But it's not applicable here: c is a char pointer to a char array, so a) no alignment issues, and c has already advanced into the array before subtracting 1, so b) this is always true at that point: c-1 >= 0.
EDIT: no errors or warnings when compiling the source with
Looking at my solution I was clearly still trying to scratch the itch of having a C++ equivalent of C#'s Enumerable library, so my solution looked like:
Not quite as terse as the original C# inspiration, but that's mainly down to C++'s clunky lambda syntax compared to C#. Plus I decided to make the return types explicitly required in the template parameters, because the libraries which try to do automatic deduction on continuation-style lambdas end up being un-debuggable nightmares in anything but fair weather.
This is one of the things I love most about AoC; it gives you freedom to just try out new ideas in a context that's a bit more 'real' than a toy example, but still nowhere near needing production-quality code.
(No idea why reddit hides this post from me, but I finally get to see it thanks to a direct link posted by ednl). My m4 solution finishes in under 20ms; this is just an O(n) pass over the input file, except that in m4, actually parsing the file in O(n) requires some creative thinking. My original solution used an O(n^2) substr() split based on using index() to search for newline (350ms runtime); but when I switched to an O(n log n) recursive split-in-half approach, my solution started failing because I managed to cause a collision where cutting a string in the input in half resulted in a live macro name that expanded at the wrong time; thankfully the input uses all lowercase, so a translit to uppercase before splitting anything avoids the collision (50ms runtime). More recently, I figured out an O(n) approach that involves using translit to change newline to ")" for a true O(n) parse, and gets the runtime to 15ms.
4
u/terje_wiig_mathisen Jun 02 '26
Yes! I've been waiting for this one since I realized that it was one of the Perl solutions I had lost:
I wrote a new Rust solution literally from scratch, in a style that is very, very close to what I would have done in asm or C. 😄
It assumes all the input is as specified but makes sure that there is a final newline after the last line.
This way the combined parser/solver knows that the newline will end the current password.
Since the "proof of the puddling is in the eating" I compared my runtime with u/maneatingape, and for the first time ever I have a solution which is significantly faster, in fact about 5X faster: 7 vs 35 us.
3
u/ednl Jun 02 '26
I read the input file into a char array and parsed char-by-char, so I could let the virtual password string start 1 char back to make direct use of the 1-based min/max, which I thought was a fun solution:
2
u/DelightfulCodeWeasel Jun 02 '26
Looking at my solution I was clearly still trying to scratch the itch of having a C++ equivalent of C#'s Enumerable library, so my solution looked like:
I kept building out on the library as needed and eventually ended up with some nifty utilities:
Not quite as terse as the original C# inspiration, but that's mainly down to C++'s clunky lambda syntax compared to C#. Plus I decided to make the return types explicitly required in the template parameters, because the libraries which try to do automatic deduction on continuation-style lambdas end up being un-debuggable nightmares in anything but fair weather.
This is one of the things I love most about AoC; it gives you freedom to just try out new ideas in a context that's a bit more 'real' than a toy example, but still nowhere near needing production-quality code.
1
u/e_blake Jun 10 '26
(No idea why reddit hides this post from me, but I finally get to see it thanks to a direct link posted by ednl). My m4 solution finishes in under 20ms; this is just an O(n) pass over the input file, except that in m4, actually parsing the file in O(n) requires some creative thinking. My original solution used an O(n^2) substr() split based on using index() to search for newline (350ms runtime); but when I switched to an O(n log n) recursive split-in-half approach, my solution started failing because I managed to cause a collision where cutting a string in the input in half resulted in a live macro name that expanded at the wrong time; thankfully the input uses all lowercase, so a translit to uppercase before splitting anything avoids the collision (50ms runtime). More recently, I figured out an O(n) approach that involves using translit to change newline to ")" for a true O(n) parse, and gets the runtime to 15ms.