プログラマ脳を鍛える数学パズル 11

フィボナッチ数の中で、各桁を足し合わせた数で割り切れるものを 5 つ探しなさい。
1, 3, 5,8, 21,144 まではわかっているので、それ以降を探しなさい。

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

start = 144
limit = 5


def is_matched(num):
    str_num = str(num)
    for idx in range(len(str_num) - 1, 0, -1):
        str_num = str_num[:idx] + '+' + str_num[idx:]
    sum_val = eval(str_num)
    return num % sum_val == 0


def limted_fib(left, right, results):
    next = left + right
    # 再起終了条件
    if is_matched(next) and next > start:
        results.append(next)
        if len(results) >= limit:
            return results
    # fib 継続
    return limted_fib(right, next, results)


results = limted_fib(1, 1, [])
print(results)

メソッド分離したので冗長になってるけど多分見やすいはず。
各桁足し合わせは、文字列化して「+」を挿入。eval で評価した。

模範解はどれもメモ化してたが、あれは引数をコールスタックに貯めない為の知恵なのだろうか…

プログラマ脳を鍛える数学パズル 10

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

# ルーレットのマスを作るのが面倒
eu = [0, 32, 15, 19, 4, 21, 2, 15, 17, 34, 6, 27, 13, 36, 11, 30, 8, 23, 10, 5, 24, 16, 33, 1, 20, 14, 31, 9, 22, 18, 29, 7, 28, 12, 35, 3, 26]
us = [0, 23, 9, 26, 30, 11, 7, 20, 32, 17, 5, 22, 34, 15, 3, 24, 36, 13, 0, 27, 10, 25, 19, 12, 8, 19, 31, 18, 6, 21, 33, 16, 4, 23, 35, 14, 2]


def sub_list(roulette, start, n):
    data = roulette[start:]
    if n > len(data):
        least = n - len(data)
        data = data + roulette[:least]
    else:
        data = data[:n]
    return data


def find_max(roulette, n):
    max = 0
    for st in range(len(roulette)):
        sub = sub_list(roulette, st, n)
        cur = sum(sub)
        if max < cur:
            max = cur
    return max


counter = 0
for n in range(2, 37):
    e_max = find_max(eu, n)
    u_max = find_max(us, n)
    if e_max < u_max:
        counter += 1

print(f'Found: {counter}')

回答見たら、メソッド分けせずにループだけで書いてた…
でも冗長かもしれないが読める方が優先てことで読める…よな？（汗

プログラマ脳を鍛える数学パズル 09

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

釣り合わない男女という問題。
問題は書籍を見るんだー説明が長文になるのでめんどい

boy, girl = (20 + 1, 10 + 1)

map = [[0 for f in range(girl)] for m in range(boy)]
map[0][0] = 1

for f in range(girl):
    for m in range(boy):
        left = 0
        bottom = 0

        if m > 0:
            left = map[m - 1][f]
        if f > 0:
            bottom = map[m][f - 1]

        # 先頭グループが釣り合うケースはカウントしない
        # もしくは、後半グループが釣り合うケースでもカウントしない
        if m == f or (boy - m == girl - f):
            left = 0
            bottom = 0

        map[m][f] = map[m][f] + left + bottom

# どういうマップになっているのかの確認用
#for line in map:
#    print([format(v, "6d") for v in line])

print(map[19][10])

多分これはマップの特定座標まで何通りの行き方があるのか計算する為の考え方と、問題文をそれに当てはめるという2つの要素が問題の趣旨だと思われる。
全力で無視するなら順列作ってさっさと判定してしまえばいい（多分見た目はもっともシンプルになる。速度にさえ目を瞑れば…）。

プログラマ脳を鍛える数学パズル 08

前後左右に動けるロボットが存在し、こいつが 12 回移動したとすると、移動経路は何通り考えられるか？
ただし一度移動したルートを踏むことはできないこととする。

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

ということで、アルゴリズムらしくなってきた？感じですね。

再起であぼん

def count_move(log, max_move):
    if len(log) == max_move + 1:
        return 1

    patterns = 0
    for move_to in [(0,1), (1,0), (0, -1), (-1, 0)]:
        x, y = log[-1]
        x += move_to[0]
        y += move_to[1]
        position = (x, y)
        if position in log:
            continue
        else:
            nlog = log[:]
            nlog.append(position)
            patterns += count_move(nlog, max_move)
    return patterns

print(count_move([(0, 0)], 12))

1. 初期座標含めて 13 (12 + 初期座標)個座標を格納したら 1 を返す。
2. その場所から前後左右をとりあえず移動できるなら移動して、次の再起へ進む
3. 帰ってきた 1 と蓄えて、再起の呼び出し元に通知

を繰り返す。
全幅探索だったっけか深さ優先探索だったか…

python３て末尾再起最適化ないんだっけ…デコレータつかって擬似末尾再起最適化はあったのだけど…
あるなら書き直す。

プログラマ脳を鍛える数学パズル 07

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

1964/10/10 から 2020/7/25 までの日付を

1. 8 桁整数に直す
2. 二進数に変換する
3. 前後の並びを反転する
4. 数字に戻す

