Nearness and contiguity
Weekly challenge 288 — 23 September 2024
Week 288: 23 Sep 2024
You are given a string, $str
, which is an integer.
Write a script to find out the closest palindrome, not including itself. If there are more than one then return the smallest.
The closest is defined as the absolute difference minimized between two integers.
Example 1 Input: $str = "123" Output: "121" Example 2 Input: $str = "2" Output: "1" There are two closest palindrome "1" and "3". Therefore we return the smallest "1". Example 3 Input: $str = "1400" Output: "1441" Example 4 Input: $str = "1001" Output: "999"
I toyed with a number of clever solutions to this, but concluded that the simplest one was probably fast enough.
My solution therefore is to look at $str - 1
and $str + 1
, and then $str - 2
and $str + 2
, and so
on. The first of these that is palindromic is the answer, and by doing -
before +
, that will yield
the smaller answer as demanded.
In many cases, particularly for large numbers, the answer will follow the pattern:
abcdefghijk → abcdefedcba
but that is not always the closest palindrome: for example the nearest palindrome to 9820189013 is 9820220289 (difference 31276) and not 9820110289 (difference 78724).
As my solution comes up with the answer in under 2 seconds for 12-digit numbers I didn't pursue this further.
#!/usr/bin/perl # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge use v5.26; # The Weekly Challenge - 2024-09-23 use utf8; # Week 288 - task 1 - Closest palindrome use warnings; # Peter Campbell Smith binmode STDOUT, ':utf8'; closest_palindrome(5); closest_palindrome(123); closest_palindrome(1001); closest_palindrome(1400); closest_palindrome(987654321); closest_palindrome(int(rand(10000000000))); sub closest_palindrome { my ($less, $more, $j, $test); # start counting at $str ± 1 $less = $_[0] - 1; $more = $less + 2; # loop outwards from $str for $j (1 .. $less) { $test = reverse($less); last if $test eq $less --; $test = reverse($more); last if $test eq $more ++; } say qq[\nInput: \$str = '$_[0]']; say qq[Output: '$test']; }
Input: $str = '5' Output: '4' Input: $str = '123' Output: '121' Input: $str = '1001' Output: '999' Input: $str = '1400' Output: '1441' Input: $str = '987654321' Output: '987656789' Input: $str = '9610784061' Output: '9610770169'
Any content of this website which has been created by Peter Campbell Smith is in the public domain