Advent of Code 2020 day16
part1
class: 1-3 or 5-7
row: 6-11 or 33-44
seat: 13-40 or 45-50
your ticket:
7,1,14
nearby tickets:
7,3,47
40,4,50
55,2,20
38,6,12
のような入力が与えられる。
最初に各fieldの範囲の条件が 1-3 or 5-7 のような形で与えられる。境界を含む「1以上3以下 または 5以上7以下」という意味のもの。
次にyour ticketの数値列が与えられ、そこからは他人たちのticket数値列。
part1はまず、完全にinvalidなticketを探す、という問題。どのfieldの条件にも当てはまらない数値が含まれているので、それを見つける。
上の例では 4, 55, 12 という数値が 最初の3つのfieldで示される範囲どれにも該当しない。のでそれらを足し合わせた 71 が解となる。
まずは入力のparse。part1では不要なものもあるけどとりあえず全部取得しておく。
struct Solution {
rules: Vec<(String, Vec<(u32, u32)>)>,
ticket: Vec<u32>,
nearby: Vec<Vec<u32>>,
}
impl Solution {
fn new(inputs: Vec<String>) -> Self {
let mut rules = Vec::new();
let mut nearby = Vec::new();
let mut ticket = Vec::new();
let mut read_nearby = false;
for line in inputs.iter().filter(|&s| !s.is_empty()) {
if line.starts_with(char::is_numeric) {
let values = line.split(',').filter_map(|s| s.parse().ok()).collect();
if read_nearby {
nearby.push(values);
} else {
ticket.extend(values);
}
} else if line.ends_with(char::is_numeric) {
let kv: Vec<&str> = line.split(": ").collect();
let ranges: Vec<(u32, u32)> = kv[1]
.split(" or ")
.filter_map(|range| {
if let Some(minmax) = range
.split('-')
.map(|s| s.parse::<u32>().ok())
.collect::<Option<Vec<u32>>>()
{
Some((minmax[0], minmax[1]))
} else {
None
}
})
.collect();
rules.push((kv[0].to_string(), ranges));
}
if line.starts_with("nearby") {
read_nearby = true;
}
}
Self {
rules,
ticket,
nearby,
}
}
}
で、いよいよinvalidなvalueを探していく。すべてのticketsのすべての数値についてそれぞれすべてのfieldの範囲内かチェックしていっても可能だが、値の範囲がせいぜい3桁なので、可能な範囲を示すVecを作ってしまっても良さそう。
最初にすべてのfieldの範囲の数値に関して取り得るかどうかをセットしてしまえば、後ですべてのnearby ticketsの値を調べるときにはvalidかどうかのチェックが
fn solve_1(&self) -> u64 {
let max = self
.rules
.iter()
.filter_map(|rule| rule.1.iter().map(|&range| range.1).max())
.max()
.unwrap();
let mut v: Vec<bool> = vec![false; max as usize + 1];
for (_, ranges) in self.rules.iter() {
for &r in ranges.iter() {
(r.0..=r.1).for_each(|i| v[i as usize] = true);
}
}
let mut ret = 0;
for ticket in self.nearby.iter() {
for &val in ticket.iter() {
if val > max || !v[val as usize] {
ret += val as u64;
}
}
}
ret
}
part2
ではいよいよ、自分のticketの数値がそれぞれどのfieldに該当するものなのかを特定したい。自分のもの含めすべてのticketsは固定順のfieldになっている。part1で求めた完全にinvalidな値を持つnearby ticketsはすべて無視する、とのこと。
例として
class: 0-1 or 4-19
row: 0-5 or 8-19
seat: 0-13 or 16-19
your ticket:
11,12,13
nearby tickets:
3,9,18
15,1,5
5,14,9
のような入力があるとすると、0番目のcolumnが 3, 15, 5 の値を取り得るが それを許容できるのは row だけ(classは3が入らないし seatは15が入らない)なので 0番目はrowと確定できる。そうすると1番目はclassかseatのどちらかだがseatに14が入らないのでclassに確定する。すると残りの2番目はseatに確定、という感じになる。
すべてのfieldが何番目のcolumnかを確定し、departureで始まるfieldのyour ticketのvalueをすべて掛け合わせた値を求めよ、という問題。
問題自体は順番に潰していけば解けるように出来ているようで(「どれも確定できないがこれをこのfieldと仮定すると矛盾が生じるのでこれは無し」、みたいな試行は必要なさそう)、ならば20個のfieldと各columnのvalueで有り得る組み合わせのmatrixを作っていけば良い。
上の例でいうと各fieldの取り得る範囲に入っているかどうかをすべてチェックすることで以下のような組み合わせが得られる。
0 1 2
class False True True
row True True True
seat False False True
この中で Trueが1つだけしか無いcolumnを探せばそれが何のfieldに該当するかが確定でき、そのcolumnとfieldはmatrixから削除して(無視して)良くなる。残ったものからまた確定できるものを探す、という操作を繰り返していけば良い。
実際にmatrixを作っても良かったが、せっかくなのでpart1の解法の延長でbit manipulationで実現することにした。
Vec<bool>で「ある値がどこかのfieldに入り得るかどうか」を管理していたものを Vec<u32>に変更し、「ある値がi番目のfieldに入り得るかどうか」を1 << iを論理和していくことで多重に管理できるようにした。値が0なら結局どのfieldにも該当しないし、0b111...111になったらすべてのfieldに該当し得る、ということになる。
その後、最初にcandidatesを[0b1111...111; 20]で初期化しておいて、すべての(validな)nearby ticketsを見ていって、各columnの値で該当し得るfieldsが引けるので&=で論理積を取っていく。
fn identify(&self) -> (u64, Vec<String>) {
let max = self
.rules
.iter()
.filter_map(|rule| rule.1.iter().map(|&range| range.1).max())
.max()
.unwrap();
let mut v: Vec<u32> = vec![0; max as usize + 1];
for (i, rule) in self.rules.iter().enumerate() {
for &r in rule.1.iter() {
(r.0..=r.1).for_each(|j| v[j as usize] |= 1 << i);
}
}
let mut candidates = vec![(1 << self.ticket.len()) - 1; self.ticket.len()];
for ticket in self.nearby.iter() {
if !ticket.iter().any(|&val| val > max || v[val as usize] == 0) {
for (i, &val) in ticket.iter().enumerate() {
candidates[i] &= v[val as usize];
}
}
}
...
}
こうして得られるcandidatesが、上述のmatrixの代わりになる。例だと [2, 3, 7]が得られるが、3bitでみると [0b010, 0b011, 0b111] ということであり、各columnが「下位からi番目のbitがtrueならi番目のfieldに該当し得る」ということを示すものになる。0番目のcolumnは1番目のbitしか立っていないので1番目のfield(例ではrow)に確定することになる。
確定したらcandidatesのすべての値からそのbitをfalseにして、また同じように見ていけば良い。
let mut fields = vec![String::new(); self.ticket.len()];
while fields.iter().any(|s| s.is_empty()) {
if let Some(i) = candidates.iter().position(|&c| c.count_ones() == 1) {
let n = candidates[i];
fields[i] += self.rules[n.trailing_zeros() as usize].0.as_str();
candidates.iter_mut().for_each(|c| *c &= !n);
}
}
これですべてのfieldの順番が得られる。
invalidな値を含むticketかどうかをチェックするところでその値も取得しておけば、part1の答えに使う値も同時に取得できる。
code
use std::io::{BufRead, BufReader};
struct Solution {
rules: Vec<(String, Vec<(u32, u32)>)>,
ticket: Vec<u32>,
nearby: Vec<Vec<u32>>,
}
impl Solution {
fn new(inputs: Vec<String>) -> Self {
let mut rules = Vec::new();
let mut nearby = Vec::new();
let mut ticket = Vec::new();
let mut read_nearby = false;
for line in inputs.iter().filter(|&s| !s.is_empty()) {
if line.starts_with(char::is_numeric) {
let values = line.split(',').filter_map(|s| s.parse().ok()).collect();
if read_nearby {
nearby.push(values);
} else {
ticket.extend(values);
}
} else if line.ends_with(char::is_numeric) {
let kv: Vec<&str> = line.split(": ").collect();
let ranges: Vec<(u32, u32)> = kv[1]
.split(" or ")
.filter_map(|range| {
if let Some(minmax) = range
.split('-')
.map(|s| s.parse::<u32>().ok())
.collect::<Option<Vec<u32>>>()
{
Some((minmax[0], minmax[1]))
} else {
None
}
})
.collect();
rules.push((kv[0].to_string(), ranges));
}
if line.starts_with("nearby") {
read_nearby = true;
}
}
Self {
rules,
ticket,
nearby,
}
}
fn solve_1(&self) -> u64 {
self.identify().0
}
fn solve_2(&self) -> u64 {
self.identify()
.1
.iter()
.enumerate()
.filter(|(_, field)| field.starts_with("departure"))
.map(|(i, _)| self.ticket[i] as u64)
.product()
}
fn identify(&self) -> (u64, Vec<String>) {
let max = self
.rules
.iter()
.filter_map(|rule| rule.1.iter().map(|&range| range.1).max())
.max()
.unwrap();
let mut v: Vec<u32> = vec![0; max as usize + 1];
for (i, rule) in self.rules.iter().enumerate() {
for &r in rule.1.iter() {
(r.0..=r.1).for_each(|j| v[j as usize] |= 1 << i);
}
}
let mut candidates = vec![(1 << self.ticket.len()) - 1; self.ticket.len()];
let mut error_rate = 0;
for ticket in self.nearby.iter() {
let mut valid = true;
for &val in ticket.iter() {
if val > max || v[val as usize] == 0 {
error_rate += val as u64;
valid = false
}
}
if valid {
for (i, &val) in ticket.iter().enumerate() {
candidates[i] &= v[val as usize];
}
}
}
let mut fields = vec![String::new(); self.ticket.len()];
while fields.iter().any(|s| s.is_empty()) {
if let Some(i) = candidates.iter().position(|&c| c.count_ones() == 1) {
let n = candidates[i];
fields[i] += self.rules[n.trailing_zeros() as usize].0.as_str();
candidates.iter_mut().for_each(|c| *c &= !n);
}
}
(error_rate, fields)
}
}
fn main() {
let solution = Solution::new(
BufReader::new(std::io::stdin().lock())
.lines()
.filter_map(|line| line.ok())
.collect(),
);
println!("{}", solution.solve_1());
println!("{}", solution.solve_2());
}
Discussion