DEV Community: Eduardo Lanchares

Periodic table code golf

Eduardo Lanchares — Tue, 12 Jul 2022 21:58:58 +0000

The other day I came across this tweet:
// Detect dark theme var iframe = document.getElementById('tweet-1537447575573233666-880'); if (document.body.className.includes('dark-theme')) { iframe.src = "https://platform.twitter.com/embed/Tweet.html?id=1537447575573233666&theme=dark" }

I thought this was a nice challenge to solve and refresh some programming stuff, so I opened my editor and started coding a solution 🤓

Understanding the problem

Reading about periodic table in Wikipedia I've discovered that there's more than one way to display it. Taking into account the example in the tweet, we're going to assume it's the standard form.

If we take a look at the table, the first thing to notice is how elements are disposed in it

As we can see it's just a regular table but with some exceptions. For instance, helium with an atomic number of 2 should start at group 2, but it doesn't (check this if you want to know why), so we need to keep track of these special cases. In total we have 3 exceptions (He, B and Al).

There's another special case to consider: Lanthanoids and actinoids. For the sake of simplicity we're not going to consider it for this challenge.

Now that everything is clear, let's start!

Step 1 - 1D to 2D

First task is finding a way to map an atomic number to a row and a column in the table. We know that atomic numbers are sequential and goes from 1 to 118 and also that periodic table has 18 groups. Considering a regular table we could do the following:

function getElementPosition(atomicNumber) {
  const groups = 18
  const index = atomicNumber - 1;
  const row = Math.trunc(index / groups)
  const column = index % groups

  return [row + 1, column + 1]
}

Here we're transforming a one dimensional index into a two dimensional one. That's a good starting point but we need to take special cases into consideration

Step 2 - Special cases

For special cases we can use an array to store when they start and what's the offset we need to apply:

function getElementPosition(atomicNumber) {
  let groups = 18
  let index = atomicNumber - 1;
  let specialNumbers = [
    [2, 16], 
    [5, 10],
    [13, 10],
  ]

  for (let [number, offset] of specialNumbers) {
    if (number <= atomicNumber) {
      index += offset
    }
  }

  let row = Math.trunc(index / groups)
  let column = index % groups

  return [row + 1, column + 1]
}

In this case we're adding the required offset based on our special numbers (He, B and Al). We can now do getElementPosition(2) and it'll return [1, 18] 💪.

But wait a minute, what happens with gold? Calling getElementPosition(79) returns [7, 7]. Nope, something is definetively not working

Step 3 - Lanthanoids and actinoids

Ok, we didn't thought of lanthanoids and actinoids. Let's try to fix it with our special cases array:

function getElementPosition(atomicNumber) {
  let groups = 18
  let index = atomicNumber - 1;
  let specialNumbers = [
    [2, 16], 
    [5, 10],
    [13, 10],
    [71, -14],
    [103, -14],
  ]

  for (let [number, offset] of specialNumbers) {
    if (number <= atomicNumber) {
      index += offset
    }
  }

  let row = Math.trunc(index / groups)
  let column = index % groups

  return [row + 1, column + 1]
}

In this case instead of expanding (positive offset) we're collapsing (negative offset). Yes, it works now, calling getElementPosition(79) returns [6, 11] 🙂.

Almost there, let's go to final step

Step 4 - Minification

After using a minification service the code looks like this:

function getElementPosition(t){let e=t-1,n=[[2,16],[5,10],[13,10],[71,-14],[103,-14]];for(let[o,r]of n)o<=t&&(e+=r);return[Math.trunc(e/18)+1,e%18+1]}

150 bytes characters in total (far below 280 for a tweet). Not bad but we can still short it a bit:

g=(e=>{let r=e-1,t=[[2,16],[5,10],[13,10],[71,-14],[103,-14]];for(let[f,l]of t)f<=e&&(r+=l);return[~~(r/18)+1,r%18+1]});

