Skip to content

Instantly share code, notes, and snippets.

@huffman
Created August 8, 2012 08:58
Show Gist options
  • Save huffman/3293613 to your computer and use it in GitHub Desktop.
Save huffman/3293613 to your computer and use it in GitHub Desktop.
from math import factorial
digits = "0123456789"
target = 1000000
def lex(perm, values):
vlen = len(values)
for i in xrange(vlen):
num_perms = factorial(vlen - i)
if perm >= num_perms:
iterations = int(perm / num_perms)
perm = perm % num_perms
swap = i - 1
values = move(values, swap + iterations, swap)
return values
def move(values, a, b):
return values[:b] + values[a] + values[b:a] + values[a+1:]
print 'perm: %d, %s' % (target, lex(target-1, digits))
# perm: 1000000, 2783915460
# python 24.py 0.03s user 0.01s system 95% cpu 0.038 total
from math import log
def fib(n, mem={}):
if n == 1 or n == 2:
return 1
if n in mem:
return mem[n]
v = fib(n-1) + fib(n-2)
mem[n] = v
return v
n = 1
while (log(fib(n), 10) < 999):
n += 1
print n, fib(n)
#4782 1070066266382758936764980584457396885083683896632151665013235203375314520604694040621889147582489792657804694888177591957484336466672569959512996030461262748092482186144069433051234774442750273781753087579391666192149259186759553966422837148943113074699503439547001985432609723067290192870526447243726117715821825548491120525013201478612965931381792235559657452039506137551467837543229119602129934048260706175397706847068202895486902666185435124521900369480641357447470911707619766945691070098024393439617474103736912503231365532164773697023167755051595173518460579954919410967778373229665796581646513903488154256310184224190259846088000110186255550245493937113651657039447629584714548523425950428582425306083544435428212611008992863795048006894330309773217834864543113205765659868456288616808718693835297350643986297640660000723562917905207051164077614812491885830945940566688339109350944456576357666151619317753792891661581327159616877487983821820492520348473874384736771934512787029218636250627816
#python 25.py 0.04s user 0.01s system 93% cpu 0.050 total
import sys
with open(sys.argv[1]) as f:
for idx, line in enumerate(f):
if idx == 0:
continue
line = line.strip()
values = {}
for ch in line:
if ch not in values:
lval = len(values)
if lval == 0:
values[ch] = 1
elif lval == 1:
values[ch] = 0
else:
values[ch] = lval
lval = len(values)
base = lval if lval >= 2 else 2
total = 0
for i, ch in enumerate(line):
total += values[ch] * (base ** (len(line) - 1 - i))
print "Case #%d: %d" % (idx, total)
#python a.py ~/Downloads/A-large-practice.in 0.03s user 0.01s system 95% cpu 0.038 total
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment