Jump to content

Beginner - Project Euler Problem 8


tomhurst

Recommended Posts

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;
Link to comment
Share on other sites

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 by Jacques1
Link to comment
Share on other sites

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;
Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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;


?>
Link to comment
Share on other sites

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.
Link to comment
Share on other sites

This thread is more than a year old. Please don't revive it unless you have something important to add.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.