壊れた時計-解答編-


お待たせ?しました。前回の続きです。会社の納会で「解いたよ」という社員から声を掛けられました。既に取り組んだ人もいらっしゃるようですね。

7セグメントディスプレーの、ある3つのセグメントだけ点灯することが分かっており、
その前提で数字の0,1,2,3,4,5を見分けることが出来るセグメントの組み合わせはいくつ存在するか

という問題を解きます。結局、総当たりで計算する方法しか思いつかなかったので今回はそれをご紹介しようと思います。

基本的な考え方は以下の通りです。

  1. 7セグメントディスプレイ を元に、表示パターンを6行7列の行列に表す
  2. 7セグメントの内3セグメントが残る組み合わせを列挙
  3. 上記組み合わせのそれぞれについて、表示パターンの列を抜き出した後、行の重複が無いか判定。重複が無ければ、数字が見分けられるということになる。
  4. 行の重複が無いセグメントの組み合わせパターンを数える

今回はこれをoctaveで書いてみました。

% コメントです。
% ledは7セグメントディスプレーで数字を表すパターンを行列にしたもの。値の0が消灯、1が点灯。
%      A B C D E F G
led = [1 1 1 1 1 1 0; %0
       0 1 1 0 0 0 0; %1
       1 1 0 1 1 0 1; %2
       1 1 1 1 0 0 1; %3
       0 1 1 0 0 1 1; %4
       1 0 1 1 0 1 1];%5
patterns = []; % 数字を区別出来る組み合わせの行列。1行が一つの組み合わせ

% 1から7の数列から3つを取り出す組み合わせを列挙。1行が一つの組み合わせとなる行列
combinations = nchoosek([1:7],3);
% 全ての組み合わせを総当たり
for i=1:size(combinations,1) % 組み合わせ行列の行数を数える(7C3=7x6x5÷3x2x1=35)
  pattern = combinations(i,:); % i行目の組み合わせをベクトルに代入.:は全ての列要素を指す
  % 表示パターンの内3セグメントだけ残す。:は全ての行要素を指す。列にベクトルを指定すると1,2,3列目だけ残す、といった指定。
  remain = led(:,pattern);
  % 残ったセグメントの表示パターンを、重複を除いて数える
  d = size(unique(remain, "rows"), 1);
  if d == 6, % 0から5の6つのままなら、数字の識別が成功
    patterns = [patterns;pattern]; %patterns行列に入れる
  end;
end;

% 結果を確認
% 正解数を表示
disp(sprintf("answer=%d",size(patterns,1)));
% 残ったセグメントによる表示イメージを示す
for j=1:size(patterns,1),
  pattern=patterns(j,:);
  disp([0, pattern]);
  disp([[0:9]' led(:, pattern)]);
  disp("---");
end;

実行結果は以下の通り。前回ご紹介したのは[4,5,6]のパターンでした。3セグメントの組み合わせは35通りあるので、2/35となかなかの偶然だということが分かりました。

answer=2
   0   1   5   6
   0   1   1   1
   1   0   0   0
   2   1   1   0
   3   1   0   0
   4   0   0   1
   5   1   0   1
---
   0   4   5   6
   0   1   1   1
   1   0   0   0
   2   1   1   0
   3   1   0   0
   4   0   0   1
   5   1   0   1

[表示パターンの行列を図示]

ちなみに数字の0から9を識別するためには、セグメントは少なくとも5つ必要(情報量的には4つで十分)で、可能な組み合わせは一通り[1,2,5,6,7]だけでした。

answer=1
   0   1   2   5   6   7
   0   1   1   1   1   0
   1   0   1   0   0   0
   2   1   1   1   0   1
   3   1   1   0   0   1
   4   0   1   0   1   1
   5   1   0   0   1   1
   6   1   0   1   1   1
   7   1   1   0   0   0
   8   1   1   1   1   1
   9   1   1   0   1   1

[表示パターンの行列を図示]

以上、2013年最初のエントリでした。今年もよろしくお願いいたします。


This entry was posted in その他. Bookmark the permalink.