[PYTHON] Projekt Euler 32

Problem

Angenommen, eine Zahl mit 1 bis n, die nur einmal in jeder Ziffer verwendet wird, ist eine Pandigitalzahl mit n Ziffern: Beispielsweise ist die 5-stellige Zahl 15234 ein Pandigital mit 1 bis 5.

7254 hat eine interessante Eigenschaft: Schreiben Sie 39 x 186 = 7254, und es wird ein Pan Digital mit einer zu multiplizierenden Zahl, einer zu multiplizierenden Zahl und einem Produkt von 1 bis 9.

Finden Sie die Summe der Produkte so, dass die zu multiplizierende Zahl / die zu multiplizierende Zahl / das Produkt von 1 bis 9 pan-digital ist.

TIPP: Einige Produkte haben eine oder mehrere Multiplikations- / Multiplikations- / Produktkombinationen, zählen jedoch nur einmal. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2032

Antworten

Es gibt 9! Pan digitale Zahlen wegen ihrer Bedeutung. Das heißt, Dezimalzahlen von 0 bis weniger als 9! Entsprechen jeder der pan-digitalen Zahlen. Die Antwort erhalten Sie, indem Sie die Dezimalzahl kleiner als 9 in eine digitale Schwenkzahl umwandeln, die digitale Schwenkzahl teilen und feststellen, ob die Bedingung erfüllt ist oder nicht. Unter Beachtung von TIPP wird auch der Wert des Produkts gespeichert und die gleiche Berechnung wird ausgeschlossen. (Es ist wahrscheinlich effizienter, zuerst eine Funktion zu erstellen, die einfach nur das Produkt extrahiert. Da aus einer einfachen Überlegung ersichtlich ist, dass das zu berechnende Produkt nicht aus 3 oder 5 Ziffern bestehen kann, wird der folgende Code auf 4 Ziffern gesetzt.

import math
def create_pandigital(target,n,seeds):

  ret = ''
  while n > 0:
    kaijo = math.factorial(int(n))
    (q, r) = (target//kaijo, target%kaijo)
    ret += str(seeds.pop(q))
    target = r
    n -= 1
  return ret + str(seeds[0])

def main():
  N = 10
  MAX = math.factorial(int(N-1))
  ans = 0
  seeds = []
  seq = range(1,N)
  ls = []
  for target in range(3,MAX):
    seeds[:] = seq
    n = N - 2
    pan =  create_pandigital(target, n, seeds)

    for i in range(1,4):
      if not (pan[:4] in ls) and int(pan[:4]) == (int(pan[4:4+i+1]) * int(pan[4+i+1:])):
        ls.append(pan[:4])
        ans += int(pan[:4])
        break
  print ans

main()