プログラム脳を鍛える数学パズル in python3

pazzle01.py

# 数年ぶりの Python.
# ついでだし Python3 でやってみたログ。
# 2,8,10 進数で回文を探す

def is_int_kai(num):
    v = str(num)
    rev = v[::-1]
    return v == rev


def is_oct_kai(num):
    v = oct(num)[2:]
    rev = v[::-1]
    return v == rev


def is_bin_kai(num):
    v = bin(num)[2:]
    rev = v[::-1]
    return v == rev

current = 10

while True:
    current += 1
    if is_int_kai(current) and is_oct_kai(current) and is_bin_kai(current):
        print('answer:' + str(current))
        break

pazzle02.py

from functools import reduce

# 1000 - 9999 までの数字で、文字列として割って四則演算したら、元の数字の並びと逆になるものを探す

positions = [
    [1], [2], [3],
    [2, 1], [3, 2], [3, 1],
    [3, 2, 1]
]


def split(str, pos, stack):
    if len(pos) == 0:
        stack.append(str)
        return stack
    else:
        i = pos[0]
        stack.append(str[i:])
        return split(str[:i], pos[1:], stack)


def multiple(l):
    return reduce(lambda a, b: a * b, l)


def is_kaibun(left, right):
    return left == right[::-1]

for cur in range(1000, 9999):
    strCur = str(cur)
    for pos in positions:
        splits = split(strCur, pos, [])
        result = multiple(map(lambda v: int(v), splitted))
        if is_kaibun(strCur, str(result)):
            print(str(splits) + " = " + str(result))
            print("success: " + strCur)

pazzle03.py

# 100 枚のカードが裏で寝そべってるとき、
# n 番目から n 枚おきにカードを裏返し、
# 最終的に裏のままのカードは何枚目だろうか？

is_card_opens = [False for i in range(100)]

for step in range(2, 101, 1):
    start = step - 1
    for index in range(start, 100, step):
        is_card_opens[index] = not is_card_opens[index]

for i in range(100):
    if not is_card_opens[i]:
        print(str(i + 1) + ", ", end='')

pazzle04.py

# ある長さの棒を、カッターで二等分していく。
# １ターンで使えるカッターの枚数に制限があるとき、
# 100m の棒を 5 枚のカッターで 100 当分するのにかかるターン数は？
#
# 綺麗に当分するのをシミュレートするのではなくて、
# １ターンで切れるだけ切って、100 切れ以上になるまでのターン数を数えてみた

max_len = 100
max_cut = 5


def cut_bar(cutter, length, cut_bar_num):
    if cut_bar_num > length:
        return 0
    elif cut_bar_num < cutter:
        return 1 + cut_bar(cutter, length, cut_bar_num * 2)
    else:
        return 1 + cut_bar(cutter, length, cut_bar_num + cutter)

print("Split finished at: " + str(cut_bar(max_cut, max_len, 1)))

pazzle05.py

# 1000 円を 10 円以上の硬貨で両替する時、15 枚以下の組み合わせは何通りある？
# Scala あたりで combination あったんだから Python にもあるだろう → あった

from itertools import combinations_with_replacement
from functools import reduce

start = 1000
coins = [10, 50, 100, 500]
limit = 15
count = 0

for length in range(2, limit + 1):
    for com in combinations_with_replacement(coins, length):
        if reduce(lambda a, v: a + v, com, 0) == start:
            count += 1
            print("Count: " + str(count) + " with: " + str(com))

print(count)

pazzle06.py

# 関数にも書いてるけど、
# 与えられた引数をコラッツ関数にかけて、元の値に戻ってくる数字を探します。
# ただし、初期値が偶数である場合、v * 3 + 1 がコラッツ計算式の初期値となります。

# この辺でドキュメントの書き方練習

def collatz(v) -> int:
    """コラッツ予想に含まれる、関数です。

    コラッツ予想は wikipedia 参照。

    >>> collatz(3)
    10
    >>> collatz(4)
    2

    :param v: 引数
    :return: 結果
    """
    if v % 2 == 0:
        return int(v / 2)
    else:
        return v * 3 + 1


def is_be_back(v) -> bool:
    """与えられた引数をコラッツ関数にかけて、元の値に戻ってくるかを判定します。

    ただし、初期値が偶数である場合、v * 3 + 1 がコラッツ計算式の初期値となります。

    >>> is_be_back(4)
    True
    >>> is_be_back(6)
    False

    :param v:
    :return:
    """
    t = v
    if v % 2 == 0:
        t = v * 3 + 1
    while t != 1:
        t = collatz(t)
        if t == v:
            return True
    return False

cnt = 0

for i in range(2, 10001, 2):
    if is_be_back(i):
        cnt += 1
        print("is back: " + str(i))

print("Answer : " + str(cnt))

import doctest
doctest.testmod()

pazzle07.py

from datetime import datetime, timedelta

# 日付を二進数にして、反転して、また日付に直した時に、回文になってる日付を探す。
# ただし 19641010 から 20200724 までの範囲。

current = datetime(1964, 10, 10)
end = datetime(2020, 7, 24)


