DEV Community: El Marshall (she/they)

Project Rambles

El Marshall (she/they) — Fri, 19 Jun 2020 20:27:59 +0000

This week I discovered this awesome program called Chingu! You join a cohort of other learning coders, and together you make a project. There are three tiers of difficulty, and the fee to join is small.

I'm excited, as it will be a great opportunity to build my portfolio and show employers some experience working with a remote development team.

Anyways, before the cohort starts (mine is slated for 6/29), you have to complete and submit a small solo-project, to show your chops and help make sure you've placed yourself in the right tier. You can submit something you've already made, but I thought it would be a good opportunity to get some practice in, so I decided to make one of their suggested starter projects. I chose the matching game - that classic memory game where you flip cards two at a time to find matches.

It's a pretty simple application, but is still stretching my coding muscles nicely. I decided to use React, since I like it, and the 'cards' seemed to lend themselves to it nicely.

Here's what it looks like so far:

It still needs work before I'll be satisfied with its appearance, but for now I'm pleased to say it's got basic functionality!

The components are pretty simple - There is only the main App, then a Board, and inside of that, Game Cards. Once you start building out the functionality, it's surprising how many little details you need to account for.

I have state (through React Hooks - really glad to have learned them!) keeping track of the order of the cards, because they should be shuffled for each new game. State keeping track of which cards are flipped and which cards are matched. State tracking number of turns taken, and state that tells the board when to make cards un-clickable, so that users don't click on more cards while the system is assessing their choices.

For the animation to flip the cards, I decided not to reinvent the wheel and looked up who might have made such a functionality for React already, and indeed was able to find a plug-in pretty easily. I believe it's just called ReactCardFlip.

I don't have a super concrete or coherent point to make about this project, there isn't, for instance, a super specific and interesting bug I've overcome. Mostly it's been an exercise in keeping my JS/React skills sharp and puzzling out what level will be best to keep different pieces of state in.

I'm excited to get the final functionality (such as notifications for a win or loss, and maybe a timer) working, and to get it prettied up. I'll be taking the opportunity to learn some more about dynamic sizing.

But I'm even more excited to start Chingu in a couple weeks!

Sessions and Cookies and (local)Storage, Oh My!

El Marshall (she/they) — Fri, 12 Jun 2020 22:29:02 +0000

Cookies, Sessions, and LocalStorage are all methods of storing data client-side, and specifically on the user's browser. Why do we have so many different versions? Do I need to know them all?? They are all super similar, but do have key differences that make them useful for different purposes. It's important that you understand the benefits and limitations of each so that you can choose which is most appropriate to use for any given application.

Cookies are a much older concept than either Sessions or LocalStorage, and are also much more limited in size. This is because the entirety of a cookie is actually passed back to the server with each request. You can see why you need to keep them small!

LocalStorage and Sessions are much closer to each other than either is to Cookies. They use similar setting and access methods, and can store similar sizes of information. In fact, there's really just one big thing that distinguishes them from each other: Sessions data is isolated to the current tab or window. As soon as you close that tab or window, the information goes away. This is why it's referred to as "Sessions." LocalStorage data, on the other hand, will persist across multiple windows and tabs of the same browser (as will cookies).

We saw above that Session data persists so long as you have that "session" open. LocalStorage will persist indefinitely, until the user or the program deletes it. Cookies have an expiration set by the code. They can be set to expire anywhere from just a few seconds or minutes down the line to a date so far in the future that it is essentially indefinite (such as the year 9999).

So to sum up:

Consider these differences when implementing any kind of browser storage. Cookies are great for password tokens when you want a user to be logged out after a period of inactivity, for instance, while localStorage is good when you want a user's password and username info to stay put, allowing them to be automatically logged in on every visit. Sessions are good if having multiple pages of the same content up might mess with the running of your program.

How to actually set and access all these methods are really quite simple, but not something I'm going to go over here. This video lays the high level basics out pretty clearly.

Hopefully this serves as a clear and concise resource for someone!

EDIT: Also worth noting are the varied security risks. It's not a good idea to use Local Storage for sensitive info such as user passwords, for instance, since it's vulnerable to xss attacks.

Recursion and Space Complexity

El Marshall (she/they) — Fri, 05 Jun 2020 21:40:41 +0000

When I was first reading up on recursive solutions to algorithms, I kept hearing about space complexity and the call stack, and at first had no idea what was up. It's turns out, it's actually pretty simple! I'm hoping this post can condense into one spot what was a disparate learning experience for me.

Let's define some things first.

What is recursion? Honestly that one is worth a blog post (or a few) in itself, so if you're not already familiar with how recursion works, I recommend you read this excellent rundown or find something similar to help you understand, as I'm not going to be going into it fully here. I'll wait.

You back? Okay cool. Next, what is Space Complexity?

Space complexity in algorithm development is a metric for how much storage space the algorithm needs in relation to its inputs. -Technopedia

So if my solution to an algorithm involves creating two hash-tables, my space complexity is going to be a lot higher than if it only involves creating a single primitive variable.

Finally, what is the Call Stack?

In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. - Wikipedia

Translation, it's how many tasks the system is juggling at once.

With recursion, every time you call the function recursively you add one more function to the call stack. Until you hit the 'bottom' and start traveling back up or out, you're adding one each time. Now suppose that your function requires establishing a variable. That variable is being established anew every time you call the function.

It goes like this. You have a function that requires that 2 rocks be balanced in your hands. Every time you call the function, you add two more rocks to your pile. You can't start putting rocks down until the function they are for finishes. Because of the nested nature of recursion, you're doing a lot of things at once, and so that pile is going to grow bigger and bigger and may get pretty unwieldy and heavy.

That pile of rocks is your space complexity! The more levels of recursion you have, the higher it will get. You're going to get better performance out of your machine the fewer functions you've got going.

Recursion is really neat, and can lead to some beautifully simple code, but it definitely has its drawbacks.

JavaScript: typeof null

El Marshall (she/they) — Fri, 29 May 2020 21:17:09 +0000

The thing about programming languages is, they aren't facts of the universe, they were made by people, sometimes very quickly. This means that they are often full of little quirks and oddities. Some cause problems, some don't, some we can fix, and some we have to learn to live with.

One such example is what some would call the typeof null bug.

So what am I talking about? In JavaScript, there are primitive values, and objects. Most value types fall under the heading of primitive, such as Number, String, Boolean, Null, and Undefined. An object, on the other hand, is more complex, being typically thought of as a collection of properties.

Null is a primitive value, and has only the one possible value: null. But take a look at the following code, and make a guess about what it would output:

let x = null
console.log(typeof x, x === null)

Based on what I've said above, you would likely expect to see null, true. typeof returns the value type, and === strictly evaluates equality. x is null, so we'd expect to get null, and true.

Logical. Unfortunately, what you actually get is object, true.

That's right, null is an object... But doesn't that seem off?

Well, this is due to a quirk of the way null was defined in the early days of JavaScript, and can’t be altered at this point. It comes down to the way the creators of JavaScript defined types, and how this interacted with common representations for NULL on most platforms. This post sums it up nicely:

In the first implementation of JavaScript, values were represented in two parts - a type tag and the actual value. There were 5 type tags that could be used, and the tag for referencing an object was 0. The null value, however, was represented as the NULL pointer, which was 0x00 for most platforms. As a result of this similarity, null has the 0 type tag, which corresponds to an object.

The upshot of all this is, if you're writing a function and you need to check whether or not a value is null, you’ll need to use the === operator, not typeof, if you want to get accurate results.

While I confess to lacking a great deal of the context for why this happened, it fascinates me that it did. I love getting little glimpses into the past that clear up why things are the way they are today. Sure, it may cause some confusion and I may grumble when it causes a hitch in my programming, but it helps me remember that ultimately, everything we do we do as people, in conversation with people past and present. Maybe I'm sappy, but as a social psych major I just think that's neat.

Algorithm Time: Secret Number

El Marshall (she/they) — Fri, 22 May 2020 22:19:04 +0000

or: Technical Interview Take Two

I had an interview this week (yay!) and worked on two different algorithms. With the second one, I felt that I rushed things due to my nerves, and while I got a working solution, it didn't sit right with me. I felt I could do better, especially since I ended up with a time complexity of O(n²). I was sure I could get it lower.

