The stories and information posted here are artistic works of fiction and falsehood. Only a fool would take anything posted here as fact.
The stories and information posted here are artistic works of fiction and falsehood. Only a fool would take anything posted here as fact.
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]==&\#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.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]==&\#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.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&\#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.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 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.jsjsanon/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.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 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.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 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.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&\#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.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; }