--- /dev/null
+#!/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)))