Ask Experts Questions for FREE Help !
Ask
    Unknown008's Avatar
    Unknown008 Posts: 8,076, Reputation: 723
    Uber Member
     
    #1

    Mar 12, 2011, 10:26 AM
    I was doing one Euler project problem, but stuck...
    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, e.g.. 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!
    nobody123's Avatar
    nobody123 Posts: 9, Reputation: 2
    New 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 [email protected]
    Unknown008's Avatar
    Unknown008 Posts: 8,076, Reputation: 723
    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.
    nobody123's Avatar
    nobody123 Posts: 9, Reputation: 2
    New 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);
    Unknown008's Avatar
    Unknown008 Posts: 8,076, Reputation: 723
    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? :confused:
    nobody123's Avatar
    nobody123 Posts: 9, Reputation: 2
    New 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)

    #! /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);
    nobody123's Avatar
    nobody123 Posts: 9, Reputation: 2
    New 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);
    nobody123's Avatar
    nobody123 Posts: 9, Reputation: 2
    New 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);
    Unknown008's Avatar
    Unknown008 Posts: 8,076, Reputation: 723
    Uber Member
     
    #9

    Apr 12, 2011, 11:39 AM

    Oh my! >.<

    All this time, I thought 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 :)
    Unknown008's Avatar
    Unknown008 Posts: 8,076, Reputation: 723
    Uber Member
     
    #10

    Apr 21, 2011, 11:10 AM

    Okay, I'm late due to being busy :o

    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 :o since I declared $Largest by my.
    nobody123's Avatar
    nobody123 Posts: 9, Reputation: 2
    New Member
     
    #11

    Apr 24, 2011, 12:38 AM

    I am not sure why you are using 10**?? For your
    max and min values.

    Code:
    print "First number:\n";
    my $dig1 = <>;
    chomp($dig1);
    print "Second number:\n";
    my $dig2 = <>;
    chomp($dig2);
    
    my $debug = 'TRUE';
    
    print "dig1 = $dig1  dig2 = $dig2 \n" if ($debug);
    
    my $dig = $dig1 + $dig2;
    my $max1 = 10**$dig1;
    my $max2 = 10**$dig2;
    my $min1 = 10**($dig1-1);
    my $min2 = 10**($dig2-1);
    
    
    print "max1 = $max1  max2 = $max2  min1 = $min1  min2 = $min2 \n" if ($debug);
    
    
    
    my ($A, $B, $P, @digits, $Largest, $Rev, @reverse);
    
    # Add this line to your code.
    $Largest = 0;
    

    Unknown008's Avatar
    Unknown008 Posts: 8,076, Reputation: 723
    Uber Member
     
    #12

    Apr 24, 2011, 09:45 AM

    I changed it so that if three is chosen, the upper bound is 1000 (so, all numbers from 0 to 999 are taken). Then, in the loop, the variable $A will have initial value 1000, and then, min value will be 100 so that after all, the loop tests for all numbers between 100 and 1000. (I figured it's sufficient and that there was no need to check the lower figures, 1-99)

    Okay, I see the problem with the $Largest now, thanks! :)

    Hm... debugging is something I never thought about until now... I think I can something like:

    Code:
    my $debug = 1;
    
    if ($debug == 1)
    {
        print "dig1 = $dig1  dig2 = $dig2 \n";
        print "max1 = $max1  max2 = $max2  min1 = $min1  min2 = $min2 \n";
    }
    That way, I change it at only one entry :)
    nobody123's Avatar
    nobody123 Posts: 9, Reputation: 2
    New Member
     
    #13

    Apr 26, 2011, 11:41 PM
    Is it working the way you want?

    Do you have any other questions?

    You could add this to make debugging easier.

    use Getopt::Std;
    getopts('d', \%opts);
    $debug = 0;
    foreach (keys %opts) {
    $debug = 1 if($_ eq 'd'); # -d set for debugging
    }

    Then when you run the program just add "-d" and $debug will be "1"
    Unknown008's Avatar
    Unknown008 Posts: 8,076, Reputation: 723
    Uber Member
     
    #14

    Apr 27, 2011, 09:27 AM

    Okay, as I told you, I'm completely new to debugging.

    If you could explain the commands you used, that'd make me more at ease :)

    Specifically:
    The module 'Getop::Std'
    Getopts( 'd', \%opts)

    Oh and one thing you made me remember. What's the deal about @_ and $_? I don't think I understand them much :(
    chuym's Avatar
    chuym Posts: 1, Reputation: 1
    New Member
     
    #15

    Jun 11, 2011, 03:51 PM
    Why so complicated?

    Code:
    $largest=0;
    for($i=999;$i>=100;$i--){
        for($j=$i;$j>=100;$j--){
            $result = $i*$j;
            @values = split(undef,$result);
            $size = @values;
            $alrevez = "";
            for($c=$size-1;$c>=0;$c--){
                $alrevez = $alrevez.$values[$c];
            }
            if($result-$alrevez==0 && $result > $largest){
                $largest = $result;
            }
        }
    }
    Unknown008's Avatar
    Unknown008 Posts: 8,076, Reputation: 723
    Uber Member
     
    #16

    Jun 12, 2011, 07:07 AM

    Okay, couple of things I don't understand here:

    @values = split(undef,$result);
    $size = @values;
    $alrevez = $alrevez.$values[$c];

    What do these actually do?

    1. I've never used the split with undef. Does that split the $result into each digit?
    2. You are making $size an array? :confused:
    3. I'm not sure I understand the '.' (dot) function here...

    and if you could answer my last queries:
    What's the deal about @_ and $_?

    How do I use them and why should I use them?

Not your question? Ask your question View similar questions

 

Question Tools Search this Question
Search this Question:

Advanced Search

Add your answer here.


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 questions Search