11/6 課題問題

数当てゲーム MOO を遊ぶためのプログラムを作成する.

MOO は, Hit & Blow, Cow & Bull などさまざまな名で呼ばれ, 親しまれて きた数当てゲームである. ゲームのルールは以下のようになっている.

人間同士でプレイするのも楽しいが,その場合は相手が必要であるし,bull 数とcow数を間違えて答えられたりするとゲームそのものが成り立たなくなっ てしまう.そこで,コンピュータに出題者をさせるプログラムを作成してみる.
コンピュータに解答させるプログラムはそれはそれで面白い.かなり単純な プログラムでも人間のエキスパートレベルに達するし,工夫をすると更に良く なる.なお,平均質問数を最小にする戦略は計算されている.


作成プログラムの概要

プログラムを作成する前に,決めなくてはいけないことがいくつかある.ま ずは,どのようなユーザインタフェースを用意するかである.しかし,いまの ところGUI(Graphical User Interface)プログラムは想定していないので, CUI(Character User Interface)でキーボードからの入力で操作することにする.

また,繰り返しゲームをプレイするプログラムを作るか,1回だけゲームをプ レイするプログラムにするかが問題になる.プログラムの作成しやすさを考え て,1回だけゲームをプレイするプログラムにしてみよう.

ktanaka@ux019> java Kadai1106
Guess a Moo number  入力を促す1行(メッセージは任意を表示) 
0123  4桁の数字 
1:1B1C   メッセージ内部に 「数字」「大文字B」「数字」「大文字C」 という文字列(すべていわゆる半角)を含む 
0245
2:0B0C
6137
3:1B2C
3178
4:2B1C
3179
5:2B0C
3168
6:2B2C
3186
7:4B0C  正解の時も4B0C を表示する 
Correct answer in 7

プログラム全体の流れは以下のようになるはずである.

  1. 正解のMOO数を乱数で生成する
  2. ユーザの入力を受け取る
  3. 正解と一致したら解答回数を表示して,プログラムを終了
  4. 正解とのMOO積を表示
  5. 2に戻る.

クラスの設計

MOO数は4桁の数なので int で表しても良いが,ある概念に対応するものなの で,クラスを作る.クラス名は MooNumber とする.
// Moo数を表すクラス
class MooNumber{
}
まずは,MOO数をどのようなインスタンス変数で保持するか考える.10000以 下の整数でも表せるし,MOO積を高速に計算するためには,どの数が使われて いるかというビットの配列を使うなどのテクニックもあるが,今回のプログラ ムは速度を使わないので,4桁の10進数に対応した配列で表現して良い.コン ストラクタの中で配列の実体を確保しても良いが,インスタンス変数の初期化 でおこなっても良い.
// Moo数を表すクラス
class MooNumber{
  // 4桁の10進表現に対応した配列
  int digits[]=new int[4];
}
コンストラクタは2種類用意する.まずは問題を出題する際に,乱数でMOO数 を作るためのもので,これは引数なしで呼ぶ.次は,ユーザの入力した文字列 からMOO数を作成する時で,これは文字列を引数として呼ぶ.まずは,乱数で MOO数を作るための方法を見ていく.乱数を生成するには,Random クラスを使う.このクラスのインスタンスを作成してから,nextInt(int) メソッドを呼んで,0から指定した数までの一様乱数を作成することができる.

MOO数を作るには,0123456789という列を作ってから,0(番目の要素)と 0-9 (の範囲の乱数を添字とする tmpDigitsの要素)の入れ換え,1と1-9,2と 2-9, 3と3-9を入れ換えていく.以下のようになる.

  // 乱数でのMOO数の生成
  // 0123456789を並び替えて最初の4桁
  MooNumber(){
    int tmpDigits[]=new int[10];
    int i;
   // tmpDigitsに 0123456789を入れる
    for(i=0;i< 10;i++){
      tmpDigits[i]=i;
    }
    // 乱数を生成するためのクラス
    Random r=new Random();
    // 0 と 0-9(の範囲の乱数を添字とする tmpDigitsの要素)を, 
    // 1と1-9を, 2と2-9を,3と3-9を入れ換える
    for(i=0;i< 4;i++){
      int j=i+r.nextInt(10-i);
      digits[i]=tmpDigits[j];
      tmpDigits[j]=tmpDigits[i];
    }
  }
文字列を元にしたコンストラクタは実現が簡単だが,正しくない入力があっ た時に,例外を返す必要がある.本来は Exceptionのサブクラスを作っておく のが良いが,ここではさぼって,Exception のインスタンスを throw するよう にする.
  // 文字列から対応するMoo数を作る
  MooNumber(String str) throws Exception{
    if(str.length() != 4){
      throw new Exception("Not a Moo Number");
    }
    // 同じ数字が2回使われないかどうかのチェック
    boolean used[]=new boolean[10];
    for(int i=0;i< 4;i++){
      // strのi番目の文字が 0-9にあてはまるか?
      int index="0123456789".indexOf(str.charAt(i));
      // 0-9以外の文字か,index番目の数字が既に使われた時
      if(index == -1 || used[index]){
	throw new Exception("Not a Moo Number");
      }
      // index番目の数字が使われた
      used[index]=true;
      // インスタンス変数 digitのi桁目をindexにする.
      digits[i]=index;
    }
  }
