How I Made my Own Programming Language — Verbosity

An explanation of how my compiler compiles my own programming into C++.

If you’d like to follow along with the code then you can access it here.

The Grammar

My initial goal was to create a programming language that contained no characters like <, >, “, (, and other punctuation marks. This meant all these characters had to be replaced with words (making the language verbose and hence the name verbosity).

To start, I created a basic informal grammar for the language shown below:

=========================
        Variables
=========================

let [name] of type [type] be [expression]


=========================
        Functions
=========================

define doSomething with [parameter name] of type [type] gives back [type] as
  give [expression] back
end

call doSomething stop


=========================
       Conditionals
=========================

if [inequality expression] then
  [code]
otherwise if [inequality expression] then
  [code]
otherwise
  [code]
end

=========================
          Loops
=========================

for [identifier name] [inequality expression] repeat
end

With this basic grammar in place, I knew what I wanted the language to look like and I could move onto coding the actual compiler.

The Lexer

To do anything useful with the input code I need to first understand what each word in the input file means.

To do this, I first split up all the tokens based on certain delimiters like spaces and other keywords which signify the end of a statement or the start of a new code block.

With the input file split up into chunks, I could now go through and assign a TokenType to each string. Since I wanted to keep both the TokenType (which is an Enum with all the different types of elements) and string I created the following Token class:

class Token {
public:
  TokenType tokenType;
  std::string tokenString;

  Token(const TokenType tokenType, std::string tokenString) : tokenType(tokenType), tokenString(std::move(tokenString)) {}
};

With this place, I simply looped through all string that was split up and assigned a token type to everything. For instance, if I see the word “let” then I would use the following code to assign a type to it:

token.tokenType = TokenType::LET;

Doing this all the different strings then allows the program to easily parse what everything means in the file rather than just seeing if certain strings equal something else which can be very error prone.

Constructing the Abstract Syntax Tree (AST)

Now, the program knows that certain tokens exist everywhere, but it still can’t make sense of them. For instance, take the following arithmetic expression:

So far the program knows what each part of this expression is:

However, it doesn’t know how to make sense of these tokens as there’s no structure to them. They’re just a list of strings and enums.

To give these tokens structure, we can create an Abstract Syntax Tree (AST). For an expression like 2 + 3, it could look like the image below:

A great website that shows the ASTs that existing programming languages create is https://astexplorer.net/.

To create this tree, I started by creating a function called constructAST which would be called recursively every time I had to process another code block. Inside this function, I essentially check for the start of variable statements, function statements, if statements, etc.

This is done by simply checking what the current token is. For instance, if the token type is LET then it means it is the start of a variable statement which was defined in the grammar previously.

Let’s say the function finds a function statement as shown below by seeing that there’s a DEFINE keyword:

define doSomething gives back integer as
  let x of type integer be 5 stop
  give x back
end

The first thing it will do is extract the statement using a function called incrementToKeyword . The reason it’s given this name is because I have the function increment to the as keyword as that is the end of the statement and also the start of the actual code block inside the function. This means the code above gets split up as shown below:

The yellow box represents the statement, and the green box represents the code block. Now, to process the code block, all I have to do is recursively call constructAST and it’ll keep applying the same process and will return nodes for variables, if statements, etc.

This process of extracting the statement, and then processing the code block is essentially repeated for all the different types of statements that could exist like return statements, print statements, variable statements, etc.

Now, the last major part of constructing the AST was dealing with numerical expressions like 5 + 6 / 3. The way I did this was by using a technique called Pratt Parsing from this amazing article. I also added support for inequalities by simply splitting the expression wherever the inequality sign was and evaluating both sides as shown in the code below:

optional<int> inequalityIndex = isInequality(statement);
if (inequalityIndex.has_value()) {
  vector<Token> leftArray, rightArray;

  // Split the two sides of the inequality into their own arrays
  for (int j = 0; j < inequalityIndex.value(); ++j)
    leftArray.push_back(statement[j]);
  for (int j = inequalityIndex.value() + 1; j < statement.size(); ++j)
    rightArray.push_back(statement[j]);

  // Parse both sides
  int iCopy = i;
  variant<TYPES> left = evaluateExpression(leftArray, iCopy, 0);
  iCopy = i;
  variant<TYPES> right = evaluateExpression(rightArray, iCopy, 0);

  return BinaryExpression(statement[inequalityIndex.value()].tokenType, left, right);
}

Once the constructAST function is done running it should create a tree like the one below for the following statement, let a of type integer be 5 plus 10 divide 2 stop:

Variable Statement
|
|__ Identifier - "a"
|
|__ Variable type - Integer
|
|__ Value - Binary Expression
    |
    |__ Operator - Plus
    |
    |__ Left - Integer literal
        |
        |___ Value - 5
    |
    |__ Right - Binary Expression
        |
        |__ Operator - Divide
        |
        |__ Left - Integer Literal
            |
            |__ Value - 10
        |
        |__ Right - Integer Literal
            |
            |__ Value - 2

You can see how this tree represents how the code is structure in a fairly recursive format as there’s binary expressions inside binary expressions.

Code Generation

Once the constructAST function is done running it returns a pointer to the Root node shown below:

struct Root final : ASTNode {
  std::vector<std::shared_ptr<ASTNode>> nodes;

  std::string generateCode() override;
};

All this node has is an array of other nodes, so all we have to do is simply loop through all of them and call generateCode . It doesn’t matter whether some specific node is a variable, function, if statement, etc, they are all derived from the abstract class ASTNode and thus have a method of generateCode (OOP is so cool 😀).

The core of the code for the code generation is shown below:

for (Root *pointer = rootNode.get(); const auto &node : pointer->nodes) {
  if (FunctionStatement *functionStatement = dynamic_cast<FunctionStatement *>(node.get()))
    functionCode += node->generateCode();
  else
    currentCode += node->generateCode();
}

The reason I check for a function statement separately is because it has to be appended to a separate string since all the functions the user has been defined can’t put inside the main function in a C++ program.

Once the code is generated all that’s left is to write to a compiled.cpp file and boom the program is compiled!

Conclusion

Just like that, I can now compile my own programming language!

Now one thing to note is that I didn’t create methods like peek or consume to process tokens while constructing the AST. Typically, these are used to just look ahead by one index, or take the value of the next token and increment the index. However, I chose to just use raw indexes with arrays due to how I was processing the individual statements, but this isn’t really the standard way of doing it.

Other than that, if you have any questions, feedback, or other thoughts then please feel free to contact me!

Creating Citrus🍋 — Tetris Written in C

My short little journey of creating Tetris in the terminal using C and its standard library.

Here’s the GitHub repository in case you want to try playing it or check out the code!

A little primer on Citrus

It’s really just a clone of Tetris that I made in the terminal using just C and its standard library. It’s got the barebone features of Tetris such as making a piece fall faster, moving it left or right, and rotating it. It’ll also destroy lines when they span the entire width of the playing grid.

Why did I make it?

I had nothing else to do in my Computer Programming class, so I was like, “well, making Tetris can’t be that bad, right?” I also wanted to just try making a project in C because I’ve always used C++ and only made stuff for robotics.

The Process

I knew the following things when I started:

• I wanted to make it in C
• It had to run in the terminal
• I can only use the standard library, so things like printf()

Why did I put these constraints on myself? It’s pretty straightforward, web development got pretty annoying cause it was always like taking one library, taking another library, and smashing them both together. This is not always the case, but because I never went deep into working on the tooling itself (at least for now), like Deno or Hono, it got kind of annoying.

Now all I had to do was figure out how to print squares to the terminal.

It’s pretty simple, though, trust me:

1. You create an empty string and just add \033[
2. After this you have a giant table to choose what you want your text to look like. You can find the table in this Stack Overflow post (big thank you to Richard for writing this post🙏).
3. You use this random character that I never knew existed, ▀, to create a perfect square because otherwise if you use any other character, it’ll be a rectangle. Quite unfortunate.
4. Then you put two of these things, ▀, together, and you get half a square, ▀▀.
5. To make it a full square, you set the foreground color, which changes the color of the square, and then the background color, which changes the color beneath the square. If they’re the same color, then you get a full square! It’s a little bit of a hack, but it works.

To make my life easier, I made a few little preprocessor directives (kind of like a variable but not quite) to hold the different colors:

#define DARK_BLUE "\033[38;5;19;48;5;19m▀▀\033[0m"
#define LIGHT_BLUE "\033[38;5;14;48;5;14m▀▀\033[0m"
#define ORANGE "\033[38;5;208;48;5;208m▀▀\033[0m"
#define PURPLE "\033[38;5;57;48;5;57m▀▀\033[0m"
#define YELLOW "\033[38;5;226;48;5;226m▀▀\033[0m"
#define RED "\033[38;5;9;48;5;9m▀▀\033[0m"
#define GREEN "\033[38;5;82;48;5;82m▀▀\033[0m"
#define WHITE "\033[38;5;15;48;5;15m▀▀\033[0m"

Then I created a few abstractions and got the pieces printed to the screen.

To create the grid, I just had a function that kept on printing the grid out. Then, to create new pieces, there were functions to get the coordinates on the grid on which I have to add the piece and one to actually modify the grid (represented as a 2d array).

The rest of the code to get the pieces falling and all of that was pretty simple as well as I just used some of the abstractions I had created.

I only had to refactor the code like, seven times. Not that bad.

To get the input, I just simply created one thread that would detect for key presses and another that is constantly displaying the updated grid. There is a noticeable amount of lag because the two threads are updating the variables at the same time, and honestly, I didn’t really know how to fix this.

If anyone reading this article as any ideas, then feel free to put it down in the comments, I’d love to know!

Other Random Stuff

Why did I choose C over C++?

My hypothesis was that OOP is bad because I have to spend more time on creating the classes and all of that. My conclusion, it’s pretty bad.

Why is everything in one file?

This was just another one of those, “hmm, it can be that bad right?” moments. It’s also just a pretty small project, so I didn’t really see any point in having to split up the files.

Why is it laggy?

There are two threads, one for input and one for displaying. Additionally, they’re both writing to the data at the same time, so if you do something like hold the right arrow, then it’ll keep moving the piece even when you let go. If you have any ideas on how to fix this, please let me know!

Why is it called Citrus?

Tetris → Cetris → Citrus

Anyways, I hope you enjoyed reading this, feel free to comment your thoughts on the article, the writing, the game, or anything else down below!

Hello 🙋‍♂️, if you’re new here then welcome!

If you haven’t checked out my previous two articles on Static Queries and Binary Indexed Trees then I’d suggest you do so since they cover what Range Queries are and we’ll be making some comparisons to them as well

Anyways, time for the fun part, Segment Trees :)

What are Segment Trees?

Binary Indexed Trees were cool, but it only did sum queries :(

Segment Trees are meant to be able to do minimum, maximum, and sum queries which is pretty awesome

It also works in O(log n) time for queries and updating the array in between these queries just like Binary Indexed Trees

The downside though is it’ll require more memory, and it’s a little bit harder to implement

For me personally, while it is harder to implement, I found it much easier to understand than Binary Indexed Trees

How a Segment Tree works

A Segment Tree at it’s core is just a binary tree

Each parent, will have 2 child nodes or less, but for our implementation we’ll make sure they all have exactly 2 child nodes

In order to achieve this we have to make sure the length of the array is a power of 2, so it can be 1, 2, 4, 8, etc.

If it isn’t, and it has something like 6 elements, then we can just add 2 elements to the end with values of 0

Let’s use this array as an example: [5, 8, 6, 3, 2, 7, 2, 6]

Here’s how we’ll represent it as a tree:

Keep in mind that this tree is only meant for sum queries it won’t work for minimum or maximum queries, but we’ll see how to do those later

In the tree you’ll also see that the parent node is simply the sum of the two children nodes

Let’s say we want to get the sum from index 2 to index 7 (inclusive, and it’s 0 indexed):

Since we’ve computed the sums for both of the child nodes we can basically split up the array into ranges for which we’ve computed the values

In this example we’ split it up into the first range with 6 and 3 who’s sum is 9, and then the other range 2, 7, 2, and 6 who’s sum is 17

Since we know both of these sums we just add them together and get 26

Updating values is also quite simple

Let’s say we want to update the value at index 5 with value 7 to be a 10

We can first change that value:

After that we can move up a level to update the parent node:

And so on until we reach the root node:

Boom, we’ve updated the tree in O(log n) time!

Awesome stuff

Now, it’s time to implement it

Implementing a Segment Tree

Sum Queries

So far we’ve visually been looking at a tree, but from the code, it’ll all be represented as an array

Here’s what it would look like (let’s call this array tree):

Notice that it’s one indexed, but in the code you can just add an empty element at index 0

The way the tree is represented here is that tree[1] is the root node, it’s child nodes are tree[2] and tree[3], then the child nodes of tree[2] are tree[4] and tree[5], and so on

Here are some important things for traversing the tree:

• Getting to the two child nodes — You can use tree[2n] and tree[2n + 1] where n is the index of the current element. Let’s say n is 2 with value 22, it’s children are then tree[4] and tree[5] which have values 13 and 9, which is the correct answer
• Going up levels — To go from the current node to it’s parent node we can use tree[n / 2] where n is the index of the current element. If n is 8 with value 5 then tree[n / 2] is 4 with value 13 which is the parent

Using this we can use the following code to get the sum within the range of a to b:

int sum(int a, int b) {
    a += n; b += n;
    int s = 0;
    while (a <= b) {
	if (a % 2 == 1) s += tree[a++];
	if (b % 2 == 0) s += tree[b--];
	a /= 2; b /= 2;
    }
    return s;
}

Let’s go through it

We start off by doing a +=n and b +=n this is simply making this range start at the very last level

Let’s say we want to find the range from index 3 to 7, in that case a would become 11 and b would become 15 since the length of the array, n, is 8:

We also have a variable s which contains the sum

Then we continue in the loop while the variable a is less than b because if the pointer a goes to the right of b it means we’ve reached the root node, and we’re done

Now, here’s the confusing part

The two if statements, we’re checking if a % 2 ==1 and if b % 2 == 0, and only then do we add the current node to the sum

Why these specific conditions?

Let’s go through the first iteration to see how it works

We’re checking if a % 2 == 1, and since a is 11, this condition is true

This means we select the current element 3

What if we didn’t select it though?

Well, which element would you select then?

The parent node, 9, is the sum of it’s two child nodes, but those aren’t a part of the range

If it’s still confusing then let’s look at b

The condition b % 2 == 0 will be false since b is 15, and that’s good!

If we did select the current element 6, then that’s wrong, because after that what would we have done?

Selected it’s parent node 8?

That would give us the wrong answer because if you do 8 + 6 you’re basically saying you want the range from 14 to 15, and also the element at 15

This means you’re basically adding a duplicate element, and that’s wrong

I hope this explains why we’re doing that modulo, we just want to check whether we should select the current node, or wait, and select some other parent node which contains the sum for the range we want

If we do go into the if statement then we also increment a and decrement b

This is because if we don’t then a might continue going to the left of the tree and that will be out of the range of our query, and therefore would have no meaning

This is why we’re basically “nudging” a to stay inside the range

The same logic applies to the variable b because it would also continue drifting off to the right, but if we decrement it then it’ll stay within the range

That’s quite a bit, but try debugging the code, that’s what helped me

The next lines of code are pretty simple, doing a /= 2 and b /=2 simply moves them up a level, and then we just return the sum s

Minimum and maximum queries

To do a minimum or maximum query we use the exact same code as before

The only thing we change is how the tree is constructed

For minimum queries here’s what the tree would look like using the original array:

Now we simply just query it the same as before starting at the bottom, and updating the minimum value as we go up

Updating values

Here’s the code for updating a value k by x:

void add(int k, int x) {
    k += n;
    tree[k] += x;
    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = tree[2*k]+tree[2*k+1];
    }
}

This code is much simpler

We again start at the bottom of the tree by doing k += n

Then update the current value there by x

Now we just want to move up the tree while updating the values

To do that we first move up a level with k /= 2

Then update the value at tree[k] by adding it’s two children using the expressions we had seen before

We keep on doing this until we reach the top of the tree, and we’ve updated the tree in O(log n) time!

Conclusion

The code behind Segment Trees might be a little daunting at first, I personally found it very confusing to understand, but try debugging it line by line and creating diagrams, it’ll really help

If you have any questions, comments, or feedback then feel free to reach out to me on LinkedIn!

I also hope this entire series on Range Queries helped you, I’m also going to be releasing an article on Bit Manipulation soon!

Bye ✌️

Bibliography

Competitive Programmer’s Handbook

Hey 👋, if you’re new here then read this article that gives an introduction to range queries and static queries.

Other then that, let’s get started with binary indexed trees :)

