DEV Community

Cover image for Coding challenges #2 🧩
Killian Frappart
Killian Frappart

Posted on

Coding challenges #2 🧩

Greetings fellow problem solvers! 🤓

As I said already, problem-solving is just like a muscle and it is necessary to practice often in order to improve and grow as a developer.

In this second episode, I picked some easy problems to solve from my favorite algorithms website.

Table of Contents

Can you get the loop ?

From Codewars

The problem:

You are given a node that is the beginning of a linked list. This list always contains a tail and a loop.

Your objective is to determine the length of the loop.

For example in the following picture the tail's size is 3 and the loop size is 11.

Alt Text

Use the "next" attribute to get the following node.

Note: do NOT mutate the nodes!

My solution (JavaScript):

function loop_size(node){
  let turtle = node;
  let rabbit = node;

  /* We need the turtle and the rabbit to start at the same 
  place. (The rabbit being faster will catch up the turtle at 
  some point) */
  do {
    turtle = turtle.getNext();
    rabbit = rabbit.getNext().getNext();
  } while (turtle !== rabbit)

  /* The rabbit goes for a run and we know that ends when he 
  reaches the turtle position again. */
  let counter = 0;
  do {
    rabbit = rabbit.getNext();
    counter++;
  } while (turtle !== rabbit)

    return counter;
} 

Enter fullscreen mode Exit fullscreen mode

Morse Code

From Codewars

The problem:

In this kata you have to write a simple Morse code 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 A is coded as ·−, letter Q is coded as −−·−, and digit 1 is coded as ·−−−−. 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.

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 SOS (that was first issued by Titanic), that is coded as ···−−−···. 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"
Enter fullscreen mode Exit fullscreen mode

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:

JavaScript/TypeScript: MORSE_CODE['.--']

My solution (JavaScript):

const decodeMorse = (morseCode) => {
  const response = [];

  const words = morseCode.trim().split('   ');

  for (const word of words) {
    const wordArr = [];
    for (const letter of word.split(' ')) {
      wordArr.push(MORSE_CODE[letter]);
    }
    response.push(wordArr.join(''))
  }

  return response.join(' ');

}
Enter fullscreen mode Exit fullscreen mode

Rectangle into Squares

From Codewars

The problem:

The drawing below gives an idea of how to cut a given "true" rectangle into squares ("true" rectangle meaning that the two dimensions are different).

Alt Text

Can you translate this drawing into an algorithm?

You will be given two dimensions

  • a positive integer length (parameter named lng)
  • a positive integer width (parameter named wdth)

You will return a collection or a string (depending on the language; Shell bash, PowerShell, Pascal and Fortran return a string) with the size of each of the squares.

Example:

  sqInRect(5, 3) should return "3 2 1 1"
  sqInRect(3, 5) should return "3 2 1 1"
Enter fullscreen mode Exit fullscreen mode

My solution (JavaScript):

function sqInRect(lng, wdth){
  console.log(lng, wdth);

  if (lng === wdth) { return null; }

  let lngx = lng;
  let wdthx = wdth;

  let area = lng * wdth;
  let result = [];



  while (area > 0) {
    if (lngx > wdthx) {
      area -= Math.pow(wdthx, 2);
      result.push(wdthx);
      lngx =  lngx - wdthx;
    } else {
      area -= Math.pow(lngx, 2);
      result.push(lngx);
      wdthx = wdthx - lngx;
    }
  }

  return result;  
}
Enter fullscreen mode Exit fullscreen mode

Meeting

From Codewars

The problem:

John has invited some friends. His list is:

s = "Fred:Corwill;Wilfred:Corwill;Barney:Tornbull;Betty:Tornbull;Bjon:Tornbull;Raphael:Corwill;Alfred:Corwill";
Enter fullscreen mode Exit fullscreen mode

Could you make a program that

  • makes this string uppercase
  • gives it sorted in alphabetical order by last name.

When the last names are the same, sort them by first name. Last name and first name of a guest come in the result between parentheses separated by a comma.

So the result of function meeting(s) will be:

"(CORWILL, ALFRED)(CORWILL, FRED)(CORWILL, RAPHAEL)(CORWILL, WILFRED)(TORNBULL, BARNEY)(TORNBULL, BETTY)(TORNBULL, BJON)"
Enter fullscreen mode Exit fullscreen mode

It can happen that in two distinct families with the same family name two people have the same first name too.

My solution (Python):

def meeting(s):
    result = ""

    # Convert string to list
    names_list = s.upper().split(";")

    # Create a dictionnary and bind a list of first names to every last names
    names_dic = {}
    for name in names_list:
        first_name = name.split(":")[0]
        last_name = name.split(":")[1]

        if last_name in names_dic: names_dic[last_name].append(first_name)
        else: names_dic[last_name] = [first_name]

    # Sort and add every entry to the result string
    for key in sorted(names_dic):
        for first_name in sorted(names_dic[key]):
            result = result + f"({key}, {first_name})"

    return result
Enter fullscreen mode Exit fullscreen mode

Playing with digits

From Codewars

The problem:

Some numbers have funny properties. For example:

89 --> 8¹ + 9² = 89 * 1

695 --> 6² + 9³ + 5⁴= 1390 = 695 * 2

46288 --> 4³ + 6⁴+ 2⁵ + 8⁶ + 8⁷ = 2360688 = 46288 * 51

Given a positive integer n written as abcd... (a, b, c, d... being digits) and a positive integer p

we want to find a positive integer k, if it exists, such as the sum of the digits of n taken to the successive powers of p is equal to k * n.
In other words:

Is there an integer k such as : (a ^ p + b ^ (p+1) + c ^(p+2) + d ^ (p+3) + ...) = n * k

If it is the case we will return k, if not return -1.

Note: n and p will always be given as strictly positive integers.

dig_pow(89, 1) should return 1 since 8¹ + 9² = 89 = 89 * 1
dig_pow(92, 1) should return -1 since there is no k such as 9¹ + 2² equals 92 * k
dig_pow(695, 2) should return 2 since 6² + 9³ + 5⁴= 1390 = 695 * 2
dig_pow(46288, 3) should return 51 since 4³ + 6⁴+ 2⁵ + 8⁶ + 8⁷ = 2360688 = 46288 * 51
Enter fullscreen mode Exit fullscreen mode

My solution (JavaScript):

function digPow(n, p){
  if(!n || !p){
    return -1;
  }
  let digitArray = n.toString().split("");
  let sun = 0;
  for(let i = 0; i<digitArray.length; i++){
    sun += Math.pow(digitArray[i], p+i);

  }
  if(parseInt(sun/n) === sun/n){
  return sun/n;
  }
  else{
    return -1;
  }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (2)

Collapse
 
kiliman profile image
Kiliman

Nice. DEV has a coding challenge series (dev.to/thepracticaldev/series/1326) that I've done a few of. One thing I do is actually write tests first (the challenge requirements) then write the code to implement it. This way you can verify that you solved the challenge.

Here's an example:

Test

import { code, decode } from '.'

describe('encode data', () => {
  it('should return encoded data', () => {
    expect(code('mer', 6015)).toBe('6015ekx')
    expect(code('hello', 9317)).toBe('9317lkvvw')
    expect(code('goodbye', 1234603)).toBe('1234603kggftoy')
  })
})

describe('decode data', () => {
  it('should return decoded data', () => {
    expect(decode('6015ekx')).toBe('mer')
    expect(decode('9317lkvvw')).toBe('hello')
    expect(decode('1234603kggftoy')).toBe('goodbye')
  })

  it('should return "Impossible to decode" if unable to decode', () => {
    expect(decode('5057aan')).toBe('Impossible to decode')
    expect(decode('xxx5057aan')).toBe('Impossible to decode')
  })
})
Enter fullscreen mode Exit fullscreen mode

Implementation

export const code = (s: string, num: number): string => {
  const map = (c: string) => c.charCodeAt(0) - 97
  const unmap = (x: number) => String.fromCharCode(x + 97)
  const f = (x: number) => (num * x) % 26

  let r = ''
  for (let i = 0; i < s.length; i++) {
    const x = map(s[i])
    const ch = unmap(f(x))
    r += ch
  }
  return String(num) + r
}

// calculate modular inverse
// https://rosettacode.org/wiki/Modular_inverse#JavaScript
const modInverse = (a: number, b: number): number => {
  a %= b
  for (let x = 1; x < b; x++) {
    if ((a * x) % b === 1) {
      return x
    }
  }
  return 1
}

export const decode = (r: string): string => {
  const match = r.match(/^\d+/)
  let num = -1
  if (match) {
    num = parseInt(match[0])
    r = r.substring(match[0].length)
  }
  const a_ = modInverse(num, 26)
  if (num === -1 || a_ === 1) {
    return 'Impossible to decode'
  }

  const map = (c: string) => c.charCodeAt(0) - 97
  const unmap = (x: number) => String.fromCharCode(x + 97)
  const f = (x: number) => (a_ * x) % 26

  let s = ''
  for (let i = 0; i < r.length; i++) {
    const x = map(r[i])
    const ch = unmap(f(x))
    s += ch
  }

  return s
}
Enter fullscreen mode Exit fullscreen mode

github.com/kiliman/dev-to-daily-ch...

Collapse
 
killianfrappartdev profile image
Killian Frappart

Thank you for sharing! I like to have my own series of challenges because it leaves a trace of my progression.

It is a great idea to write tests before starting a challenge, I'll keep that in mind for the next time :)