Day 7: Handy Haversacks

=ARRAYFORMULA(
  QUERY(
   {SPLIT(
    TRIM(
     FLATTEN(
      IF(ISBLANK('07.1'!A1:A),,
       REGEXEXTRACT('07.1'!A1:A,"(.*) bag?s\.? contain .*")&"|"&
       REGEXREPLACE(
        SPLIT(
         REGEXREPLACE(
          REGEXEXTRACT(
           '07.1'!A1:A,
           "bag?s\.? contain (.*)"),
          "bags?\.?|\.",""),
         ", ",FALSE,TRUE),
        "([0-9]+) (.*)",
        "$1|$2")))),
    "|");
    IF(ISBLANK('07.1'!A1:A),,REGEXEXTRACT('07.1'!A1:A,"(.*) bags?\.? contain")),
    IF(ISBLANK('07.1'!A1:A),,0),
    IF(ISBLANK('07.1'!A1:A),,REGEXEXTRACT('07.1'!A1:A,"(.*) bags?\.? contain"))},
   "select Col1, Sum(Col2) 
    where Col2 is not null 
    group by Col1
    pivot Col3
    label Sum(Col2) ''"))

Basically, I'm pulling everything apart and categorizing it in its source bag. I then create another array that is stacked below this that is all bags with the value of 0.

From here I run this sloppy bullshit that is a tweak on a formula I saw on reddit.

=ARRAYFORMULA(
   SUMPRODUCT(
    B$2:B$650,
    OFFSET('07.2'!$B$2:$B$650,0,ROW()-2)))

I hate everything about this, but I really think it is the only way to get the value we're looking for. You need to drag fill it across 14 columns.

I tried to run a copy of the sheet I got off of reddit, but after about twenty minutes, Sheets basically came to a halt and refused to work. Essentially it's the same idea, but with a few thousand fewer formulas.

import sys
import re

inp = sys.stdin.readlines()
bags = {}
for l in inp:
    bag, content = re.match("(.+) bags contain (.+)\.", l).groups()
    for c in content.split(", "):
        m = re.match("\d+ (.+) bags?", c)
        if m:
            contentBag = m.groups()[0]
            if contentBag in bags:
                bags[contentBag].append(bag)
            else:
                bags[contentBag] = [bag]

print(bags)
queue = bags['shiny gold']
possibleContainers = set(queue)

while len(queue) > 0:
    checkBag = queue.pop()
    possibleContainers = possibleContainers.union(set(bags.get(checkBag, [])))
    queue = queue + bags.get(checkBag, [])

print(len(possibleContainers))

import sys
import re

inp = sys.stdin.readlines()
bags = {}
for l in inp:
    bag, content = re.match("(.+) bags contain (.+)\.", l).groups()
    for c in content.split(", "):
        m = re.match("(\d+) (.+) bags?", c)
        if m:
            count, contentBag = m.groups()
            count = int(count)
            if bag in bags:
                bags[bag] = bags[bag] + [contentBag for _ in range(count)]
            else:
                bags[bag] = [contentBag for _ in range(count)]

queue = bags['shiny gold']
bagCount = len(queue)

while len(queue) > 0:
    checkBag = queue.pop()
    bagCount += len(bags.get(checkBag, []))
    queue = queue + bags.get(checkBag, [])

print(bagCount)

For the first part, my approach was to use regular expressions to parse the input into an adjacency list graph representation and then just traverse the graph (BFS/DFS) to check if any source bag eventually reached the target "shiny gold" bag.

import re
import sys

# Constants

CONTAIN_RE = r'^(.*) bags contain\s(.*)$'
TARGETS_RE = r'(\d+) ([a-z]+ [a-z]+) bags*[,.]' 

# Functions

def parse_rules():
    rules = {}

    for line in sys.stdin:
        source, targets = re.findall(CONTAIN_RE, line.strip())[0]
        rules[source]   = {}
        for count, target in re.findall(TARGETS_RE, targets):
            rules[source][target] = int(count)

    return rules

def contains(rules, source, target, first=False):
    if source == target:
        return not first

    return any(contains(rules, neighbor, target) for neighbor in rules[source])

# Main Execution

def main():
    rules = parse_rules()
    count = sum(1 for source in rules if contains(rules, source, 'shiny gold', True))

    print(count)

if __name__ == '__main__':
    main()

For the second part, my solution just recursively counts the number of bags that can be reached from the "shiny gold" source bag.

import re
import sys

# Constants

CONTAIN_RE = r'^(.*) bags contain\s(.*)$'
TARGETS_RE = r'(\d+) ([a-z]+ [a-z]+) bags*[,.]' 

# Functions

def parse_rules():
    rules = {}

    for line in sys.stdin:
        source, targets = re.findall(CONTAIN_RE, line.strip())[0]
        rules[source]   = {}
        for count, target in re.findall(TARGETS_RE, targets):
            rules[source][target] = int(count)

    return rules

def count_bags(rules, source):
    return sum(
        number * (count_bags(rules, bag) + 1) for bag, number in rules[source].items()
    )

# Main Execution

def main():
    rules = parse_rules()
    bags  = count_bags(rules, 'shiny gold')

    print(bags)

if __name__ == '__main__':
    main()

//
//  main.swift
//  advent_of_code_7
//
//  Created by skg on 12/7/20.
//

import Foundation


// i love the internet
// https://exceptionshub.com/swift-extract-regex-matches.html
extension String {
  func regex (pattern: String) -> [String] {
    do {
        let regex = try NSRegularExpression(pattern: pattern, options: NSRegularExpression.Options(rawValue: 0))
      let nsstr = self as NSString
      let all = NSRange(location: 0, length: nsstr.length)
      var matches : [String] = [String]()
        regex.enumerateMatches(in: self, options: NSRegularExpression.MatchingOptions(rawValue: 0), range: all) {
        (result : NSTextCheckingResult?, _, _) in
        if let r = result {
            let result = nsstr.substring(with: r.range) as String
          matches.append(result)
        }
      }
      return matches
    } catch {
      return [String]()
    }
  }
}

final class Bag {
    var color: String
    var contents: Dictionary<String, Int>
    
    init(color: String, contents: Dictionary<String, Int>) {
        self.color = color
        self.contents = contents
    }
}

func readFile(path: String) -> [String] {
    errno = 0
    if freopen(path, "r", stdin) == nil {
        perror(path)
        return []
    }
    
    var inputArray = [String]()
    
    while let line = readLine() {
        inputArray.append(line)
    }
    return inputArray
}

func parseInput(puzzleInput: [String]) -> Dictionary<String, Bag> {
    // There are two types of strings
    
    // light red bags contain 1 bright white bag, 2 muted yellow bags.
    // ---------              --------------      --------------
    //   color                        # of other color(s)
    
    // However, there can be a line with a bag that has no contents
    // faded blue bags contain no other bags.
    // ----------              --
    //   color             No contents
    
    // every bag is described with 2 words followed by the word "bag(s)"
    // bags that contain no other bags just have the word "no"
//    let bagColorRegex = NSRegularExpression("^[a-z]* [a-z]*")
//    let bagContentsRegex = NSRegularExpression("[0-9]+ [a-z]* [a-z]*")
    
    var luggageRack: Dictionary<String, Bag> = [:]
    
    for rule in puzzleInput {
        let bagColor = rule.regex(pattern: "^[a-z]* [a-z]*")
        let bagContentsArray = rule.regex(pattern: "[0-9]+ [a-z]* [a-z]*")
        var bagContentsDict: Dictionary<String, Int> = [:]
        for bag in bagContentsArray {
            let bagComponents = bag.components(separatedBy: " ")
            let bagContentsCount = bagComponents[0]
            let bagContentsDescriptor = bagComponents[1] + " " + bagComponents[2]
            bagContentsDict[bagContentsDescriptor] = Int(bagContentsCount)
        }
        let newBag = Bag(color: bagColor[0], contents: bagContentsDict)
        luggageRack[newBag.color] = newBag
    }
    return luggageRack
}

func doesItHave(bags: Dictionary<String, Bag>, bag: Bag, desiredColor: String) -> Bool {
    if bag.color == desiredColor {
        return true
    }
    
    for bagKey in bag.contents.keys where doesItHave(bags: bags, bag: bags[bagKey]!, desiredColor: desiredColor) {
        return true
    }
    
    return false
    
}

let puzzleInput = readFile(path: "input_7")
let bags = parseInput(puzzleInput: puzzleInput)

var dayOneCount: Int = 0
for bag in bags.values where doesItHave(bags: bags, bag: bag, desiredColor: "shiny gold") && bag.color != "shiny gold" {
    dayOneCount += 1
}
print("Part 1: \(dayOneCount)")

//
//  main.swift
//  advent_of_code_7
//
//  Created by skg on 12/7/20.
//

import Foundation


// i love the internet
// https://exceptionshub.com/swift-extract-regex-matches.html
extension String {
  func regex (pattern: String) -> [String] {
    do {
        let regex = try NSRegularExpression(pattern: pattern, options: NSRegularExpression.Options(rawValue: 0))
      let nsstr = self as NSString
      let all = NSRange(location: 0, length: nsstr.length)
      var matches : [String] = [String]()
        regex.enumerateMatches(in: self, options: NSRegularExpression.MatchingOptions(rawValue: 0), range: all) {
        (result : NSTextCheckingResult?, _, _) in
        if let r = result {
            let result = nsstr.substring(with: r.range) as String
          matches.append(result)
        }
      }
      return matches
    } catch {
      return [String]()
    }
  }
}

final class Bag {
    var color: String
    var contents: Dictionary<String, Int>
    
    init(color: String, contents: Dictionary<String, Int>) {
        self.color = color
        self.contents = contents
    }
}

func readFile(path: String) -> [String] {
    errno = 0
    if freopen(path, "r", stdin) == nil {
        perror(path)
        return []
    }
    
    var inputArray = [String]()
    
    while let line = readLine() {
        inputArray.append(line)
    }
    return inputArray
}

func parseInput(puzzleInput: [String]) -> Dictionary<String, Bag> {
    // There are two types of strings
    
    // light red bags contain 1 bright white bag, 2 muted yellow bags.
    // ---------              --------------      --------------
    //   color                        # of other color(s)
    
    // However, there can be a line with a bag that has no contents
    // faded blue bags contain no other bags.
    // ----------              --
    //   color             No contents
    
    // every bag is described with 2 words followed by the word "bag(s)"
    // bags that contain no other bags just have the word "no"
//    let bagColorRegex = NSRegularExpression("^[a-z]* [a-z]*")
//    let bagContentsRegex = NSRegularExpression("[0-9]+ [a-z]* [a-z]*")
    
    var luggageRack: Dictionary<String, Bag> = [:]
    
    for rule in puzzleInput {
        let bagColor = rule.regex(pattern: "^[a-z]* [a-z]*")
        let bagContentsArray = rule.regex(pattern: "[0-9]+ [a-z]* [a-z]*")
        var bagContentsDict: Dictionary<String, Int> = [:]
        for bag in bagContentsArray {
            let bagComponents = bag.components(separatedBy: " ")
            let bagContentsCount = bagComponents[0]
            let bagContentsDescriptor = bagComponents[1] + " " + bagComponents[2]
            bagContentsDict[bagContentsDescriptor] = Int(bagContentsCount)
        }
        let newBag = Bag(color: bagColor[0], contents: bagContentsDict)
        luggageRack[newBag.color] = newBag
    }
    return luggageRack
}

func countBag(bags: Dictionary<String, Bag>, desiredColor: String) -> Int {
    var count: Int = 0
    for (bagKey, bagValue) in bags[desiredColor]!.contents {
        count = count + (bagValue * (countBag(bags: bags, desiredColor: bagKey) + 1))
    }
    return count
}

let puzzleInput = readFile(path: "input_7")
let bags = parseInput(puzzleInput: puzzleInput)

print("Part 2: \(countBag(bags: bags, desiredColor: "shiny gold"))")

#!/usr/bin/awk -f
# ignore empty bags
! /no other/{
        # light red bags contain 1 bright white bag, 2 muted yellow bags.
        # -> light red,bright white,muted yellow
        gsub(/( [0-9] |\.| bag| bags)/ , "")
        gsub(/ contain/, ",")

        # iterate over the rules and link bags to their parents
        rules = split($0, rule, ",")
        for (i = 2; i <= rules; ++i)
                bag[rule[i]] = bag[rule[i]] "," rule[1]
}

END {
        color = "shiny gold"
        for (;;) {
                # append the bag's direct parents to the stack
                parents = split(bag[color], parent, ",")
                for (i = 2; i <= parents; ++i)
                        stack[++ptr] = parent[i]

                color = stack[ptr--]
                if (ptr == -1)
                        break

                # use array keys to remove duplicates
                colors[color] = 1
        }

        for (i in colors)
                sum += 1

        print sum
}

#!/usr/bin/awk -f
# ignore empty bags
! /no other/{
        # light red bags contain 1 bright white bag, 2 muted yellow bags.
        # -> light red,1 bright white,2 muted yellow
        gsub(/(\.| bag| bags)/ , "")
        gsub(/( contain |, )/, ",")

        # iterate over the rules and link the bags to their contents
        # -> bags["light red"] = ,bright white,muted yellow,muted yellow
        rules = split($0, rule, ",")
        for (i = 2; i <= rules; ++i) {
                j = match(rule[i], /[a-z]/)
                num = substr(rule[i], 1, j-2)
                str = substr(rule[i], j)
                # create the actual number of bags
                for (k = 1; k <= num; ++k)
                        bags[rule[1]] = bags[rule[1]] "," str
        }
}

END {
        color = "shiny gold"
        # start at -1 to exclude shiny gold itself
        for (sum = -1; ptr >= 0; ++sum) {
                # append the bag's direct contents to the stack
                parents = split(bags[color], parent, ",")
                for (i = 2; i <= parents; ++i)
                        stack[++ptr] = parent[i]

                color = stack[ptr--]
        }

        print sum
}

for line in lines:
	container, contains = line[:-1].split(" contain ")
	container = container[:container.find(" bag")]
	if contains == "no other bags":
		continue
	contains = contains.split(", ")
	for i, contained in enumerate(contains):
		contains[i] = contained[contained.find(" ") + 1:contained.find(" bag")]
	
	for i in contains:
		if i not in containedby:
			containedby[i] = set([container])
		else:
			containedby[i].add(container)

found = set([])
def traverseBags(name):
	if name in found:
		return
	found.add(name)
	if name in containedby:
		for c in containedby[name]:
			traverseBags(c)

traverseBags("shiny gold")
print(len(found) - 1)

for line in lines:
	container, contains = line[:-1].split(" contain ")
	container = container[:container.find(" bag")]
	if contains == "no other bags":
		continue
	contains = contains.split(", ")
	for i, contained in enumerate(contains):
		val = int(contained[:contained.find(" ")])
		name = contained[contained.find(" ") + 1:contained.find(" bag")]
		contains[i] = [val, name]
	if container not in containsNums:
		containsNums[container] = {}
	myCNum = containsNums[container]
	for val,name in contains:
		if name not in myCNum:
			myCNum[name] = val
		else:
			myCNum[name] += val

# found = set([])
def traverseBags(name):
	totalContains = 0
	if name not in containsNums:
		return 1
	myCNum = containsNums[name]
	for cts in myCNum.keys():
		totalContains += traverseBags(cts) * myCNum[cts]

	return totalContains + 1

print(traverseBags("shiny gold") - 1)

function parseInput(input) {
  const contains = {}
  const containedIn = {}

  input.split('\n').forEach(line => {
    let [, color, children] = line.match(/(.*) bags contain (.*)/)

    contains[color] = []
    for (let [, num, type] of children.matchAll(/(\d+) (.+?) bags?[,.]/g)) {
      contains[color].push({ num: Number(num), type })
      ;(containedIn[type] || (containedIn[type] = [])).push(color)
    }
  })

  return { contains, containedIn }
}

export function solvePart1(input) {
  let { containedIn } = parseInput(input)

  function containers(color, set = new Set()) {
    containedIn[color]?.forEach(c => {
      set.add(c)
      containers(c, set)
    })
    return set
  }

  return containers('shiny gold').size
}

export function solvePart2(input) {
  let { contains } = parseInput(input)

  function sumBags(root) {
    return 1 + _.sum(contains[root].map(c => c.num * sumBags(c.type)))
  }

  return sumBags('shiny gold') - 1
}

#!/usr/bin/env python3

import sys
import re

OUTER_COLOR = r'([a-z]+ [a-z]+) bags contain'
INNER_COLOR = r'(?: (\d+) ([a-z]+ [a-z]+) bags?[,.])'

has_shiny_gold = set()

def shiny_gold(has_bag, color):
    global has_shiny_gold
    if color in has_bag:
        for clr in has_bag[color]:
            try:
                has_shiny_gold.add(clr)
            except KeyError:
                has_shiny_gold = {clr}
            shiny_gold(has_bag, clr)

def main():
    has_bag = {}
    count = 0

    for line in sys.stdin:
        outer_color = re.findall(OUTER_COLOR, line)[0]
        for inner_count, inner_color in re.findall(INNER_COLOR, line):
            try:
                has_bag[inner_color].add(outer_color)
            except KeyError:
                has_bag[inner_color] = {outer_color}

    shiny_gold(has_bag, "shiny gold")
    print(len(has_shiny_gold))

if __name__ == '__main__':
    main()

#!/usr/bin/env python3

import sys
import re

OUTER_COLOR = r'([a-z]+ [a-z]+) bags contain'
INNER_COLOR = r'(?: (\d+) ([a-z]+ [a-z]+) bags?[,.])'


def bags_needed(bags_inside, color):
    count = 0
    if color in bags_inside:
        for bag, num in bags_inside[color]:
            count += int(num) + (int(num) * bags_needed(bags_inside, bag))
    return count



def main():
    bags_inside = {}
    count = 0

    for line in sys.stdin:
        outer_color = re.findall(OUTER_COLOR, line)[0]
        for inner_count, inner_color in re.findall(INNER_COLOR, line):
            try:
                bags_inside[outer_color].add((inner_color, inner_count))
            except KeyError:
                bags_inside[outer_color] = {(inner_color, inner_count)}

    print(bags_needed(bags_inside, "shiny gold"))



if __name__ == '__main__':
    main()

I went ahead and built an actual tree. First I constructed the nodes individually, noting the relationships between them via their bag name. Then, once all the nodes were built I actually made real references between them, so that each node could see its children. From there I built a recursive algorithm to check if a bag contains gold anywhere among its children.

import re
#database = test_data.split('.\n')
database = input_data.split('.\n')

left_pattern = re.compile('^([a-z]+\s[a-z]+)\sbags')
right_pattern = re.compile('(\d)+\s([a-z]+\s[a-z]+)\sbags?')

class bag_node(object):
    def __init__(self, name):
        self.name = name
        self.children_count = {}
        self.children_nodes = {}
        self.contains_shiny_gold = None
    def __str__(self):
        return f'{self.name} bags contain {self.children}'
    def check_for_gold(self):
        if self.contains_shiny_gold == None:
            self.contains_shiny_gold = False
            if 'shiny gold' in self.children_count.keys():
                self.contains_shiny_gold = True
                return True
            else:
                for child in self.children_nodes.values():
                    if child.contains_shiny_gold == None:
                        child.check_for_gold()
                    if child.contains_shiny_gold == True:
                        self.contains_shiny_gold = True
        return self.contains_shiny_gold
        
bag_nodes = {}

for row in database:
    container = left_pattern.search(row).group(1)
    contents = right_pattern.findall(row)
    
    node = bag_node(container)
    
    for bag in contents:
        node.children_count[bag[1]] = bag[0]
    bag_nodes[container] = node
#TREESEMBLE
for bag in bag_nodes.values():
    for key in bag.children_count.keys():
        bag.children_nodes[key] = bag_nodes[key]
#TREEVERSAL
gold_count = 0
for bag in bag_nodes.values():
    if bag.check_for_gold():
        gold_count = gold_count + 1
print(gold_count)

I had already done the heavy lifting when I built my tree, so I just swapped out my first recursive algorithm that checked for gold for one that instead checked how many bags fit inside a given bag.

import re
#database = test_data_2.split('.\n')
database = input_data.split('.\n')

left_pattern = re.compile('^([a-z]+\s[a-z]+)\sbags')
right_pattern = re.compile('(\d)+\s([a-z]+\s[a-z]+)\sbags?')

class bag_node(object):
    def __init__(self, name):
        self.name = name
        self.children_count = {}
        self.children_nodes = {}
        self.contains_shiny_gold = None
    def __str__(self):
        return f'{self.name} bags contain {self.children}'
    def contains(self):
        if len(self.children_count.keys()) == 0:
            return 0
        else:
            contents = 0
            for bag in self.children_count.keys():
                child_multiplier = int(self.children_count[bag])
                child_contents = self.children_nodes[bag].contains()
                contents = contents + (child_multiplier * (child_contents + 1))
            return contents
bag_nodes = {}

for row in database:
    container = left_pattern.search(row).group(1)
    contents = right_pattern.findall(row)
    
    node = bag_node(container)
    
    for bag in contents:
        node.children_count[bag[1]] = bag[0]
    bag_nodes[container] = node
#TREESEMBLE
for bag in bag_nodes.values():
    for key in bag.children_count.keys():
        bag.children_nodes[key] = bag_nodes[key]
#TREEVERSAL
print(bag_nodes['shiny gold'].contains())

• For this problem, thinking about how you store your data is very important. I built an actual data structure, which is a more elaborate way of storing data than your average array or dict. Mine is a tree which stores information about the relationships between different bags. You don't HAVE to do something like this, but it might be a fun learning exercise. And it can make your data much easier to navigate if you aren't sure what you're going to need to do with it.

• My tree structure allowed me to use recursion which is a computer science technique where your build a process that needs to be able to use itself. For example, if I want to know how many bags a shiny gold bag, I need to know what bags are in it directly. Then I need to look at each of THOSE bags and see what's in THEM directly. Then I need to look at THOSE bag... and so on an so on. It can get quite tedious until you make it to the bottom of your pile of bags. Recursion helps simplify the behavior you want the computer to repeat by saying 'for every bag, look inside it' until you get to empty bags'

• As usually, there are many ways to solve this problem

const fs = require('fs');
const readline = require('readline');

let luggageArray = []

async function openFileForReading(file) {
	const fileStream = fs.createReadStream(file);

	const rl = readline.createInterface({
		input: fileStream,
		crlfDelay: Infinity
	});

	for await (const line of rl) {
		luggageArray.push(line);
	}
}

function parseContents(contents) {
	let regex = /(((\d+) (\w+) (\w+) bag[s]?[,.])+|no other bags\.)/g;
	let found = contents.matchAll(regex);
	let contentsArray = [];
	for (const match of found) {
		if (match[3] == undefined) {
			contentsArray.push({ type: 'none', amount: 0 });
		} else {
			let bagType = match[4] + ' ' + match[5];
			let bagAmount = parseInt(match[3]);
			contentsArray.push({ type: bagType, amount: bagAmount });
		}
	}
	return contentsArray;
}

function parseLine(line) {
	let regex = /^(\w+) (\w+) bags contain (.*)$/;
	let found = line.match(regex);
	let adj1 = found[1];
	let adj2 = found[2];
	let contents = found[3];
	let parsedContents = parseContents(contents);
	return { bag: adj1 + ' ' + adj2,
		contents: parsedContents };
}

function allContainedBagTypes(array, bag, containedTypes = []) {
	let currentBag = array.filter(element => element.bag == bag);
	for (const content of currentBag[0].contents) {
		if (content.type == "none") {
			return containedTypes;
		}
		if (containedTypes.indexOf(content.type) == -1) {
			containedTypes.push(content.type);
			containedTypes.concat(allContainedBagTypes(array, content.type, containedTypes));
		}
	}
	return containedTypes;
}

(async function mainExecution() {
	await openFileForReading('input.txt');
	let parsedArray = [];
	for (const line of luggageArray) {
		parsedArray.push(parseLine(line));
	}
	let containedTypes = parsedArray.map(element => allContainedBagTypes(parsedArray, element.bag));
	let containsGold = containedTypes.filter(element => element.indexOf('shiny gold') != -1);
	console.log(containsGold.length);
})();

const fs = require('fs');
const readline = require('readline');

let luggageArray = []

async function openFileForReading(file) {
	const fileStream = fs.createReadStream(file);

	const rl = readline.createInterface({
		input: fileStream,
		crlfDelay: Infinity
	});

	for await (const line of rl) {
		luggageArray.push(line);
	}
}

function parseContents(contents) {
	let regex = /(((\d+) (\w+) (\w+) bag[s]?[,.])+|no other bags\.)/g;
	let found = contents.matchAll(regex);
	let contentsArray = [];
	for (const match of found) {
		if (match[3] == undefined) {
			contentsArray.push({ type: 'none', amount: 0 });
		} else {
			let bagType = match[4] + ' ' + match[5];
			let bagAmount = parseInt(match[3]);
			contentsArray.push({ type: bagType, amount: bagAmount });
		}
	}
	return contentsArray;
}

function parseLine(line) {
	let regex = /^(\w+) (\w+) bags contain (.*)$/;
	let found = line.match(regex);
	let adj1 = found[1];
	let adj2 = found[2];
	let contents = found[3];
	let parsedContents = parseContents(contents);
	return { type: adj1 + ' ' + adj2,
		contents: parsedContents };
}

function allContainedBagTypes(array, bag, containedTypes = []) {
	console.log("DEBUG: running allContainedBagTypes on " + bag.type);
	// current position, used to get contents
	let currentBag = array.find(element => element.type == bag.type);
	let total = 0;
	// loop
	for (const contained of currentBag.contents) {
		console.log("DEBUG: contained = " + contained.type);
		// break condition
		if (contained.type == 'none') {
			console.log("DEBUG: breaking loop...");
			containedTypes.push({ type: contained.type, amount: 0 });
			return { total: 0, containedTypes };
		}
		// if value doesn't exist
		if (!containedTypes.map(element => element.type).includes(contained.type)) {
			// push it into the array as value of 0
			containedTypes.push({ type: contained.type, amount: contained.amount });
		}
		console.log("DEBUG: containedTypes:");
		console.log(containedTypes);
		let recurse = allContainedBagTypes(array, contained, containedTypes);
		console.log("DEBUG: recurse:");
		console.log(recurse);
		containedTypes[containedTypes.findIndex(element => element.type == contained.type)].amount += (recurse.containedTypes[containedTypes.findIndex(element => element.type == contained.type)].amount);
		total += (recurse.total * contained.amount) + contained.amount;;
		console.log("DEBUG: new total is: " + total);
	}
	console.log("DEBUG: returning from allContainedBagTypes...");
	return { total, containedTypes };
}

(async function mainExecution() {
	await openFileForReading('input.txt');
	let parsedArray = [];
	for (const line of luggageArray) {
		parsedArray.push(parseLine(line));
	}
	let containsArray = [];
	for (const line of parsedArray) {
		if (line.type == 'shiny gold') {
			let temp = allContainedBagTypes(parsedArray, line);
			console.log(temp);
			console.log(temp.total);
		}
	}
})();

#![feature(str_split_once)]

use std::collections::HashMap;

type BagCount = usize;
type BagColor = String;
type BagContainerMap = HashMap<BagColor, Vec<BagColor>>;
type BagContainsMap = HashMap<BagColor, Vec<(BagCount, BagColor)>>;

pub fn generate_bag_container_maps(bags: &Vec<Bag>) -> BagContainerMap {
    let mut map: HashMap<BagColor, Vec<BagColor>> = HashMap::new();

    for b in bags.iter() {
        for (_, color) in b.contents.iter() {
            match map.get_mut(color) {
                Some(v) => v.push(b.color.clone()),
                None => {
                    map.insert(color.clone(), vec![b.color.clone()]);
                }
            }
        }
    }

    map
}

pub fn count_bag_containers(color: &BagColor, bags: BagContainerMap) -> usize {
    let mut count = 0;
    let mut visited = Vec::new();
    let mut to_visit = vec![color];

    while to_visit.len() > 0 {
        let visiting = to_visit.pop().unwrap();

        match bags.get(visiting) {
            Some(containers) => {
                for c in containers {
                    if !to_visit.contains(&c) && !visited.contains(&c) {
                        to_visit.push(c);
                        count += 1;
                    }
                }
            },
            None => ()
        }

        visited.push(visiting)
    }

    count
}

pub fn generate_bag_contains_maps(bags: &Vec<Bag>) -> BagContainsMap {
    let mut map = HashMap::new();

    for b in bags {
        map.insert(b.color.clone(), b.contents.clone());
    }

    map
}

pub fn count_bag_contents(color: &BagColor, bags: &BagContainsMap) -> usize {
    let contents = bags.get(color).unwrap();
    if contents.len() == 0 {
        return 0
    } else {
        let mut total_count = 0;
        for (count, color) in contents.iter() {
            // Count of the bags inside this bag
            total_count += count;

            // Count of the bags inside the bags inside this bag
            total_count += count_bag_contents(color, bags) * count;
        }

        return total_count;
    }
}


#[derive(PartialEq, Eq, Debug)]
pub struct Bag {
    pub color: BagColor,
    pub contents: Vec<(BagCount, BagColor)>
}

impl Bag {
    pub fn from_line(line: &str) -> Bag {
        let (color, contains) = line.split_once(" bags contain ").unwrap();

        if contains == "no other bags." {
            return Bag { color: color.to_string(), contents: Vec::new() };
        } else {
            let mut contents = Vec::new();

            for b in contains.split(',') {
                let mut bag_words = b.split_whitespace();

                let count = bag_words.next().unwrap().parse::<usize>().expect("Expected number of bags.");
                let c = format!("{} {}", bag_words.next().unwrap(), bag_words.next().unwrap());

                contents.push((count, c));
            }

            return Bag { color: color.to_string(), contents: contents };
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_contents_one() {
        let line = "bright white bags contain 1 shiny gold bag.";
        let expect = Bag { color: "bright white".to_string(), contents: vec![(1, "shiny gold".to_string())] };

        assert_eq!(Bag::from_line(&line), expect);
    }

    #[test]
    fn test_contents_many() {
        let line = "vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.";
        let expect = Bag { color: "vibrant plum".to_string(), contents: vec![(5, "faded blue".to_string()), (6, "dotted black".to_string())] };

        assert_eq!(Bag::from_line(&line), expect);
    }

    #[test]
    fn test_contents_none() {
        let line = "dotted black bags contain no other bags.";
        let expect = Bag { color: "dotted black".to_string(), contents: vec![] };

        assert_eq!(Bag::from_line(&line), expect);
    }
}

use std::io;
use std::io::prelude::*;

use day7::{
    Bag,
    generate_bag_container_maps,
    count_bag_containers,
    generate_bag_contains_maps,
    count_bag_contents,
};

fn main() {
    let stdin = io::stdin();
    let lines: Vec<String> = stdin
        .lock()
        .lines()
        .collect::<Result<_, _>>()
        .unwrap();

    let mut bags = Vec::new();

    for line in lines {
        bags.push(Bag::from_line(&line));
    }

    let bag_map = generate_bag_container_maps(&bags);
    let shiny_gold_count = count_bag_containers(&("shiny gold".to_string()), bag_map);

    let contains_map = generate_bag_contains_maps(&bags);
    let part_2 = count_bag_contents(&("shiny gold".to_string()), &contains_map);

    println!("Part 1: {}", shiny_gold_count);
    println!("Part 2: {}", part_2);
}

#!/usr/bin/env ruby
require "set"

input = File.read(ARGV[0] || "test2.txt")

rules = {}

input.lines.each do |line|
  outer_bag, inner = line.split("bags contain").map(&:strip)
  inner = inner.gsub(/\./,'')
            .split(',')
            .map(&:strip)
            .reject{ |s| s == "no other bags" }
            .map { |s| c = s.match(/(\d+)\s(\w+)\s(\w+)\s(.+)/).captures
                       [c[0].to_i, c[1] << " " << c[2]] }

  rules[outer_bag] = inner
end

def find_containers(rules, target)
  containers = Set.new
  rules.each do |container, contained|
    if contained.any? { |rule| rule[1] == target }
      containers.add(container)
      containers += find_containers(rules, container)
    end
  end
  return containers
end

puts "Part 1"
puts find_containers(rules, "shiny gold").size

def score_bag(rules, target)
  rules[target].reduce(1) do |sum, rule|
    sum + (rule[0] * score_bag(rules, rule[1]))
  end
end

puts "Part 2"
puts score_bag(rules, "shiny gold") - 1 #sub one for the gold bag itself

use regex::Regex;
use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;

#[derive(Debug, Clone)]
struct Bag {
    name: String,
    contains: Vec<(u32, Rc<RefCell<Bag>>)>,
}

pub fn day07(input: String) {
    let mut bags: HashMap<String, Rc<RefCell<Bag>>> = HashMap::new();

    let input: Vec<Vec<_>> = input
        .lines()
        .map(|x| x.split("contain").collect())
        .collect();

    let remove_bag_suffix = Regex::new(r" (bag|bags)\.*$").unwrap();

    for line in input {
        let name = remove_bag_suffix.replace(line[0].trim(), "");
        let contains: Vec<_> = line[1]
            .split(",")
            .map(|x| remove_bag_suffix.replace(x.trim(), ""))
            .collect();
        let contains = contains
            .iter()
            .map(|x| x.splitn(2, " ").collect::<Vec<_>>())
            .map(|x| {
                if x[0] == "no" {
                    None
                } else {
                    Some((x[0].parse::<u32>().unwrap(), x[1]))
                }
            })
            .filter(|&x| x != None)
            .map(|x| x.unwrap())
            .map(|(num, x)| {
                let bag = if bags.contains_key(&String::from(x)) {
                    bags.get(&String::from(x)).unwrap().clone()
                } else {
                    bags.insert(
                        String::from(x),
                        Rc::new(RefCell::new(Bag {
                            name: String::from(x),
                            contains: vec![],
                        })),
                    );
                    bags.get(&String::from(x)).unwrap().clone()
                };
                (num, bag)
            })
            .collect::<Vec<_>>();

        let bag = if bags.contains_key(&String::from(name.clone())) {
            bags.get(&String::from(name)).unwrap().clone()
        } else {
            bags.insert(
                String::from(name.clone()),
                Rc::new(RefCell::new(Bag {
                    name: String::from(name.clone()),
                    contains: vec![],
                })),
            );
            bags.get(&String::from(name)).unwrap().clone()
        };

        bag.borrow_mut().contains = contains;
    }

    fn find_recurse(bag: Rc<RefCell<Bag>>) -> bool {
        bag.borrow().contains.iter().fold(false, |acc, val| {
            acc | (val.1.borrow().name == "shiny gold")
                | (find_recurse(Rc::new(RefCell::new(val.1.borrow().clone()))))
        })
    }

    let res = bags.iter().fold(0, |acc, (_, bag)| {
        if find_recurse(bag.clone()) {
            acc + 1
        } else {
            acc
        }
    });

    println!("{}", res);

    fn count_recurse(bag: Rc<RefCell<Bag>>) -> u32 {
        bag.borrow().contains.iter().fold(1, |acc, val| {
            acc + val.0 * count_recurse(Rc::new(RefCell::new(val.1.borrow().clone())))
        })
    }

    let res = Rc::new(RefCell::new(
        bags.get("shiny gold").unwrap().borrow().clone(),
    ));

    println!("{}", count_recurse(res) - 1);
}

(define (get-lines parse-line)
  (with-input-from-file "input"
    (lambda ()
      (let loop ((line (read-line))
                 (lines '()))
        (if (eof-object? line)
            (reverse lines)
            (loop (read-line)
                  (cons (parse-line line) lines)))))))

(define (try-match-exact pattern string)
  (regsexp-match-string (compile-regsexp
                         (append '(seq (line-start))
                                 pattern
                                 '((line-end))))
                        string))

(define (bag-str->symbol str)
  (string->symbol (string-replace (string-downcase str)
                                  #\space
                                  #\-)))

(define (parse-bag line)
  (let* ((bag-name '(seq (* (char-in alphabetic)) #\space (* (char-in alphabetic))))
         (matches (try-match-exact
                   `((group k ,bag-name)
                     #\space
                     "bag" (? #\s)
                     " contain"
                     (alt " no other bags."
                          (* (seq #\space (group n (* (char-in numeric)))
                                  #\space (group b ,bag-name)
                                  #\space "bag" (? #\s) (alt #\, #\.)))))
                   line)))
    (if (not matches) (begin (display "Parse failed: ") (display line) (newline))
        (let* ((groups (cddr matches))
               (bag (bag-str->symbol (cdar groups)))
               (inner (cdr groups)))
          (cons bag
                (if (null? inner) '()
                    (map (lambda (n b)
                           (cons (string->number (cdr n))
                                 (bag-str->symbol (cdr b))))
                         (filter (lambda (x) (eq? (car x) 'n)) inner)
                         (filter (lambda (x) (eq? (car x) 'b)) inner))))))))

(define (contains? alst bag target)
  (if (eq? bag target) #t
      (any (lambda (n-bag-pair) (contains? alst (cdr n-bag-pair) target))
           (cdr (assq bag alst)))))

(define (one lines)
  (- (count (lambda (bag) (contains? lines (car bag) 'shiny-gold))
            lines)
     1))

(define (sum lst)
  (fold + 0 lst))

(define (bags-in alst bag)
  (let ((contents (cdr (assq bag alst))))
    (if (null? contents) 1
        (+ (sum (map (lambda (n-bag-pair)
                       (* (car n-bag-pair)
                          (bags-in alst (cdr n-bag-pair))))
                     contents))
           1))))

(define (two lines)
  (- (bags-in lines 'shiny-gold)
     1))

(define (run lines)
    (display "One: ")
    (display (one lines))
    (newline)
    (display "Two: ")
    (display (two lines))
    (newline))

(run (get-lines parse-bag))

(define (make-memoized-contains? alst target)
  (let ((memo-table (make-strong-eq-hash-table)))
    (define (contains? bag)
      (if (eq? bag target) #t
          (let ((memo-val (hash-table/get memo-table bag '())))
            (if (not (null? memo-val)) memo-val
                (let ((result (any (lambda (n-bag-pair) (contains? (cdr n-bag-pair)))
                                   (cdr (assq bag alst)))))
                  (hash-table/put! memo-table bag result)
                  result)))))
    contains?))

(define (one lines)
  (let ((contains? (make-memoized-contains? lines 'shiny-gold))
        (bag-list (filter (lambda (bag) (not (eq? bag 'shiny-gold)))
                          (map car lines))))
    (count contains? bag-list)))

# Find how many bags can hide a target bag, kinda recursively
function hide_bag(target, bags, current)

    # We can't hide a bag in itself
    if current == target
        return false
    end
    
    # Can't hide a bag in a bag that's not real
    curr_contents = get(bags, current, nothing)
    if isa(curr_contents, Nothing)
        return false
    end

    # Check if our current bag holds our target, if not, check the bags it does hold
    curr_bag_types = [content[1] for content in curr_contents]
    if target in curr_bag_types
        return true
    else
        return any([hide_bag(target, bags, new_bag) for new_bag in curr_bag_types])
    end

end

function main()

    # Get the input
    input = []
    open("Day07/input.txt") do fp
        input = split.(readlines(fp), ' ')
    end

    # Do the gross work of parsing the input into a dictionary
    bag_mapping = Dict()
    for line in input
        bag = line[1] * " " * line[2]

        if line[5] == "no"
            bag_mapping[bag] = nothing
            continue
        end

        idx = 5
        contents = []
        # This could probably be a for loop, but eh
        while idx < length(line)
            number = parse(Int, line[idx])
            inside_bag = line[idx+1] * " " * line[idx+2]
            push!(contents, (inside_bag, number))
            idx += 4
        end
        bag_mapping[bag] = contents
    end

    # Calculate and print results
    result_1 = count([hide_bag("shiny gold", bag_mapping, bag) for bag in keys(bag_mapping)])
    println("Result for part 1 is ", result_1)
    
end

main()

@@ -6,7 +6,7 @@ function hide_bag(target, bags, current)
         return false
     end
     
-    # Can't hide a bag in a bag that's not real
+    # Can't hide a bag in a bag that's not real or empty
     curr_contents = get(bags, current, nothing)
     if isa(curr_contents, Nothing)
         return false
@@ -22,6 +22,22 @@ function hide_bag(target, bags, current)
 
 end
 
+# Find out how many bags must be in a bag, kinda recursively
+function number_contained(bags, current)
+
+    # If a bag doesn't have anything in it, it's 1 bag
+    curr_contents = get(bags, current, nothing)
+    if isa(curr_contents, Nothing)
+        return 1
+    else
+        # Otherwise it's one bag plus the quantities of bags it contains times
+        # how many bags they in turn contain
+        curr_bag_types = [content[1] for content in curr_contents]
+        curr_bag_nums = [content[2] for content in curr_contents]
+        return 1 + sum(curr_bag_nums .* [number_contained(bags, type) for type in curr_bag_types])
+    end
+end
+
 function main()
 
     # Get the input
@@ -55,6 +71,10 @@ function main()
     # Calculate and print results
     result_1 = count([hide_bag("shiny gold", bag_mapping, bag) for bag in keys(bag_mapping)])
     println("Result for part 1 is ", result_1)
+
+    # This is a hack to discount the very top bag, but eh
+    result_2 = number_contained(bag_mapping, "shiny gold") - 1
+    println("Result for part 2 is ", result_2)
     
 end

# PC
BenchmarkTools.Trial: 
  memory estimate:  54.36 MiB
  allocs estimate:  1206470
  --------------
  minimum time:     154.670 ms (1.68% GC)
  median time:      157.183 ms (1.66% GC)
  mean time:        157.939 ms (2.00% GC)
  maximum time:     164.645 ms (1.60% GC)
  --------------
  samples:          32
  evals/sample:     1
# Pi
BenchmarkTools.Trial: 
  memory estimate:  54.36 MiB
  allocs estimate:  1206470
  --------------
  minimum time:     1.447 s (1.59% GC)
  median time:      1.452 s (1.58% GC)
  mean time:        1.468 s (1.56% GC)
  maximum time:     1.522 s (1.47% GC)
  --------------
  samples:          4
  evals/sample:     1

# PC
BenchmarkTools.Trial: 
  memory estimate:  54.36 MiB
  allocs estimate:  1206470
  --------------
  minimum time:     137.153 ms (2.24% GC)
  median time:      143.299 ms (2.16% GC)
  mean time:        143.782 ms (2.69% GC)
  maximum time:     155.217 ms (2.79% GC)
  --------------
  samples:          35
  evals/sample:     1
# Pi
BenchmarkTools.Trial: 
  memory estimate:  54.36 MiB
  allocs estimate:  1206470
  --------------
  minimum time:     1.290 s (1.81% GC)
  median time:      1.295 s (1.79% GC)
  mean time:        1.312 s (1.76% GC)
  maximum time:     1.366 s (1.66% GC)
  --------------
  samples:          4
  evals/sample:     1

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;

extern crate regex;
use regex::Regex;

extern crate itertools;
use itertools::Itertools;

struct Regulation {
    color: String,
    contains: Vec<Bag>,
}
impl Regulation {
    pub fn new(input: &str) -> Regulation {
        let parts: Vec<_> = input.split(" contain ").collect();

        let re = Regex::new(r"^(\w+ \w+) bags$").unwrap();
        let matches = re.captures(&parts[0]).unwrap();
        let color: String = matches[1].parse().unwrap();

        let contains: Vec<Bag> = match parts[1] {
            "no other bags." => Vec::new(),
            _ => parts[1].split(",").map(|x| Bag::from_string(x)).collect(),
        };

        Regulation {
            color: color,
            contains: contains,
        }
    }
}

struct Bag {
    color: String,
    number: usize,
}
impl Bag {
    pub fn from_string(input: &str) -> Bag {
        let re = Regex::new(r"(\d+) (\w+ \w+) bag").unwrap();
        let matches = re.captures(input).unwrap();
        let number: usize = matches[1].parse().unwrap();
        let color: String = matches[2].parse().unwrap();
        Bag {
            color: color,
            number: number,
        }
    }
}

fn possible_containers(regs: &[Regulation], containers_for: &str) -> Vec<String> {
    let mut containers: Vec<String> = Vec::new();
    let applicable_regs = regs.iter().filter(|r| r.contains.iter().any(|b| b.color == containers_for));
    for reg in applicable_regs {
        containers.push(reg.color.clone()); // direct containers
        containers.append(&mut possible_containers(&regs, &reg.color)); // recursive containers
    }
    containers
}

fn bag_count(regs: &[Regulation], containers_for: &str) -> usize {
    regs
        .iter()
        .filter(|r| r.color == containers_for)
        .map(|r| {
            r.contains.iter().map(|x| x.number).sum::<usize>() + // direct containers
            r.contains.iter().map(|c| &c.number*bag_count(&regs, &c.color)).sum::<usize>() // recursive containers
        })
        .sum()
}

fn day07(input: &str) {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };

    let regs: Vec<Regulation> = input.iter().map(|x| Regulation::new(x)).collect();

    // Part 1
    let part1 = possible_containers(&regs, "shiny gold").iter().unique().count();
    println!("Part 1: {}", part1); // 348

    // Part 2
    let part2 = bag_count(&regs, "shiny gold");
    println!("Part 2: {}", part2); // 18885

}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    day07(&filename);
}