問題
まずはこの問題を解いて欲しい
これは会社の同僚に出された問題です。
100個のチョコレートがあります。
その内の1個には毒が入っています。
一口でも食べると20時間前後で必ず死にます。
毒見役を使って24時間以内に毒が入ったチョコレートを見つけるためには、
最低何人の毒見役が必要でしょうか。
※毒見役は何個でもチョコレートを食べることができます。
※毒は前兆なく突然死ぬことになります。
解説
最初問題を出された時にすぐには解けなくヒントをもらいました。
そのもらったヒントがエンジニアなら解けるというもので
やっとのことたどり着いたのは2進数で正解は、必要な毒見役は7人です。
7人なった、経緯を解説していきます。
まずチョコレートに1から100まで番号を割り振りこれを2進数に置き換える。
1 | 0000001 |
2 | 0000010 |
3 | 0000011 |
4 | 0000100 |
: | : |
99 | 1100011 |
100 | 1100100 |
7人の毒見役を2進数のそれぞれの桁に割り振り、自分の桁が1の場合にチョコレートを食べるようにする。
そして20時間後に死んだ毒見役が担当していた桁を1として2進数から10進数に置き換えると毒チョコレートの番号が見分けることが出来る。
例えば55番が毒入りのチョコレートの倍は、1,2,3,5,6桁目の毒見役5名が死ぬことになる。
フラグ管理
今回は2進数でのフラグ管理を応用した問題でした。
我々エンジニアがよく見かける2進数を使ったフラグ管理といえばLinuxなどのファイル/ディレクトリの権限設定ではないだろうか?
$ chmod 764 hoge.txt
これはファイルの権限を以下のように割り振り
10進数 | 2進数 | 権限 |
4 | 100 | 読込 |
2 | 010 | 書込 |
1 | 001 | 実行 |
それぞれの桁数に意味をもたせ0,1で権限のON/OFFを制御しています。
4(読込)+2(書込)+1(実行)=7(111)
4(読込)+2(書込)=6(110)
4(読込)=4(100)
Pythonでの利用方法
さていよいよ本題ですが、Pythonでも2進数でのフラグ管理は利用できます。
ここではビット演算子の論理積(&)と論理和(|)を先程のLinuxのファイル権限を例にプログラムを書いてみました。
フラグON
FLAG_1 = 1 # 実行権限 FLAG_2 = 2 # 書込権限 FLAG_3 = 4 # 読込権限 hoge = 0 #読込権限付与 hoge |= FLAG_3 print (hoge) #書込権限付与 hoge |= FLAG_2 print (hoge) #実行権限付与 hoge |= FLAG_1 print (hoge)
実行結果
$ python3 test.py 4 6 7
この様に最終的にすべての権限がONになり7(111)という結果になっています。
続いてフラグOFF
FLAG_1 = 1 # 実行権限 FLAG_2 = 2 # 書込権限 FLAG_3 = 4 # 読込権限 hoge = 7 #読込権限取り消し hoge -= hoge & FLAG_3 print (hoge) #書込権限取り消し hoge -= hoge & FLAG_2 print (hoge) #実行権限取り消し hoge -= hoge & FLAG_1 print (hoge)
実行結果
$ python3 test.py 3 1 0
フラグの検知
ちなみにフラグの検知はこの様にやります。
FLAG_1 = 1 # 実行権限 FLAG_2 = 2 # 書込権限 FLAG_3 = 4 # 読込権限 hoge = 0 #読込権限付与 hoge |= FLAG_3 print (hoge) if hoge & FLAG_3: print ("読込権限") if hoge & FLAG_2: print ("書込権限") if hoge & FLAG_1: print ("実行権限")
実行結果
$ python3 test.py 4 読込権限
最後に
私は、このフラグ管理を使ったプログラムは、検索処理で一致度が高いもの順位ソートするときなどに使ったことがあります。
左に行くほど優先度を高くして一致している項目のフラグをONにして
出来上がった数字を元にソートする処理です。