[Day 5: Print Queue](https://adventofcode.com/2024/day/5)
与えられた前後関係のルールに基づいて各配列の順序をチェックする。
それなりにアルゴリズムを問われるようになってきた…
### 例
```
47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13
75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47
```
前半で前後関係のルールを与えられ、後半の配列たちについて判定していく。
part1は「すべて正しい順序」のものを探し、その中央の要素を足し合わせる。この例では先頭3行のものが正しいので `61`, `53`, `29` を足し合わせた **`143`** が解になる。
part2では、「正しい順序になっていない」ものに対して、正しい順序に修正し、それらの中央の要素を足し合わせる。上の例では
- `75,97,47,61,53` → `97,75,47,61,53`
- `61,13,29` → `61,29,13`
- `97,13,75,29,47` → `97,75,47,29,13`
と修正されるので `47`, `29`, `47` を足し合わせた **`123`** が解になる。
## 方針
各updateに関して、含まれる数値同士の順序のルールを使ってtopological sortする、という感じになる。
[トポロジカルソート - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%9D%E3%83%AD%E3%82%B8%E3%82%AB%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88)
例では問題ないが、実際の入力のルールでは循環があるので「あらかじめすべての数値の順序を決定しておく」ということはできない。
問題の性質上、順序は一意に定まるはずではあるので、各updateで登場する数値同士だけで「この値より前/後に出現しなければならないものの数」をカウントすればそれを使ってソートするだけで正しい順序は決定できそうだ。
## 実装
### Rust
parseは丁寧に書くとちょっと面倒だが、とにかく「この値より後に出現すべき値たち」を `HashSet` で持っておく。
既に正しい順序か否か、の情報はpart1/part2どちらでも使用するのでparse時に判定してしまって保持してしまって良い。
`.is_sorted_by()` でまさに「`a`が`b`より前に来るべき」というルールを満たしているか否かによる判定ができて大変便利。正しい順序に並び換える場合も、 `.sort_by()` で正しい順序のときに `Ordering::Less` を返しそれ以外のときは `Ordering::Greater` を返す、という処理で実現できる。
```rust
struct Solution {
rules: HashMap<u32, HashSet<u32>>,
updates: Vec<(Vec<u32>, bool)>,
}
impl Solution {
fn new<R>(r: R) -> Result<Self, Error>
where
R: Read,
{
let lines = BufReader::new(r).lines().collect::<Result<Vec<_>, _>>()?;
let (rule_lines, update_lines) = lines
.split(String::is_empty)
.collect_tuple()
.ok_or(Error::InvalidInput)?;
let mut rules = HashMap::new();
for rule in rule_lines.iter().map(|line| {
line.split('|')
.map(|s| s.parse().map_err(Error::Parse))
.collect::<Result<Vec<u32>, _>>()
.and_then(|v| v.into_iter().collect_tuple().ok_or(Error::InvalidLine))
}) {
let (before, after) = rule?;
rules
.entry(before)
.or_insert_with(HashSet::new)
.insert(after);
}
let updates = update_lines
.iter()
.map(|line| {
line.split(',')
.map(|s| s.parse().map_err(Error::Parse))
.collect()
})
.collect::<Result<Vec<Vec<_>>, _>>()?
.into_iter()
.map(|update| {
let sorted =
update.is_sorted_by(|a, b| rules.get(a).map_or(false, |set| set.contains(b)));
(update, sorted)
})
.collect();
Ok(Self { rules, updates })
}
fn part1(&self) -> u32 {
self.updates
.iter()
.filter(|(_, sorted)| *sorted)
.map(|(update, _)| update[update.len() / 2])
.sum()
}
fn part2(&self) -> u32 {
self.updates
.iter()
.filter(|(_, sorted)| !*sorted)
.map(|(update, _)| {
update
.iter()
.cloned()
.sorted_by(|a, b| {
if self.rules.get(a).map_or(false, |set| set.contains(b)) {
Ordering::Less
} else {
Ordering::Greater
}
})
.collect_vec()[update.len() / 2]
})
.sum()
}
}
```