bancaldo™

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1. 
Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.
Find the value of n, 1 < n < 107, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

Analisi:

Le fonti utili per la soluzione del problema:
wikipedia (Totient Function)

Dal link sono ricavabili le due formule fondamentali relative ai numeri primi:

n = p1 * p2
phi(n) = (p1 – 1) * (p2 – 1)

In sostanza:
Dobbiamo trovare il numero ‘n’ per il quale la funzione phi(n) riusulta essere una permutazione di ‘n’ stesso ed il rapporto tra n e phi(n) deve essere il più piccolo possibile.
Perchè un rapporto sia minimale, i denominatore deve essere il più grande possibile.
Verrebbe da pensare che prendendo il numero primo prossimo a 10^7 si abbia il risultato cercato.
Questo è errato in quando da un’altra analisi della funzione phi, è risaputo che se n è primo, quindi finisce per 1,3,7,9 allora:

phi(n) = n-1

ciò comporterebbe una variazione dell’ultima cifra del numero, quindi non si avrebbe come risultato una permutazione.
Se cercassimo invece due numeri primi che all’incirca fossero dell’ordine di grandezza della radice quadrata di 10^7, restringeremmo enormemente il campo di ricerca ed avremmo buone possibilità di ottenere il risultato.

√10^7 = ~3162

Useremo un campo di ricerca da 1000 a 5000 per stare tranquilli.

Python:

import time

st = time.time()

def is_prime(num):
    if num <= 1: return False
    elif num == 2: return True
    elif num % 2 == 0: return False
    else:
        d = 3
        r = int(num**0.5)
        while d <= r:
            if num % d == 0: return False
            d += 2
        return True


primes = [p for p in xrange(999, 5001, 2) if is_prime(p)]

minrate = 2
nmin = 1
tmax = 1

for p1 in primes:
    for p2 in primes:
        n = p1 * p2
        totien = (p1 - 1)*(p2 - 1)
        rate = float(n) / totien
        if n > 10**7: break
        if sorted(str(totien)) == sorted(str(p1*p2)) and rate < minrate:
            minrate = rate
            nmin = n
            tmax = totien
            
print nmin
print 'elapsed time: %ssec' %(time.time() - st)

Consider quadratic Diophantine equations of the form:

x^2 – Dy^2 = 1

For example, when D=13, the minimal solution in x is 649^2 – 13×180^2 = 1.

It can be assumed that there are no solutions in positive integers when D is square.

By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:

3^2 – 2×2^2 = 1
2^2 – 3×1^2 = 1
9^2 – 5×4^2 = 1
5^2 – 6×2^2 = 1
8^2 – 7×3^2 = 1

Hence, by considering minimal solutions in x for D ≤ 7, the largest x is obtained when D=5.

Find the value of D ≤ 1000 in minimal solutions of x for which the largest value of x is obtained.

Analisi:

In pratica la soluzione del problema, sta nell’unione dei problemi 64 e 65.
Questo perchè da wikipedia risulta che: la soluzione all’equazione di Pell

x^2 - D*y^2 = 1

sta nella ricerca delle convergenti della frazione continua della radice
quadrata di D. Grazie alle dovute semplificazioni, risulta che i valori di x
sono niente altro che i numeratori delle convergenti, mentre i valori di y,
i denominatori.

Quindi: prima si ottiene la notazione della frazione continua della radice quadrata di D, poi
si calcolano le convergenti di tale frazione continua.
Dopodichè trovare la soluzione ovvero la prima coppia di x,y per la quale si ha
x^2 – D*y^2 = 1
è un gioco abbastanza semplice.

Unica modifica sta nel fatto che non è detto che x,y si riescano a calcolare dal
periodo ciclico segnato in notazione.
Es: per D = 13, notazione [3; 1, 1, 1, 1, 6], calcolando i convergenti per
[3; 1, 1, 1, 1, 6], non si risolve l’equazione di Pell.
Si deve quindi ripetere il periodo, diventando:
[3; 1, 1, 1, 1, 6, 1, 1, 1, 1, 6]
e così via, fino alla risoluzione dell’equazione di Pell.
Sempre per D=13 si otterranno così x=649 e y=180.

