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.