Here's the scenario: I'm thinking of a secret number that is n digits long. You can guess what number I'm thinking of, and I'll tell you how many digits in your guess were exact matches to my number, and how many were partial matches. An exact match means that the number and position were both correct. A partial match means that that number appears somewhere in my secret number, but not where you put it.

So for example, if my secret number is "1243" and you guessed "1235", there would be 2 exact matches (1 and 2) and one partial match (the 3).

The challenge is to write a function that takes in the secret number and the guess as parameters, and prints the number of exact and partial matches. You can assume the guess will always be the same length as the secret, and you can assume the strings won't ever be empty.

Take 1

Below is the code I worked up during the interview, or as close as I could recreate it from memory.

function guesser(secret, guess) {
  let partial = 0;
  let exact = 0;
  let sArr = secret.split("");
  let gArr = guess.split("");

  for (let i = 0; i < sArr.length; i++) {
    if (gArr[i] === sArr[i]) {
      exact++;
      gArr.splice(i, 1);
      sArr.splice(i, 1);
      i--;
    }
  }

  for (let i = 0; i < sArr.length; i++) {
    if (sArr.includes(gArr[i])) {
      partial++;
      sArr.splice(sArr.indexOf(gArr[i]), 1);
      gArr.splice(i, 1);
      i--;
    }
  }

  console.log("exact: ", exact, "partial: ", partial);
}

Let's run through the basics. sArr and gArr are arrays of the characters in secret and guess respectively. This was done to make the data easier to work with.

The first loop runs through the secret array and compares each character to the character at the same index in the guess array. If they are the same, we tick up our exact match counter, and remove the character from each array so we don't repeat it later. We also need to decrement the index counter (i) by one to make up for the fact that we just shortened the array and prevent our loop from getting out of sync.

The second loop runs through the guess array. For each character, it checks whether or not that character is found in the secret array. If it is, same deal as before, we increment the partial match counter, remove the characters from the arrays, and decrement i.

This solution works, but it's not the fastest. At a first glance I was inclined to call it O(n) but my interviewer pointed out that you have to take the .splice and .includes methods into account. Those methods work by looping through an array to find what you've asked for. An absolute best case scenario, where what you're looking for is always the first element, may end up being O(n), but most of the time that's not going to happen. So in actuality, this solution has a time complexity of O(n²). Space Complexity is O(n), because of the arrays.

Take 2

I was pretty sure I could use a hash to simplify the solution, so I pursued that angle. Here is what I ended up with:

function guesser(secret, guess) {
  let partial = 0;
  let exact = 0;
  let sHash = {};
  let gHash = {};

  for (let i = 0; i < secret.length; i++) {
    if (secret[i] === guess[i]) {
      exact += 1;
    } else {
      sHash[secret[i]] ? sHash[secret[i]]++ : (sHash[secret[i]] = 1);
      gHash[guess[i]] ? gHash[guess[i]]++ : (gHash[guess[i]] = 1);
    }
  }

  for (char in gHash) {
    if (sHash[char]) {
      partial++;
      sHash[char]--;
    }
  }

  console.log("exact: ", exact, "partial: ", partial);
}

Right away, there's no need to split the strings into arrays. Instead of creating an array of characters that we remove from as we go, we will store any characters that were not an exact match in some new hashes, with a count.

Then for the second loop, we check each character left in guess and see if it appears in the hash of secret's leftover characters. When we find a match, we increment the partial match counter and we decrement the count for that character in the secret hash. That way we avoid duplicate matches. In fact, we don't even need to set up any logic to check whether the count is above zero. Since 0 is "falsy" in JavaScript, simply calling on s[char] in a conditional will tell us if the number has dropped to zero.

Comparing the Two

Now to compare these two solutions. Space Complexity stays the same, at O(n). If there's a way to reduce it, I haven't done enough puzzling to find it.

Time complexity, though, is another matter entirely. Using this hash method, I have cut out the use of both .splice and .includes. A call to a hash (at least a very simple one like this) takes constant time, so we've dropped our total time complexity down to O(n)!

Algorithm Time: Minimum Swaps

El Marshall (she/they) — Fri, 15 May 2020 23:23:26 +0000

Today I'm going to dive into my solution to HackerRank's "New Year Chaos" problem, written in JavaScript.

I found this one rather challenging to wrap my head around, and none of the solutions in the 'discussions' section were as thorough as I wanted them to be. The closest is this one, but it was in a language I'm not as familiar with, and could use some more breaking down.

So here we go. The setup is like this: There are a bunch of people waiting in line, each assigned a number, beginning with 1 at the start of the queue, and so on. This can be represented simply with a row of numbers like this:
1 2 3 4 5 6

Before the event, each person can choose to bribe the person in front of them to swap spots, so that they can move up. Each person can do this up to 2 times. So say person 3 bribes person 2, the queue will now look like this:
1 3 2 4 5 6

That's the setup, here's the challenge. You are provided with a list of numbers representing a queue of people that has undergone this bribing process. Your job is to return the minimum number of swaps required to get the line to that state. Or, if that state is not possible, to return "Too Chaotic."

First let's handle the "Too Chaotic" condition, since that's simplest. If a person has ended up more than two spots closer to the front, you know it's too chaotic. They cannot bribe more than twice, and people can't bribe anyone behind them, so they can only move forward on their own bribes. Here's an example of an input that's too chaotic:

1 5 4 2 3 Person number 5 doesn't have enough bribes to get that far up!

Figuring out the minimum bribes is quite a bit trickier. Tallying how many people have moved won't work, because a single transaction moves two people. Counting how many bribes each person has made won't work for similar reasons. What you can do, however, is count how many times each person has been bribed, and add those up.

In 1 2 5 4 3 for example, 3 has received two bribes, 4 has received one, and none of the others have received any. We know this because among the people just to the left of 3, there are two numbers higher than 3. To the left of 4, only one number is higher. Adding up the counts, we get a minimum bribe count of 3.

It is possible that a couple more bribes than this happened, of course, and in the final standings you cannot see them. For instance, perhaps 2 bribed 1, but then 1 bribed 2. However, since we are only interested in the minimum number of swaps necessary, we don't need to worry about those circumstances.

So how do we turn this into code? Let's take it one step at a time. First, we'll initiate our bribe count at 0. Next, we know we'll need to loop through each person in the list to find their count, so let's set that up.

function minimumBribes(q) { // q is our... queue! In the form of an array.
    let minBribes = 0;
    for(let i=0; i < q.length; i++){ 

    }    
    return minBribes;
}

We will need to check each person to see if their position means our queue is too chaotic. If their number is more than 2 higher than their position, they've moved too far.

function minimumBribes(q) {
    let minBribes = 0;
    for(let i=0; i < q.length; i++){
        if (q[i] - 3 > i){ //It's -3 not -2 here because 
                           //our queue starts at 1
                           //while our array index starts at 0
            return "Too chaotic"
        }
    }    
    return minBribes
}

Next, we'll need to add one to our minimum bribes count for every time someone was overtaken. Once we add that in, the function is complete:

function minimumBribes(q) {
    let minBribes = 0;
    for(let i=0; i < q.length; i++){
        if (q[i] - 3 > i){
            console.log("Too chaotic")
            return
        } else {
            for (let j = Math.max(0, q[i]-2); j < i; j++){
                if (q[j] > q[i]){
                    minBribes++
                }
            }
        }
    }    
    return minBribes
}

But there's a lot going on there, so let's break it down. Here's just the internal loop:

for (let j = Math.max(0, q[i]-2); j < i; j++){
                if (q[j] > q[i]){
                    minBribes++
                }
            }

Remember that i is the position of the person we are currently considering, the one receiving bribes, the bribee. j represents where we begin examining the line to see who has bribed our bribee. The briber cannot move further than one position in front of the bribee's original position. On the first bribe, they take the bribee's position, on the second bribe, they move one past it. So, we only need to look two positions to the left of i. (Theoretically this would work with simply j=0, but that bumps our run time from O(n) up to O(n²). This cut saves us quite a bit of runtime.)