python:

import time

st = time.time()

def cont_fract(n):
    '''get the continued fraction'''
    notation = []
    a0 = int(n ** 0.5)
    notation.append(a0)
    if a0 * a0 == n:
        return notation
    a, m, d = a0, 0, 1
    while a != 2 * a0 or d != 1:
        m = d * a - m
        d = (n - m * m) / d
        a = int((a0 + m) / d)
        notation.append(a)
    return notation

def get_x_pell(notation, d):
    '''get numerator of the convergents for
       wich Pell's equation is solved'''
    hs = [0,1]
    ks = [1,0]
    i = 0
    period = notation[1:]
    for n in notation:
        h = n*hs[i+1] + hs[i]
        k = n*ks[i+1] + ks[i]
        hs.append(h)
        ks.append(k)
        i += 1
        if h**2 - d*k**2 == 1:
            return h
        else: # it multiplies the period in notation
            notation.extend(period)

xs = {}
for d in xrange(2, 1001):
    if int(d**0.5) * int(d**0.5) == d: continue
    cf = cont_fract(d) # continued fraction
    x = get_x_pell(cf, d) # get convergent numerator
    xs[d] = x

max_x = max(xs.values())
res = [d for d in xs.keys() if xs[d] == max_x][0]

print 'euler 66: {}\nelapsed time: {}sec'.format(res, time.time() - st)

...
the sequence of the first ten convergents for √2 are:
1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...

What is most surprising is that the important mathematical constant,
e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].

The first ten terms in the sequence of convergents for e are:
2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...

The sum of digits in the numerator of the 10th convergent is 1+4+5+7=17.

Find the sum of digits in the numerator of the 100th convergent of the
continued fraction for e.

Analisi:

Problema!

Come per il problema 64, mi sono affidato a Wikipedia.
Per le frazioni continue si possono trovare i numeratori (h) ed
i denominatori (k) secondo queste formule ricorsive:

hn = an * hn-1 + hn-2
kn = an * kn-1 + kn-2

dove i valori iniziali sono:

h-1 = 0
h0 = 1
k-1 = 1
k0 = 0

Considerata la costante ‘e’ con la seguente notazione:

[2; 1, 2, 1, 1, 4, 1, 1, 6, ...]

dovrei ottenere le seguenti convergenze:

[2; 3, 8/3, 11/4,...]

utilizzando la notazione generica fornita da wp, avrei:

[a0; a1, a2, a31, a4, ...]

ma utilizzando le formule ricorsive, non ottengo i numeratori
che sto cercando:

hn = an * hn-1 + hn-2

h1 = a1 * h0 + h-1 = 1 * 1 + 0 = 1  >> dovrei avere 3
h2 = a2 * h1 + h0 = 2 * 1 + 0 = 1  >> dovrei avere 8

il problema è l’errata notazione letterale, che andrebbe aumentata di una
unità (link) e che deve quindi essere:

[a1; a2, a3, a4, a5, ...]

infatti:

[a1; a2, a3, a4, ...]
[2; 1, 2, 1, ...]
[2; 3, 8/3, 11/4,...]

ottengo:

h1 = a1 * h0 + h-1 = 2 * 1 + 0 = 2 (2/1)
h2 = a2 * h1 + h0 = 1 * 2 + 1 = 3 (3/1)
h3 = a3 * h2 + h1 = 2 * 3 + 2 = 8 (8/3)
h4 = a4 * h3 + h2 = 1 * 8 + 3 = 11 (11/4)

Ora il codice viene da sè…

python:

import time

st = time.time()

def get_e_notation():
    start = [2, 1]
    new = [1]*200
    mult = 2
    for i in range(len(new)):
        if i == 0 or i % 3 == 0:
            new[i] = mult
            mult += 2
    start.extend(new)
    return start

e_not = get_e_notation()