Binary Indexed Tree

In the previous article the array we had was static, so it didn’t change in between queries

If it did, then we’d have to recompute all the values again which isn’t that efficient

This is why we have binary indexed trees, they allow us to do O(log n) time operations on an array when getting the sum or updating the array

We’ll be using this array as an example: [3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3]

Here’s the order of the indexes in the tree, actually represented as an array but we’ll see that later:

The numbers on the sides of this tree are actually the indexes from the array, I’ve left the boxes empty because we’ll be computing their values later

Let’s first look at how we actually got this particular order for the indexes

Let’s look at index 6, and why it’s there and not anywhere else in the tree

The binary form of 6 is 0110, and if we flip the rightmost one bit to a 0 then we get 0100 which is equal to 4, and that’s why 4 is the parent of index 6

Let’s look at 8 who’s binary form is 1000, if we flip the rightmost one bit to a 0 we get 0000 which is just equal to 0, which is 8’s parent in the tree!

To set the rightmost bit to a zero in the code we use x & (x — 1)

If x = 8 then 8–1 = 7, who’s binary form is 0111, then if we do 1000 & 0111 we will get 0000 which is the parent of 8!

Pretty cool stuff

Now, let’s compute the actual value in each of those boxes (called nodes)

The idea is that we can represent any number as powers of 2 (in binary form)

