M.Hiroi's Home Page

続・お気楽 Java プログラミング入門

リストで遊ぼう


Copyright (C) 2016-2021 Makoto Hiroi
All rights reserved.

前回作成した連結リストを使った簡単な問題集です。

  1. リスト xs はリスト ys よりも長いか調べるメソッド longer(xs, ys) を定義してください。
  2. リスト xs の最後尾から n 個の要素を取り除くメソッド butlast(xs, n) を定義してください。
  3. リスト xs を長さ n の部分リストに分割するメソッド group(xs, n) を定義してください。
  4. リスト xs の n 番目から m - 1 番目までの要素を部分リストとして取り出すメソッド subList(xs, n, m) を定義してください。
  5. 2 つのリスト xs, ys の要素を Pair に格納し、それをリストに格納して返すメソッド zip(xs, ys) を定義してください。
  6. zip() で生成したリスト xs を 2 つリストに分離するメソッド unzip(xs) を定義してください。
  7. 連想リスト xs からキー key を探索するメソッド assoc(key, xs) を定義してください。
  8. リスト xs の要素を述語 pred で二分割するメソッド partition(pred, xs) を定義してください。
  9. リスト xs をクイックソートするメソッド quickSort(xs) を定義してください。
  10. 整列済みの 2 つのリスト xs, ys をマージするメソッド mergeList(xs, ys) を定義してください。
  11. リスト xs をマージソートするメソッド mergeSort(xs) を定義してください。
  12. リスト xs から n 個の要素を選ぶ順列を求めるメソッド permutations(n, xs) を定義してください。
  13. リスト xs から n 個の要素を選ぶ組み合わせを求めるメソッド combinations(n, xs) を定義してください。
  14. リスト xs のべき集合を求めるメソッド powerSet(xs) を定義してください。
  15. n 以下の素数を求めるメソッド sieve(n) を定義してください。
  16. マスターマインドを解くプログラムを作ってください。

Pair は組を表す immutable なクラスです。パッケージ immutable に追加して使ってください。 

//
// Pair.java : immutable な Pair
//
//             Copyright (C) 2016-2021 Makoto Hiroi
//
package immutable;

public final class Pair<T, U> {
  final private T fst;
  final private U snd;

  private Pair(T a, U b) {
    fst = a;
    snd = b;
  }

  public static <T, U> Pair<T, U> pair(T a, U b) {
    return new Pair<T, U>(a, b);
  }
  
  public T getFst() { return fst; }
  public U getSnd() { return snd; }

  public String toString() {
    return "(" + fst.toString() + ", " + snd.toString() + ")";
  }
}

●解答

リスト : 「リストで遊ぼう」の解答

import java.util.Optional;
import java.util.function.Predicate;
import immutable.ImList;
import immutable.Pair;
import static immutable.ImList.*;

public class listproblem {
  // Q01
  static <E> boolean longer(ImList<E> xs, ImList<E> ys) {
    while (!xs.isEmpty() && !ys.isEmpty()) {
      xs = xs.rest();
      ys = ys.rest();
    }
    return !xs.isEmpty();
  }

  // Q02
  static <E> ImList<E> butlast(ImList<E> xs, int n) {
    return xs.reverse().drop(n).reverse();
  }

  // Q03
  static <E> ImList<ImList<E>> group(ImList<E> xs, int n) {
    if (xs.isEmpty())
      return nil();
    else
      return cons(xs.take(n), group(xs.drop(n), n));
  }

  // Q04
  static <E> ImList<E> subList(ImList<E> xs, int n, int m) {
    return xs.drop(n).take(m - n);
  }

  // Q05
  static <K, V> ImList<Pair<K, V>> zip(ImList<K> xs, ImList<V> ys) {
    return zipWith(Pair::pair, xs, ys);
  }

