Project Euler – Problem # 20 – Solved with Python

Find the sum of digits in 100!

n! means n * (n – 1) * … * 3 * 2 * 1

For example, 10! = 10 * 9 * … * 3 * 2 * 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

['9332621544394415268169923885626670049071596826438162146859296389521759999
32299156089414639761565182862536979208272237582511852109168640000000000000
00000000000']

So 100! gives you a long number, what the question is asking is to sum each digit in that long number.

# Python version = 2.7.2
# Platform = win32

from math import factorial

def main():
    """Main Program"""
    n = 100
    Sum = 0
    result = factorial(n)
    string_result = str(result)
    for number in string_result:
        Sum += int(number)
    print "Sum = %d" % Sum        
    
if __name__ == '__main__':
    main()

Project Euler

Advertisements

Pig Solitare – version I

The objective of this lab is to learn how to use functions to implement a solitaire version of a game called Pig. In Pig Solitaire, our objective is to reach a given goal score g within n turns. For example, you win the game if you score 100 points within 5 turns. Or, 50 points within 2 turns. You get to set the game parameters. In Pig Solitaire, during each turn, a player repeatedly rolls a die until either a 1 is rolled or the player holds and scores the sum of the rolls (i.e., the turn total). At any time during a player’s turn, the player is faced with two choices: roll or hold. If the player rolls a 1, the player scores nothing and a new turn begins. If the player rolls a number other than 1, the number is added to the player’s turn total and the player’s turn continues. If the player instead chooses to hold, the turn total is added to the player’s score and a new turn begins

Problem:

Pig Solitaire 1. Design and implement a Python program to implement Pig Solitaire. Your program must use the following three functions: (a) roll_die()—returns the result of a single roll of the die. (b)play_single_turn(total)—plays a single turn of Pig Solitaire and returns the number of points the player achieved on this turn. This function expects a value that will be stored in the parameter total, which denotes the total number of points the player has achieved so far. (c) main()—the foundation of the program and contains all of the code that does not appear in the roll_die or play_single_turn functions.

import random

g = input('How many points to win?: ')
n = input('What is the maximum number of turns?: ')

def roll_die():
    # Roll the die
    return random.randint(1,6)

def play_single_turn(total):
    # Play a single turn
    play = 'y'
    turn_total = 0
    while play != 'h':
        y = roll_die()
        if y == 1:
            # Turn over - got a 1!
            turn_total = 0
            print "Total points:\t", total
            print "Roll:\t", y
            print "Your turn is over!"
            print "Turn total: \t", turn_total
            print raw_input("Press <Enter> to continue... ")
            play = 'h'
        else:
            # Play turn
            turn_total = turn_total + y
            print "Total points:\t", total
            print "Roll:\t", y
            print "Turn total: \t", turn_total
            play = raw_input("Press <Enter> to roll again or 'h' to hold: \n")
            
    return turn_total

def main():
    total = 0
    turn = 1
    while turn <= n:
        print "\n*** TURN %s ***\n" % turn
        turn += 1
        x = play_single_turn(total)
        print "Total points = ", x
        total = total + x
        if total >= g:
            print "\nYOU WIN!"
            print "It took you %s turns to reach %s points." % ((turn-1),g)
            break
        else:
            continue
    else:
        print "\nYOU LOSE!"
        print "You failed to reach %s points in %s turns." % (g,(turn-1))

        
if __name__ == '__main__':
    main()

Output:


How many points to win?: 50
What is the maximum number of turns?: 3

*** TURN 1 ***

Total points: 0
Roll: 2
Turn total: 2
Press to roll again or 'h' to hold:

Total points: 0
Roll: 5
Turn total: 7
Press to roll again or 'h' to hold:

Total points: 0
Roll: 3
Turn total: 10
Press to roll again or 'h' to hold:

Total points: 0
Roll: 6
Turn total: 16
Press to roll again or 'h' to hold:
h
Total points = 16

*** TURN 2 ***

Total points: 16
Roll: 1
Your turn is over!
Turn total: 0
Press to continue...

Total points = 0

*** TURN 3 ***

Total points: 16
Roll: 4
Turn total: 4
Press to roll again or 'h' to hold:

Total points: 16
Roll: 1
Your turn is over!
Turn total: 0
Press to continue...

Total points = 0

YOU LOSE!
You failed to reach 50 points in 3 turns.
>>>
How many points to win?: 50
What is the maximum number of turns?: 3

*** TURN 1 ***

Total points: 0
Roll: 3
Turn total: 3
Press to roll again or 'h' to hold:

Total points: 0
Roll: 2
Turn total: 5
Press to roll again or 'h' to hold:

Total points: 0
Roll: 3
Turn total: 8
Press to roll again or 'h' to hold:

Total points: 0
Roll: 6
Turn total: 14
Press to roll again or 'h' to hold:

Total points: 0
Roll: 5
Turn total: 19
Press to roll again or 'h' to hold:

Total points: 0
Roll: 3
Turn total: 22
Press to roll again or 'h' to hold:
h
Total points = 22

*** TURN 2 ***

Total points: 22
Roll: 2
Turn total: 2
Press to roll again or 'h' to hold:

Total points: 22
Roll: 4
Turn total: 6
Press to roll again or 'h' to hold:

Total points: 22
Roll: 5
Turn total: 11
Press to roll again or 'h' to hold:

Total points: 22
Roll: 4
Turn total: 15
Press to roll again or 'h' to hold:

Total points: 22
Roll: 4
Turn total: 19
Press to roll again or 'h' to hold:
h
Total points = 19

*** TURN 3 ***

Total points: 41
Roll: 5
Turn total: 5
Press to roll again or 'h' to hold:

Total points: 41
Roll: 2
Turn total: 7
Press to roll again or 'h' to hold:

Total points: 41
Roll: 6
Turn total: 13
Press to roll again or 'h' to hold:
h
Total points = 13

YOU WIN!
It took you 3 turns to reach 50 points.

Original link

Pig Solitare – version II

The objective of this lab is to learn how to use functions to implement a solitaire version of a game called Pig. In Pig Solitaire, our objective is to reach a given goal score g within n turns. For example, you win the game if you score 100 points within 5 turns. Or, 50 points within 2 turns. You get to set the game parameters. In Pig Solitaire, during each turn, a player repeatedly rolls a die until either a 1 is rolled or the player holds and scores the sum of the rolls (i.e., the turn total). At any time during a player’s turn, the player is faced with two choices: roll or hold. If the player rolls a 1, the player scores nothing and a new turn begins. If the player rolls a number other than 1, the number is added to the player’s turn total and the player’s turn continues. If the player instead chooses to hold, the turn total is added to the player’s score and a new turn begins.

Problem:

Pig Solitaire 2. Design and implement a Python program to implement Pig Solitaire to maximize one’s score in n turns.

from __future__ import division
import random

n = input('What is the maximum number of turns?: ')

def roll_die():
    # Roll the die
    return random.randint(1,6)

def play_single_turn(total):
    # Play a single turn
    play = 'y'
    turn_total = 0
    while play != 'h':
        y = roll_die()
        if y == 1:
            # Turn over - got a 1!
            turn_total = 0
            print "Total points:\t", total
            print "Roll:\t", y
            print "Your turn is over!"
            print "Turn total: \t", turn_total
            print raw_input("Press <Enter> to continue... ")
            play = 'h'
        else:
            # Play turn
            turn_total = turn_total + y
            print "Total points:\t", total
            print "Roll:\t", y
            print "Turn total: \t", turn_total
            play = raw_input("Press <Enter> to roll again or 'h' to hold: \n")
            
    return turn_total

def main():
    total = 0
    turn = 1
    while turn <= n:
        print "\n*** TURN %s ***\n" % turn
        turn += 1
        x = play_single_turn(total)
        print "Total points = ", x
        total = total + x
        avg = total/n
    else:
        print "\n***GAME SUMMARY***"
        print "With %s turns, you reached %s points." % (n,total)
        print "Average points per turn: %s\n" % avg
    
if __name__ == '__main__':
    main()

Output:


What is the maximum number of turns?: 5

*** TURN 1 ***

Total points: 0
Roll: 4
Turn total: 4
Press to roll again or 'h' to hold:

Total points: 0
Roll: 3
Turn total: 7
Press to roll again or 'h' to hold:

Total points: 0
Roll: 1
Your turn is over!
Turn total: 0
Press to continue...

Total points = 0

*** TURN 2 ***

Total points: 0
Roll: 5
Turn total: 5
Press to roll again or 'h' to hold:

Total points: 0
Roll: 4
Turn total: 9
Press to roll again or 'h' to hold:

Total points: 0
Roll: 1
Your turn is over!
Turn total: 0
Press to continue... h
h
Total points = 0

*** TURN 3 ***

Total points: 0
Roll: 6
Turn total: 6
Press to roll again or 'h' to hold:

Total points: 0
Roll: 6
Turn total: 12
Press to roll again or 'h' to hold:

Total points: 0
Roll: 4
Turn total: 16
Press to roll again or 'h' to hold:
h
Total points = 16

*** TURN 4 ***

Total points: 16
Roll: 1
Your turn is over!
Turn total: 0
Press to continue...

Total points = 0

*** TURN 5 ***

Total points: 16
Roll: 2
Turn total: 2
Press to roll again or 'h' to hold:

Total points: 16
Roll: 4
Turn total: 6
Press to roll again or 'h' to hold:

Total points: 16
Roll: 1
Your turn is over!
Turn total: 0
Press to continue...

Total points = 0

***GAME SUMMARY***
With 5 turns, you reached 16 points.
Average points per turn: 3.2

Original link

Use Functions to Write the Following Python Programs:

This problem was similar to Project Euler’s # 17 so I decided to solve it.

Can anyone solve this using functions?

Problem:

Integer to English conversion. Given an integer value,
return a string with the equivalent Englist text of each digit.
For example, an input of 89 results in “eight-nine” being
returned. For an extra challenge, return English text with
proper usage, i.e., “eighty-nine.” For this problem, restrict
values to be between 0 and 1,000.

number = {
    1:'one',2:'two',3:'three',4:'four',5:'five',6:'six',7:'seven',
    8:'eight',9:'nine',10:'ten',11:'eleven',12:'twelve',13:'thirteen',
    14:'fourteen',15:'fifteen',16:'sixteen',17:'seventeen',
    18:'eighteen',19:'nineteen',20:'twenty',30:'thirty',40:'fourty',
    50:'fifty',60:'sixty',70:'seventy',80:'eighty',90:'ninety',
    100:'hundred',1000:'thousand'}

x = input('Please enter an number between 1 and 1000: ')
x1 = str(x)
if len(x1) == 1:
    # If user enters a number between 1-9
    print "Integer in English is: ",  number[x]
elif len(x1) == 2:
    # If user enters a number between 10-99
    x2 = x1[0:1]
    x3 = x1[1:2]
    if x < 20:
        # Consider numbers less than 20
        print "Integer in English is: ", number[x]
    elif x2 != '0' and x3 == '0':
        # Consider multiples of 10: 20, 30 ...
        print "Integer in English is: ", number[x]
    else:
        # Consider all other numbers less than 100
        x4 = str(x2 + '0')
        print "Integer in English is:", number[int(x4)] + \
              '-' + number[int(x3)]
elif len(x1) == 3:
    # If user enters a number between 100-999
    x2 = x1[0:1]
    x3 = x1[1:2]
    x4 = x1[2:3]
    x5 = (x3 + x4)
    x6 = x3 + '0'
    if x3 == '0' and x4 == '0':
        # Consider the 100, 200, 300 numbers ...
        print "Integer in English is:", number[int(x2)] \
              + '-' + number[100]
    elif x3 == '0' and x4 != '0':
        # Consider 101-109, 201-209, ...
        print "Integer in English is:", number[int(x2)]+ \
              '-' + number[100] + ' and ' + number[int(x4)]
    elif x3 != '0' and x4 == '0':
        # Consider 110,120,130, 210,220,230 ...
        print "Integer in English is:", number[int(x2)] \
              + '-' + number[100] + ' and ' + number[int(x5)]
    elif x3 == '1' and x4 != '0':
        # Consider the teens 111-119, 211-219 ...
        print "Integer in English is:", number[int(x2)] \
              + '-' + number[100] + ' and ' + number[int(x5)]
    else:
        # Consider all other 3 digit numbers
        print "Integer in English is:", number[int(x2)] \
              + '-' + number[100] + ' and ' + number[int(x6)] \
              + '-' + number[int(x4)]
elif len(x1) == 4 and x == 1000:
    # If user enters 1000
    print "Integer in English is:", number[1] + '-' + number[1000]
else:
    # If user enters something other than a number from 1-1000
    print "Please try again"



Project Euler – Problem # 17 – Solved with Python

Update:

Thanks to a nice comment from a gentleman – Adam… He pointed out that the correct spelling for ‘fourty’ is ‘forty’. The answer now comes out to be 21124.

I did this problem twice and came up with a total of 21224 each time. The correct answer is supposed to be 21124.

Problem:

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.

One Possible Solution:

Project Euler – Problem # 14 – Solved with Python

Problem:

The following iterative sequence is defined for the set of positive integers:

n –> n/2 (n is even)

n –> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 –> 40 –> 20 –> 10 –> 5 –> 16 –> 8 –> 4 –> 2 –> 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

**********

Help from this blog for the idea of a Cache of known numbers.

# Python version = 2.7.2
# Platform = win32

import time

def main():
    """Main Program"""
    start_time = time.clock()
    largest = 0
    longest_sequence = 0
    Cache = dict()
    for n in xrange(2, 1000001):
        Number = n
        counter = 0
        while Number > 1:
            try:
                counter += Cache[Number] - 1
                break
            except KeyError:
                pass
            
            if Number % 2 == 0:
                Number = Number / 2
            else:
                Number = Number * 3 + 1
            counter += 1

        counter += 1
        Cache[n] = counter

        if counter > longest_sequence:
            longest_sequence = counter
            largest = n

    print "Answer = %s" % largest
    print "longest sequence = %s" % longest_sequence
    
    run_time = time.clock() - start_time
    print "Run time = ", run_time
        
if __name__ == '__main__':
    main()

Project Euler – Problem # 13 – Solved with Python

Python can handle these large number (50 digits and their addition) without any special handling

Problem:

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

# Python version = 2.7.2
# Platform = win32

def main():
    f = open('one-hundred_50.txt', 'rU')
    tally = 0 
    for g in f.readlines():
        gpl = g.replace('\n', '')
        if gpl.isdigit():
            number = int(gpl)
            tally = number + tally
        else:
            print "The varialble gpl contains no digit"
    f.close()
    print "tally = ", tally

if __name__ == '__main__':
    main()

Project Euler