MooNumberクラスの重要なメソッドとして,別のMoo数とのMoo積を求めるとい うことがある.MOO積を bull, cowのペアとして一度に扱うのも可能だが,こ こでは bull を求める getBull, cowを求める getCowを別に定義する.
  // 別のMoo数との間のbullを数える
  int getBull(MooNumber m){
    int bull=0;
    for(int i=0;i< 4;i++)
      if(digits[i]==m.digits[i])
	bull++;
    return bull;
  }
  // 別のMoo数との間のcowを数える
  int getCow(MooNumber m){
    int cow=0;
    for(int i=0;i< 4;i++)
      for(int j=0;j< 4;j++)
	if(i!=j && digits[i]==m.digits[j]){
	  cow++;
	  break;
	}
    return cow;
  }
デバッグ(プログラムのミスをチェックする)などのために,MooNumberクラス のインスタンスを直接(見易く)表示すると嬉しい.そのためには,public String toStringメソッドを定義しておくと良い.
  // デバッグ用など表示に使う.
  public String toString(){
    return ""+digits[0]+""+digits[1]+""+digits[2]+""+digits[3];
  }

プログラムの作成

上で述べたMooNumberクラスを用いる場合,プログラムの以下の部分を埋めれ ばプログラムができるはずである.もちろん,自分で用意したMooNumberクラ スを使っても良い.
// Randomクラスを使うために必要
import java.util.*;
// キーボード入力のために必要
import java.io.*;
// Moo数を表すクラス
class MooNumber{
  // 4桁の10進表現に対応した配列
  int digits[]=new int[4];
  // 乱数でのMOO数の生成
  // 0123456789を並び替えて最初の4桁
  MooNumber(){
    int tmpDigits[]=new int[10];
    int i;
   // tmpDigitsに 0123456789を入れる
    for(i=0;i< 10;i++){
      tmpDigits[i]=i;
    }
    // 乱数を生成するためのクラス
    Random r=new Random();
    // 0 と 0-9(の範囲の乱数を添字とする tmpDigitsの要素)を, 
    // 1と1-9を, 2と2-9を,3と3-9を入れ換える
    for(i=0;i< 4;i++){
      int j=i+r.nextInt(10-i);
      digits[i]=tmpDigits[j];
      tmpDigits[j]=tmpDigits[i];
    }
  }
  // 文字列から対応するMoo数を作る
  MooNumber(String str) throws Exception{
    if(str.length() != 4){
      throw new Exception("Not a Moo Number");
    }
    // 同じ数字が2回使われないかどうかのチェック
    boolean used[]=new boolean[10];
    for(int i=0;i< 4;i++){
      // strのi番目の文字が 0-9にあてはまるか?
      int index="0123456789".indexOf(str.charAt(i));
      // 0-9以外の文字か,index番目の数字が既に使われた時
      if(index == -1 || used[index]){
	throw new Exception("Not a Moo Number");
      }
      // index番目の数字が使われた
      used[index]=true;
      // インスタンス変数 digitのi桁目をindexにする.
      digits[i]=index;
    }
  }
  // 別のMoo数との間のbullを数える
  int getBull(MooNumber m){
    int bull=0;
    for(int i=0;i< 4;i++)
      if(digits[i]==m.digits[i])
	bull++;
    return bull;
  }
  // 別のMoo数との間のcowを数える
  int getCow(MooNumber m){
    int cow=0;
    for(int i=0;i< 4;i++)
      for(int j=0;j< 4;j++)
	if(i!=j && digits[i]==m.digits[j]){
	  cow++;
	  break;
	}
    return cow;
  }
  // デバッグ用など表示に使う.
  public String toString(){
    return ""+digits[0]+""+digits[1]+""+digits[2]+""+digits[3];
  }
}
class Kadai1106{
  public static void main(String [] args) throws Exception{
   // この部分を埋めて下さい.
  }
}

提出

プログラムが正しく動くことが分かったら, ことを確認の上で,センターのUnixサーバ上で
/home/ktanaka/bin/report1106 1
を実行する.プログラムのコンパイル実行をチェックした上で,プログラムを コピーし,実行結果を記録する.なお,このプログラムを通っても正しくない プログラムはありうる.その場合は減点されることもある.


提出締切りは 11/13(火)の21時まで
オプション課題

この問題に興味があって, 以下のようなことにチャレンジした人は,ローカルニュースグループ lectures.g01.cp1-ktanaka-W-Tue-5 上に投稿してください. 以前, 計算機プログラミングI 共通掲示板も投稿先に指定しておきましたが,そちらの方はそのような目的に使えないようなので,取り消します.