Let’s say we want to calculate the value at index 1 in the tree

Let’s convert it to powers of 2 first, so we will get 1 = 0 + 2⁰

What this is saying is we start at index 0 in the array, and we take one element from there

In the array we have the value 3 at index 0, and since we’re taking just one element, we simply put 3 into the node!

Let’s calculate the value at index 4 in the tree

If we convert 4 into powers of 2 we get 4 = 0 + 2²

Again, we will start at index 0 in the array, but this time we will get the sum of 4 elements from there since two to the power of two is four

This means we get 3 + 2–1 + 6 = 10, and we put the number 10 into the node

Let’s look at one last example and index 7

If we represent 7 as powers of 2 we get 7 = 2² + 2¹ + 2⁰

If we sum up the first two numbers we get 6 which tells us to start at index 6 in the array, and select 1 element from that index

This means we put the number -3 into that node

Here’s the full tree after all the values have been computed:

I also mentioned before that all of these values are actually stored in an array and we’re just using a tree here to make it easier to see visually

This means as an array it should look something like this:

Now to get the sum we just need to figure out how to traverse the tree and go up levels

To do it we’ll use this, k — (k& -k)

Let’s break it down when k = 5, and we know it needs to equal 4 if we go up a level because that’s the parent in the tree

First let’s take the two’s complement, which is what the negative sign is telling us to do

Here we flip all the bits, so 5’s bit representation is 0101, and flipping all of them we get 1010, and if we add one we get 1011

Finally we perform an and operation with the original number so we get 0101 & 1011 = 0001 which is equal to 1

Finally we will subtract this from the original number, 5, so we get 5–1 = 4, and that is the parent node!

Let’s look at the code:

int sum(int k) {
  int s = 0;
  while (k >= 1) {
    s += tree[k];
    k -= k&-k;
  }
  return s;
}

All of this just for 6 lines of code 😭

Anyways, the function will compute a sum from index 1 up to index k

It’ll first check if k is greater than or equal to 1 because if it isn’t then it means we’ve reached the highest level in the tree and can return the sum

Inside the while loop it’ll first add the sum, and use the equal from before to move up a level to the parent node, then it’ll get it’s sum, and so on

If we want to get the sum from index 1 to index 7 then the tree would look something like this:

This gives us the correct sum of 16!

Just keep in mind that when you’re counting the values in the original array that they will be one indexed because the root node with value 0 at index 0 has no significance

Fun, now we can do a sum query in O(log n) time!

Updating the values is also quite simple, and we can do it in the same time complexity as well, O(log n)

To update a value at index k by x we start at the top of the tree instead of the bottom, and traverse it the same way we did before!

Here’s the code:

void add(int k, int x) {
    while (k <= n) {
	tree[k] += x;
        k += k&-k;
    }
}

Here we’re using the same equation as before, except now we’re adding that value to k instead of subtracting it, so the equation is just k + (k & -k)

Here’s what it looks like when we’re traversing the tree if we wanted to update the value at index 7:

That’s it!

We can now perform a sum query on an array, and update values in it even when the array changes!

Conclusion

I hope this helped, if you have questions or feedback feel free to reach out to me on LinkedIn!

In the next article we’ll be looking at a Segment Tree which is sort of like an alternative to a Binary Indexed Tree but it’s still just as interesting.

Alright, bye 👋, have fun coding!

Bibliography

Competitive Programmer’s Handbook

Binary Indexed Tree video

You’re given a subarray of an array, so if the original array is [1, 2, 3, 4, 5] you could be given [1, 2, 3] or [4, 5].

Your task is to perform one of the following operations:

• sum(a, b): Calculate the sum of values in range [a, b]
• min(a, b): Find the minimum value in range [a, b]
• max(a, b): Find the maximum value in range [a, b]

Seems pretty simple right? Honestly, it is, if you want to do it in O(n) time. In order to optimize it you have to go a little bit more complex, but don’t worry, it’ll be pretty chill.

Static array queries

In a static array query the array just will not change in between queries.

This means if you’re given [1, 2, 3, 4, 5], and you find the sum of [1, 2, 3], then after that the array won’t have elements added, removed, or changes, it’ll just stay the same.

Sum queries

Let’s say we’re given the following array, [1, 3, 4, 8, 6, 1, 4, 2], and we want to perform a sum query on it, so we want to find the sum from let’s say [0, 3] which corresponds to the elements [1, 3, 4, 8], and their sum is 16.

We could of course just loop through the array in O(n) time, and we’ll have our answer, but we can also create a data structure in O(n) time, and when we go to do our queries it will only take O(1), constant time, to get the result!

The thing we’ll use to create the data structure is called a prefix sum array, here’s an example:

original_array = [1, 3, 4, 8, 6, 1, 4, 2]
prefix_sum_array = [1, 4, 8, 16, 22, 23, 27, 29]

Here we create a new array where each value is going to be the sum of all the values from the original array up to that point.

Now, it’s pretty simple, all we need to do to find the sum of [a, b] is find the value at index b in the prefix sum array, and subtract that from the value at index (a — 1) from the prefix sum array.

Let’s say we want to get the sum from [2, 5], this subarray is [4, 8, 6, 1]. We get the value from the prefix sum at index 5, which is 23, and subtract it from the value at index 1, which is 4, and so we get 23–4 = 19.

Here’s the generalized formula:

S[l, r] = PrefixSum[R] — PrefixSum[L — 1]

Boom, we can query it in O(1) time! 😀

Minimum queries

We’ll just be looking at just minimum queries since it’s basically the same concept for maximum queries.

Anyways, minimum queries are a little more complicated, but don’t worry, just read it all through, and you’ll get it!

Let’s say we’re given the same array as before again, [1, 3, 4, 8, 6, 1, 4, 2].

What we’re going to do to create the data structure is calculate the minimum values in subarrays where their lengths are powers of 2.

You’ll see why this is important later on, but it’s really cool!

Here’s the values that will be calculated from the array:

You can see the lengths, like from 0 to 3, are 4, or from 2 to 3 are 1 since they are both powers of 2.

This will take O(n log n) time since we go through all the elements in the array, and then calculate log(n) values since we are doing it by powers of 2.

Now how do we actually calculate the minimum values within these ranges? In the image of the table it mentions a function called minq(a, b), how does it work?

Let’s get to that.

Scary equation alert ⚠️😬

Well, that’s a lot, but don’t worry, once it clicks, it’ll stay with you forever.

Let’s break it down by what’s being passed into the parameters first.

The variables a and b are the range as we’ve see so far, so something like [2, 5].

In the first recursive call we are passing in the variable a, and then for the variable b we are passing in (a + w — 1).

Then if we move onto the second recursive call you’ll see we pass in (a + w) as the parameter for a.

Here the variable w is the following equation:

The top part of the equation is simply getting the length of the array and then we are just dividing it by 2 to get half of the length of the array.

Why is this the case though?

Well, we’re literally just splitting the array in half, and giving each function those halves.

If you’re familiar with merge sort this should be basically the same.

Words don’t always help though, let’s look at the function calls visually. In the image we are going to use a function called m to represent the minq function.

Here’s what the recursive function calls look like:

Now let’s see what they all return.

I also put the array in as reference because the parameters are indexes of the array, just keep that in mind.

We can finally create the data structure now.

That’s right, that was only the data structure, only half way there 😭.

Scary equation alert ⚠️😬

Let’s dissect this one now, it’s meant to actually find the minimum value in the subarray.

Here’s the main idea behind getting the minimum value in a range [a, b].

Let’s say we want to find it in the range of [1, 6]:

Remember how we calculated the minimum values when the lengths were powers of 2?

This is where that comes in, let’s split this range into 2 ranges each of length 4, which is a power of 2, which means we already have it calculated!

Since we have the minimum values of each of the subarrays saved in the data structure we can just get the values from there, so the left range has a minimum value of 3, and the right range has a minimum value of 1.

Finally we just take the minimum of 3 and 1 and we have our answer! 🤯

That means in the range [1, 6] the minimum value is 1, and we calculated it in O(1) time!

Now let’s look at the equation.

You’ll see we are splitting the array again since we’re making two function calls.

Here the variable k is the largest power of 2 that doesn’t exceed the length of the subarray.

Let’s say the length of the subarray were 8, then the largest power of 2 to the power of 3 which is 8!

In this example the length of the subarray was 6, sot he largest power of 2 was 4, because 8 would be too big.

Then for the left side of the array we simply go from a to (a + k), and in the example k was 4, so the length of the left subarray is 4.

Tt’s the same thing for the right subarray as well where we start from (b — k) and go up to b, again the resulting subarray will be of length 4.

There you have it! We can calculate the minimum value of a subarray in O(1) time after creating it’s data structure in O(n log n) time.

Conclusion

If you have any questions, comments, or feedback feel free to drop them in the comment section down below, or DM me on LinkedIn!

In the second part we’re going to be looking at binary trees, and then in the third part we’ll look at segment trees!

It’s really fun stuff, so stay tuned!

Bibliography

Competitive Programmer’s Handbook

Thanks for reading! Subscribe for free to receive new posts and support my work.

Javascript import/export andcommon problems/solutions

Introduction

Imports and exports in Javascript can be incredibly useful when trying to organize your code, because it lets you export a certain variable, function, or class from one file and import it in another allowing you to organize your code and keep it easy to maintain.

Exporting

Let’s say you have a variable, function, and class in one file that you want to export to another file and use it there:

class Animal { ... }
function SomeFunction { ... }
let x = 1;

Now all we have to do to export all of these is add in the export keyword before it:

export class Animal { ... }
export function SomeFunction { ... }
export let x = 1;

We can also add the default keyword after export if we are exporting only one component or if that component is the main one in the file:

export default class Animal { ... }
export function SomeFunction { ... }
export let x = 1;

In the example above we have exported the class as the default export. You can also export multiple things inside curly braces as shown below:

let x = 1;
let y = 2;
export default {x, y};

Importing

Importing items is also very simple, and can be done as shown below:

export.js:

export default let x = 1;

index.js:

import x from "./index.js"

Imports can also be done with the curly braces that we used before when exporting:

export.js:

let x = 1;
let y = 1;
export default {x, y};

index.js:

import {x, y} from "./export.js"

Common Problems

Let’s say you have a file name export.js containing the same code as before:

let x = 1;
let y = 1;
export {x, y};

Then we have another file called index.js which is importing x and y:

import {x, y} from "./export"

/* Do stuff */

Now in index.html we are using index.js:

<!doctype html>
<html lang="en">
    <head>
        ...
    </head>
    <body>
        <script src="./index.js"></script>
    </body>
</html>

If we ran this code we would get the error below:

Now this is a simple fix because inside the HTML script tag we can just add type="module:

<script src="./index.js" type="module"></script>

This will take this error away, but another error may come up:

You may not have come across this problem if you noticed a small difference in how we imported export.js, but, for me personally, I didn’t when this error came up for me the first time and I spent a fair bit of time trying to solve it. Then I found out that literally all I was missing was .js after the file name in the import. This means we can change the code below to the update version:

import {x, y} from "./export"; // Old code
import {x, y} from "./export.js"; // New code

This will fix the problem, and now if we log out both x and y then you will see 1 be printed out twice. Below is the new code for all the files:

export.js:

let x = 1;
let y = 1;
export {x, y};

index.js:

import {x, y} from "./export.js"

console.log(x);
console.log(y);

index.html:

<!doctype html>
<html lang="en">
    <head>
        ...
    </head>
    <body>
        <script src="./index.js" type="module"></script>
    </body>
</html>

Conclusion

I hope this article helped you learn about imports and exports in javascript and/or helped you solve some problem that you were facing. If there was any error in this article or if you think that something could be explained more clearly then please do let me know. Thank you for reading!

Introduction

Recently, I’ve been wanting to get into machine learning with PyTorch, and I looked for resources that were simple to understand with minimal math (I am still a high school student so I do not know very advanced math concepts, yet). Below is a list of some of the courses I have found so far, and am either planning to learn or am already using it to learn:

1. PyTorch for Deep Learning & Machine Learning — Full Course

This is a course that I have currently been doing, and it has been amazing! The instructor can teach concepts in such a simple manner, and, while there may be a lot of repetiveness in the course, I have found it to be a really good thing because it helps me gain confidence when I go to write my own machine learning models. The course starts off with talking about the basics of PyTorch (and really all machine learning frameworks), tensors, and different manipulations that can be done on them. Then you will go onto building models such a simple linear regression model, binary classification, and multi-class classification. After this you will be working with computer vision and creating models to deal with images. The overall course is very engaging and fun, and I would highly recommend doing it.

2. Deep Neural Networks with PyTorch

I haven’t been doing this course, but might do it if I really want to get some more practice in. I’ve looked through the modules, and the things do seem quite similar to the first course, but there is not any computer vision. It seems like a good course if you don’t want to do compter vision, and do a bit deeper in some topics, but I wanted to learn computer vision as well so I chose the first course.

Deep Neural Networks with PyTorch

3. Deep Learning with PyTorch

If you prefer reading instead of watching videos then this book might just be for you. It goes fairly deep into PyTorch and machine learning concepts, and has quite a bit of detail. This book is definetly quite long and also requires some more advanced math concepts such as vectors, matrices, and dot products (not too complicated though). A great thing about this book is that it goes a bit into how PyTorch works behind the scenes in part 1, and then in part 2 it uses a real life example of detecting lung cancer to teach you more concepts. If you are someone that wants to go really deep into PyTorch and machine learning then this book might be a good choice.

https://isip.piconepress.com/courses/temple/ece_4822/resources/books/Deep-Learning-with-PyTorch.pdf

Conclusion

I hope that you found some resources that you like from this page, and have fun learning!