I have been having the same problem. The Code Jam team said it is okay to post
code now, so here's mine. Not sure where I could be getting a runtime error.
I don't think there should be any division by 0, because the only places I
divide are when I am dividing a product of 2 primes by one if its prime
factors. This is Python 3:
import numpy as np
def gcd(a, b):
return np.gcd(a,b)
def FindFirstPrime(vals):
"""Finds one prime factor of the first integer in vals."""
v0 = vals[0]
for x in vals[1:]:
if x != v0:
v1 = x
break
p = int(gcd(v0, v1))
return p
def Decode(vals, primes_used):
"""Decodes vals given the set of prime numbers used for encoding""
primes_sorted = sorted(set(primes_used))
alphabet = [c for c in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ']
table = dict()
for p, c in zip(primes_sorted, alphabet):
table[p] = c
plaintext = ''.join([table[p] for p in primes_used])
return plaintext
def Decrypt(vals):
# p0 and p1 are the prie factors of vals[0]
p0 = FindFirstPrime(vals)
p1 = vals[0] / p0
# Determine which of p0, p1 is also a prime factor of v[1]
# primes_used will be populated with the primes numbers used to encode
# the original plaintext, in the correct order
if vals[1] % p0 == 0:
prev = p0
primes_used = [p1, p0]
else:
prev = p1
primes_used = [p0, p1]
# Iterate through vals[1:] to obtain all the primes used
for v in vals[1:]:
p = v / prev
primes_used.append(p)
prev = p
return Decode(vals, primes_used)
T = int(input())
for t in range(1, T+1):
N, L = [int(s) for s in input().split(' ')]
vals = [int(s) for s in input().split(' ')]
plaintext = Decrypt(vals)
print('Case #{}: {}'.format(t, plaintext))
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/8e17f71c-a040-4739-b92b-ea2726d354b6%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
