4
\$\begingroup\$

I just finished Project Euler #8 in Swift, and since there is not any version yet on Code Review, I would like to have some comments on what I did to try to improve it.

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

import Foundation

extension String {
    subscript (r: Range<Int>) -> String {
        get {
            let subStart = advance(self.startIndex, r.startIndex, self.endIndex)
            let subEnd = advance(subStart, r.endIndex - r.startIndex, self.endIndex)
            return self.substringWithRange(Range(start: subStart, end: subEnd))
        }
    }
    func substring(from: Int, length: Int) -> String {
        let end = from + length
        return self[from..<end]
    }
}

func largestProduct(digits:Int) -> Int {

    let str = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"

    var maxNumber = 0
    let maxLength = countElements(str) - digits
    for var i = 0; i < maxLength; ++i {

        let strNumber = str.substring(i, length: digits)

        var number = 1
        for char in strNumber {
            let charNumber = String(char).toInt()!
            number *= charNumber
        }

        if number > maxNumber {
            maxNumber = number
        }
    }

    return maxNumber
}

func printTimeElapsedWhenRunningCode(operation:(Int) -> Int) {
    let startTime = CFAbsoluteTimeGetCurrent()
    let number = operation(4)
    println(number)
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    println("Time elapsed : \(timeElapsed) s")
}

printTimeElapsedWhenRunningCode(largestProduct)

The code executes in 0.0799770355224609 s

\$\endgroup\$
  • \$\begingroup\$ I have taken the liberty to undo your last edit. Compare "What you can and cannot do after receiving answers", in particular "You must not edit the code in the question, ..." and "You also should not append your revised code to the question. ..." \$\endgroup\$ – Martin R Dec 29 '14 at 12:35
  • \$\begingroup\$ Oh ok. Thanks, I did not know that. So how someone is supposed to try and make the code better/cleaner/faster in the future while comparing to the latest version ? Posting a new question seems overkill to me... \$\endgroup\$ – Mehdi.Sqalli Dec 29 '14 at 13:37
  • \$\begingroup\$ The above referenced meta answer lists all your options. \$\endgroup\$ – Martin R Dec 29 '14 at 13:48
1
\$\begingroup\$

I may not know swift, but here's a java code to fasten the calculation. Please find the algorithm inline with the comments.:

public static void main (String[] args) throws java.lang.Exception
{
    String input ="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";

    int digit = 13;
    // 1.calculate the initial product of first 13 numbers.
    long max = getProduct(input,0,digit); 

    long prevVal = max;
    // Run a loop and use sliding window concept.
    // i.e remove the first number of the window from the product and add the new one.
    // For window size 3, with input "10345", prevVal = 1*0*3 for window "103". 
    // Slide the window to prevVal  = (1*0*3)/1 * 3; for window "034".
    // In case if removed element is 0, recalculate the window product.
    // For window "345", do prevVal = 3*4*5 instead of the above rule.
    for(int i=digit;i<input.length();i++){
        int leftVal = input.charAt(i-digit)-48;
        if(leftVal!=0){
            if(prevVal!=0){ // An optimisation to avert calculation if prevVal is 0
            // Sliding the window.
            prevVal = (prevVal/leftVal) * (input.charAt(i)-48);
            }
        }else{
            // Recalculation because of 0.
            prevVal = getProduct(input,i-digit+1,i+1);;
        }
        max = Math.max(max,prevVal);
    }
    System.out.println(">> " + max);
}

// calculates the product for the given window size , i.e from startIdx(inclusive) to endIdx (exclusive).
private static long getProduct(String input, int startIdx, int endIdx){
    long product = 1;
    for(int i=startIdx;i<endIdx;i++){
        product = product*(input.charAt(i)-48);
    }
    return product;
}
\$\endgroup\$
  • \$\begingroup\$ You can also consider pseudocode if this may be harder to understand for the OP. \$\endgroup\$ – Jamal Dec 24 '14 at 22:23
  • \$\begingroup\$ Thanks for the review, but the code of @MartinR, is faster. \$\endgroup\$ – Mehdi.Sqalli Dec 25 '14 at 8:46
  • 1
    \$\begingroup\$ Are you sure? Could you combine my optimisation in Swift code along with Martin's and check. I am sure this should be faster because Martin or yours has complexity of O(13*n) where n is the length of input. Mine's worst/avg/best case is O(13*n) when all input is 0 and best case is O(n) \$\endgroup\$ – thepace Dec 25 '14 at 10:44
  • \$\begingroup\$ My bad. It is faster now. 0.012s. Thanks! \$\endgroup\$ – Mehdi.Sqalli Dec 25 '14 at 15:47
  • 1
    \$\begingroup\$ You can use just my answer without the changes from Martin's . It would work with same latency. \$\endgroup\$ – thepace Dec 25 '14 at 15:50
3
\$\begingroup\$

Let's start with a performance improvement: Your method repeatedly extracts substrings from the given digit string (which is a costly operation with Swift strings), and then repeatedly converts the characters in a substring to an integer. It is better to convert the entire string to an array of integers once with a single string traversal:

