ちょまど問題

■ちょまど問題（引用・加筆）
4択問題10問のテストを全部埋めて提出すると正解数がわかります。
何回提出すればすべての正解を知ることができますか。
（最後の満点となる提出は回数に含めなくてよいということ）

何回で満点とれる？【ちょまど問題に挑む人々】

　ちょまど問題を見たとき、全解答候補から点数で解答候補を絞りこんでいけば、いいな、と思ったのだけれど、すぐに(1 1 1 1 1 1 1 1 1 1)で「1」の解答の問題の個数がわかるし、((1 1 1 1 1 1 1 1 1 1)(2 2 2 2 2 2 2 2 2 2)(3 3 3 3 3 3 3 3 3 3))の試行は(4 4 4 4 4 4 4 4 4 4)の試行と同等、と思い返してしまった。そうすると、((1 1 1 1 1 1 1 1 1 1)(2 2 2 2 2 2 2 2 2 2)(3 3 3 3 3 3 3 3 3 3)(1 2 1 2 1 2 1 2 1 2)(2 3 2 3 2 3 2 3 2 3)(3 1 3 1 3 1 3 1 3 1))の試行でひとつに解答候補が絞りこめるんじゃないか？
　ところがやってみると、そんなことはなかった。
　しかも愚直に全解答候補を絞りこんでいくやり方よりも結果が悪い(試行回数が多い)。よくよく考えてみると、(1 1 1 1 1 1 1 1 1 1)の結果が点数が0でなかった場合は解答候補から(2 2 2 2 2 2 2 2 2 2)と(3 3 3 3 3 3 3 3 3 3)と(4 4 4 4 4 4 4 4 4 4)が外れてしまう。つまり((1 1 1 1 1 1 1 1 1 1)(2 2 2 2 2 2 2 2 2 2)(3 3 3 3 3 3 3 3 3 3))の試行は無駄があるということらしい。

　愚直な方法とは次のようなやり方。

1. 全解答候補を生成
2. 解答候補からランダムに解答を求める
3. 解答する
4. もどってきた点数になる解答候補のみを残す
5. 2.にもどって処理をくり返す(候補が1個になるまで)

　このやり方だとだいたい試行回数は10回以下(もっとかかると思っていたので意外だった)。時々、11回の結果がでていたけれど、点数0のとき、もうすこし絞りこめるのでそのロジックをいれたらでなくなった。

※(1 1 1 1 1 1 1 1 1 1)が0のときは1を含んだ候補は除外できる。

　ロジックで解くやり方も試してもみたのだが、どうも愚直な方法には勝てない。

※(1 1 1 1 1 1 1 1 1 1)->(2 1 1 1 1 1 1 1 1 1)で点数差が+1だったら2が正答
※(1 1 1 1 1 1 1 1 1 1)->(2 1 1 1 1 1 1 1 1 1)で点数差が0だったら1,2は誤答
※(1 1 1 1 1 1 1 1 1 1)->(2 1 1 1 1 1 1 1 1 1)で点数差が-1だったら1が正答
※(1 1 1 1 1 1 1 1 1 1)->(2 1 1 1 1 1 1 1 1 1)で9点になったら先頭以外はすべて1
….etc

　愚直な方法はランダムな処理があるので全パターンを試してみても確実とはいえないのだけれど、だいたい10回以下で正答にたどりつく模様(試したらパソコンが熱暴走してしまったので未テスト)。
(追記)200件ほどテストしてみたところ、11回が発生。うーん、残念。

;; ちょまど問題

