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

(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 &\#39;string strs))
    
    (defun replace-all (string part replacement &key (test \#&\#39;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)))
                &\#39;("," "." " 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 &\#39;string x y)) 
            (split-sequence \#\space str :from-end t :count 2))))
    
    (defun line-num  (line)
        (cons (replace-all (car line) " " "")
              (mapcar \#&\#39;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 &\#39;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 \#&\#39;car data))
               (bdata (mapcar \#&\#39;cdr data)))
          (count &\#39;t 
                 (mapcar (lambda (x)
                    (find-recur "shinygold" x))
                  (rep fdata bdata data)))
          ))
    
    (defun part2 ()
        (let\* ((data (get-data))
               (fdata (mapcar \#&\#39;car data))
               (bdata (mapcar \#&\#39;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

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, &\#39;&\#39;).trim();
            quantaties =  bag[1].match(/[0-9]+/g) || ["0"];
            contains = bag[1].replace(/[0-9]+|bag[s]\*|\./g, &\#39;&\#39;).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

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(&\#39;,&\#39;).map(str::trim\_start) {
                  let (count, s) = s.split\_at(s.find(&\#39; &\#39;).unwrap());
                  let count = count.parse().unwrap();
                  let (inner, \_) = s.split\_at(s.rfind(&\#39; &\#39;).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<&\#39;a>(
      graph: &HashMap<&str, Vec<(&&\#39;a str, u32)>>,
      visited: &mut Option<HashSet<&&\#39;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

\#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 != &\#39; &\#39;) {
            acc = ((acc << 5) - acc) ^ \*((\*s)++);
        }
        acc = ((acc << 5) - acc) ^ &\#39; &\#39;;
        (\*s)++;
        while (\*\*s > &\#39; &\#39;) {
            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] <= &\#39;\n&\#39;) 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 < &\#39;0&\#39;) ptr++;
                    struct item\_entry \*cur\_ent = cur\_bag->contain + (cur\_bag->contain\_cnt++);
                    cur\_ent->bag\_cnt = 0;
                    while (\*ptr != &\#39; &\#39;) {
                        cur\_ent->bag\_cnt \*= 10;
                        cur\_ent->bag\_cnt += \*ptr - &\#39;0&\#39;;
                        ptr++;
                    }
                    ptr++;
                    cur\_ent->bag\_id = scan\_color(&ptr);
                    ptr += 4;
                    if (\*ptr == &\#39;s&\#39;) ptr++;
                } while (\*ptr != &\#39;.&\#39;);
                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: