Daily Challenge #60 - Find the Missing Letter

Write a method that takes an array of consecutive (increasing) letters as input and that returns the missing letter in the array.

You will always get a valid array. And it will be always exactly one letter be missing. The length of the array will always be at least 2.
The array will always contain letters in only one case.

Example:

Good luck!

---

Today's challenge comes from user5036852 onCodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email [e-mail] with your suggestions!

Comments

[Daniel Sellers]

This makes an assumption about where the missing letter is in the string that isn't valid for all the test cases?

It returns incorrectly for both test cases that they propose in the problem. You're on the right track but have a little bit more work to do.

[Cagatay Kaya]

Thanks for the heads up. I did not get the challenge right and posted a wrong answer. Here is the correct one, I hope :)

missingL = input => {
  const alphabet = [
    "a","b","c","d","e","f","g",
    "h","i","j","k","l","m","n",
    "o","p","q","r","s","t","u",
    "v","w","x","y","z"
  ];

  const alphabetUp = alphabet.map(item => item.toUpperCase());

  input[0] == input[0].toUpperCase()
    ? alphabet.splice(0, 26, ...alphabetUp)
    : alphabet;
  const compareArray = alphabet.slice(
    alphabet.indexOf(input[0]),
    alphabet.indexOf(alphabet[alphabet.indexOf(input[0]) + input.length])
  );

  return compareArray.filter(item => !input.includes(item));
};

[Daniel Sellers]

Here is another JS version

const LETTERS = [
  'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 
  'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 
  'x', 'y', 'z'
];

const findMissing = ltrArr => {
  const offset = LETTERS.findIndex(l => l === ltrArr[0].toLowerCase());
  const index = ltrArr.findIndex((l, i) => l.toLowerCase() !== LETTERS[offset + i]);

  return ltrArr[0].toLowerCase() === ltrArr[0]
    ? LETTERS[index + offset]
    : LETTERS[index + offset].toUpperCase();
};

The LETTERS constant could be inside the findMissing function... but that seemed less reusable. Covers all the test cases and should only iterate the arrays fully if there is no missing character to be found. So should be pretty fast as well.

[Marco Slooten]

Nice challenge, I tried doing it in JS with an array.reduce and character codes. I think it works well enough! I don't think the arr.splice(1) is really clean though, so perhaps a traditional loop would be better.

const returnMissingLetter = letters => {
  return letters.reduce((acc, curr, i, arr) => {
    if (curr.charCodeAt() - acc.charCodeAt() === 1) {
      return curr;
    }
    arr.splice(1);
    return String.fromCharCode(acc.charCodeAt() + 1);
  });
};

[Victor Nascimento]

const hasLargerDiff = (num, index, list) => list[index + 1] - num > 1;
const toCharCode = char => char.charCodeAt(0);

function findMissingLetter(sequence) {
  const missingCode = sequence
    .map(toCharCode)
    .find(hasLargerDiff) + 1;

  return String.fromCharCode(missingCode)
}

[Ricardo Delgado]

This my solution, I also tried to account for the possibility that there wasn't just one letter missing:

checkChar = array => {
    const missing = []

    for(let i = 1; i < array.length; i++) {
        var firstLet = array[i].charCodeAt(0)
        var prevLet = array[i - 1].charCodeAt(0)
        if (firstLet - prevLet > 1) missing.push([firstLet, prevLet])
    }

    return missing.map(letterArray => {
        const letters = []

        for(let i = letterArray[1] + 1, c = 0; c < (letterArray[0] - letterArray[1] - 1); c++) {
            letters.push(String.fromCharCode(i))
            i++
        }
        return letters
    })[0]
}

[Donald Feury]

Time to Go find the missing letter!

missing_letter.go

package find

// MissingLetter indicates what the missing character is in a ordered sequence of characters
func MissingLetter(chars []rune) rune {
    var last int

    for _, r := range chars {
        if last != 0 && int(r)-last > 1 {
            return rune(r - 1)
        }
        last = int(r)
    }

    return rune(last)
}

missing_letter_test.go

package find

import "testing"

type testCase struct {
    description string
    input       []rune
    expected    rune
}

func TestMissingLetter(t *testing.T) {
    testCases := []testCase{
        {
            "two characters",
            []rune{'A', 'C'},
            'B',
        },
        {
            "dev-to example one",
            []rune{'a', 'b', 'c', 'd', 'f'},
            'e',
        },
        {
            "dev-to example two",
            []rune{'O', 'Q', 'R', 'S'},
            'P',
        },
    }

    for _, test := range testCases {
        if result := MissingLetter(test.input); result != test.expected {
            t.Fatalf("FAIL: %s - MissingLetter(%+v): %v - expected %v", test.description, test.input, result, test.expected)
        }
        t.Logf("PASS: %s", test.description)
    }
}

