[PYTHON] Project Euler 38

problem

Let's multiply 192 by 1, 2, 3.

   192 × 1 = 192
   192 × 2 = 384
   192 × 3 = 576

Concatenating the products yields the Pandigital number 192384576 from 1 to 9. 192384576 is called the concatenated product of 192 and (1,2,3).

In the same way, multiplying 9 by 1,2,3,4,5 and concatenating gives the Pandigital number 918273645. This is the concatenated product of 9 and (1,2,3,4,5). is there.

What is the largest 9-digit Pandigital number obtained as the concatenated product of an integer and (1,2, ..., n) (n> 1)? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2038

Answer

First, I made a generator that generates a specified number of Pandigital numbers (character strings) from a specified set of numbers.

import copy
def pandigital(digit,seq1,seq2=[]):
  iter1 = map(str,seq1)
  if seq2:
    iter2 = map(str,seq2)
  else:
    iter2 = copy.deepcopy(iter1)
  for d in range(digit-1):
    iter1 = (x+y for x in iter1 for y in iter2 if not (y in x))
  return iter1

To generate a generator with a 10-digit Pandigital number that does not include 0 at the beginning, specify as follows. If seq2 is omitted, seq1 is copied to seq2.

 pandigital(digit=10,seq1=range(1,10),seq2=range(0,10))

I think that this generator returns values in ascending order if you pass range (1,10), and returns values in descending order if you pass range (10,1, -1).

In answering this question, we first create a set of 9-digit Pandigital numbers, PAND_SET, using the above function. Later, in order to refer to whether other numbers are included in this set of Pandigital numbers, set () is used here to make it a set type object in consideration of reference speed.

Then loop i from 2 to 10,000 and do the following calculation until s is (a string of) 9 digits. s = str (i) + str (i * 2) + str (i * 3) ・・・

Confirm that the s calculated in this way is larger than the answer candidate ans and that s is included in PAND_SET. If both are true, replace ans with s.

import pandigital
def main():
  SEARCH_MAX = 10**4
  PAND_SET = set(pandigital.pandigital(9,range(1,10)))
  ans = 0

  for i in range(2,SEARCH_MAX):
    s = str(i)
    j = 2
    while len(s)<9:
      s += str(i*j)
      j+=1
    if len(s)>=10:
      continue
    if int(s) > ans and s in PAND_SET:
      ans = int(s)
  print ans
main()