【Project Euler】Problem 93: 四則演算で連続数

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 93.四則演算で連続数

原文 Problem 93: Arithmetic expressions

問題の要約: 4つの数字を使って四則演算を行った結果を1から順番に並べたとき、最も連続が長く続くような4つの数字を求めよ

いわゆるテンパズル(Wikipedia)で10だけでなく、1から順番に数を一番連続で作れる4つの数字はどれかという問題です。

この手の問題はカッコとかがあると扱いがややこしいので逆ポーランド記法(Wikipedia)を使うと簡略化できます。以下のように考えます。

1. 数字は4個、演算子は3個ある
2. スタックに数字をプッシュしていく
3. スタックに数字が2つ以上あったら演算子を適用して、上の2つをポップして演算してスタックに返す
4. 2.か3．を繰り返して、残りの数字と演算子がなくなったらスタックに残った数字が答。
5. この答えが自然数だったら重複を除くためにsetに入れていく。

これを再帰関数でで実装したのがrevPolです。引数に(スタック, 残りの数字のリスト, 残りの演算子の数)を渡します。

from operator import add, sub, truediv, mul
from copy import copy
opefunc = dict({'*':mul,'/':truediv, '+':add, '-':sub})

def isNnum(n): # return True if n is natural number
  return int(n) == n and n > 0

 # Reverse Polish: stack, remaining numbers, remaining operator count
def revPol(stk, nlist, on):  
  if len(stk) == 1 and len(nlist) == 0 and on == 0:  # calcuration complete 
    if isNnum(stk[0]):          # if natural number
      ansSet.add(int(stk[0]))   # add to answer set 
    return
  ## ----- use an operator ------
  if len(stk) >= 2 and on > 0:
    stk1 = copy(stk)
    a2, a1 = stk1.pop(), stk1.pop()
    for o1 in list(opefunc.keys()):       # for all operators
      if o1 == '/' and a2 == 0: continue  # avoid zero devide
      revPol(copy(stk1)+[opefunc[o1](a1, a2)], nlist, on-1)
  ## ----- use an number -----
  if len(nlist) > 0:
    revPol(copy(stk)+[nlist[0]], copy(nlist)[1:], on) # push number to stack and remove from nlist
  return

ansSet = set()
revPol([], [1,2,3,4], 3)  # stack, numbers, #of operand
print(ansSet)
# {1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 20, 21, 24, 25, 28, 36}

これは[1,2,3,4]をその順番で使った場合なので、これを順列すべてについての結果の和集合を取り、１からの連続する個数をチェックするのが次のcontNumsです。ここで[1,2,3,4]からは28まで連続することが確認できました。

def contNums(nn):
  ansSet.clear()     # clear answer set
  for nlist in permutations(nn,4):  # for all permutations
    revPol([], list(nlist), 3)      # collect result numbers to ansSet
  for i in count(1): # check 1-n continues numbers in the set 
    if i not in ansSet: break
  return (i-1)
print(contNums([1,2,3,4]))
# 28

後は4つの数字の組み合わせを1から9の中から選んで一番長く連続する組み合わせを探せば良いことになります。

digit = range(1,10)
cmax, cmaxNL, ansSet = 0, [], set()
for nn in combinations(digit,4):
  cont  = contNums(nn)
  if cont > cmax: 
    cmax, cmaxNL = cont,  "".join(map(str,nn))

print(f"Answer = {cmaxNL} (continued up to {cmax}).")

（開発環境：Google Colab）