func largestProduct(numDigits : Int) -> Int {

    let str = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
    let digits = Array(str).map { String($0).toInt()! }

    var maxNumber = 0
    let maxLength = digits.count - numDigits
    for var i = 0; i < maxLength; ++i {

        var number = 1
        for var j = i; j < i + numDigits; j++ {
            number *= digits[j]
        }

        if number > maxNumber {
            maxNumber = number
        }
    }

    return maxNumber
}

On my computer (with the program compiled in Release mode), this reduced the time to compute largestProduct(13) from 0.065 seconds to 0.002 seconds.

(The rest of this review is about the code organisation and might be opinion based.)

I would pass the given digits as an argument to the largestProduct() function. One advantage is that it is easier to add test cases.

for var i = 0; i < maxLength; ++i {  }

can be written more swifty using a range:

for i in 0 ..< maxLength { }

and the multiplication of the digits to a number can be done with reduce().

Then your function would look like this:

func largestProduct(digits : [Int], numDigits : Int) -> Int {

    var maxNumber = 0
    let maxLength = digits.count - numDigits
    for i in 0 ..< maxLength {
        let number = reduce(i ..< i + numDigits, 1) { $0 * digits[$1] }
        if number > maxNumber {
            maxNumber = number
        }
    }

    return maxNumber
}

Your printTimeElapsedWhenRunningCode() function is not optimal for reuse. It is restricted to functions taking an Integer argument and returning an integer, and the argument (4 or 13 in this case) is part of the function.

I would change that to take a ()->Void closure:

func printTimeElapsedWhenRunningCode(operation:()->Void) {
    let startTime = CFAbsoluteTimeGetCurrent()
    operation()
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    println("Time elapsed : \(timeElapsed) s")
}

and define a function doing all the work:

func euler8()  {
    let str = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"

    let digits = Array(str).map { String($0).toInt()! }

    let result = largestProduct(digits, 13)
    println(result)
}

Now you can measure the time with:

printTimeElapsedWhenRunningCode(euler8)

and the printTimeElapsedWhenRunningCode function is fully reusable.

\$\endgroup\$
  • \$\begingroup\$ Thanks. Really clean. And it is more swifty like this. The performance went from 0.079 s to 0.035 s. It is weird though that when I use the more swifty way of iteration, it is a little slower. If I use var i = 0; i <...;i++, and make a loop instead of the reduce and map, it goes down to 0.029 \$\endgroup\$ – Mehdi.Sqalli Dec 25 '14 at 8:51
  • \$\begingroup\$ @Mehdi.Sqalli: Did you compare in "Debug" or "Release" mode? \$\endgroup\$ – Martin R Dec 25 '14 at 9:30
  • \$\begingroup\$ Release, every time. \$\endgroup\$ – Mehdi.Sqalli Dec 25 '14 at 9:34
  • \$\begingroup\$ @Mehdi.Sqalli please see my answer - I have an O(n) algorithm that should be substantially faster than this one. \$\endgroup\$ – Alnitak Dec 28 '14 at 16:06
2
\$\begingroup\$

Using the same refactoring as @MartinR, this is my answer that performs 4x faster than the naive algorithm with a loop, and 6x faster than using reduce:

func largestProduct(digits: [Int], numDigits: Int) -> Int {

    var maxNumber = 0
    let maxLength = digits.count

    var runningCount = 0
    var number = 1

    for var i = 0; i < maxLength; ++i {
        var n = digits[i];
        if (n > 0) {
            number *= n
            if ++runningCount == numDigits {
                if number > maxNumber {
                    maxNumber = number
                }
                number /= digits[i - numDigits + 1]
                --runningCount
            }
        } else {
            runningCount = 0
            number = 1
        }
    }

    return maxNumber
}

It works by successively accumulating the product until the required number of digits is found, and then dividing by the first digit in preparation for the next iteration.

In this way it avoids performing m multiplications per digits, making the algorithm O(n) instead of O(n * m), where n is the original string length and m is the number of digits to consider.

Furthermore, if the found digit is zero it knows to short circuit the evaluation and start again from the digit following the zero.

\$\endgroup\$
  • \$\begingroup\$ Yes, it is the same algorithm that @thepace used. I updated my code with the new version. My code runs as fast as yours in Release mode. And I prefer the more swifty look of mine. \$\endgroup\$ – Mehdi.Sqalli Dec 29 '14 at 10:20
  • \$\begingroup\$ @Mehdi.Sqalli this is an improved version of thepace's algorithm and in my own benchmarks (which separated out the creation of the digit array from the search) this part far outperformed any other version here, doing 10k iterations in 5ms total. \$\endgroup\$ – Alnitak Dec 29 '14 at 12:48
  • \$\begingroup\$ You can check my code here : github.com/MehdiSv/Swift-Euler-Project/blob/master/… I have the same execution time. \$\endgroup\$ – Mehdi.Sqalli Dec 29 '14 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.