def add_a_day(t) -> datetime:
    """指定された datetime に 1 日を追加します。

    >>> add_a_day(datetime(2017, 11, 2))
    datetime.datetime(2017, 11, 3, 0, 0)

    :param t: 追加対象のベース日付
    :return: １日後の日付
    """
    return t + timedelta(days=1)

while True:
    current = add_a_day(current)
    if current >= end:
        break

    date_str = current.strftime("%Y%m%d")
    date_num = int(date_str)
    bin_num = bin(date_num)[2:] # remove 0b prefix.
    rev_int = int(bin_num[::-1], 2)

    if date_num == rev_int:
        print("Date : " + date_str)

pazzle08.py

# １ ターンで 1m 前後左右に動き、同じところは二度と通らない ○ンバ が
# 12 ターン動いたら、そのパターンはいくつあるか？
max_move = 12


def move(log) -> int:
    """再起をしながら動作パターンのカウントをする。

　　　　　　　　○ンバを前後左右に動かして、再起をかけて行って、13 スタック目（つまり動作限界）で 1 を返す（このパターンはカウント）。
    一つ前のスタックで、その先のスタックのカウンタを総計していく再起。
    末尾再起じゃないんだよなー(Python に末尾最適化無いらしいって見るけど…)と若干の気持ち悪さを感じつつ…
    """
    if len(log) == max_move + 1:
        return 1
    cnt = 0
    last_log = log[-1]
    for mv in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        next_pos = (last_log[0] + mv[0], last_log[1] + mv[1])
        if next_pos not in log:
            cnt = cnt + move(log + [next_pos])
    return cnt

print(move([(0, 0)]))

pazzle09.py

# 男子 20 人, 女子 10 人が順不同に整列したとき、並びのどこから 2 グループに切っても
# 男女比が 1:1 のグループが生まれない並び順パターンはいくつあるか？

# 正直ヒント見ないとわからなかった…
# 経路探索問題だと教えてもらってもかなり悩んだ。
# 作ったことねーよ(~_~;)

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

ary = [[0 for n in range(girl)] for i in range(boy)]
ary[0][0] = 1

for g in range(girl):
    for b in range(boy):
        # boy 人数と girl 人数の一致する経路はカウントしない。
        if b != g and (boy - b != girl - g):
            ary[b][g] += ary[b - 1][g]
            ary[b][g] += ary[b][g-1]

print(ary[-1][-2] + ary[-2][-1])

pazzle10.py

# ヨーロッパ型ルーレットと、アメリカ型ルーレット。
# それぞれ、n 個連続した値を引っこ抜いて、合計が最大になるような引き抜き方をしたとき、
# アメリカ型ルーレットの方が値が大きくなる n は何個ある？

# ルーレットの数字分、先頭を後ろにすげ替えながら先頭 n 個の合計値を拾う。
# ちょっと自信なくてテスト書いて途中試した。
# なんというかルーレットの盤面作るのが一番大変だった気がする。

euro = [0, 32, 15, 19, 4, 21, 2, 25, 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]
usa = [0, 28, 9, 26, 30, 11, 7, 20, 32, 17, 5, 22, 34, 15, 3, 24, 36, 13,
       1, 0, 27, 10, 25, 29, 12, 8, 19, 31, 18, 6, 21, 33, 16, 4, 23, 35, 14, 2]


def find_max_sum(source, num):
    """source をリングリストと見た時のある地点から num 個を sum した時の最大値を算出します。

    >>> find_max_sum([1, 2, 3, 4, 5], 3)
    12
    >>> find_max_sum([5, 1, 2, 4, 3], 3)
    12

    :param source:
    :param num:
    :return:
    """
    tmp_max = 0
    for m in range(len(source)):
        current = sum(source[:num])
        if current > tmp_max:
            tmp_max = current
        source = source[1:] + [source[0]]
    return tmp_max

cnt = 0

for n in range(2, 37):
    euro_sum = find_max_sum(euro, n)
    usa_sum = find_max_sum(usa, n)
    print("sum: " + str(n) + " euro: " + str(euro_sum) + " usa: " + str(usa_sum))
    if euro_sum < usa_sum:
        cnt += 1

print(cnt)

import doctest
doctest.testmod()

pazzle11.py

# フィボナッチ数列のうち、144 より大きいもので、
# 各桁の数字を足して（144 → 1 + 4 + 4）、元の数を割り切れるものを５つ求める。

# 無限に数列を求めたい訳でもないので、再起よりはさっさと while で抜ける。
#
# 回答後に答えみたら値が増える方向の再起ではなくて、元の方に遡る再起が書いてあった…
# そりゃ原理的に単純だから遡れなくはないか…メモ化しながら値を全部遡っていくよりも、
# 増える再起の中で、５個目の該当数になったら return で抜けるとかした方が良さげ。
# ただ、Python だとスコープの問題があるからそこでハマりそうね。

before = 1
cur = 1
after = 144
count = 0
count_max = 5


def is_match(v):
    """v を各桁足して、v を割り切れるかどうか

    :param v:
    :return:
    """
    str_v = str(v)
    tmp = sum(map(int, str_v))
    return v % tmp == 0

while count < count_max:
    tmp = cur + before
    if tmp > after and is_match(tmp):
        print(tmp)
        count += 1
    before = cur
    cur = tmp

pazzle11_another.py

# フィボナッチ数列のうち、144 より大きいもので、
# 各桁の数字を足して（144 → 1 + 4 + 4）、元の数を割り切れるものを５つ求める。

# ということで、増える方向での再起をしてみたが…
# 微妙…

before = 1
cur = 1
after = 144
count = 0
count_max = 5


def is_match(v):
    """v を各桁足して、v を割り切れるかどうか

    :param v:
    :return:
    """
    str_v = str(v)
    tmp = 0
    for c in str_v:
        tmp += int(c)
    return v % tmp == 0


def find_fib(prev_last, last, cnt):
    if cnt == 0:
        return
    cur = prev_last + last
    if cur > after and is_match(cur):
        cnt -= 1
        print(cur)
    find_fib(last, cur, cnt)

find_fib(1, 1, count_max)

pazzle12.py

from math import sqrt

# 正の整数のうち、
# 小数点以下で 0-9 の文字が最小で出現する（≒小数点 10 桁が 0-9）整数。
# 小数点を文字として取り除いて、最小で出現する（≒整数含め先頭 10 桁が 0-9）整数。
# この二つを求める。


def is_min_match(v, conv):
    str_v = "{0:4.20f}".format(v)
    tmp = conv(str_v)[:10]
    return len(set(tmp)) == 10


def min_contain_0_to_9_all(v):
    return is_min_match(v, lambda s: s.replace(".", ""))


def min_contain_0_to_9_under_decimal(v):
    return is_min_match(v, lambda s: s[s.find(".") + 1:])

num = 1
found_min_all = False
found_min_dec = False

while not found_min_all or not found_min_dec:
    cur = sqrt(num)

    if not found_min_all and min_contain_0_to_9_all(cur):
        found_min_all = True
        print("all Found: {0} Sqrt: {1:3.10f}".format(num, cur))

    if not found_min_dec and min_contain_0_to_9_under_decimal(cur):
        found_min_dec = True
        print("dec Found: {0} Sqrt: {1:3.10f}".format(num, cur))

    num += 1

pazzle13.py

# READ + WRITE + TALK == SKILL
# でアルファベットを数字に直した時に成り立つような組み合わせはどれだけあるか？

# めんどくさいので python で順列生成して割り当てて eval

import re
import itertools
import sys

exp = "READ + WRITE + TALK == SKILL"
matches = re.findall("([a-zA-Z]+)", exp)

non_zero_chars = [v[0] for v in matches]
all_chars = list(set("".join(matches)))
char_len = len(all_chars)

if char_len > 10:
    print("Too large char pattern.")
    sys.exit()


def contains_ng(char_num_map) -> bool:
    for c in non_zero_chars:
        if char_num_map[c] == 0:
            return True
    return False

cnt = 0

for num_set in itertools.permutations(range(10), char_len):
    # char sets.
    char_map = {}
    for i in range(char_len):
        char_map[all_chars[i]] = num_set[i]

    # skip ignore pattern.
    if contains_ng(char_map):
        continue

    # as str
    fnc_str = exp
    for k in char_map.keys():
        fnc_str = fnc_str.replace(k, str(char_map[k]))

    if eval(fnc_str):
        cnt += 1
        print(fnc_str)

print(cnt)

pazzle14.py

# 国名でしりとりを作り、もっとも長く続くパターンを示せ

# 国名列挙が一番だるい。
# 再起関数に入る前に書いてるコードと、再起関数でやってるコードの一部意味が被ってて、dry で無いのが地味に気になる

countries = [
    "Brazil", "Croatia", "Mexico", "Cameroon",
    "Spain", "Netherlands", "Chile", "Australia",
    "Colombia", "Greece", "Cote d'Ivoire", "Japan",
    "Uruguay", "Costa Rica", "England", "Italy",
    "Switzerland", "Ecuador", "France", "Honduras",
    "Argentina", "Bosnia and Herzegovina", "Iran", "Nigeria",
    "Germany", "Portugal", "Ghana", "USA",
    "Belgium", "Algeria", "Russia", "Korea Republic"
]

# 大文字小文字で比較とかだるいので、小文字のリストにしてしまう
lowers = [v.lower() for v in countries]

# もっとも長いしりとり記録変数
longest = []


def join(cur, source):
    global longest

    # リスト最後の国名と、そこに繋がる候補国
    tail = cur[-1]
    afters = [v for v in source if v[0] == tail[-1]]

    # 候補がなければ再起を抜ける。
    if len(afters) == 0:
        # この時、今まででもっとも長く繋がってたら、記録を更新する。
        if len(longest) < len(cur):
            longest = cur
        return
    else:
        # 候補から国を取り出して、使ってない国一覧（コピー）からその国を引く。
        # それを次の再起に回す。
        for joint in afters:
            next_source = source[:]
            next_source.remove(joint)
            next_cur = cur + [joint]
            join(next_cur, next_source)

# 再起スタートの１国目
for country in lowers:
    tmp = lowers[:]
    tmp.remove(country)
    join([country], tmp)

print(longest)

pazzle15.py

# 一度に３段飛ばし（４歩）進める人間が、10 段の階段を上と下両方から同時に上り下りするとき
# 同じマスに偶然にも止まるパターンはいくつある？

# 二人の距離を減算する方向で再帰
max_step = 4


def step(least) -> int:
    if least == 0:
        return 1
    elif least < 0:
        return 0

    current = 0
    for l in range(max_step):
        for r in range(max_step):
            current += step(least - 2 - l - r)
    return current

print(step(10))

pazzle16.py

# 3 本の同じ長さの紐があるとき、
# 1 本を正方形にして、２本を長方形とし、長方形二つの面積 = 正方形の面積 となる組み合わせはいくつある？
# ただし、一度出た正方形と長方形の長さの比は同一のものとしてカウントします

# x^2 = (x - n)(x + n) + (x - m)(x + m) の等式が成り立つ m, n の組み合わせなので
#     = x^2 - n^2 + x^2 - m^2
#     = 2x^2 - (n^2 + m^2)
# となるので、x^2 = n^2 + m^2 となる n, m の組み合わせを探す
# なおかつ、一度出た m : n 比はカウントしない
import itertools

max_length = 500      # ひもの最長
result_patterns = {}  # 比率 -> 組み合わせ でハッシュ

for x in range(1, int(max_length / 4) + 1):  # 正方形の一辺
    combination = itertools.combinations(range(1, x), 2)
    valid_patterns = [n for n in combination if n[0] * n[0] + n[1] * n[1] == x * x]
    for pat in valid_patterns:
        result_patterns[pat[1] / pat[0]] = pat

print(len(result_patterns))

pazzle17.py

# 男女が 30 人並んでますが、女子だけ連続して並ぶことができません。
# 並び方のパターンは何個あるでしょう？

# 再帰でドカドカ足してみた。とりあえずこれで答えは出たっぽい。
max_num = 30
boy = True
girl = False


def count_pattern(children) -> int:
    # 最後まで並んだらパターンをコミット。
    if len(children) == max_num:
        return 1
    
    pattern = 0
    last_child = children[-1]  # 最後の一人を取り出して
    if last_child == girl:     # 女子なら男子を追加する
        next_children = children + [boy]
        pattern += count_pattern(next_children)
    else:                      # 男子なら男子か女子を追加する
        for a in [boy, girl]:
            next_children = children + [a]
            pattern += count_pattern(next_children)
    return pattern

print(count_pattern([boy]) + count_pattern([girl]))

pazzle17_a.py

# 別解。
# 1 人目 M, F = 2
# 2 人目 MM, MF, FM = 3
# 3 人目 MMM, MMF, MFM, FMM, FMF = 5
# 4 人目 MMMM, MMMF, MMFM, MFMM, MFMF, FMMM, FMMF, FMFM = 8

# M の出現パターン数 = 一つ前の数 (最後が何であれ追加できるから)
# F の出現パターン数 = 二つ前の数（間に M を挟まないとならないので１ターン遅れる）
# あかんコレフィボナッチ数や

max_num = 30
n_1 = 2
n_2 = 1

for n in range(2, max_num):
    cur = n_1 + n_2
    n_2 = n_1
    n_1 = cur

print(n_1 + n_2)

pazzle18.py

# 1-N 個（総計 1 + 2 + ... + N = N(N + 1)/2）のイチゴが乗ったケーキを、N 個に切り分けたい。
# ただし、隣り合った二つの切れは足したら平方数（√して整数になる）にならなければならない。
# このときこの条件を満たせる最小の N はなんぞや？

import math

n = 2  # カレントは 2 で開始


def is_match_count(n, log, square):
    pre_n = log[-1]

    if n == len(log):  # N つまり最大値までリストが増えた≒1-N の番号を使い終わった
        if (1 + pre_n) in square:  # 先頭（1）と足して平方数ですかい？
            print(n)
            print(log)
            return True
    else:  # まだ 1-N は全部使い切ってない
        un_use_nums = [i for i in range(1, n + 1) if i not in log]  # 1-N で未使用の Num 取得
        for i in un_use_nums:
            if (pre_n + i) in square:  # 前の値と今選んだ値足して（隣を足して）平方数？
                if is_match_count(n, log + [i], square):  # じゃー次の値を探そう
                    return True
        return False

# ヒントを元に平方数のリストを計算
while True:
    square = [i ** 2 for i in range(2, int(math.sqrt(n * 2)) + 1)]
    if is_match_count(n, [1], square):
        break
    n += 1

pazzle18_a.py

# 1-N 個（総計 1 + 2 + ... + N = N(N + 1)/2）のイチゴが乗ったケーキを、N 個に切り分けたい。
# ただし、隣り合った二つの切れは足したら平方数（√して整数になる）にならなければならない。
# このときこの条件を満たせる最小の N はなんぞや？

import math

n = 2  # カレントは 2 で開始


# ループ中から range しなくしてみた
# 速度的には、2.2 sec -> 0.6 sec
def is_match_nums(N, used, unused, square):
    last = used[-1]
    if N == len(used):
        if (last + 1) in square:
            print(n)
            print(used)
            return True
    else:
        for i in [i for i in unused if (i + last) in square]:
            tmp_unused = unused[:]
            tmp_unused.remove(i)
            if is_match_nums(N, used + [i], tmp_unused, square):
                return True
    return False

while True:
    # ヒントを元に平方数のリストを計算
    square = [i ** 2 for i in range(2, int(math.sqrt(n * 2)) + 1)]  # 存在しうる平方数
    nums = [i for i in range(2, n + 1)]  # 未使用番号
    if is_match_nums(n, [1], nums, square):
        break
    n += 1

pazzle18_c.py

# 1-N 個（総計 1 + 2 + ... + N = N(N + 1)/2）のイチゴが乗ったケーキを、N 個に切り分けたい。
# ただし、隣り合った二つの切れは足したら平方数（√して整数になる）にならなければならない。
# このときこの条件を満たせる最小の N はなんぞや？

# 事前計算パターン 0.6 -> 0.2 sec まで短縮
import math, time


def is_match_count(N, used, pattern):
    last = used[-1]
    if len(used) == N:  # 最後までループして
        if last in pattern[1]:  # 最終値が選択可能な数字なら
            return used  # そこまでのスタックを返す
        return []
    else:
        selectable = [i for i in pattern[last] if i not in used]  # 次の値候補を拾う
        for i in selectable:
            res = is_match_count(N, used + [i], pattern)
            if len(res) > 0:
                return res
        return []

n = 1
start = time.time()
result = []

# ヒントを元に平方数のリストを計算
while len(result) == 0:
    n += 1
    square = [i ** 2 for i in range(2, int(math.sqrt(n * 2)) + 1)]

    patterns = {}
    for i in range(1, n + 1):
        patterns[i] = [s - i for s in square if s > i and s - i <= n]

    result = is_match_count(n, [1], patterns)

print(n)
print(result)

end = time.time()

print(end - start)

pazzle19.py

# 共通の公約数がある二つの数を「知り合い」とみなしたとき、
# 1-n の数字の中で、7 つの値直列で 6 次の知り合いとなる最小の n を求めよ。

# 公約数がある ≒ 非素数で、例えば 3 次の知り合いなら
#   A*A → A*B → B*C → C*C で素数が 3 つあればいい。
# 最小を求めるから、2, 3, 5 を割り当てると最小の組み合わせは、
#   4(2x2) → 10(2x5) → 15(5x3) → 9(3x3)
# となり、最小の n は 15 となるわけだ。
# 今回は 6 次の知り合いであればよいので、
#   AA,AB,BC,CD,DE,EF,FF

import itertools

CONNECT = 6


def primes_take(num):
    """指定個数の素数リストを取得
    :param num:
    :return:
    """
    if num < 1:
        return []
    primes = [2]
    cur = 2
    while num > len(primes):  # 素数の数が num 個になるまで探す
        if cur % 2 == 0:  # 偶数の素数は 2 のみ≒それ以外は評価しない
            cur += 1
            continue
        is_prime = True
        half = int(cur / 2)
        for n in primes:  # 合成数は、素数で割れる
            if n > half:  # 最小の素数は 2 なので、それ以下でしか割れるか見ない
                break
            if cur % n == 0:  # 割り切れるなら素数ではない
                is_prime = False
                break
        if is_prime:  # 素数と判定されたらリスト追加
            primes.append(cur)
        cur += 1
    return primes


def to_pairs(l):
    pairs = []
    pre = l[0]
    for n in l[1:]:
        pairs.append((pre, n))
        pre = n
    return pairs


primes = primes_take(CONNECT)
min_value = primes[-1] ** 2
min_friend = []

for n in itertools.permutations(primes):  # 組み合わせを探すのが面倒なので自動作成
    friends = [l * r for l, r in to_pairs(n)]   # 2 個ペアにして掛け算
    friends = [n[0] ** 2] + friends + [n[-1] ** 2]  # 先頭末尾は２乗数
    max_size = max(friends)
    if min_value > max_size:  # より小さければ記録を上書き
        min_value = max_size
        min_friend = friends

print(min_value)
print(min_friend)

pazzle20.py

# 下の魔法陣は上下斜め、どの方向から足しても 33 で、「受難のファサード」って魔法陣らしい。
# とりま、それはどうでもよくて、任意の数の足し合わせを行って行った時、最も出現頻度の高い合計値はなんぞや？

magic_square = [ 1, 14, 14,  4,
                11,  7,  6,  9,
                 8, 10, 10,  5,
                13,  2,  3, 15]

# 安直に考えれば itertools で combination とってsum して出現数数える。
from itertools import combinations

results = {}
max_sum = 0
max_count = 0

for n in range(1, len(magic_square) + 1):
    for tpl in combinations(magic_square, n):
        sum_nums = sum(list(tpl))
        if sum_nums in results.keys():
            results[sum_nums] += 1
        else:
            results[sum_nums] = 1

        if max_count < results[sum_nums]:
            max_count = results[sum_nums]
            max_sum = sum_nums

print(max_sum)
print(max_count)

pazzle20_a.py

# 下の魔法陣は上下斜め、どの方向から足しても 33 で、「受難のファサード」って魔法陣らしい。
# とりま、それはどうでもよくて、任意の数の足し合わせを行って行った時、最も出現頻度の高い合計値はなんぞや？
magic_square = [ 1, 14, 14,  4,
                 11,  7,  6,  9,
                 8, 10, 10,  5,
                 13,  2,  3, 15]

# 回答見たら、合計値から減らす方向でカウントしてた…

total = sum(magic_square)
results = [0 for i in range(total + 1)]

# 今ひとつわからなかったので、3,2,4 のリストで計算して見たら
# 取り出すごとにこんな形に。
# 回数 ----->
#    0 3 2 4
# 9        1
# 8
# 7        1
# 6        1
# 5      1
# 4        1
# 3    1
# 2      1
# 1
# 0 1

# 取り出した数の位置に、インデックス 0 が一致して出現、
# それ以外は、すでに[出現している位置 + 取り出した位置] のインデックスにシフトして加算される。
# ごめん、こんな図にして言われないと気づかないわ（汗
# しかも上の値から順に計算していかないと、結果がずれるのか…

results[0] = 1
for n in magic_square:
    for i in range(total - n, -1, -1):
        results[i + n] += results[i]

max_num = max(results)
max_cnt = results.index(max_num)

print(max_cnt)
print(max_num)

pazzle21.py

# ビット列があるとき、前の行の２値ペアで排他論理和で次の行を計算していきます。
# 前後は固定 1 デス。
# 例えば、11 の次の行を考える時、 1(1 ^ 1)1 -> 101 となります。

# ではこのピラミッドで、0 の出現数が合計 2014 になるのは何行目？
# いやこれ左シフト＋シフト前値で排他論理和だよね。

loop_cnt = 1
zero_cnt = 1
start_num = 1
finish_zero_cnt = 2014

while zero_cnt < finish_zero_cnt:
    new_num = (start_num << 1) ^ start_num
    n_str = bin(new_num)[2:]
    zero_cnt += len([1 for i in n_str if i == '0'])
    start_num = new_num
    loop_cnt += 1
    print(n_str.center(150))

print(loop_cnt)

pazzle22.py

# N 人の子供が円形に並んで糸電話したとき糸が絡まないパターン数を計算せよ。
# 課題: 16 人

# 再起するための結果ペア
# 0 = もう一方のグループに固まった = 1 通り
n = 16
memo = {0: 1}


def count(pairs):  # 二人ひと組みのペア数を指定する
    if pairs in memo.keys():  # 過去キャッシュしてたらそれを返す
        return memo[pairs]
    else:
        cnt = 0
        for a in range(pairs):
            # ペアの組み合わせを考えるとき、ベースペア * それ以外のペアで考える
            # 例えば 6 人なら xx の組み合わせと xxxx の組み合わせの掛け算になる。
            cnt += count(a) * count(pairs - a - 1)
        # キャッシュしとけば高速
        memo[pairs] = cnt
        return cnt

print(count(int(n / 2)))

pazzle23.py

# コインが 10 枚あり、勝てば +1 負ければ -1 していきます。
# 24 回ゲームをやったとき、手元にコインが残る経過は何通りある？

# 今のゲームに買った場合と負けた場合でそれぞれカウント。
# コインが 0 でゲームオーバー depth=0 で勝ち抜きで + 1
# ルートによって同じ coins/depth が頻出することは想像できるのでメモ
# …模範解とそんな離れてなかった…
memo = {}


def this_game(coins, depth):
    if (coins, depth) in memo.keys():
        return memo[(coins, depth)]
    
    if coins == 0:
        return 0
    if depth == 0:
        return 1

    won = this_game(coins + 1, depth - 1)
    lose = this_game(coins - 1, depth - 1)
    memo[(coins, depth)] = won + lose

    return memo[(coins, depth)]

print(this_game(10, 24))

pazzle24.py

# 1-9 のストラックアウトがあります
# 1 2 3
# 4 5 6
# 7 8 9
# 真ん中（5）以外は最大まとめて２枚引っこ抜けます。
# 全部落とすパターンは何通り？

# 真ん中は必ず1回はかかるという制約条件…
# 1 回は２枚抜きするパターン
bord = [[1, 2], [2, 3], [3, 6], [6, 9], [8, 9], [7, 8], [4, 7], [1, 4]]

for i in range(1, 10):
    bord.append([i])


# メモ化でもすれば早くなりそう
def shot(bord):
    if len(bord) == 0:
        return 1
    cnt = 0
    for n in bord:
        cp_list = bord.copy()
        for s in n:
            cp_list = [i for i in cp_list if s not in i]
        cnt += shot(cp_list)
    return cnt

print(shot(bord))

pazzle25.py

# 左右６個の穴のあるシューズで、いろんな紐の結び方を検討する。
# 紐の交点は最大何通りですか？

from itertools import permutations

N = 6
max_cnt = 0

for left_holes in permutations(range(N)):
    for right_holes in permutations(range(N)):
        path = []
        left = 0
        right = right_holes[0]
        for i in range(N - 1):
            path.append([left, right])
            left = left_holes[i]
            path.append([left, right])
            right = right_holes[i + 1]
        path.append([left, 0])
        # …この辺までは思いついた…ですが、交差判定は答え見ました
        # 書いてたら思い浮かぶかなーと思ったけど思い浮かばなかったという…

        # 経路衝突判定
        cnt = 0
        for i in range(N * 2):
            for j in range(i + 1, N * 2 - 1):
                if ((path[i][0] - path[j][0]) * (path[i][1] - path[j][1])) < 0:
                    cnt += 1
        
        max_cnt = max([max_cnt, cnt])

print(max_cnt)

pazzle26.py

# W x H の盤があって、駒が敷き詰めてあり、空いているのが一番右下の１マスのみ
# この状態からこの隙間を使って一番左上の駒を一番右下へ導くとして、
# 最短何手で移動できるか？

# 空白を移動させると考える。
# 例えば 5 x 4 なら、x にたどり着くには最短 (5 - 1) + (4 - 1)
#
# x 1 1 1 1
# 1 1 1 1 1
# 1 1 1 1 1
# 1 1 1 1 o
#
# o x 1 1 1
# 1 1 1 1 1
# 1 1 1 1 1
# 1 1 1 1 1
#
# 右に対象がいて、下に移動させるなら、この空白を、下、右、上と３手動かす
# 1 o 1 1 1
# 1 x 1 1 1
# 1 1 1 1 1
# 1 1 1 1 1
# こうなったら右、下、左で動いて対象を右に動かす
# 1 1 1 1 1
# 1 o x 1 1
# 1 1 1 1 1
# 1 1 1 1 1
#
# 最初に o がひらり上に到達したのが右からと過程すると、x が移動すべき距離は
# 下 (4 - 1) 右 (5 - 2) となる
# (3 + 3) * 3 = 18 手移動と組み合わせると、18 + 7 = 25
#
# 汎用的に考えないなら、10x10 のマスは上、左どっちで先に動いても一緒なので、
# 9 + 9 (左上に移動) + (10 - 1 + 10 - 2) * 3 = 18 + 17 * 3 = 69
# ...あれーコード書かずにもとまっちゃったよ
# 基本的に abs(WIDTH - HEIGHT) > 2 だともう少し複雑になる

# W x H の盤があって、駒が敷き詰めてあり、空いているのが一番右下の１マスのみ
# この状態からこの隙間を使って一番左上の駒を一番右下へ導くとして、
# 最短何手で移動できるか？

# 空白を移動させると考える。
# 例えば 5 x 4 なら、x にたどり着くには最短 (5 - 1) + (4 - 1)
#
# x 1 1 1 1
# 1 1 1 1 1
# 1 1 1 1 1
# 1 1 1 1 o
#
# o x 1 1 1
# 1 1 1 1 1
# 1 1 1 1 1
# 1 1 1 1 1
#
# 右に対象がいて、下に移動させるなら、この空白を、下、右、上と３手動かす
# 1 o 1 1 1
# 1 x 1 1 1
# 1 1 1 1 1
# 1 1 1 1 1
# こうなったら右、下、左で動いて対象を右に動かす
# 1 1 1 1 1
# 1 o x 1 1
# 1 1 1 1 1
# 1 1 1 1 1
#
# 最初に o がひらり上に到達したのが右からと過程すると、x が移動すべき距離は
# 下 (4 - 1) 右 (5 - 2) となる
# (3 + 3) * 3 = 18 手移動と組み合わせると、18 + 7 = 25
#
# 汎用的に考えないなら、10x10 のマスは上、左どっちで先に動いても一緒なので、
# 9 + 9 (左上に移動) + (10 - 1 + 10 - 2) * 3 = 18 + 17 * 3 = 69
# ...あれーコード書かずにもとまっちゃったよ

import math

WIDTH = 10
HEIGHT = 10


class Pos:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Pos(self.x + other.x, self.y + other.y)

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __sub__(self, other):
        return Pos(self.x - other.x, self.y - other.y)

    def __str__(self):
        return "Pos({0}, {1})".format(self.x, self.y)

    def is_wrong(self):
        return self.x < 0 or self.y < 0 or self.x > WIDTH - 1 or self.y > HEIGHT - 1

    def distant(self, other):
        dis = self - other
        return math.sqrt(dis.x ** 2 + dis.y ** 2)

    def is_long_distant(self, other):
        dis = self.distant(other)
        return dis > math.sqrt(2)

target = Pos(WIDTH - 1, HEIGHT - 1)
blank = Pos(0, 0)

# blank を target の (-1, 0) か (0, -1) に移動して石と位置を交換する
# ただし、移動について target の座標へ移動してはならない
UP = Pos(0, 1)
DOWN = Pos(0, -1)
LEFT = Pos(1, 0)
RIGHT = Pos(-1, 0)


def move(from_pos, to_pos, log_list, mv_cnt):
    # 目標地点についたら、移動距離を返す
    if from_pos == to_pos:
        return mv_cnt

    # 前回の位置を計算
    prev_distant = from_pos.distant(to_pos)
    total_mv = WIDTH * HEIGHT

    # とりま移動してみる
    for mv in [DOWN, RIGHT, UP, LEFT]:
        next_pos = from_pos + mv

        # 移動できない場所なら読み飛ばす
        if next_pos.is_wrong():
            continue

        # 過去に通った場所も読み飛ばす
        if next_pos in log_list:
            continue

        # 距離が離れて、しかもターゲット座標の周辺以外ならカウントしない
        next_distant = next_pos.distant(to_pos)
        if next_distant > prev_distant and next_pos.is_long_distant(target):
            continue

        # 距離が短くなるなら記録する
        moves = move(next_pos, to_pos, log_list + [next_pos], mv_cnt + 1)
        if moves < total_mv:
            total_mv = moves

    return total_mv

total_cnt = 0

while True:
    # 初手が横か下かは意識してない。多分これで手数が変わるときはもう少し考えなければならない。
    right_pos = target + RIGHT
    down_pos = target + DOWN
    right_cnt = WIDTH * HEIGHT
    down_cnt = WIDTH * HEIGHT

    if not right_pos.is_wrong():
        right_cnt = move(blank, right_pos, [blank], 0)
    if not down_pos.is_wrong():
        down_cnt = move(blank, down_pos, [blank], 0)

    if right_cnt < down_cnt:
        total_cnt += right_cnt + 1
        blank = target
        target = right_pos
    else:
        total_cnt += down_cnt + 1
        blank = target
        target = down_pos

    if target == Pos(0, 0):
        break

print(total_cnt)

pazzle27.py

# 正方形のブロックが並んだ長方形の街で、直進/左折しかできないとき、
# 6x4 ブロックで、一番左下から、区画の一番右上まで移動するパターンはいくつかるか？
# ただし、一度通った道は再度通らない。
width = 6
height = 4

# 0-3 で方向制御
vectors = [[1, 0], [0, 1], [-1, 0], [0, -1]]

# 水平方向の通った道
horizontal_road = [0 for h in range(height + 1)]

# 垂直方向の通った道
vertical_road = [0 for w in range(width + 1)]


# 移動できるか判定
def move(pos, v, h_log, v_log) -> int:

    vector = vectors[v]
    next_pos = [pos[0] + vector[0], pos[1] + vector[1]]

    # 枠の外には出れない
    if next_pos[0] < 0 or next_pos[0] > width:
        return 0
    if next_pos[1] < 0 or next_pos[1] > height:
        return 0

    # 過去通った道を通ろうとするのもダメ
    cp_h_log = h_log[:]
    cp_v_log = v_log[:]
    if v in [0, 2]:  # 水平方向移動
        min_x = min([pos[0], next_pos[0]])
        if cp_h_log[pos[1]] & (1 << min_x):
            return 0
        cp_h_log[pos[1]] |= (1 << min_x)
    else:  # 然もなくば上下移動
        min_y = min([pos[1], next_pos[1]])
        if cp_v_log[pos[0]] & (1 << min_y):
            return 0
        cp_v_log[pos[0]] |= (1 << min_y)

    # ゴールならその時点で終了
    if next_pos[0] == width and next_pos[1] == height:
        return 1

    # さもなくば継続
    cnt = 0
    cnt += move(next_pos, v, cp_h_log, cp_v_log)
    cnt += move(next_pos, (v + 1) % 4, cp_h_log, cp_v_log)
    return cnt

print(move([0, 0], 0, horizontal_road, vertical_road))

pazzle28.py

from itertools import combinations

# 各種クラブ活動があり、面積と人数がわかっている
# 150 人 max で組み合わせた時に、面積が最大となる組み合わせを求めなさい


class Club:
    def __init__(self, name, area, num):
        self.name = name
        self.area = area
        self.num = num

    def __str__(self):
        return "Club(Name:{0},Area:{1},Num:{2})".format(self.name, self.area, self.num)


clubs = [
    Club('野球', 11000, 40),
    Club('サッカー', 8000, 30),
    Club('バレーボール', 400, 24),
    Club('バスケットボール', 800, 20),
    Club('テニス', 900, 14),
    Club('陸上', 1800, 16),
    Club('ハンドボール', 1000, 15),
    Club('ラグビー', 7000, 40),
    Club('卓球', 100, 10),
    Club('バドミントン', 300, 12)
]

MAX = 150
MAX_COMBINATION = 8
MIN_COMBINATION = 5

max_area = 0
combination = []

current = MIN_COMBINATION

while current <= MAX_COMBINATION:
    for comb in combinations(clubs, current):
        sum_num = sum(map(lambda a: a.num, comb))
        sum_area = sum(map(lambda a: a.area, comb))
        if sum_num < MAX:
            if sum_area > max_area:
                max_area = sum_area
                combination = comb
    current += 1

msg = ','.join(map(lambda a: str(a), combination))

print('max : ' + str(max_area))
print('res : ' + msg)