  // Q06
  static <K, V> Pair<ImList<K>, ImList<V>> unzip(ImList<Pair<K, V>> xs) {
    if (xs.isEmpty()) {
      return Pair.pair(nil(), nil());
    } else {
      var ys = unzip(xs.rest());
      return Pair.pair(cons(xs.first().getFst(), ys.getFst()),
                       cons(xs.first().getSnd(), ys.getSnd()));
    }
  }
  
  // Q07
  static <K, V> Optional<V> assoc(ImList<Pair<K, V>> xs, K key) {
    return xs.findIf(p -> p.getFst() == key).map(p -> p.getSnd());
  }

  // Q08
  static <E> Pair<ImList<E>, ImList<E>> partition(Predicate<? super E> pred, ImList<E> xs) {
    ImList<E> a = nil();
    ImList<E> b = nil();
    for (E x: xs) {
      if (pred.test(x))
        a = cons(x, a);
      else
        b = cons(x, b);
    }
    return Pair.pair(a.reverse(), b.reverse());
  }

  // Q09
  static <E extends Comparable<E>> ImList<E> quickSort(ImList<E> xs) {
    if (xs.isEmpty()) return xs;
    E pivot = xs.first();
    var a = partition(x -> pivot.compareTo(x) > 0, xs.rest());
    var ys = quickSort(a.getFst());
    var zs = quickSort(a.getSnd());
    return ys.append(cons(pivot, zs));
  }

  // Q10
  static <E extends Comparable<E>> ImList<E> mergeList(ImList<E> xs, ImList<E> ys) {
    if (xs.isEmpty()) {
      return ys;
    } else if (ys.isEmpty()) {
      return xs;
    } else {
      if (xs.first().compareTo(ys.first()) <= 0)
        return cons(xs.first(), mergeList(xs.rest(), ys));
      else
        return cons(ys.first(), mergeList(xs, ys.rest()));
    }
  }

  // Q11
  static <E extends Comparable<E>> ImList<E> mergeSortSub(ImList<E> xs, int n) {
    if (n == 0) {
      return nil();
    } else if (n == 1) {
      return of(xs.first());
    } else {
      int m = n / 2;
      ImList<E> ys = mergeSortSub(xs, m);
      ImList<E> zs = mergeSortSub(xs.drop(m), n - m);
      return mergeList(ys, zs);
    }
  }

  static <E extends Comparable<E>> ImList<E> mergeSort(ImList<E> xs) {
    return mergeSortSub(xs, xs.length());
  }

  // Q12
  static <E> ImList<ImList<E>> permutations(int n, ImList<E> xs) {
    if (n == 0)
      return of(nil());
    else
      return xs.flatMap(x -> permutations(n - 1, xs.filter(y -> !x.equals(y))).map(z -> cons(x, z)));
  }

  // Q13
  static <E> ImList<ImList<E>> combinations(int n, ImList<E> xs) {
    if (n == 0) {
      return of(nil());
    } else if (n == xs.length()) {
      return of(xs);
    } else {
      return combinations(n - 1, xs.rest())
        .map(ys -> cons(xs.first(), ys))
        .append(combinations(n, xs.rest()));
    }
  }

  // Q14
  static <E> ImList<ImList<E>> powerSet(ImList<E> xs) {
    if (xs.isEmpty()) {
      return of(nil());
    } else {
      var ys = powerSet(xs.rest());
      return ys.append(ys.map(zs -> cons(xs.first(), zs)));
    }
  }

  // Q15
  static <E> ImList<E> revAppend(ImList<E> xs, ImList<E> ys) {
    for (E x: xs) ys = cons(x, ys);
    return ys;
  }

  static ImList<Integer> sieve(int n) {
    var xs = iota(2, n);
    ImList<Integer> ys = nil();
    while (true) {
      Integer p = xs.first();
      if (p * p > n) break;
      ys = cons(p, ys);
      xs = xs.rest().filter(x -> x % p != 0);
    }
    return revAppend(ys, xs);
  }

  // Q16
  static class Query {
    ImList<Integer> code;
    int bulls;
    int cows;

