Project Euler Problem 30

My solution to Project Euler Problem 30.

Here’s the problem:

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44
As 1 = 14 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

My Solution:

# Author: Will Clausen
# Date: 4/7/14
# Description: This file solves problem 30 for Project Euler

import math

# This function solves problem 30. Some noteworthy solution details include
# using a list to go through the set of possible numbers. I used a list
# because I wanted a way to easily obtain the next distinct permutation of
# numbers with digits in increasing order from left to right.
def problem30():
    # Store the final sum in this variable
    final = 0

    # Start by checking 11, because the numbers 1 through 10 are clearly
    # not going to meet the crtiteria of the problem.
    check = [0, 0, 0, 0, 1, 1]
    checkNum = listToNum(check)

    # This loop condition is an artifact of how I increment the number I am
    # checking (note that I check numbers in list form). Think of it as
    # saying, "while the number being checked is within the known limit of
    # possibilities"
    while check[0] != 10:
        # Get the sum of the fifth powers of the digits.
        digitSum = sumOfDigits(check)

        # Convert this sum into a list
        digitSumList = numToList(digitSum)
        helper = []

        # Loop through the digits of the number being checked
        # to determine if the number being checked can be permuted
        # into its sum (in which case, we want to add that number to
        # the final sum).
        good = True
        for i in range(len(check)):
            if check[i] not in digitSumList:
                good = False
                break
            digitSumList.remove(check[i])
        if good:
            final += digitSum

        # Move to the next number 
        check = nextNum(check)
        checkNum = listToNum(check)

    return final

# This function takes in a number in list form (base 10) and increments it
# to the next number that has all its digits in increasing order from left to
# right.
def nextNum(numList):
    # The list must have length greater than 0 for
    # this function to make any sense
    assert(len(numList) > 0)

    # Start with the least significant digit, and work towards
    # the bigger numbers
    index = len(numList) - 1

    # Increment the number
    numList[index] += 1

    # If this causes the number to equal 10, update accordingly
    while numList[index] == 10:
        # If the last spot in the number list is now at 10
        # that means there is nowehere left to increment, so
        # just terminate and return the messed up list
        if index == 0:
            break

        # Move the index to the left 1
        index -= 1

        # Demonstrate that ten 1's is equal to one 10 and add
        # accordingly.
        numList[index] += 1

    # Here's where things get weird. In the while loop above,
    # note that some indices of numList will have tens in them
    # here's where we make those numbers make sense. In the problem,
    # it's not necessary to loop through every number, we only need to
    # loop through distinct permutations of numbers with a certain number
    # of digits. e.g. if we just checked 123, we have also checked
    # 132, 231, 213, 312, 321. This loop ensures that we get a new DISTINCT
    # number that we haven't checked before. It makes everything much faster.
    for i in range(index, len(numList)):
        numList[i] = numList[index]

    return numList

# This function takes a number in list form, and converts it to integer form
def listToNum(numList):
    # Start by taking the most significant digit
    num = numList[0]
    for i in range(1, len(numList)):
        # This ensures that the most significant digit ends up in the right
        # place.
        num *= 10

        # Add the proper digit in the proper spot
        num += numList[i]

    return num

# This function takes a number in integer form and converts it to list form.
def numToList(num):
    # The easiest way to code this was to make the number a string...
    strNum = str(num)
    final = [0, 0, 0, 0, 0, 0]
    
    # ... then loop through the string and convert the character back to an
    # integer. I don't know if this is the most efficient way to do this,
    # but it was the solution that came to mind most quickly.
    for i in range(len(strNum)):
        final[len(final) - i - 1] = int(strNum[len(strNum) - i - 1])

    return final
    
# This function sums the fifth power of the digits in an input number
def sumOfDigits(numList):
    final = 0
    for i in range(0, len(numList)):
        final += pow(numList[i], 5)

    return final

# Run the program to determine the solution.
if __name__ == "__main__":
    answer = problem30()
    print "Answer: " + str(answer)