「水晶玉をどうぞ壊してください」

現在、この本で取り組んだ内容を記事に挙げています。

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考

前回↓

今回は5章の「水晶玉をどうぞ壊してください」を取り上げようと思います。基数表現を使った問題ですね。

はじめに

この問題を考えるにあたって前提となる要素があります。少し長くなってしまいますが本書のP53～P54を引用させていただきます。

一連の同じ種類の水晶玉の「硬度」を決定するのが今回の仕事です。 2015年に完成した有名な上海タワーは128階あります。水晶玉を高いところから落としたときに地面に当たって壊れるか、それとも壊れずに跳ね返るかを調べるのです。この重要な実験を行うときには、周囲は人がいなくて安全だと仮定します。

上海タワーで、 水晶玉を落としても壊れない最高階の階数をボスに報告します。 f階 と報告するということは、玉がf階からだと壊れないが、 f+1階からだと壊れる ( そうでなければf+1階と報告しています) という意味です。 高い階ほどボーナスが出て、 f 階と報告したのに、そこから落として玉が壊れると、罰金を取られます。 これはなんと しても避けたいことです。

玉が壊れたら、再利用はできません。壊れなければ再利用できます。玉が床に当たる落下速度が壊れるかどうかの唯一の決定要因であり、この速度が階数とともに増加するので2階から落としても壊れなかったら、より下のどの階から落としても割れないと考えます。同様に、y階から落として壊れたなら、より上のどの階から落としても割れるということです。

残念ながら、水晶玉が他の乗客を怯えさせるので、エレベーターを使うことは許可されていません。よって、階段の昇り降りが大変なので、玉を落とす回数を最小にしたいのです。

もちろん、水晶玉がいくつあるかが大問題です。 1つしかないなら、選択の余地はあ りません。 例えば、43階から落として壊れたとしたら、42階とは報告できません。42階、 41階、あるいは1階から落としてすら壊れるかもしれません。 罰金を避けるには0階と報告せねばならず、ボーナスはありません。玉が1つなら、1階から始めねばなりません。 玉が壊れたら、0階と報告、壊れなければ2階に行き、最終的には128階まで行けるか もしれません。128階で壊れなければ、幸せにも128階と報告できます。 f階から落として壊れたら、玉をf回落としました。落とす回数は最大128で、1階から128階までです。

玉が2個あればどうでしょうか。 1個を128階から落とすとしましょう。壊れなければ 128階と報告して、それで終わりで、お金が入ります。 しかし、壊れてしまったら、1 個の玉の状態に戻り、わかったのは128階では壊れるということだけです。罰金を避けてボーナスを最大にするには、2個目の玉を1階で落とし、既に述べたように1階ずつ 登って、運が良ければ127階まで上がることです。 最悪時の落とす回数は、(128階か らの) 1足す1階から127階までの127で、全部で128回です。 1個の玉のときから、進歩していません。

直感的には、128階のビルなら区間 [1,128] の中点にすべきに思えます。 いつものように、2つの場合があります。

1. 玉が壊れる。1階から63階で行うということです。 つまり、残りの玉は区間 [1,63] ということ。

2.玉は壊れない。65階から128階で行うということです。つまり、両方の玉で区間[65, 128] ということ。

最悪時の落とす回数は、第1の場合に、区間を最低階から順に上るので64です。 128 よりは良いですが、 2倍しかよくありません。

玉が2つなら、この64回よりうまくやりたいものです。 ボーナスをあきらめたくないし、罰金はまっぴらです。

ボーナスを最大にして罰金を避け、2つの玉で21回より少ない方式を考えられないでしょうか。もっと玉が多かったらどうでしょうか。 上海タワーの高さ(階数)が2倍になったらどうでしょうか。

このように、水晶玉の硬度を計測するためにビルから水晶玉を落として確認しますが、何度も落としてはビルの階段を上るのはしんどいのでなるべく水晶玉を落とす回数を少なくして計測したい、というものですね。
基数の決め方は説明が難しいですが、rを進数、dを水晶玉、nを階数とすると

となるrを選びます。n=128、r=4、d=4の場合、最初の玉をである64階から落とし、玉が壊れなければの128階から落とします。もしもその段階で壊れたら水晶玉の硬度は「から」（10進数で65階から127階）の範囲だと仮定し、（80階）から落とします。

練習問題解答

この章には練習問題が3つあります。

