Project Euler – Problem 62 – Solved with Python

The cube, 41063625 (345³), can be permuted to produce two other cubes: 56623104 (384³) and 66430125 (405³). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

**********

Since we know that all permutations are in the list of cubes, we can just iterate thru that list. I created a sorted list for the permutation and compared it with a sorted list of the other elements in the cubes list.

# Python version = 2.7.1
# Platform = win32

import time

def create_cubes():
    """Create a set of cubes"""
    L = []
    for c in range(1, 20000):
        cube = pow(c, 3)
        L.append(cube)
    return set(L)

def main():
    """Main program"""
    start_time = time.clock()
    cc = create_cubes()
    for n in cc:
        cbe = str(n)
        cbe = sorted(list(cbe))
        L = []
        for m in cc:
            cpr = str(m)
            cpr = sorted(list(cpr))
            if cpr == cbe:
                L.append(m)
        if len(L) == 5:
            print L
            print "\n"
            break
        else:
            continue
    run_time = time.clock() - start_time
    print "Run time = ", run_time

if __name__ == '__main__':
    main()

Project Euler – Problem # 58 – Solved with Python

Problem:

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

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%?

**********

This problem is similar to Project Euler problem # 28. I just reworked that problem: We form a diagonal, and check the numbers in the diagonal for primality. I used high – low, ‘guess this number’ testing for the length of the diagonal. 13121 is the first number that came out as less than 10% for the ratio. So if we double that number we get 26242, with 26241 being the answer to this problem. (The last diagonal with 10% or more primes is 13120. Multiply this by 2 we get 26240, then add 1 for the center and we have 26241.)

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

from __future__ import division
import gmpy

def isprime(n):
    """Return True of False - Prime Number"""
    if gmpy.is_prime(n):
        return True
    else:
        return False

def form_diagonal(passed):
    """Form a leg of the diagonal, return the
    number of primes in that leg, and (i), which
    is 1/2 the length of the diagonal."""
    summer = 1
    adder = 0
    L = []
    for i in range(1, 13121): # 1/2 the length of the diagonal
        if i < 2:
            adder = passed
        else:
            adder = adder + 8
        summer = summer + adder
        if isprime(summer):
            L.append(summer)
    return len(L), i
        
def main():
    """Main Program"""
    upper_right = form_diagonal(2)
    upper_left = form_diagonal(4)
    lower_left = form_diagonal(6)
    lower_right = form_diagonal(8)
    primes = upper_right[0] + upper_left[0] + \
             lower_left[0] + lower_right[0]
    all_numbers = (lower_right[1] * 4) + 1
    ratio = primes / all_numbers
    print "ratio = ", ratio
    if ratio < .10:
        print "Ratio is less than 10%"
    
if __name__ == '__main__':
    main()

Project Euler – Problem # 56 – Solved with Python

Problem:

