知恵袋で見つけた一番上のボックスに入る数字の問題をPythonで解いてみた。

　知恵袋で見つけたピラミッドの一番上のボックスに入る数字を求める問題をPythonで解いてみました。元ネタは、インテルの入社試験問題のようです。

i                                    
..              +---+                
1               | ? |                
              +-+-+-+-+              
2             |   |138|              
            +-+-+-+-+-+-+            
3           |80 |   |   |            
          +-+-+-+-+-+-+-+-+          
4         |   |   |   |43 |          
        +-+-+-+-+-+-+-+-+-+-+        
5       |29 |   |15 |   |   |        
      +-+-+-+-+-+-+-+-+-+-+-+-+      
6     |   |   |   |   |   |18 |      
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+    
7   |   |   |   |   | 3 |   |   |    
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  
8 | x | y | z | 3 | a | b | c | d |  
  +---+---+---+---+---+---+---+---+  
    1   2   3   4   5   6   7   8 :j

　プログラムでは、一番上の段を1段目、一番左端を左から1番目として、上の図のように最下段の8段目の数のリストを[x,y,z,3,a,b,c,d]としました。
　それぞれの文字は、上方向左右45°圏内にある数より小さくなります。たとえば、a,b<=3 や b,c,d<=18となりますが、とりあえず、0≦x,y,z,a,b,c,d＜10でループを回してみました。(^_^;
　関数pyramid(i,j,lst)で、8段目がlstで与えられるときの上からi段目の左からj番目の数を求めて枝狩りして、チェックを潜り抜けたものだけを表示するようにしました。
　[x,y,z]より[a,b,c,d]の方が早く枝が刈れそうなので[a,b,c,d]の方をループの前の方に分けてみました。
　自力で解くには、次の図のような既知数A,B,Cが作る三角形パターン(A,B,C)において、未知数x,y,zが決まってしまうというのを使っています。まず、三角形パターン(80,29,15)から、三角形内部の数を決定します。次に、三角形パターン(138,33,43)の内部を決定すると、上から3段目がすべて決定するので、後は一番上のボックスに入る数字まで足し算で求めます。

    +-+-+     
    | A |       A=y+z
  +-+-+-+-+       y=B+x
  | y | z |         z=x+C
+-+-+-+-+-+-+ ∴A=B+2x+C
| B | x | C | ∴x={A-(B+C)}/2
+---+---+---+

　ちなみに、この問題は条件が多過ぎる問題になっていて、たとえば、29と15の条件を下のプログラムからコメントアウトしても解けてしまいます。(^_^;

● iPyramid.py

# coding: UTF-8
# iPyramid.py

import itertools
from time import time

N = 8
def pyramid(i,j,lst):
    if i==N: return(lst[j-1])
    return pyramid(i+1,j,lst)+pyramid(i+1,j+1,lst)

def PrintResult(lst):
    for i in range(1,N+1):
        s = ' '*((N-i)*2)
        for j in range(1,i+1):
            s+='%3d '%pyramid(i,j,lst)
        print(s[:-1])

def main():
    tm=time()  # Timer Start

    for a,b,c,d in itertools.product(range(10),repeat=4):
        li = [0,0,0,3,a,b,c,d]
        if pyramid(7,5,li)!= 3: continue
        if pyramid(6,6,li)!=18: continue
        if pyramid(4,4,li)!=43: continue
        for x,y,z in itertools.product(range(10),repeat=3):
            li = [x,y,z,3,a,b,c,d]
            if pyramid(5,3,li)!= 15: continue
            if pyramid(5,1,li)!= 29: continue
            if pyramid(3,1,li)!= 80: continue
            if pyramid(2,2,li)!=138: continue
            # チェックを潜り抜けたものだけを表示
            PrintResult(li)

    print("Runtime : %.3f [sec]"%(time()-tm))   # Timer Stop & Disp

if __name__ == '__main__':
    main()

●実行結果

               282
             144 138
            80  64  74
          47  33  31  43
        29  18  15  16  27
      19  10   8   7   9  18
    13   6   4   4   3   6  12
   8   5   1   3   1   2   4   8
Runtime : 0.032 [sec]

※参考URL
●ネタバレ⇒【超難問】1分以内に解けたら合格インテルの入社試験問題 | ツイネタ〜スパムネタバレ＼(^o^)／