(require 'cl)

;; (testexec 'test3 wrk)
;; (testexec 'test3 wrk (get-anser))で同じ解答の試行
(defun testexec(func allanscer &optional data)
  "テスト実行"
  (let ((anser (if data
     data
   (nth (random (length allanscer)) allanscer))))
    (set-anser anser)
    (let ((wrk (funcall func 'quest allanscer)))
      (print (format "%s:%d:%s" (get-anser)(get-count)(get-anserlist)))
      "")))
      ;; wrk)))

(defun genarate(x)
  (let ((y x)
 (wrklist nil))
    (loop repeat 10 do
   (let ((i (% y 4)))
     (setq wrklist (append1 wrklist (+ i 1)))
     (setq y (/ y 4))))
    wrklist))

;; 全解答生成
;; (setq wrk (loop for x from 1 to (expt 4 10)
;;   collect
;;   (genarate x)))

(defun get-ten(listA listB)
  "何点か"
  (apply '+ (mapcar* (lambda(x y)(if (= x y) 1 0)) listA listB)))

;; テスト提出側
(lexical-let (anser count anserlist)
  (defun set-anser(list)
    "解答を設定"
    (setq anser list)
    (setq count 0)
    (setq anserlist nil))

  (defun get-anser()
    anser)

  (defun get-count()
    count)

  (defun get-anserlist()
    anserlist)

  (defun quest(list)
    "解答。点数を返却"
    (let ((wrk (get-ten anser list)))
      (setq count (+ count 1))
      (setq anserlist (append anserlist (list (list wrk list))))
      wrk)))

(defun filter(listA listB ten)
  (remove-if-not (lambda(x)(= ten (get-ten listA x))) listB))

(defun filter2(func testlist anserlist)
  (let ((ten (funcall func testlist)))
    (when (= ten 0) (setq anserlist (filter3 anserlist testlist)))
    (filter testlist anserlist ten)))

(defun filter3(anserlist zerolist)
  (let ((wrk (loop for x in anserlist
     collect
     (if (= (count-if nil (gemmap x zerolist)) 0)
         x
       nil))))
    (remove-if nil wrk)))

(defun gemmap(now before)
  (loop for x in now
 for y in before
 collect
 (not (= x y))))

(defun test3(func allanser)
  (catch 'exit
    (let ((anserlist allanser))
      (loop for x from 1 to (length anserlist)
     do
     (setq anserlist 
    (filter2 
     func 
     (nth (random (length anserlist)) anserlist) anserlist))
     (when (= (length anserlist) 1) (throw 'exit (list x anserlist)))))))

結果：(答え):試行回数:(((点数(試行パターン)).......)

(loop repeat 10 do (testexec 'test3 wrk))

"(4 4 3 3 4 4 3 1 3 2):8:((0 (1 1 4 1 3 3 2 3 2 4)) (5 (4 2 2 4 4 1 3 1 1 2)) (4 (2 2 2 4 4 4 1 4 3 2)) (6 (3 4 3 4 4 4 3 2 1 2)) (6 (3 2 3 3 4 1 3 2 3 2)) (6 (4 3 3 4 4 2 3 2 3 2)) (4 (3 3 3 4 4 1 3 4 4 2)) (10 (4 4 3 3 4 4 3 1 3 2)))"

"(4 3 4 2 3 3 3 3 4 1):7:((0 (2 2 2 3 2 2 2 1 1 4)) (4 (4 4 4 1 3 4 1 2 4 2)) (3 (3 1 4 1 4 4 1 3 2 1)) (3 (1 1 4 2 1 4 4 2 4 3)) (1 (3 4 3 4 4 1 1 2 4 3)) (7 (1 3 4 1 3 3 3 4 4 1)) (10 (4 3 4 2 3 3 3 3 4 1)))"

"(4 3 3 1 2 2 1 4 2 4):7:((2 (4 4 3 4 4 3 3 2 1 2)) (1 (1 2 4 3 4 3 4 3 4 4)) (2 (2 4 4 1 3 2 2 1 1 3)) (7 (4 3 1 2 2 2 1 4 1 4)) (8 (4 3 1 1 2 2 1 2 2 4)) (6 (4 3 1 2 3 2 1 2 2 4)) (8 (4 3 1 1 2 2 3 4 2 4)))"

"(3 4 1 4 1 4 3 1 4 2):9:((1 (2 2 2 3 2 4 1 2 2 3)) (1 (1 2 1 1 4 1 2 4 1 1)) (4 (2 3 3 4 4 2 4 1 4 2)) (4 (3 1 1 2 2 2 4 1 4 4)) (5 (3 1 3 4 3 1 3 1 4 3)) (4 (3 1 3 4 1 3 4 1 2 1)) (3 (3 1 3 4 4 2 3 2 3 4)) (4 (3 1 3 1 3 4 4 3 4 2)) (10 (3 4 1 4 1 4 3 1 4 2)))"

"(2 1 4 4 4 2 4 4 4 2):10:((4 (3 1 1 2 4 2 4 2 3 3)) (4 (4 1 2 3 4 4 4 3 4 3)) (2 (4 4 1 1 4 2 2 3 2 3)) (3 (3 3 2 3 4 3 4 2 2 2)) (3 (2 1 1 3 4 4 3 2 1 1)) (4 (1 4 4 2 4 4 4 2 4 4)) (3 (3 1 3 2 4 3 3 3 4 4)) (5 (2 1 4 1 3 3 4 2 4 3)) (5 (2 2 3 4 4 1 4 2 4 3)) (10 (2 1 4 4 4 2 4 4 4 2)))"

"(2 4 4 1 3 2 4 2 1 1):8:((3 (4 3 4 3 2 3 2 4 1 1)) (2 (4 2 2 4 3 1 3 4 4 1)) (3 (4 4 3 1 1 3 4 4 3 2)) (1 (4 1 1 2 2 3 1 2 4 2)) (3 (3 3 4 1 1 1 3 3 1 2)) (8 (1 4 4 1 3 4 4 2 1 1)) (6 (1 3 3 1 3 4 4 2 1 1)) (10 (2 4 4 1 3 2 4 2 1 1)))"

"(3 2 1 3 1 4 2 1 1 3):8:((5 (3 1 1 1 1 4 2 2 3 4)) (3 (2 3 3 1 1 4 2 2 4 1)) (3 (4 3 1 4 4 4 2 4 3 4)) (2 (3 4 3 1 1 2 3 4 3 4)) (4 (3 1 2 1 4 4 2 3 1 2)) (2 (3 1 2 4 2 1 2 2 3 1)) (5 (3 2 1 1 4 4 4 2 2 3)) (10 (3 2 1 3 1 4 2 1 1 3)))"

"(1 2 4 1 4 4 3 2 3 4):8:((1 (2 1 2 3 3 3 1 3 1 4)) (4 (1 4 1 2 3 4 4 2 3 1)) (2 (1 2 1 2 2 3 4 1 4 3)) (2 (3 2 3 4 3 1 4 2 2 1)) (2 (2 4 1 1 1 2 2 2 4 1)) (2 (4 4 4 2 1 4 4 3 2 2)) (4 (1 1 4 4 2 4 2 4 3 1)) (5 (4 1 1 4 4 4 3 2 3 3)))"

"(1 3 4 2 2 1 1 1 3 3):8:((4 (4 3 2 2 1 1 4 1 2 2)) (2 (4 3 2 1 3 4 4 4 3 4)) (3 (4 4 4 2 1 1 2 4 1 1)) (3 (4 2 3 2 3 1 3 2 2 3)) (3 (4 2 4 3 2 3 4 1 2 1)) (2 (3 2 2 3 1 1 3 1 1 4)) (3 (2 2 1 2 2 1 4 4 4 2)) (10 (1 3 4 2 2 1 1 1 3 3)))"

"(2 1 1 2 2 1 3 2 2 4):10:((2 (3 1 2 2 4 3 1 1 3 1)) (2 (3 2 1 1 1 2 2 4 3 4)) (3 (4 1 1 3 2 3 2 3 1 3)) (2 (4 4 3 3 1 3 3 2 3 2)) (4 (2 1 4 4 3 3 2 2 4 4)) (3 (2 1 2 4 1 2 3 3 4 3)) (2 (3 3 3 4 2 3 4 3 4 4)) (3 (2 1 3 4 4 1 2 4 1 2)) (1 (1 4 2 4 3 3 2 4 2 3)) (10 (2 1 1 2 2 1 3 2 2 4)))"


(loop repeat 15 do (testexec 'test3 wrk (get-anser)))

"(1 1 4 3 4 1 3 3 3 3):7:((2 (2 3 2 3 1 2 3 2 1 2)) (3 (4 4 1 3 2 4 1 3 3 2)) (0 (4 4 3 1 1 4 2 4 1 1)) (1 (2 3 1 4 2 1 1 1 4 4)) (3 (3 2 2 2 3 2 1 3 3 3)) (3 (1 2 1 2 4 3 4 2 3 2)) (6 (1 1 1 3 3 3 3 3 2 3)))"

"(1 1 4 3 4 1 3 3 3 3):9:((2 (2 4 4 1 1 4 1 1 3 2)) (3 (1 3 1 3 4 3 1 2 1 2)) (2 (2 2 1 3 3 4 4 2 4 3)) (1 (4 3 3 3 1 2 4 4 2 2)) (4 (1 4 1 4 4 4 3 3 2 4)) (4 (1 2 4 1 4 3 3 4 4 4)) (2 (4 4 1 2 4 3 3 1 4 1)) (3 (1 2 4 4 3 3 1 3 2 1)) (7 (1 1 4 4 4 2 3 2 3 3)))"

"(1 1 4 3 4 1 3 3 3 3):7:((0 (3 3 3 2 2 3 4 4 1 1)) (2 (2 2 4 1 1 4 2 1 2 3)) (4 (4 4 2 3 4 2 2 2 3 3)) (3 (4 4 4 4 4 4 3 2 4 4)) (3 (1 4 1 4 3 2 2 3 4 3)) (6 (1 2 4 3 4 2 1 3 3 4)) (2 (1 2 2 4 1 2 1 2 3 4)))"

"(1 1 4 3 4 1 3 3 3 3):9:((4 (1 3 1 1 4 1 3 1 4 2)) (4 (1 2 1 3 3 1 1 1 3 1)) (5 (1 4 1 1 2 1 2 3 3 3)) (6 (1 1 1 3 2 4 3 3 3 2)) (5 (1 1 1 2 1 1 4 3 3 2)) (6 (1 3 1 3 4 4 4 3 3 3)) (4 (1 4 1 4 4 4 1 3 3 2)) (8 (3 1 1 3 4 1 3 3 3 3)) (10 (1 1 4 3 4 1 3 3 3 3)))"

"(1 1 4 3 4 1 3 3 3 3):8:((4 (1 1 2 2 2 2 3 1 3 2)) (5 (1 1 1 3 2 4 4 3 3 4)) (3 (2 1 3 3 2 3 4 2 3 2)) (3 (1 1 1 4 1 4 1 4 3 2)) (2 (2 1 2 2 2 4 1 3 4 4)) (4 (1 3 4 1 2 4 4 1 3 3)) (3 (3 4 1 3 2 4 3 1 3 1)) (2 (1 2 1 2 3 3 4 1 3 4)))"

"(1 1 4 3 4 1 3 3 3 3):9:((1 (2 3 1 3 2 4 2 1 2 1)) (5 (3 1 4 2 4 2 3 1 1 3)) (4 (3 4 4 2 4 3 1 3 2 3)) (3 (3 1 4 4 4 2 4 4 2 2)) (2 (3 2 2 2 4 1 1 1 1 2)) (4 (2 4 4 1 4 2 3 3 1 4)) (6 (3 2 4 3 1 2 3 3 3 3)) (3 (3 4 4 2 1 2 3 2 3 1)) (5 (4 1 4 3 1 2 1 3 1 3)))"

"(1 1 4 3 4 1 3 3 3 3):9:((2 (1 3 2 2 1 2 3 1 4 1)) (3 (2 2 4 4 1 1 2 3 4 4)) (4 (1 4 2 4 3 4 2 3 3 3)) (3 (2 4 2 3 4 2 2 2 3 4)) (2 (4 4 1 4 4 3 2 1 4 3)) (2 (3 2 3 2 1 4 2 2 3 3)) (6 (1 2 2 3 4 1 4 3 2 3)) (2 (1 2 2 4 4 4 4 4 2 4)) (10 (1 1 4 3 4 1 3 3 3 3)))"

"(1 1 4 3 4 1 3 3 3 3):6:((3 (1 4 2 4 3 2 3 4 2 3)) (4 (1 3 1 1 3 1 3 3 4 4)) (5 (1 1 1 2 4 1 4 4 4 3)) (5 (1 2 2 3 2 1 4 3 4 3)) (7 (1 2 1 3 4 1 3 1 3 3)) (8 (1 2 4 2 4 1 3 3 3 3)))"

"(1 1 4 3 4 1 3 3 3 3):7:((0 (3 2 2 4 1 4 1 4 2 2)) (4 (1 4 4 3 2 1 2 2 4 4)) (3 (4 3 1 3 3 1 2 1 4 3)) (2 (1 3 1 1 4 2 2 2 1 4)) (5 (1 3 4 2 2 3 3 3 4 3)) (5 (4 1 4 3 2 3 3 2 1 3)) (6 (1 1 4 3 4 3 3 1 4 1)))"

"(1 1 4 3 4 1 3 3 3 3):9:((1 (2 3 4 4 2 4 4 4 2 2)) (3 (2 1 2 3 3 1 2 1 4 4)) (3 (3 1 3 2 2 2 3 1 4 3)) (7 (3 4 4 3 3 1 3 3 3 3)) (5 (3 2 4 3 3 2 3 3 3 4)) (6 (3 1 4 1 3 1 1 3 3 3)) (4 (3 4 4 3 3 3 1 3 4 3)) (9 (4 1 4 3 4 1 3 3 3 3)) (8 (4 1 4 3 1 1 3 3 3 3)))"

"(1 1 4 3 4 1 3 3 3 3):8:((2 (2 2 2 2 1 1 1 3 2 1)) (1 (2 3 3 1 3 3 2 1 2 3)) (2 (4 2 4 4 2 3 3 2 4 1)) (2 (3 4 2 4 2 1 2 4 3 2)) (2 (3 4 4 2 4 4 4 2 2 4)) (2 (3 1 1 3 1 3 1 2 1 2)) (6 (1 1 4 4 1 2 4 3 3 3)) (2 (1 2 1 4 1 2 4 1 3 4)))"

"(1 1 4 3 4 1 3 3 3 3):9:((3 (2 1 2 3 3 1 1 1 4 4)) (2 (3 4 3 1 1 1 1 1 2 3)) (2 (4 2 2 4 1 1 2 3 4 2)) (1 (4 4 1 2 4 3 1 4 4 4)) (2 (2 3 2 1 2 2 3 2 4 3)) (2 (2 2 4 3 1 4 1 2 1 1)) (5 (4 1 4 4 3 4 3 1 3 3)) (4 (2 1 3 2 3 4 2 3 3 3)) (2 (3 1 2 4 3 4 4 4 1 3)))"

"(1 1 4 3 4 1 3 3 3 3):9:((4 (4 1 4 2 2 1 3 4 4 4)) (1 (4 4 1 2 1 4 3 4 2 2)) (2 (3 2 3 2 4 1 1 2 4 4)) (5 (4 1 4 3 4 2 4 3 1 4)) (6 (1 1 4 3 3 1 4 3 4 2)) (5 (2 1 4 3 2 1 1 3 1 2)) (4 (3 1 4 3 3 1 4 4 1 1)) (7 (1 1 4 3 1 1 2 3 3 4)) (10 (1 1 4 3 4 1 3 3 3 3)))"

"(1 1 4 3 4 1 3 3 3 3):10:((2 (2 1 1 1 1 3 4 4 4 3)) (3 (3 4 1 3 4 1 2 1 4 4)) (3 (4 4 1 4 1 1 3 3 2 2)) (1 (3 2 3 2 1 1 1 4 2 4)) (2 (4 3 1 1 2 2 3 1 3 4)) (2 (3 3 4 4 2 3 2 3 4 2)) (5 (2 1 4 4 4 1 3 1 1 1)) (3 (1 1 1 4 4 4 1 1 1 2)) (4 (4 1 2 1 4 1 2 3 1 1)) (10 (1 1 4 3 4 1 3 3 3 3)))"

"(1 1 4 3 4 1 3 3 3 3):7:((2 (1 3 3 1 4 4 2 4 4 1)) (1 (2 4 4 1 2 2 4 2 2 1)) (2 (4 3 1 4 3 1 4 4 3 4)) (2 (3 3 2 3 1 3 2 2 3 2)) (3 (3 4 3 4 3 3 3 3 4 3)) (0 (3 2 3 2 3 4 1 2 1 4)) (3 (1 1 1 4 1 2 3 1 4 2)))"