    Query(ImList<Integer> xs, int b, int c) {
      code = xs;
      bulls = b;
      cows = c;
    }
  }
  
  static int countBulls(ImList<Integer> xs, ImList<Integer> ys) {
    return zip(xs, ys).foldLeft((a, p) -> p.getFst() == p.getSnd() ? a + 1 : a, 0);
  }

  static int countSameNumber(ImList<Integer> xs, ImList<Integer> ys) {
    return xs.foldLeft((a, x) -> ys.contains(x) ? a + 1 : a, 0);
  }

  static boolean checkQuery(ImList<Query> qs, ImList<Integer> xs) {
    return qs.allMatch(q -> {
      int b = countBulls(q.code, xs);
      int c = countSameNumber(q.code, xs) - b;
      return b == q.bulls && c == q.cows;
    });
  }
  
  static void masterMind(ImList<Integer> answer) {
    var codeTable = permutations(4, iota(0, 9));
    ImList<Query> qs = nil();
    int n = 1;
    for (ImList<Integer> code: codeTable) {
      if (checkQuery(qs, code)) {
        int bulls = countBulls(answer, code);
        int cows = countSameNumber(answer, code) - bulls;
        qs = cons(new Query(code, bulls, cows), qs);
        System.out.printf("%d: %s, bulls = %d, cows = %d\n", n++, code, bulls, cows);
        if (bulls == 4) {
          System.out.println("Good Job!!");
          break;
        }
      }
    }
  }

  public static void main(String[] args) {
    var xs = iota(1, 8);
    var ys = iota(1, 9);
    System.out.println("----- Q01 -----");
    System.out.println(longer(ys, xs));
    System.out.println(longer(xs, ys));
    System.out.println(longer(xs, xs));
    System.out.println("----- Q02 -----");
    System.out.println(butlast(xs, 0));
    System.out.println(butlast(xs, 1));
    System.out.println(butlast(xs, 7));
    System.out.println(butlast(xs, 8));
    System.out.println("----- Q03 -----");
    System.out.println(group(xs, 2));
    System.out.println(group(ys, 3));
    System.out.println(group(xs, 4));
    System.out.println(group(ys, 5));
    System.out.println("----- Q04 -----");
    System.out.println(subList(xs, 2, 5));
    System.out.println(subList(xs, 0, 8));
    System.out.println("----- Q05 -----");
    var nList1 = zip(iota(1, 5), iota(11, 15));
    var nList2 = zip(iota(1, 6), iota(11, 15));
    var nList3 = zip(iota(1, 5), iota(11, 16));
    System.out.println(nList1);
    System.out.println(nList2);
    System.out.println(nList3);
    System.out.println("----- Q06 -----");
    System.out.println(unzip(nList1));
    System.out.println("----- Q07 -----");
    var aList = of(
      Pair.pair("foo", 10),
      Pair.pair("bar", 20),
      Pair.pair("baz", 30),
      Pair.pair("oops", 40));
    System.out.println(assoc(aList, "foo"));
    System.out.println(assoc(aList, "oops"));
    System.out.println(assoc(aList, "FOO"));
    System.out.println("----- Q08 -----");
    System.out.println(partition(x -> x % 2 == 0, xs));
    System.out.println(partition(x -> x % 2 != 0, ys));
    System.out.println("----- Q09 -----");
    var zs = of(5,6,4,7,3,8,2,9,1,0);
    System.out.println(quickSort(zs));
    System.out.println(quickSort(ys));
    System.out.println(quickSort(ys.reverse()));
    System.out.println("----- Q10 -----");
    var a = of(1,3,5,7,9);
    var b = of(2,4,6,8,10);
    System.out.println(mergeList(a, b));
    System.out.println(mergeList(b, a));    
    System.out.println(mergeList(a, a));    
    System.out.println("----- Q11 -----");
    System.out.println(mergeSort(zs));
    System.out.println(mergeSort(ys));
    System.out.println(mergeSort(ys.reverse()));
    System.out.println("----- Q12 -----");
    System.out.println(permutations(3, iota(1, 3)));
    System.out.println(permutations(4, iota(1, 4)));
    System.out.println("----- Q13 -----");
    System.out.println(combinations(3, iota(1, 5)));
    System.out.println(combinations(4, iota(1, 5)));
    System.out.println("----- Q14 -----");
    System.out.println(powerSet(iota(1, 3)));
    System.out.println(powerSet(iota(1, 4)));
    System.out.println("----- Q15 -----");
    System.out.println(sieve(100));
    System.out.println(sieve(500));
    System.out.println(sieve(1000));
    System.out.println("----- Q16 -----");
    masterMind(of(9,8,7,6));
    masterMind(of(9,4,3,1));
  }
}