A googol (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 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?

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

def main():
    """Main Program"""
    answer = 0 
    for a in range(1, 101):
        for b in range(1, 101):
            natural_number = a ** b
            L = list(str(natural_number))
            digital_sum = 0
            for i in L:
                digital_sum = digital_sum + int(i)
            if digital_sum > answer:
                answer = digital_sum
    print "Answer = ", answer

if __name__ == '__main__':
    main()

Project Euler – Problem # 55 – Solved with Python

Problem:

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

• 349 + 943 = 1292,
• 1292 + 2921 = 4213
• 4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

def palindromic(tally):
    """Check if number (tally) is a palindrome"""
    x = str(tally)
    y = x[::-1]
    if x == y:
        return True
    else:
        return False

def isLychrel(n):
    """Check if number (n) is a Lychrel number"""
    counterL = 0
    while counterL < 50:
        reverse = int(str(n)[::-1])
        tally = n + reverse
        if palindromic(tally):
            return False
        else:
            n = tally
        counterL += 1
    return True
   
def main():
    """Main Program"""
    counter = 0
    for n in range(10, 10001):
        if isLychrel(n):
            counter += 1
    print "Answer = ", counter

if __name__ == '__main__':
    main()

Project Euler – Problem # 54 – Solved with Python

Problem:

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?

One Possible Solution:

# Python version = 2.7.1
# Platform = win32

from collections import Counter

d = {'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, 'One Pair': 29, 'Two Pairs': 59, \
     'Three of a Kind': 74, 'Straight': 89, 'Flush': 104, \
     'Full House': 119, 'Four of a Kind': 134,
     'Straight Flush': 149, 'Royal Flush': 164}

def high_card(dL):
    """Is the hand High Card?"""
    holder = 0
    if len(dL) == 5:
        return True
    else:
        return False

def one_pair(dL):
    """Is the hand One Pair?"""
    if len(dL) == 4:
        for k, v in dL.iteritems():
            if v == 2:
                return True
            else:
                continue
    else:
        return False

def two_pairs(dL):
    """Is the hand Two Pairs?"""
    counter = 0
    k1 = 0
    if len(dL) == 3:
        for k, v in dL.iteritems():
            if v == 2:
                if k > k1:
                    k1 = k
                counter += 1
                if counter == 2:
                    return True
            else:
                continue
    else:
        return False
    
def three_of_a_kind(dL):
    """Is the hand Three of a Kind?"""
    if len(dL) == 3:
        for k, v in dL.iteritems():
            if v == 3:
                return True
            else:
                continue
    else:
        return False

def straight(L):
    """Is the hand a Straight?"""
    L = sorted(L)
    if (L[0] + 1) == L[1] and (L[0] + 2) == \
       L[2] and (L[0] + 3) == L[3] and \
       (L[0] + 4) == L[4]:
        return True
    else:
        return False
    
def flush(L1):
    """Is the hand a Flush"""
    if len(Counter(L1)) == 1:
        return True
    else:
        return False

def full_house(dL):
    """Is the hand a Full House?"""
    if len(dL) == 2:
        for k, v in dL.iteritems():
            if v == 3:
                return True
            else:
                continue
    else:
        return False

def four_of_a_kind(dL):
    """Is the hand Four of a Kind?"""
    if len(dL) == 2:
        for k, v in dL.iteritems():
            if v == 4:
                return True
            else:
                continue
    else:
        return False

def straight_flush(L, L1):
    """Is the hand a Straight Flush?"""
    L = sorted(L)
    if len(Counter(L1)) == 1 and \
       ((L[0] + 1) == L[1] and (L[0] + 2) == \
       L[2] and (L[0] + 3) == L[3] and \
       (L[0] + 4) == L[4]):
        return True
    else:
        return False

def royal_flush(L, L1):
    """Is the hand a Royal Flush?"""
    if len(Counter(L1)) == 1 and sum(L) == 60:
        return True
    else:
        return False
    
def examine_cards(cards):
    """Examine Cards"""
    L, L1 = [], []
    dL = {}
    for i in range(0, 9, 2):
        x1 = d[cards[i]]
        L.append(x1)
    for i in range(1, 10, 2):
        x1 = cards[i]
        L1.append(x1)
    for i in L:
        dL[i] = L.count(i)
    if royal_flush(L, L1):
        return d['Royal Flush']
    elif straight_flush(L, L1):
        return d['Straight Flush']
    elif four_of_a_kind(dL):
        c1 = 0
        for k, v in dL.iteritems():
            if v == 4:
                c1 = k
        return d['Four of a Kind'] + c1
    elif full_house(dL):
        c2 = 0
        for k, v in dL.iteritems():
            if v == 3:
                c2 = k
        return d['Full House'] + c2
    elif flush(L1):
        c3 = 0
        for k, v in dL.iteritems():
            if k > c3:
                c3 = k
        return d['Flush'] + c3
    elif straight(L):
        c4 = 0
        for k, v in dL.iteritems():
            if k > c4:
                c4 = k
        return d['Straight'] + c4
    elif three_of_a_kind(dL):
        c5 = 0
        for k, v in dL.iteritems():
            if v == 3:
                c5 = k
        return d['Three of a Kind'] + c5
    elif two_pairs(dL):
        k1 = 0
        for k, v in dL.iteritems():
            if v == 2:
                if k > k1:
                    k1 = k
        return d['Two Pairs'] + k1
    elif one_pair(dL):
        c6 = 0
        for k, v in dL.iteritems():
            if v == 2:
                c6 = k
        return d['One Pair'] + c6 
    elif high_card(dL):
        count1 = 0
        for k, v in dL.iteritems():
            if k > count1:
                count1 = k
        return count1
    else:
        print "***Error Message***"
    
def main():
    """Main Program"""
    player1 = 0
    f = open('poker.txt', 'r')
    for line in f:
        x = line.split(' ')
        y = ''.join(x)
        player_one = y[0:10]
        player_two = y[10:20]
        j = examine_cards(player_one)
        t = examine_cards(player_two)
        if j == t:
            print "player_one = ", player_one
            print "player_two = ", player_two
            print "EQUAL"
        elif j < t:
            continue
        elif j > t:
            player1 += 1
        else:
            pass
    f.close()
    print "Answer = ", player1
    
if __name__ == '__main__':
    main()

Project Euler – Problem # 52 – Solved with Python

Problem:

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

One Possible Solution:

# Python version = 2.7.1
# Platform = win32
# stop_time =  11.3020665768 (seconds)

import time

d = {0: "zero", 1: "one", 2: "two", 3: "three", 4: "four", \
     5: "five", 6: "six", 7: "seven", 8: "eight", 9: "nine"}

def main():
    """Main Program"""
    start_time = time.clock()
    counter = 1
    while counter < 150000:
        L = []
        for n in range(2, 7):
            result = str(counter * n)
            L.append(result)
        L3 = []
        for number in L:
            L2 = []
            for i, digit in enumerate(number):
                s = int(digit)
                L2.append(d[s])
            L3.append(L2)
        if cmp(sorted(L3[0]), sorted(L3[1])) == 0 and \
           cmp(sorted(L3[0]), sorted(L3[2])) == 0 and \
           cmp(sorted(L3[0]), sorted(L3[3])) == 0 and \
           cmp(sorted(L3[0]), sorted(L3[4])) == 0:
            print "YAHOO = ", counter
        counter += 1
    stop_time = time.clock() - start_time
    print "stop_time = ", stop_time
    
if __name__ == '__main__':
    main()