DEV Community: JP Antunes

Integer to Roman and back

JP Antunes — Mon, 20 Jul 2020 19:11:37 +0000

I haven't posted in a while and now that my career took a U-turn back into the boardroom, I suppose it might be the beginning of the end of my coding days... again. Strange times!

While on the topic of switching back and forth between worlds, here's two simple O(n) solutions to Leetcode's Roman to Integer and Integer to Roman problems.

// integer to roman numeral
const intToRoman = function(num) {
    const rosettaStone = {
        1: 'I',
        5: 'V',
        10: 'X',
        50: 'L',
        100: 'C',
        500: 'D',
        1000: 'M'
    };            
    let resStr = '';

    for (let i = 1000; i >= 1; i /= 10) {
        const times = Math.trunc(num / i);
        if (times > 0) {
            if (times % 9 == 0) {
                resStr += rosettaStone[i]
                    .concat(rosettaStone[(times + 1) * i])    
            } else if (times % 8 == 0) {
                resStr += rosettaStone[(times - 3) * i]
                    .concat(rosettaStone[(times - 7) * i]
                    .repeat(3))
            } else if (times % 7 == 0) {
                resStr += rosettaStone[(times - 2) * i]
                    .concat(rosettaStone[(times - 6) * i]
                    .repeat(2))                
            } else if (times % 6 == 0) {
                resStr += rosettaStone[(times - 1) * i]
                    .concat(rosettaStone[i])
            } else if (times % 5 == 0) {
                resStr += rosettaStone[(times) * i] 
            } else if (times % 4 == 0) {
                resStr += rosettaStone[i]
                    .concat(rosettaStone[(times + 1) * i])   
            } else if (times <= 3) {
                resStr += rosettaStone[i].repeat(times);            
            } 
            num -= times * i;
        } 
    }        

    return resStr;            
};

// roman numeral to integer
const romanToInt = function(s) {
    const rosettaStone = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000        
    };
    let result = 0;
    let lastValue = 0;

    for (let i = s.length -1; i >= 0; i--) {
        const value = rosettaStone[s[i]];
        if (lastValue > value) {
            result -= value;
        } else {
            result += value;
        }
        lastValue = value;
    }

    return result;
};

optional soundtrack

Number of Ways to Paint N × 3 Grid - a short saga

JP Antunes — Sat, 06 Jun 2020 17:00:43 +0000

Today's Leetcode problem was a bit of a wormhole but I feel like my notes and the process to find the answer make for a much more interesting post than just the winning algorithm, so this is the short saga of how I got to a top entry :-)

The Problem

You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colours while making sure that no two adjacent cells have the same colour.
You are given n the number of rows of the grid. Return the number of ways you can paint this grid modulo 10^9 + 7.

The naive solution

var numOfWays = n => {
    const allowedSets = ['RGB', 'RBG', 'RGR', 'RBR', 
                        'GBR', 'GRB', 'GRG', 'GBG', 
                        'BRG', 'BGR', 'BGB', 'BRB'];
    if (n == 1) return allowedSets.length;

    let collection = allowedSets;
    for (let i = 1; i < n; i++) {        
        let newCollection = [];
        collection.forEach(row => {
            let filtered = allowedSets.filter(e => 
                                 e[0] !== row[0] 
                                 && e[1] !== row[1] 
                                 && e[2] !== row[2]);
            newCollection = [...newCollection, ...filtered]; 
        })
        collection = newCollection;
    }
    return collection.length % (10**9 + 7);
}

The first step was to write down the most basic algorithm that could possibly work, aka the "naive solution". The time and space complexity are exponential but using dynamic programming techniques I believe it could be made faster and smarter.

On the other hand, I got to see the actual sets growing with each iteration over the collection and since I wasn't on time pressure I decided to investigate a bit deeper.

Finding patterns