• 1問目は階数128、水晶玉6個を指定すると、なのでr=3が選ばれますが、とから考える必要がないので桁数を減らす必要があります。実行中に実際に使用する水晶玉の数を出力する。
• 2問目は壊れた水晶玉の数を出力すること。
• 3問目は現在考えている区間を出力すること。

これらを踏まえてコードを掲載します。

import numpy as np
from copy import deepcopy

def hard_slice_skip(n: int, d: int): # 問題解答
    """
n=階数、　d=水晶玉の数
howHardIsCrystal(128, 6)を実行すると3進数が選ばれ６桁の数字になるが、
[1, 0, 0, 0, 0, 0]はn=128を超えてしまう。
その為、ここの段落をスキップしなければならない
また、
"""
    r = 1
    broken = 0 # 壊れた水晶玉の数
    section = [] # 区間
    while (r**d <= n):
        r += 1
    print(f'{r}進数を使います。') 
    num_drops = 0
    floor_no_break = [0] * d # 基数による数値表現
    start = 0
    end = list(np.base_repr(n, r))
    for i in range(len(end)):
        end[i] = int(end[i])
    check = deepcopy(floor_no_break)
    for i in range(len(check)): # 水晶玉の数（桁数）が多い場合、減らす
        check[i] = 1
        if my_convert(check, r) > n:
            del floor_no_break[i]
            d -= 1
        check[i] = 0
    print(f"使用する水晶玉の数は{d}個です")
    
    section = [start, my_convert(end, r)]
    for i in range(d):
        
        for j in range(r-1):
            print(f'区間＝{section}')
            floor_no_break[i] += 1
            floor = my_convert(floor_no_break, r) # convertToDecimal
            if floor > n:
                floor_no_break[i] -= 1
                break
            print(f'{i+1}個目の水晶玉を{floor}から落とします。')
            yes = input('水晶玉は壊れる？(yes/no):')
            num_drops += 1
            if yes.lower() == 'yes':
                floor_no_break [i] -= 1
                end = deepcopy(floor_no_break)
                if (i+1) < len(end):
                    end[i+1] += 1
                broken += 1
                start = deepcopy(floor_no_break)
                section = [my_convert(start, r),
                           my_convert(end, r)]
                break
            else:
                start = deepcopy(floor_no_break)
                end = deepcopy(floor_no_break)
                start[-1] += 1
                end[i] += 1
                section = [my_convert(start, r),
                           my_convert(end, r)]
            print()
    print(f'区間＝{section}')
    hardness = my_convert(floor_no_break, r)
    return hardness, num_drops, broken

def my_convert(value: list, base: int) -> int:
    """与えられたリストを任意の記数法を指定して10進数に変換する"""
    num = 0
    multi = len(value) - 1
    for i in value:
        num += i * base ** multi
        if multi > 0:
            multi -= 1
    return num

def base10int(value, base):
    """10進数を任意のr進数表記にする"""
    return list(np.base_repr(value, base))

if __name__ == '__main__':
    hardness, num_drops, broken = hard_slice_skip(128, 6)
    print(f'硬度:{hardness}, 落とした回数:{num_drops}, 壊れた水晶:{broken}')

出力結果

出力結果のyesとnoは私が勝手に入力したものなので、入力によって最終的な出力は変わります。

3進数を使います。

使用する水晶玉の数は5個です

区間＝[0, 128]

1個目の水晶玉を81から落とします。

水晶玉は壊れる？(yes/no):no
区間＝[82, 162]

区間＝[82, 162]

2個目の水晶玉を108から落とします。

水晶玉は壊れる？(yes/no):yes

区間＝[81, 90]

3個目の水晶玉を90から落とします。

水晶玉は壊れる？(yes/no):no
区間＝[91, 99]

3個目の水晶玉を99から落とします。

水晶玉は壊れる？(yes/no):yes

区間＝[90, 93]

4個目の水晶玉を93から落とします。

水晶玉は壊れる？(yes/no):no
区間＝[94, 96]

4個目の水晶玉を96から落とします。

水晶玉は壊れる？(yes/no):yes

区間＝[93, 94]

5個目の水晶玉を94から落とします。

水晶玉は壊れる？(yes/no):no
区間＝[95, 95]

5個目の水晶玉を95から落とします。

水晶玉は壊れる？(yes/no):yes

区間＝[94, 94]

硬度:94, 落とした回数:8, 壊れた水晶:4