AdventJS 2023 Day 11 Challenge. Finding index for a Palindrome

The solution to challenge #11 of AdventJS 2023

The solution to the previous challenge

Challenge Description

In Santa's workshop, the elves love puzzles 🧠. This year, they have created a special one: a challenge to form a Christmas palindrome.

A palindrome is a word that reads the same forwards and backward. The elves want to know if it is possible to form a palindrome by making, at most, one exchange of letters.

Create a function getIndexsForPalindrome that receives a string and returns:

If it is already a palindrome, an empty array.
If it is not possible, null.
If a palindrome can be formed with one change, an array with the two positions (indexes) must be swapped to create it.

For example:

getIndexsForPalindrome('anna') // []
getIndexsForPalindrome('abab') // [0, 1]
getIndexsForPalindrome('abac') // null
getIndexsForPalindrome('aaaaaaaa') // []
getIndexsForPalindrome('aaababa') // [1, 3]
getIndexsForPalindrome('caababa') // null

If the palindrome can be formed with different swaps, always return the first one found.

Analysis

In this challenge, our goal is to find a palindrome by swapping two elements of the string and return the indices of those two elements. If a palindrome cannot be found, return an empty array.

Input

Word (word): A string with the word to evaluate.

Output

An array of two elements with the indices to change to find the palindrome.
If it's already a palindrome, return an empty array.
If none of the above conditions are met, return null.

Considerations

If multiple palindromes can be formed, always return the first one found.

Solution

It can be solved by iterating over each element of the string, and within that iteration, iterating again and swapping elements to compare.

Code

/**
 * Returns the indices of characters that need to be reversed in order to make a word a palindrome.
 *
 * @param {string} word - The word to check for palindromic properties.
 * @return {number[] | null} - An array of two indices representing the characters to be reversed, or null if no such indices exist.
 */
function getIndexsForPalindrome(word) {
  // Check if the given word is already a palindrome
  const isPalindrome = (s) => s === s.split("").reverse().join("");

  // If the word is already a palindrome, return an empty array
  if (isPalindrome(word)) {
    return [];
  }

  // Iterate through all possible pairs of indices
  for (let i = 0; i < word.length; i += 1) {
    for (let j = i + 1; j < word.length; j += 1) {
      // Create a new word by swapping the characters at indices i and j
      const newWord =
        word.substring(0, i) +
        word[j] +
        word.substring(i + 1, j) +
        word[i] +
        word.substring(j + 1);

      // If the new word is a palindrome, return the indices i and j
      if (isPalindrome(newWord)) {
        return [i, j];
      }
    }
  }

  // If no such indices exist, return null
  return null;
}

Community Solutions

Solution by iswilljr:

function getIndexsForPalindrome(word: string) {
  const _letters = [...word]
  const palindrome = word === [..._letters].reverse().join('')

  let initial: number[] | null = [null, []][+palindrome]
  let index = 0
  let aux = 1

  const letters = [_letters, []][+palindrome]
  let auxLetters = letters.slice(1)

  for (const letter of letters) {
    for (const auxLetter of auxLetters) {
      const w = [...letters]
      w[index] = auxLetter
      w[aux] = letter

      const isPalindrome = +(w.join('') === w.reverse().join(''))
      const isInitialNull = +(initial == null)
      const isDifferentIndex = +(index !== aux)

      const values = [initial, initial, initial, [index, aux]]

      initial = values[isInitialNull + isDifferentIndex + isPalindrome]
      aux++
    }

    index++
    aux = 1
    auxLetters = [[], auxLetters][+(initial == null)]
  }

  return initial
}

Solution by Achalogy:

function getIndexsForPalindrome(word) {
  let res: any = null
  for (const a of Array.from({ length: word.length }).keys()) {
    for (const b of Array.from({ length: word.length }).keys()) {
      let swapped = [...word]
      let aux = word[a]
      swapped[a] = word[b]
      swapped[b] = aux

      let left = swapped.slice(0, Math.floor(word.length / 2)).join("")
      let right = swapped.slice(Math.ceil(word.length / 2)).reverse().join("")

      res = [
        [
          null
          , [
            []
            , [a, b]
          ][+((a + b) > 0)]
        ][+(left == right)]
        , res
      ][+!!res]
    }
  }
  return res
}

And that was the challenge for December 11th and its solutions. Give it a like if you enjoyed the challenge or the solution! Do you have an alternative solution? Leave it in the comments!

AdventJS 2023: Day 11 Challenge

Comments

AdventJS 2023