By using arrow function syntax and changing Math.trunc to ~~ we've trimmed it to just 120 characters!

Conclusion

This was a great challenge, nothing too hard but difficult enough to train our brains. And we also have learned some interesting thing about this famous table 👨‍🔬

Cover image source https://www.flickr.com/photos/mindfrieze/258644767

Moving zeros

Eduardo Lanchares — Mon, 24 Aug 2020 00:10:31 +0000

Moving zeros

Last day I was thinking about all possible ways I could find to solve the following problem:

Given an array of random integers, move all the zeros in the array to the end of the array.

At first it seemed like a pretty simple problem, but the challenge also stated:

Try to keep this in O(n) time (or better)!

Ok. Things just got more interesting.

This challenge came from cassidoo's newsletter and every week, she post a new interview question. If you're not subscribed to it yet, I really encourage you to do so.

After taking some time to think about it, I came across several ways of solving the problem, going from procedural to functional styles. I thought it'd be interesting to share, so here we go:

Bubbling

This approach is based on the bubble sort algorithm and the idea is to "bubble up" zeros to the end of the array.

function moveZeros(input) {
  for (let i = 0, lastZeroIndex = -1; i < input.length; i++) {
    const n = input[i];

    if (n === 0 && lastZeroIndex < 0) {
      lastZeroIndex = i;
      continue;
    }

    if (n !== 0 && lastZeroIndex >= 0) {
      input[lastZeroIndex++] = n;
      input[i] = 0;
    }
  }

  return input;
}

We store variable lastZeroIndex which points to the last zero position. When we encounter a number which is non zero, we swap that value with the last position found.

This algorithm performs in O(n) time and is the most efficient I could came up with. It's written in procedural style and mutates the original array, but when talking about performance, mutation is usually the fastest option.

Recursion

Being a big fan of functional programming, this is my favorite one. The idea is to split input array into first and rest parts. If first item is zero, we move it to the end and delegate rest part to the next moveZeros call. If not, we just keep it at its current position.

function moveZeros([first = null, ...rest]) {
  switch (first) {
    case null:
      return [];
    case 0:
      return [...moveZeros(rest), first];
    default:
      return [first, ...moveZeros(rest)];
  }
}

Another version using pattern matching proposal:

const moveZeros = (input) => case (input) {
  when [] -> [];
  when [0, ...rest] -> [...moveZeros(rest), 0];
  when [number, ...rest] -> [number, ...moveZeros(rest)];
}

I'm obviously biased, but I find it the most readable solution of all of them. Performance is not the key point of this approach, as it creates lots of intermediate arrays in the process. Also recursion can be a problem with big arrays (though it can be solved using tail call optimization)

Grouping

This approach filters numbers in two arrays, zeros and non-zeros, then arrays are flattened into one, pushing zeros to the right:

function moveZeros(input) {
  input
    .reduce(
      (groups, number) => {
        const [nonZeros, zeros] = groups;

        if (number === 0) {
          zeros.push(0);
        } else {
          nonZeros.push(number);
        }

        return groups;
      },
      [[], []]
    )
    .flat();
}

Splice

Another one, this time using splice to insert numbers and zeros in their corresponding place. This method is partially based on how insertion sort algorithm works:

function moveZeros(input) {
  let output = [];
  let lastZeroIndex = 0;

  for (const number of input) {
    output.splice(number === 0 ? lastZeroIndex : lastZeroIndex++, 0, number);
  }

  return output;
}

Sort

And the last one, using sort. In the end moving zeros is nothing more than sorting numbers, right? Here we use a compare function that, when comparing a zero with another number, will put zero after the other number. Otherwise will preserve original order.

function moveZeros(input) {
  return input.sort((_, number) => (number === 0 ? -1 : 0));
}

This internally may use quick sort algorithm, which performs in O(n * log n)

Conclusion

One of the things I like the most about programming is the so many ways we have to solve a given problem. And with every solution, we learn new ways to approach future ones.