Day 7

Previous: Day 06 | Next: Day 08

Bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in bags in you forgot to add an end state to your recursive function, idiot.

Also, off by one.

AUTO-ACQUIRED DATA FOLLOWS...

archivist/day07.lisp
archivist/day07.lisp
(asdf:load-system :split-sequence)
    (asdf:load-system :iterate)
    (defpackage #:aoc-7
      (:use #:cl #:split-sequence #:iterate))
    (in-package #:aoc-7)
    
    (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)))
    
    (defun getinput ()
        (let* ((fname "testinput")
               (lines (uiop:read-file-lines  fname)))
          lines
          ))
    
    (defun replac (lines)
        (mapcar 
            (lambda (x)
              (last (mapcar 
                (lambda (s r)
                  (setf x (replace-all x s r)))
                '("," "." " bags " " bag " "contain " "no other" " bags" " bag")
                `(""  ""  ,(string #\newline) ,(string #\newline) "" "" "" "")))
              )
            lines)
        )
    
    
    (defun split (lines)
        (remove-if
          (lambda (x)
            (eq (length x) 1))
          (mapcar 
            (lambda (x)
                    (split-sequence #\newline (car x)
                                    :remove-empty-subseqs t))
            lines)))
    
    (defun split-num (str)
        (list
          (parse-integer (car (split-sequence #\space str :count 1)))
          (apply 
            (lambda (x y) 
              (concatenate 'string x y)) 
            (split-sequence #\space str :from-end t :count 2))))
    
    (defun line-num  (line)
        (cons (replace-all (car line) " " "")
              (mapcar #'split-num
                      (cdr line))))
    
    (defun split-nums (lines)
        (mapcar
          (lambda (x)
                  (line-num x))
          lines))
    
    (defun get-data ()
        (split-nums (split (replac (getinput)))))
    
    (defun searchline (str line)
        (reduce (lambda (&optional x y)
                  (or x y))
                (mapcar (lambda (sub)
                          (equal (cadr sub)
                                 str))
                        line)))
    
    (defun getline (str data)
        (car 
          (remove-if-not (lambda (x)
                           (equal str (car x)))
                         data)))
    (defun remline (str data)
        (remove-if (lambda (x)
                     (equal str (car x)))
                   data))
    
    (defun rep-element (el data &optional (keepln t))
        (if (getline (second el) data)
            (list (first el) 
                  (rep-line (cdr (getline (second el) data))
                            data keepln))
            (if keepln el (list (first el))))  )
    
    (defun rep-line (line data &optional (keepln t))
        (mapcar (lambda (x)
                  (rep-element x data keepln)) 
                  line))
    
    (defun rep (col1 lines data &optional (keepln t))
        (mapcar (lambda (x l)
                  (cons x
                        (rep-line l data keepln)))
                col1 lines))
    
    (defun find-recur (el l)
        (cond ((null l) nil)
              ((atom l) (equal el l))
              (t (if (equal el (car l))
                     t
                     (or
                       (find-recur el
                                 (car l))
                       (find-recur el
                                 (cdr l)))))))
    (defun nostring (l)
        (let ((nl (if (not (or (atom l) (null l))) 
                      (remove-if 
                        (lambda (x)
                          (typep x 'string ))
                         l)
                      l)))
          (cond ((atom nl) nl)
                ((null (cdr nl)) (list (nostring (car nl))))
                (t (list (nostring (car nl))
                         (nostring (cdr nl)))
                         ))))
    
    (defun count-recur (l)
        (cond ((null l) 0)
             ((atom l) l)
             ((and (> (length l) 1)
                   (atom (car l))
                   (not (atom (cadr l))))
              (+ (car l)
                 (* (car l)
                    (count-recur (cdr l)))))
             (t (+ (count-recur (car l))
                      (count-recur (cadr l))))))
    
    (defun part1 ()
        (let* ((data (remline "shinygold" (get-data)))
               (fdata (mapcar #'car data))
               (bdata (mapcar #'cdr data)))
          (count 't 
                 (mapcar (lambda (x)
                    (find-recur "shinygold" x))
                  (rep fdata bdata data)))
          ))
    
    (defun part2 ()
        (let* ((data (get-data))
               (fdata (mapcar #'car data))
               (bdata (mapcar #'cdr data))
               (pdata (rep fdata bdata data nil))
               (gold (getline "shinygold" pdata)))
          (print pdata)
          (print gold)
          (print (nostring gold))
          (cdr gold)
          (count-recur (cdr gold))))
    
javanon/day07.js
javanon/day07.js
dataset = document.querySelector("body > pre");
    bagRuleList = dataset.innerText.trim().split("\n");
    
    function day7 (bagRuleList) {
        const bagsFinder = function (bags, colours, specifiedColour) {
            return colours && colours.some(c => c.colour == specifiedColour || bagsFinder(bags, bags[c.colour], specifiedColour));
        }
        const bagsCounter = function (bags, colour) {
            return (colour == "no other") ? 1 : bags[colour].reduce((acc, bag) => acc += bag.value * bagsCounter(bags, bag.colour), 1);
        }
        var bags = {};
        bagRuleList.map(bagRule => {
            bag = bagRule.split("contain");
            bagColour = bag[0].replace(/(bags)/g, '').trim();
            quantaties =  bag[1].match(/[0-9]+/g) || ["0"];
            contains = bag[1].replace(/[0-9]+|bag[s]*|./g, '').split(",").map((colour, index) => { return {value: quantaties[index], colour: colour.trim()} });
            return {
                bagColour: bagColour,
                container: contains
            };
        }).forEach(bag => bags[bag.bagColour] = bag.container);
        
        var silver = Object.keys(bags).filter(colour => bagsFinder(bags, bags[colour], "shiny gold"));
        var gold = bagsCounter(bags, "shiny gold") - 1;
        
        return {"silver": silver.length, "gold": gold};
    }
    
steveklabnik/steveklabnik-day07.rs
steveklabnik/steveklabnik-day07.rs
use std::collections::{HashMap, HashSet};
    
    fn solve(input: &str) -> (u32, u32) {
        let mut graph: HashMap<_, Vec<_>> = Default::default();
        let mut graph2: HashMap<_, Vec<_>> = Default::default();
    
        for s in input.lines() {
            let (outer, s) = s.split_at(s.find(" bags").unwrap());
            let s = &s[14..];
    
            if s != "no other bags." {
                for s in s.split(',').map(str::trim_start) {
                    let (count, s) = s.split_at(s.find(' ').unwrap());
                    let count = count.parse().unwrap();
                    let (inner, _) = s.split_at(s.rfind(' ').unwrap());
                    let inner = inner.trim();
    
                    graph.entry(outer).or_default().push((inner, count));
                    graph2.entry(inner).or_default().push((outer, 1));
                }
            }
        }
    
        (
            dfs(&graph2, &mut Some(HashSet::new()), "shiny gold"),
            dfs(&graph, &mut None, "shiny gold")
        )
    }
    
    fn dfs<'a>(
        graph: &HashMap<&str, Vec<(&'a str, u32)>>,
        visited: &mut Option<HashSet<&'a str>>,
        from: &str
    ) -> u32 {
        graph.get(&from).map_or(0, |tos| {
            let mut count = 0;
    
            for &(to, c) in tos {
                if visited.as_mut().map_or(true, |v| v.insert(to)) {
                    count += c + c * dfs(graph, visited, to);
                }
            }
    
            count
        })
    }
    
unknown-cnile/ucnile-day07.c
unknown-cnile/ucnile-day07.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
    
    struct item_entry {
        uint32_t bag_id;
        uint32_t bag_cnt;
    };
    
    struct bag {
        uint32_t bag_id;
        int32_t p1_state;
        uint32_t contain_cnt;
        struct item_entry contain[16];
    };
    
    struct bag data[MAX_DATA];
    int data_len = 0;
    
    #define MAX_LINE 256
    
    #define MOD_HASH(acc, c) acc = (((acc) << 5) - (acc)) ^ (c)
    
    int compare_bag(const void *a, const void *b) {
        uint32_t an = ((struct bag *) a)->bag_id;
        uint32_t bn = ((struct bag *) b)->bag_id;
        // assume no collisions
        if (an < bn) return -1;
        if (an > bn) return 1;
        __builtin_trap();
    }
    
    uint32_t scan_color(char **s) {
        uint32_t acc = 0;
        while (**s != ' ') {
            acc = ((acc << 5) - acc) ^ *((*s)++);
        }
        acc = ((acc << 5) - acc) ^ ' ';
        (*s)++;
        while (**s > ' ') {
            acc = ((acc << 5) - acc) ^ *((*s)++);
        }
        return acc;
    }
    
    int find_bag_idx(uint32_t bag_id) {
        int min = 0;
        int max = data_len - 1;
        while (1) {
            int pick = (min + max) / 2;
            if (data[pick].bag_id == bag_id) return pick;
            else if (min == max) __builtin_trap();
            else if (data[pick].bag_id < bag_id) min = pick + 1;
            else if (data[pick].bag_id > bag_id) max = pick - 1;
        }
    }
    
    static uint32_t shiny_gold_hash;
    
    int is_p1_mark_idx(int idx);
    
    int is_p1_mark(int id) {
        if (id == shiny_gold_hash) return 1;
        return is_p1_mark_idx(find_bag_idx(id));
    }
    
    int is_p1_mark_idx(int idx) {
        if (data[idx].p1_state == -1) {
            for (int i = 0; i < data[idx].contain_cnt; i++) {
                if (is_p1_mark(data[idx].contain[i].bag_id)) {
                    return data[idx].p1_state = 1;
                }
            }
            return data[idx].p1_state = 0;
        } else return data[idx].p1_state;
    }
    
    int count_bag(uint32_t id) {
        int idx = find_bag_idx(id);
        int acc = 1;
        for (int i = 0; i < data[idx].contain_cnt; i++) {
            acc += count_bag(data[idx].contain[i].bag_id) * data[idx].contain[i].bag_cnt;
        }
        return acc;
    }
    
    void calc_sgh() {
        char *ptr = "shiny gold";
        shiny_gold_hash = scan_color(&ptr);
    }
    
    int main(int argc, char **argv) {
        calc_sgh();
        // read input
        FILE *fd = map_file("test.txt");
        char line[MAX_LINE];
        while (fgets(line, MAX_LINE, fd) != NULL) {
            if (line[0] <= '\n') continue;
            char *ptr = line;
            uint32_t head_id = scan_color(&ptr);
            ptr += 14;
            if (!strcmp(ptr, "no other bags.\n")) {
                data[data_len++] = (struct bag) {.bag_id = head_id, .p1_state = 0, .contain_cnt = 0};
            } else {
                struct bag *cur_bag = data + data_len;
                *cur_bag = (struct bag) {.bag_id = head_id, .p1_state = -1, .contain_cnt = 0};
                do {
                    while (*ptr < '0') ptr++;
                    struct item_entry *cur_ent = cur_bag->contain + (cur_bag->contain_cnt++);
                    cur_ent->bag_cnt = 0;
                    while (*ptr != ' ') {
                        cur_ent->bag_cnt *= 10;
                        cur_ent->bag_cnt += *ptr - '0';
                        ptr++;
                    }
                    ptr++;
                    cur_ent->bag_id = scan_color(&ptr);
                    ptr += 4;
                    if (*ptr == 's') ptr++;
                } while (*ptr != '.');
                data_len++;
            }
        }
        int p1_acc = 0;
        qsort(data, data_len, sizeof(struct bag), &compare_bag);
        for (int i = 0; i < data_len; i++) {
            p1_acc += is_p1_mark_idx(i);
        }
        printf("P1: %d\n", (int) p1_acc);
        printf("P2: %d\n", count_bag(shiny_gold_hash) - 1);
        return 0;
    }
    

Tags: