1つの巨大な数を掲示するだけで合否発表を行うシステムを構築してみた(番外編)

はじめに

この記事(番外編)は本編を前提として書いているので、まだの方は是非お読みください。
本編では1つの巨大な数は素数の積(合成数)でしたが、今回はsuzuki@idfortweetさんの件のツイートへのメンションのアイディアを実装します。
その内容は以下の通りです。

合格者の受験番号をkとすれば合否発表は1つの巨大な数M,
M=Σ2^k
を掲示するだけで済む。

より厳密に書けば、

合格者の受験番号数列を$a$、その$k$番目を$a_k$、合格者数を$n$としたとき、合否発表は1つの巨大な数

M := \sum_{k=1}^n 2^{a_k-1}

を掲示するだけで済む。

となります。

2進数との関係

M = \sum_{k=1}^n 2^{a_k-1}

上式で与えられる$M$を2進数変換すると$a_k(k=1,2,...,n)$桁目だけが$1$で他が$0$の数になるので、$M$を掲示するだけで全員の合否が分かります。つまり、掲示された数を2進数変換して、(あなたの受験番号)桁目の数字が1なら合格、0なら不合格というわけです。

例えば合格者受験番号列が$\{1,3,5\}$なら、$M=2^0+2^2+2^4=21$となり、2進数変換すると$10101$です。1,3,5桁目が1なので合格者受験番号列が$\{1,3,5\}$であることが分かります。

システムの簡易シミュレーターの実装

番外編なのであまり凝ったことはせず、本編のなんちゃってシミュレーターの今回のアイディア版のみを実装します。
また、システムの簡易化のため、生成する受験番号数列は受験者がn人のとき$\{1,2,3,...,n\}$であるとします。

受験番号数列の生成

受験者がn人のとき$\{1,2,3,...,n\}$なので受験番号数列Identification_numbersは受験者数nが与えられてるとして以下のように書けます。

.py

Identification_numbers=[i+1 for i in range(n)]

合否発表用巨大数の生成

M := \sum_{k=1}^n 2^{a_k-1}

この$M$(ソースコード上ではPassNumber)を求めるプログラムは、合格者の受験番号数列がPassMembersというリストで与えられているとすると以下のように書けます。

.py

PassNumber = 0
for Num in PassMembers:
    PassNumber += 2**(Num-1)

合否判定プログラムの作成

掲示された数を2進数変換して、(あなたの受験番号)桁目の数字が1なら合格、0なら不合格という判定法に基づいて、合格判定プログラムを書きます。

.py

def judge(PassNumber,judgeNum):
    PassNumber = f'{PassNumber:b}' #2進数表記に変換
    print(f'受験番号{judgeNum}は{"不"*(int(PassNumber[-judgeNum]) != 1)}合格です。')

int(PassNumber[-judgeNum]) != 1がTrueのとき不合格、Falseのとき合格なので良さそうですが、例えば10人受験したとして、合格者受験番号列が$\{1,3,5\}$なら、$M=2^0+2^2+2^4=21$となり、2進数変換すると$10101$です。このとき、受験番号10の人の合否判定をしようとするとPassNumber[-10]は存在しないのでIndexErrorになってしまいます。
これを回避するためにtry``except構文を使ってもいいのですが、ここはorを使いましょう。

.py

def judge(PassNumber,judgeNum):
    PassNumber = f'{PassNumber:b}'
    print(f'受験番号{judgeNum}は{"不"*(len(PassNumber) < judgeNum  or int(PassNumber[-judgeNum]) != 1)}合格です。')

PythonでA or Bは、AがTrueならBは実行(処理)されません。このことを使ってIndexErrorを回避しています。実際、judge(21,10)でも動作します。

合格者リストを事前に生成しておく方法もあります。

.py

def judge(PassNumber,judgeNum):
    PassNumber = f'{PassNumber:b}'
    PassMembers = [i for i,Num in enumerate(reversed(PassNumber), 1) if int(Num) == 1]
    print(f'受験番号{judgeNum}は{"不"*(judgeNum not in PassMembers)}合格です。')

reversed()は要素を逆順に取り出すイテレータをつくる組み込み関数で、enumerate(*,1)は*の要素と、その要素の1から始めたインデックスを同時に取り出すイテレータをつくる組み込み関数です。

シミュレーターの実装

以上のことを組み合わせて簡易シミュレーターを実装します。

.py

import random

def judge(PassNumber,judgeNum):
    PassNumber = f'{PassNumber:b}'
    print(f'受験番号{judgeNum}は{"不"*(len(PassNumber) < judgeNum  or int(PassNumber[-judgeNum]) != 1)}合格です。')

def simulate():
    print("受験者数を入力してください。",end='')
    examinees = int(input(">"))
    print("合格者数を入力してください。",end='')
    successfulExaminees = int(input(">"))
    Identification_numbers=[i+1 for i in range(examinees)]
    PassMembers=random.sample(Identification_numbers,successfulExaminees)

    PassNumber = 0
    for Num in PassMembers:
        PassNumber += 2**(Num-1)
    
    print(f'合否番号は{PassNumber}です。')
    
    while(True):
        print(f'合否判定をしたい受験番号を入力してください。シミュレーションを終了する場合は\'z\'と入力してください。',end='')
        judgeNum = input(">")
        if judgeNum=="z":break
        judge(PassNumber,int(judgeNum))
    
simulate()

実行例

受験者数を入力してください。
>300
合格者数を入力してください。
>250
合否番号は2032802885641225265241387045515974854776713270107571399316704393739326877057655134673153628です。
合否判定をしたい受験番号を入力してください。シミュレーションを終了する場合は'z'と入力してください。
>1
受験番号1は不合格です。
合否判定をしたい受験番号を入力してください。シミュレーションを終了する場合は'z'と入力してください。
>2
受験番号2は合格です。
合否判定をしたい受験番号を入力してください。シミュレーションを終了する場合は'z'と入力してください。
>4
受験番号4は合格です。
合否判定をしたい受験番号を入力してください。シミュレーションを終了する場合は'z'と入力してください。
>178
受験番号178は合格です。
合否判定をしたい受験番号を入力してください。シミュレーションを終了する場合は'z'と入力してください。
>300
受験番号300は不合格です。
合否判定をしたい受験番号を入力してください。シミュレーションを終了する場合は'z'と入力してください。
>z

16万人受けて2万人受かる想定

先ほどのコードでsimulate()を実行して、受験者数160000、合格者数20000にしても動作しました。
このときの巨大数は12304184726969734909077(中略)7685569926945326082という48163桁の数でした。

この方法の利点

本編でも言及しましたが、16万人中2万人の合格者の受験番号を全て掲示するには(受験番号が1,2,3,...,160000という風に単純に割り当てられていたとして)10万桁程度は必要となるので、今回取得した約5万桁の合否発表用の1つの巨大数を掲示する方が効率がいいということになります。300人中250人受かる場合はさらに顕著で、巨大数を掲示する方法だと100桁程度なのに対して、合格者の受験番号を全て掲示するには500桁以上は必要になります。ただ、合格判定が人力の暗算では難しいので実用化には向きませんが...
また、本編で示した素数を用いる方法に比べ、受験番号数列に自由があるという利点もあります。

ビット列で表示

この記事で、巨大な数は10進法で表記して2進数に変換しましたが、より分かりやすさを求めるならば最初から0(不合格)と1(合格)だけのビット列として表示することもできます。ただ、この場合桁数が増えるので分かりやすさと桁数はトレードオフですが。

おわりに

一見ふざけたように見える方法でも実際にやってみると実は優れているところもあったりするので面白いですね。

誤字脱字や誤った記述、更に良いアルゴリズム(特に、巨大数を用いたもっと効率の良い(桁数の少ない)方法)、気づいたこと、分かりにくい箇所、感想などがあればぜひコメントをください。