day07/bags.sh

   1 #!/bin/bash
   2
   3 declare -A contained_by
   4 declare -A contains
   5 shopt -s extglob
   6
   7 exec 3<input.txt
   8
   9 while read -u 3 line; do
  10     bag_name=${line% bags contain *}
  11     contain=${line#* bags contain }
  12     contain=${contain%.}
  13     while [ ${#contain} -gt 0 ]; do
  14         next_bag=${contain%%,*}
  15         if [ ${#next_bag} -eq 0 ]; then
  16             next_bag=${contain%%.}
  17         fi
  18         contain=${contain#"$next_bag"}
  19         contain=${contain#[,.]}
  20         contain=${contain# }
  21
  22         bag_count=${next_bag%% *}
  23         next_bag=${next_bag#$bag_count }
  24         next_bag=${next_bag% bag*}
  25         next_bag=${next_bag#,}
  26
  27         if [ ${contains[$bag_name]+a} ]; then
  28             contains[$bag_name]+=":$bag_count,$next_bag"
  29         else
  30             contains[$bag_name]="$bag_count,$next_bag"
  31         fi
  32
  33         if [ ${contained_by[$next_bag]+a} ]; then
  34             contained_by[$next_bag]+=",$bag_name"
  35         else
  36             contained_by[$next_bag]="$bag_name"
  37         fi
  38     done
  39 done
  40
  41 declare -A temp
  42 declare -a new_bags
  43 declare -a new_new_bags
  44
  45 looking_for="shiny gold"
  46 bag_name="$looking_for"
  47
  48 IFS=","
  49 for bag in ${contained_by["$bag_name"]}; do
  50     if ! [ ${temp["$bag"]+a} ]; then
  51         temp["$bag"]="1"
  52         new_bags+=("$bag")
  53     fi
  54 done
  55
  56 while [ ${#new_bags[@]} -gt 0 ]; do
  57     for bag in "${new_bags[@]}"; do
  58         if [ ${contained_by["$bag"]+a} ]; then
  59             for bag2 in ${contained_by["$bag"]}; do
  60                 if ! [ ${temp["$bag2"]+a} ]; then
  61                     new_new_bags+=("$bag2")
  62                     temp["$bag2"]=1
  63                 fi
  64             done
  65         fi
  66     done
  67     unset new_bags
  68     new_bags=("${new_new_bags[@]}")
  69     unset new_new_bags
  70     declare -a new_new_bags
  71 done
  72
  73 echo "Found ${#temp[@]} bags that hold ${looking_for}"
  74
  75 get_count() {
  76     local bag_name=$1
  77     local count=0
  78     if ! [ ${contains[$bag_name]+a} ]; then
  79         echo 0
  80         return 0
  81     fi
  82     IFS=":"
  83     for bag_details in ${contains[$bag_name]}; do
  84         num=${bag_details%,*}
  85         bag=${bag_details#*,}
  86         addcount=$((($(get_count $bag)+1)*num))
  87         count=$((count+$addcount))
  88     done
  89
  90     echo $count
  91 }
  92
  93 # now looking for how many bags in bags we're looking for
  94 echo "Contains $(get_count $looking_for) bags"
  95
  96 exit 0
  97
  98 #!/usr/bin/python3
  99
 100 import re
 101
 102 contained_by={}
 103 contains={}
 104
 105 for rule in open("input.txt", "r"):
 106     rule=rule.rstrip()
 107     print("Rule: {}".format(rule))
 108     m=re.match("^(.*?) bag(s|) contain (.*)$", rule)
 109     if m:
 110         bag=m.group(1)
 111         contain=m.group(3).split(", ")
 112         for contained in contain:
 113             m2=re.match('^([0-9]*) (.*?) bag(s|).*$', contained)
 114             if m2 is not None:
 115                 bag_count=int(m2.group(1))
 116                 bag_name=m2.group(2)
 117                 if not bag in contains:
 118                     contains[bag]=[]
 119                 contains[bag].append((bag_count, bag_name))
 120                 if not bag_name in contained_by:
 121                     contained_by[bag_name] = []
 122                 if not bag in contained_by[bag_name]:
 123                     contained_by[bag_name].append(bag)
 124
 125 looking_for="shiny gold"
 126
 127 bags=[]
 128 for bag in contained_by[looking_for]:
 129     if bag not in bags:
 130         bags.append(bag)
 131
 132 print(bags)
 133
 134 new_bags=True
 135 new_bag_list=[b for b in bags]
 136 new_new_bag_list=[]
 137 while new_bags:
 138     for bag1 in new_bag_list:
 139         if bag1 not in contained_by:
 140             continue
 141         for bag2 in contained_by[bag1]:
 142             if bag2 not in bags:
 143                 new_new_bag_list.append(bag2)
 144                 bags.append(bag2)
 145     if (len(new_new_bag_list) > 0):
 146         new_bag_list=[b for b in new_new_bag_list]
 147         new_new_bag_list=[]
 148         new_bags=True
 149     else:
 150         new_bag_list=[]
 151         new_bags=False
 152
 153 print("Found {} bags that can contain {} bags".format(len(bags), looking_for))
 154
 155 def get_count(bag_name):
 156     count=0
 157     if not bag_name in contains:
 158         return 0
 159     for (num,bag) in contains[bag_name]:
 160         count+=(get_count(bag)+1)*num
 161     return count
 162
 163 # now looking for how many bags in bags we're looking for
 164 print("Contains {} bags".format(get_count(looking_for)))