[AOJ]「IPT1_11_B サイコロIII」の同一サイコロを判定処理がわかりません

Question

前提・実現したいこと

AIZU ONLINE JUDGEの「IPT1_11_C サイコロIII」の問題で、同一のサイコロを判定する処理をどのように書けばいいかわかりません。
2つの同一のサイコロを判定する処理は、以下のソースコードのis_same_dice関数です。

問題文については、お手数をかけしますが、リンク先をご覧ください。
リンク先にありますSample Input1と2は期待通りの出力が得られます。
https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/11/ITP1_11_C

どうぞよろしくお願いいたします。

発生している問題・エラーメッセージ

以下のソースコードを投稿すると、テストケース6でYESの出力が得られません。
テストケース6の入力値

10 20 20 40 50 50
50 10 20 20 40 50

該当のソースコード

#include <bits/stdc++.h>
using namespace std;

class Dice {
  public:
    Dice(int number[]);
    void print_status();
    int get_status(int number);
    void toss(char direction);
    bool is_same_dice(Dice d);

  private:
    int dice[6];
};

Dice::Dice(int n[]) {
    for(int i = 0; i < 6; i++) {
        dice[i] = n[i];
    }
}

void Dice::print_status() {
    for(int i = 0; i < 6; i++) {
        cout << dice[i] << " ";
    }
    cout << endl;
}

int Dice::get_status(int number) { return dice[number]; }

void Dice::toss(char direction) {
    int tmp;
    switch(direction) {
    case 'N':
        tmp = dice[0];
        dice[0] = dice[1];
        dice[1] = dice[5];
        dice[5] = dice[4];
        dice[4] = tmp;
    case 'S':
        tmp = dice[0];
        dice[0] = dice[4];
        dice[4] = dice[5];
        dice[5] = dice[1];
        dice[1] = tmp;
    case 'E':
        tmp = dice[0];
        dice[0] = dice[3];
        dice[3] = dice[5];
        dice[5] = dice[2];
        dice[2] = tmp;
    case 'W':
        tmp = dice[0];
        dice[0] = dice[2];
        dice[2] = dice[5];
        dice[5] = dice[3];
        dice[3] = tmp;
    }
}

bool Dice::is_same_dice(Dice d) {
    for(int i = 0; i < 6; i++) {
        if(i < 4) {
            toss('S');
        } else if(i == 4) {
            toss('E');
        } else {
            toss('W');
            toss('W');
        }

        if(get_status(0) == d.get_status(0) &&
           get_status(1) == d.get_status(1) &&
           get_status(2) == d.get_status(2)) {
            return true;
        }
    }
    return false;
}

