Project Euler: Problem 13

Another day, another problem to solve, let's see what the problem No. 13 is about:

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

    …[44 more numbers]…

Okay, this time the issue to overcome is dealing with such large numbers. Adding them then is easy, just the strategy need to be developed. I decided to stick with the usual way of adding numbers where you wrtie the numbers below each other and then add the corresponding numbers. If the result is bigger than 9, you add the leftover to the next row of numbers of higher order.

Using simple arrays this can be accomplished without complications, what we will do is that we'll parse all the number strings and create arrays of numbers from them. Then, adding corresponding numbers together we get our mid results and parse them again, and adding new arrays if they'd be bigger than 9 and only collecting single digits. When all these digits are collected, appending first ten to an empty string does the trick.

    fn getNums filePath =
        local result = #()
        local file = openFile filePath

        while NOT EOF file do
            append result (readLine file)

        close file

    fn parseNum str =
        local charCount = str.count
        for char = 1 to charCount collect str[char] as integer

    fn addNums strArr =
        local resultArr = #()
        local arr = for str in strArr collect parseNum str

        while arr.count > 0 do
            local eachCount
            local sum = 0

            for index = arr.count to 1 by -1 do
                local each = arr[index]
                if (eachCount = each.count) > 0 then
                    sum += each[eachCount]
                    deleteItem each eachCount
                else deleteItem arr index
            if sum >= 10 do
                local parsedSum = parseNum (sum as string)
                sum = parsedSum[parsedSum.count]
                deleteItem parsedSum parsedSum.count
                append arr parsedSum
            insertItem sum resultArr 1
        if resultArr[1] == 0 do
            deleteItem resultArr 1


    local res = addNums (getNums "Z:\Euler\prob13.txt")
    local solution = ""
    for i = 1 to 10 do append solution (res[i] as string)

Just one side note, if I'd do it again, I'd collect the digits in reverse order, makes iterating and adding higher order digits much easier and elegant.

DISCLAIMER: All scripts and snippets are provided as is under Creative Commons Zero (public domain, no restrictions) license. The author and this blog cannot be held liable for any loss caused as a result of inaccuracy or error within these web pages. Use at your own risk.

This Post needs Your Comment!

Return to top