//pairing table for n == 2
{
    RGB: [ 'GBR', 'GRG', 'GBG', 'BRG' ],
    RBG: [ 'GRB', 'BGR', 'BGB', 'BRB' ],
    RGR: [ 'GRB', 'GRG', 'GBG', 'BRG', 'BRB' ],
    RBR: [ 'GRB', 'GRG', 'BRG', 'BGB', 'BRB' ],
    GBR: [ 'RGB', 'BRG', 'BGB', 'BRB' ],
    GRB: [ 'RBG', 'RGR', 'RBR', 'BGR' ],
    GRG: [ 'RGB', 'RGR', 'RBR', 'BGR', 'BGB' ],
    GBG: [ 'RGB', 'RGR', 'BGR', 'BGB', 'BRB' ],
    BRG: [ 'RGB', 'RGR', 'RBR', 'GBR' ],
    BGR: [ 'RBG', 'GRB', 'GRG', 'GBG' ],
    BGB: [ 'RBG', 'RBR', 'GBR', 'GRG', 'GBG' ],
    BRB: [ 'RBG', 'RGR', 'RBR', 'GBR', 'GBG' ]
}

Initially I pre-calculated the twelve "allowed sets" by hand and then used Array.reduce to create pairing tables as each new row up to n was added.

Looking at the evolution of this table allowed me to make a few interesting observations, such as:

when n == 1 result is 12, namely 6 two colour sets and 6 three colour sets.
when n == 2 result is 54, because every two colour set from the previous round is repeated 5 times totalling 30 sets, while the three colour ones repeat 4, making for 24 sets.
when n == 3 result is 246, with 108 three colours sets and 138 sets of two colours.

Trust your instincts but test exhaustively anyway
My first instinct was to calculate the growth in number of compatible pairs for each of the 12 distinct sets with a pen and paper. It looked something like this:

4*6 + 5*6 = 54          //pairs with 3 colour sets + pairs with 2 colour sets if n = 2
54 * (4/12) = 18      
54 * ceil(5/12) = 23 
18*6 + 23*6 = 246       //pairs with 3 colour sets + pairs with 2 colour sets if n = 3
246 * (18/54) = 82      
246 * ceil(23/54) = 105
82*6 + 105*6 = 1122     //pairs with 3 colour sets + pairs with 2 colour sets if n = 4

I didn't keep the code created for this one because it turned out to be a red herring. Somewhere between n == 15 and n == 25, depending on different rounding mechanisms implemented (...and I spent 1h plus on this), the result would be off.

There was something there... but I was trying to calculate how many pairs each of the 12 unique sets would have per row, and it took me a while to realise a much simpler pattern exists, one which allows directly calculating the total number of unique sets per row without fractions.

This is why a REPL is so useful :-)

> let twoC = 6, threeC = 6
> let next2C = (c2, c3) => 2 * c3 + 3 * c2
> let next3C = (c2, c3) => 2 * c3 + 2 * c2
> next2C(twoC, threeC)
30
> next3C(twoC, threeC)
24
> next3C(30, 24)
108
> next2C(30, 24)
138

Ok then! Let's give this one a try and let's see how it runs now....

var numOfWays = n => {
    let twoColours = 6;
    let threeColours = 6;
    const mod = (10**9 +7);

    for (let i = 1; i < n; i++) {
        let prevTwo = twoColours;
        let prevThree = threeColours;
        twoColours = (2 * prevThree + 3 * prevTwo) % mod;
        threeColours = (2 * prevThree + 2 * prevTwo) % mod;
    }
    return (twoColours + threeColours) % mod;
}
//64ms, better than 70.43%

Right. I'm about 2 hours into this problem and all I get is a top 70% result...

Persistence in the face of defeat
Once the feeling of utter failure gave way to the much more familiar impostor syndrome, I was able to make an honest evaluation of my code. Here it is:

This solution starts with a pre-calculated result for n = 1, has two variables that can be removed without loss of functionality and I should be able to do away with the final modulo operation because I'm storing intermediate results using clock arithmetic anyway.
Also, exponentiation is expensive so I could replace the 10**9 + 7 with 1000000007 to spare the CPU an instruction or two.

> numOfWays(4)
twoC: 15, threeC: 12
twoC: 69, threeC: 54
twoC: 315, threeC: 246
twoC: 1437, threeC: 1122
2559

What a rabbit hole! Now the sum of two and three colour sets is completely off... but the threeC variable holds the right result?? Before I worry too much about how this works, let me shave off one more CPU instruction and just return threeC instead of the sum of twoC + threeC!

var numOfWays = function(n) {
    let temp = 3;
    let res = 3;

    for (let i = 0; i < n; i++) {
        let prevRes = res;
        res = (2 * res + 2 * temp) % 1000000007;
        temp = (2 * prevRes + 3 * temp) % 1000000007;
    }
    return res;   
}
// Runtime: 60 ms, faster than 83.58% of JavaScript online submissions for Number of Ways to Paint N × 3 Grid.
// Memory Usage: 35.5 MB, less than 91.30% of JavaScript online submissions for Number of Ways to Paint N × 3 Grid.

Oh... top 83%... neat.

I suppose that means there is a solution that beats O(n) time and O(1) space but I can't imagine what it could be. I'm also not really sure of how to optimise for a JIT compiler, so perhaps I'm missing some of the nuances of modern Javascript... or maybe I should get a paid Leetcode account, because that's what the "speed up" link directs me to do?

My head hurts and I'm at my wits' end... I'm quite persistent but I've often felt like I had something to prove to my colleagues with CS degrees throughout my now 22 year career so I wasn't sure it wasn't hubris that was driving me madness. In other words, I wasn't ready to call it a day just yet ¯\(ツ)/¯

Convinced the exact same code would be blazingly fast in C, I gave it a go, and wouldn't you know it...

int numOfWays(int n){
    long int temp = 3;
    long int res = 3;

    for (int i = 0; i < n; i++) {
        long int prevRes = res;
        res = (2 * res + 2 * temp) % 1000000007;
        temp = (2 * prevRes + 3 * temp) % 1000000007;
    }
    return res;   
}
// Runtime: 0 ms, faster than 100.00% of C online submissions for Number of Ways to Paint N × 3 Grid.
// Memory Usage: 5.1 MB, less than 64.52% of C online submissions for Number of Ways to Paint N × 3 Grid.

Finally! It feels like my efforts paid off, and I'm only slightly annoyed because I don't fully understand why this variation works well in C but nowhere near the 95th percentile in JS. However, finding the patterns, pursuing my intuitions until finally discovering two working algorithms was definitely too much fun for me not to share!

Hope you've enjoyed this post, and if you know something I don't... please share too :-)

ransom note - updated

JP Antunes — Sun, 31 May 2020 14:49:53 +0000

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false. Each letter in the magazine string can only be used once in your ransom note.

Update: It was troubling me that I couldn't get a higher result, and since JS gives us many ways of doing the same thing I decided to try one more time.

Now with a 90th percentile + result, I'm much happier :-)

// Runtime: 64 ms, faster than 94.72% of JavaScript online submissions for Ransom Note.
// Memory Usage: 38.4 MB, less than 33.33% of JavaScript online submissions for Ransom Note.

var canConstruct = function(ransomNote, magazine) {
  if (ransomNote.length > magazine.length) return false;
  let charMap = [];
  for (let i = 0; i < ransomNote.length; i++) {
      if (magazine.indexOf(ransomNote[i]) == -1) return false;
      let char = ransomNote.codePointAt(i);
      charMap[char] = charMap[char] - 1 || -1;
  }

  for (let i = 0; i < magazine.length; i++) {
      let char = magazine.codePointAt(i);
      charMap[char] = charMap[char] + 1 || 1;
  }
  for (const charCount of charMap) if (charCount < 0) return false;
  return true; 
};

** previously **
Didn't get a particularly impressive result, but here's 3 valid solutions exploring different data structures and approaches.

// Runtime: 76 ms, faster than 77.31% of JavaScript online submissions for Ransom Note.
// Memory Usage: 38.1 MB, less than 33.33% of JavaScript online submissions for Ransom Note

var canConstruct = function(ransomNote, magazine) {
    let retVal = true;
    const noteCharMap = [...ransomNote].reduce((acc, val, _, arr) => {
        acc[val] = acc[val] + 1 || 1;
        if (magazine.indexOf(val) == -1) {
            retVal = false;
            arr.pop(); //force early return with arr mutation
        }
        return acc;
    }, {});
    if (!retVal) return false;

    const magzCharMap = [...magazine].reduce((acc, val) => {
        acc[val] = acc[val] + 1 || 1;
        return acc;
    }, {});
    for (const [char, count] of Object.entries(noteCharMap)) {
        if (magzCharMap[char] < count) return false;
    }
    return true;
};

var canConstruct = function(ransomNote, magazine) {
    let charMap = {};
    for (const char of ransomNote) {
        if (magazine.indexOf(char) == -1) return false;
        charMap[char] = charMap[char] + 1 || 1;
    }
    for (const char of magazine) {
        if (charMap[char]) charMap[char] -= 1;
        if (charMap[char] == 0) delete charMap[char];
    }
    for (const _ in charMap) return false;
    return true;
};

var canConstruct = function(ransomNote, magazine) {
    const charMap = new Map();
    for (const char of ransomNote) {
        if (magazine.indexOf(char) == -1) return false;
        charMap.set(char, charMap.get(char) + 1 || 1)
    }
    for (const char of magazine) {
        charMap.set(char, charMap.get(char) - 1 || 0)
        if (charMap.get(char) <= 0) charMap.delete(char);
    }
    for (const _ of charMap) return false;
    return true;
};

Compress a string such that 'AAABCCDDDD' becomes 'A3B1C2D4'

JP Antunes — Mon, 25 May 2020 14:17:00 +0000

This seems to be a popular interview question that I stumbled upon in an Anki deck

const compress = str => {
        //build a character frequency map
    const freqM = [...str].reduce((acc, val) => { 
        acc[val] = acc[val] + 1 || 1; 
        return acc;
    }, {});
        //return str if length <= unique characters * 2 (ie, 'A' vs 'A1') 
    if (str.length <= Object.keys(freqM).length * 2) return str;
        //return the frequency map as a string otherwise 
    return  Object.entries(freqM).flat().join('');
}

Idempotent vs Deterministic

JP Antunes — Tue, 12 May 2020 18:36:46 +0000

Since I had to look it up more than once, here's a small reminder of the differences between the two concepts.

//f(x) + f(x) == 2 * f(x) for all x
const addTwo = (x, y) => x + y;

This is a deterministic or pure function, the same input always returns the same output

//f(x) == f(f(x)) for all x
let someExternalState = 'off';
const activate = () => someExternalState = 'on';

This is an idempotent function, calling it once or many times in a row produces the same side effect

First Missing Positive

JP Antunes — Thu, 30 Apr 2020 11:53:33 +0000

Given an unsorted integer array, find the smallest missing positive integer. Note: Your algorithm should run in O(n) time and use constant extra space.

Sounds hard right?

var firstMissingPositive = function(nums) {
  if (nums.length <= 1)  return nums[0] == 1 ? 2 : 1;    

  const max = Math.max(...nums);
  for (let i = 1; i <= max + 1; i++) {
      if (!nums.includes(i)) return i;
      //alternatively: if (nums.indexOf(i) === -1) return i;
  }    
  return 1; //every other case, ie all n in nums are < 0
};

// Runtime: 48 ms, faster than 95.76% of JavaScript online submissions for First Missing Positive.
// Memory Usage: 33.8 MB, less than 91.67% of JavaScript online submissions for First Missing Positive.

Next Permutation

JP Antunes — Wed, 29 Apr 2020 20:01:15 +0000

Today's Leetcode problem is quite interesting and, personally, I found the in-line array mutation tricky to get right.

We are asked to return the next highest number possible with a given array, falling back to sorting it by ascending order if the source value is the highest possible for that set of numbers.

Sound like a couple of loops to me!

var nextPermutation = function(nums) {
  for (let i = nums.length; i > 0; i--) {
    if (nums[i - 1] < nums[i]) {
      let nextHigherIdx = Infinity;
      for (let j = i; j < nums.length; j++) {
        if (nums[j] > nums[i - 1] && nums[j] <= (nums[nextHigherIdx] || Infinity)) {
          nextHigherIdx = j;
        }
      }
      //replacement must be in-place and use only constant extra memory
      [nums[i - 1], nums[nextHigherIdx]] = [nums[nextHigherIdx], nums[i - 1]];      
      nums.splice(i, nums.length - i, ...nums.splice(i).reverse());
      return;
    }
  }
  //sorted in ascending order as fallback
  nums.sort((a, b) => a - b);
};

//Runtime: 52 ms, faster than 99.41% of JavaScript online submissions
//Memory Usage: 35 MB, less than 33.33% of JavaScript online submissions

Add two numbers

JP Antunes — Mon, 27 Apr 2020 18:21:40 +0000

Leetcode time again!

This one actually took me a bit. The problem description states we should sum two non-empty linked lists representing two positive integers stored in reverse order, and return the result as a linked list.

The sum can exceed JS's Max Integer size and that means that adding the numbers requires some type coercion between string and BigInt but it replaces a loop with a simple arithmetic addition so it seemed worth it.

var addTwoNumbers = function(l1, l2) {
  let num1Str = '';
  let num2Str = '';
  let node = l1;

  while (node) {
    num1Str = node.val + num1Str;
    node = node.next;
  }

  node = l2;
  while (node) {
    num2Str = node.val + num2Str;
    node = node.next;
  }

  const sum = BigInt(num1str) + BigInt(num2str);  
  const sumStr = sum.toString();
  const resLst = new ListNode(sumStr[sumStr.length - 1]);

  node = resLst;
  for (let i = sumStr.length - 2; i >= 0; i--) {
    node.next = new ListNode(sumStr[i]);
    node = node.next;
  }
  return resLst;   
};

//Runtime: 96 ms, faster than 99.18% of JavaScript online submissions for Add Two Numbers.
//Memory Usage: 39.2 MB, less than 13.89% of JavaScript online submissions for Add Two Numbers.

Tiniest bubble sort on the net?

JP Antunes — Sun, 26 Apr 2020 08:01:04 +0000

I stumbled on an older dev.to post by the great Greg Bullmash that I really liked because it triggered my code-golfing nerve, and I figured I could come up with a bubble sort one-liner!

Turns out I was wrong, I need at least 4 3 lines to make tiniest working bubble sort algo on the net* but it was still a fun exercise so I'm sharing it.

const bubblie = (arr, swaps = false) => {
  arr.forEach((e,i) => { e > arr[i+1] ? ([arr[i], arr[i+1]] = [arr[i+1], arr[i]], swaps = true) : false });
  return !swaps ? arr : bubblie(arr, false);
}

*citation needed

It's Friday, let's break an Integer with math!

JP Antunes — Fri, 24 Apr 2020 14:44:40 +0000

Leetcode's Integer Break problem popped up in my mailbox today just before I had my morning coffee.

For that reason alone, I won't explain the math behind the solution :-)

var integerBreak = function(n) {
  if (n < 4) return n - 1;

  let times3 = Math.floor(n / 3);
  let diff = n - (times3 * 3);

  if (diff == 0) {
    return 3 ** times3;
  } else if (diff == 1) {
    return (3 ** (times3 - diff) * (3 + diff));
  } else { //diff == 2
    return (3 ** times3 / (3 + diff) * 10);
  }  
};

// Runtime: 48 ms, faster than 93.94% of JavaScript online submissions for Integer Break.
// Memory Usage: 33.9 MB, less than 100.00% of JavaScript online submissions for Integer Break.