int main() {
    int dice_table[2][6];

    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 6; j++) {
            cin >> dice_table[i][j];
        }
    }

    Dice d1(dice_table[0]), d2(dice_table[1]);

    if(d1.is_same_dice(d2)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

追加（2021/06/16）

bool Dice::is_same(Dice d) {
    for(int i = 0; i < 6; i++) {
        if(dice[i] != d.get_status(i)) {
            return false;
        }
    }
    return true;
}

bool Dice::is_same_dice(Dice d) {
    for(int i = 0; i < 6; i++) {
        if(i < 4) {
            toss('S');
        } else if(i == 4) {
            toss('E');
        } else {
            toss('W');
            toss('W');
        }

        for(int j = 0; j < 4; j++) {
            if (j == 1) {
                toss('E');
            } else if(j < 4) {
                toss('S');
            }
            if (is_same(d)) {
                return true;
            }
        }
        // toss('S');
        toss('W');
    }
    return false;
}

テストケース11の入力値
期待通りのYesの出力が得られない。

1 2 3 4 5 6
5 3 6 1 4 2

追加（2021/06/17）

側面のみを回転させる関数right_rotationを書いてみましたが、不合格になってしまっています。

bool Dice::is_same_dice(Dice d) {
    for(int i = 0; i < 6; i++) {
        if(i < 4) {
            toss('S');
        } else if(i == 4) {
            toss('E');
        } else {
            toss('W');
            toss('W');
        }

        for(int j = 0; j < 4; j++) {
            right_rotation();
            if(is_same(d)) {
                return true;
            }
        }
    }
    return false;
}

void Dice::right_rotation() {
    int tmp = dice[1];
    dice[1] = dice[2];
    dice[2] = dice[4];
    dice[4] = dice[3];
    dice[3] = tmp;
}

Answer 1

同一のサイコロを判定する処理をどのように書けばいいか

私は頭が良くないので，同一判定方法を以下のように考えます．

• 方針：一方のダイスの姿勢を固定し，他方のダイスの姿勢を変えていく．ある姿勢において６つの面の全ての値が等しければ同一である．
• 探索回数：ダイスの姿勢のパターン数．ある面を上にした姿勢は４パターンあるので，単純に考えて 6*4=24 パターン調べるんじゃないだろうか？

---

…という話と，示された Dice::is_same_dice とを見比べてみると，

• ３面の値しか等値のチェックをしていないように見える
• ６パターンの姿勢しか調べていないように見える

というところが不思議です．
おそらく私の考えよりも効率的な何らかの話を実装しているのではないかと思うのですが，

2つの同一のサイコロを判定する処理は、以下のソースコードのis_same_dice関数です

とだけ言われても，どのようなアルゴリズムで判定をするつもりのコードなのかが不明です．
（まともに動かないコードならば，コードから読み取るのも限界があります）

Comments

[smile_20200722]

fanaさん、コメントありがとうございます。
is_same_dice関数の3面しかチェックしてないのは、私の理解不足です。
一つのサイコロの姿勢を固定し、6面を上にもってきて、その値と隣り合う2面を比較すれば同一だと考えていました。
探索回数の「ある面を上にした姿勢は4パターン」とはどういう意味でしょうか？

[fana]

問題文を見る限り，入力値には何の仮定も与えられていない：
ある面の値とその裏側の面の値との間に何かの関連性があるわけでもなく，
また，２つのダイスの面の値として「同一の６つの値の組」が与えられるという話でもない

…ようですから，単純に考えれば６個の面の値は全て比較する必要があると見えます．

> 「ある面を上にした姿勢は4パターン」

ある面を上に向けてダイスを置いたとき，ダイスの６面を｛上面と底面と「側面が４こ」｝と呼べますよね．
この４つの側面のうちどれがどっち方向に向いているか（例えば，どれが"手前側"に向いているか）？　という点で，姿勢にパターンがありますよね．
鉛直軸を回転軸としてくるくる回せるので．

[smile_20200722]

fanaさん、コメントありがとうございます。
追加でソースコードを掲載しましたので、見ていただけると助かります。
側面の4つについて判定することはわかりましたが、その4つをどのように記述すればいいかわかりません。
側面の4つについて自分なりの解釈でis_same_dice関数を書いてみましたが、テストケース11で期待通りの出力が得られませんでした。
やってることは、それぞれの上を軸とした6面に対して、側面に向きを変えて各4面を上にし、サイコロの各面が一致しているかを判定し、サイコロを元の向きに戻しています。
これだとテストケース11まで通ります。
ただ、私の考えだとコメントアウトしている向きに直したいのですが、これですと一つもテストケースが通らなくなってしまいます。
根本的に考えた方が間違えているでしょうか？

[fana]

考えている通りに動いているのかを確認してください．
（その作業を他者に投げるべきではないです）

私の考えで言えば，6*4 = 24 パターンの姿勢をチェックすることになりますが，
もしも私がそれを実装して「なんか動作しない」という状態になったとしたら，
まずは
24パターンの回転姿勢の状態を全てどこかに出力し，
各姿勢での要素数６個の配列のあるべき内容を紙上で書き出したものと比較します．

[smile_20200722]

fanaさん、コメントありがとうございます。
サイコロの状態を出力して確認しました。
6面の姿勢で重要なtoss関数に誤りがありました。
switch文の各項目にbreakを書いておらず、一部姿勢がもとのままになってしまっていました。

[fana]

解決したようでなによりです．

---

「デバッグしてください」という話が出ると
｛無言で退会する，どこかにマルチポストする，逆ギレする｝等々，とにかくまともな反応が得られないのが平常運転なteratailにおいて，
「しました/そして問題点がわかりました」という真っ当な反応が返された稀有な例ですね．

[fana]

それはそれとして，効率の面で考えれば
「一方のダイスAの姿勢を固定して，他方のダイスBの姿勢を色々変えてチェックする」とき，
たとえば
Aの上面の値が10であるとしたら，チェックすべきBの姿勢とは，上面の値が10である姿勢のみです．
なので，
「Bの6面の値を見て，値が10である面についてのみ，（それを上面とした姿勢を）チェックする」というような形の記述にできれば，不要な姿勢の計算をせずに済むかもしれません．
また，上面の値を合わせてから４つの回転姿勢を試す前に底面の値の一致チェックを先に行えば，４つの姿勢を試す前に棄却できます．
そうすると，細かい話ですが，4つの回転姿勢においてチェックする値は４箇所で済む（上下の面はもうチェック済みなので）とかいう形になりますね．

回答内に書いた

> 私の考えよりも効率的な何らかの話を実装しているのではないか

というのは，「そういったような効率の最適化を施した結果のコードなのかも」という話でした．

[smile_20200722]

fanaさん、コメントありがとうございます。
正直、動作するコードを書くことがままなりませんので、なかなか最適化まで頭が回ってない状況です。
効率の面のご指摘もありがとうございます。
それらを踏まえた書き方にも挑戦してみたいと思います。