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]=='B' || code[i]=='R') 
                min = (min+max)/2+1;
            if(code[i]=='F' || code[i]=='L') 
                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] = '\0';
    
        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]=='B' || code[i]=='R') 
                min = (min+max)/2+1;
            if(code[i]=='F' || code[i]=='L') 
                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] = '\0';
        int n_lines = 0;
        for(int i = 0; i < length; i++){
            if(input[i] == '\n')
                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'Range loop
                if Item (I) = '1' 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'First);
        begin
           for I in Seats'First + 1 .. Seats'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'first .. 7)));
            Column := ConvertBase2 (ReplaceBits (Item (8 .. Item'last)));
            Seats (Index) := Row * 8 + Column;
            Index := Index + 1;
        end loop;
    
        Put_Line (Get_Maximum (Seats)'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 flugzeug128;
        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++){
                flugzeugi = '.';
            }
        }
    
        int i = 0;
        while((c = getc(input)) != EOF){
            if(c != '\n'){
                if(c == 'B') c = 1;
                if(c == 'F') c = 0;
                if(c == 'L') c = 0;
                if(c == 'R') 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;}
                flugzeugreihe = '#';
            }
        }
        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(flugzeugi == '.' && folge == 1 && flugzeugi+1 == '#'){
                    sitz = i*8+j;
                    folge = 0;
                    //i = 128;
                    printf("P2: %d\n",sitz);
                }
                if(flugzeugi == '#') folge = 1;
            }
        }
        fclose(input);
        return 0;
    }
    
jsanon/javascript-day05.js
jsanon/javascript-day05.js
#!/usr/bin/env node
    'use strict';
    
    const { exit, argv } = require('process');
    const readInput = require('../lib/read-input.js');
    
    // 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 'B' value, we just have to shift on a 1.
    // When we encounter a 'F' 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 'B', we use 'R' and for 'F' we use 'L'
    function getSeatId(pass)
    {
        if (pass.length !== 10) throw Error('Assert: Value is too small/big.');
    
        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] === 'B' || pass[i] === 'R');
        }
        return id;
    }
    
    async function main([ part, inputFile ])
    {
        const input = (await readInput(inputFile /* stdin = undefined */))
            .split('\n');
    
        console.time(Day-5: ${</span><span style="color: #cccccc">part</span><span style="color: #cd0000">});
        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 === 'part-1')
        {
            console.timeEnd(Day-5: ${</span><span style="color: #cccccc">part</span><span style="color: #cd0000">});
            console.log(Max Seat ID: ${</span><span style="color: #cccccc">max</span><span style="color: #cd0000">});
        }
        else if (part === 'part-2')
        {
            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: ${</span><span style="color: #cccccc">part</span><span style="color: #cd0000">});
            console.log(My Seat ID: ${</span><span style="color: #cccccc">mySeat</span><span style="color: #cd0000">});
        }
        else
        {
            console.timeEnd(Day-5: ${</span><span style="color: #cccccc">part</span><span style="color: #cd0000">});
            throw Error('Must be part-1 or part-2.');
        }
    }
    
    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 '1' 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    $'\n', 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 ('F' or 'B' 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 'F' = 0x46, and 'B' =
        0x42. Hence, if we subtract 'B', 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 ('F' or 'B' 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 'L' = 0x4C, and 'R' =
        0x52. Hence, if we subtract 'L', 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 '1' 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't save it because we clobber it on return anyway.
    //    push    %rax
    
        // Load taken_tab into %rsi
        movq    $taken_tab, %rdx
    
        // Remember, it can'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'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    $'\n', 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 ('F' or 'B' 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 'F' = 0x46, and 'B' =
        0x42. Hence, if we subtract 'B', 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 ('F' or 'B' 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 'L' = 0x4C, and 'R' =
        0x52. Hence, if we subtract 'L', 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'B' || b == b'R'))
            })
            .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
    }
    
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: