CodeWars: Weekly Newsletter

8kyu – positiveSum

The first question is to sum up all the positive integers in an array. Basically two things need to be done:

  • Filter out Values that should not be added to the sum
  • Sum up every item in the array

Basically you can write the solution like this:

export function positiveSum(arr: number[]): number {
  return arr
          .filter(val => val > 0)
          .reduce((total, current) => total + current, 0)
}

It is important to note that the initial value of 0 must be set, as if you pass in an empty array it would return NaN

7kyu – next Prime

Basically you need to check every number if it isPrime. Then you need to select an algorithm that can check if it is a prime number.

In this case I just took the code from the npm package is-number-prime. Which is a brute force way of figuring out if the number is prime or not. (There is probably something more mathematically elegant out there)

function isNumberPrime(n) {
  if (n === 2 || n === 3){
    return true;
  }
  
  if (n < 2 || n % 1 || n % 2 === 0 || n % 3 === 0) {
    return false;
  }
  let foo = Math.floor(Math.sqrt(n));
  for (let i = 5; i <= foo; i += 6) {
    if (n % i === 0 || n % (i + 2) == 0) {
      return false;
    }
  }
  return true;
}

function nextPrime(n){
  while (true){
    n++;
    if (isNumberPrime(n)){
      return n;
    }
  }
}

CodeWars: Weekly Newsletter 02

8kyu – Logic Drills: Traffic light

You need a function to handle each change from green, to yellow, to red, and then to green again.

Based on how the question is formulated it is suggested that you should always return the next item in an array. If it is the last item it should return the first item.

/**
 * 
 * @param {'green'| 'yellow'| 'red'} current 
 * @returns {string}
 */
function updateLight(current) {
  let lights = ['green', 'yellow', 'red'];
  let nextIndex = (lights.indexOf(current) + 1) % lights.length;
  return lights[nextIndex];
}

However as alternative you also could say: We always already know the next state, we do not need to calculate the next state. For traffic lights this system also probably will never change. Thus you can use an object to save the next states.

/**
 * 
 * @param {'green'| 'yellow'| 'red'} current 
 * @returns {string}
 */
function updateLight2(current) {
    return {
    'green': 'red',
    'yellow': 'green',
    'red': 'yellow'
  }[current];
}

7kyu – Sum of numerous arguments

The idea of this problem is mostly to make aware of that you can pass in an arbitrary amount of arguments into a js function.

In ES5 you would be using the arguments object and iterate over the array. in ES6 however we can use the cleaner spread-syntax:

/**
 * 
 * @param {number[]} args 
 * @returns {number}
 */
function findSum(...args){
  if (args.find(val => val < 0)){
    return -1;
  } else {
    return [...arguments].reduce((total, current) => total + current);
  }
}

CodeWars: 7kyu – The Highest Profit wins

I am exercising to get back into Python. Even though the solution to this exercise is quite straightforward, you could tweak the code a little bit so that it runs a little faster.

Basically, with min() and max(), the list would need to be iterated over 2 times. You could rewrite the code so that you only iterate once over the array. Overall I choose to stick with my initial solution as it is better readable, thus making it easier to maintain in the long run.

def min_max(lst):
    '''
    Exercise: https://www.codewars.com/kata/the-highest-profit-wins/train/python
    Example:
        min_max([1, 2, 3, 4, 5]) => [1, 5]
    Args:
        lst: A list of numbers
    
    Returns:
        A list with two entries of the min and the max value of the list
    '''
    return [min(lst), max(lst)]

CodeWars: 6kyu – Counting Bits

You got numbers, you want to know how many bits are flipped to a 1

Sourcehttps://www.codewars.com/kata/bit-counting/train/python

Approach:

Well, first we need to convert our number from an integer to a binary number.

There are two ways to do this:

Variant 1: String Formatting

"{:b}.format(number)"

Variant 2: Build In a binary converter “bin(number)”

Then well now we just have to count the occurrences of ones.

