スクラッチカードの得点計算。
part2はメタ的で少し特殊
## 方針
実際に問題を解くのに必要なのは「各カードでmatchしている個数」の情報だけ。
事前に各行でそのカウントを計算してしまうと良い。
part1はそれぞれmatch数から `0, 1, 2, 4, 8, 16` に変換できればあとは足すだけ。
part2はポイントではなくmatch数だけ後続のカードがコピーされ増える、というもの。
これは初期状態ですべて`1`になっている配列を用意し、カードを順に見ていく中で「matchした数だけそのカード枚数を後続の要素に足し込んでいく」という操作で計算できる。
末尾に到達している場合は切り捨てる必要があるが、この問題も入力が調整されて作られているようで、実際には切り捨てる必要のあるものは出てこないようだ。
## 実装
### Rust
1行ずつparseし、matchした数だけ保持しておく。
part1は `1 << n >> 1` でポイントを計算できる。
```rust
struct Solution {
matches: Vec<usize>,
}
impl Solution {
...
fn part1(&self) -> u32 {
self.matches.iter().map(|n| 1 << n >> 1).sum()
}
fn part2(&self) -> u32 {
let mut v = vec![1; self.matches.len()];
for (i, n) in self.matches.iter().enumerate() {
for j in i + 1..(i + 1 + *n).min(v.len()) {
v[j] += v[i];
}
}
v.iter().sum()
}
}
```
### Python
matchする数だけが必要なので`int`に変換する必要もなく、単に`str.split()`した結果の集合を使ってカウントを求めることができる。
この場合、実は`":"`でsplitする必要もなく、左側に`Card 13:` のようなものが残っていても `["Card", "13:", ...]`のようにカード番号は`":"`つきで取得されるため集合の計算では上手く除外される。
```python
def __init__(self, io: TextIO) -> None:
def match_count(s: str) -> int:
winning, have = map(str.split, s.split(":")[1].split("|"))
return len(set(winning) & set(have))
self.matches = list(map(match_count, io))
```
### OCaml
parseは分割した後にそれぞれ`int list`に変換し、`List.mem ~equal`でカウント。高々5要素のListからの探索なのでこれで十分。
```ocaml
let parse input =
let match_count line =
let to_int_list s =
String.split s ~on:' '
|> List.filter ~f:(Fn.non String.is_empty)
|> List.map ~f:Int.of_string
in
String.lsplit2_exn line ~on:':' |> snd |> String.lsplit2_exn ~on:'|'
|> fun (winning, have) ->
let w = winning |> to_int_list in
have |> to_int_list |> List.count ~f:(List.mem w ~equal)
in
In_channel.input_lines input |> List.map ~f:match_count
```
part2は`Array`を使うことになる。
```ocaml
let part2 matches =
let a = Array.create ~len:(List.length matches) 1 in
List.iteri matches ~f:(fun i x ->
List.range (i + 1) (i + 1 + x)
|> List.iter ~f:(fun j -> a.(j) <- a.(j) + a.(i)));
Array.fold a ~init:0 ~f:( + ) |> Answer.of_int
```