CodeIQ に「カラフルな八面体を転がそう。」の、解説・解題

CodeIQ に「カラフルな八面体を転がそう。」( https://codeiq.jp/ace/nabetani_takenori/q708 )という問題を出した。
挑戦の募集はすでに締めきっている。
というわけで、解説・解題。

問題は以下の URL に：
http://nabetani.sakura.ne.jp/codeiq/octaheroll/

で。

出題の意図とか

問題に書いた通り、オフラインリアルタイムの第12回( http://atnd.org/events/40389 )で類題「サイコロを転がす」( http://nabetani.sakura.ne.jp/hena/ord12rotdice/ ) を出している。

八面体だと状況が少し複雑になるので、面白いかな、と思って出題した。

対面が同じ色なのは、手元にあるおもちゃには赤緑青黄黒白の6色しかなく、8面全部違う色にすることができなかったから。
残念なような気もしていたんだけど、実装方針に幅が出たのでよかったかなと思っている。

実装方針

八面体を転がすと、立方体の場合と違って、図形自体の向きが変わる。
これに対処する必要があるんだけど、

向きは2通り。これをちゃんと管理して実装する。
向きを気にしなくて良いように実装する。

という2つの方針がある。

前者で行くと、抽象クラスの使いどころのような感じになる。
が。
私は、気にしないようにする方法を選んで実装した。( 抽象クラスを使った実装も書いたけど )
具体的には

八面体を、六角柱に読み替える。
転がす方向が確定したら、その方向に転がせるような八面体に読み替えてから転がし、その結果を六角柱に読み替える。

こんな感じ。

管理されるべきものは六角柱だけなので簡単。
八面体をちゃんと管理する場合とちがって、12時の方向に二回連続転がすことができてしまったりするんだけど、そんな入力は来ないことが保証されているので大丈夫。

六角柱だけになってしまえば、面の色を置換するだけ。
転がす方向は6種類。それぞれの方向に転がしたらどんな置換が起こるのかをまとめれば出来上がり。

ruby による実装

手元ではまず ruby で実装した。

#!ruby
def rotate( o, dir )
  m=case dir
  when "2";[5,1,0,3,4,7,6,2]
  when "4";[6,1,2,0,4,5,7,3]
  when "6";[1,7,2,3,0,5,6,4]
  when "8";[2,1,7,3,4,0,6,5]
  when "T";[3,1,2,7,4,5,0,6]
  when "D";[4,0,2,3,7,5,6,1]
  end
  m.map{ |i| o[i] }
end

def solve_impl(st,s)
  s.chars.inject( st ) do |acc, c|
    acc + [rotate( acc.last, c )]
  end
end

def solve(s)
  st=["YRGBRGBY".chars]
  solve_impl(st,s).map{ |c| c.first }.join
end

case〜when がちょっと無様な感じではあるけど、これがこの問題の本質でもある。
つまり、転がす前にどこにあった面が、転がした後にどこに行くか。

Java による実装

実装方針にはもう一箇所、決定的な選択肢がある。対面が同じ色だということを利用するかしないか。
先ほどの ruby による実装では、対面が同じ色であることを利用していない。
で。利用すると、こんな感じになる。

慣れない Java で。

class Octahedron {
  private final char[] faces;

  public Octahedron(char[] faces_) {
    faces = faces_;
  }

  char top() {
    return faces[0];
  }

  Octahedron getRolled(char c) {
    char[] new_faces = new char[4];
    int[] indices = getRollIndices(c);
    for (int i = 0; i < 4; ++i) {
      new_faces[i] = faces[indices[i]];
    }
    return new Octahedron(new_faces);
  }

  private static int[] getRollIndices(char c) {
    switch (c) {
      case '2':
      case '8':
        return new int[]{2, 1, 0, 3};
      case '4':
      case 'T':
        return new int[]{3, 1, 2, 0};
      case '6':
      case 'D':
        return new int[]{1, 0, 2, 3};
    }
    throw new UnknownError("invalid roll command.");
  }
}

class RollOctahedron {
  public static String solve(String src) {
    Octahedron o = new Octahedron("YRGB".toCharArray());
    StringBuilder result = new StringBuilder();
    result.append(o.top());
    for (int i = 0; i < src.length(); ++i) {
      o = o.getRolled(src.charAt(i));
      result.append(o.top());
    }
    return result.toString();
  }
}

import とかいろいろ省略。
RollOctahedron.solve( "入力文字列" )
みたいな感じで使う。
で。
注目すべきは、getRollIndices メソッド。
対面が同じなので、おぼえておくべき面は4つになる。
転がしたときに起こる置換を、ruby の時と同じように記述してみると、2時の方向に転がすことと8時の方向に転がすことは、実は同じだということがわかる。
意外だった。

ここからさらに、剰余などを使って算術的に攻めるともっと短くなるけど、私はこれでいいかなと思ってこれ以上攻めていない。

使用言語ランキング

使用言語はこんな感じになった。

ruby 14名
Java 10名
Python 9名
C++ 4名
Haskell 3名
Perl 3名
その他 7名

順当なところかなとも思うけど、市場で高いシェアを誇っているはずの PHP、VB、JavaScript はそれほど多くなく、市場シェアがほとんどないはずの Haskell が3名いるというところが面白い。

問題についてもうちょっと

課題データと場合の数

八面体なので、上面は 8通り。
上面が確定すると、置き方は3通り。
そこから転がせる方向は3通り。
都合、72通りある。

この72通りをすべて書きつくせばそれで解けるんだけど、そうしたくなってしまった人のために、課題となっている80文字のデータは、72通りがすべて使われるように作った。

数学

ジャンルに「数学」をつけていただいたんだけど、ここまで読んでお分かりのとおり、全然数学らしくない。
数学らしいところは、群だよ、という点にある。
だからどうしたということはあまりないんだけど、そういう視点に立てると実装が容易になると思う。

宣伝

CodeIQで出しているものより簡単な問題をその場で解いて、発表しあう「オフラインリアルタイムどう書く」というプログラミング勉強会というか、プログラムを書く遊びを主催してます。
CodeIQ と違って、制限時間があったり、他の人のコードを見ることができたり、懇親会があったりします。
主催者としては、仕事を終えた後のフットサルのような気分の楽しいイベントのつもりです。

日時：2014年3月7日（金）19:00～
場所：西公会堂(横浜駅徒歩10分ぐらい)
申し込み：http://atnd.org/events/47670

スポーツと同様、時間内に実装できないと悔しかったりするんだけど、仕事じゃないので負けてもくやしいだけで、被害も迷惑もありません。
キャッチフレーズは「負けられる戦いがここにある」。

最後に

今月中に次の問題を出す予定（未着手）なのでよろしくお願い致します。

Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。