最近CodeIQでちょこちょこ問題を解いています。

その中でこの問題を解いてみた。

今週のお題：7セグメントコードの反転

7セグメントディスプレイ

詳しくはこちら参照→Wikipedia: 7セグメントディスプレイ

７桁の２進数を使って０〜９の数字を表現することができるディスプレイのこと。

原理はこんな感じ↓(CodeIQ様より引用)

問題

肝心の課題は要約すると

「7セグメントディスプレイで1,0の切り替え回数を最も少なく0から9を表現するとき、切り替え回数は何回か」

というもの。

ここで言う切り替え回数とは、例えば以下の場合は1,3,4,5,7桁目を切り替えればいいので切り替え回数は５回。

１→２

1 → 0110000

2 → 1101101

０〜９の数字を並び替えて、切り替え回数が最も少なくなる時の回数を求めよとの問題。

解答

回答方法に指定はなかったので、Pythonで求めてみた。

              #!/usr/bin/python
              # -*- coding: utf-8 -*-
              
              # 切り替え回数を入れる
              tmp_ans = 0
              ans = 100
              
              # セグメントの順番
              order = []
              ans_order = []
              
              def check_change(before,after):
                  res = 0
                  for (b,a) in zip(before,after):
                      if b != a:
                          res += 1
                  return res
              
              # n = セグメントの順番
              def make_segment(array, order, n):
                  global ans, tmp_ans, ans_order
              
                  if n == len(array):
                      tmp_ans += check_change(order[n-2], order[n-1])
                      if ans > tmp_ans:
                          ans = tmp_ans
                          ans_order = order
                      tmp_ans -= check_change(order[n-2], order[n-1])
                      return
                  for i in range(len(array)):
                      if array[i] not in order:
                          order.append(array[i])
                          if len(order) >= 2: tmp_ans += check_change(order[n-1], order[n])
                          make_segment(array, order, n+1)
                          if len(order) >= 2: tmp_ans -= check_change(order[n-1], order[n])
                          order.pop()
                      else:
                          continue
              # main
              array = ['1111110','0110000','1101101','1111001','0110011','1011011','1011111','1110000','1111111','1111011']
              
              make_segment(array, order, 0)
              print ans
              

とりあえず０〜９の２進数表示をarrayに格納。

２つの要素を渡すと切り替え回数を求めるcheck_change関数を作成。

それでひたすら０〜９の順列を求めて総当り。

ans変数に暫定トップの答えを格納。

一応答えは出せたので提出しました。答え合わせ待ち〜

ただ、言わずもがなですが処理時間が長すぎるのでうまいこと枝切りする必要がありましたね。

いじってgistにあげようと思います。

---

※この記事は WordPress に投稿した記事を変換したものです。一部不自然な表示があるかも知れません。ご了承ください。また、記事タイトル先頭の * は WordPress から移行した記事である印です。