Valid Number

JP Antunes — Wed, 22 Apr 2020 04:27:54 +0000

The valid number problem currently has the lowest acceptance rate of Leetcode at just 14.9%. That must mean it's hard right?

This one reminded me of my Perl days because somehow it's 3 AM and I'm having fun with regular expressions :-)

/**
 * @param {string} s
 * @return {boolean}
 */
var isNumber = function(s) {

  const trimRegex = /(^\s+|\s+$)/g;
  const trimedS = s.replace(trimRegex, '')
  if (trimedS.length == 0) return false;

  const validCharsRegex = /[0-9e+-.]/;
  if (![...trimedS].every(e => e.match(validCharsRegex))) return false;

  const invalidPatternsRegex = /(^\.e|^\.$|^e.*?|e.+?\.+?|\..+?\.|.+?e$|\d+?[+-]\d.?|[+-]+?\.$|.+?[+-]$|.+?e+?.*?e+?|\+[e+-]+?|\-[e+-]+?|\.[.+-]+?|e\.+?)/gi;
  if (trimedS.match(invalidPatternsRegex)) return false;

  return true;
};

Short, and hopefully correct description of the scary regex:

const invalidPatternsRegex = /
    (^\.e               -> . at the beginning of string followed by e
    |^\.$               -> only 1 .
    |^e.*?              -> e at the beginning of string followed by any zero or more times
    |e.+?\.+?           -> e 1 or more times followed by . 1 or more times
    |\..+?\.            -> . followed by any 1 or more times followed by .
    |.+?e$              -> any 1 or more times followed by e at the end of string
    |\d+?[+-]\d.?       -> [0-9] 1 or more times followed by either + or - followed by [0-9] 1 or more times
    |[+-]+?\.$          -> either + or - 1 or more times followed by . at the end of string
    |.+?[+-]$           -> any 1 or more times followed by either + or - at the end of string
    |.+?e+?.*?e+?       -> any 1 or more times followed by e 1 or more times followed by any zero or more times followed by e 1 or more times
    |\+[e+-]+?          -> + followed by either e or + or - 1 or more times
    |\-[e+-]+?          -> - followed by either e or + or - 1 or more times
    |\.[.+-]+?          -> . followed by either . or + or - 1 or more times
    |e\.+?              -> e followed by any 1 or more times
    )
    /gi;                -> flags: global and case insensitive

// Runtime: 76 ms, faster than 92.92% of JavaScript online submissions for Valid Number.
// Memory Usage: 37.5 MB, less than 12.50% of JavaScript online submissions for Valid Number.

Render to Caesar the things that are Caesar's

JP Antunes — Sun, 19 Apr 2020 12:40:41 +0000

The /r/portugal sub-reddit can be a surprising little place. Today someone asked if the message in the cover picture was some form of encrypted text.

Well, it's a Caesar's cipher with ROT1, which is a simple dictionary substitution cipher and we can easily come up with encrypt/decrypt functions by mapping the character index in the source message's alphabet to the destination's.

//first we need to define our regular alphabet
const alphaB = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
//now the rot1 alphabet, ie our regular alphabet shifted by one place
const rot1 = 'ZABCDEFGHIJKLMNOPQRSTUVWXY'

//our encrypt/ decrypt functions use the same logic but invert the source and target alphabets
const caesarsEnc = str => [...str].map(e => alphaB[rot1.indexOf(e)])
const caesarsDec = str => [...str].map(e => rot1[alphaB.indexOf(e)])

The functions only work with capital letters, but it's enough for our purposes.

const myMsg = 'HELLO WORLD';
> caesarsEnc(myMsg).map(e => e !== undefined ? e : ' ').join('')
'IFMMP XPSME'

const mySecretMsg = 'IFMMP XPSME'
> caesarsDec(mySecretMsg).map(e => e !== undefined ? e : ' ').join('')
'HELLO WORLD'