Forem: mari tang

sicp 1.13 - higher order functions

mari tang — Tue, 14 Jul 2020 20:58:11 +0000

Whew, the math really starts kicking in on this one. I'm working off of this lecture series alongside the book itself, and honestly, I haven't been able to finish the entire problemset, but I'm trying to keep myself on track with 2 lessons per week, so here we are.

I had a bit of trouble following Hal, since the way that these concepts are applied is geared towards solving math problems- in this case, how to calculate a square root.

I'll skip past a lot of it, but there are a few core concepts that I got out of this lesson that are a bit unrelated to the concept of higher order functions, but are implemented through higher order functions.

what is a derivative?

I'll talk about derivatives first, since that's the thing i've got the most context for.

As I understand them (from my memories of highschool calculus), derivatives are functions that describe the rate of change of another function. i.e. if you have f(x) = 3x + 5, and chart it out, you'll notice a pattern:

f(0) = 5
f(1) = 8
f(2) = 11
f(3) = 14

every time x increases by 1, f(x) increases by 3. so what's the derivative of f(x)? 3.

pretty simple so far, right? we generally use the notation f'(x) (notice the ' to denote a derivative. f'(x), pronounced "f prime of x", is a function that describes the rate of change in f(x).

I'm not going to teach you how to do derivatives the mathy way, but I'll at least say that they get more complicated as the functions you're differentiating get more complicated. for instance, we can look at the following:

f(x)  = x^2 + 2x + 5
f'(x) = 2x + 2

f(x) changes at a rate of f'(x), which makes sense, doesn't it? if we chart out f(x), it grows faster and faster as x increases, rather than growing steadily like our previous example does.

Anyways, if we want to bring it back to dealing with higher order functions, I'll put it this way: taking the derivative of a function f(x) produces a function that describes the rate of change of f(x). In other words, we can think of a derivative as a higher order function.

How do we find a derivative?

How would we figure out what that function is?

Getting the real deal is a bit... difficult / I have no idea at my level, but we can approximate it.

There's a mathematical definition for a derivative:

f'(x) = (f(x + dx) - f(x))/(dx)
as dx -> 0

this will need a little bit of explaining as well. If we think about our previous example, where we took the derivative of f(x) = 3x + 5, what were we doing?

Well, we put f(0) in, then f(1), and calculated the difference between them. f(1) - f(0). That gives us the total change between f(0) and f(1), but how do we get the rate at which it's changing? The change in total amount divided by the extent to which we changed our input will give us the answer.

Again:

f'(x) = (f(x + dx) - f(x))/(dx)
as dx -> 0

dx, thus, represents the amount by which we change our inputs. but why as dx -> 0?

We want to produce a function that is able to tell us what the rate of change is at any point in f(x), so we need a function that is continuous. The only way we get that is by using a dx that is so infinitesimally small that it's basically 0.

For the purposes of this function, though, we're only estimating a derivative, so we'll give it an arbitrary small value. something like dx = 0.0000001 will be good enough for us.

Implementation in Scheme

With all that being said, all we have to do is translate that into scheme, as follows:

(define derivative 
  (lambda (f)
    (define dx 0.000001)
    (lambda (x)
      (/ (- (f (+ x dx)) (f x)) dx))))

in this function definition, derivative is defined as a lambda function that takes in a function f, defines a dx to be 0.000001 and returns a lambda function that takes in some x and uses our previous formula to compute the rate of change in f at x. This is not a perfect answer, but it's close enough for some uses.

SICP 1.2 - Ackermann's Function and Contemplating Infinity

mari tang — Sat, 11 Jul 2020 00:23:30 +0000

Let's talk about Ackermann's function. It looks something like this

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

to describe its behavior:

if y is 0, return 0
if x is 0, return 2*y
if y is 1, return 2
otherwise, return Ackemrann's function with x = x-1 and y = Ackermann(x, y-1)

In order to evaluate it at anything besides the base cases, we're actually recursively evaluating Ackermann's function to even get the second argument. Working it out with arguments as low as (A 2 4) leads to huge numbers. (A 2 4) results in 65536, and larger numbers such as (A 4 4) are theoretically computable, but not within our lifetimes, at least with current hardware.

How do we start to deal with numbers like that?

SICP has us manually compute (A 1 10), (A 2 4), and (A 3 3), which should be enough to convince you that we're dealing with unfathomably large numbers.

I started to see some interesting patterns. (A 1 10) starts unrolling like this:

(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
(A 0 (A 0 (A 0 (A 1 7))))
....
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))

Once we hit the (A 1 1) we've finally got a base case, and it returns 2 to the parent context. (A 0 2) then evaluates to (* 2 2), which will kick one down to (A 0 4), and so on.

If the 10 just unrolls the function 10 layers deep until it finally results in a 2, and each layer is resolved by multiplying the value returned from the next layer by 2, what we've actually got is (A 1 10) = 2^10, which we can generalize as (A 1 y) = 2^y.

That's a good step, and it explains the behavior of the function for certain values, but let's dig a bit deeper. Can we do the same thing for other values of x? Let's look at the case of (A 0 y), and plug in some values so we can see what happens.

(A 0 1) => 2
(A 0 2) => 4
(A 0 3) => 6
(A 0 4) => 8

that looks like a 2*y to me!

Here's the part that blew my mind: how do we prove it?

Well, functions in comp sci are not entirely unlike functions in math. We can actually just plug in what we know- we can do partial applications of arguments and see how much we can work out. if we want to find out what (A 0 y) is, we can actually just try to evaluate it!

Let's take the body of our function and substitute 0 for x and y for y.

(cond ((= y 0) 0)
      ((= 0 0) (* 2 y))
      ((= y 1) 2)
      (else (A (- 0 1)
               (A 0 (- y 1)))))

it looks like the second conditional is being hit. 0 == 0, after all. so what does that return? (* 2 y), exactly as desired.

Let's scale it up. what if we work with (A 1 y)?

(cond ((= y 0) 0)
      ((= 1 0) (* 2 y))
      ((= y 1) 2)
      (else (A (- 1 1)
               (A 1 (- y 1)))))

what we get is:

(A (- 1 1) (A 1 (- y 1))))

which becomes:

(A 0 (A 1 (- y 1))))

Now, if (A 0 y) = 2*y, we can substitute 2*y for (A 0 y)

(* 2 (A 1 (- y 1)))

Okay, but we still have to get the second argument by evaluating (A 1 (- y 1))

(* 2 (A (- 1 1)
        (A 1 (- 1 (- y 1)))))

hmmmmmm

(* 2 (A 0 (A 1 (- y 2))))

hmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm

(* 2 (* 2 (A 1 (- y 2))))

okay, so we've seen how this unfolds, right? Eventually we'll get to ...(A 1(- y y-1)), which is ...(A 1 1). Let's see what that looks like:

(cond ((= 1 0) 0)
      ((= 1 0) (* 2 y))
      ((= 1 1) 2)
      (else (A (- 1 1)
               (A 1 (- 1 1)))))

((= 1 1) 2)

well, 1 == 1, no?

...(A 0 (A 0 (A 1 2)))

which becomes

...(A 0 (A 0 2))

and finally

...(A 0 (* 2 2))

Each of the (A 0 ...) becomes 2 * (whatever the rest is). What do we call it when we multiply by the same number a bunch of times? exponentiation! we're doing n*2 y times, so that's 2^y!

You can scale up to (A 2 y), which ends up being the next order higher, raising 2^2^2... y times.

so why all of this? Ackermann's function does a few interesting things. each X is one level "up" from the previous (constant -> multiplication -> exponentiation -> exponentiation of exponents), which i find abstractly really fascinating.

On more practical levels, it gives us insight into how we can understand super-exponential growth through recursion, how we can think about a function that grows at a nearly unthinkable rate.

What I learned today (SICP 1.1)

mari tang — Thu, 09 Jul 2020 22:34:42 +0000

Sadly, this series is not written for anyone except me, as a way of tracking my progress while I teach myself some computer science fundamentals. You've been warned.

I'm working through the venerable SICP, using the book and this playlist and doing the exercises in the book as homework. Today I've covered chapter 1.1

I'm using Jupyter Notebook with the MIT-Scheme-Kernel via a docker image. I've had to do a bit of digging to understand how to get it to persist, though. Here's a script I wrote to run the notebook, forward port 8888 (the one used by Jupyter), and persist the notebooks that I make at whatever you fill in for <host filepath>

This is, of course, assuming you've got docker installed. it'll handle the rest.

#!bin/bash

docker run --rm -it -p 8888:8888 -v <host filepath>:/work kkwok/jupyter-mit-scheme

So, what did I actually learn today?

We did an exercise where we built a function to do an approximation of the value of a square root. The initial version of this would start from some arbitrary guess, check if guess * guess is within some proximity of the number we're trying to sqrt, then improve it if not, and try the whole process over again.

One thing I learned was that we're making implicit assumptions about the problem when we decide on the threshold for a "close enough" guess. If we want the guess to be within 0.001 of the real target, well- what if our number is huge, like 123801983120? It'll take forever to get close enough to be within 1 of the target, let alone 0.001! Same goes for small numbers. If we're trying to find the square root of 0.0001, any number we guess will probably always be within the threshold, making it worthless!

So, what do we do? the answer is that we look not at an absolute closeness, but a relative closeness; what percent does our guess change? That'll scale regardless of whether the number itself is actually big or small. Brilliant.

Okay, so now that that's out of the way, what else is there to learn?

The sqrt function we wrote is composed of a couple of different pieces. it's composed of sqrt, the "main" function, and its dependencies close-enough? and improve-guess, which check if we're close enough to the target, and get us closer to our target respectively.

the main sqrt function itself- if you think about it, all of the domain specific stuff for finding a square root is encapsulated in close-enough and improve-guess, which are what determines where the number goes and when it's there. That's a process that isn't about square roots. it's about iterative approximation.

The last exercise of ch 1.2 was to build a cube root approximation function. we were given (x/(y^2) + 2y)/3 as a formula for improving a guess at a cube root, when we're trying to get to y^3 = x

All that we actually need to do is replace the improve-guess function with one that carries out this process, and it frickin' works.

Distributed Systems: The CAP Theorem

mari tang — Thu, 08 Aug 2019 14:24:47 +0000

So, I'm gonna start talking about distributed systems, as I learn them. I'm starting with the CAP theorem, which seems like a central consideration in designing distributed data stores (DBs with sharding).

This is mostly a summary of other sources, particularly Coda Hale's fantastic article

The three parts of CAP are as follows:

Consistency: Every time we try to read data from the database, we'll either get the most recent data, or nothing. (This is different from ACID consistency, which is about maintaining compliance with a schema/table structure)
Availability: Requests receive data in response (pretty much no matter what, without any assurance that the most recent data will be sent out)
Partition Tolerance: This one basically means that it works over a network / can function despite messages being dropped, truncated, delayed, or otherwise damaged by the network

Essentially, we take Partition Tolerance as a given- We can't really have a distributed data store without being reliant on a network, and it gets definitionally not-distributed if we give this one up. People are going to accidentally cut wires, or EMPs will happen, or the power grid will go down. We can't have a distributed system at all without having to consider these hiccups.

So the choice becomes this: When the network takes down one of our nodes, do we still accept requests, sending back partial (or not-fully up to date) data? Or do we wait for everything to come back online, reconcile any writes that might have happened in the meantime, and not send data until we know we're good to go?

Of course, it's not completely cut and dried. Stonebreaker makes assertions about CAP that, frankly, I'm not quite qualified to talk about. It seems like his concern is that availability isn't a real thing, and that single node failures can happen while maintaining consistency, without disruption to availability.

To summarize my first point, the CAP theorem assumes reliable applications, reliable DBMS, reliable humans and no change in resources. Unfortunately, these are all issues, which must be considered. In addition, modeling node failures as network partitions leads to an obviously bad conclusion.

Obvious to who? Probably someone more well-versed in DBs than I. Regardless, Stonebreaker ends up clarifying that it doesn't make much sense to "give up" consist.ency, since a sufficiently screwed up network will kill your application anyways. It's not infrastructural failure, but human error, bad actors, and glitchy code that are the real, frequent sources of downtime.

Hale responds with some stories, though:

Multi-node failures may be rarer than single-node failures, but they are still common enough to have serious effects on business. In my limited experience I’ve dealt with long-lived network partitions in a single data center (DC), PDU failures, switch failures, accidental power cycles of whole racks, whole-DC backbone failures, whole-DC power failures, and a hypoglycemic driver smashing his Ford pickup truck into a DC’s HVAC system. And I’m not even an ops guy.

Ultimately, I do somewhat lean towards Hale's perspective, and it's essentially this: There are usually tolerances for consistency, and eventual consistency is good enough a lot of the time. Losing availability means losing money, and that's ultimately what determines the requirements of most systems, so that's what we need to prioritize.

(As an aside, I'm also really tickled by the names of distributed systems - CockroachDB, and Project Voldemort are particularly funny names to me)

Further reading:
https://www.microsoft.com/en-us/research/wp-content/uploads/2011/10/ConsistencyAndBaseballReport.pdf
https://codahale.com/you-cant-sacrifice-partition-tolerance/
https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html
https://en.wikipedia.org/wiki/Consistency_model

Adventures in BLE with Node

mari tang — Tue, 06 Aug 2019 19:24:11 +0000

Out of curiosity, I decided that today would be the day I set up a node server that can control my YN360 (a Chinese LED wand meant for photography), so that I can start using it as an alarm clock, a remote light that I can turn on and off, a notification light, or to do fancy programmatic things for interesting videos/photos.

My plan is to have a node server running on my Thinkpad x230 (which I'm gradually growing into a home server). I found that the x230 has a bluetooth chipset that can at least recognize my YN360, so hopefully it'll be able to write to it as well.

I'm kinda stuck at the moment, so writing this blog is part of my debugging process.

BLE

As far as I can understand from the official documentation, a BLE device basically has a series of attributes, which come in a few different flavors: Services, Characteristics, and Descriptors.

A Service is a set of related Characteristics, which may represent a specific feature of the device (i.e. one Service might hold device info). Characteristics are current data that has to do with either internal state or external state as measured by a sensor.

The LED brightness / state of the YN360 should be handled by Characteristics, so we won't get further into it than that. Instead, let's talk about the YN360-specific stuff I found.

YN360 hardware

On the YN360 side, I learned a lot from Samuel Pinches's excellent blog, but the main takeaways were that the YN360 takes a few commands that determine which LEDs to turn on and to what brightness.

0xAEAA01XXYY56 will turn on the white LEDs, where the cold LEDs have a brightness of XX and the warm LEDs have a brightness of YY.
0xAEA1RRGGBB56 does the same for the RGB LEDs, with RR being the red value, BB being blue, and GG being green.
0xAEEE00000056 turns off the light (but even when off, it'll still listen for BTLE commands)

I fired up LightBlue (android, iOS) to do a bit of investigation into the device.

I found a service with a UUID of f000aa61-0451-4000-b000-00000000000000, and within that service, I found two characteristics: f000aa63-0451-4000-b000-00000000000000 and f000aa61-0451-4000-b000-00000000000000. I'm not sure exactly what this means, but I noticed that the latter (starting with f000aa61) supported writes. After sending it AEAA01999956 (white LED string with a brigthness of 99), the light actually turned on!

Now, the goal is to get Node to send the signal, so that I can have routes on my home server to interact with the light over my local network.

node

NodeJS was a bit harder, and I still haven't got it fully running yet. I found a library called noble, which refused to install on my machine. The last commit was made on Jun 7, 2018. Luckily, there's an abandonware fork of it that was last updated on April 15, 2019. Luckily this one installs, and it was even able to detect my YN360 with a scan!

The flow is something like this:

discover device -> connect to device -> find services -> write to the appropriate service. The discover, connect, and discoverAllServicesAndCharacteristics methods are all callback-based, so they'd have to be nested inside of one another, or defined as named functions in an effort to reduce nesting.

I've gotten up to the point where I've found 2 Characteristics that can be written to. One has a name of 'Device Name', which I'm assuming ain't it. The other has an undefined name. By checking UUIDs, I can see that it matches the UUID of f000aa61-0451-4000-b000-00000000000000 (without spaces), which should refer to the Characteristic we need to write to.

The last bit, now, is to try to actually write to the dang thing, then refactor my code into a more modular shape.

what's the first website/project you made?

mari tang — Tue, 30 Jul 2019 17:54:57 +0000

I'm in the interview process for my next tech job, but I figured I'd stop to look back a bit. The earliest bit of web development I can remember was my Angelfire site. It's a static site that I built at the tender age of 11, all the way back in 2005.

It wasn't always orange- I had a cool tiled black-and-green matrix-style background (it was an animated GIF as well!) until link rot killed it. There were also a bunch of embedded pieces of code from other sites that were supposed to add different animations or sounds, none of which really work any more anyways. The whole thing is written solely in HTML, with some inline styling.

It was super fun making it, and both embarrassing and fun to look at it again, now that I'm a proper MERN stack developer working with all kinds of high-tech containerization and automation tools.

Do any of y'all have old projects you'd like to share?

Algorithms: Range Sum Query

mari tang — Sun, 14 Jul 2019 22:56:03 +0000

It's algorithm time again!

This one's a leetcode easy, but there's a lot to be learned from it.

Here's the problem:

RANGE SUM QUERY:

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

So, if we have an array of, say [1,2,3,4,5], and indices of 2 and 4, we'd add 3 + 4 + 5 to get 12.

Pretty simple, right? We can just loop over our array and sum up whatever's between (and including) the indexes we get.

function NumArr(arr){
  this.data = arr;
}

NumArr.prototype.rangeSum = function(i, j){
  let output = 0;
  for(i; i<=j;i++){
    output+=this.data[i];
  }
  return output;
}

This is not a horrible solution. If we query our array only once or twice, or if we expect to get in a variety of arrays, this works. Computers are very good at addition-it's possibly the fastest operation a CPU can do. In fact, it's so fast that it actually does pass the leetcode tests.

However, there are two stipulations provided, which give us space to improve and optimize our solution.

You may assume that the array does not change.

There are many calls to sumRange function.

So, let's think about how this works. If we're doing a sufficient number of sums, some of them will probably hit the same range, right? We can cache our solution and look it up instead of re-calcluating it. Let's put a cache on the constructor.

Caching

What shape should the cache take?
If we think about it for a minute, a two dimensional array seems to make the most sense- we're adding a range from i to j, so we can dump our cached results at this.cache[i][j]

function NumArray(arr){
  this.data = arr;
  this.cache = arr.map(()=>[]); //fill cache with one empty array per item in arr
}

NumArray.prototype.sumRange = function(i, j){
  if(!this.cache[i][j]){
    let output = 0;
    for(let k = i; k<=j;k++){
      output+=this.data[k];
    }
    this.cache[i][j] = output;
  }
  return this.cache[i][j];
}

This works, but the extra task of storing stuff in our cache makes the initial query to a range much slower. Each successive time we query is gonna be plenty fast, but it also counts on us landing on our exact range again.

Is there an even better solution?

Short answer: yes. very yes.

Getting there was a bit of a pain. Initially, I'd glanced at the leetcode solution and saw something about precomputing the results. I took this to mean that we should pre-calculate and cache the entire thing- and why not?

If we're computing any range sum, we're doing repeated work. i.e. if we sum the values from index 0 to index 5, we've calculated arr[0]+arr[1], arr[0]+arr[1]+arr[2], etc etc. This means that we can simply cache some of those intermediary values as we go.

I could intuit that I could at least get the first set of sums like this:

function NumArray(arr){
  this.data = arr;
  this.cache = []
  arr.reduce((acc,val)=>{
    acc += val;
    cache.push(val)
    return acc;
  },0)
}

When this finishes computing, our cache will be an array with all of the sums from 0 to n. [(sum of index 0), (sum of index 0 to index 1), (sum of index 0 to index 2), ...., (sum of index 0 to index n)]

That's a nice little bit of computation that makes our lives easier, but how would we think about getting all of the sums of index 1 to index n, then index 2 to index n, all the way up to index n-1 to index n?

I tried to figure out if there was an easy way to compute all possible sums, but kept getting O(n^2) solutions that would time out on leetcode.

So I tried to figure out what sort of patterns I could see in a test case, modelling it by hand with a very simple array of [0,1,2,3,4]

There are a few interesting things going on. We can see that each successive row is basically made by taking the previous row and subtracting whatever integer we're skipping.

The first row is made by summing all numbers.
The second row can be made by taking the first row and subtracting the first number
The third row can be made by taking the second row and subtracting the second number
The fourth row can be made by taking the third row and subtracting the third number
...and so on.

It took a bit for this to sink in, but the secret here depends on rearranging that previous insight:

In other words, we can find any range from i to j by taking the sum of numbers from index 0 to j, and subtracting the sum of numbers from index 0 to i.

With this being the case, all of the data we need is created when we make our initial pass. We're guaranteed to have the appropriate sum for index 0 to i, and likewise, for index 0 to j. We don't even have to cache every possible answer to have an O(1) operation.

Here's what my final result looks like:

const NumArray = function(nums){
  this.cache = [0]; // done to avoid an "if" check for the first number
  for (let i = 0; i < nums.length; i++){
    this.cache.push(this.cache[i]+nums[i]);
  }
}

NumArray.prototype.sumRange = function(i,j){
  return this.cache[j+1]-this.cache[i];
}

This saves immensely on time complexity- Our initial pass through the array is O(n), which is the same time complexity as calculating a single range sum in the first place (i.e. if you want to sum from 0 to arr.length-1). Afterwards, getting any successive answers is an O(1) operation!

The only real tradeoff is that the space complexity of this solution is also O(n), but it's well worth it.

Algorithms: Closest to TwoSum

mari tang — Fri, 05 Jul 2019 08:28:19 +0000

Today I was introduced to another algorithm. It was framed to me as similar to TwoSum, but with a major caveat- Rather than figuring out if/which two numbers in an array added to a target number, it asked to figure out the two numbers that summed closest to the target.

If that's not immediately clear, let's look at an example case.

If we have a set of [1,5,12,6,13], with a target of 12, the closest we can get is either 1+12, which is 13 (distance of 1), or 5+6, which is 11 (also distance of 1).

It's not too hard to do it in O(n^2) time. We can just compute all possible sums, and either compare them at the end (O(n) space complexity), or maintain a lowestDistance value that we update as we continue to navigate our array (O(1) space). That might look something like this:

function closestTwo(arr, target){
  let lowestDistance = Infinity;
  let nums = [null, null];
  for(let i = 0; i < arr.length; i++){
    for(let j = i+1; j < arr.length; j++){
      const sum = arr[i] + arr[j];
      const dist = Math.abs(target-sum);
      if(dist<lowestDistance){
        lowestDistance = dist;
        nums[0] = arr[i];
        nums[1] = arr[j];
      }
    }
  }
  return nums;
}

However, we can actually do better than O(n^2). How much better? We'll find out.

At first, I was perplexed by this; with the way that the problem is framed, I guessed that the solution might be similar to twoSum, and that it would have something to do with that type of inverted thinking. Here are a few of the routes that I went down.

We could do the twoSum thing and subtract our target from each number, storing them in a datastructure that we can check quickly, like a Set.
- However, if we're talking about being "close", rather than spot on, we can't fuzz the thing we're going to give to our .has()- I want to delimit it by a certain range, but even the closest number could end up being very far from our target, and if we have to check each step in the range, it ends up being extremely slow.
We could sort the array. it's O(nlogn), which would make the behavior of the array more predictable
- But how do we find a solution from there? Perhaps a binary search is possible?
- If we do a binary search, how do we know what we're looking for?

Well, the sort and binary search kind of actually works. It's still not the fastest, but we can do it in O(nlogn) time, which is the best time complexity I've gotten so far, even though it can be optimized further.

Here's how this approach works:

Start one pointer at the beginning of the array
Subtract it from the target sum
Whatever the remainder is, binary search through all items after it and grab the closest value you can find
Move the pointer to the next item in the array and repeat the process
Compare to previous lowest distance and keep whatever's a closer answer
Repeat until you've traversed the entire array

Let's write it.

function closestTwo(arr, target){
  arr.sort((a,b)=>a-b);
  let lowestDist = Infinity;
  let lowestNums = [null,null];
  for(let i=0; i<arr.length; i++){
    const searchTarget = target - arr[i];
    let guess = Math.floor((i + arr.length)/2);
    let lastGuess = guess;
    let lastDist = Math.abs(searchTarget - guess);
    while(Math.abs(guess-lastGuess)!=1){
      let dist;
      if(searchTarget>guess){
        guess = Math.floor((guess + arr.length)/2);
        dist = Math.abs(searchTarget - arr[guess]);
      }
      if(searchTarget<guess){
        guess = Math.floor((i+guess)/2);
        dist = Math.abs(searchTarget - arr[guess]);
      }
      if(dist > lastDist){
        break;
      }
      lastGuess = guess;
      lastDist = dist;
    }
    if(lastDist<lowestDist){
      lowestDist = lastDist;
      lowestNums[0] = arr[i];
      lowestNums[1] = arr[lastGuess];
    }
  }
  return lowestNums
}

So, this is well and fine, but it's doing 2 O(nlogn) operations. The first is that we sort it, and the second is that we're iterating through the array, plus doing a binary search for each of those iterations. That's as good as the time complexity gets, but we can tweak it a bit to do one O(nlogn) operation (sorting), and one O(n) operation.

Let's talk about how we do this.

Remember when I said earlier that the behavior of our array gets a lot more predictable after we've sorted it? Let's think about how we can use that to our advantage. If we sort from low to high, we know that the closer you are to the beginning of the array, the lower your number is, and the more you move towards the end, the higher the number is. The lowest possible sum is the two first items of the array, and the highest possible sum is the two last items of the array.

[1,2,3,4,5] has a lowest possible sum of 1+2, and a highest possible sum of 4+5- but how do we figure out the stuff in between? The magic of it is that we can do so by moving around a couple of pointers, which will inevitably converge to the closest possible sum. The way that we ensure that we're moving closer to the desired solution is that we'll use two pointers- one at the start and one at the end of our array. Here's how it works:

Sort the array
Put a pointer at the beginning of the array
Put a pointer at the end of the array
sum the two values we're pointing at
Is our sum higher or lower than the target?
If the sum is too high, move the end pointer to the next lowest item. If it's too low, move the low pointer to the next higher item
Find the sum of the two values again
If that sum has a higher distance than the last sum, return the previous values
Otherwise, continue the process.

Here's what that looks like:

function closestSum(arr, target){
  arr.sort((a,b)=>a-b);
  let lowPointer = 0;
  let highPointer = arr.length-1;
  let nums = [null,null];
  let closestDist = Infinity;
  while((lowPointer+1)!==highPointer){
    const sum = arr[lowPointer] + arr[highPointer];
    const dist = Math.abs(target-sum);
    if (dist < closestDist){
      closestDist = dist;
      nums[0] = arr[lowPointer];
      nums[1] = arr[highPointer];
      if(sum<target){
        lowPointer++;
      }
      if(sum>target){
        highPointer--;
      }
    }else{
      break;
    }
  }
  return nums;
}

It's also not the easiest to read, but we're basically either scooching our low pointer up, or our high pointer down. We know that it's over if our guesses are getting worse, or if our pointers are directly next to each other, at which point we can simply break out of our loop and return our values.

Major takeaways:

Making comparisons and analogies is good, but don't let yourself get trapped in them - I might have been able to solve this faster if I didn't already know twoSum
An initial sort is often key to manipulating your dataset, and can provide you with valuable tools for searching it (binary search in O(logn) in particular).
There are other types of intuitions to develop about handling your dataset- I couldn't intuit that moving pointers from the outside in would guarantee full coverage of the array, but it's now clear to me that any subarray can be reached by doing so. This may prove useful for other algorithms.
This solution also works for twoSum, though the time complexity is slightly worse b/c of the sort. If the array were pre-sorted, we'd be able to do this in both O(n) time and O(1) space.

Creating and provisioning VMs with Vagrant and VirtualBox

mari tang — Sat, 29 Jun 2019 02:59:43 +0000

At my job, we've been having a lot of issues with students having misconfigured / incompatible (or annoying to set up) hardware. Dealing with PostgreSQL, MongoDB, Docker, and filesystem operations in a place where people are split between Windows and UNIX-like environments is a total pain, and WSL isn't fully mature, so I decided to prepare a VM that would allow them to develop MERN stack applications with minimal fuss. (it's here if you want to check it out or give feedback!)

I used Vagrant with VirtualBox, which I hear isn't ideal for heavy lifting- but hey, we'll use Docker if we need better performance.

The process of using Vagrant is pretty simple. You create a Vagrantfile, which defines the behavior of your VM. In my case, I want to use it for webdev, so I'm starting with an Ubuntu 18.04 installation (as opposed to a Windows one). I'm also forwarding ports 3000, 5432, 8000, 8080, and 27017, which are for web servers, except for 5432 and 27017, which are for PostgreSQL and MongoDB respectively.

My Vagrantfile looks like this:

Vagrant.configure("2") do |config|
  config.vm.box = "ubuntu/bionic64"

  # we're opening 3000, 8000, and 8080 because they're the most
  # likely to be used during your webdev process.
  #
  # if you need more ports, copy paste the examples and change the numbers
  config.vm.network "forwarded_port", guest:3000, host:3000
  config.vm.network "forwarded_port", guest:5432, host:5432
  config.vm.network "forwarded_port", guest:8000, host:8000
  config.vm.network "forwarded_port", guest:8080, host:8080
  config.vm.network "forwarded_port", guest:27017, host:27017

  # this will run initial setup
  config.vm.provision :shell, path: "bootstrap.sh"
end

I'm sure there's a way for me to loop over and forward an array of ports, but I'll work that out later. The important thing is that if we need to forward additional ports, we can do so inside of this file, following the same syntax we've already got.

So, the config.vm.box tells us what OS to use, the config.vm.network tells us how to deal with networking - but what does the config.vm.provision do? Well, to answer that question, I'll tell you about how I ended up settling on it.

Provisioning

So, initially when I installed Vagrant and spun up a VM, I was using it pretty much the same way that I used my actual Linux box. I was installing stuff on it, even using vim within the VM to edit and write code. But, one of the things that appealed to me about VMs is that they let you set up an environment exactly the way that you want it. What's the best way to go about that?

Well, one thing we can do is package our entire VM image as a box. This is a nice idea, but it means that we'll have to upload the image somewhere, and download the whole thing every time we want to get another machine set up.

The alternative to this is that we "provision" our machine automatically. Rather than packaging everything together, we can simply have a set of scripts that will automatically install our utilities when we first set up our VM. We can use a tool like Ansible for this (and I'll move over to it eventually), but I opted for a simple bash script, which is what we're doing when we see the line config.vm.provision :shell, path: "bootstrap.sh". The Vagrantfile references a bootstrap.sh script file that is simply a list of bash commands that will install and configure stuff for us.

#!/usr/bin/env bash

apt-get update
curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.34.0/install.sh | bash
nvm install node
sudo apt-get install -y npm
sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv 9DA31620334BD75D9DCB49F368818C72E52529D4
echo "deb [ arch=amd64 ] https://repo.mongodb.org/apt/ubuntu bionic/mongodb-org/4.0 multiverse" | sudo tee /etc/apt/sources.list.d/mongodb-org-4.0.list
sudo apt-get update
sudo apt-get install -y mongodb
sudo systemctl start mongod
sudo systemctl enable mongod
sudo apt-get install -y postgresql postgresql-contrib
sudo su - postgres -c "createuser vagrant"
sudo mkdir /data
sudo mkdir /data/db

As you can see, we're mostly adding PPAs and installing stuff, with the addition of a couple of operations where we're creating a user for our PostgreSQL installation and a data folder for our MongoDB. We just run vagrant up, and everything else takes care of itself.

All in all, this process is super nice, because I only have to package and pass around the Vagrantfile and bootstrap.sh script, which are only a few lines each, rather than a 500-800MB behemoth. Everything gets reliably set up, and then we're working with exactly the environment we want!

It's definitely a little bit of a process to set up (though nowhere near as involved as dual booting Ubuntu, or as expensive as buying a new computer), and I can foresee issues with getting confused about shared folders or which OS they're working in, but I'm really excited to save some of the Windows users from the nightmare of configuring their computers for a curriculum that was developed entirely for UNIX environments.

Next Steps

I'd like to dig into Ansible, and provision machines using a playbook. I'd also like to figure out if Docker is a more feasible / efficient solution to this problem (but having a full OS that defaults to an interactive terminal and being able to just keep projects in the shared folder is so much better than rewriting a docker compose file every time you want to do something else, and Docker on Windows is annoying!). I'll probably add a docker installation to it, and I'd like to dig into emulating clusters using multiple VMs (I've been meaning to learn Kubernetes, and it'd be nice to learn to deal with the complexities of load balancing across multiple pieces of hardware)

In general, I'm focusing on the backend, and dipping into the DevOps roadmap. I've really been enjoying this level of abstraction and the process of thinking about systems at scale! Now that I've had a taste of containerization and virtualization, I'd like to virtualize/containerize and try scaling some projects. I've got a Raspberry Pi cluster in the works, and want to try setting up a CI/CD pipeline and a webserver on it, with some cute extras like home automation (check out my server for doing BLE transmissions to a YN360 RGB light!).

I'm pretty excited to delve a bit deeper into this world, and am pretty excited to see what comes out of it! Any suggestions as far as what technologies I should look at next?

Redux for Buddies Pt2: writing to state

mari tang — Wed, 29 May 2019 21:14:21 +0000

Where we last left off, we had a general understanding of the Redux loop. We understood that containers provide access to our store, which we selectively use to hydrate our components' props via mapStateToProps.

As a quick refresher, here's what the general loop looks like:

store (state) -defines-> frontend -triggers-> event handler (or other functionality) -sends data/signal (action) to-> reducer -updates-> store (state)

For convenience's sake, we'll take the code we've written and replace the otherComponent we were rendering with a <p> tag that will display our userCount. With that modification, here's our code so far:

import React, { Component } from 'react';
import { connect } from 'react-redux';
const mapStateToProps = store => ({
    users: store.users.userCount // store looks like: {'userCount':5}
})

const mapDispatchToProps = dispatch =>({
    //we'll fill this in and explain it later!
})

class DisplayUsers extends Component{
    constructor(props){
        super(props);
    }
}
render(){
    <p>{this.props.users}</p>
}
export default connect(mapStateToProps, mapDispatchToProps)(DisplayUsers)

Now, to get state updates to work, we need to send data from the frontend. We'll start with that. Remember mapDispatchToProps?

Well, dispatch is what allows our frontend to send data up to the store. Let's imagine that we have a button that we want to click to add 1 to our usercount.

import React, { Component } from 'react';
import { connect } from 'react-redux';
const mapStateToProps = store => ({
    users: store.users.userCount // store looks like: {'userCount':5}
})

const mapDispatchToProps = dispatch =>({
    //we'll fill this in and explain it later!
})

class DisplayUsers extends Component{
    constructor(props){
        super(props);
    }
}
render(){
  <div>
    <p>{this.props.users}</p>
    <button onClick={/* some function */}>add user</button>
  </div>
}

So, in order to mutate our state, we need to dispatch an action to our store. Let's start by talking about what an action is, starting with how they're created.

Action Creators / Actions

An Action Creator is a function. It takes a single argument in, and returns an object which we refer to as an action. An action is just an object that has two properties on it: type and payload.

Here's what an action creator might look like:

import * as types from '../constants/actionTypes'

export const addUser = (payload) =>({
  type: types.ADD_USER,
  payload: payload  
})

As you can see, addUser returns an object that looks like this: {type: types.ADD_USER, payload: /* whatever payload we give it */}, which is the action that it is creating.

So, what is a type? and what data might we want to have in our payload?

Action Types

A type is really just a string that we're importing from our actionTypes file. By convention, the names of our actions are capitalized.

Basically, there are different types of state updates that we would like our reducers to
handle, and our type determines which one to use. We'll get into our reducers a little further down, but, for now, we'll look at what our actionTypes.js file might have inside of it:

export const ADD_USER = 'ADD_USER';

It's really just a string with a few conventions applied to it.

So, as far as why we'd store that string in a variable instead of just typing it in directly, it has to do with the reason that Redux exists in the first place: scale.

At scale, there are a few benefits to using action types. From Dan Abramov's own words:

It helps keep the naming consistent because all action types are gathered in a single place.

Sometimes you want to see all existing actions before working on a new feature. It may be that the action you need was already added by somebody on the team, but you didn’t know.

The list of action types that were added, removed, and changed in a Pull Request helps everyone on the team keep track of scope and implementation of new features.

If you make a typo when importing an action constant, you will get undefined. This is much easier to notice than a typo when you wonder why nothing happens when the action is dispatched.

it's total overkill for a project this scale, but so is Redux. That being said, we'll get to our payload

Payload

payload is the other property on our action. This is the actual data that we'll send to our reducers. (if our action needs to provide data at all- increasing our user count by 1 doesn't require any info other than action type).

We'll need to talk about reducers to really understand actions, but we'll talk about how we send actions to our reducers first.

Back To mapDispatchToProps

So, we've got an actionCreator, which returns an action, which has a type and payload. It's called addUser. Let's import it and send it to our store!

import React, { Component } from 'react';
import { connect } from 'react-redux';

import * as actions from '../actions/actions';

const mapStateToProps = store => ({
    users: store.users.userCount 
})

const mapDispatchToProps = dispatch =>({
    addUser: (e)=>dispatch(actions.addUser(e))
})

class DisplayUsers extends Component{
    constructor(props){
        super(props);
    }
}
render(){
  <div>
    <p>{this.props.users}</p>
    <button onClick={this.props.addUser}>add user</button>
  </div>
}

export default connect(mapStateToProps, mapDispatchToProps)(DisplayUsers)

There are four changes we made.

we're importing actions, as we defined above.
we're adding a property to the object returned by mapDispatchToProps, which is a function that takes in something called dispatch.
mapDispatchToProps returns an object whose properties and methods will be made available on our this.props by virtue of the next thing:
We use connect to make the properties on mapStateToProps and the methods on mapDispatchToProps available on our this.props by running a function on all of those things and exporting the results.

dispatch and store are provided by Redux, by virtue of the connect method we're importing from it. dispatch ultimately accepts an action, but in this case we're using an action creator to generate that action, providing similar benefits to using constant action types.

Now that we've done all of this, we can finally hit the reducers.

Reducers

In our implementation of Redux, we'll have an index.js file that will serve as an entrypoint for our reducers- that is, we'll import all of our reducers to index and have redux decide which ones to use. We'll also have a usersReducer.js where we'll write our functionality.

index.js will look like this:

import { combineReducers } from 'redux';
import usersReducer from './usersReducer';
const reducers = combineReducers({
  users: usersReducer
})

export default reducers

First, a note about the key name of users that we're using to store usersReducer. If you look at our mapStateToProps, we're grabbing store.users.userCount. This is why/how we shape our store, which is just an object that holds objects that hold the state associated with their respective reducer.

So, what does our usersReducer look like?

usersReducer should be a function that takes in two parameters, one of which is the state contained by our store, and the other of which is an action (such as the ones we've created with our action creators and dispatched to the store by virtue of our dispatch). The body of our usersReducer should essentially be a big switch statement that returns an object, which will comprise the new state of our store, thus completing the process.

Let's write our usersReducer. We'll create some initial state, and have our function fall back to returning it if nothing happens.

import * as types '../constants/actionTypes';
const initialState = {
  userCount: 0
}

const usersReducer = (state = initialState, action) =>{
  switch (action.type){
    default:
      return state;
  }
}

The type of an action will determine what part of the switch gets fired off. Let's add a case for when we receive ADD_USER as our type.

import * as types '../constants/actionTypes';
const initialState = {
  userCount: 0
}

const usersReducer = (state = initialState, action) =>{
  switch (action.type){
    case types.ADD_USER:{
      const userCount = state.userCount + 1;
      return {
        ...state,
        userCount
      }
    }
    default:
      return state;
  }
}

let's break down what we did here.

First, we're creating a const for userCount. We're doing this to keep our code organized, which is more of a factor when we're trying to create a new state that has multiple properties that differ from the old one. Next, we're simply returning a new object that spreads our previous state, then overwrites the old value of userCount with a new one.

We do this partially to merge our old state into our new state, and partially so that we generate an entirely new state object. In generating a new state object, we ensure that React recognizes that we've changed our state and appropriately rerenders its components. (If you need more info on why we do this, I'll write a bit about primitive vs composite data types in JS and link here later)

Anyways, now that we've handled our reducer, that's the end of the whole Redux cycle. We've written to our store!

Let's walk it through

a user clicks "add user"
"add user" fires off a version of addUser which has had dispatch mapped to it by mapDispatchToProps
addUser takes in the action returned by our ADD_USER action creator and triggers our reducers
our reducers find a matching case for ADD_USER, then generates a new state object.
the new state object gets passed back to our frontend components by mapStateToProps

And that's the flow of this particular Redux implementations. There are plenty of other ways to do it, and the value of it is only really seen at scale. Thanks for following along!

NAND2Tetris: The Magic of NAND

mari tang — Wed, 22 May 2019 06:31:41 +0000

So, I've embarked on the journey of nand2tetris.

What is nand2tetris? It's basically a vertically-integrated course on computer science. Starting from 0s and 1s, we build up a whole simulated computer, build an operating system on top of it, build a compiler on top of that OS, and finally build a game on that whole tower.

It's quite a daunting task. How do we get started?

The Magic of NAND

In computers (or, at least in the computer that we're implementing), there is a single circuit that we basically use for everything. It's called NAND. If you're familiar with boolean logic, it's defined something like this: NOT(A AND B)).

The truth table for NAND looks like this:

 A B | OUTPUT
==============
 0 0 |   1
 0 1 |   1
 1 0 |   1
 1 1 |   0

While this may seem unimpressive, our NAND gate includes behaviors in it such that we can create literally any other logic gate from some combination of just NAND gates. We won't be getting into formal proofs, but we'll demonstrate how to build NOT, AND, and OR from just NAND. (taking NAND as a given)

NOT

We'll start with NOT, since it's the simplest operation. The secret to NOT has to do with a property of AND. Anything AND itself simply outputs itself. Have a look: 0 AND 0 is 0, and 1 AND 1 is 1.

If we consider NAND to be a combination of NOT and AND, a value NAND itself will cancel out the AND, leaving the NOT operation. If we refer back to our truth table, 0 NAND 0 is 1 and 1 NAND 1 is 0. So, NOT A is A NAND A

Here's roughly what the logic gates look like. I'll represent NAND as a box with N written on it. If we've only got one input, we'll assume that it's hooked up to both inputs.

AND

Now that we've got a NOT, it's pretty easy to get to AND, for fairly self-evident reasons. A NOT inverts a value, so NOTing a NOT will cancel out the NOT, leaving the original value. ~~0 outputs 0, and ~~1 outputs 1.

NAND is NOT applied to the result of an AND, so if we cancel out the NOT, we're left with the AND operation. We've already built a NOT, and can simply add it to the output of our NAND

The operation looks like this: (A NAND B) NAND (A NAND B), but it's easier to draw a diagram.

If we have AND and NOT, it won't be too hard to derive OR.

OR

OR can be built through DeMorgan's law, which I've been lucky enough to derive myself a few months ago. Basically, we can represent A OR B as NOT ( NOT(A) AND NOT(B)).

if our NOT is A NAND A and our AND is made up of (A NAND B) NAND (A NAND B), we actually have enough to build an OR by substituting them in for their relevant terms.

This will be a mess to start, but we'll simplify it.

First, let's replace our NOTs, since they're simplest to do. NOT(A) is A NAND A and NOT(B) is B NAND B.

NOT( (A NAND A) AND (B NAND B) )

The overall NOT will take its term (A NAND A) AND (B NAND B) and NAND it with itself as both inputs. It'll come out like this:

((A NAND A) AND (B NAND B)) NAND ((A NAND A) AND (B NAND B))

Now, AND translates as follows: A AND B = (A NAND B) NAND (A NAND B). If we make our substitution where A = (A NAND B) and B = (B NAND B), this happens:

(((A NAND A) NAND (B NAND B)) NAND ((A NAND A) NAND (B NAND B))) NAND (((A NAND A) NAND (B NAND B)) NAND ((A NAND A) NAND (B NAND B)))

Which is, of course, completely unreadable. Let's represent it visually instead.

This is difficult to see in the written version of this logic gate implementation, but our last two NANDs are simply acting as NOT operators, flipping our output value, then flipping it back. We can simplify our logic gate by removing them, since ~~A is just A, no matter the value.

Now, if we walk backwards from our diagram, we can translate it back into a statement.

(A NAND A) NAND (B NAND B)

Not so bad.

We'll be building more complex systems in the future, but this is certainly a start!

Logic Gates: The Controlled Not

mari tang — Tue, 21 May 2019 06:56:04 +0000

Tonight, my brother told me the story of a particular logic gate, the Controlled Not.

The Controlled Not is a gate that takes two inputs. If the first input is 0, the second input is unaffected, and sent as our output. If the first input is 1, we invert the second input before sending it as our output.

Pretty neat, huh? Maybe take a minute to think about how to implement it from basic logic gates (not/and/or).

I've had this spoiled for me, but here's my solution.

Previously, I've created a multiplexer. A multiplexer can be described as follows: there are three inputs, a,b, and S. S is a selector, which determines whether we output A or B. If S is 1, we output A. If S is 0, we output B.

It's represented as (A*S)+(B*~S) and looks like this:

Adapting it to our use case is pretty simple. We just need to replace A and B with A and ~A. When S is true (when our controller is on), we want to flip our A, so we'll represent that operation as (~A*S). When S is false, we want to output our A unchanged, which means that we should slot it in for what used to be our B. This looks like this: (A*~S).

All together, we get (~A*S)+(A*~S), or in plainer terms, (NOT(A) AND S) OR(A AND NOT(S)). It looks like this:

Notice anything? If not, we'll do a quick truth table.

A S | OUTPUT
------------
0 0 |   0
0 1 |   1
1 0 |   1
1 1 |   0

We've got a name for this, and it's XOR.

Our takeaway is this: Even at the lowest, simplest level that we can use to try to make truth claims about the world around us- even when we've reduced everything to a collection of 1s and 0s that behave in 100% predictable ways, we're still constructing narratives around our data, still affected by the way that we choose to frame behavior, problems, solutions.

So, step back. Think about your assumptions. Think about the stories you choose to tell about your software. They matter.