Day 5

Previous: Day 04 | Next: Day 06

(spoiler: YOU DON’T NEED TO BINARY SEARCH A BINARY NUMBER TO FIND OUT WHAT NUMBER IT IS. THERE’S SOMETHING THAT CAN DO THAT FOR YOU, IT’S CALLED print(num))
(…banert…?)

###AUTO-ACQUIRED DATA FOLLOWS…
archivist/day05-1.c
archivist/day05-1.c
\#include <stdio.h>
    \#include <stdlib.h>
    \#include <string.h>
    
    \#define PLANE\_LENGTH 128
    \#define PLANE\_WIDTH 8
    
    int blookup(int min,int max, char \* code, int n\_splits){
        for(int i = 0; i < n\_splits; i++){
            if(code[i]==&\#39;B&\#39; || code[i]==&\#39;R&\#39;) 
                min = (min+max)/2+1;
            if(code[i]==&\#39;F&\#39; || code[i]==&\#39;L&\#39;) 
                max = (min+max)/2;
        }
        //printf("min %d, max %d\n", min, max);
        return min;
    };
    
    int main (int argc, char\*\*argv){
        int  length = 0;
        FILE \*f = fopen(argv[1], "r");
        char \*input;
        if (!f) return -1; 
        fseek(f, 0, SEEK\_END);
        length = ftell(f);
        rewind(f);
        input = (char\*)malloc(sizeof(char) \* (length+1));
        fread(input, sizeof(char), length, f);
        //printf("length is %d\n", length);
        fclose(f);
        ((char\*)input)[length] = &\#39;\0&\#39;;
    
        int biggest\_possible\_id = (0 + 8\*127+7);
        printf("Biggest possible ID: %d\n", biggest\_possible\_id);
        int biggest\_id = 0;
        char \* line = 0;
        while((line = strsep(&input, "\n"))!= NULL){
            if(strlen(line) == 0) break;
            int row = 0;
            int column = 0;
            int id = 0;
            //printf("%s\n", line);
            //boarding seat code is 10 chars long
            row = blookup(0, PLANE\_LENGTH-1, line,7);
            column = blookup(0, PLANE\_WIDTH-1, line+7,3);
            id=row\*8+column;
            //printf("Row %d, Column %d, ID %d\n", row, column, id);
            if(id>biggest\_id) biggest\_id=id;
        }
            printf("Biggest ID so far: %d\n", biggest\_id);
        
        return 0;
    }
    
archivist/day05-2.c
archivist/day05-2.c
\#include <stdio.h>
    \#include <stdlib.h>
    \#include <string.h>
    
    \#define PLANE\_LENGTH 128
    \#define PLANE\_WIDTH 8
    
    int compare(const void\* a, const void\* b){
        return (\*(int \*)a < \*(int \*)b) ? -1 : 1;
        return 0;
    }
    
    int blookup(int min,int max, char \* code, int n\_splits){
        for(int i = 0; i < n\_splits; i++){
            if(code[i]==&\#39;B&\#39; || code[i]==&\#39;R&\#39;) 
                min = (min+max)/2+1;
            if(code[i]==&\#39;F&\#39; || code[i]==&\#39;L&\#39;) 
                max = (min+max)/2;
        }
        //printf("min %d, max %d\n", min, max);
        return min;
    };
    
    int main (int argc, char\*\*argv){
        int  length = 0;
        FILE \*f = fopen(argv[1], "r");
        char \*input;
        if (!f) return -1; 
        fseek(f, 0, SEEK\_END);
        length = ftell(f); rewind(f);
        input = (char\*)malloc(sizeof(char) \* (length+1));
        fread(input, sizeof(char), length, f);
        fclose(f);
        ((char\*)input)[length] = &\#39;\0&\#39;;
        int n\_lines = 0;
        for(int i = 0; i < length; i++){
            if(input[i] == &\#39;\n&\#39;)
                n\_lines++;
        }
    
        printf("no. of lines: %d\n", n\_lines);
        int \* idlist = malloc(sizeof(int)\*n\_lines);
    
        int list\_index = 0;
        char \* line = 0;
        while((line = strsep(&input, "\n"))!= NULL){
            if(strlen(line) == 0) break;
            int row = 0;
            int column = 0;
            int id = 0;
            row = blookup(0, PLANE\_LENGTH-1, line,7);
            column = blookup(0, PLANE\_WIDTH-1, line+7,3);
            id=row\*8+column;
            idlist[list\_index++] = id;
        }
        qsort(idlist, n\_lines, sizeof(int), &compare);
        for(int i = 0; i < n\_lines-1; i++){
            if ((idlist[i+1]-idlist[i]) > 1){
                printf("ID between %d and %d\n", idlist[i], idlist[i+1]);
                printf("My ID is %d\n", idlist[i]+1);
            }
        }
        return 0;
    }
    
day-5/day05-part-1-ada.adb
day-5/day05-part-1-ada.adb
with Ada.Text\_IO; use Ada.Text\_IO;
    with Ada.Strings.Maps;
    with Ada.Strings.Fixed;
    
    procedure Index is
        type Seats\_Raw is array (1 .. 839) of String (1 .. 10);
        type Seats\_Array is array (1 .. 839) of Integer;
    
        File : File\_Type;
        File\_Name : constant String := "input.txt";
        Index : Integer := 1;
    
        Input : Seats\_Raw;
        Row : Integer;
        Column : Integer;
        Seats : Seats\_Array;
    
        function ReplaceBits (Item : String) return String is
        begin
            return Ada.Strings.Fixed.Translate(
                Source => Item,
                Mapping => Ada.Strings.Maps.To\_Mapping(From => "FBLR", To => "0101")
            );
        end ReplaceBits;
    
        function ConvertBase2 (Item : String) return Integer is
            Result : Integer;
            Multiplier : Integer;
        begin
            Result := 0;
            Multiplier := 1;
    
            for I in reverse Item&\#39;Range loop
                if Item (I) = &\#39;1&\#39; then
                    Result := Result + Multiplier;
                end if;
    
                Multiplier := Multiplier \* 2;
            end loop;
    
            return Result;
        end ConvertBase2;
    
        function Get\_Maximum (Seats : Seats\_Array) return Integer is
           Maximum : Integer := Seats (Seats&\#39;First);
        begin
           for I in Seats&\#39;First + 1 .. Seats&\#39;Last loop
              if Seats (I) > Maximum then
                 Maximum := Seats (I);
              end if;
           end loop;
           return Maximum;
        end Get\_Maximum;
    begin
        Open(File, In\_File, File\_Name);
    
        Index := 1;
        while not End\_Of\_File (File) loop
            Input (Index) := Get\_Line (File);
            Index := Index + 1;
        end loop;
    
        Close (File);
    
        Index := 1;
        for Item of Input loop
            Row := ConvertBase2 (ReplaceBits (Item (Item&\#39;first .. 7)));
            Column := ConvertBase2 (ReplaceBits (Item (8 .. Item&\#39;last)));
            Seats (Index) := Row \* 8 + Column;
            Index := Index + 1;
        end loop;
    
        Put\_Line (Get\_Maximum (Seats)&\#39;Img);
    end Index;
    
deutschanon/deutschanon-day05.c
deutschanon/deutschanon-day05.c
\#include <stdio.h>
    \#include <stdlib.h>
    
    int main(int argc, char\*\* argv){
        char pass[10];
        int max = 0;
        int id = 0;
        char c = 0;
        char flugzeug[128][8];
        FILE \*input;
        if(argc < 2){
            input = fopen("input.txt","r");
        }else{
            input = fopen(argv[1],"r");
        }
    
        for(int i = 0;i < 128;i++){
            for(int j = 0; j < 8;j++){
                flugzeug[i][j] = &\#39;.&\#39;;
            }
        }
    
        int i = 0;
        while((c = getc(input)) != EOF){
            if(c != &\#39;\n&\#39;){
                if(c == &\#39;B&\#39;) c = 1;
                if(c == &\#39;F&\#39;) c = 0;
                if(c == &\#39;L&\#39;) c = 0;
                if(c == &\#39;R&\#39;) c = 1; 
                pass[i] = c;
                i++;
            }else{
                i = 0;
                int reihe = 0;
                int spalte = 0;
                for(int j = 0; j < 7; j++){
                    if(pass[j]){ reihe = reihe + (128 >> j+1);}
                }
                for(int j = 7; j < 10; j++){
                    if(pass[j]){spalte = spalte + (8 >> (j-6));}
                }
                id = reihe \* 8 + spalte;
                if(id > max){ max = id;}
                flugzeug[reihe][spalte] = &\#39;\#&\#39;;
            }
        }
        printf("P1: %d\n",max);
        int sitz = 0;
        int folge = 0;
        for(int i = 0; i < 128; i++){
            for(int j = 0; j < 8;j++){
                if(flugzeug[i][j] == &\#39;.&\#39; && folge == 1 && flugzeug[i+1][(j+1)%8] == &\#39;\#&\#39;){
                    sitz = i\*8+j;
                    folge = 0;
                    //i = 128;
                    printf("P2: %d\n",sitz);
                }
                if(flugzeug[i][j] == &\#39;\#&\#39;) folge = 1;
            }
        }
        fclose(input);
        return 0;
    }
    
jsanon/javascript-day05.js
jsanon/javascript-day05.js
\#!/usr/bin/env node
    &\#39;use strict&\#39;;
    
    const { exit, argv } = require(&\#39;process&\#39;);
    const readInput = require(&\#39;../lib/read-input.js&\#39;);
    
    // We only care about the ID,
    // which looks something like [0-127] \* 8 + col.
    // Where [0-127] is effectively a bit field for the first 7bits.
    //
    // When encountering a &\#39;B&\#39; value, we just have to shift on a 1.
    // When we encounter a &\#39;F&\#39; value, we just shift on a 0 at the end.
    // We do this 7 times til the first B/F value is in the 7th position.
    //
    // the \* 8 mearly is the same as (field << 3) padding the 7 bits into a field of 10
    // Thus the first shifted on value is now in the 10th, with the first three being 0
    // making the value 10bit.
    // Because of this, we can just repeat the same process for the remaining 3 specifiers.
    // Again, the actual Row/Col is unnecessary.
    //
    // the + col is the remainder 3 bits
    // Same rules, but instead of &\#39;B&\#39;, we use &\#39;R&\#39; and for &\#39;F&\#39; we use &\#39;L&\#39;
    function getSeatId(pass)
    {
        if (pass.length !== 10) throw Error(&\#39;Assert: Value is too small/big.&\#39;);
    
        let id = 0;
        for (let i = 0; i < 10; ++i)
        {
            // we pretend the string is valid and ignore F/L altogether...
            id = (id << 1) + (pass[i] === &\#39;B&\#39; || pass[i] === &\#39;R&\#39;);
        }
        return id;
    }
    
    async function main([ part, inputFile ])
    {
        const input = (await readInput(inputFile /\* stdin = undefined \*/))
            .split(&\#39;\n&\#39;);
    
        console.time(`Day-5: ${part}`);
        let max = -1;
        const seats = new Set();
        for (const boarding of input)
        {
            const id = getSeatId(boarding);
            seats.add(id);
            if (id > max) max = id;
        }
        if (part === &\#39;part-1&\#39;)
        {
            console.timeEnd(`Day-5: ${part}`);
            console.log(`Max Seat ID: ${max}`);
        }
        else if (part === &\#39;part-2&\#39;)
        {
            let mySeat = max;
            for (const s of seats)
            {
                if (seats.has(s - 1) && !seats.has(s - 2) && seats.has(s - 3))
                {
                    mySeat = s - 2;
                    break;
                }
                else if (seats.has(s + 1) && !seats.has(s + 2) && seats.has(s + 3))
                {
                    mySeat = s + 2;
                    break;
                }
            }
            console.timeEnd(`Day-5: ${part}`);
            console.log(`My Seat ID: ${mySeat}`);
        }
        else
        {
            console.timeEnd(`Day-5: ${part}`);
            throw Error(&\#39;Must be part-1 or part-2.&\#39;);
        }
    }
    
    main(argv.slice(2)).catch(err =>
    {
        console.error(err);
        exit(1);
    });
    
milkanon/assembly-day05-1.s
milkanon/assembly-day05-1.s
 .text
    
        .global \_start
        .type \_start, @function
        
        .set SYS\_READ, 0
        /\* SYS\_OPEN:
    rdi:  int fd
    rsi:  char \*buffer
    rdx:  size\_t count
      \*/
        
        .set SYS\_OPEN, 2
        /\* SYS\_OPEN:
    rdi:  const char \*filename
    rsi:  int flags
    rdx:  int mode
      \*/
        
        .set SYS\_EXIT, 60
        /\* SYS\_EXIT:
    rdi:  int exitcode
      \*/
        
        .set O\_RDONLY, 0
    \_start:
        movq   %rsp, %rbp
    
        // Open input file
        movq $SYS\_OPEN, %rax
        movq $filename, %rdi
        movq $O\_RDONLY, %rsi
        movq $0600, %rdx
        syscall
    
        // We should have the fd in `rax`. Store it.
        movq %rax, fd
    
    .Lread\_seat\_entry:
        // Read 11 bytes.
        movq $SYS\_READ, %rax
        movq fd, %rdi
        movq $buffer, %rsi
        movq $BUFFER\_SIZE, %rdx
        syscall
    
        // `rax` returns the number of bytes read, or negative for
        // error.
        cmp    $0, %rax
        je .Lread\_all\_ok
    
        // At this point, `buffer` looks like
        //     (gdb) p \*((char [11] \*)$rsi)
        //     $1 = "FFBBBFBLRL\n"
        
        // Get the row index of `buffer` string specifier
        call   get\_row
        // Save it before it gets clobbered
        push   %rax
        // Now get the row index
        call   get\_col
        // Restore rax, use (rax, rbx) as (row, col) tuple
        mov    %rax, %rbx
        pop    %rax
    
        // Mark this seat as occupied in the `taken\_tab`
        call   mark\_taken
    
        // Also calculate and store the id for this seat in `id\_tab`
        call   store\_id
    
        jmp    .Lread\_seat\_entry
    
    .Lread\_all\_ok:
        // Get the max id for Silver
        call   get\_max\_id
        push   %rax
        mov    $silver\_str, %rax
        call   print\_string
        
        pop    %rax
        call   print\_number
    
        // Exit program
        movq   $SYS\_EXIT, %rax
        movq   $0, %rdi
        syscall
    
        .size \_start, .-\_start
    
    
        .section .data
        
        /\* Utility symbols \*/
        .set WIDTH, 8
        .set HEIGHT, 128
    
        /\* File descriptor \*/
    fd:
        .quad 0
        
        /\* Table whether or not seat is taken. \*/
        .align 8
    taken\_tab:
        .zero 8 \* (8 \* WIDTH \* HEIGHT)
    
        /\* Table of seat ids \*/
        .align 8
    id\_tab:   
        .zero 8 \* (8 \* WIDTH \* HEIGHT)
    
        .set BUFFER\_SIZE, 11
    buffer:
        // 7 bytes for the column string (e.g. "FFBFFBF")
        .byte 0
        .byte 0
        .byte 0
        .byte 0
        .byte 0
        .byte 0
        .byte 0
        
        // 3 bytes for the row string (e.g. "LRL")
        .byte 0
        .byte 0
        .byte 0
        
        // 1 byte for the newline
        .byte 0
    
        .section .rodata
    silver\_str:
        .asciz "Silver star answer: "
    
    filename:
        .asciz "input.txt"
    
        /\* Lookup table for the "BFBBBFB"-to-binary conversion \*/
    bintab\_row:
        .quad 64
        .quad 32
        .quad 16
        .quad 8
        .quad 4
        .quad 2
        .quad 1
        
        /\* Lookup table for the "LRL"-to-binary conversion \*/
    bintab\_col:
        /\* Due to the way the lookups happen, we need to offset these
      abit forward to account for how the fact that the row
      specifier appears at the end of the string. This just makes
      indexing more easier elsewhere in the code. \*/
        .quad 0
        .quad 0
        .quad 0
        .quad 0
        .quad 0
        .quad 0
        .quad 0
        
        .quad 4
        .quad 2
        .quad 1
        
        
        /\* Helper routines \*/
        .section .text
        
        /\* size\_t get\_row(void): Get row of string spec in `buffer`. \*/
        .global get\_row
        .type get\_row, @function
        
        /\* size\_t get\_col(void): Get col of string spec in `buffer`. \*/
        .global get\_col
        .type get\_col, @function
    
        /\* void mark\_taken(size\_t row, size\_t col): Set corresponding
      seat location to &\#39;1&\#39; in `taken\_tab`.
          rax - row
          rbx - col
      \*/
        .global mark\_taken
        .type mark\_taken, @function
    
        /\* void store\_id(size\_t row, size\_t col): Set corresponding
      seat location to the seat id in `id\_tab`.
          rax - row
          rbx - col
      \*/
        .global store\_id
        .type store\_id, @function
    
        .global get\_max\_id
        .type get\_max\_id, @function
    
        .global print\_silver
        .type print\_silver, @function
    
        .global print\_string
        .type print\_string, @function
    
        .global strlen
        .type strlen, @function
    
    strlen:
        push   %rbx
        push   %rsi
        
        mov    %rax, %rsi
        mov    $0, %rbx
    
    .Lstrlen\_loop:
        mov    (%rsi, %rbx, 1), %al
        cmp    $0, %al
        je .Lstrlen\_done
    
        inc    %rbx
        jmp    .Lstrlen\_loop
        
    .Lstrlen\_done:
        mov    %rbx, %rax
    
        pop    %rsi
        pop    %rbx
    
        ret
    
    print\_string:
        push   %rax
        push   %rcx
        push   %rsi
        push   %rdi
    
        call   strlen
        mov    %rax, %rdx
    
        movq   $1, %rax
        movq   $1, %rdi
        movq   24(%rsp), %rsi
        syscall
    
        pop    %rdi
        pop    %rsi
        pop    %rcx
        pop    %rax
    
        ret
    
        .size print\_string, .-print\_string
    
    print\_number:
        // I need a bit of scratch memory space cos i need
        // to give sys\_write an address to a buffer
        push   %rbp
        movq   %rsp, %rbp
        
        // number to print
        push   %rax
        // index
        push   %rbx
        push   %rcx
        push   %rdx
    
        // We need to zero terminate it cos `print\_string`
        // will be scanning for it until we get the zero
        // so $10 (MAXINT="42945967295") + $2 ("\n\0") = $12
        sub    $12, %rsp
        movb   $&\#39;\n&\#39;, 10(%rsp)
        movb   $0, 11(%rsp)
        
        movq   $9, %rbx
        movq   $10, %rcx
    
    .Lprint\_number\_loop:
        cltd
        idiv   %ecx
        
        add    $0x30, %dl
        mov    %dl, (%rsp, %rbx, 1)
    
        cmp    $0, %rbx
        je .Lprint\_number\_done
    
        dec    %rbx
        jmp    .Lprint\_number\_loop
    .Lprint\_number\_done:
    
        mov    %rsp, %rax
        call   print\_string
    
        add    $12, %rsp
        
        pop    %rdx
        pop    %rcx
        pop    %rbx
        pop    %rax
    
        pop    %rbp
        ret
    
    print\_silver:
        
    
        .size print\_silver, .-print\_silver
    
    get\_max\_id:
        push   %rbx
    
        push   %rdx
        push   %rsi
        push   %rdi
    
        /\* Pointer to `taken\_tab` table \*/
        movq   $taken\_tab, %rsi
        /\* Pointer to `id\_tab` table \*/
        movq   $id\_tab, %rdi
        /\* Index \*/
        movq   $0, %rdx
        /\* Running max \*/
        movq   $0, %rbx
    
    .Lget\_max\_id\_loop:
        /\* load the taken variable for this seat \*/
        movq   (%rsi, %rdx, 8), %rax
        
        /\* if its 0, it is not taken, and therefore we skip it. \*/
        cmp    $0, %rax
        je .Lget\_max\_id\_skip
    
        /\* load the id for this seat \*/
        movq   (%rdi, %rdx, 8), %rax
    
        cmp    %rax, %rbx
        cmovc  %rax, %rbx
        
    .Lget\_max\_id\_skip:
        inc    %rdx
        cmp    $(128 \* 8), %rdx
        jl .Lget\_max\_id\_loop
    
        mov    %rbx, %rax
    
        pop    %rdi
        pop    %rsi
        pop    %rdx
        
        pop    %rbx
    
        ret
    
        .size get\_max\_id, .-get\_max\_id
    
    store\_id:
        push   %rax
        push   %rbx
        push   %rcx
        push   %rdi
    
        // calculate id
        imul   $8, %rax
        add    %rbx, %rax
        
        // store it in rcx
        mov    %rax, %rcx
    
        // restore rax
        mov    24(%rsp), %rax
    
        // calculate row memory location
        movq   $id\_tab, %rdi
        imul   $(8 \* 8), %rax
        add    %rax, %rdi
        
        // add column offset
        imul   $8, %rbx
        add    %rbx, %rdi
    
        // store id in rcx to slot in id\_tab
        movq   %rcx, (%rdi)
    
        pop    %rdi
        pop    %rcx
        pop    %rbx
        pop    %rax
    
        ret
    
        .size store\_id, .-store\_id
    
    mark\_taken:
        push   %rax
        push   %rbx
        push   %rcx
        push   %rdi
    
        // calculate id
        imul   $8, %rax
        add    %rbx, %rax
        
        // store it in rcx
        mov    %rax, %rcx
    
        // restore rax
        mov    24(%rsp), %rax
    
        // calculate row memory location
        movq   $taken\_tab, %rdi
        imul   $(8 \* 8), %rax
        add    %rax, %rdi
        
        // add column offset
        imul   $8, %rbx
        add    %rbx, %rdi
    
        // store presence in rcx to slot in id\_tab
        movq   $1, (%rdi)
    
        pop    %rdi
        pop    %rcx
        pop    %rbx
        pop    %rax
    
        ret
    
        .size mark\_taken, .-mark\_taken
        
    get\_row:
        push   %rbx
        push   %rcx
        push   %rdx
        push   %rsi
        push   %rdi
        push   %r8
    
        /\* zero-register for cmov below \*/
        movq   $0, %rbx
        /\* input buffer, e.g. "FFBBFFBLRL\n" \*/
        movq   $buffer, %rsi
        /\* lookup table for (2 \* %ecx) \*/
        movq   $bintab\_row, %rdi
        /\* index \*/
        movq   $0, %rcx
    
        /\* r8 will contain the row number \*/
        movq   $0, %r8
        
    .Lget\_row\_loop:  
        /\* Load in this seat (&\#39;F&\#39; or &\#39;B&\#39; into eax) \*/
        mov    (%rsi, %rcx, 1), %eax
        
        /\* Load in the value of this bit \*/
        movq   (%rdi, %rcx, 8), %rdx
        
        /\* I use a trick here: Notice that &\#39;F&\#39; = 0x46, and &\#39;B&\#39; =
      0x42. Hence, if we subtract &\#39;B&\#39;, we get either zero or
      non-zero.  Then, we can use `cmov` on the zero flag to move in
      the addend. \*/
        cmp    $0x42, %al
        cmovnz %rbx, %rdx
        add    %rdx, %r8
    
        inc    %rcx
        cmp    $7, %rcx
        jl .Lget\_row\_loop
    
    .Lget\_row\_done:
        mov    %r8, %rax
    
        pop    %r8
        pop    %rdi
        pop    %rsi
        pop    %rdx
        pop    %rcx
        pop    %rbx
    
        ret
    
        .size get\_row, .-get\_row
    
    get\_col:
        push   %rbx
        push   %rcx
        push   %rdx
        push   %rsi
        push   %rdi
        push   %r8
    
        /\* zero-register for cmov below \*/
        movq   $0, %rbx
        /\* input buffer, e.g. "FFBBFFBLRL\n" \*/
        movq   $buffer, %rsi
        /\* lookup table for (2 \* %ecx) \*/
        movq   $bintab\_col, %rdi
        /\* index (NOTE! We start at 7) \*/
        movq   $7, %rcx
    
        /\* r8 will contain the col number \*/
        movq   $0, %r8
        
    .Lget\_col\_loop:  
        /\* Load in this seat (&\#39;F&\#39; or &\#39;B&\#39; into eax) \*/
        mov    (%rsi, %rcx, 1), %eax
        
        /\* Load in the value of this bit \*/
        movq   (%rdi, %rcx, 8), %rdx
        
        /\* I use a trick here: Notice that &\#39;L&\#39; = 0x4C, and &\#39;R&\#39; =
      0x52. Hence, if we subtract &\#39;L&\#39;, we get either zero or
      non-zero.  Then, we can use `cmov` on the zero flag to move in
      the addend. \*/
        cmp    $0x4C, %al
        cmovz  %rbx, %rdx
        add    %rdx, %r8
    
        inc    %rcx
        cmp    $10, %rcx
        jl .Lget\_col\_loop
    
    .Lget\_col\_done:
        mov    %r8, %rax
    
        pop    %r8
        pop    %rdi
        pop    %rsi
        pop    %rdx
        pop    %rcx
        pop    %rbx
    
        ret
    
        .size get\_col, .-get\_col
    
milkanon/assembly-day05-2.s
milkanon/assembly-day05-2.s
 .text
    
        .global \_start
        .type \_start, @function
        
        .set SYS\_READ, 0
        /\* SYS\_OPEN:
    rdi:  int fd
    rsi:  char \*buffer
    rdx:  size\_t count
      \*/
        
        .set SYS\_OPEN, 2
        /\* SYS\_OPEN:
    rdi:  const char \*filename
    rsi:  int flags
    rdx:  int mode
      \*/
        
        .set SYS\_EXIT, 60
        /\* SYS\_EXIT:
    rdi:  int exitcode
      \*/
        
        .set O\_RDONLY, 0
    \_start:
        movq   %rsp, %rbp
    
        // Open input file
        movq $SYS\_OPEN, %rax
        movq $filename, %rdi
        movq $O\_RDONLY, %rsi
        movq $0600, %rdx
        syscall
    
        // We should have the fd in `rax`. Store it.
        movq %rax, fd
    
    .Lread\_seat\_entry:
        // Read 11 bytes.
        movq $SYS\_READ, %rax
        movq fd, %rdi
        movq $buffer, %rsi
        movq $BUFFER\_SIZE, %rdx
        syscall
    
        // `rax` returns the number of bytes read, or negative for
        // error.
        cmp    $0, %rax
        je .Lread\_all\_ok
    
        // At this point, `buffer` looks like
        //     (gdb) p \*((char [11] \*)$rsi)
        //     $1 = "FFBBBFBLRL\n"
        
        // Get the row index of `buffer` string specifier
        call   get\_row
        // Save it before it gets clobbered
        push   %rax
        // Now get the row index
        call   get\_col
        // Restore rax, use (rax, rbx) as (row, col) tuple
        mov    %rax, %rbx
        pop    %rax
    
        // Mark this seat as occupied in the `taken\_tab`
        call   mark\_taken
    
        // Also calculate and store the id for this seat in `id\_tab`
        call   store\_id
    
        jmp    .Lread\_seat\_entry
    
    .Lread\_all\_ok:
        // Get the max id for Silver
        call   get\_max\_id
        push   %rax
        mov    $silver\_str, %rax
        call   print\_string
        
        pop    %rax
        call   print\_number
    
        // Get our seat id for Gold
        call   find\_empty\_seat\_id
        push   %rax
        mov    $gold\_str, %rax
        call   print\_string
    
        pop    %rax
        call   print\_number
    
        // Exit program
        movq   $SYS\_EXIT, %rax
        movq   $0, %rdi
        syscall
    
        .size \_start, .-\_start
    
    
        .section .data
        
        /\* Utility symbols \*/
        .set WIDTH, 8
        .set HEIGHT, 128
    
        /\* File descriptor \*/
    fd:
        .quad 0
        
        /\* Table whether or not seat is taken. \*/
        .align 8
    taken\_tab:
        .zero 8 \* (8 \* WIDTH \* HEIGHT)
    
        /\* Table of seat ids \*/
        .align 8
    id\_tab:   
        .zero 8 \* (8 \* WIDTH \* HEIGHT)
    
        .set BUFFER\_SIZE, 11
    buffer:
        // 7 bytes for the column string (e.g. "FFBFFBF")
        .byte 0
        .byte 0
        .byte 0
        .byte 0
        .byte 0
        .byte 0
        .byte 0
        
        // 3 bytes for the row string (e.g. "LRL")
        .byte 0
        .byte 0
        .byte 0
        
        // 1 byte for the newline
        .byte 0
    
        .section .rodata
    silver\_str:
        .asciz "Silver star answer: "
    
    gold\_str:
        .asciz "Gold star answer: "
    
    filename:
        .asciz "input.txt"
    
        /\* Lookup table for the "BFBBBFB"-to-binary conversion \*/
    bintab\_row:
        .quad 64
        .quad 32
        .quad 16
        .quad 8
        .quad 4
        .quad 2
        .quad 1
        
        /\* Lookup table for the "LRL"-to-binary conversion \*/
    bintab\_col:
        /\* Due to the way the lookups happen, we need to offset these
      abit forward to account for how the fact that the row
      specifier appears at the end of the string. This just makes
      indexing more easier elsewhere in the code. \*/
        .quad 0
        .quad 0
        .quad 0
        .quad 0
        .quad 0
        .quad 0
        .quad 0
        
        .quad 4
        .quad 2
        .quad 1
        
        
        /\* Helper routines \*/
        .section .text
        
        /\* size\_t get\_row(void): Get row of string spec in `buffer`. \*/
        .global get\_row
        .type get\_row, @function
        
        /\* size\_t get\_col(void): Get col of string spec in `buffer`. \*/
        .global get\_col
        .type get\_col, @function
    
        /\* void mark\_taken(size\_t row, size\_t col): Set corresponding
      seat location to &\#39;1&\#39; in `taken\_tab`.
          rax - row
          rbx - col
      \*/
        .global mark\_taken
        .type mark\_taken, @function
    
        /\* void store\_id(size\_t row, size\_t col): Set corresponding
      seat location to the seat id in `id\_tab`.
          rax - row
          rbx - col
      \*/
        .global store\_id
        .type store\_id, @function
    
        .global get\_max\_id
        .type get\_max\_id, @function
    
        .global print\_silver
        .type print\_silver, @function
    
        .global print\_string
        .type print\_string, @function
    
        .global strlen
        .type strlen, @function
    
        .global find\_emtpy\_seat\_id
        .type find\_empty\_seat\_id, @function
    
    find\_empty\_seat\_id:
        // Ok, so we have x and y to walk the entire plane.
        // We know the seat infront must not be empty,
        // and the seat behind must not be empty.
        // So we iterate over [1, 126] of the [0, 127] rows
        // (because it obviously cant be the front most or back most row)
    
        // Once we find an empty seat, look at the seat infront, and the
        // seat behind. if theyre both populated, return id in `rax`.
    
        // linear index of current seat
        push   %rsi
        // linear index of alternative seat
        push   %rdi
    
        // `taken\_tab` or `id\_tab` pointer
        push   %rdx
        // `taken\_tab` or `id\_tab` slot
        // We don&\#39;t save it because we clobber it on return anyway.
    //    push    %rax
    
        // Load `taken\_tab` into %rsi
        movq   $taken\_tab, %rdx
    
        // Remember, it can&\#39;t be the first or last row
        // so start on second row
        movq   $8, %rsi
    
    .Lfind\_empty\_seat\_id.loop:
        // Load our seat
        movq   (%rdx, %rsi, 8), %rax
    
        // If its empty, go check the front seat.
        cmp    $0, %rax
        je .Lfind\_empty\_seat\_id.check\_front
    
        inc    %rsi
        jmp    .Lfind\_empty\_seat\_id.loop
    
    .Lfind\_empty\_seat\_id.check\_front:
        // Now check if the seat infront is taken
        
        // Calculate the index of seat infront
        movq   %rsi, %rdi
        subq   $8, %rdi
        
        // Lookup in `taken\_tab`
        movq   (%rdx, %rdi, 8), %rax
    
        // If its taken, go check the back seat.
        cmp    $0, %rax
        jne    .Lfind\_empty\_seat\_id.check\_back
    
        inc    %rsi
        jmp    .Lfind\_empty\_seat\_id.loop
    
    .Lfind\_empty\_seat\_id.check\_back:
        // Now check if the seat behind is also taken
        
        // Calculate the index of seat behind
        movq   %rsi, %rdi
        addq   $8, %rdi
        
        // Lookup in `taken\_tab`
        movq   (%rdx, %rdi, 8), %rax
    
        // If its taken, that means we&\#39;ve found our seat
        cmp    $0, %rax
        jne    .Lfind\_empty\_seat\_id.found
    
        inc    %rdi
        jmp    .Lfind\_empty\_seat\_id.loop
    
    .Lfind\_empty\_seat\_id.found:
        // Ok, we found an empty seat with both the front and
        // back seats taken. %rsi already has the id, return it.
        
        movq   %rsi, %rax
        
        pop    %rdx
        pop    %rdi
        pop    %rsi
    
        ret
        
        .size find\_empty\_seat\_id, .-find\_empty\_seat\_id
    
    strlen:
        push   %rbx
        push   %rsi
        
        mov    %rax, %rsi
        mov    $0, %rbx
    
    .Lstrlen\_loop:
        mov    (%rsi, %rbx, 1), %al
        cmp    $0, %al
        je .Lstrlen\_done
    
        inc    %rbx
        jmp    .Lstrlen\_loop
        
    .Lstrlen\_done:
        mov    %rbx, %rax
    
        pop    %rsi
        pop    %rbx
    
        ret
    
    print\_string:
        push   %rax
        push   %rcx
        push   %rsi
        push   %rdi
    
        call   strlen
        mov    %rax, %rdx
    
        movq   $1, %rax
        movq   $1, %rdi
        movq   24(%rsp), %rsi
        syscall
    
        pop    %rdi
        pop    %rsi
        pop    %rcx
        pop    %rax
    
        ret
    
        .size print\_string, .-print\_string
    
    print\_number:
        // I need a bit of scratch memory space cos i need
        // to give sys\_write an address to a buffer
        push   %rbp
        movq   %rsp, %rbp
        
        // number to print
        push   %rax
        // index
        push   %rbx
        push   %rcx
        push   %rdx
    
        // We need to zero terminate it cos `print\_string`
        // will be scanning for it until we get the zero
        // so $10 (MAXINT="42945967295") + $2 ("\n\0") = $12
        sub    $12, %rsp
        movb   $&\#39;\n&\#39;, 10(%rsp)
        movb   $0, 11(%rsp)
        
        movq   $9, %rbx
        movq   $10, %rcx
    
    .Lprint\_number\_loop:
        cltd
        idiv   %ecx
        
        add    $0x30, %dl
        mov    %dl, (%rsp, %rbx, 1)
    
        cmp    $0, %rbx
        je .Lprint\_number\_done
    
        dec    %rbx
        jmp    .Lprint\_number\_loop
    .Lprint\_number\_done:
    
        mov    %rsp, %rax
        call   print\_string
    
        add    $12, %rsp
        
        pop    %rdx
        pop    %rcx
        pop    %rbx
        pop    %rax
    
        pop    %rbp
        ret
    
    print\_silver:
        
    
        .size print\_silver, .-print\_silver
    
    get\_max\_id:
        push   %rbx
    
        push   %rdx
        push   %rsi
        push   %rdi
    
        /\* Pointer to `taken\_tab` table \*/
        movq   $taken\_tab, %rsi
        /\* Pointer to `id\_tab` table \*/
        movq   $id\_tab, %rdi
        /\* Index \*/
        movq   $0, %rdx
        /\* Running max \*/
        movq   $0, %rbx
    
    .Lget\_max\_id\_loop:
        /\* load the taken variable for this seat \*/
        movq   (%rsi, %rdx, 8), %rax
        
        /\* if its 0, it is not taken, and therefore we skip it. \*/
        cmp    $0, %rax
        je .Lget\_max\_id\_skip
    
        /\* load the id for this seat \*/
        movq   (%rdi, %rdx, 8), %rax
    
        cmp    %rax, %rbx
        cmovc  %rax, %rbx
        
    .Lget\_max\_id\_skip:
        inc    %rdx
        cmp    $(128 \* 8), %rdx
        jl .Lget\_max\_id\_loop
    
        mov    %rbx, %rax
    
        pop    %rdi
        pop    %rsi
        pop    %rdx
        
        pop    %rbx
    
        ret
    
        .size get\_max\_id, .-get\_max\_id
    
    store\_id:
        push   %rax
        push   %rbx
        push   %rcx
        push   %rdi
    
        // calculate id
        imul   $8, %rax
        add    %rbx, %rax
        
        // store it in rcx
        mov    %rax, %rcx
    
        // restore rax
        mov    24(%rsp), %rax
    
        // calculate row memory location
        movq   $id\_tab, %rdi
        imul   $(8 \* 8), %rax
        add    %rax, %rdi
        
        // add column offset
        imul   $8, %rbx
        add    %rbx, %rdi
    
        // store id in rcx to slot in id\_tab
        movq   %rcx, (%rdi)
    
        pop    %rdi
        pop    %rcx
        pop    %rbx
        pop    %rax
    
        ret
    
        .size store\_id, .-store\_id
    
    mark\_taken:
        push   %rax
        push   %rbx
        push   %rcx
        push   %rdi
    
        // calculate id
        imul   $8, %rax
        add    %rbx, %rax
        
        // store it in rcx
        mov    %rax, %rcx
    
        // restore rax
        mov    24(%rsp), %rax
    
        // calculate row memory location
        movq   $taken\_tab, %rdi
        imul   $(8 \* 8), %rax
        add    %rax, %rdi
        
        // add column offset
        imul   $8, %rbx
        add    %rbx, %rdi
    
        // store presence in rcx to slot in id\_tab
        movq   $1, (%rdi)
    
        pop    %rdi
        pop    %rcx
        pop    %rbx
        pop    %rax
    
        ret
    
        .size mark\_taken, .-mark\_taken
        
    get\_row:
        push   %rbx
        push   %rcx
        push   %rdx
        push   %rsi
        push   %rdi
        push   %r8
    
        /\* zero-register for cmov below \*/
        movq   $0, %rbx
        /\* input buffer, e.g. "FFBBFFBLRL\n" \*/
        movq   $buffer, %rsi
        /\* lookup table for (2 \* %ecx) \*/
        movq   $bintab\_row, %rdi
        /\* index \*/
        movq   $0, %rcx
    
        /\* r8 will contain the row number \*/
        movq   $0, %r8
        
    .Lget\_row\_loop:  
        /\* Load in this seat (&\#39;F&\#39; or &\#39;B&\#39; into eax) \*/
        mov    (%rsi, %rcx, 1), %eax
        
        /\* Load in the value of this bit \*/
        movq   (%rdi, %rcx, 8), %rdx
        
        /\* I use a trick here: Notice that &\#39;F&\#39; = 0x46, and &\#39;B&\#39; =
      0x42. Hence, if we subtract &\#39;B&\#39;, we get either zero or
      non-zero.  Then, we can use `cmov` on the zero flag to move in
      the addend. \*/
        cmp    $0x42, %al
        cmovnz %rbx, %rdx
        add    %rdx, %r8
    
        inc    %rcx
        cmp    $7, %rcx
        jl .Lget\_row\_loop
    
    .Lget\_row\_done:
        mov    %r8, %rax
    
        pop    %r8
        pop    %rdi
        pop    %rsi
        pop    %rdx
        pop    %rcx
        pop    %rbx
    
        ret
    
        .size get\_row, .-get\_row
    
    get\_col:
        push   %rbx
        push   %rcx
        push   %rdx
        push   %rsi
        push   %rdi
        push   %r8
    
        /\* zero-register for cmov below \*/
        movq   $0, %rbx
        /\* input buffer, e.g. "FFBBFFBLRL\n" \*/
        movq   $buffer, %rsi
        /\* lookup table for (2 \* %ecx) \*/
        movq   $bintab\_col, %rdi
        /\* index (NOTE! We start at 7) \*/
        movq   $7, %rcx
    
        /\* r8 will contain the col number \*/
        movq   $0, %r8
        
    .Lget\_col\_loop:  
        /\* Load in this seat (&\#39;F&\#39; or &\#39;B&\#39; into eax) \*/
        mov    (%rsi, %rcx, 1), %eax
        
        /\* Load in the value of this bit \*/
        movq   (%rdi, %rcx, 8), %rdx
        
        /\* I use a trick here: Notice that &\#39;L&\#39; = 0x4C, and &\#39;R&\#39; =
      0x52. Hence, if we subtract &\#39;L&\#39;, we get either zero or
      non-zero.  Then, we can use `cmov` on the zero flag to move in
      the addend. \*/
        cmp    $0x4C, %al
        cmovz  %rbx, %rdx
        add    %rdx, %r8
    
        inc    %rcx
        cmp    $10, %rcx
        jl .Lget\_col\_loop
    
    .Lget\_col\_done:
        mov    %r8, %rax
    
        pop    %r8
        pop    %rdi
        pop    %rsi
        pop    %rdx
        pop    %rcx
        pop    %rbx
    
        ret
    
        .size get\_col, .-get\_col
    
steveklabnik/steveklabnik-day05.rs
steveklabnik/steveklabnik-day05.rs
fn solve(input: &str) -> (u32, u32) {
      let (min, max, sum) = input
          .lines()
          .map(|s| {
              s.bytes()
                  .fold(0, |acc, b| (acc << 1) | u32::from(b == b&\#39;B&\#39; || b == b&\#39;R&\#39;))
          })
          .fold((!0, 0, 0), |(min, max, sum), id| {
              (min.min(id), max.max(id), sum ^ id)
          });
    
      (max, cum\_xor(max) ^ cum\_xor(min - 1) ^ sum)
    }
    
    fn cum\_xor(a: u32) -> u32 {
      [a, 1, a + 1, 0][a as usize % 4]
    }
    
unknown-cnile/ucnile-day05.c
unknown-cnile/ucnile-day05.c
\#include <stdlib.h>
    \#include <stdio.h>
    \#include <string.h>
    \#include <sys/types.h>
    \#include <sys/stat.h>
    \#include <fcntl.h>
    \#include <sys/mman.h>
    \#include <unistd.h>
    \#include <limits.h>
    
    void die(char \*str) {
        fprintf(stderr, "[ERROR] %s\n", str);
        exit(-1);
    }
    
    FILE \*map\_file(const char \*filename) {
        int fd;
        if ((fd = open(filename, O\_RDONLY)) == -1) die("failed to open file");
        struct stat fd\_stat;
        if (fstat(fd, &fd\_stat) == -1) die("failed to stat file");
        void \*data;
        // never unmapped, probably fine
        if ((data = mmap(NULL,
                         fd\_stat.st\_size,
                         PROT\_READ,
                         MAP\_PRIVATE,
                         fd, 0)) == MAP\_FAILED) die("failed to map file");
        close(fd);
        return fmemopen(data, fd\_stat.st\_size, "r");
    }
    
    unsigned int xor\_z(unsigned int x) {
        switch (x % 4) {
            case 0: return x;
            case 1: return 1;
            case 2: return x + 1;
            case 3: return 0;
        }
    }
    
    unsigned int xor\_range(unsigned int min, unsigned int max) {
        // should underflow on min == 0, resulting in xor\_z(min - 1) == xor\_z(3) == 0
        return xor\_z(min - 1) ^ xor\_z(max);
    }
    
    \#define SEAT\_CNT 1024
    
    int main(int argc, char \*\*argv) {
        // read input
        FILE \*fd = map\_file("test.txt");
        char data[16];
        unsigned int min = UINT\_MAX;
        unsigned int max = 0;
        unsigned int acc = 0;
        while (fgets(data, 16, fd) != NULL) {
            unsigned int sid = 0;
            for (int i = 0; i < 10; i++) {
                sid <<= 1;
                sid |= ((data[i] >> 2) & 1);
            }
            sid ^= SEAT\_CNT - 1;
            if (sid > max) max = sid;
            if (sid < min) min = sid;
            acc ^= sid;
        }
        printf("P1: %u\n", max);
        printf("P2: %u\n", acc ^ xor\_range(min, max));
        return 0;
    }
    

Tags: