Puzzle Python

[Python] 数学パズルのQ29が僕には難解だった

プログラマ脳を鍛える 数学パズルをちょこちょこ読んでいます。
自分の中でルールを決めていて、全てPythonで解こうとしています。
(解答例は全てrubyで書かれています) 全部解いたら再度解きながらブログに書こうと思っていたのですが、Q29の回答を理解するのが難しかったので、紹介します。

コード

私が作成した回答のコードです(Python3版)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import itertools
import functools
import operator
import sys
import collections
 
#
# from : https://www.lifewithpython.com/2014/01/python-flatten-nested-lists.html
#
def flatten_with_any_depth(nested_list):
    """深さ優先探索の要領で入れ子のリストをフラットにする関数"""
    # フラットなリストとフリンジを用意
    flat_list = []
    fringe = [nested_list]
 
    while len(fringe) > 0:
        node = fringe.pop(0)
        # ノードがリストであれば子要素をフリンジに追加
        # リストでなければそのままフラットリストに追加
        if isinstance(node, list):
            fringe = node + fringe
        elif isinstance(node, tuple):
            val = list(node)
            fringe = val + fringe
        else:
            flat_list.append(node)
 
    return flat_list
 
# 配列の直積を計算
def product(ary):
    result = ary[0]
    for i in range(1, len(ary)):
        result = list(itertools.product(result, ary[i]))
 
    val = map(lambda r: flatten_with_any_depth(r), result)
    return list(val)
 
# 並列の場合の抵抗値を算出
#
# R = 1 / (1/w + 1/w2 ...)
#
def parallel(ary):
    # aryには配列で入ってくる [[1,2]] ので0番目を取り出して計算する
    tmp_ary = map(lambda i: 1.0 / i, ary[0])
    tmp_val = functools.reduce(operator.add, tmp_ary, 0)
    return 1.0 / tmp_val
 
memo = {1 : [1]}
 
def calc(n):
    if n in memo:
        return memo[n]
 
    # 直列 (自分自身 (1) と残りのパターンを直列接続したパターン)
    result = list(map(lambda i: i + 1, calc(n - 1)))
 
    # 並列
    for i in range(2, n):
        # 並列で区切る個数を設定
        cut = {}
        # 区切る位置のパターンを出して、その位置で区切った時にいくつづつになるかパターンを出す
        for ary in list(itertools.combinations(range(1, n - 1), i - 1)):
            pos = 0
            r = []
            for j in range(len(ary)):
                r.append(ary[j] - pos)
                pos = ary[j]
            r.append(n - pos)
            r.sort()
            # dictionaryに入れることで重複を排除する
            cut[tuple(r)] = 1
 
        #区切った位置で再帰的に抵抗を設定
        keys = list(map(lambda c: list(map(lambda e: calc(e), c)), cut.keys()))
 
        # 抵抗値を計算
        # 抵抗値のパターンはkeysの直積になる
        for k in list(map(lambda k: product(k), keys)):
            for vv in k:
                result.append(parallel([vv]))
 
    # メモキャッシュ
    memo[n] = result
 
    return result
 
golden_ratio = 1.6180033987
min_val = sys.float_info.max
 
for i in calc(5):
    if abs(golden_ratio - i) < abs(golden_ratio - min_val):
        min_val = i
 
print("val :" + str(min_val))

難しかった点

  1. 並列で区切る時の区切りパターンの算出
  2. 直積を算出する方法がPythonにない (あってもそのまま使えなかった)
  3. 配列で抵抗値を持っているが、何を持っているのかよく分からなかった

並列で区切る時の区切りパターンの算出

5個(n)の物を区切る事を考えた時、区切る位置は4箇所あります。(n - 1箇所)
区切るパターンは4箇所から1つ, 2つ, 3つ, 4つと選択して行ったパターンだけあります。
そのあたりのコメントがなかったので、写経しただけでも何をしているのかわかりませんでした。

4箇所から2箇所を選ぶパターン

?
>>> list(itertools.combinations([1,2,3,4], 2))
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

直積を算出する方法がPythonにない

実際にはあるのですが、タプルになります。
また、入れ子の配列になっているときに、入れ子構造をフラットにするメソッドもありませんでした。
この辺りはググりまくって解決しました。

配列で抵抗を持っているが何を持っているのかよく分からなかった

配列で抵抗値を持っているのですが、実際には4個なら4個の抵抗を繋いで作成できる抵抗値のパターンでした。
メモ化しているのも、その値なので、並列にしたりした時にそれを再利用して高速化しています。

まとめ

頭の体操になって面白くて最近ちょこちょこやっています。
てか、初級でつまづきまくっているのですが、この先大丈夫でしょうか...
とにかくプログラムを書きたい時にオススメです。

0 件のコメント :

コメントを投稿