hs = [0,1]
i = 0
for n in e_not:
    h = n*hs[i+1] + hs[i]
    hs.append(h)
    i += 1
    if i == 100: break

res = sum([int(n) for n in str(hs[-1])])
print 'euler 65: {}\nelapsed time: {}sec'.format(res, time.time() - st)

Project Euler problem #64

All square roots are periodic when written as continued fractions
...
It can be seen that the sequence is repeating.
For conciseness, we use the notation √23 = [4;(1,3,1,8)],
to indicate that the block (1,3,1,8) repeats indefinitely.
The first ten continued fraction representations of (irrational) square roots are:

√2=[1;(2)], period=1
√3=[1;(1,2)], period=2
√5=[2;(4)], period=1
√6=[2;(2,4)], period=2
√7=[2;(1,1,1,4)], period=4
√8=[2;(1,4)], period=2
√10=[3;(6)], period=1
√11=[3;(3,6)], period=2
√12= [3;(2,6)], period=2
√13=[3;(1,1,1,1,6)], period=5

Exactly four continued fractions, for N ≤ 13, have an odd period.

How many continued fractions for N ≤ 10000 have an odd period?

Analisi:

Solo grazie a Wikipedia sono giunto alla soluzione.
Facendo riferimento a questo link, e precisamente:
“Sometimes what is desired is finding not the numerical value of a square root,
but rather its continued fraction expansion.
The following iterative algorithm can be used for this purpose
(S is any natural number that is not a perfect square):…”

In pratica il punto di partenza dell’algoritmo è:
m0 = 0
d0 = 1
a0 = la parte intera della radice quadrata del numero analizzato

>>> a0 = int(5**0.5)
>>> a0
2

a0 in sostanza è il primo termine della notazione classica delle frazioni
continue

Poi continuiamo con l’algoritmo secondo le formule:

m1 = d0 * a0 - m0
d1 = (n - m1 **2) / d0
a1 = int((a0 + m1)/ d1)

Nota: solo nel calcolo di ax, utilizziamo sempre a0, ovvero:

m2 = d1 * a1 - m1
d2 = (n - m2 **2) / d1
a2 = int((a0 + m2)/ d2)

es. con n = 114:

m0 = 0
d0 = 1
a0 = 10 (la radice quadrata di 114 = 10.677, quindi la parte intera è 10)
notazione = [10; ...]

avanti…

m1 = d0 * a0 - m0 = 1*10 - 0 = 10
d1 = (n - m1 **2) / d0 = (114 - 100) / 14 = 14
a1 = int((a0 + m1)/ d1) = int((10 + 10)/ 14 = int(20/14) = 1
notazione = [10; 1, ...]

avanti…

m2 = d1 * a1 - m1 = 14*1 - 10 = 4
d2 = (n - m2 **2) / d1 = (114 - 16) / 14 = 7
a2 = int((a0 + m2)/ d2) = int((10 + 4)/ 7 = int(17/7) = 2
notazione = [10; 1, 2, ...]

avanti…

m3 = d2 * a2 - m2 = 7*2 - 4 = 10
d3 = (n - m3 **2) / d2 = (114 - 100) / 7 = 2
a3 = int((a0 + m3)/ d3) = int((10 + 10)/ 2 = int(20/2) = 10
notazione = [10; 1, 2, 10, ...]

avanti…

m4 = d3 * a3 - m3 = 2*10 - 10 = 10
d4 = (n - m4 **2) / d3 = (114 - 100) / 2 = 7
a4 = int((a0 + m4)/ d4) = int((10 + 10)/ 7 = int(20/7) = 2
notazione = [10; 1, 2, 10, 2, ...]

avanti…

m5 = d4 * a4 - m4 = 7*2 - 10 = 4
d5 = (n - m5 **2) / d4 = (114 - 16) / 7 = 14
a5 = int((a0 + m5)/ d5) = int((10 + 4)/ 14 = int(14/14) = 1
notazione = [10; 1, 2, 10, 2, 1, ...]

avanti…

m6 = d5 * a5 - m5 = 14*1 - 4 = 10
d6 = (n - m6 **2) / d5 = (114 - 100) / 14 = 1 ** Bingo: d = 1
a6 = int((a0 + m6)/ d6) = int((10 + 10)/ 1 = int(20/1) = 20 ** Bingo: 2 * a0
notazione = [10; 1, 2, 10, 2, 1, 20, ...]

Qui, per la soluzione del nostro problema, ci fermiamo, poichè le cifre
comincerebbero a ripetersi:

m7 = d6 * a6 - m6 = 1*20 - 10 = 10 **** Uguale ad m1
d7 = (n - m7 **2) / d6 = (114 - 100) / 1 = 14 **** Uguale a d1
a7 = int((a0 + m7)/ d7) = int((10 + 10)/ 14 = int(20/14) = 1 **** Uguale a d1
notazione = [10; (1, 2, 10, 2, 1, 20)]

Quindi, ci interromperemo quando dx = 1 o quando ax = 2 * a0 (grazie Google,
anche se proseguendo in profondità e provando qualche numero, si giungerebbe
a questa soluzione anche senza il nostro immancabile amico).

Ecco il tutto messo insieme, per la risoluzione, con python, dell’odioso problema:

import time

st = time.time()
res = 0
 
for n in range(2, 10000):
    a0 = int(n ** 0.5)
    if a0 * a0 == n: continue # saltato perche' quadrato perfetto
    a, m, d = a0, 0, 1
    period = 0
    while a != 2 * a0 or d != 1: # esco dal ciclo
        m = d * a - m
        d = (n - m * m) / d
        a = int((a0 + m) / d)
        period += 1
    if period % 2 == 1: res += 1
 
print "euler 64: {}\n elapsed time: {}sec".format(res, time.time() - st)

oppure usando una funzione:

import time

st = time.time()
 
def odd_period(n):
    a0 = int(n ** 0.5)
    if a0 * a0 == n: return False # quadrato perfetto
    a, m, d = a0, 0, 1
    period = 0
    while a != 2 * a0 or d != 1:
        m = d * a - m # es. m2 = d1 * a1 - m1
        d = (n - m * m) / d # es. d2 = (n - m2*m2)/d1
        a = int((a0 + m) / d) # es. a2 = int((a0 + m2)/d2) sempre a0!
        period += 1
    if period % 2 == 1: return True

res = len([n for n in xrange(2, 10000) if odd_period(n)])
 
print "euler 64: {}\n elapsed time: {}sec".format(res, time.time() - st)

Quest’ultima è anche più veloce…
0.21sec contro 0.32sec della prima.

The primes 3, 7, 109, and 673, are quite remarkable.
By taking any two primes and concatenating them in any order
the result will always be prime.
For example, taking 7 and 109, both 7109 and 1097 are prime.
The sum of these four primes, 792, represents the lowest sum
for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any
two primes concatenate to produce another prime.

python:

import time
import itertools as it

ts = time.time()

def is_prime(num):
    if num <= 1: return False
    elif num == 2: return True
    elif num % 2 == 0: return False
    else:
        d = 3
        r = int(num**0.5)
        while d <= r:
            if num % d == 0: return False
            d += 2
        return True


def conc_primes(n, m):
    return is_prime(int(str(n) + str(m))) and is_prime(int(str(m) + str(n)))

def prime_pairs(iterable):
    for n, m in it.combinations(iterable, 2):
        if not conc_primes(n, m): return False
    return True

primes = [n for n in xrange(3,10000,2) if is_prime(n)] + [2]

def get_five():
    for n in primes:
        for m in primes[primes.index(n):]:
            if conc_primes(n ,m):
                for x in primes[primes.index(m):]:
                    if prime_pairs([x, n, m]):
                        for y in primes[primes.index(x):]:
                            if prime_pairs([y, x, n, m]):
                                for z in primes[primes.index(y):]:
                                    if prime_pairs([z, y, x, n, m]):
                                        return sum([z, y, x, n, m])

res = get_five() 
print "euler 60: {}\nelapsed time: {}sec".format(res, time.time() - ts)

Each character on a computer is assigned a unique code and the preferred standard is ASCII (American Standard Code for Information Interchange). For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.

A modern encryption method is to take a text file, convert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advantage with the XOR function  is that using the same encryption key on the cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 = 65.

For unbreakable encryption, the key is the same length as the plain text message, and the key is made up of random bytes. The user would keep the encrypted message and the encryption key in different locations, and without both "halves", it is impossible to decrypt the message.

Unfortunately, this method is impractical for most users, so the modified method is to use a password as a key. If the password is shorter than the message, which is likely, the key is repeated cyclically throughout the message. The balance for this method is using a sufficiently long password key for security, but short enough to be memorable.

Your task has been made easy, as the encryption key consists of three lower case characters. Using cipher1.txt (right click and 'Save Link/Target As...'), a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.

Analisi:
Ricorrendo a Google e più precisamente all’analisi crittografica, all’analisi della frequenza dei caratteri ed all’analisi della frequenza, è risultato che in un testo di medie dimensioni, il carattere più ripetuto è lo spazio.
Il carattere spazio è il doppio più frequente del carattere ‘e’ (più frequente tra le lettere in lingua inglese).
Quindi del testo cifrato, sapendo che la chiave di crittazione è di 3 caratteri, trovando i 3 caratteri cifrati più ricorrenti, si dovrebbero in teoria ottenere i caratteri spazio, sui quali sono state utilizzate ciclicamente le tre lettere della chiave di crittazione.
Sapendo che lo spazio rappresenta il numero 32, tramite XOR risaliamo a quale lettera della chiave di crittazione ci stiamo riferendo.
Ottenute le 3 lettere, si fanno i tentativi con le possibili parole di tre lettere inglesi, finchè non otteniamo un testo decrittato plausibile.

file_in = open(r'/home/banco/Python/cipher1.txt')
seq = [int(n) for n in file_in.readlines()[0].rstrip().split(',')]
file_in.close()
occs = set(seq)

qty = {}
for occ in occs:
    qty[occ] = seq.count(occ)
# ricerco i 3 caratteri più ripetuti
for i in range(3):
    value = max(qty.values())
    key = [k for k in qty.keys() if qty[k]==value][0]
    print 'chr: %s - count: %s - decrypted: %s' %(key, value, chr(key ^ 32))
    qty.pop(key)

otteniamo che i tre caratteri (presumibilmente sempre ‘spazio’) più ricorrenti sono:

>>> 
chr: 79 - count: 86 - decrypted: o
chr: 68 - count: 77 - decrypted: d
chr: 71 - count: 70 - decrypted: g

non ci sono moltepossibilità in inglese: ‘dog’ e ‘god’

God ispira di più… proviamo a decrittare:

# decritto il messaggio
i = 0
enc = ''
while i < len(seq):
    if i % 3 == 0:
        c = chr(seq[i]^ord('g'))
    elif (i + 2) % 3 == 0:
        c = chr(seq[i]^ord('o'))
    else:
        c = chr(seq[i]^ord('d'))
    enc += c
    i += 1
print enc

risultato:

>>>
"(The Gospel of John, chapter 1) 1 In the beginning the Word already existed.
....

sembra tanto lui.
Ora non resta che calcolare la somma dei singoli caratteri:

sum(ord(c) for c in enc)

Nota:
Il mio approccio è stato inizialmente di tentare le parole di tre lettere della lingua inglese, decisamente un approccio di Brute Force, che difficilmente sarebbe rimasto sotto al minuto.
Grazie Google.

Starting with 1 and spiralling anticlockwise in the following way,
a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right
diagonal, but what is more interesting is that 8 out of the 13 numbers
lying along both diagonals are prime; that is, a ratio of 8/13 ~ 62%.

If one complete new layer is wrapped around the spiral above,
a square spiral with side length 9 will be formed. If this process
is continued, what is the side length of the square spiral for which
the ratio of primes along both diagonals first falls below 10%?

python:

import time

ts = time.time()

_MEMO = {3:3, 5:5, 7:8}

def is_prime(num):
    if num <= 1: return False
    elif num == 2: return True
    elif num % 2 == 0: return False
    else:
        d = 3
        r = int(num**0.5)
        while d <= r:
            if num % d == 0: return False
            d += 2
        return True

def get_spiral_primes(side):
    count = 0
    for i in xrange(1,4):
        if is_prime(side**2 - i*side + i):
            count += 1
    return count

def spiral(side):
    _MEMO[side] = _MEMO[side-2] + get_spiral_primes(side)
    return _MEMO[side]

for i in xrange(7, 1000000, 2):
    if spiral(i)/float(i * 2 - 1) < 0.1:
        break

print "PE58: %s\nelapsed time: %ssec" %(i, time.time() - ts)

It is possible to show that the square root of two can be expressed
as an infinite continued fraction.

sqrt( 2 ) = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

The next three expansions are 99/70, 239/169, and 577/408,
but the eighth expansion, 1393/985, is the first example where the number
of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a
numerator with more digits than denominator?

Analisi:
partendo dalla prima iterazione del testo, si nota che la frazione successiva, sarà sempre così composta:
nuovo denominatore = vecchio numeratore + vecchio denominatore
nuovo numeratore = nuovo denominatore + vecchio denominatore

rapido ed indolore

python:

import time

ts = time.time()
num, den = 3, 2
count  = 0

i = 1
while i < 1000:
    newden = num + den
    num, den = newden + den, newden
    if len(str(num)) > len(str(den)):
        count += 1
    i += 1

print "problem euler 57: {}\nelapsed time: {}".format(count, time.time() - ts)

A googol (10^100) is a massive number: one followed by one-hundred zeros;
100^100 is almost unimaginably large: one followed by two-hundred zeros.
Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, a^b, where a, b < 100,
what is the maximum digital sum?

python:

import time

ts = time.time()

gmax = 0
for a in range(1, 100):
    for b in range(1, 100):
        googol = sum(int(digit) for digit in str(a**b))
        if googol > gmax:
            gmax = googol

print "problem euler 56: {}\nelapsed time: {}".format(gmax, time.time() - ts)

In the card game poker, a hand consists of five cards and are ranked,
from lowest to highest, in the following way:

  *  High Card: Highest value card.
  *  One Pair: Two cards of the same value.
  *  Two Pairs: Two different pairs.
  *  Three of a Kind: Three cards of the same value.
  *  Straight: All cards are consecutive values.
  *  Flush: All cards of the same suit.
  *  Full House: Three of a kind and a pair.
  *  Four of a Kind: Four cards of the same value.
  *  Straight Flush: All cards are consecutive values of same suit.
  *  Royal Flush: Ten, Jack, Queen, King, Ace, in same suit.

The cards are valued in the order:
2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.

If two players have the same ranked hands then the rank made up of the
highest value wins; for example, a pair of eights beats a pair of fives
(see example 1 below). But if two ranks tie, for example, both players
have a pair of queens, then highest cards in each hand are compared
(see example 4 below); if the highest cards tie then the next highest cards
are compared, and so on.

Consider the following five hands dealt to two players:
Hand	 	Player 1	 	Player 2	 	Winner
1	 	5H 5C 6S 7S KD          2C 3S 8S 8D TD          Player 2     
                Pair of Fives           Pair of Eights
	 	
2	 	5D 8C 9S JS AC          2C 5C 7D 8S QH          Player 1
                Highest card Ace        Highest card Queen
	 	
3	 	2D 9C AS AH AC          3D 6D 7D TD QD          Player 2
                Three Aces              Flush with Diamonds
	 	
4	 	4D 6S 9H QH QC          3D 6D 7H QD QS          Player 1     
                Pair of Queens          Pair of Queens
                Highest card Nine       Highest card Seven
	 	
5	 	2H 2D 4C 4D 4S          3C 3D 3S 9S 9D          Player 1
                Full House              Full House
                With Three Fours        with Three Threes
	 	
The file, poker.txt, contains one-thousand random hands dealt to two players.
Each line of the file contains ten cards (separated by a single space):
the first five are Player 1's cards and the last five are Player 2's cards.
You can assume that all hands are valid (no invalid characters or repeated
cards), each player's hand is in no specific order, and in each hand there
is a clear winner.

How many hands does Player 1 win?

python:

import time

ts = time.time()

def highest_card(cards):
    vals = []
    for card in [card[0] for card in cards]:
        vals.append(int(specials[card]))
    return max(vals)

def has_pairs(cards, limit=1):
    cards = ''.join([card[0] for card in cards])
    pairs = 0
    for card in cards:
        if cards.count(card) == 2:
            cards = cards.replace(card, '')
            pairs += 1
    return pairs == limit

def has_tris(cards):
    cards = ''.join([card[0] for card in cards])
    for card in cards:
        if cards.count(card) == 3:
            return True

def has_straight(cards):
    cards = sorted([specials[card[0]] for card in cards])
    for i in range(len(cards)):
        try:
            diff = cards[i+1] - cards[i]
            if diff == 1:
                straight = True
            else:
                straight = False
                break
        except IndexError:
            pass
    return straight

def has_flush(cards):
    suits = ''.join([card[1] for card in cards])
    flush = False
    for suit in 'HCSD':
        if suits.count(suit) == 5:
            flush = True
    return flush

def has_full(cards):
    cards = ''.join([card[0] for card in cards])
    n = cards.count(cards[0])
    if n == 2 or n == 3:
        cards = cards.replace(cards[0], '')
        m = cards.count(cards[0])
        if n + m == 5: return True
    return False

def has_poker(cards):
    cards = ''.join([card[0] for card in cards])
    return (cards.count(cards[0]) == 4 or cards.count(cards[1]) == 4)

def check_card(cards):
    if has_straight(cards) and has_flush(cards) and \
       highest_card([card[0] for card in cards]) == 14:
        return 9
    elif has_straight(cards) and has_flush(cards):
        return 8
    elif has_poker(cards):
        return 7
    elif has_full(cards):
        return 6
    elif has_flush(cards):
        return 5
    elif has_straight(cards):
        return 4 
    elif has_tris(cards):
        return 3
    elif has_pairs(cards, 2):
        return 2
    elif has_pairs(cards):
        return 1
    else: return 0

def check_tie_pair(cards):
    cards = ''.join([card[0] for card in cards])
    for card in cards:
        if cards.count(card) == 2:
            return specials[card]

specials = {'1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7,
            '8':8, '9':9, 'T': 10, 'J': 11, 'Q': 12, 'K': 13, 'A': 14}

file_in = open(r'poker.txt')
hands = file_in.readlines()
file_in.close()

count_p1 = 0
count_p2 = 0

for hand in hands:
    p1 = sorted(hand.split(' ')[:5])
    p2 = sorted(hand.rstrip().split(' ')[5:])
    score_p1 = check_card(p1)
    score_p2 = check_card(p2)
    if score_p1 > score_p2: count_p1 += 1
    elif score_p1 < score_p2: count_p2 += 1
    else:
        if score_p1 == 0:
            if highest_card(p1) > highest_card(p2):
                count_p1 += 1
            elif highest_card(p1) < highest_card(p2):
                count_p2 += 1
            
        elif score_p1 == 1: # tie pair
            if check_tie_pair (p1) > check_tie_pair(p2):
                count_p1 += 1
            elif check_tie_pair (p1) == check_tie_pair(p2):
                if highest_card(p1) > highest_card(p2):
                    count_p1 += 1
                elif highest_card(p1) < highest_card(p2):
                    count_p2 += 1
            else: count_p2 += 1
        if count_p1 + count_p2 == len(hands): break

print "problem euler 54: %s \nelapsed time: %ssec" %(
    count_p1, time.time() - ts)