Day 8

Previous: Day 07 | Next: Day 09

Bing bing wahoo edition

AUTO-ACQUIRED DATA FOLLOWS...

archivist/day08.lisp
archivist/day08.lisp
(asdf:load-system :split-sequence)
    (asdf:load-system :iterate)
    (defpackage #:aoc-8
      (:use #:cl #:split-sequence #:iterate))
    (in-package #:aoc-8)
    
    (defun cat (&rest strs)
        (concatenate 'string strs))
    
    (defun replace-all (string part replacement &key (test #'char=))
      "Returns a new string in which all the occurences of the part 
    is replaced with replacement."
      (with-output-to-string (out)
        (loop with part-length = (length part)
              for old-pos = 0 then (+ pos part-length)
              for pos = (search part string
                                :start2 old-pos
                                :test test)
              do (write-string string out
                               :start old-pos
                               :end (or pos (length string)))
              when pos do (write-string replacement out)
              while pos)))
    
    (defstruct machine
        (pointer 0)
        (accum 0))
    (defparameter *vm* (make-machine))
    
    (defun copy-array  (array)
        (let ((new (make-array (array-dimensions array) :displaced-to array)))
                   (adjust-array new (array-dimensions array) :displaced-to nil))) 
    
    (defun getinput ()
        (let* ((fname "bigboylarge")
               (lines (uiop:read-file-lines  fname)))
          lines
          ))
    (defun process (input)
        (make-array (length input) 
                    :initial-contents
                    (mapcar (lambda (x) 
                              (list (str-to-op x)
                                    nil))
                            input)))
    
    (defun str-to-op (str)
        (let ((substr (subseq str 0 3)))
          (list (cond ((equal substr "nop") #'nop) 
                      ((equal substr "acc") #'acc)
                      ((equal substr "jmp") #'jmp))
                (parse-integer (subseq str 4)))))
    
    (defun nop (vm val)
        (incf (machine-pointer vm)))
    
    (defun acc (vm val)
        (setf (machine-accum vm)
              (+ (machine-accum vm)
                 val))
        (incf (machine-pointer vm)))
    
    (defun jmp (vm val)
        (setf (machine-pointer vm)
              (+ (machine-pointer vm)
                 val)))
    
    (defun part1 ()
      (let ((vm (make-machine))
            (code (process (getinput))))
        (iterate 
          (while (and (not (cadr (aref code (machine-pointer vm))))
                      (<= (machine-pointer vm) (length code))))
            (let ((op (aref code (machine-pointer vm))))
              (setf (cadr op) t)
              (funcall (caar op) vm (cadar op)))
          )
        (print code)
        (machine-accum vm)))
    
    (defun part2-run (code)
      (let ((vm (make-machine)))
        (iterate 
          (while (and (< (machine-pointer vm) (length code))
                      (>= (machine-pointer vm) 0)
                   (not (cadr (aref code (machine-pointer vm))))
                      ))
            (let ((op (aref code (machine-pointer vm))))
              (setf (cadr op) t)
              (funcall (caar op) vm (cadar op))
              )
            (finally  (return (if (>= (machine-pointer vm) 
                                    (length code))
                                  (machine-accum vm)
                                  nil))))))
    
    (defun swap (fun)
        (cond ((eq fun #'jmp) #'nop)
              ((eq fun #'nop) #'jmp)
              (t fun)))
    
    (defun part2 ()
        (let* ((code (process (getinput))))
          ;(part2-run vcode)
          ;reset
          (print (1- (length code)))
          (iterate (for i from 0 to (1- (length code))) 
                   (if (eq (mod i 10000) 0) (print i))
                   (let ((op (aref code i)))
                     (if (not (eq (caar op) #'acc))
                         (progn 
                           (setf (caar op) 
                                 (swap (caar op)))
                           (let ((res (part2-run code)))
                             (if res (return res)))
                           
                           (iterate (for i from 0 to (1- (length code)))
                                    (setf (cadr (aref code i)) nil))
                           (setf (caar op) 
                                 (swap (caar op)))))))))
    
steveklabnik/steveklabnik-day08.rs
steveklabnik/steveklabnik-day08.rs
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
    enum Op {
        Nop,
        Jmp,
        Acc
    }
    
    fn solve(input: &str) -> (i32, i32) {
        let ops: Vec<_> = input
            .lines()
            .map(|s| {
                let arg = s[4..].parse().unwrap();
    
                match &s[..3] {
                    "nop" => (Op::Nop, arg),
                    "jmp" => (Op::Jmp, arg),
                    "acc" => (Op::Acc, arg),
                    _ => unreachable!()
                }
            })
            .collect();
    
        let b = (0..ops.len())
            .filter(|&i| ops[i].0 != Op::Acc)
            .map(|i| {
                let mut ops = ops.clone();
                let op = &mut ops[i].0;
                *op = if *op == Op::Nop { Op::Jmp } else { Op::Nop };
                ops
            })
            .filter_map(|ops| run(&ops).ok())
            .next()
            .unwrap();
    
        (run(&ops).unwrap_err(), b)
    }
    
    fn run(ops: &[(Op, i32)]) -> Result<i32, i32> {
        let mut set = vec![false; ops.len()];
        let mut pc: u32 = 0;
        let mut acc = 0;
    
        while !std::mem::replace(&mut set[pc as usize], true) {
            match ops[pc as usize] {
                (Op::Nop, _) => pc += 1,
                (Op::Jmp, arg) => pc = ((pc as i32) + arg) as u32,
                (Op::Acc, arg) => {
                    acc += arg;
                    pc += 1;
                }
            }
    
            if pc as usize == ops.len() {
                return Ok(acc);
            }
        }
    
        Err(acc)
    }
    
unknown-cnile/ucnile-day08.c
unknown-cnile/ucnile-day08.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 <stdint.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");
    }
    
    #define MAX_DATA 4096
    
    #define INS_ACC 0
    #define INS_JMP 1
    #define INS_NOP 2
    
    struct ins {
        uint32_t op;
        uint32_t val;
    };
    
    struct ins asm_data[MAX_DATA];
    int asm_mark[MAX_DATA];
    int asm_len = 0;
    
    #define MAX_LINE 256
    
    int exec_asm() {
        int pos = 0, acc = 0;
        while (1) {
            if ((pos > asm_len) || (pos < 0)) return 0;
            if (pos == asm_len) {
                printf("P2: %d\n", acc);
                exit(0);
            } else if (asm_mark[pos]) {
                memset(asm_mark, 0, sizeof(asm_mark));
                return acc;
            }
            asm_mark[pos] = 1;
            switch (asm_data[pos].op) {
                case INS_ACC: acc += asm_data[pos].val; pos++; break;
                case INS_JMP: pos += asm_data[pos].val; break;
                case INS_NOP: pos++; break;
            }
        }
    }
    
    int main(int argc, char **argv) {
        // read input
        FILE *fd = map_file("test.txt");
        char line[MAX_LINE];
        while (fgets(line, MAX_LINE, fd) != NULL) {
            char optxt[8];
            int arg;
            if (sscanf(line, "%s %d", optxt, &arg) != 2) break;
            asm_data[asm_len].val = arg;
            switch (*optxt) {
                case '\n':
                case '\0': break;
                case 'a': asm_data[asm_len++].op = INS_ACC; break;
                case 'j': asm_data[asm_len++].op = INS_JMP; break;
                case 'n': asm_data[asm_len++].op = INS_NOP; break;
            }
        }
        printf("P1: %d\n", exec_asm());
        for (int i = 0; i < asm_len; i++) {
            if (asm_data[i].op == INS_ACC) continue;
            asm_data[i].op ^= 3;
            exec_asm();
            asm_data[i].op ^= 3;
        }
        return 0;
    }
    

Tags: