Algorithm Challenges

For the past year, I have been training myself on programming challenges, known as katas, on Codewars. You can find below my solutions. All katas have been solved with JavaScript. I've exported this data from Codewars' platform using my Kata Crawler.

Katas

All

Reverse words

7 kyu

Solved: January 2021

Complete the function that accepts a string parameter, and reverses each word in the string. All spaces in the string should be retained.

Examples

"This is an example!" ==> "sihT si na !elpmaxe"
"double  spaces"      ==> "elbuod  secaps"

View kata on Codewars

function reverseWords(str) {
  return str.split(' ').map(e => e.split('').reverse().join('')).join(' ')
}

Friend or Foe?

7 kyu

Solved: January 2021

Make a program that filters a list of strings and returns a list with only your friends name in it.

If a name has exactly 4 letters in it, you can be sure that it has to be a friend of yours! Otherwise, you can be sure he's not...

Ex: Input = ["Ryan", "Kieran", "Jason", "Yous"], Output = ["Ryan", "Yous"]

i.e.

friend ["Ryan", "Kieran", "Mark"] `shouldBe` ["Ryan", "Mark"]

Note: keep the original order of the names in the output.

View kata on Codewars

function friend(friends){
  return friends.filter(e => e.length === 4);
}

Delete occurrences of an element if it occurs more than n times

6 kyu

Solved: January 2021

Enough is enough!

Alice and Bob were on a holiday. Both of them took many pictures of the places they've been, and now they want to show Charlie their entire collection. However, Charlie doesn't like these sessions, since the motive usually repeats. He isn't fond of seeing the Eiffel tower 40 times. He tells them that he will only sit during the session if they show the same motive at most N times. Luckily, Alice and Bob are able to encode the motive as a number. Can you help them to remove numbers such that their list contains each number only up to N times, without changing the order?

Task

Given a list lst and a number N, create a new list that contains each number of lst at most N times without reordering. For example if N = 2, and the input is [1,2,3,1,2,1,2,3], you take [1,2,3,1,2], drop the next [1,2] since this would lead to 1 and 2 being in the result 3 times, and then take 3, which leads to [1,2,3,1,2,3].

## NASM notes

Write the output numbers into the `out` parameter, and return its length.

The input array will contain only integers between 1 and 50 inclusive. Use it to your advantage.

For C:
* Assign the return array length to the pointer parameter `*szout`.
* Do not mutate the input array.

Example

  delete_nth ([1,1,1,1],2) # return [1,1]
  
  delete_nth ([20,37,20,21],1) # return [20,37,21]

  delete_nth ([1,1,1,1],2) # return [1,1]
  
  delete_nth ([20,37,20,21],1) # return [20,37,21]

  deleteNth ([1,1,1,1],2) // return [1,1]
  
  deleteNth ([20,37,20,21],1) // return [20,37,21]

deleteNth [20,37,20,21]       1 `shouldBe` [20,37,21]
deleteNth [1,1,3,3,7,2,2,2,2] 3 `shouldBe` [1, 1, 3, 3, 7, 2, 2, 2]

Kata.DeleteNth (new int[] {20,37,20,21}, 1) // return [20,37,21]
Kata.DeleteNth (new int[] {1,1,3,3,7,2,2,2,2}, 3) // return [1, 1, 3, 3, 7, 2, 2, 2]

deleteNth [20;37;20;21] 1 // return [20;37;21]
deleteNth [1;1;3;3;7;2;2;2;2] 3 // return [1;1;3;3;7;2;2;2]

EnoughIsEnough.deleteNth(new int[] {20,37,20,21}, 1) // return [20,37,21]
EnoughIsEnough.deleteNth(new int[] {1,1,3,3,7,2,2,2,2}, 3) // return [1, 1, 3, 3, 7, 2, 2, 2]

deleteNth({20,37,20,21}, 1) // return {20,37,21}
deleteNth({1,1,3,3,7,2,2,2,2}, 3) // return {1, 1, 3, 3, 7, 2, 2, 2}

deleteNth(List(20,37,20,21), 1) // return List(20,37,21)
deleteNth(List(1,1,3,3,7,2,2,2,2), 3) // return List(1, 1, 3, 3, 7, 2, 2, 2)

delete_nth(4, {1, 1, 1, 1}, 2, *p)     // returns {1, 1}, 2
delete_nth(4, {20, 37, 20, 21}, 1, *p) // returns {20, 37, 21}, 3

delete_nth(&[20,37,20,21], 1);       // returns vec![20,37,21]
delete_nth(&[1,1,3,3,7,2,2,2,2], 3); // returns vec![1, 1, 3, 3, 7, 2, 2, 2])

View kata on Codewars

function deleteNth(arr,n){
  const sorted = {}
  
  return arr.filter(e => {
    if (sorted[e]) {
      sorted[e].push(e)
      return sorted[e].length > n ? null : e
    } else {
      sorted[e] = [e]
      return e
    }
  })
}

Greed is Good

5 kyu

Solved: January 2021

Greed is a dice game played with five six-sided dice. Your mission, should you choose to accept it, is to score a throw according to these rules. You will always be given an array with five six-sided dice values.

 Three 1's => 1000 points
 Three 6's =>  600 points
 Three 5's =>  500 points
 Three 4's =>  400 points
 Three 3's =>  300 points
 Three 2's =>  200 points
 One   1   =>  100 points
 One   5   =>   50 point

A single die can only be counted once in each roll. For example, a given "5" can only count as part of a triplet (contributing to the 500 points) or as a single 50 points, but not both in the same roll.

Example scoring

 Throw       Score
 ---------   ------------------
 5 1 3 4 1   250:  50 (for the 5) + 2 * 100 (for the 1s)
 1 1 1 3 1   1100: 1000 (for three 1s) + 100 (for the other 1)
 2 4 4 5 4   450:  400 (for three 4s) + 50 (for the 5)

In some languages, it is possible to mutate the input to the function. This is something that you should never do. If you mutate the input, you will not be able to pass all the tests.

View kata on Codewars

function score(dice) {
  const greed = [];
  const sorted = dice.sort((a,b) => a - b); 
  const points = { 1: 1000, 2: 200, 3: 300, 4: 400, 5: 500, 6: 600 }
  let groupArray; 
  
  sorted.forEach((e, i) => {
    if (sorted[i-1] !== e) {
      groupArray = [];
      greed.push(groupArray);
    };
    groupArray.push(e);
  })
  
  return greed.reduce((acc, cur) => {
    if (cur.includes(1)) {
      return acc + (100 * (cur.length % 3)) + (points[cur[0]] * Math.floor(cur.length/3));
    }
    if (cur.includes(5)) {
      return acc + (50 * (cur.length % 3)) + (points[cur[0]] * Math.floor(cur.length/3));
    }
    if (cur.length > 2) {
      return acc + (points[cur[0]] * Math.floor(cur.length/3));
    }
    return acc;    
  }, 0); 
}

Highest Scoring Word

6 kyu

Solved: January 2021

Given a string of words, you need to find the highest scoring word.

Each letter of a word scores points according to its position in the alphabet: a = 1, b = 2, c = 3 etc.

You need to return the highest scoring word as a string.

If two words score the same, return the word that appears earliest in the original string.

All letters will be lowercase and all inputs will be valid.

View kata on Codewars

function score(word) {
  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']
  return word.split('').reduce((acc, cur) => acc + alphabet.indexOf(cur) + 1, 0)
}

function high(x){
  let result = ''
  x.split(' ').forEach(e => {
    if (score(e) > score(result)) {
      result = e
    }
  })
  return result
}

Split Strings

6 kyu

Solved: January 2021

Complete the solution so that it splits the string into pairs of two characters. If the string contains an odd number of characters then it should replace the missing second character of the final pair with an underscore ('_').

Examples:

solution('abc') // should return ['ab', 'c_']
solution('abcdef') // should return ['ab', 'cd', 'ef']

solution('abc') // should return ['ab', 'c_']
solution('abcdef') // should return ['ab', 'cd', 'ef']

SplitString.Solution("abc"); // should return ["ab", "c_"]
SplitString.Solution("abcdef"); // should return ["ab", "cd", "ef"]

solution('abc') # should return ['ab', 'c_']
solution('abcdef') # should return ['ab', 'cd', 'ef']

solution('abc') # should return ['ab', 'c_']
solution('abcdef') # should return ['ab', 'cd', 'ef']

solution("abc") # should return ["ab", "c_"]
solution("abcdef") # should return ["ab", "cd", "ef"]

solution("abc") # should return ["ab", "c_"]
solution("abcdef") # should return ["ab", "cd", "ef"]

solution('abc') # should return ['ab', 'c_']
solution('abcdef') # should return ['ab', 'cd', 'ef']

solution "abc" `shouldBe` ["ab", "c_"]
solution "abcdef" `shouldBe` ["ab", "cd", "ef"]

Solution("abc") //should return ["ab", "c_"]
Solution("abcdef") //should return ["ab", "cd", "ef"]

solution('abc')    // should return List("ab", "c_")
solution('abcdef') // should return List("ab", "cd", "ef")

(solution "abc") ; => ["ab" "c_"]
(solution "abcd") ; => ["ab" "cd"]

