Cartalk Puzzler: The Palindromic Odometer

[MillerH]

Howdy All,

There yet another Cartalk Puzzler that begs for a programmatic solution for y'all to dig your teeth into.

It shouldn't take very much code to do this, so if you would post your code in [ignore]

[COLOR=WHITE WHITE][/COLOR]

[/ignore] tags, we'll at least get to see the differences in our coding styles.

As an additional problem, you could try golfing it, but that goes against my own sensibilities

Enjoy,
- Miller

# Highlight text to reveal my solution:
[COLOR=white white]
use strict;

# Palindrome Rules
# X: substr(S, -4)
# X+1: substr(S, -5)
# X+2: substr(S, -5, 4)
# X+3: S

for my $i (1..999999) {
	if (length($i+3) == 6
		&& is_palidrome(substr($i, -4))
		&& is_palidrome(substr($i+1, -5))
		&& is_palidrome(substr($i+2, -5, 1))
		&& is_palidrome($i+3)
	) {
		print $i, "\n";
	}
}

sub is_palidrome {
	my ($num) = @_;

	my $len = 1 + int(length($num) / 2);

	my $x = substr($num, 0, $len);
	my $y = reverse substr($num, -$len);

	return $x eq $y;
}[/COLOR]

 

[prex1]

There is a small error in your code (easily corrected: [tt] && is_palidrome(substr($i+2, -5, 1))[/tt] should be [tt] && is_palidrome(substr($i+2, -5, -1))[/tt]); also you don't test the 6 digit groups starting with '0' (not very important, as there are no solutions there).
Below is my tentative: to achieve a better efficiency I test only the 1000 palindromic 6 digit numbers (instead of your 1000000 numbers: the execution time is noticeably shorter). Also the sub is possibly more efficient, though I'm not sure of that.

use strict;
my$num;
for my$i(0..9){
  for my$j(0..9){
    for my$k(0..9){
      $num="$i$j$k$k$j$i";
      print$num,"\n" if is_palindrome(substr(sprintf("%06d",--$num),1,4))
      && is_palindrome(substr(sprintf("%06d",--$num),1))
      && is_palindrome(substr(sprintf("%06d",--$num),2));
    }
  }
}
sub is_palindrome {
  my($num)=@_;
  my$j=-1;
  for(my$i=0;$i<=length($num)/2;$i++){
    return 0 unless substr($num,$i,1)eq substr($num,$j,1);
    $j--;
  }
  return 1;
}

Something more for the sake of efficiency could still be done, avoiding the [tt]sprintf[/tt]'s, but that will suffice.
I'm not sure that the original puzzle was about finding a programmatic solution: the real challenge is to find a way of determining the two solutions by a logic reasoning.

Franco

http://www.xcalcs.com

: Online tools for structural design

http://www.megamag.it

: Magnetic brakes for fun rides

http://www.levitans.com

: Air bearing pads

 

[KevinADC]

Your program also does not seem to find the answer to the question, Franco. Since the answer is not the objective here, I will post a possible answer, the series of miles on the odometer is:

199999 <- first four (five really) are palindromic
+    1
------
200000 <- first five are palindromic
+    1
------
200001 <- middle four are palindromic
+    1
------
200002 <- all six are palindromic

This is actually a problem where intuition is good at solving the problem because it's a sort of trick question. There is no logcical formula you can apply that I am aware of.

------------------------------------------
- Kevin, perl coder unexceptional!

 

[prex1]

It works for me, and there are two solutions: one is yours, Kevin (with my compliments), the other one is left for others to take the challenge.
I think that some logical way of reasoning can help narrow down the solution, if not find it: will try.

Franco

http://www.xcalcs.com

: Online tools for structural design

http://www.megamag.it

: Magnetic brakes for fun rides

http://www.levitans.com

: Air bearing pads

 

[ishnid]

Here's what I had come up with.

[COLOR=WHITE WHITE]
#!/usr/bin/perl
use strict;

for ( 1 .. 999996 ) {

   if ( is_palindrome( substr( sprintf( '%06d', $_ ), 2 ) ) &&
        is_palindrome( substr( sprintf( '%06d', $_ + 1 ), 1 ) ) &&
        is_palindrome( substr( sprintf( '%06d', $_ + 2 ), 1, 4 ) ) &&
        is_palindrome( sprintf( '%06d', $_ + 3 ) ) ) {
      printf "Terry may have seen %06d\n", $_;
   }
}

sub is_palindrome {
   my @digits = split //, $_[0];
   for ( 0 .. @digits / 2 ) {
      return 0 if $digits[$_] != $digits[$#digits-$_];
   }
   return 1;
}[/COLOR]

 

[wxb2744]

How about this?

[COLOR=WHITE WHITE]
for ( 99999 .. 999996 ){
	print "$_\n" if	is_palindrome( $_, 2, 4 ) 
		and is_palindrome( $_ + 1, 1, 5 ) 
		and is_palindrome( $_ + 2, 1, 4 )
		and is_palindrome( $_ + 3, 0, 6 );
}

sub is_palindrome {
	( $number, $start, $len ) = @_;
	$str = sprintf("%06d", $number );
	return substr( $str, $start, $len ) eq reverse( substr( $str, $start, $len ) );
}
[/COLOR]

 

[KevinADC]

It works for me, and there are two solutions: one is yours, Kevin (with my compliments), the other one is left for others to take the challenge.

Yes it does, I was expecting to see a different output but your code does print the beginning pattern for two solutions.

------------------------------------------
- Kevin, perl coder unexceptional!

 

[prex1]

Actually the unique solution is 198888: this because the other one given by Kevin (199999) has the last five digits palindromic instead of only four, as stated in the puzzle.
This is a tentative to solve it logically:
1)The last digit may only be 7,8 or 9, otherwise the only change in the number would be in the last digit, and this clearly conflicts with the conditions
2)The case 7 is soon eliminated by a short inspection, based on arguments similar to the ones below, but too long to be detailed here
3)Now let's observe the second number (last 5 palindromic) and the third one (middle 4 palindromic): it is clear that either the 5 last digits are the same in the second number, or they are 98889, so that in the third number this becomes 98890
4)In the first case under 3, the 5 equal digits may only be zeroes, so that the starting number has 9999 (palindrome) in the last 4 positions; it is easy to conclude that the number corresponding to this is 199999 (simply observe that the the 4th combination is 200002)
5)In the second case under 3 it is immediately clear that the starting number is 198888
6)So we are left with only two possibilities, and one of them must be cancelled as said above.

Easy to do when you already know the solution...

Franco

http://www.xcalcs.com

: Online tools for structural design

http://www.megamag.it

: Magnetic brakes for fun rides

http://www.levitans.com

: Air bearing pads