def count_bits:
   return bin(number).count(str(1))

Note: It is important to count the instances of ones as strings of “1” instead of integers of 1. This is the case because we converted the int to a string and are now looking for strings instead of numbers.

Codewars: Sum Of Pairs

Given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that add up to form the sum.

Source: https://www.codewars.com/kata/sum-of-pairs

The initial problem does seem quite simple:

  1. Iterate over the array
  2. Check for every item if there is a corresponding pair
  3. Return the pair that has the lowest right index
var sum_pairs = function (arr, sum) {
    let pairs = []
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if (arr[i] + arr[j] === sum && i != j && j > i) {
                results.push(j);
            }
        }
    }
    if (results.length) {
        let value = arr[Math.min(...results)];
        return [sum - value, value];
    } else {
        return undefined;
    }
}

All Tests pass. You think to yourself, well that was quite straightforward. No big deal. Let’s attempt the solution.

‘Attempt timed out’ solution must finish before 12s pass.

Then let’s optimize the algorithm. what all can we do?

  1. We can replace the second loop with the internal array.indexOf Function
  2. If we found a match we can stop looking for matches past the matches index
  3. We can avoid the pairs array, as we are only interested in a specific pair
var sum_pairs = function (arr, sum) {
    let rightIndex = arr.length;
    let match = false;
    for (let i = 0; i < rightIndex; i++) {
        let pairIndex = arr.indexOf(sum - arr[i]);

        if (pairIndex != -1 && pairIndex < rightIndex && pairIndex !== i) {
            rightIndex = pairIndex;
            match = true;
        }
    }
    if (match) {
        let value = arr[rightIndex];
        return [sum - value, value];
    }
    return undefined;
}

At this point, we only optimized for a couple of edge cases. We did not really reduce the complexity of the algorithm in the worst case every item in the array would need to be compared with every item in the array O(n*n). As even when we are using the internal functions we are still iterating over all items.

Next round of optimizations:

  • Instead of iterating and forgetting what we did let’s save our result.

Initially, I had a solution to map all values to an array and then iterate and find the pairs so it would have been O(2*n). But I had difficulties implementing that solution as the array of values could contain duplicates. Then I thought about it and said, hey if I simply compare the current value with the previous values then If I find a match, then I can stop and it would always be the right value. and as a bonus, the complexity is now 0(n), as if the pair is the last two elements of the array we would have needed to visit all elements before that.

var sum_pairs = function (arr, sum) {
    let viewedValues = []
    for (let i = 0; i & lt; arr.length; i++) {
        let currentValue = arr[i];
        let difference = sum - currentValue;
        if (viewedValues[difference]) {
            let result = [difference, currentValue];
            return result;
        }
        viewedValues[currentValue] = true;
    }
    return undefined;
}

comparing the first and the last solution there is a tradeoff between the two solutions.

  1. In the 0(n*n) solution it takes longer to get to the result. However, we do not need so much memory.
  2. With the O(n) solution, we get the result quicker, but we need a lot more memory.

CodeWars Kata: File Path Operations

The quick Code Wars Kata I am taking a look at the Kata File-Path-Operations.

My approach to solving the kata was, first to figure out what skills are needed to solve the problem. Since all three problems are similar and try to find a specific pattern in a string, the obvious answer is Regular Expressions.

The fastest way to learn, create and test your Regular Expressions is using Regex 101.

I solved the Kata using Typescript and this is my final code:

export class FileMaster {

  constructor(private filepath:string) { }

  extension() {
   return this.filepath.match(/\.(.*)/)[1];
  }

  filename() {
   return this.filepath.match(/\/([^\/]*)\./)[1];
  }

  dirpath() {
   return this.filepath.match(/(.*\/)/)[1];
  }
}

This piece of code would not be suitable for production. It does not take into account of malformed filenames, it would not work for windows; It would have problems with folders that contain a “.” etc.

If you would be using NodeJS you would use the existing functions in the Path Module.