Advent of Code
毎日2題出題されます。競技プログラミングチックに楽しめます。
この問題概要と実装解答を以下にご紹介します。
問題概要は生成AIに書いてもらったものを貼り付けています。
実装は人間が行なっています。
Day 10: Factory
part1 問題概要
インジケータランプの目標パターン：[.##.] のような角括弧 と ボタンの配線情報：(0,3,4) のような丸括弧 () が複数与えられます。
初期状態はすべてオフ (.....) からスタートして、ボタンを押して入力で与えられたパターンと一致させるのが目標。
ボタンiを押すと括弧内の箇所が., #でトグルする。
目標の文字列になるまでの最小ボタン押下回数を教えてください。
解答
括弧の文字列が多くて10個くらいなので、すべての状態は <= 2 ^ 10 = 1024くらいで余裕で全状態を保持できます。
よって、BFSが可能です。
use std::{collections::{HashMap, VecDeque}, io::{self, Read}};
use itertools::Itertools;
use regex::Regex;
fn parse_input(s: &str) -> (Vec<char>, Vec<Vec<usize>>, Vec<usize>) {
let reg1 = Regex::new(r"\[([.#]+)\]").unwrap();
let reg2 = Regex::new(r"\(([^)]+)\)").unwrap();
let reg3 = Regex::new(r"\{([^}]+)\}").unwrap();
let mut v = vec![];
for p in reg2.captures_iter(&s) {
let t = &p[1];
let nums = t.split(',').map(|e| e.parse::<usize>().unwrap()).collect_vec();
v.push(nums);
}
let s1 = reg1.captures(&s).unwrap()[1].chars().collect_vec();
let s3 = reg3.captures(&s).unwrap()[1].split(',').map(|e| e.parse::<usize>().unwrap()).collect_vec();
(s1, v, s3)
}
fn main() {
let mut input = String::new();
io::stdin().read_to_string(&mut input).unwrap();
let s = input
.lines().collect_vec();
let t = s.iter().map(|e| parse_input(e)).collect_vec();
let mut ans = 0;
for (target, button, _) in t.iter() {
let n = target.len();
let mut dist = HashMap::new();
dist.insert(vec!['.'; n], 0usize);
let mut que = VecDeque::new();
que.push_back(vec!['.'; n]);
while !que.is_empty() {
let v = que.pop_front().unwrap();
let &now = dist.get(&v).unwrap();
for row in button.iter() {
let mut new = v.to_owned();
for &idx in row.iter() {
new[idx] = if new[idx] == '#' {'.'} else {'#'};
}
let pre = dist.get(&new);
if pre.is_some() {
continue;
}
dist.insert(new.to_owned(), now + 1);
que.push_back(new);
}
}
let &a = dist.get(target).unwrap();
ans += a;
}
println!("{}", ans);
}
part2問題概要
中括弧で数字が
(3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
のように与えられます。
先ほどと同様にボタンを押すことで書かれたindexがインクリメントされます。
数字が中括弧のようになるようなボタンの押下最小回数を教えて！
解答
これ入力見ると中括弧の数字は最大300くらいあって、要素数も10程度あるので、全状態は 300 ^ 10 くらいになるのでとんでもない回数になり、先ほどと同様なbfsすると一生終わらないと思います。
そこで、例えば↑の例では、0番の3という数字は5番目と6番目のボタンを使ってやる必要があるので、
⑤ + ⑥ = 3
という式が成立します。
そのほかの番号に対してもそれぞれ書けるので、結局行列Aに対して
$$
Ax = B
$$
を満たすxについて解く問題に帰着できます。
詳しいところは
https://drken1215.hatenablog.com/entry/2019/03/20/202800
を見ていただければと思いますが、連立方程式はガウスの吐き出し法でO(N^3)で解けます。
ただ、今回は自由度が出てくるので、連立方程式をガウスの吐き出し法でといておいて、ピポッドとランクを見つけて、自由度を算出します。
その後自由度を持った変数について枝刈り全探索をdfsで行って答えを算出します。
難しかった....
use std::{
cmp::min,
io::{self, Read},
};
use itertools::Itertools;
use num::integer::gcd;
use regex::Regex;
fn parse_input(s: &str) -> (Vec<char>, Vec<Vec<usize>>, Vec<isize>) {
let reg1 = Regex::new(r"\[([.#]+)\]").unwrap();
let reg2 = Regex::new(r"\(([^)]+)\)").unwrap();
let reg3 = Regex::new(r"\{([^}]+)\}").unwrap();
let mut v = vec![];
for p in reg2.captures_iter(&s) {
let t = &p[1];
let nums = t
.split(',')
.map(|e| e.parse::<usize>().unwrap())
.collect_vec();
v.push(nums);
}
let s1 = reg1.captures(&s).unwrap()[1].chars().collect_vec();
let s3 = reg3.captures(&s).unwrap()[1]
.split(',')
.map(|e| e.parse::<isize>().unwrap())
.collect_vec();
(s1, v, s3)
}
fn gauss(v: &mut Vec<Vec<isize>>) -> (usize, Vec<usize>) {
let n = v.len();
let m = v[0].len() - 1;
let mut rank = 0;
let mut cs = vec![];
for col in 0..m {
let mut t = usize::MAX;
for row in rank..n {
if v[row][col] != 0 {
t = row;
break;
}
}
if t == usize::MAX {
continue;
}
v.swap(rank, t);
cs.push(col);
let p = v[rank][col];
for row in (rank + 1)..n {
if v[row][col] == 0 {
continue;
}
let g = gcd(p, v[row][col]);
let t = v[row][col] / g;
let tt = p / g;
for j in col..=m {
v[row][j] = v[row][j] * tt - v[rank][j] * t;
}
}
rank += 1usize;
}
(rank, cs)
}
fn dfs(
idx: usize,
now: &mut Vec<isize>,
nowsum: isize,
table: &Vec<Vec<isize>>,
v: &Vec<usize>,
rv: &Vec<usize>,
ans: &mut isize,
lim: isize,
) {
if nowsum >= *ans {
return;
}
let m = table[0].len() - 1;
let mm = rv.len();
if idx == v.len() {
for rank in (0..mm).rev() {
let col = rv[rank];
let mut right = table[rank][m];
for j in (col + 1)..m {
right -= table[rank][j] * now[j];
}
let tm = table[rank][col];
if tm == 0 {
if right != 0 {
return;
} else {
continue;
}
}
if right % tm != 0 {
return;
}
let val = right / tm;
if val < 0 {
return;
}
now[col] = val;
}
let t = now.iter().sum::<isize>();
*ans = min(*ans, t);
return;
}
for c in 0..=lim {
now[v[idx]] = c;
dfs(idx + 1, now, nowsum + c, table, v, rv, ans, lim);
}
}
fn solve(button: Vec<Vec<usize>>, target: Vec<isize>) -> isize {
let m = button.len();
let n = button.iter().flatten().max().unwrap() + 1;
let mut table = vec![vec![0; m + 1]; n];
for i in 0..m {
for &j in button[i].iter() {
table[j][i] = 1isize;
}
}
for i in 0..n {
table[i][m] = target[i];
}
let (_, cs) = gauss(&mut table);
let t = (0..m).filter(|&e| !cs.contains(&e)).collect_vec();
let rt = (0..m).filter(|&e| cs.contains(&e)).collect_vec();
let lim = target.iter().sum::<isize>();
let mut ans = isize::MAX;
let mut now = vec![0; m];
dfs(0, &mut now, 0, &table, &t, &rt, &mut ans, lim);
ans
}
fn main() {
let mut input = String::new();
io::stdin().read_to_string(&mut input).unwrap();
let s = input.lines().collect_vec();
let t = s.iter().map(|e| parse_input(e)).collect_vec();
let mut ans = 0;
for (_, button, target) in t {
ans += solve(button, target);
}
println!("{}", ans);
}
終わりに
part2がこれまでの問題で一番難しかったです。
day11も頑張ります！