X-Git-Url: https://git.sommitrealweird.co.uk/advent-of-code-2020.git/blobdiff_plain/fe0197cb1dc8f701b69ce52b9acb445351557c8d..b33a1377092119697b3ab349a7a4c066c7471879:/day07/bags.sh

diff --git a/day07/bags.sh b/day07/bags.sh
new file mode 100755
index 0000000..5be32b8
--- /dev/null
+++ b/day07/bags.sh
@@ -0,0 +1,164 @@
+#!/bin/bash
+
+declare -A contained_by
+declare -A contains
+shopt -s extglob
+
+exec 3<input.txt
+
+while read -u 3 line; do
+    bag_name=${line% bags contain *}
+    contain=${line#* bags contain }
+    contain=${contain%.}
+    while [ ${#contain} -gt 0 ]; do
+        next_bag=${contain%%,*}
+        if [ ${#next_bag} -eq 0 ]; then
+            next_bag=${contain%%.}
+        fi
+        contain=${contain#"$next_bag"}
+        contain=${contain#[,.]}
+        contain=${contain# }
+
+        bag_count=${next_bag%% *}
+        next_bag=${next_bag#$bag_count }
+        next_bag=${next_bag% bag*}
+        next_bag=${next_bag#,}
+
+        if [ ${contains[$bag_name]+a} ]; then
+            contains[$bag_name]+=":$bag_count,$next_bag"
+        else
+            contains[$bag_name]="$bag_count,$next_bag"
+        fi
+
+        if [ ${contained_by[$next_bag]+a} ]; then
+            contained_by[$next_bag]+=",$bag_name"
+        else
+            contained_by[$next_bag]="$bag_name"
+        fi
+    done
+done
+
+declare -A temp
+declare -a new_bags
+declare -a new_new_bags
+
+looking_for="shiny gold"
+bag_name="$looking_for"
+
+IFS=","
+for bag in ${contained_by["$bag_name"]}; do
+    if ! [ ${temp["$bag"]+a} ]; then
+        temp["$bag"]="1"
+        new_bags+=("$bag")
+    fi
+done
+
+while [ ${#new_bags[@]} -gt 0 ]; do
+    for bag in "${new_bags[@]}"; do
+        if [ ${contained_by["$bag"]+a} ]; then
+            for bag2 in ${contained_by["$bag"]}; do
+                if ! [ ${temp["$bag2"]+a} ]; then
+                    new_new_bags+=("$bag2")
+                    temp["$bag2"]=1
+                fi
+            done
+        fi
+    done
+    unset new_bags
+    new_bags=("${new_new_bags[@]}")
+    unset new_new_bags
+    declare -a new_new_bags
+done
+
+echo "Found ${#temp[@]} bags that hold ${looking_for}"
+
+get_count() {
+    local bag_name=$1
+    local count=0
+    if ! [ ${contains[$bag_name]+a} ]; then
+        echo 0
+        return 0
+    fi
+    IFS=":"
+    for bag_details in ${contains[$bag_name]}; do
+        num=${bag_details%,*}
+        bag=${bag_details#*,}
+        addcount=$((($(get_count $bag)+1)*num))
+        count=$((count+$addcount))
+    done
+
+    echo $count
+}
+
+# now looking for how many bags in bags we're looking for
+echo "Contains $(get_count $looking_for) bags"
+
+exit 0
+
+#!/usr/bin/python3
+
+import re
+
+contained_by={}
+contains={}
+
+for rule in open("input.txt", "r"):
+    rule=rule.rstrip()
+    print("Rule: {}".format(rule))
+    m=re.match("^(.*?) bag(s|) contain (.*)$", rule)
+    if m:
+        bag=m.group(1)
+        contain=m.group(3).split(", ")
+        for contained in contain:
+            m2=re.match('^([0-9]*) (.*?) bag(s|).*$', contained)
+            if m2 is not None:
+                bag_count=int(m2.group(1))
+                bag_name=m2.group(2)
+                if not bag in contains:
+                    contains[bag]=[]
+                contains[bag].append((bag_count, bag_name))
+                if not bag_name in contained_by:
+                    contained_by[bag_name] = []
+                if not bag in contained_by[bag_name]:
+                    contained_by[bag_name].append(bag)
+
+looking_for="shiny gold"
+
+bags=[]
+for bag in contained_by[looking_for]:
+    if bag not in bags:
+        bags.append(bag)
+
+print(bags)
+
+new_bags=True
+new_bag_list=[b for b in bags]
+new_new_bag_list=[]
+while new_bags:
+    for bag1 in new_bag_list:
+        if bag1 not in contained_by:
+            continue
+        for bag2 in contained_by[bag1]:
+            if bag2 not in bags:
+                new_new_bag_list.append(bag2)
+                bags.append(bag2)
+    if (len(new_new_bag_list) > 0):
+        new_bag_list=[b for b in new_new_bag_list]
+        new_new_bag_list=[]
+        new_bags=True
+    else:
+        new_bag_list=[]
+        new_bags=False
+
+print("Found {} bags that can contain {} bags".format(len(bags), looking_for))
+
+def get_count(bag_name):
+    count=0
+    if not bag_name in contains:
+        return 0
+    for (num,bag) in contains[bag_name]:
+        count+=(get_count(bag)+1)*num
+    return count
+
+# now looking for how many bags in bags we're looking for
+print("Contains {} bags".format(get_count(looking_for)))