この時 4 の結果と 1 が一致する日付を探す…というもの

これは多分日付ライブラリの使い方を問う問題

from datetime import date, timedelta

current_date = date(1964, 10, 10)
end_date = date(2020, 7, 25)

while end_date > current_date:
    date_int = int(current_date.strftime('%Y%m%d'))
    str_bin = bin(date_int)[2:]
    reverse = str_bin[::-1]
    if str_bin == reverse:
        # 二進数で回文すれば同じ日付やろ
        print(current_date)
    current_date = current_date + timedelta(days = 1)

date の関数が何使うか分からなかったので、help(date) すると、ドキュメントが現れる。
これは関数のドキュメントコメントなのだけど、インタラクティブシェルでこれが見れるのは Python ならでは。

あと、使い方に迷ったら REPL(Read Eval Print Loop. 読み取ってその場で解釈して print するループ。要するにシェルみたいに書いたその場で実行する環境)できるのも強い。
ちなみに Java は 10 から確か使えたはず。Scala は言うに及ばず、Ruby/PHP なんかもこれができる。というかVM持ってるような言語は大体できる。
ちょっと調べて見たら IGCC なんて C/C++ 用 REPL があった…公式言語仕様じゃないけどマジか…

プログラマ脳を鍛える数学パズル 06

改変型コラッツ予想。
最初に 3 倍 + 1 して、コラッツ予想の処理にかけ、元の数字に戻る偶数は、10,000 までにいくつあるでしょうか？
てのがお題目。

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

この問題何を見たいんだろう…二重ループと if 文で完結するし、コラッツ予想の説明もしてるので、問題文の通り書くだけ。特にアルゴリズムも何もない気が…

counter = 0
for start in range(2, 1000, 2):
    n = start * 3 + 1
    while True:
        n = n / 2 if n % 2 == 0 else n * 3 + 1
        if n == start:
            counter += 1
        elif n == 1:
            break

print(counter)

まぁさっくり２分位で。
Python の if は後置表現と呼ばれる類のものなので、三項演算子ともまた少し違う。
Java もそういえば OSS のサンプルコードとか、Thymeleaf みたいなテンプレートエンジンの公式ドキュメントでも平然と三項演算子使ってくるよね。JavaScript でも VueJS 公式ドキュメントとかでも…
三項演算子を蛇蝎の如く嫌ってるのは、要するに読みづらい三項演算をする奴がいるからだろうか…

個人的に、if 文はあんまり気に入らなくて、if 関数が欲しいのだけど（差は、if が値をreturnするかどうか）。

暇になってきたから、言語を変えながらやってみるか？
でも Python の練習にならんしううむ…

プログラマ脳を鍛える数学パズル 4, 5

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

問題 4

出題意図は…ルールの読み替えができるかどうか…だろうか？

def cout_days(length, cutters):
    rods = 1
    days = 0
    # 棒が何本に増えたかという考え方をする。
    # 20m の棒を切っていくなら、rods が 20 本になった時点が終了地点のはずだ
    while rods < length:
        days += 1
        if rods < cutters:
            # 棒の本数が切断者を下回るなら、全ての棒が2等分されたはずだ
            rods *= 2
        else:
            # 棒の本数が切断者を上回るなら、切断者が全員仕事したはず。
            # 既存の棒を切って増やしたなら切断者の数だけ増える
            rods += cutters
    return days


print(cout_days(20, 3))  # 20m を 3 人で
print(cout_days(100, 5))  # 100m を 5 人で

問題5

MAX15 枚以下で、両替の組み合わせを計算せよ。

組み合わせを作る問題。
Python, Scala, Ruby なんかは、 combination 関数があるので、それを呼べば一発。

だけど、敢えて再起で書いてみた

max_stack = 15
memo = {}

def exchange(remain, usables, coin_stack):
    # メモがあるならそこから返す
    key = (remain, len(usables), len(coin_stack))
    if key in memo:
        return memo[key]

    if remain == 0:
        # 再起の果てで、0 円達成 = 両替できたらOK終了
        print(coin_stack)
        return 1
    elif len(coin_stack) >= max_stack:
        # コインの組み合わせが 15 を超えそうなら、NG
        return 0

    counter = 0

    for next in range(len(usables)):
        next_coins = usables[next:]  # 使えるコインの種類は、そのままか先頭から１種類減る
        next_remain = remain - next_coins[0]  # 残りの支払い金額計算して
        next_stack = coin_stack[:]
        next_stack.append(next_coins[0])  # コインスタックを増やす(表示用)
        counter += exchange(next_remain, next_coins, next_stack)

    # 戻ってきたらメモに記録
    memo[key] = counter
    return counter


print(exchange(1000, [500, 100, 50, 10], []))

メモ化しとけばはやいかなーと思ったのだけど、そもそもこれの意味があるか分からない。
メモ化は後付け。

ちなみに順列の場合は、利用可能なコインなんて引数持たずに、[500, 100, 50, 10] でしれっと再起すればいい。
再起階層にリミットがあるので、普通のマシンでバッファオーバーフローとか考える必要がないのは楽。