Project Euler #8 - Largest product in a sequence

Question

I've just finished Project Euler Problem 8, which ask for the greatest product of any sequence of 13 consecutive digits in a given string.

I wonder if there's something that could be improved.

function EulerProblem8() {

	var amountOfDigits = 13;
	var sequence = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
	var highestSum = 0;
	var firstIndx = 0;
	var lastIndx = firstIndx + amountOfDigits;
	
	while(lastIndx != sequence.length)
	{
		var substr = sequence.substring(firstIndx, lastIndx);
		var array = substr.split('');
		
		var sum = 1;
		for(var c in array) {
			var i = array[c] * 1.0;
			
			sum = sum * i;
		}
		
		if(sum > highestSum)
			highestSum = sum;
			
		firstIndx = firstIndx + 1;
		lastIndx = firstIndx + amountOfDigits;
	}
	
	document.getElementById('output').innerHTML = "Result: " + highestSum;
}

EulerProblem8();

<pre id="output">...working...</pre>

Answer 1

There are some obvious items, and then some not-so-obvious ones, that should be addressed.

The most obvious, is this line here:

sum = sum * i;

Really? That's a sum. Don't you mean product?

The next obvious item is that the function should take the number of digits, and the input sequence, as parameters. I would expect a function like:

function eulerProblem8(span, digits) {
    ....

and then the function returns the largest value.

Now, about the algorithm, this is more complicated. There is a way to do it in \$O(n)\$ time complexity. You can scan all the data just once, with a zero-counter, and multiplication and division.

1. scan each position in the input
2. if your sequence will be longer than the span, remove the unneeded digit using division (if the value is non-zero - or decreasing the zero-counter if the value is zero).
3. if the next value in the sequence is zero, increment the zero counter, otherwise include the digit by mutiplying the product.
4. if the new product is larger than previous products, then remember this new maximum
5. report the maximum.

Consider the following....

function eulerProblem8(span, sequence) {

    var follow = -1;
    var zeroes = 0;
    var maxprod = 0;
    var prod = 1;
    var digit;
  
    for (var lead = 0; lead < sequence.length; lead++) {

      // determine the least digit
      if (lead - follow > span) {
        follow = lead - span;
      }

      if (follow >= 0) {
        // remove least digit
        digit = Number(sequence[follow]);
        if (digit == 0) {
          zeroes--;
        } else {
          prod /= digit;
        }
      }

      // include the next digit
      digit = Number(sequence[lead]);
      if (digit == 0) {
        zeroes++;
      } else {
        prod *= digit;
      }

      // if there are no zeros in the sequence, and it exceeds previous...
      if (zeroes == 0 && prod > maxprod) {
        maxprod = prod;
      }
    }

    return maxprod;
}

var amountOfDigits = 13;
var sequence = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"

document.getElementById('result').innerHTML = "Max: " + eulerProblem8(amountOfDigits, sequence);

<p id="result">result</p>
<pre id="debug">unused</pre>

Answer 2

Well, your solution is a so-called "naive" one. Here's why: You are multiplying sequences of numbers containing zeros - which are obviously not going to win in this competition. It is also possible to make the loop somewhat shorter, but ultimately, multiplication here can be replaced by sorting. With long math sorting digits may be faster than multiplying large numbers, so here's my solution:

function pe8() {
    var digits = ['73167176531330624919225119674426574742355349194934',
                  '96983520312774506326239578318016984801869478851843',
                  '85861560789112949495459501737958331952853208805511',
                  '12540698747158523863050715693290963295227443043557',
                  '66896648950445244523161731856403098711121722383113',
                  '62229893423380308135336276614282806444486645238749',
                  '30358907296290491560440772390713810515859307960866',
                  '70172427121883998797908792274921901699720888093776',
                  '65727333001053367881220235421809751254540594752243',
                  '52584907711670556013604839586446706324415722155397',
                  '53697817977846174064955149290862569321978468622482',
                  '83972241375657056057490261407972968652414535100474',
                  '82166370484403199890008895243450658541227588666881',
                  '16427171479924442928230863465674813919123162824586',
                  '17866458359124566529476545682848912883142607690042',
                  '24219022671055626321111109370544217506941658960408',
                  '07198403850962455444362981230987879927244284909188',
                  '84580156166097919133875499200524063689912560717606',
                  '05886116467109405077541002256983155200055935729725',
                  '71636269561882670428252483600823257530420752963450'].join('');
    var candidates = [], i, j, candidate, sorted, result;
    for (i = 0; i < digits.length - 13; i++) {
        for (j = i; j < i + 13; j++) {
            candidate = digits.substr(j, 13);
            if (candidate.indexOf('0') == -1) {
                sorted = candidate.split('');
                sorted.sort();
                sorted.reverse();
                candidates.push({ value: candidate, key: sorted.join('') });
            }
        }
    }
    candidates.sort(function (a, b) {
        return +b.key - a.key;
    });
    result = candidates[0].value.split('').reduce(function (a, b) {
        return (+a) * (+b);
    });
    console.log('result: ' + candidates[0].value + ' = ' + result);
    return candidates.length;
}

Answer 3

I am going to look at the code that you have and see if I can simplify a little bit of it

I am a little confused by this

    for(var c in array) {
        var i = array[c] * 1.0;

        sum = sum * i;
    }

why do you need to have a decimal representation of the value in array[c]? I assume that you are trying to convert the string representation to a number before you try to perform calculations on it, but you don't need a float for multiplication because you should be dealing with whole numbers the entire time.

for (var c in array) {
    product *= parseInt(array[c]);
}

that looks much simpler than what you had, I do not know the performance impact of using parseInt over multiplying into a float, but I would assume that you would take a hit in memory allocation.

---

Your for loop looks odd to me, it resembles a for each loop but you use the variable c as an index to the array and not a value from the array. I have been looking into this, and found that for each ... in is deprecated

The for each...in statement is deprecated as the part of ECMA-357 (E4X) standard. E4X support has been removed, but for each...in will not be disabled and removed because of backward compatibility considerations. Consider using for...of instead. (Please refer to bug 791343.)

for each ... in MDN

There is also an experimental for ... of

I would go further into this, but I have found the documentation on for ... in on MDN and it now makes sense to me.

for future thought, I don't know if for ... of works on Euler problems or if for ... in is still accepted, there is also another way that you could loop through an Array, but I don't know if it will be accepted by Euler either, it's called Array.prototype.forEach()