[Chris Achard]

Here it is in JS, uses charCodeAt and fromCharCode to convert from char to ASCII number, then looks for the number difference of 2 (missing number in between them):

const missing = arr => {
  for(let i in arr) {
    const letter = arr[i]
    const next = arr[Number(i) + 1]
    if(next.charCodeAt(0) - letter.charCodeAt(0) === 2
    ) {
      return String.fromCharCode(arr[i].charCodeAt(0) + 1)
    }
  }
}

[Kamaal Aboothalib]

Almost identical but I try with the functional approach and typescript
checks any number of chars instead of one.

const getDiff = (a:number, b: number):number => b - a
const getGap = (a:number, maxDiff:number = 1):number => a - maxDiff
const fillGaps = (a:number, gap:number):string[] => gap > 0 ? [...(Array(gap).fill(0))].map((_, e) => e + 1 )
    .map(i => i + a )
    .map(i => String.fromCharCode(i)) : []

const missing = (input:string[]): string => {
  return input.reduce((a, b, index, array) => {
    const positionIndex = `${b}`.charCodeAt(0)
    const nextPositionIndex:number = index + 1 < array.length ? array[index+1].charCodeAt(0) : positionIndex
    const gap = getGap(getDiff(positionIndex, nextPositionIndex), 1)
    const gaps = fillGaps(positionIndex, gap)
    return [...a,...gaps]
  }, []).join(', ')
}

codesandbox.io/s/quirky-davinci-sk826

[Amin]

My take at the challenge written in TypeScript this time and using a recursive solution!

"use strict";

type Letters = string[];
type LetterCode = number | undefined;
type MissingLetter = string | false;

function missingLetter(
    letters: Letters,
    nextLetterCode: LetterCode = undefined
): MissingLetter {
    if (letters.length === 0) {
        return false;
    }

    if (nextLetterCode === undefined) {
        nextLetterCode = letters[0].charCodeAt(0);
    }

    const [ letter, ...rest ]: Letters = letters;
    const letterCode: LetterCode = letter.charCodeAt(0);

    if (letterCode !== nextLetterCode) {
        return String.fromCharCode(letterCode - 1);
    }

    return missingLetter(rest, nextLetterCode + 1);
}

console.log(missingLetter(["a", "b", "c", "d", "f"])); // "e"
console.log(missingLetter(["O", "Q", "R", "S"])); // "P"
console.log(missingLetter(["a", "b", "c", "d", "e", "f"])); // false

I haven't done that much of a test so do not hesitate to tell me if I'm wrong. I also have returned false whether when there was no missing letters. I guess my solution will fail when the first letter is at the beginning or at the end of the array. The source-code with the playground is available here!

[Amin]

I also did use my algorithm in Elm. Here is the source-code for the inner logic function.

getMissingLetter : List Char -> Char -> Maybe Char
getMissingLetter letters nextCharacter =
    case letters of
        [] ->
            Nothing

        letter :: rest ->
            let
                characterCode =
                    Char.toCode letter

                nextCharacterCode =
                    Char.toCode nextCharacter
            in
            if characterCode /= nextCharacterCode then
                Just nextCharacter

            else
                getMissingLetter rest <| Char.fromCode <| nextCharacterCode + 1

I bet there could be a way to use it in Haskell or PureScript as well, but I'm more confortable using Elm for now.

And the testing is of course available here on Ellie App.

[willsmart]

A quicky using reduce in JS

First up it converts the array of letters to an array of char codes.
It then uses reduce to find the 2-code gap, and return the letter with char code one less that that of the letter just after the gap.

If there is more than one gap it will return the letter for the last one.
If there is no 2-code gap, then it will return undefined.

findMissingLetter = letters =>
  letters
    .map(c => c.charCodeAt(0))
    .reduce(
      (acc, code, index, codes) => (index && code == codes[index - 1] + 2 ? String.fromCharCode(code - 1) : acc),
      undefined
    );

(checked on kata)

[Melvin Yeo]

I wrote the code (in Python) assuming that the missing letter is within the list, if not there would be 2 answers to it.

def missing_letter(input):
    for index in range(len(input) - 1):
        if ord(input[index + 1]) - ord(input[index]) != 1:
            return chr(ord(input[index]) + 1)

Here is my previous implementation, I wrote this to handle the scenario that the input list wasn't in an ascending order (I didn't read the question completely 🤣)

def missing_letter(input):
    arr = [input[0]] + [None] * len(input)

    for elem in input[1:]:
        if elem < arr[0]:
            offset = elem - arr[0]
            arr = arr[offset::] + arr[:offset]
            arr[0] = elem
        else:
            arr[ord(elem) - ord(arr[0])] = elem

    for index, elem in enumerate(arr):
        if elem is None:
            return chr(ord(arr[0]) + index)