So what's this Math.max(0, q[i]-2) nonsense? Looks complicated, but all it's doing is protecting us from accidentally entering a negative index. j will be set to whichever is larger, 0 or 1 before the bribee's original position (it's -2 to account for the one-indexing).

The loops end condition is j < i. We only need to look at people to the bribee's left.

Now, if any of those people have a number higher than our bribee (if q[j] > q[i]), we know they must have bribed them to get there, so we add one to our minimum bribes count (minBribes++).

And that's it! This may still not be terribly clear, but I'm hoping that I've been able to explain each piece well. I really wanted to understand both how this worked, and why it worked, so I'm glad to have taken this time to write it out.

Too Many Languages

El Marshall (she/they) — Fri, 08 May 2020 21:27:55 +0000

The thing about job hunting in the tech field is, everyone wants a different set of languages. Job A wants someone with Node and React, Job B wants someone with C#. Job C wants a WordPress expert and Job D wants Rails.

If you wanted, you could learn a little about absolutely all the languages out there, running yourself ragged making sure you have exposure to every possible language. But I sincerely doubt that's really going to up your chances of getting hired. There's just no way to learn everything, and I think you'd be poorer off than when you started.

I am, quite obviously, not an expert here. But here's what's working for me, in terms of keeping me engaged and learning, and giving me a sense that I am doing worthwhile things during my job hunt.

Pick just a couple languages and learn those deeply. What this looks like for me is investing time in a project or two that can be enhanced by me improving my knowledge of a language. For instance, I recently decided to throw together a little two player online game, and it's given me the opportunity to deepen my knowledge of Node.js, React Hooks, and even introduce myself to Sockets.
If there's another language I'm curious about but don't have time to learn, I'll watch a 15-20 minute basics video so that I have a sense of what sort of language it is. Just enough that I can hold a competent and curious conversation about it.

I've said it many times, the most valuable thing the bootcamp taught was not any one coding language, but how to learn coding languages.

You learn the basic building blocks, and the patterns to look for, and then you're ready to strike out and learn more and more.

Sorting an Array of Number Strings in JavaScript

El Marshall (she/they) — Mon, 04 May 2020 04:47:31 +0000

Okey dokey, the binary tree hiatus continues, because my node deletion post got out of hand and I need to get a post up in the next couple hours and I am tired y'all.

So I'm gonna write a quick post about a function in JavaScript that I found really confusing for a long time - I guess no one satisfactorily explained to me what was going on, so it just looked like gibberish.

You ask the internet how to sort an array of numbers in JavaScript, and they'll tell you this:

arr.sort(function(a, b){return a-b});

Honestly my brain looked at that and went... Huh?
Ultimately it really is not very difficult, but no one had properly explained to me why each piece of this does what it does. So I'm gonna lay it out.

First, the basics of the JavaScript sort method. The language has a built in function sort() that can be applied to an array. Take for example, this array of integers:

let arr = [2, 6, 3, 8, 54, 846, 4]
arr.sort()
console.log(arr) // [2, 3, 4, 6, 8, 54, 846]

That did just what you expected, really. Now we'll apply it to an array of strings:

let arr = ['cat', 'monkey', 'apple', 'apples']
arr.sort()
console.log(arr) // ['apple', 'apples', 'cat', 'monkey']

You can even mix integers and string representations of numbers, like so:

let arr = [2, "6", 3, "8", 54, 846, 4]
arr.sort()
console.log(arr) // [2, 3, 4, "6", "8", 54, 846]

But there's a wrinkle. See what happens to the following array:

let arr = ["8", "4", "54"]
arr.sort()
console.log(arr) // ["4", "54", "8"]

Because it's comparing these elements as strings, not integers, "54" comes before "8" because it starts with "5". That's probably not what you were going for. Let's take another look at that fancy nonsense from above now:

arr.sort(function(a, b){return a-b});

The problem I had upon first seeing this was that I was trying to interpret this logically, reading the code on its face. I didn't realize this is a case of another built in method for JavaScript. The function is actually an optional parameter, called the compareFunction, that allows you to define an alternative sort order.

Per the W3schools page on the subject,

When the sort() method compares two values, it sends the values to the compare function, and sorts the values according to the returned (negative, zero, positive) value.

The magic is that by performing an operation (subtraction) on the numbers in question, JavaScript converts them to integers. So it receives "54" and 4 and returns 54 - 4. That's a positive number, so the sort method knows to put 4 first. If you wanted to sort in descending order, you could use this instead:

arr.sort(function(a, b){return b-a});

Personally I think this is some pretty clunky syntax to remember, but it's what we've got!

Compact vs Readable Code

El Marshall (she/they) — Fri, 24 Apr 2020 15:58:26 +0000

Happy Friday everyone! I'm gonna be honest y'all, I'm picking up a new cat today so my focus is not the best. His name is Bumble Bee and he's the cutest:

So in light of this, we're going to wait to do part VI of the binary tree series, since I don't have time to do thorough research. Have a bit of an opinion piece instead!

This week I was sent an interesting interpretation of the classic FizzBuzz challenge. For those who do not know, FizzBuzz is a classic algorithm challenge, that goes like so:

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

This article provides an extremely concise means of solving the problem:

for(let i=0;i<100;)console.log((++i%3?'':'fizz')+(i%5?'':'buzz')||i)

It then runs through exactly what's going on there, because frankly it is a pretty intimidating looking jumble of code. But the feather in its cap here is just how short it is. You could say that it is extremely simple, since it uses only one line of code.

On the other hand, if you define simplicity around readability, I would consider it very complex. A more traditional, but longer, solution looks like this (as provided in the same article):

for (var i=1; i < 101; i++){
    if (i % 15 == 0) console.log("FizzBuzz");
    else if (i % 3 == 0) console.log("Fizz");
    else if (i % 5 == 0) console.log("Buzz");
    else console.log(i);
}

This code is much more readable, as a human. If this, do this, else if this do this, and so on. More lines of code are used, but it allows for much more approachable code.

Some will tell you that the best code is code that uses as few lines as possible.

Some will tell you that the best code is code that is readable.

While I certainly agree that you should make sure your code is tight, concise, not bloated, etc, I do not think that that should be taken so far as to sacrifice readability. If I'm new to your code, I should be able to walk in and understand what's going on easily.

So far as I can tell, there is no performance difference between the above two samples of code, or if there is one it's negligible (if someone reads this and does know a difference please let me know, I'd be super curious to see where the difference lies! That's an area I'm still growing my knowledge). Given that, I'll take the readable version any day.

I really enjoyed getting to see this - I learned something new about console.log and the || operator for one, and it was a neat thought experiment to see how this solution could be distilled down.

Still, at the end of the day, I think I'll stick to my ifs and switches!

Binary Search Trees V/? - Duplicates

El Marshall (she/they) — Fri, 17 Apr 2020 17:21:01 +0000

Okie dokie, where was I? Right, duplicates!

Okay so. Possibly the simplest solution is simply to disallow duplicates. If you don't care how many of a given piece of data you have, then you may be willing to simply say, "Oh, we've got this one, no need to add it to the tree."

In that case, we just need to check for equality before checking whether to move right or left, as we were doing before. See below:

function addNode(currentNode, newNode){

    if (currentNode.data == newNode.data){
        return; // if we have a duplicate, we're done!
    } else if (currentNode.data < newNode.data){ // if our newNode is bigger, move right
        // code for adding
    } else ( // if our newNode is smaller, move left
        // code for adding
    };

};

There's many a time, however, when you want to keep track of your duplicates. I have seen it suggested that you can pick one side of the tree to allow duplicates on, but not only does this have multiple drawbacks to the runtime of searching through the tree, it goes against the spirit of Binary Search Trees (that being that every node is distinct), so as far as I'm concerned it's not really an option.

A much more elegant solution is to include a count in your nodes. Here is the node class as we have been defining it thus far:

// Node class 
class Node 
{ 
    constructor(data) 
    { 
        this.data = data; 
        this.left = null; 
        this.right = null; 
    } 
}

We'll add to this a place to keep track of the number of instances of that data piece, like so:

// Node class 
class Node 
{ 
    constructor(data) 
    { 
        this.data = data; 
        this.count = 1;
        this.left = null; 
        this.right = null; 
    } 
}

Now if we have a node currentNode we can call currentNode.count to find out how many of that node we have. It should start at one by default, since we'll assume that on creation of a node, you only have the one instance.

So, say we need to add '12' to a tree, but we already have a node of data '12'? We'll create a method on the Node class for increasing its count.

// Node class 
class Node 
{ 
    constructor(data) 
    { 
        this.data = data; 
        this.count = 1;
        this.left = null; 
        this.right = null; 
    } 

    increase(){
        this.count++
    }
}

So now instead of simply exiting out of our function when we find a duplicate, as we did above, we'll call this increase function.

function addNode(currentNode, newNode){

    if (currentNode.data == newNode.data){
        currentNode.increase(); // increase the count on this node
    } else if (currentNode.data < newNode.data){ // if our newNode is bigger, move right
        // code for adding
    } else ( // if our newNode is smaller, move left
        // code for adding
    };

};

Those are the methods I've come across - if you have a preferred one let me know!

Ruby on Rails .create Rollback Mystery

El Marshall (she/they) — Fri, 10 Apr 2020 18:41:35 +0000

I interrupt your regularly scheduled Binary Tree blogs to bring you a frustration I ran into, and then the fix.

In my pet project, The World Builder's Tome, which started as my final project at Flatiron, I have quite a few interconnected models in my Ruby backend. There are worlds and stories and characters and notes and more, and each of these models "has many" images. The way I have handled this is to have only one Images model, with foreign keys for all these different categories.

Initially, the image.rb file in models looked like this:

class Image < ApplicationRecord
    belongs_to :world_note
    belongs_to :story_note
    belongs_to :world
    belongs_to :story
    belongs_to :character
    belongs_to :location 
end

