サイコロの移動
プログラミングの実装練習問題として、「6面サイコロを平らな床に置き、パタパタと回転させながら移動させた後に上を向いている面の数字などを求める」というものがある。
- Dice I (Aizu Online Judge)
用語定義
４ ５１２６ ３
このような展開図のサイコロで、6の面が床と接し、３の面が手前側になるように置かれている場合、各面の方向を以下のように呼ぶ。
１⇔６ ２⇔５ ３⇔４ 頂 底 右 左 下 上
管理の方針
サイコロの動きは以下のようになる。これをシミュレートする。
- 縦方向の回転
- 左右の面は不変
- 左右以外の4面の数字が1つずつ回転
- 横方向の回転
- 上下の面は不変
- 上下以外の4面の数字が1つずつ回転
サイコロの向きは、初期配置がわかっていれば、固定された2面1)の位置に来る2つの数字がわかれば残りの面は一意に特定できる。
2面の位置に来る数をサイコロの動きに追従させることで状態管理は一応できる。しかし、あまりに最小限過ぎてちょっと扱いづらい。
6面全ての数字を管理すると考えやすいので、まずはそこから考える。
管理方法例
6要素の配列
state = [頂, 右, 下, 上, 左, 底] それぞれに何の数字が来るかを配列で持っておく。順番はこの通りでなくてもよい。
たとえば右方向への回転だと、以下のように $i=0,4,5,1$ につき、この順に数字を1つずつずらした状態となる。
i: 0 1 2 3 4 5 回転前: １ ２ ３ ４ ５ ６ 回転後: ５ １ ３ ４ ６ ２ new_state[0] ← state[4] new_state[4] ← state[5] new_state[5] ← state[1] new_state[1] ← state[0]
この $0,4,5,1$ というindexは、stateにおける面の順番と転がす向きによって変化するため、あらかじめ求めておく。
同様に、下方向の回転は $i=0,3,5,2$ につき、この順に数字を1つずつずらした状態となる。
i: 0 1 2 3 4 5 回転前: １ ２ ３ ４ ５ ６ 回転後: ４ ２ １ ６ ５ ３ new_state[0] ← state[3] new_state[3] ← state[5] new_state[5] ← state[2] new_state[2] ← state[0]
左方向・上方向については、同様にずらすindexを調べてもよいし、少し計算時間は延びるが「右回転3回」「下回転3回」で代用することも可能。
3要素の配列
サイコロが「裏の数字を足したら7になる」という原則を守っているなら、表裏どちらか一方の情報は省略できる。
state = [頂, 右, 下] それぞれに何の数字が来るかを配列で持っておく。
右方向の回転なら、以下のようになる。
i: 0 1 2 ( 3 4 5) 回転前: １ ２ ３ (４ ５ ６) 回転後: ５ １ ３ (４ ６ ２) new_state[0] ← 7 - state[1] new_state[1] ← state[0]
下方向の回転なら、以下のようになる。
i: 0 1 2 ( 3 4 5) 回転前: １ ２ ３ (４ ５ ６) 回転後: ４ ２ １ (６ ５ ３) new_state[0] ← 7 - state[2] new_state[2] ← state[0]
ハッシュによる3面管理
1～6は3bitで表現できるため、各面の数字を3bitずつ並べれば、18bit（6面を管理する場合）や9bit（3面を管理する場合）の整数値として扱える。
また、表裏の和である7はちょうど 0b111 のため、裏面の数字はbit反転することで取得できる。
この方法は、1つの整数値で状態を表現できるので、たとえば途中途中のサイコロの向きを保存したい場合などに重宝する。
配列より省メモリで保存できるし、状態の一致判定も定数倍高速になる。
右方向の回転なら、以下のようになる。（下の桁から埋めるため、$i$ が見た目上逆順である点に注意）
i: 2 1 0 回転前: ３ ２ １ bit表現: 011 010 001 回転後: ３ １ ５ bit表現: 011 001 101 new_state = state & 0b111000000 new_state |= (~state & 0b000111000) >> 3 new_state |= (state & 0b000000111) << 3
