Ask Experts Questions for FREE Help !
Ask

I was doing one Euler project problem, but stuck...

Asked Mar 12, 2011, 09:26 AM — 15 Answers
Okay, as the title says, I'm stuck. I got a program and from what I know, it is supposed to work, but fact is... it doesn't. I don't know what might be wrong it it, for is seems good to me.

The question is to find the largest palindrome number (one which can be read in either directions, eg. 323, 4224, 510015, etc) which is formed by the product of two 3-digit numbers. Here's my coding:

Code:
$L = 1000;

for ($A = 100 ; $A < $L ; $A++)
{
	for ($B = 100 ; $B < $L ; $B++)
	{
		$P = $A*$B;
		if 
                ( 
                   substr($P, 0, 1) == substr($P, (length($P)-1), (length($P))) && 
		   substr($P, 1, 2) == substr($P, (length($P)-2), (length($P)-1)) && 
		   substr($P, 2, 3) == substr($P, (length($P)-3), (length($P)-2)) && 
	           length($P) == 6
                )
		{
			print $A, " x " , $B, " = ", $P, "\n";
			push @array, $P;
		}
	}
}

$max = $array[0];

foreach $i (@array[1..$#array])
{
	if ($i > $max)
	{
		$max = $i;
	}
}

print "The largest palindrome is " , $max , "\n";
Or through pastebin: http://pastebin.com/iyGAJVKx

I inserted the line:

print $A, " x " , $B, " = ", $P, "\n";

To check all the incoming numbers as an attempt to find the problem. When I put only the first condition, that is:

substr($P, 0, 1) == substr($P, (length($P)-1), (length($P)))

I get palindromes and other non-palindromic numbers, of course, and the answer is in the lot of numbers, that is 906609.

However, with the full conditions, it doesn't give me the required palindrome. For a certain reason, all it gives me are numbers with all the same digits and the largest turns out to be 888888.

Any help in understanding what's wrong?
Thanks!

15 Answers
nobody123's Avatar
nobody123 Posts: 9, Reputation: 15
Junior Member
 
#2

Apr 8, 2011, 12:16 AM
First off, instead of starting with 100 x 100, I would start with 999 x 999 and work my way down.

for ($A = 999 ; $A >= 100 ; $A--)

Secondly, I think the third argument of your substr command should always be 1.
You want to compare one char with one char.

If you still need an answer to this problem, you can E-mail me at maps@cstevens.org
Helpful
Unknown008's Avatar
Unknown008 Posts: 8,147, Reputation: 3745
Uber Member
 
#3

Apr 8, 2011, 07:32 AM
What do you mean by "the third argument of your substr command should always be 1."

Could you write the code for that part?

About sending emails, sorry, this is not how forums work, everything is kept in the thread.

Also, I want the code to be able to find the palindrome for any number of digits and conditions that I want with minimal editing. Since I posted this, I leaned a few more things and I think that maybe a regex would speed up things, if I get to find out how to do it.
Helpful
nobody123's Avatar
nobody123 Posts: 9, Reputation: 15
Junior Member
 
#4

Apr 9, 2011, 10:41 PM
Try this. This is a more efficient way to do it.
If you want to see all the palindromes, then comment out this line:
next if ($P <= $max) ;


#! /usr/bin/perl -w

Use strict;
My ($L, $A, $B, $P, $max, $i );

$L = 1000;
$max = 0;

For ($A = 999 ; $A >= 100 ; $A--)
{
for ($B = 999 ; $B >= 100 ; $B--)
{
$P = $A*$B;
next if ($P <= $max) ;
next if (length($P) != 6) ;
if
(
substr($P, 0, 1) eq substr($P, (length($P)-1), 1) &&
substr($P, 1, 1) eq substr($P, (length($P)-2), 1) &&
substr($P, 2, 1) eq substr($P, (length($P)-3), 1)
)
{
print $A, " x " , $B, " = ", $P, "\n";
if ($P > $max) { $max = $P; }
}
}
}


Print "The largest palindrome is " , $max , "\n";

Exit(0);
Helpful  (1)
Unknown008's Avatar
Unknown008 Posts: 8,147, Reputation: 3745
Uber Member
 
#5

Apr 10, 2011, 10:08 AM
Okay, this one works, I just can't understand the substr part.

What does "substr($P, 1, 1)" mean exactly?

I know that if I have a string, $P = 123456

Then, substr($P, 0, 1) means the program is picking the first digit (between 'position' 0 and 1)

But by using that logic... Substr($P, 1, 1) would mean the digit(s) between the 'position' 1 and 1?
Helpful
nobody123's Avatar
nobody123 Posts: 9, Reputation: 15
Junior Member
 
#6

Apr 11, 2011, 11:11 PM
substr EXPR,OFFSET,LENGTH

1. My $s = "The black cat climbed the green tree";
2. My $color = substr $s, 4, 5; # black
3. My $middle = substr $s, 4, -11; # black cat climbed the
4. My $end = substr $s, 14; # climbed the green tree
5. My $tail = substr $s, -4; # tree
6. My $z = substr $s, -4, 2; # tr


Substr($P, 0, 1) eq substr($P, (length($P)-1), 1) &&
Compare the first char to the last char.

Substr($P, 1, 1) eq substr($P, (length($P)-2), 1) &&
Compare the second char to the second to last char.


Here is a solution that allows you to change the number of
Digits and the range of numbers. (Change High, Low, and Digits)

Quote:
#! /usr/bin/perl -w

Use strict;
My ($A, $B, $P, $Max, $i );

My $High = 9999; # Highest number
My $Low = 1000; # Lowest number
My $Digits = 8; # Number of digits required.


$Max = 0;

For ($A = $High ; $A >= $Low ; $A--)
{
for ($B = $High ; $B >= $Low ; $B--)
{
$P = $A*$B;
# Don't need to check for palindrome, if this is smaller than the Max.
next if ($P <= $Max) ;
# Don't need to check not the correct number of digits.
next if (length($P) != $Digits) ;

# Check for palindrome
for ($i = 0; $i <= ($Digits/2) ; $i++ ) {
last if ( substr($P, $i, 1) ne substr($P, (length($P)-($i+1)), 1) );
if ($i == ($Digits/2)) {
$Max = $P;
print $A, " x " , $B, " = ", $P, "\n";
}
}


}
}

Print "The largest palindrome is " , $Max , "\n";

Exit(0);
Helpful
nobody123's Avatar
nobody123 Posts: 9, Reputation: 15
Junior Member
 
#7

Apr 11, 2011, 11:14 PM
This should look better. I didn't know there was a code button.
I am new at askmehelpdesk.com

Code:
#! /usr/bin/perl -w

use strict;
my ($A, $B, $P, $Max, $i );

my $High = 9999;   # Highest number
my $Low  = 1000;   # Lowest  number
my $Digits = 8;    # Number of digits required.


$Max = 0;

for ($A = $High ; $A >= $Low ; $A--)
{
	for ($B = $High ; $B >= $Low ; $B--)
	{
		$P = $A*$B;
                # Don't need to check for palindrome, if this is smaller than the Max.
		next if ($P <= $Max) ;
                # Don't need to check not the correct number of digits.
		next if (length($P) != $Digits) ;

                # Check for palindrome
                for ($i = 0; $i <= ($Digits/2) ; $i++ ) { 
		   last if ( substr($P, $i, 1) ne substr($P, (length($P)-($i+1)), 1) );
		   if ($i == ($Digits/2)) {
		        $Max = $P;
		        print $A, " x " , $B, " = ", $P, "\n";
		   }
		}
		
		
	}
}

print "The largest palindrome is " , $Max , "\n";

exit(0);
Helpful
nobody123's Avatar
nobody123 Posts: 9, Reputation: 15
Junior Member
 
#8

Apr 11, 2011, 11:39 PM
The last one did not work for an odd number of digits.
This one works well. I think it is pretty cool.

Code:
#! /usr/bin/perl -w

use strict;
my ($A, $B, $P, $Max, $i );

my $High = 6000;   # Highest number
my $Low  = 1000;   # Lowest  number
my $Digits = 8;    # Number of digits required.

$Max = 0;

for ($A = $High ; $A >= $Low ; $A--)
{
	for ($B = $High ; $B >= $Low ; $B--)
	{
		$P = $A*$B;

                # Don't need to check for palindrome, if this is smaller than the Max.
#		next if ($P <= $Max) ;
                # Don't need to check for palindrome, if this is not the correct number of digits.
		next if (length($P) != $Digits) ;

                # Check for palindrome
                for ($i = 0; $i <= int($Digits/2) ; $i++ ) { 
		   last if ( substr($P, $i, 1) ne substr($P, (length($P)-($i+1)), 1) );
		   # if this is true,  then it is a palindrome
		   if ($i == int($Digits/2)) {
		        if ($Max < $P) { $Max = $P; }
		        print $A, " x " , $B, " = ", $P, "\n";
		   }
		}
		
		
	}
}

print "The largest palindrome is " , $Max , "\n";

exit(0);
Helpful
Unknown008's Avatar
Unknown008 Posts: 8,147, Reputation: 3745
Uber Member
 
#9

Apr 12, 2011, 11:39 AM
Oh my! >.<

All this time, I thought the the third argument is the 'limit'. Thanks for clearing it up!

Unfortunately, I couldn't give you another agree.

Okay, I'll try to make it more user friendly now, for example, using the chomp function and let the program do the work etc. Okay, I will need some time to write the program down and post it, as I don't have much time right now.

Thanks for taking your time
Helpful
Unknown008's Avatar
Unknown008 Posts: 8,147, Reputation: 3745
Uber Member
 
#10

Apr 21, 2011, 11:10 AM

Okay, I'm late due to being busy

Code:
use strict;

print "The goal is to find the largest palindrome made from the product of two numbers.\n
Enter the number of digits for the two numbers. \n";

print "First number:\n";
my $dig1 = <>;
chomp($dig1);
print "Second number:\n";
my $dig2 = <>;
chomp($dig2);

my $dig = $dig1 + $dig2;
my $max1 = 10**$dig1;
my $max2 = 10**$dig2;
my $min1 = 10**($dig1-1);
my $min2 = 10**($dig2-1);

my ($A, $B, $P, @digits, $Largest, $Rev, @reverse);

for ($A = $max1 ; $A >= $min1 ; $A--)
{
	for ($B = $max2 ; $B >= $min2 ; $B--)
	{
		$P = $A*$B;
		if ( $P < $Largest || length($P) != $dig) {next;}

		@digits = split(//, $P);
		@reverse = reverse(@digits);
		$Rev = join("",@reverse);
		if ( $P == $Rev) { $Largest = $P; }
	}
}

print "The largest palindrome is " , $Largest , "\n";
I don't know something though... I'm used to add

use warnings;

but then, there's an error (which doesn't affect the result) saying:

Use of uninitialized value $Largest in numeric lt (<) at Euler 4'.pl line 26, <> line 2.

I'm not sure what that means since I declared $Largest by my.
Helpful

Not your question? Ask your question View similar questions

 
Thread Tools Search this Thread
Search this Thread:

Advanced Search

Add your answer here.

Remove Text Formatting

Undo
Redo
 
Decrease Size
Increase Size
Bold
Italic
Underline
Align Left
Align Center
Align Right
Ordered List
Unordered List
Decrease Indent
Increase Indent
Insert Email Link
Wrap [QUOTE] tags around selected text
Wrap [CODE] tags around selected text
Wrap [HTML] tags around selected text
Wrap [PHP] tags around selected text
Wrap [YOUTUBE] tags around selected text
Notification Type:



Check out some similar questions!

Smallest euler circuit [ 1 Answers ]

Hi:) I was wondering if there's a formula or an algorithm for how to find the shortest/smallest path in a vertex-edge graph. Like if you made a vertex-edge for linking network hubs together. The verticies= hubs and the edges=amount of cable. How would I find the smallest amount of cable needed....


View more Perl questions Search