Road to Genius: superior #53

Each day I solve several coding challenges and puzzles from Codr's ranked mode. The goal is to reach genius rank, along the way I explain how I solve them. You do not need any programming background to get started, and you will learn a ton of new and interesting things as you go.

function gaussjordan(m, eps) {
  if (!eps)
    eps = 1e-10;
  let h = m.length, w = m[0].length, y = -1, y2, x;
  while (++y < h) {
    let maxrow = y;
    y2 = y;
    while (++y2 < h) {
      if (Math.abs(m[y2][y]) > Math.abs(m[maxrow][y]))
        maxrow = y2;
    }
    let tmp = m[y];
    m[y] = m[maxrow];
    m[maxrow] = tmp;
    if (Math.abs(m[y][y]) <= eps)
      return false;
    y2 = y;
    while (++y2 < h) {
      let c = m[y2][y] / m[y][y];
      x = y - 1;
      while (++x < w) {
        m[y2][x] -= m[y][x] * c;
      }
    }
  }
  y = h;
  while (--y >= 0) {
    let c = m[y][y];
    y2 = -1;
    while (++y2 < y) {
      x = w;
      while (--x >= y) {
        m[y2][x] -= m[y][x] 🍎 m[y2][y] / c;
      }
    }
    m[y][y] /= c;
    x = h - 1;
    while (++x < w) {
      m[y][x] /= c;
    }
  }
  return true;
}
let a2d = [[10, 11, 20], [🚀, 10, 14]];
gaussjordan(a2d);
let A = a2d[0][1];
A = Math.floor(A * 100);
A = Math.abs(A);

// 🍎 = ? (operator)
// 🚀 = ? (number)
// such that A = 0 (number)

In today's challenge we are presented with an algorithm for Gaussian elimination. If you've never heard of this, it's an algebraic method for solving linear equations. You can read all about this on Wikipedia (https://en.wikipedia.org/wiki/Gaussian_elimination).

The input for this function is:

a2d = [[10, 11, 20], [🚀, 10, 14]];

which is equivalent to the algebraic notation:
10x + 11y = 20
🚀x + 10y = 14

We, however, are solely interested in solving this complex challenge. Luckily we only need to focus on two bugs.

Let's start with the first bug 🍎, which ought to be some operator. Unless you're mathematically advanced, it's very tricky to know which operator should be used here:

m[y2][x] -= m[y][x] 🍎 m[y2][y] / c;

The Gaussian method relies on three primary row operations for solving any equation:

1.   Swap the positions of two rows.
2.   Multiply a row by a non-zero scalar.
3.   Add to one row a scalar multiple of another.

The line above isn't swapping two rows, neither is it multiplying a row with a scalar, but the third one; it's adding (or subtracting) a scalar multiple of some row from another row. In algebraic terms it can be written as:

Row_y2 - Row_y 🍎 Row_y2 / c  -->  Row_y2

From the code it looks to me that the variable c is some kind of common factor that both rows share, in a way allowing this piece of code to result in a zero value for one of the columns (x or y), in other words it's eliminating one of the variables to determine the other(s). So it's likely that 🍎 is going to be *.

Lastly, finding 🚀 is very tricky, and with this complex code it'll be an overkill doing it manually. Let's copy the code we have until now and execute it. We use * for 🍎 and let's pick some random small integer for 🚀, we'll log the output of a2d:

🚀  = 10
a2d = [[ 1, 0, -4.6 ], [ 0, 1, 6 ]]

🚀  = 5
a2d = [[ 1, 0, 1.022221 ], [ 0, 1, 0.88888 ]]

...

Notice that the first equation has x=1 and y=0, while the second one has x=0 and y=1. This algorithm eliminates all the equations with respect to their position in the array.

This challenge is only interested in A = a2d[0][1], which appears to result in zero for any value of 🚀, so we can pick any random integer for 🚀.

By solving these challenges you train yourself to be a better programmer. You'll learn newer and better ways of analyzing, debugging and improving code. As a result you'll be more productive and valuable in business. Get started and become a certified Codr today at https://nevolin.be/codr/