●実行例

$ javac listproblem.java
$ java listproblem
----- Q01 -----
true
false
false
----- Q02 -----
(1 2 3 4 5 6 7 8)
(1 2 3 4 5 6 7)
(1)
()
----- Q03 -----
((1 2) (3 4) (5 6) (7 8))
((1 2 3) (4 5 6) (7 8 9))
((1 2 3 4) (5 6 7 8))
((1 2 3 4 5) (6 7 8 9))
----- Q04 -----
(3 4 5)
(1 2 3 4 5 6 7 8)
----- Q05 -----
((1, 11) (2, 12) (3, 13) (4, 14) (5, 15))
((1, 11) (2, 12) (3, 13) (4, 14) (5, 15))
((1, 11) (2, 12) (3, 13) (4, 14) (5, 15))
----- Q06 -----
((1 2 3 4 5), (11 12 13 14 15))
----- Q07 -----
Optional[10]
Optional[40]
Optional.empty
----- Q08 -----
((2 4 6 8), (1 3 5 7))
((1 3 5 7 9), (2 4 6 8))
----- Q09 -----
(0 1 2 3 4 5 6 7 8 9)
(1 2 3 4 5 6 7 8 9)
(1 2 3 4 5 6 7 8 9)
----- Q10 -----
(1 2 3 4 5 6 7 8 9 10)
(1 2 3 4 5 6 7 8 9 10)
(1 1 3 3 5 5 7 7 9 9)
----- Q11 -----
(0 1 2 3 4 5 6 7 8 9)
(1 2 3 4 5 6 7 8 9)
(1 2 3 4 5 6 7 8 9)
----- Q12 -----
((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))
((1 2 3 4) (1 2 4 3) (1 3 2 4) (1 3 4 2) (1 4 2 3) (1 4 3 2) (2 1 3 4) (2 1 4 3)
 (2 3 1 4) (2 3 4 1) (2 4 1 3) (2 4 3 1) (3 1 2 4) (3 1 4 2) (3 2 1 4) (3 2 4 1)
 (3 4 1 2) (3 4 2 1) (4 1 2 3) (4 1 3 2) (4 2 1 3) (4 2 3 1) (4 3 1 2) (4 3 2 1))
----- Q13 -----
((1 2 3) (1 2 4) (1 2 5) (1 3 4) (1 3 5) (1 4 5) (2 3 4) (2 3 5) (2 4 5) (3 4 5))
((1 2 3 4) (1 2 3 5) (1 2 4 5) (1 3 4 5) (2 3 4 5))
----- Q14 -----
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
(() (4) (3) (3 4) (2) (2 4) (2 3) (2 3 4) (1) (1 4) (1 3) (1 3 4) (1 2) (1 2 4)
(1 2 3) (1 2 3 4))
----- Q15 -----
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103
107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211
223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331
337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449
457 461 463 467 479 487 491 499)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103
107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211
223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331
337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449
457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587
593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709
719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853
857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991
997)
----- Q16 -----
1: (0 1 2 3), bulls = 0, cows = 0
2: (4 5 6 7), bulls = 0, cows = 2
3: (5 4 8 9), bulls = 0, cows = 2
4: (6 7 9 8), bulls = 0, cows = 4
5: (8 9 7 6), bulls = 2, cows = 2
6: (9 8 7 6), bulls = 4, cows = 0
Good Job!!
1: (0 1 2 3), bulls = 0, cows = 2
2: (1 0 4 5), bulls = 0, cows = 2
3: (2 3 5 4), bulls = 0, cows = 2
4: (3 4 0 6), bulls = 1, cows = 1
5: (3 5 6 1), bulls = 1, cows = 1
6: (6 5 0 2), bulls = 0, cows = 0
7: (7 4 3 1), bulls = 3, cows = 0
8: (8 4 3 1), bulls = 3, cows = 0
9: (9 4 3 1), bulls = 4, cows = 0
Good Job!!

