Palindrome Descendant (Code Challenge)
- Page Owner: Not Set
- Last Reviewed: 2019-08-30
Everyone was asking for a harder challenge, So we'll up the difficulty a little bit.
Palindrome Decendant
A number may not be a palindrome, but it's descendant can be. A number's direct child is created by summing each pair of adjacent digits to create the digits of the next number.
For instance, 123312 is not a palindrome, but it's next child 363 is, where: 3 = 1 + 2; 6 = 3 + 3; 3 = 1 + 2.
Create a function that returns true if the number itself is a palindrome or any of its descendants down to 2 digits. Since a 1 digit number is effectively a palindrome, return false.
Examples
palindromedescendant(11211230) ➞ true
// 11211230 ➞ 2333 ➞ 56 ➞ 11
palindromeDescendant(13001120) ➞ true
// 13001120 ➞ 4022 ➞ 44
palindromeDescendant(23336014) ➞ true
// 23336014 ➞ 5665
palindromeDescendant(11) ➞ true
// Number itself is a palindrome
Notes
- Numbers will always have an even number of digits.
- If a number becomes odd, and is not a palindrome, it will return false.
Tests
palindromeDescendant(11211230) == true
palindromeDescendant(13001120) == true
palindromeDescendant(23336014) == true
palindromeDescendant(11) == true
palindromeDescendant(1122) == false
palindromeDescendant(332233) == true
palindromeDescendant(10210112) == true
palindromeDescendant(9735) == false
palindromeDescendant(97358817) == false
Additional Posts
Another golfy solve with JS reduce. 253 characters including newlines.
p = a => {
let b = a.toString();
return b.length % 2 == 1 ? false : isP(b) || p(b.split("").reduce((a, c, i) =>
(i % 2 == 0) ? (a += (+(c) + +(b[i + 1])).toString()) : a, ""));
}
isP = x => x == x.toString().split("").reverse().join("");
console.log(p(11211230) == true)
console.log(p(13001120) == true)
console.log(p(23336014) == true)
console.log(p(11) == true)
console.log(p(1122) == false)
console.log(p(332233) == true)
console.log(p(10210112) == true)
console.log(p(9735) == false)
console.log(p(97358817) == false)
I hope you're ready for some barf, but its functional:
def isPal(ori):
if(str(ori)==str(ori)[::-1]):
return True
return False
def palindromeDescendant(s):
if isPal(s) and len(str(s))>=2:
return True
if((len(str(s)))%2!=0):
return False
else:
newP = []
for i in range(1,(len(str(s))/2)+1):
tmp = str(s)[(i*2)-2:i*2]
newP.append(int(tmp[1:]) + int(tmp[:1]))
g=[str(i) for i in newP]
return palindromeDescendant(int("".join(g)))
print(palindromeDescendant(11211230))
print(palindromeDescendant(13001120))
print(palindromeDescendant(23336014))
print(palindromeDescendant(11))
print(palindromeDescendant(1122))
print(palindromeDescendant(332233))
print(palindromeDescendant(10210112))
print(palindromeDescendant(9735))
print(palindromeDescendant(97358817))
Here's my extremely verbose take on it. I was going for clarity, but also trying to not represent numbers as strings. I still cheated and used a string to do the palindrome detection, though. I'm open to suggestions on how to detect a palindrome without conversion to a string (or other use of a list).
Note: the spec isn't clear what to do when deriving and 2 digits add up to more than 9. I think my take probably handles it wrong, but still gets the correct results... so.. ¯\_(ツ)_/¯
// The check for palindromic can return 3 possible values:
#[derive(PartialEq)]
pub enum PalindromeState {
/// This is not a palindrome, but could potentially be derived to be one.
NotInCurrentIteration,
/// This is not a palindrome and cannot be derived.
NotAPalindrome,
/// This is a palindrome
Palindrome
}
pub fn derive(number:u32) -> u32 {
// Iterate through the digits, from the smallest place to the largest place.
// `last_digit` tracks the last time we've seen a digit. If it's None, then we
// just track it. If it's Some, then we add them to the final_result list.
// Basically `Option<T>` has 2 states, and we need to combine 2 digits, so we're
// using the states to do that.
// Using a linked list here so we can push to the front of the list efficiently.
let mut last_digit:Option<u32> = Option::None;
let mut final_result:u32 = 0;
let mut remaining_digits:u32 = number.clone();
while remaining_digits > 0 {
let current_digit : u32 = remaining_digits % 10;
// Each iteration we flip last_digit from Some(x) to None (and back)
last_digit = match last_digit {
Some(value) => {
final_result = (final_result * 10) + (value + current_digit);
None
},
None => Some(current_digit)
};
remaining_digits = remaining_digits / 10;
}
// Sanity check. `last_digit` should fip an even number of times.
// If not, something went terribly wrong.
match last_digit {
Some(_) => panic!("This should never happen"),
_ => {}
};
final_result
}
pub fn is_palindrome(number:u32) -> PalindromeState {
// Convert to a string representation, not super efficient, but makes it simple to reason about
let number_as_string = number.to_string();
// If the string representation is an uneven length, we don't consider it a palindrome and it cannot be derived.
let string_length = number_as_string.len();
if string_length % 2 != 0 {
return PalindromeState::NotAPalindrome;
}
// Create 2 iterators, one going forward, one going backwards. Only take
// half the length of the string (no need to compare beyond that)
let half = string_length / 2;
let forward_iterator = number_as_string.chars().take(half);
let backwards_iterator = number_as_string.chars().rev().take(half);
// If they're equal, it's a palindrome, otherwise it might be possible to derive to a palindrome.
match forward_iterator.eq(backwards_iterator) {
true => PalindromeState::Palindrome,
false => PalindromeState::NotInCurrentIteration
}
}
pub fn test_for_palindrome(number:u32) -> bool {
// Using tail-recursion here, so in theory, the compiler should be able to rewrite this
// as a loop.
match is_palindrome(number) {
PalindromeState::Palindrome => true,
PalindromeState::NotAPalindrome => false,
PalindromeState::NotInCurrentIteration => test_for_palindrome(derive(number))
}
}
pub fn execute() {
assert_eq!(test_for_palindrome(11211230), true);
assert_eq!(test_for_palindrome(13001120), true);
assert_eq!(test_for_palindrome(23336014), true);
assert_eq!(test_for_palindrome(11), true);
assert_eq!(test_for_palindrome(1122), false);
assert_eq!(test_for_palindrome(332233), true);
assert_eq!(test_for_palindrome(10210112), true);
assert_eq!(test_for_palindrome(9735), false);
assert_eq!(test_for_palindrome(97358817), false);
println!("OK");
}
My code golf game could use some work. Sample output at the end.
using System;
using System.Collections.Generic;
public class Program
{
public static void Main ()
{
var testInput = new List<string>{
"11211230",
"13001120",
"23336014",
"11",
"1122",
"332233",
"10210112",
"9735",
"97358817"
};
foreach (var input in testInput){
var output = CheckForPalindrome (input);
Console.WriteLine (output + "\n\n");
}
}
public static string CheckForPalindrome (string input)
{
bool longerThanOne = true;
string output = "";
while (longerThanOne)
{
var firstHalf = input.Substring (0, input.Length / 2);
var charArray = input.ToCharArray ();
Array.Reverse (charArray);
var reversedInput = new string (charArray);
var secondHalf = reversedInput.Substring(0, reversedInput.Length / 2);
if (firstHalf.Equals(secondHalf))
{
output += input + " is a palindrome.\n";
} else {
output += input + " is not a palindrome.\n";
}
input = GetChild(input);
longerThanOne = input.Length >= 2;
}
return output;
}
public static string GetChild (string input)
{
var startingLength = input.Length;
List<int> child = new List<int> ();
for (var x = 0; x < startingLength / 2; x++) {
if (input.Length > 0){
child.Add(PopOffLastTwo (input));
input = input.Substring(0, input.Length - 2);
}
}
child.Reverse ();
string childString = "";
foreach (int number in child) {
childString += number.ToString ();
}
return childString;
}
public static int PopOffLastTwo (string input)
{
int firstNumber;
int secondNumber;
firstNumber = int.Parse(input) % 10;
secondNumber = int.Parse(input.Substring (0, input.Length - 1)) % 10;
return (firstNumber + secondNumber);
}
}
Testing 11211230:
11211230 is not a palindrome. 2333 is not a palindrome. 56 is not a palindrome. 11 is a palindrome.
Testing 13001120:
13001120 is not a palindrome. 4022 is not a palindrome. 44 is a palindrome.
Testing 23336014:
23336014 is not a palindrome. 5665 is a palindrome. 1111 is a palindrome. 22 is a palindrome.
Testing 11:
11 is a palindrome.
Testing 1122:
1122 is not a palindrome. 24 is not a palindrome.
Testing 332233:
332233 is a palindrome. 646 is a palindrome. 10 is not a palindrome.
Testing 10210112:
10210112 is not a palindrome. 1313 is not a palindrome. 44 is a palindrome.
Testing 9735:
9735 is not a palindrome. 168 is not a palindrome. 14 is not a palindrome.
Testing 97358817:
97358817 is not a palindrome. 168168 is not a palindrome. 7914 is not a palindrome. 165 is not a palindrome. 11 is a palindrome.