StringSplit.solution("abc") // should return {"ab", "c_"}
StringSplit.solution("abcdef") // should return {"ab", "cd", "ef"}

solution("abc", &count) // should return {"ab", "c_"} with count == 2
solution("abcdef", &count) // should return {"ab", "cd", "ef"} with count == 3

The returned array and strings will be free'd.

solution("abc") // should return {"ab", "c_"}
solution("abcdef") // should return {"ab", "cd", "ef"}

solution("abc",  ["ab", "c_"]).
solution("abcd", ["ab", "cd"]).

solution("abc") == ["ab", "c_"]
solution("abcdef") == ["ab", "cd", "ef"]

solution("abcdef") // should return ["ab", "cd", "ef"]
solution("abcdefg") // should return ["ab", "cd", "ef", "g_"]

View kata on Codewars

function solution(str){
  if (!str) return []
  const res = str.match(/.{1,2}/g)
  let last = res[res.length - 1]
  if (last.length < 2) {
    res[res.length - 1] = last += "_"
  } 
  return res; 
}

Find the unique number

6 kyu

Solved: January 2021

There is an array with some numbers. All numbers are equal except for one. Try to find it!

findUniq([ 1, 1, 1, 2, 1, 1 ]) === 2
findUniq([ 0, 0, 0.55, 0, 0 ]) === 0.55

find_uniq([ 1, 1, 1, 2, 1, 1 ]) == 2
find_uniq([ 0, 0, 0.55, 0, 0 ]) == 0.55

find_uniq([ 1, 1, 1, 2, 1, 1 ]) == 2
find_uniq([ 0, 0, 0.55, 0, 0 ]) == 0.55

Kata.findUniq(new double[]{ 1, 1, 1, 2, 1, 1 }); // => 2
Kata.findUniq(new double[]{ 0, 0, 0.55, 0, 0 }); // => 0.55

getUnique [1, 1, 1, 2, 1, 1] -- Result is 2
getUnique [0, 0, 0.55, 0, 0] -- Result is 0.55

findUniq([ 1; 1; 1; 2; 1; 1 ]) = 2
findUniq([ 0; 0; 0.55; 0; 0 ]) = 0.55

It’s guaranteed that array contains at least 3 numbers.

The tests contain some very huge arrays, so think about performance.

This is the first kata in series:

Find the unique number (this kata)
Find the unique string
Find The Unique

View kata on Codewars

function findUniq(arr) {
  return arr.find((e, i) => i === arr.indexOf(e) && i === arr.lastIndexOf(e))
}

Simple validation of a username with regex

8 kyu

Solved: January 2021

Write a simple regex to validate a username. Allowed characters are:

lowercase letters,
numbers,
underscore

Length should be between 4 and 16 characters (both included).

View kata on Codewars

function validateUsr(username) {
  return /^[a-z0-9_]{4,16}$/g.test(username)
}

Extract the domain name from a URL

5 kyu

Solved: January 2021

Write a function that when given a URL as a string, parses out just the domain name and returns it as a string. For example:

domain_name("http://github.com/carbonfive/raygun") == "github" 
domain_name("http://www.zombie-bites.com") == "zombie-bites"
domain_name("https://www.cnet.com") == "cnet"

domain_name("http://github.com/carbonfive/raygun") == "github" 
domain_name("http://www.zombie-bites.com") == "zombie-bites"
domain_name("https://www.cnet.com") == "cnet"

domainName("http://github.com/carbonfive/raygun") == "github" 
domainName("http://www.zombie-bites.com") == "zombie-bites"
domainName("https://www.cnet.com") == "cnet"

View kata on Codewars

function domainName(url){
  return url
    .replace('http://', '')
    .replace('https://', '')
    .replace('www.', '')
    .match(/(.*?)(?=\.)/g)[0]
}

Decode the Morse code

6 kyu

Solved: January 2021

<div style="border:1px solid;position:relative;padding:1ex 1ex 1ex 11.1em;"><div style="position:absolute;left:0;top:0;bottom:0; width:10em; padding:1ex;text-align:center;border:1px solid;margin:0 1ex 0 0;color:#000;background-color:#eee;font-variant:small-caps">Part of Series 1/3</div><div>This kata is part of a series on the Morse code. After you solve this kata, you may move to the <a href="/kata/decode-the-morse-code-advanced">next one</a>.</div></div><br>In this kata you have to write a simple <a href="https://en.wikipedia.org/wiki/Morse_code">Morse code</a> decoder. While the Morse code is now mostly superseded by voice and digital data communication channels, it still has its use in some applications around the world.

