The blog of dlaa.me

Posts from June 2020

Make the Pi Higher [Configuring a Raspberry Pi for Node.js and web development]

Since the beginning of the year, I've been doing all my OSS project development on a Raspberry Pi 4 running Raspberry Pi OS (née Raspbian). It's not as powerful a machine as my Intel-based desktop PC running Windows, but it's much smaller, it uses much less power, it's completely silent, and it cost about 5% of the price. To be clear, I still do photo editing on Windows and the extra speed of the PC is nice for running unit tests - but most of the time I'm perfectly happy using the Pi.

There are some great resources for Setting up your Raspberry Pi. If you want to configure it for development work like I did, here are steps that worked for me. (They assume some familiarity with Linux, but not much.)

  1. Install Raspberry Pi OS (32-bit) with desktop
  2. sudo apt update
  3. sudo apt upgrade
  4. If you want to use the Xfce desktop environment:
    1. sudo apt install xfce4 xfce4-terminal
    2. sudo update-alternatives --config x-session-manager
    3. Choose startxfce4
  5. Install the Git UI tools and configure Git
    1. sudo apt install git-gui gitk
    2. Set your username in Git
    3. Set your commit email address in Git
    4. Connect to GitHub with SSH
  6. Install a current version of Node.js
  7. Install a community build of Visual Studio Code
    1. Trust the corresponding GPG key: wget -qO - https://packagecloud.io/headmelted/codebuilds/gpgkey | sudo apt-key add -

Note: The community build of VS Code is the only part of this process that uses an unofficial release. I'd love for VS Code to support the Pi officially, but this issue from 2016 has not been addressed.

That's pretty much it! I really enjoy this minimalist configuration and find there are very few compromises with the Pi relative to a "real" computer. Plus, it's easy to swap drives (SD cards) and keep a set of different OS'es / configurations handy for experimenting and trying new things.

If you thought the Pi was just a toy, maybe it's time for another look!

Without geometry, life is pointless [Another interesting programming puzzle worked through]

I happened across another coding puzzle recently that caught my interest. (If you're curious, here is a link to the puzzle I discussed a few weeks ago about implementing a weird kind of addition.) The problem this time is as follows:

You are given an array of coordinates, coordinates[i] = [x,y], where [x,y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.

I saw an approach to solving this that didn't thrill me, so I wanted to solve it for myself.

If you're going to do the same, stop reading now because there are spoilers ahead!

As an aside, one thing I don't love about this problem is that it requires a certain amount of geometry knowledge to solve and furthermore the solution I use benefits from experience with trigonometric functions. However, one can be a perfectly good programmer without knowing either of these topics and they're not likely to come up in most roles. I try to avoid questions like this when I'm interviewing because they're likely to favor some backgrounds over others. That said, I didn't come up with this scenario and it's still interesting to think about, so let's go.

The first thing is to figure out how to approach the problem. If you remember much about linear equations, you might think to use the equation for a line to solve this: y = mx + b. If the slope, m, and the y-intercept, b, are the same for all pairs of points, then they all lie on the same line. This is helpful, but the equation starts to fall apart for points that lie on the same vertical line (for example, along the y-axis) because the slope there is infinite. Now, maybe you are comfortable dealing with infinity or risking division by zero, but I am not. That makes the vertical line scenario a special case and "special case" is often another phrase for "bug farm".

We don't want to use the slope equation, but we're in luck because there's something similar that's easier to work with: angle. Specifically:

The Math.atan2() function returns the angle in the plane (in radians) between the positive x-axis and the ray from (0,0) to the point (x,y), for Math.atan2(y,x).

That's not a solution as-is, but if we choose two points from the input and subtract the corresponding x and y coordinates, we get coordinates that define a ray in the manner described above. Now, two sets of points on line segments sharing the same angle (as calculated above) will be parallel, but not necessarily collinear. However, if we use the same point to calculate the angle to every other point of the input, that should be sufficient to determine collinearity of the set. In words:

If the angle of the line segment made up by pairing the first point of the input array with every other point of the array is the same, then we know all those rays point in the same direction and all originate at the same point (the first point) and therefore all the points are on the same line!

We're nearly there, but there's one more observation: two rays that go in exactly opposite directions from the same point are also on the same line. For example, the line segment defined by two points on a ray with an angle of 10° to the x-axis are parallel to the segment corresponding to two points on a ray with an angle of 190° to the x-axis. So instead of worrying about all 360°, we can focus on just the first 180°. The modulo operator provides an easy way to map angles between 180° and 360° into the range of 0° to 180°. (Except that the atan2 function returns values in radians instead of degrees because "Why not?" so we're going to be dealing with π.)

With all that behind us, the following algorithm should make sense. There are a few subtleties so it correctly handles empty lists as well as lists with just one point and also lists where the same point appears multiple times. In addition, it bails out as soon as it finds a non-collinear point for efficiency. Here's the code - as is the custom with JavaScript, there's no parameter validation, but this is intended to work for all valid inputs:

function arePointsCollinear(points) {
  let angle = null;
  const first = points[0];
  for (let i = 1; i < points.length; i++) {
    const current = points[i];
    const deltaX = current[0] - first[0];
    const deltaY = current[1] - first[1];
    if (deltaX || deltaY) {
      const theta = (Math.atan2(deltaY, deltaX) + Math.PI) % Math.PI;
      if (angle === null) {
        angle = theta;
      } else if (angle !== theta) {
        return false;
      }
    }
  }
  return true;
}