2020-12-07 09:52:51 +01:00
#![ feature(test) ]
2020-12-10 14:44:42 +01:00
use std ::collections ::HashSet ;
2020-12-07 09:52:51 +01:00
extern crate test ;
2020-12-10 14:44:42 +01:00
use aoc2020 ::common ::* ;
2020-12-07 09:52:51 +01:00
2020-12-07 12:30:39 +01:00
const COLOR : & str = " shiny gold " ;
2020-12-07 09:52:51 +01:00
fn main ( ) {
let input = parse_input ( & read_input ( ) ) ;
2020-12-07 12:30:39 +01:00
println! ( " Part 1: {} " , part1 ( & input , COLOR , & mut HashSet ::new ( ) ) . len ( ) ) ;
println! ( " Part 2: {} " , part2 ( & input , COLOR ) ) ;
2020-12-07 09:52:51 +01:00
}
#[ derive(Debug) ]
struct Bag {
color : String ,
contents : Vec < InnerBag > ,
}
#[ derive(Debug) ]
struct InnerBag {
qty : usize ,
color : String ,
}
// this is dumb
impl From < & str > for Bag {
fn from ( raw : & str ) -> Self {
let mut split = raw . split ( " , " ) ;
Self {
color : split . next ( ) . unwrap ( ) . to_string ( ) ,
contents : split
. filter_map ( | s | {
if s . starts_with ( " no other " ) {
None
} else {
let mut split = s . splitn ( 2 , ' ' ) ;
Some ( InnerBag {
qty : split . next ( ) . unwrap ( ) . parse ( ) . unwrap ( ) ,
color : split . next ( ) . unwrap ( ) . to_owned ( ) ,
} )
}
} )
. collect ( ) ,
}
}
}
fn read_input ( ) -> String {
2020-12-10 14:44:42 +01:00
read_file ( 7 )
2020-12-07 09:52:51 +01:00
}
2020-12-07 12:14:45 +01:00
fn part1 < ' a , ' b > ( bags : & ' b [ Bag ] , color : & str , seen : & ' a mut HashSet < & ' b str > ) -> & ' a mut HashSet < & ' b str > {
2020-12-07 12:09:30 +01:00
for bag in bags . iter ( ) . filter ( | bag | bag . contents . iter ( ) . any ( | b | b . color = = color ) ) {
2020-12-07 12:14:45 +01:00
seen . insert ( & bag . color ) ;
2020-12-07 12:02:51 +01:00
part1 ( bags , & bag . color , seen ) ;
2020-12-07 09:52:51 +01:00
}
2020-12-07 12:02:51 +01:00
seen
2020-12-07 09:52:51 +01:00
}
fn part2 ( bags : & [ Bag ] , color : & str ) -> usize {
bags . iter ( )
. filter ( | bag | bag . color = = color )
. map ( | bag | bag . contents . iter ( ) . map ( | c | ( part2 ( bags , & c . color ) * c . qty ) + c . qty ) . sum ::< usize > ( ) )
. sum ( )
}
fn parse_input ( s : & str ) -> Vec < Bag > {
s . replace ( " bags contain " , " , " )
2020-12-10 12:44:07 +01:00
. replace ( " bags " , " " )
. replace ( " bag " , " " )
2020-12-07 09:52:51 +01:00
. replace ( '.' , " " )
. lines ( )
2020-12-07 12:09:30 +01:00
. map ( Bag ::from )
2020-12-07 09:52:51 +01:00
. collect ( )
}
#[ cfg(test) ]
mod tests {
use super ::* ;
2020-12-10 14:01:25 +01:00
use aoc2020 ::* ;
2020-12-07 09:52:51 +01:00
use test ::black_box ;
2020-12-10 16:41:54 +01:00
use paste ::paste ;
2020-12-07 09:52:51 +01:00
const TEST_INPUT : & str = " light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags , 4 muted yellow bags .
bright white bags contain 1 shiny gold bag .
muted yellow bags contain 2 shiny gold bags , 9 faded blue bags .
shiny gold bags contain 1 dark olive bag , 2 vibrant plum bags .
dark olive bags contain 3 faded blue bags , 4 dotted black bags .
vibrant plum bags contain 5 faded blue bags , 6 dotted black bags .
faded blue bags contain no other bags .
dotted black bags contain no other bags . " ;
const TEST_INPUT_2 : & str = " shiny gold bags contain 2 dark red bags.
dark red bags contain 2 dark orange bags .
dark orange bags contain 2 dark yellow bags .
dark yellow bags contain 2 dark green bags .
dark green bags contain 2 dark blue bags .
dark blue bags contain 2 dark violet bags .
dark violet bags contain no other bags . " ;
2020-12-10 16:41:54 +01:00
#[ test ]
fn part1_test ( ) {
let input = parse_input ( TEST_INPUT ) ;
assert_eq! ( part1 ( & input , COLOR , & mut HashSet ::new ( ) ) . len ( ) , 4 ) ;
}
2020-12-07 09:52:51 +01:00
#[ test ]
fn part2_test ( ) {
let input = parse_input ( TEST_INPUT ) ;
2020-12-07 12:30:39 +01:00
assert_eq! ( part2 ( & input , COLOR ) , 32 ) ;
2020-12-07 09:52:51 +01:00
let input = parse_input ( TEST_INPUT_2 ) ;
2020-12-07 12:30:39 +01:00
assert_eq! ( part2 ( & input , COLOR ) , 126 ) ;
2020-12-07 09:52:51 +01:00
}
2020-12-10 14:01:25 +01:00
bench_input! ( len = = 594 ) ;
2020-12-07 09:52:51 +01:00
#[ bench ]
fn bench_part1 ( b : & mut test ::Bencher ) {
let bags = parse_input ( & read_input ( ) ) ;
2020-12-07 12:30:39 +01:00
b . iter ( | | assert_eq! ( part1 ( black_box ( & bags ) , COLOR , & mut HashSet ::new ( ) ) . len ( ) , 226 ) )
2020-12-07 09:52:51 +01:00
}
2020-12-10 16:41:54 +01:00
bench! ( part2 ( COLOR ) = = 9569 ) ;
2020-12-07 09:52:51 +01:00
}