In the midst of solving some minor bug (I honestly can't remember what it was now), I added a reference to the foreign keys, which is more syntactically correct. This looked like this:

class Image < ApplicationRecord
    belongs_to :world_note, :foreign_key => "world_note_id"
    belongs_to :story_note, :foreign_key => "story_note_id"
    belongs_to :world, :foreign_key => "world_id"
    belongs_to :story, :foreign_key => "story_id"
    belongs_to :character, :foreign_key => "character_id"
    belongs_to :location, :foreign_key => "location_id"

end

Little did I know, however, that this would cause me another issue somewhere else.

When I next came back to the program, I discovered that I could no longer successfully create images. Narrowing things down, I confirmed it wasn't an issue with Heroku, my hosting site, since it also wasn't working on my localhost. I even tried directly running Image.create() in the Rails Console, which confirmed that it wasn't an issue with a fetch somewhere that was creating the problem.

Looking at the output in Rails, I saw that the .create would begin, and then immediately rollback with no explanation. Here's that code, for those curious:

2.6.1 :003 > Image.create(url: "thisisaurl")
   (0.4ms)  BEGIN
   (0.4ms)  ROLLBACK
 => #<Image id: nil, url: "thisisaurl", world_id: nil, story_id: nil, 
character_id: nil, location_id: nil, story_note_id: nil, created_at: nil, 
updated_at: nil, world_note_id: nil>

Frustratingly, this proved to be a difficult problem to google. I couldn't quite get the wording right to get at the issue I was having. Eventually, however, I managed to find this question another programmer had.

They seemed to be having just the issue I was! Huzzah! Here's a key line from the winning response: "Rails, in 5.0, requires validation on belongs_to. There are two ways to fix it, adding optional: true or required: false."

There's a spot for each of these different connections on each image instance, but any given image will only have the one connection. Given that, the foreign-key for all other connections on that instance would be nil. Turns out, you need to specify whether or not those foreign-keys are required, or Rails (5.0) will default them to required and reject any new object instance that doesn't have them!

I gave that a try, altering my code to look like so:

class Image < ApplicationRecord
    belongs_to :world_note, :foreign_key => "world_note_id", optional: true
    belongs_to :story_note, :foreign_key => "story_note_id", optional: true 
    belongs_to :world, :foreign_key => "world_id", optional: true 
    belongs_to :story, :foreign_key => "story_id", optional: true 
    belongs_to :character, :foreign_key => "character_id", optional: true 
    belongs_to :location, :foreign_key => "location_id", optional: true 

end

Lo and behold, that solved it!! Who knew this was a thing? I sure didn't. Do now, though! Learn a little something new every day. (The commenter also recommended reading this blog post describing the change.

Hopefully this will help someone with my same issue discover the problem a little faster!

Binary Search Trees IV/? - Adding Nodes

El Marshall (she/they) — Fri, 03 Apr 2020 22:49:24 +0000

Here we are, the long awaited moment for the 5 readers of this series, we have come to adding nodes! There are a couple methods for this, but I'm going to use the recursive method, since it's in line with the way I wrote up traversal, and I think it's neater.

(Before I get started, shout out again to Cracking the Coding Interview, as well as to this guide, which helped me figure all this out.)

So here's our hypothetical situation. Let's do an easy one first. We need to add the number "2" to a binary search tree that's currently empty. Let's create a function that takes in that data as a parameter. This function will be placed inside of the BinarySearchTree class, so we can refer to the tree using the "this" keyword.

function add(data){
    let newNode = new Node(data)
    if (this.root === null){
        this.root = newNode
    };
};

Using the function written above, if we have a variable tree and we call tree.add(2) our empty tree will become a tree with one node of data "2".

That was super easy, but obviously most of the time you won't be so lucky as to be adding your node to an empty tree. So here's another hypothetical. Given the below binary search tree, let's add a node with the number "5."

In this case, the tree is not empty, so we need to decide where to put the new node. Let's compare our piece of data to the data of the current node. We'll make a helper function called addNode that finds the right place to put the node and inserts it.

function add(data){
    let newNode = new Node(data)
    if (this.root === null){
        this.root = newNode
    } else {
        addNode(this.root, newNode);
    };
};

If the new node is less than the current node, we'll know it needs to go somewhere to the left. As is, we see that it is in fact greater than the current node, so it will need to go somewhere to the right. So to start with, our function looks like this:

function addNode(currentNode, newNode){

    if (currentNode.data < newNode.data){ // if our newNode is bigger, move right
    }
};

If there is no right hand child node (if currentNode.right is null) then we know we can insert our new node right there. Let's add in that code.

function addNode(currentNode, newNode){

    if (currentNode.data < newNode.data){ // if our newNode is bigger, move right
        if (currentNode.right === null){
            // if there is no right node, plug in the newNode there!
            currentNode.right = newNode; 
        }
    }
};

Supposing there is a node there already, though, what do we do? We simply repeat this process - examining the node to see if we go left or right. So, we can call on the method itself so that we recurr until we find a node with no right hand child node.

function addNode(currentNode, newNode){

    if (currentNode.data < newNode.data){ // if our newNode is bigger, move right
        if (currentNode.right === null){
            // if there is no right node, plug in the newNode there!
            currentNode.right = newNode; 
        } else {
            // if the right node is not null, recurr until it is!
            addNode(currentNode.right, newNode);
        };
    }
};

If our data happens to be smaller than the current node, we simply do the same thing but headed left

function addNode(currentNode, newNode){

    if (currentNode.data < newNode.data){ // if our newNode is bigger, move right
        if (currentNode.right === null){
            // if there is no right node, plug in the newNode there!
            currentNode.right = newNode; 
        } else {
            // if the right node is not null, recurr until it is!
            addNode(currentNode.right, newNode);
        };
    } else ( // if our newNode is smaller, move left
        if (currentNode.left === null){
            // if there is no left node, plug in the newNode there!
            currentNode.left = newNode; 
        } else {
            // if the left node is not null, recurr until it is!
            addNode(currentNode.left, newNode);
        };
    };

};

So now we have two methods, insert(data) and insertNode(currentNode, newNode). insert creates a new Node from the data provided and checks if the tree is empty. If it is, it fills in the root node with this new one. If it isn't, it passes the buck to insertNode, which is a recursive function that will find the right spot for the new node and add it in.

But wait - what if your data is already in the tree? Here we've worked off the assumption that you are dealing entirely with unique values, but that might not always be the case. There are a few ways to handle this, so rather than cram it into a final paragraph I'll write the next segment on duplicates!

I hope this is helpful to someone - working through it in explicit writing like this is helpful to me.