He is a barbarian, and thinks the customs of his tribe and island are the laws of nature.
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...?)
archivist/day05-1.carchivist/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.carchivist/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.adbday-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.cdeutschanon/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.jsjsanon/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.smilkanon/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 inrax
. 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 ofbuffer
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 thetaken_tab
call mark_taken // Also calculate and store the id for this seat inid_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 inbuffer
. */ .global get_row .type get_row, @function /* size_t get_col(void): Get col of string spec inbuffer
. */ .global get_col .type get_col, @function /* void mark_taken(size_t row, size_t col): Set corresponding seat location to '1' intaken_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 inid_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 cosprint_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 totaken_tab
table */ movq $taken_tab, %rsi /* Pointer toid_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 usecmov
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 usecmov
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.smilkanon/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 inrax
. 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 ofbuffer
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 thetaken_tab
call mark_taken // Also calculate and store the id for this seat inid_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 inbuffer
. */ .global get_row .type get_row, @function /* size_t get_col(void): Get col of string spec inbuffer
. */ .global get_col .type get_col, @function /* void mark_taken(size_t row, size_t col): Set corresponding seat location to '1' intaken_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 inid_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 inrax
. // linear index of current seat push %rsi // linear index of alternative seat push %rdi //taken_tab
orid_tab
pointer push %rdx //taken_tab
orid_tab
slot // We don't save it because we clobber it on return anyway. // push %rax // Loadtaken_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 intaken_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 intaken_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 cosprint_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 totaken_tab
table */ movq $taken_tab, %rsi /* Pointer toid_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 usecmov
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 usecmov
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.rssteveklabnik/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.cunknown-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; }