概要
会津大学が運営しているAizu Online Judge(AOJ)のプログラミング初心者向けの問題で、サイコロを扱った(初心者には)少し歯ごたえのある問題(ITP1_11_C)があったので記事にまとめてみました。
(自分自身はRustを使い始める練習としてこの問題に取り組んでいたので実装例はRustになりますが、高度な機能は使っていないのでRustを知らない人も読めるかなと思います。)
この問題に歯ごたえがあると思った理由は以下のとおりです。
- AOJのITP1シリーズは基本的に定められた処理を書くだけの問題だが、この問題は全探索が要求される
- サイコロの置き方の全探索は、数は少ないものの数え方に工夫が必要
- サイコロを転がす処理は配列をうまく使わないと冗長なコードが大量発生してしまう
- 列挙子(enum)、構造体(クラス)、配列を活用するときれいなコードを書けるという良い練習課題になる
競技プログラミング経験者はenumや構造体など使用せずあっという間にmain関数内の処理だけで書き上げてしまうと思いますが、プログラミング初心者が学習目的で実装するのであれば、構造体を用いて愚直な実装から始めて徐々に冗長性のない簡潔なコードにブラッシュアップしていく体験をしやすい課題かなと思います。
初心者に向けたヒント
- サイコロの置き方を全探索することでサイコロの同一性を判定する
- サイコロのデータは要素数6の配列やベクタで表現する
- サイコロを転がすメソッドを定義する
解答の方針
問題文: ITP1_11_C
サイコロの画像: ITP1_11_A
- まず、与えられた2つのサイコロのうち片方の置き方を固定し、もう片方のサイコロについて全ての置き方を試して完全に合致するかどうかで、2つのサイコロが同じかどうかを判定する全探索の問題であると考えます
- 同じサイコロが同じ置き方をされているかどうかは、6つの面をそれぞれ要素に持つ配列が完全に一致するかどうかで検査できます
- そしてサイコロの全ての置き方の列挙方法ですが、立方体は対称性が高くとっかかりが無いので何かしらを固定して列挙することを考えます。たとえば上面を固定するならば、上に持ってきて固定する面の選び方の6通り、そしてそれぞれ上の面を固定したままコマを回す方向に0度、90度、180度、270度回転させる4通りで全パターン網羅できるので、置き方は全部で6×4 = 24通りあることが分かります
- このような全ての置き方を実現するサイコロの転がし方を、6つそれぞれの面を上の面に持ってくる操作、それから上の面を固定してコマを回すように回転させる操作に対応させ、メソッドとして定義します
- なお、コマを回す方向に回転させる操作は問題文中のE/N/S/Wに当てはまらない操作ですが、たとえばW->N->Eとして倒して縦に転がしてまた戻せばコマを回す方向に回転したのと同じ状態になるので、そのような操作をして問題ありません
- 最後に、これら24通りの転がす操作を片方のサイコロに行い、サイコロの配列が完全一致するかどうかを検査し、完全一致する置き方が見つかったらYes、そうでなければNoを表示するように実装します
※この解答の方針が実装できれば、ITP1_11_CだけでなくITP1_11_A、ITP1_11_B、ITP1_11_Dは全て簡単に解けます
Rustでの実装例
配列で簡潔な実装をするようにしていますが、かと言って簡潔さを限りなく追求するのではなくて、問題文の内容と直接的に結びつけやすい表現にもなるようにバランスを取っています。
また、Rustの書き方についても最善を追求していません。
enum Direction {
East,
North,
South,
West
}
#[derive(Clone, PartialEq, Eq)]
struct Dice {
sides: Vec<i32>
}
impl Dice {
// indicesで指定された0番目の面に1番目の面が、1番目の面に2番目の面が来るようにサイコロを90度転がす
// 面の番号は問題文中の番号から1を引いた数としている(問題文中の1~6を0~5として扱う)
fn roll(&mut self, indices: [usize; 4]) {
let temp = self.sides[indices[0]];
for i in 1..4 {
self.sides[indices[i - 1]] = self.sides[indices[i]];
}
self.sides[indices[3]] = temp;
}
// 問題文中の4つのいずれのかの方向を指定してサイコロを90度転がす
fn roll_by_direction(&mut self, d: Direction) {
match d {
Direction::East => self.roll([0, 3, 5, 2]),
Direction::North => self.roll([0, 1, 5, 4]),
Direction::South => self.roll([0, 4, 5, 1]),
Direction::West => self.roll([0, 2, 5, 3]),
}
}
// 上の面の選び方は6種類あるが、それぞれの種類が来るように仮のIDを指定してサイコロを転がす
// 0は現在の上の面がそのまま上の面でいるパターンを示す(転がさない)
// 5は現在の下の面を上の面に持ってくるため2回サイコロを90度倒す操作
fn roll_by_pattern(&mut self, pattern_id: u8) {
match pattern_id {
0 => (),
1 => self.roll_by_direction(Direction::East),
2 => self.roll_by_direction(Direction::North),
3 => self.roll_by_direction(Direction::South),
4 => self.roll_by_direction(Direction::West),
5 => {
self.roll_by_direction(Direction::East);
self.roll_by_direction(Direction::East);
},
_ => ()
}
}
// サイコロを倒さずに、z軸を中心に側面を90度回転させる
fn rotate(&mut self) {
self.roll([1, 3, 4, 2]);
}
}
// 空白区切りの標準入力値をベクタに読み込む
fn read_vec() -> Vec<i32> {
let mut buff = String::new();
std::io::stdin().read_line(&mut buff).ok();
buff.split_whitespace().map(|s| s.parse().unwrap()).collect()
}
fn main() {
// 入力値を読み込んでサイコロインスタンスの生成
let dice = Dice {sides: read_vec()};
let dice2 = Dice {sides: read_vec()};
// サイコロが一致するかを全探索(上面の選び方6通り×側面の選び方4通りの合計24通り)
for i in 0..6 {
let mut d = dice2.clone();
// ここで上面を6種類試すことになる
d.roll_by_pattern(i);
for _ in 0..4 {
if d == dice {
println!("Yes");
return;
}
// ここで側面を90度ずつ回転して4種類試すことになる
d.rotate();
}
}
println!("No");
}