●マスターマインド

マスターマインドは、0 から 9 までの重複しない 4 つの数字からなる隠しコードを当てるゲームです。数字は合っているが位置が間違っている個数を cows で表し、数字も位置も合っている個数を bulls で表します。bulls が 4 になると正解です。 

     (6 2 8 1) : 正解
---------------------------------
1.   (0 1 2 3) : cows 2 : bulls 0
2.   (1 0 4 5) : cows 1 : bulls 0
3.   (2 3 5 6) : cows 2 : bulls 0
4.   (3 2 7 4) : cows 0 : bulls 1
5.   (3 6 0 8) : cows 2 : bulls 0
6.   (6 2 8 1) : cows 0 : bulls 4

  図 : マスターマインドの動作例

今回は、私達が出した問題をコンピュータに答えてもらうことにします。それはちょっと難しいのではないか、と思った人もいるかもしれませんね。ところが、とても簡単な方法があるのです。このゲームでは、10 個の数字の中から 4 個選ぶわけですから、全体では 10 * 9 * 8 * 7 = 5040 通りのコードしかありません。コードを生成する処理は順列と同じですから、簡単にプログラムできます。

●推測アルゴリズム

次に、この中から正解を見つける方法ですが、質問したコードとその結果を覚えておいて、それと矛盾しないコードを作るようにします。具体的には、4 つの数字の順列を生成し、それが今まで質問したコードと矛盾しないことを確かめます。これは生成検定法と同じですね。

矛盾しているかチェックする方法も簡単で、以前に質問したコードと比較して、bulls と cows が等しいときは矛盾していません。たとえば、下図の例を考えてみてください。

(0 1 2 3) で bulls が 0 ですから、その位置にその数字は当てはまりません。したがって、(0 X X X) というコードは (0 1 2 3) と比較すると bulls が 1 となるので、矛盾していることがわかります。

次に (1 0 3 4) というコードを考えてみます。(0 1 2 3) の結果は cows が 2 ですから、その中で合っている数字は 2 つしかないわけです。ところが、(1 0 3 4) と (0 1 2 3) と比較すると cows が 3 になります。当たっている数字が 2 つしかないのに、同じ数字を 3 つ使うのでは矛盾していることになりますね。

次に (1 0 4 5) というコードと比較すると、bulls が 0 で cows が 2 となります。これは矛盾していないので、このコードを質問することにします。その結果が bulls = 0, cows = 1 となり、今度は (0 1 2 3) と (1 0 4 5) に矛盾しないコードを選択すればいいわけです。 

(6 2 8 1) が正解の場合

(0 1 2 3) => bulls = 0, cows = 2

           (0 1 2 3)  と比較する
     --------------------------------------------------------
           (0 X X X)  0 から始まるコードは bulls = 1
                      になるので矛盾する。
           ・・・・

           (1 0 3 4)  cows = 3, bulls = 0 になるので矛盾する

           ・・・・

           (1 0 4 5)  cows = 2, bulls = 0 で矛盾しない。
     --------------------------------------------------------

(1 0 4 5) => bulls = 0, cows = 1

次は、(0 1 2 3) と (1 0 4 5) に矛盾しない数字を選ぶ

        図 : マスターマインドの推測アルゴリズム
初版 2016 年 12 月 11 日
改訂 2021 年 2 月 28 日