The Morse code encodes every character as a sequence of "dots" and "dashes". For example, the letter <code>A</code> is coded as <code>·−</code>, letter <code>Q</code> is coded as <code>−−·−</code>, and digit <code>1</code> is coded as <code>·−−−−</code>. The Morse code is case-insensitive, traditionally capital letters are used. When the message is written in Morse code, a single space is used to separate the character codes and 3 spaces are used to separate words. For example, the message <code>HEY JUDE</code> in Morse code is <code>···· · −·−− ·−−− ··− −·· ·</code>.

NOTE: Extra spaces before or after the code have no meaning and should be ignored.

In addition to letters, digits and some punctuation, there are some special service codes, the most notorious of those is the international distress signal <a href="https://en.wikipedia.org/wiki/SOS">SOS</a> (that was first issued by <a href="https://en.wikipedia.org/wiki/RMS_Titanic">Titanic</a>), that is coded as <code>···−−−···</code>. These special codes are treated as single special characters, and usually are transmitted as separate words.

Your task is to implement a function that would take the morse code as input and return a decoded human-readable string.

For example:

decodeMorse('.... . -.--   .--- ..- -.. .')
//should return "HEY JUDE"

decodeMorse('.... . -.--   .--- ..- -.. .')
//should return "HEY JUDE"

MorseCodeDecoder.Decode(".... . -.--   .--- ..- -.. .")
//should return "HEY JUDE"

MorseCode.decode('.... . -.--   .--- ..- -.. .')
#=> "HEY JUDE"

MorseCode.decode ".... . -.--   .--- ..- -.. ."
--should return "HEY JUDE"

DecodeMorse(".... . -.--   .--- ..- -.. .")
// should return "HEY JUDE"

decodeMorse ".... . -.--   .--- ..- -.. ."
--should return "HEY JUDE"

MorseCodeDecoder.decode(".... . -.--   .--- ..- -.. .")
//should return "HEY JUDE"

decodeMorse('.... . -.--   .--- ..- -.. .')
//should return "HEY JUDE"

decodeMorse('.... . -.--   .--- ..- -.. .')
//should return "HEY JUDE"

decode_morse('.... . -.--   .--- ..- -.. .')
//should return "HEY JUDE"

decodeMorse('.... . -.--   .--- ..- -.. .')
#should return "HEY JUDE"

decodeMorse('.... . -.--   .--- ..- -.. .')
#should return "HEY JUDE"

decodeMorse('.... . -.--   .--- ..- -.. .')
//should return "HEY JUDE"

decodeMorse('.... . -.--   .--- ..- -.. .')
//should return "HEY JUDE"

MorseDecoder::new().decode_morse(".... . -.--   .--- ..- -.. .")
//should return "HEY JUDE"

MorseDecoder.decode(".... . -.--   .--- ..- -.. .")
//should return "HEY JUDE"

decode_morse(".... . -.--   .--- ..- -.. .")
// should return "HEY JUDE"

decodemorse(".... . -.--   .--- ..- -.. .")
# should return "HEY JUDE"

NOTE: For coding purposes you have to use ASCII characters . and -, not Unicode characters.

The Morse code table is preloaded for you as a dictionary, feel free to use it:

Coffeescript/C++/Go/JavaScript/Julia/PHP/Python/Ruby/TypeScript: MORSE_CODE['.--']
C#: MorseCode.Get(".--") (returns string)
Elixir: @morse_codes variable (from use MorseCode.Constants). Ignore the unused variable warning for morse_codes because it's no longer used and kept only for old solutions.
Elm: MorseCodes.get : Dict String String
Haskell: morseCodes ! ".--" (Codes are in a Map String String)
Java: MorseCode.get(".--")
Kotlin: MorseCode[".--"] ?: "" or MorseCode.getOrDefault(".--", "")
Rust: self.morse_code
Scala: morseCodes(".--")
Swift: MorseCode[".--"] ?? "" or MorseCode[".--", default: ""]

C: provides parallel arrays, i.e. morse[2] == "-.-" for ascii[2] == "C"

All the test strings would contain valid Morse code, so you may skip checking for errors and exceptions. In C#, tests will fail if the solution code throws an exception, please keep that in mind. This is mostly because otherwise the engine would simply ignore the tests, resulting in a "valid" solution.

Good luck!

After you complete this kata, you may try yourself at <a href="http://www.codewars.com/kata/decode-the-morse-code-advanced">Decode the Morse code, advanced</a>.

View kata on Codewars

decodeMorse = function(morseCode){
  return morseCode
    .split(' ')
    .map((e,i,a) => !e && a[i-1] ? ' ' : MORSE_CODE[e])
    .join('')
    .trim()
}

Pauline Massé