Advent of Code
毎日2題出題されます。競技プログラミングチックに楽しめます。
この問題概要と実装解答を以下にご紹介します。
問題概要は生成AIに書いてもらったものを貼り付けています。
実装は人間が行なっています。
Day 6: Trash Compactor
part1 問題概要
全列について：
- その列にある数字を順に演算子でつなげて計算する
- 演算子が + なら全部足す
- 演算子が * なら全部掛ける
各問題の答えを全部足し合わせる
例：
123 328 51 64
45 64 387 23
6 98 215 314
* + * +
だったら、
123 * 45 * 6 = 33210
328 + 64 + 98 = 490
51 * 387 * 215 = 4243455
64 + 23 + 314 = 401
=> 33210 + 490 + 4243455 + 401 = 4277556
解答
転置して、各配列についてopの操作をしてあげればいいだけです。
part1は空白の行とかを気にせずでよかったので楽でした。
fn transpose<T: Clone + Copy + Default>(matrix: Vec<Vec<T>>) -> Vec<Vec<T>> {
if matrix.is_empty() {
return Vec::new();
}
let rows = matrix.len();
let cols = matrix[0].len();
let mut transposed = vec![vec![T::default(); rows]; cols];
for i in 0..rows {
for j in 0..cols {
transposed[j][i] = matrix[i][j];
}
}
transposed
}
fn main() {
let row = 4;
let col = 1000;
input! {
s: [[isize; col]; row],
op: [String; col]
}
let s = transpose(s);
let mut ans = 0;
for (idx, row) in s.iter().enumerate() {
let op = op[idx].to_owned();
if op == "+" {
let t = row.iter().fold(0, |acc, &now| acc + now);
ans += t;
} else {
let t = row.iter().fold(1, |acc, &now| acc * now);
ans += t;
}
}
println!("{}", ans);
}
part2 問題概要
part1では数字としての列を数えていましたが、part2では入力の列を厳格に区別します。
例：
123 328 51 64
45 64 387 23
6 98 215 314
* + * +
だったら、一番右の64, 23, 314は列が揃っているところを縦に読むと 4, 431, 623 と読めます。
これらに対してopの操作をします。(↑だったら+の操作)
それらを足し合わせたものが答え。
例の答えは
1番右の答えは
4 + 431 + 623 = 1058
右から2番目は
175 , 581 , 32
=> 175 * 581 * 32 = 3253600
3番目は
8 , 248 , 369
=> 8 + 248 + 369 = 625
4番目は
356 , 24 , 1
=> 356 * 24 * 1 = 8544
なので、
1058 + 3253600 + 625 + 8544 = 3263827
が答え。
解答
atcoderでなかなかこういう入力の空白行に大きく依存する文字列パース系が出ないので問題を理解するのが大変でした。
しかし、入力が優しくて、0がでて来ない入力だったことに気づき、空白行は0で埋めてしまって良いことに気づけばかなり問題が楽になります。
こうすることで、入力の切れ目は"縦に読んだ数字が0になったとき"と言い換えることができます.
例えば、以下のように縦に読んだ数字が得られた場合、0が切れ目になるので[1, 24, 356], [369, 248, 8], [32, 581, 175], [623, 431, 4]がひとかたまりであることがこの配列の情報だけで取得できて楽です。
[1, 24, 356, 0, 369, 248, 8, 0, 32, 581, 175, 0, 623, 431, 4]
また、縦に読んだ数字に関しては、これまた入力に0が出てこないことで、転置して0を省いた数字と一致して更にうれしいです。
ということで、この配列をなめていき、0がくるまでどんどんそれまでの数字を一時配列に詰めていって、0になったときに配列の中をまとめて計算 => 一時配列初期化、とすることで範囲の情報をなくさずに適切に計算できます。
なんか怖くてたくさんassert入れてしまっています
fn main() {
let mut s = String::new();
io::stdin().read_to_string(&mut s).unwrap();
let mut lines: Vec<Vec<char>> = s.lines().map(|l| l.chars().collect_vec()).collect();
let m = lines.iter().map(|e| e.len()).max().unwrap();
let mut op = lines.pop().unwrap();
let mut lines = lines
.into_iter()
.map(|e| {
e.iter()
.map(|&e| e.to_string().parse::<usize>().unwrap_or(0))
.collect_vec()
})
.collect_vec();
for row in lines.iter_mut() {
while row.len() < m {
row.push(0);
}
}
while op.len() < m {
op.push(' ');
}
let s = transpose(lines);
assert!(s.len() == m);
let mut c_op = op[0];
let mut pos = op.iter().positions(|&e| e != ' ').collect_vec();
pos.reverse();
assert!(c_op != ' ');
let s = s
.iter()
.map(|e| {
e.iter()
.filter(|&&e| e != 0)
.join("")
.parse::<usize>()
.unwrap_or(0)
})
.collect_vec();
assert!(s.len() == m);
let mut ans = 0;
let mut v = vec![];
for i in 0..m {
let la = pos.iter().last();
if let Some(&v) = la {
if v == i {
let ne = pos.pop().unwrap();
c_op = op[ne];
}
}
if s[i] == 0 {
if c_op == '+' {
let t = v.iter().sum::<usize>();
ans += t;
} else {
let t = v.iter().fold(1, |acc, &now| acc * now);
ans += t;
}
v.clear();
} else {
v.push(s[i]);
}
}
if c_op == '+' {
let t = v.iter().sum::<usize>();
ans += t;
} else {
let t = v.iter().fold(1, |acc, &now| acc * now);
ans += t;
}
println!("{}", ans);
}
終わりに
day7もがんばります！