Beginner - Project Euler Problem 8

[tomhurst]

Hey - I only started learning PHP a few days ago so forgive me. I've done Codecademy and SoloLearn which teach you the basics, and now looking to practise and learn more.
 
I've had a go at some of the scenarios on Project Euler, and I'm stuck on scenario 8. 
In my head, it looks like my code should work. It's producing a number, but it's the incorrect answer apparently.
 
Can anyone tell me where I'm going wrong? I hope I'm not completely off!
 
This is the problem: https://projecteuler.net/problem=8

 

This is what I've written:

<?php
$string="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
$number=7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450;
$numberCount = strlen($string);
$answer1 = 1;
$answer2 = 0;
$subString;

for($i=0; $i < $numberCount-14; $i++) {
	$answer1 = 1;
	for($j = $i; $j<13; $j++) {
		$subString = substr($string,$j,1);
		$answer1 = $answer1 * $subString;
	
		if ($answer1 > $answer2) {
		$answer2 = $answer1;
	}
	}
}

echo $answer2;

[Jacques1]

You cannot have arbitrarily long integers in PHP (and most other languages). If you want to do arithmetic with big numbers, you need to use strings and a special library.

 

A lot of your variables don't make sense either. It seems you're trying to do variable declarations like in statically typed languages, but PHP is a dynamic scripting language. Variables are created automatically when you first use them.

 

As to the actual problem: You can get rid of the inner loop if you use a “rolling” product which you just multiply by the next number and divide by the first factor (if that factor isn't 0).

 

The if statement is also in the wrong place.

Edited December 2, 2016 by Jacques1

[tomhurst]

Ah - Sorry - New to this still!

I'm moved my if statement out of the inner loop - That does make more sense (I hope that's what you meant!)

 

I'm not fully understanding your rolling product method. Is it incorrect to do this with two loops then?

<?php
$string="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
$numberCount = strlen($string);
$answer2=0;

for($i=0; $i < $numberCount-14; $i++) {
	$answer1 = 1;
	for($j = $i; $j<13; $j++) {
		$subString = substr($string,$j,1);
		$answer1 = $answer1 * $subString;
	}
	if ($answer1 > $answer2) {
	$answer2 = $answer1;
	}
}

echo $answer2;

[Jacques1]

I'm moved my if statement out of the inner loop - That does make more sense (I hope that's what you meant!)

 

Yes.

 

 

 

I'm not fully understanding your rolling product method. Is it incorrect to do this with two loops then?

 

It's not incorrect. I'm simply saying that you can get rid of the inner loop when you realize that only two factors change when you move to the next 13 numbers: The first factor is removed, instead you append the following number as a new factor. All other factors are identical, so you don't have to recaculate the entire product.

[requinix]

Re: large integers

The largest possible result would be thirteen 9s = 2,541,865,828,329, which is beyond the limits of 32-bit PHP but still safe with 64-bit PHP, so as long as you're using a 64-bit build of PHP (eg, PHP 7) then you're okay. Otherwise it'll overflow to floating-point which uses approximations and could thus cause problems for you.

 

Re: the loop

To clarify, Jacques is saying that all you have to care about is the first (oldest) and last (newest) digits. Say you have four digits 7 1 7 6 -> 294: when you get the next number 5 then you can take 294/7 = 42 to factor out the first digit then 42*5 = 210 to factor in the new digit, rather than recalculating the full 1*7*6*5.

 

Oh, and a quick optimization tip: if you encounter a 0 then you can skip forward thirteen places because all the multiplications during then will equal zero.

[tomhurst]

I've kept my loop at the moment, is anyone able to explain what I'm doing wrong? The resulting number I'm getting is incorrect.

 

<?php
$string="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
$numberCount = strlen($string);
$answer2=0;


for($i=0; $i < $numberCount-14; $i++) {
$answer1 = 1;
for($j = $i; $j<=$i+13; $j++) {
if (substr($string,$i,1)==0) { 
$i = $i+13; 
break;
}
else {
$subString = substr($string,$j,1);
$answer1 = $answer1 * $subString;
}
}
if ($answer1 > $answer2) {
$answer2 = $answer1;
}
}


echo $answer2;


?>

[Jacques1]

What is the number you think is incorrect, and what is the number you think is correct?

 

Looking at the code alone, there are several errors:

• The outer loop must run while $i < $numberCount - 12, otherwise you're skipping the last two digits.
• The inner loop must run while $j<= $i + 12, otherwise you're multiplying 14 numbers rather than 13.
• The optimization is wrong. I recommend you first get your code right and then worry about optimizing it.