---
layout:	post
title: Bit Vectors
description: What are they are and how they work and why are they amazing
date: "2023-09-29"
tags: data-structures algorithms breadth-first-search art copenhagen contemporary
author: Kostya Farber
slug: "bit-vectors"
skip: true
head_title: ""
---

Bit Vectors are cool.

What are they are and how they work and why are they amazing

2023-09-29-bit-vectors.mdx

Bit Vectors

---
layout:	post
title: LRU Cache
description: What are they are and how they work and why are they amazing
date: "2023-09-29"
tags: data-structures algorithms breadth-first-search art copenhagen contemporary
author: Kostya Farber
slug: "lru-cache"
skip: false
head_title: "creating an lru cachce in go and compiling to wasm"
bullets: 
  [
    {
      item_colour: "#fccc0a",
      value: "S",
      font_colour: "black",
      tag: "systems"
    },
    {
      item_colour: "#00933c",
      value: "G",
      font_colour: "white",
      tag: "go"
    },
    {
      item_colour: "#76D0BD",
      value: "CS",
      tag: "computer science"
    },
  ]
---

import { Figure } from "../components/mdx/Figure";

When I think of the word cache, it evokes images of some mystical inventory item found in an MMORPG, or something of that description. Think Diablo, Runescape or maybe even Star Wars: The Old Republic for those fans of space operas.

<Figure caption="an mmorpg cache">
  <img
    src="../images/posts/lru-cache/lru-cache.png"
    alt="animated cache chest"
  />
</Figure>

But no, unfortunately this post isn't about those type of caches. This is about something you'll come across in computing. The LRU (Least Recently Used) cache.

## What Are LRU Caches?
A better question to answer first is: what is a cache? Simply put a cache is:

> the hardware or software component that stores data so that future requests for that data can be served faster

In this case we are dealing with a software cache and the *type* of the cache in question is a Least Recently Used Cache. 

The type defines how we deal with maintaining the size of the cache. An LRU cache evicts items based on when an item was accessed. As the name implies, items that have not been accessed recently will be evicted when the cache exceeds it's maximum amount of items.

<Figure caption="lru cache worked example">
  <img src="../images/posts/lru-cache/lru-example.png"/>
</Figure>

In the example above the *capacity* of the cache is 4, the maximum number of items. Items are accessed and added. There are two iterations of interest:

- Iteration 5: We replace **A** with **E** as **A** had been the least recently used (0 times)
- Iteration 7: In a similar vain **B** is replaced with **F** as **B** had been the least recently used (1 time)

Makes sense. But how do we go about implementing an LRU cache? Perhaps there are a couple of data structures that can come in handy for this type of problem.

## Implementing an LRU Cache
Thinking through what's needed for an LRU cache, two things come to mind:

1. Fast access, this implies constant time $$O(1)$$
2. At the same time, a way to keep track of which items have been used and evicting them easily

In the spirit of a great problem there are many ways to solve this one. However, in the same vain TL;DR. So there can only be one. That one will involve two fundamental data structures: ***hashmaps*** and ***linked lists***, both which lend themselves to deal with the properties above elegantly.

## Hashmaps, Linked Lists and Caches
Putting the puzzle pieces together to create an LRU Cache works as follows: we create a hashmap with items in the cache as keys and the values pointing to nodes in a *doubly linked list*. 

A hashmap will satisfy $$O(1)$$ but why a doubly linked list? Doubly-ness aside, a linked list is useful here because we can keep track of the head and tail nodes. 

Whenever we access an item, we move it to the head, as it has become the most recent. Once the linked list exceeds it's capacity, we can remove the tail as this will be the least recently used item. The new item becomes the head. 

Bringing back the doubly-ness, the utility from this property is that it makes removing nodes simpler because we always have a pointer to the previous node relative to the current node. We need this information when removing nodes.

## An Implementation
I'm going to go through a simple LRU cache I implemented in Go, highlighting some of the implementation, followed by a demo of it in action. To keep things simple, the items will only consist of *runes*, which in Go are a shorthand for a "code point".

<Figure caption="lru cache in Go">
  <img src="../images/posts/lru-cache/lru.gif"/>
</Figure>

## The Doubly Linked List: Structure
The first port of call is the doubly linked list. Linked list are comprised of nodes:

```go caption="a linked list node"
type Node struct {
    Val  rune
    Next *Node
    Prev *Node
}
```

A doubly linked list has nodes that have references to the previous and next nodes.

Now we define a linked list type:

```go caption="a doubly linked list"
type DoublyLinkedList struct {
	Head  *Node
	Tail  *Node
	Nodes []*Node
}
```

The linked list will have pointers to the `Head` and `Tail` nodes and a slice of `Node` pointers which contain all the nodes of the linked list.

With the overall structure in place we can define the functionality of the doubly linked list.

## The Doubly Linked List: Methods
Thinking in terms of the LRU cache, the doubly linked list needs to do a few things. But in basic terms we need to define ways to insert and delete. Let's start with insertion.

### Insertion
Whenever an item is retrieved from the cache it should be inserted at the head of the linked list to indicate it was the most recent item to be accessed. So let's write that:

```go title="ddl.go"
func (ll *DoublyLinkedList) InsertHead(val rune) error {
	if ll.Head == nil {
		node := CreateNode(val, nil, nil)
		ll.Nodes = append(ll.Nodes, node)
		ll.Head = ll.Nodes[0]
		ll.Tail = ll.Nodes[0]
		return nil
	}

	newHead := CreateNode(val, ll.Head, nil)
	ll.Head.Prev = newHead
	ll.Nodes = append([]*Node{newHead}, ll.Nodes...)
	ll.Head = ll.Nodes[0]
	ll.Tail = ll.Nodes[ll.Len()-1]
	return nil
}
```

If there is no head node (i.e no nodes in our list) we create the node, append it to our list and make the head and tail point to the node we just inserted.

If there are nodes in the list then we:

* Create the new node
* Point the old head previous pointer to point to the new head 
* Append the new head to the front of our slice
* Assign the tail to the end of the list

All the subsequent methods deal with deletion.

### Deletion 
Let's define a few helper methods to allow us to delete the `Head` and `Tail` nodes:

```go title="ddl.go" {1}
func (ll *DoublyLinkedList) DeleteTail() error {
	ll.Tail.Prev.Next = nil
	ll.Tail = ll.Tail.Prev
	ll.deleteNodeFromArray(len(ll.Nodes) - 1)
	return nil
}

func (ll *DoublyLinkedList) DeleteHead() error {
	ll.Head.Next.Prev = nil
	ll.Head = ll.Head.Next
	ll.deleteNodeFromArray(0)
	return nil
}
```

The keen observer will see there is some symmetry going on here. The code looks slightly confusing so let's go through it line by line, using `DeleteTail` as an example:

* First, make sure the node located before the tail's *next* pointer points to `nil`, as it's the new tail
* The new tail is now the node before the current tail.
* Delete the tail from our nodes array 

The symmetry is obvious from the `DeleteHead`. We do the same steps but switch each property. 



creating an lru cachce in go and compiling to wasm

2023-09-29-lru-cache.mdx

LRU Cache

---
layout:	post
title: Contexts in Golang
description: What are they are and how they work and why are they amazing
date: "2023-08-13"
tags: data-structures algorithms breadth-first-search art copenhagen contemporary
author: Kostya Farber
slug: "golang-contexts"
skip: true
head_title: ""
---

this is some text

2023-08-13-golang-contexts.mdx

Contexts in Golang

---
layout:	post
title: Abstract Methods On a Property	
description: What are they are and how they work and why are they amazing
date: "2023-08-12"
tags: data-structures algorithms breadth-first-search art copenhagen contemporary
author: Kostya Farber
slug: "abstract-method-with-property"
head_title: ""
skip: true
---

This is also some text

2023-08-12-abstract-method-with-property.mdx

Abstract Methods On a Property

---
title: Vim Macros
description: What are they are and how they work and why are they amazing
date: "2023-05-03"
slug: "vim-macros"
head_title: "why vim macros are awesome and how to use them"
bullets: 
  [
    {
      item_colour: "#fccc0a",
      font_colour: "black",
      value: "S",
      tag: "systems"
    },
  ]
---

According to [redhat](https://www.redhat.com/sysadmin/use-vim-macros) a vim macro is:

> a feature that allows you to record a sequence of commands that you use to perform a given task. You then execute that macro many times to repeat the same job in an automated way.

Simple and elegant, vim macros let you quickly automate tedious tasks.

## How to Record A Macro

Recording a macro involves saving a series of commands to a register (type: `:help registers` in vim to understand what they are).

To record a macro and save it to a register you enter (in command mode) `q` followed by any valid register. A popular register to save to is `q`. It's as easy as:

```bash caption="register a macro"
qq
```

Vim will record any key presses until you type `q` in command mode again.

Let's go through an example.

## Creating a List of Lists

I had the task of turning a list of commands and their descriptions into a list of lists so I could use them in a Python script. Tedious. Sounds like a job for vim macros.

I formatted the first entry and recorded a macro into register `q` with the following key presses:

```bash caption="recording a macro"
0jddi<80>kb, ^[0i"^[<80><fd>af,i"^[wi"^[A"],^[0i[^[
```

Wow that's ugly. If you type `:registers` after recording your macros you can see what key presses correspond to that register. This was what was in my register after formatting the first item. A lot of these are escape characters, for instance `^]` represents escape.

I'll leave it to the reader to map them back to what I pressed below.

Once I had done this first item, I selected everything below and typed:

```bash caption="applying the macro" 
:normal @q
```

This applies the macro to my selection.

![](../images/posts/vim-macros/airflow_macro.gif)

Boom. The whole list is formatted how I need it to be.

This may seem like overkill, but if this were thousands of entries it would of saved me a lot of time.

## Permanent Macros

What I just showed you is ephemeral. The macro disappears once you close the window. What about if you wanted a macro to persist across sessions? Well you can.

You can open up your `.vimrc` — wherever it lays — and define your macros there in the format

```bash caption="defining a macro in your .vimrc"
let @register = 'macro contents'
```

Here are a couple I use and why.

## Navigating Quotes

I find myself on a certain type of line a lot. A line where I want to jump straight inside the quotes and delete everything in it. So I defined a macro to do this in register `q` (for quotes).

```bash caption="defining a macro in your .vimrc, quotes"
let @q = '0f"di"'
```

![](../images/posts/vim-macros/quote_macro.gif)

## Navigating Ticks

The same for ticks saved to the conveniently lettered register `t` (for ticks).

```bash
let @t = "0f'di'"
```

![](../images/posts/vim-macros/tick_macro.gif)

Once I started using these I could not go back to my inefficient ways! Be awesome. Use vim macros.


why vim macros are awesome and how to use them

2023-05-03-vim-macros.mdx

Vim Macros

---
title: Terminal GIFs
description: What are they are and how they work and why are they amazing
date: "2023-05-02"
tags: data-structures algorithms breadth-first-search art copenhagen contemporary
slug: "vhs-cli"
head_title: "VHS by charmbracelet, create terminal gifs programatically"
bullets: 
  [
    {
      item_colour: "#fccc0a",
      value: "S",
      font_colour: "black",
      tag: "systems"
    },
    {
      item_colour: "#00933c",
      value: "G",
      font_colour: "white",
      tag: "go"
    },
  ]
skip: false
---

import { Figure } from "../components/mdx/Figure";

How do you make cool terminal gifs? Using VHS!

## VHS

I came across [this](https://github.com/charmbracelet/vhs) cool project that lets you create tapes of your terminal. It's command line as a code. I'll be using it lots to create useful snippets. Here's an example of what my terminal looks like when it starts up.

<Figure caption="neofetch using vhs">
  <img src="../images/posts/terminal-gifs/castle.gif" />
</Figure>

Awesome, I love some good ascii art.


VHS by charmbracelet, create terminal gifs programatically

2023-07-05-vhs-cli.mdx

Terminal GIFs

---
title: "Static variables in c"
description: "What are they are and how they work"
date: "2023-03-12"
slug: "static-variables-in-c"
head_title: "all about static variables in c"
bullets: 
  [
    {
      item_colour: "#fccc0a",
      value: "S",
      tag: "systems"
    },
    {
      item_colour: "#039BE5",
      value: "C", 
      tag: "c"
    },
  ]

---

In the c programming language we can use the keyword `static` to define a static variable. This keyword is part of the _storage class specifiers_, one of which you may know as `extern` and maybe the lesser known `auto` and `register`.

```c title="main.c"
int
main()
{
    static int x = 5;
    printf("My cool static variable... %d", x);
}
```

```bash caption="main.c ouput"
$ My cool static variable... 5
```

These keywords define how a variable is stored.

According to [C programming language standard](https://en.cppreference.com/w/c/language/storage_duration#:~:text=The%20storage%2Dclass%20specifiers%20determine%20two%20independent%20properties%20of%20the%20names%20they%20declare%3A%20storage%20duration%20and%20linkage)

> The storage-class specifiers determine two independent properties of the names they declare: storage duration and linkage.

## Storage and Linkage

All variables have the notion of storage. They may be allocated on the stack (come in and out of existence as functions are called and returned) or on the heap - dynamically.

When we declare an object (variable or function) with the `static` keyword it's storage duration is that of the entire program. It is [allocated once before the main function.](https://en.cppreference.com/w/c/language/storage_duration#:~:text=and%20the%20value%20stored%20in%20the%20object%20is%20initialized%20only%20once%2C%20prior%20to%20main%20function.)

## Implication

All variables without a storage class specifier use the `auto` keyword, meaning that it is allocated in the block in which it is entered and de-allocated when it leaves that block.

```c title="f1.c"
void f1()
{
    int x = 5; /* x goes into scope */

    /* do some stuff */

    return; /* x goes out of scope and is de-allocated and ceases to exist */
}

int
main()
{
    f1() /* We have no notion of x in main() */
}
```

In the previous example, if we declared `x` as a `static` variable after `f1()` exits we could still access, use and modify `x` even after it exits `f1()` scope.

## Linkage

Linkage refers to an object (variable or function) that can be referenced in different scopes. All variables have _external linkage_ by default. This means that they are visible to other _translation units_ in the same program. However when we use the `static` keyword in the global scope, that variable is _internally linked_ meaning it is only visible to that translation unit.

## Implication

This means that any objects defined are only visible to that translation unit. For instance if we had a variable called `buffer` in `file.c` and we want to contain this variable in `file.c` because it will conflict with other definitions we can name it like so:

```c title="file1.c"
static char[SIZE] buffer;

int
main()
{
    /* do stuff with buff here */
}
```

```c title="file2.c" {1}
char[SIZE] buffer; /* refers to a different buff than file.c buff */

int
main()
{
    /* do stuff with buff here */
}
```

Hope you enjoyed the read!


all about static variables in c

2023-03-12-static-variables-in-c.mdx

Static variables in c

---
title: "TIL: x &= (x - 1) deletes the rightmost 1 bit in x"
description: What is this magic
date: "2023-01-08"
author: Kostya Farber
slug: "delete-rm-bit"
head_title: "counting set bits, magic created by magician brian kernighan"
bullets: 
  [
    {
      item_colour: "#fccc0a",
      value: "S",
      tag: "systems"
    },
    {
      item_colour: "#DC241F",
      value: "L",
      font_colour: "white",
      tag: "linux"
    },
  ]
---

Why does this happen? The a-ha moment is to see what happens when we add $$1$$ to $$x - 1$$ which equals $$x$$. Say we have the number $$10$$ in decimal as our $$x - 1$$, and add one to it, this would look like:


```bash caption="adding 1 to 10"
1010 + 
0001 
```

The result would be (11 = x):

```bash caption="the result, 11"
1011
```

The astute observer would notice that in $$x - 1$$ there is a zero at the first one bit in $$x$$. This is because, what adding $$1$$ to $$x - 1$$ will do is place a $$1$$ bit into the first open position (the first 0). This means that first zero in $$x - 1$$ will correspond to the first 1 bit in $$x$$. So if we bitwise & this with the original number this will drop that bit (the rightmost 1 bit) in $$x$$.

```bash caption="the revelation, deleting the rightmost bit"
1010 &
1011
----
1010
```

## Why does this even matter?

Well, with this interesting fact counting bits in an integer becomes _slighly_ faster than just right shifting the integer and checking if the bitwise & of 1 and x is equal to 1. The primitive `countbits` may look like this:

```c title="count_bits_primitive.c"
int o_countbits(unsigned x) {
    int count = 0;
    for (; x != 0; x >>= 1) {
        if ((x & 1) == 1) {
            ++count;
        }
    }
    return count;
}
```

Which will have to right shift for every position in x. But with our new found knowledge we can re-write this as:

```c title="count_bits_fast.c" {4}
int n_countbits(unsigned x) {
    int count = 0;
    // deletes the right most 1 bit every iteration
    for (; x != 0; x &= (x - 1)) {
        ++count;
    }
    return count;
}
```

This way we don't have to count any of the zeroes in the integer. Awesome! +1 for micro optimisations.


counting set bits, magic created by magician brian kernighan

2023-01-08-delete-rm-bit.mdx

TIL: x &= (x - 1) deletes the rightmost 1 bit in x

---
layout:	post
title:	"TIL: bitwise ǀ and & on open flags in UNIX"
description: "0b110" 
date: "2022-12-29"
tags: data-structures algorithms breadth-first-search art copenhagen contemporary
slug: "til-bitwise-oflags"
head_title: "the open(2) system call and how it's flags are used"
exclude: ["Open(2)"]
bullets: 
  [
    {
      item_colour: "#fccc0a",
      value: "S" ,
      tag: "systems"
    },
    {
      item_colour: "#DC241F",
      value: "L",
      font_colour: "white",
      tag: "linux"
    },
  ]
---

Open flags are specified as macros provided to pass to the system call `open()`, to define what permissions and types we want to open a file with.

They can look like

```c title="open_flags.c"
#define O_RDONLY        0b00000000 
#define O_CREAT         0b00000100 
#define O_TRUNC         0b00001000
```

We can define a combination of these flags using the logical `|` like so 

```c caption="open flags"
O_RDONLY | O_CREAT | O_TRUC
```

which in binary looks like

```c caption="binary representation of an open flag"
0b00001100
```

How does `open()` use this to intepret what flags we have set?

Well it uses the `&` operator.

## Bitmasks
A bitmask is data used in bitwise operations. The `&` bitwise operator will set the bit only if both bits are 'on' (i.e 1 and 1).

Using our example above if we `&` O_CREATE with our flags

```bash
00000100 &
00001100
```

It results in
```bash
00000100
```

The idea is, if we `&` any of the flags with the [_oflag_](https://linux.die.net/man/3/open#:~:text=Values%20for-,oflag,-are%20constructed%20by) above and the result is non-zero then we know that flag is set.

This is how we `open()` checks for which flags have been set

```c
if (flags & O_CREAT) {
	// do something
}
```

In practice, we can use binary numbers like this to set states and check for states in any system, similar boolean flags.

the open(2) system call and how it's flags are used

2022-12-29-til-bitwise-oflags.mdx

TIL: bitwise ǀ and & on open flags in UNIX

---
title:	"TIL: bitwise & to check odd number"
description: "0b100" 
date: "2022-12-20"
author: Kostya Farber
slug: "til-check-odd-bitwise"
head_title: "using bitwise operations to check if a number is odd"
bullets: 
  [
    {
      item_colour: "#fccc0a",
      value: "S", 
      tag: "system"
    },
    {
      item_colour: "#DC241F",
      value: "L",
      font_colour: "white",
      tag: "linux"
    },
  ]
---

We can use the bitwise operator `&` to check if an integer is odd. Bitwise operators operate on element wise on bits. You can think of it has checking: 
> Are both bits 1?

## Example

```c caption="example of bitwise &"
01001001
00101000
```

If we take the example above and `&` it we get:

```c caption="after performing the & bitwise operation"
00001000
```

as only the 5th element had both 1s. 

## What does this have to do with even and odd numbers? 
We can use this operator to check if an integer is odd. We do this by `&` any integer with 1. 

The idea is if the least significant bit (the right most bit) is 'on' (equal to 1) then we are just adding one to powers of two which is odd. Otherwise it's even.

## Odd
For example the number 17 in binary is:


```c caption="the number 17 in binary representation"
10001
```

If we `&` this with one:

```c caption="the result of the bitwise & operation reveals if the number is odd"
10001 &
00001
-----
00001
```

We get a `1`, meaning it is odd. 

## Even
Contrast that with 12. We get `0`, which means the number is even.

```c caption="the same operation but the number is even"
1100 &
0001
----
0000
```

Next time you want to check even and odd numbers, this may be a quicker way then using `n % 2 == 0`. Or better yet just run the code below and see for yourself.


```python title="speed_test.py"
import numpy as np
import random
import time

def even_bit(n):
    if (n & 1) == 1:
        return "Odd"

    else:
        return "Even"

def even_mod(n):
    if (n % 2) == 0:
        return "Even"

    else:
        return "Odd"

def test_even_bit():
    for _ in range(100):
        time_start = time.time()
        arr = np.random.randint(-(2**31) / 2, ((2**31) - 1) / 2, size=random.randint(0, 10**3), dtype=np.int32)

        for num in arr:
            even_bit(num)

    print(f'100 iterations testing even with bits {time.time() - time_start}')

def test_even_mod():
    time_start = time.time()
    for _ in range(100):
        arr = np.random.randint(-(2**31) / 2, ((2**31) - 1) / 2, size=random.randint(0, 10**3), dtype=np.int32)

        for num in arr:
            even_mod(num)
        
    print(f'100 iterations testing even with mod {time.time() - time_start}')

def main():
    test_even_bit()
    test_even_mod()

if __name__ == "__main__":
    main()
```

## Results
On one of the runs on my Macbook Pro M1:

* 100 iterations testing even with bits: $$0.0006432533264160156s$$

* 100 iterations testing even with mod: $$0.0687568187713623s$$

Pretty nifty I think.

using bitwise operations to check if a number is odd

2022-12-20-til-check-odd-bitwise.mdx

TIL: bitwise & to check odd number

---
layout:	post
title:	"TIL: replacing characters in an array"
description: "String literals are untouchable" 
date: "2022-12-20"
tags: data-structures algorithms breadth-first-search art copenhagen contemporary
slug: "til-string-literals"
head_title: "c string literals and why they can catch you out"
bullets: 
  [
    {
      item_colour: "#039BE5",
      value: "C",
      font_colour: "white",
      tag: "c"
    },
  ]
---

I was getting an error if I tried to initialise an array as so, and change values in it.

## the right way but why?

```c title="number_of_replacements.c" {9, 21}
#include <stdio.h>

int replace(char* text) {
    int num_space_replacements = 0;

    while (*text != '\0') {
        if (*text == ' ') {
            char dash = '-';
            *text = dash;
            num_space_replacements++;

        }

        text++;
    }

    return num_space_replacements;
}

int main() {
    char test[] = "Kostya";
    int n = replace(test);

    printf("%s\n", test);
    printf("The number of replacements is: %d\n", n);

    return 0;
}
```
## Oh, string literals
I found my answer. The key is to understand [string literals](https://en.cppreference.com/w/c/language/string_literal#:~:text=String%20literals%20are%20not%20modifiable%20(and%20in%20fact%20may%20be%20placed%20in%20read%2Donly%20memory%20such%20as%20.rodata).%20If%20a%20program%20attempts%20to%20modify%20the%20static%20array%20formed%20by%20a%20string%20literal%2C%20the%20behavior%20is%20undefined.) in c. 

Specifically, is that they are **not modifiable** and in fact are usually placed into read-only memory. Thus doing something like:

```c title="number_of_replacements_wrong.c" {9, 21}
#include <stdio.h>

int replace(char* text) {
    int num_space_replacements = 0;

    while (*text != '\0') {
        if (*text == ' ') {
            char dash = '-';
            *text = dash;
            num_space_replacements++;

        }

        text++;
    }

    return num_space_replacements;
}

int main() {
    char* test = "The cat sat";
    int n = replace(test);

    printf("%s\n", test);
    printf("The number of replacements is: %d\n", n);

    return 0;
}
```

Would fail, because this is a string literal.

```c
char* test = "The cat sat"
``` 

And especially on line 9 when:

```c
*text = dash;
```

This is a memory access error, im not allowed to touch it. This will be undefined behaviour causing my program to crash.

## What to do instead
We have to initiliase an array of chars:

```c caption="how to correctly initialise an array of characters"
char string[] = "Kostya";
```

This way the string literal is copied into an array of characters (into modifiable memory) and I can change the characters in it.

Hope whoever comes across this now understands it a bit better. Thanks folks!

c string literals and why they can catch you out

2022-12-20-til-string-literals.mdx

TIL: replacing characters in an array

---
title:	"TIL: Passing arrays to functions in c"
date: "2022-12-18"
author: Kostya Farber
slug: "passing-arrays-to-functions-c"
bullets: 
  [
    {
      item_colour: "#039BE5",
      value: "C" ,
      font_colour: "white",
      tag: "c"
    },
  ]
head_title: "passing arrays to functions in c and the terminal value"
---


To define an array in `c` we can do things like:

```c title="char_arrays.c"
char name[] = "Kostya";

int nums[5] = {1, 2, 3, 4, 5};
```

and so forth. We also know that arrays are really just _pointers_ to the first element in the array (kind of). For example, `'K'` and `1` in the previous examples.

## Arrays As Parameters To Functions
We can pass in an array to a function, such as this one that prints the letters of a name:

```c title="letters_of_name.c"
void print_letters_of_name(char name[]) {
	while (*name) {
		printf("%c \n", *name);
		name++;
	}
}
```

This works because all `c` style strings have the null terminating character `\0` at the end of the array of characters. In practice the array `name` actually looks like `{'K', 'o', 's', 't', 'y', 'a', '\0'}`.

This is why:  `while(*name)`
```c title="letters_of_name.c" {2}
void print_letters_of_name(char name[]) {
	while (*name) {
		printf("%c \n", *name);
		name++;
	}
}
```

works. Because once we reach the end and dereference `\0` (which is the integer 0 in ASCII) the while loopbreaks because `false` is `0` by definition.

We could also write 
```c caption="another way to terminate the loop"
while (*name != '\0')
```

which is the same but more explicit. But what about `nums`?

## What Is The Size of The Array?
We know that arrays are just pointers to the first element. So when we define the parameters to an array we can just write:

```c caption="passing a pointer to a function"
void print_nums_of_array(int *nums)
```

Thinking in this way, when we pass in the array (pointer) to the function, we lose any notion of the size of the array **_because we can access elements outside of it_**. How do we know when to stop the function?

## Size or Terminating Element
We really have two options:
* The programmer and users can decide on a null terminating value such as `-1` which will mark the end of the array.

```c title="iterate_over_nums_array.c" {2}
void iterate_over_nums_array(int* nums) {
    while (*nums != -1) {
        printf("%d ", *nums);
        nums++;
    }
    printf("\n");
}
```
* You can pass in the size of the array to the function beforehand.
  
```c title="iterate_over_nums_array.c" {2}
void iterate_over_nums_array(size_t size, int* nums) {
    int i = 0;
		while (i < size - 1) {
        printf("%d ", *nums);
        nums++;
				i++;
    }
    printf("\n");
}
```

Each have their pros and cons. 

But TIL that mostly, you have to either pass in the size to a function that loops over an array as a parameter, or agree on a terminal value.

passing arrays to functions in c and the terminal value

2022-12-18-passing-arrays-to-functions-c.mdx

TIL: Passing arrays to functions in c

---
layout: post
title: "Subarray Sum Equals K"
description: Hashmaps and prefixes
date: "2022-12-05"
featured_image: "/images/posts/leetcode.png"
tags: data-structures algorithms breadth-first-search art copenhagen contemporary
author: Kostya Farber
slug: "subarray-sum-equal-k"
head_title: ""
skip: true
---

## Problem Description

Given an array of integers `nums` and an integer `k`, return the total number of subarrays whose sum equals to `k``.
A subarray is a contiguous non-empty sequence of elements within an array.

**Example 1:**

```
Input: nums = [1,1,1], k = 2
Output: 2
```

**Example 2:**

```
Input: nums = [1,2,3], k = 3
Output: 2
```


2022-12-05-subarray-sum-equal-k.mdx

Subarray Sum Equals K

---
title: "Prefix Sum"
description: Cumulative to rescue
date: "2022-12-04"
author: Kostya Farber
slug: "prefix-sum"
bullets: 
  [
    {
      item_colour: "#76D0BD",
      value: "CS", 
      font_colour: "black",
      tag: "computer science"
    },
  ]
head_title: "prefix sums - their applications in algorithms"
---

Prefix sums are a data structure that allow use to solve some interesting problems. A **_prefix sum array_** is an array based on a cumulative sum of another array. The value at $$prefix\_sum[i]$$ is the sum of all elements of array up to the point of $$i$$.

```math
prefix\_sum[i] = a[0] + a[1] + a[2] + ... + a[i]
```

So for example for the array:

```python caption="an example array"
array = [2, 7, 3, 1]
```

It's prefix sum will be:

```python caption="the prefix sum"
prefix_sum = [2, 9, 12, 13]
```

## How can we create prefix sums?

Notice how for any index $$i$$, to compute the value at $$i$$, we have to take the number at $$array[i]$$ and add it to the value at $$prefix[i - 1]$$.

```math
prefix\_sum[i] = prefix\_sum[i - 1] + array[i]
```

One might notice that this definition demands attention for the very first element of the array. Technically at $$i = 0$$ the prefix array is undefined. We have either two choices:

- Initiliase the prefix array with it's first value as zero.
- Initiliase the prefix array with the first value of the original array.

The choice of either will work, but have different names in terms of what the scan is called to produce the prefix array as well as the interpretation of $$i$$ in the prefix array. The first option is produced by an **_exclusive scan_** and the latter by a **_inclusive scan_**

## Inclusive and exclusive scans

If we go with the first option, then we produce an array with an **_exclusive scan_**. What this means, is that at any position $$i$$ in the prefix sum that is the sum **up to but not including** $$i$$.

For example, say we have an array:

```python caption="an example array"
array = [5, 2, 6, 8]
```

We create a prefix sum array with zero as the seed value:

```python caption="the prefix sum array"
prefix_sum = [0, 5, 7, 13, 21]
```

Let's say we take the index $$i = 2$$. The prefix sum at that index is $$7$$. However if we look at the original array we can see that the actual sum at $$i = 2$$ is $$5 + 2 + 6 = 13$$. This is what we mean by exclusive, we don't include that number at $$i$$ in the original array at that position in the prefix array.

The converse, is a **_inclusive scan_** where we **include** $$i$$ in the sum.

For example, removing the seed value of zero:

```python caption="the prefix sum array without "
prefix_sum = [5, 7, 13, 21]
```

For index $$i = 2$$, the sum is $$7$$, which includes $$i$$ since $$5 + 2 + 6 = 13$$

## Use case: Range Sum

A useful use case for prefix sums is it to calculate the sum of a range in $$O(1)$$ time. If we have an array we can pre-compute the prefix sum and access any range sum in constant time.

We can use the formula, if we use an **_inclusive scan_**:

```math
range\_sum[i...j] = prefix\_sum[j] - prefix\_sum[i - 1]
```

For instance, if sum of the array in the previous example from index $$1...3$$ the sum would be $$prefix\_sum[3] - prefix\_sum[0] = 16$$ which is correct.

One gotcha is if $$i = 0$$. It's obvious that we would get an index error so if this is the case we would just return $$j$$, which coincidentally is just the sum up until $$j$$.

However if our prefix array generated using an **_exclusive scan_**, the formula is:

```math
range\_sum[i...j] = prefix\_sum[j - 1] - prefix\_sum[i]
```

The same gotcha applies here if $$j = 0$$ in which case we return $$i$$.

## Wrap up

Hope you enjoyed reading this and have learnt something. There are many more use cases for prefix sums and they can be quite useful to solve a variety of problems. Thanks for reading. Happy coding.


prefix sums - their applications in algorithms

2022-12-4-prefix-sum.mdx

Prefix Sum

---
title: "N-Queens"
description: Leetcode problem
date: "2022-12-02"
slug: "n-queens"
head_title: "n-queens - thinking through the solution in python"
bullets: 
  [
    {
      item_colour: "#60399E",
      value: "L",
      font_colour: "white",
      tag: "leetcode"
    },
  ]

---

Given an $$n \times n$$ board what are the different ways you can place queens on that board such that they cannot attack each other.

> _Queens can move any number of squares vertically, horizontally or diagnoally_

Here are some possible configurations for a $$4 \times 4$$ board.

```python caption="possible 4x4 configuration"
[['-' 'Q' '-' '-']
 ['-' '-' '-' 'Q']
 ['Q' '-' '-' '-']
 ['-' '-' 'Q' '-']]
```

## Thought Process

If you were to look at the valid configuration of the board, you would notice that every queen is in it's own row and column. So as a start we know once we place a queen in a row, we cannot place another one in that row. We could try the next row and see if we can place a queen somewhere in this row. It might not lead to a valid solution, but it might. If this is sounding like a backtracking problem, then you are right.

## Backtracking

On a high level, a solution could look something like: **place queen in row, try the next row and see if any of the positions in that row are a valid placement for the queen**. What does it mean to be a valid placement?

## Valid Placement

If we place queen in any position on the board $$(i, j)$$ then we know column $$j$$ is knocked out. For example below column $$j=1$$ is unusable since a queen could attack there. Similarily that row is also knocked out since we just placed the queen there.

```python caption="valid placement"
[['x', 'Q', 'x']
,['-', 'x', '-']
,['-', 'x', '-']]
```

What about the diaganols? Well they are slightly more tricky.

## Diaganol

The way I like to play around with 2D matrices is to try see if any of the indexes at each position reveal any pattern. If we think about it there are two **_kinds_** of diaganols we are dealing with.

```python caption="positive diaganol, letters sloping upwards"
[['a', 'b', 'c']
,['b', 'c', 'd']
,['c', 'd', 'b']]
```

```python caption="negative diaganol, letters sloping downwards"
[['a', 'c', 'd']
,['b', 'a', 'c']
,['d', 'b', 'a']]
```

The trick here is, if we take the indexes at each position in the positive and negative diaganols and plot them, you would notice that at each move a constant calculation is being performed.

```python caption="positive diaganol with constant calculation"
[['0', '1', '2']
,['1', '2', '3']
,['2', '3', '4']]
```

```python caption="negative diaganol with constant calculation"
[['0', '-1', '-2']
,['1', '0', '-1']
,['-2', '1', '0']]
```

Trivially for the positive diaganol it is $$row + column$$. For example the diaganol starting at $$(1, 0)$$ moves to $$(0, 1)$$ which both equal $$1$$. You can check this property for the rest of the positions.

Similarily, on the negative, each value is given by $$row - column$$. For example, at position $$(0, 0)$$ we move to $$(1, 1)$$ then finally $$(2, 2)$$, all of which equal zero.

## Valid Placement Revisited

So this means that we can check a position on the board is valid by making sure that any queens currently on the board can't attack it by checking:

- A valid row (which we don't have to keep track of because once we place a queen we simply move on to the next row)
- The knocked out columns
- The knocked out positive and negative diaganols

Looks like we have an algorithm to work with here.

## Algorithm

We can follow these steps:

1. If we reach the end of the board (i.e no more queens to place) add this configuration to our result
2. Otherwise, for each column in this row, check if we can place a queen there
3. If so place the queen and try out all positions in the next row
4. If we've tried all columns and we can't find a valid configuration, return and take the queen back and try any other positions in the previous step

To keep track of the positions that we cannot place a queen into, we can keep a set of already used columns, positive diaganols and negative diaganols.

## Implementation

```python title="n_queens_solver.py"
import sys
import numpy as np

class Solution:
    def __init__(self):

        self.valid_c = set()
        self.valid_p_diag = set()
        self.valid_n_diag = set()
        self.res = []

    def _add_to_sets(self, col, p_diag, n_diag):
        self.valid_c.add(col)
        self.valid_p_diag.add(p_diag)
        self.valid_n_diag.add(n_diag)

    def _remove_from_sets(self, col, p_diag, n_diag):
        self.valid_c.remove(col)
        self.valid_p_diag.remove(p_diag)
        self.valid_n_diag.remove(n_diag)

    def _set_check(self, col, p_diag, n_diag):
        if (col not in self.valid_c
            and p_diag not in self.valid_p_diag 
            and n_diag not in self.valid_n_diag
            ):
            return True

        return False

    def _print_boards(self):
        for i, board in enumerate(self.res):
            print(f"Solution {i + 1} is: \n")
            print(np.array(board), end='\n\n')

    def solve_n_queens(self, N):
        board = [["-" for _ in range(N)] for _ in range(N)]
        def backtrack(r):
            if r == N:
                copy = [row[:] for row in board]
                self.res.append(copy)
                return

            for col in range(N):
                p_diag = r + col
                n_diag = r - col

                if self._set_check(col, p_diag, n_diag):
                    self._add_to_sets(col, p_diag, n_diag)
                    board[r][col] = 'Q'

                    backtrack(r + 1)

                    # backtrack
                    board[r][col] = '-'
                    self._remove_from_sets(col, p_diag, n_diag)

        backtrack(0)
        self._print_boards()

if __name__ == "__main__":
    try:
        n = int(sys.argv[1])

    except IndexError as e:
        print("You didn't provide a command line argument \n")
        n = int(input("Please pick a number: "))

    s = Solution()
    s.solve_n_queens(n)
```

These are the possible solutions for a $$4 \times 4$$ board:

```python caption="solution one"
[['-' 'Q' '-' '-']
 ['-' '-' '-' 'Q']
 ['Q' '-' '-' '-']
 ['-' '-' 'Q' '-']]
```

```python caption="solution two"
[['-' '-' 'Q' '-']
 ['Q' '-' '-' '-']
 ['-' '-' '-' 'Q']
 ['-' 'Q' '-' '-']]
```

## Gotcha

Don't forget to copy each **individual row (list) or perform a deep copy** if you are keeping a results list. Copying a 2D array does not copy the objects in it. Otherwise you will keep seeing an empty board becuase everytime you backtrack you remove the solution from every board!

Thanks for reading and happy coding.


n-queens - thinking through the solution in python

2022-12-02-n-queens.mdx

N-Queens

---
title: "Quicksort and Partition Algorithms"
description: Sorting Algorithms
date: "2022-11-29"
slug: "quicksort"
head_title: "quicksort: a deep dive into it's many partition functions"
bullets: 
  [
    {
      item_colour: "#76D0BD",
      value: "CS", 
      tag: "computer science"
    },
  ]
---

import { Figure } from "../components/mdx/Figure";

Quicksort is a fundamental _in-place_ sorting algorithm used to sort arrays. It uses the _divide and conquer_ approach, a famous method in tackling programming problems. It is a recursive algorithm that continually operates on sub-arrays of the original list to sort the array.

## How does Quicksort work?

Quicksort works by using something called a **_pivot value_** which is used to **_partition_** the array into left and right sub-arrays. Everything on the left is less than the pivot and everything to the right is greater than the pivot.

<Figure caption="quicksort algorithm visualisation">
  <img src="../images/posts/quicksort/quicksort.gif" />
</Figure>

Subsequently, recursive calls are made to the sort function on the left and right sub arrays until the list is sorted. At each stage the **_pivot value_** is placed in it's correct place, so once we get to an array of size one we are done.

## Time Complexity

On average the time complexity for this sorting algorithm is $$O(nlogn)$$, when the array is divided in half every time. In the worst case the time complexity is $$O(n^2)$$ when the pivot is the largest or smallest value or there are lots of duplicate values. This makes sense if we think about it:

- If the pivot is the largest or smallest, the subarray array will be $$n - 1$$ (all values are less or greater than the pivot) in size and we will only be reducing the size by one each time, culminating in a bunch of $$(n - i)$$ calls.

```math
\sum_{i=0}^n(n-i) = O(n^2)
```

- If the array has lots of duplicate values and we pick this duplicate as the pivot the same thing will happen and it may return a size of subarray close to the original, with the consequence similar to the above.

Obviously it is important to try create equal partitions in each step, which is important to remember when comparing partition functions.

## The Partition Functions

Something that has not been specified, which is quite important, is how to partition the data. The choice of the partition algorithm and choices of _where_ to pick the pivot are important points to consider and affect the performance of the algorithm considerably.

> As a result quicksort can be thought of, _really_, as a family of algorithms that are composed by picking a partition function and specifying it's parameters. To be honest I found this quite confusing as there wasn't a great deal about this online that explained it well.

There are two main partition functions that are used to implement quicksort:

- The Lomuto Partition function
- The Hoare Partition function

Let's go through both of these functions and how they pick pivots and partition the data.

## Lomuto Partition Function

The Lomuto partition function is the slightly simpler one to understand. Essentially it works like this:

- We pick the last value as the pivot and set a pivot index to the beginning of the array minus one `i = low - 1`
- We start from the beginning of the array up until `high - 1` and scan through it checking if `A[j] <= pivot`. If it is then we increment `i` and swap the values that are at `A[j]` and `A[i]`.
- At the end `i + 1` is the pivot index and we swap this with the value at `A[high]` (the pivot value).

## The Conceptual Idea

The idea is we are building the left sub-array by swapping any values into this portion of the array. If we perform a swap it means the pivot point should be moved forward hence the increment to `i` (i.e put the partition point to the right of any values less than or equal to the pivot).

We increment `i` _again_ at the end of the loop because we have `<=` checks. This means values equal to the pivot will appear in the left part of partition and the first value larger than the pivot will be next to this point (i.e `i + 1`) which will be where we want to swap our pivot value at `A[high]`.

Note that it is not a requirement here to have the left or right portions sorted. Only that everything to the left is less than or equal to the pivot and everything to the right is greater than or equal to the pivot.

The correct pivot index is returned, which is important to note for the next algorithm. Notice too, that the bounds checking here is `<=`. Keep these two points in mind.

## Psuedocode and Implementation

Below is the psuedocode for the algorithm:

```c caption="Lomuto Partition Function"
// Divides array into two partitions
algorithm partition(A, lo, hi) is
  pivot := A[hi] // Choose the last element as the pivot

  // Temporary pivot index
  i := lo - 1

  for j := lo to hi - 1 do
    // If the current element is less than or equal to the pivot
    if A[j] <= pivot then
      // Move the temporary pivot index forward
      i := i + 1
      // Swap the current element with the element at the temporary pivot index
      swap A[i] with A[j]

  // Move the pivot element to the correct pivot position (between the smaller and larger elements)
  i := i + 1
  swap A[i] with A[hi]
  return i // the pivot index
```

Here is an implementation in `c++` on an array.

```c++ title="lomuto.cpp"
#include <iostream>
#include <vector>

using namespace std;

int lomuto_partition(int start, int end, vector<int>& vec) {
    int i = start - 1;
    int pivot = vec.at(end);

    for (int j = start; j < end - 1; j++) {
        if (vec.at(j) <= pivot) {
            i++;
            swap(vec.at(j), vec.at(i));
        }
    }
    i++;
    swap(vec.at(i), vec.at(end));
    return i;
}

void print(vector<int>& vec) {
    for (auto &num: vec) {
        cout << num << " ";
    }

    cout << endl;
}

int main() {
    vector<int> example = {5, 2, 0, 1, 3};

    print(example); // 5, 2, 0, 1, 3

    int p = lomuto_partition(0, example.size() - 1, example);

    cout << "Partition point is: " << p << endl; // Partition point is: 2
    print(example); // 2 0 3 1 5
    return 0;
}
```

## Hoares Partition Function

Now for the fun part. Hoares partition function. This algorithm is slightly different to Lomuto and works better for duplicate values and already sorted arrays. You will find out why in a few minutes, but if you want learn more in-depth check out [this great cs stack exchange answer](https://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto) on the topic, which also explains a popular reason why Hoares is better:

> because it performs **_three times less swaps_** (again check out the link above to find out why).

I think it's best to just dive in with the description of the algorithm and implementation and I'll outline what I found confusing and how I reasoned about it to understand it.

## Description, Pseudocode, Implementation

This algorithm uses two pointers. Let's call them `i` and `j`, both pointing to the start and end of the array respectively. We move them towards each other until:

- We increment `i` as long as it is, and this is important, **_less than the pivot_** (i.e `A[i] < pivot`)
- We decrement `j` as long as it is, and this is important **_greater than the pivot_** (i.e `A[j] > pivot`)
- Once both conditions are met we swap both the values at these points.
- We do this until `i >= j` at which point we return `j`.

Essentially this is just swapping values that are not in the correct _relative_ position to the pivot. Values that are greater than the pivot should be on the right and vice versa. So we find a pair that are in the wrong place, swap and move forward. Okay no big deal.

Here is the psuedocode:

```c caption="Hoares Partition Function"
// Divides array into two partitions
algorithm partition(A, lo, hi) is
  // Pivot value
  pivot := A[ floor((hi + lo) / 2) ] // The value in the middle of the array

  // Left index
  i := lo - 1

  // Right index
  j := hi + 1

  loop forever
    // Move the left index to the right at least once and while the element at
    // the left index is less than the pivot
    do i := i + 1 while A[i] < pivot

    // Move the right index to the left at least once and while the element at
    // the right index is greater than the pivot
    do j := j - 1 while A[j] > pivot

    // If the indices crossed, return
    if i >= j then return j

    // Swap the elements at the left and right indices
    swap A[i] with A[j]
```

and it's implementation in `c++` (I use the start of the array as the pivot in this version)

```c++ title="hoare.cpp"
int h_partition(int start, int end, vector<int>& vec) {
    int pivot = vec.at(start);
    int i = start - 1;
    int j = end + 1;

    while (1) {
        do {
            i++;
        } while (vec.at(i) < pivot);

        do {
            j--;
        } while (vec.at(j) > pivot);


        if (i >= j) {
            return j;
        }

        swap(vec.at(i), vec.at(j));
    }
}
```

Now check out what we pass to our parition function:

```c caption="hoares algorithm"
// Sorts a (portion of an) array, divides it into partitions, then sorts those
algorithm quicksort(A, lo, hi) is
  if lo >= 0 && hi >= 0 && lo < hi then
    p := partition(A, lo, hi)
    quicksort(A, lo, p) // Note: the pivot is now included
    quicksort(A, p + 1, hi)
```

One thing that struck me immediately when I looked at this is:

> why do we pass in `p` to the first recursive call.

Intuitively, in Lomuto we left out the pivot (we pass `(low...p - 1) and (p + 1...high)`) as it was in it's correct place and now here we don't? This lead me down the rabbit hole of quicksort which opened up more questions, which I've actually quite enjoyed and hoped I've come to a better understanding of as a result of the rabbit hole. They ain't so bad!

## More questions

- Why do we use `<` and `>` here instead of `>=` like Lomuto?
- Why do we include `p`?
- Why do we return `j`?
- Why does wikipedia say we can't use `high` as the pivot in some cases and we can't use `low` in other cases?
- Why have I seen implementations that return `i`?

This left me with more questions than answers and me being me I wanted to fully understand _why_ we are making all these choices. I will try tackle these to the best of my understanding and try learn something along the way.

{/* ## Why do we use $$<$$ and $$>$$ here instead of $$>=$$ like Lomuto? */}

This one was one of the more simple ones. Per [wikipedia](https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme:~:text=With%20respect%20to,the%20first%20inversion), I found the explanation a bit hard to follow, but the gist is we do this so we don't have to run any bounds checks on our pointers. Why? Let me demonstrate with a simple example.

Say we have a simple array:

```python caption="a simple array"
 a = [0, 0]
```

We set our `pivot = 0`. If we perform `>= and <=` following the pseudocode:

- We increment `i` first as this is a `do while` loop
- We enter the `while loop` and since `a[i] <= 0` is always true, we increment `i` until it hits 2 and check `a[2] <= 0` and get an out of bounds exception.

Okay we can't have that happen. I will leave it up to the reader to see what happens if we use `> and <` instead (it's nothing phenomenal, we do a useless swap and return `j` because we increment both pointers after the swap because of the nature of a `do while` loop, by which I mean we always run the code before the check).

## We do we include p?

Okay this is an interesting one. Best demonstrated through an example. Let's say we have an array:

```python caption="a simple array"
array = [5, 2, 3, 1, 0]
```

and from this array we pick the pivot `p=3`.

If we run Hoares partition function on this array we get back this:

```python caption="after applying hoares algorithm"
array = [0, 2, 1, 3, 5]
```

and the pivot index returned is `2`.

> Huh? Isn't the pivot value at index `3`? If we used Lomuto (i.e `p + 1, p - 1`) we would be skippping `1` which isn't correct

By the way, to be super clear this is happening because in this function we are actively swapping the pivot value and we can't know where it will end up in the [great dividing range](https://en.wikipedia.org/wiki/Great_Dividing_Range).

Okay... so it seems in this case we should include the pivot. But wait. There are two options now, why? becuase the [pivot can be in either sub array](https://en.wikipedia.org/wiki/Quicksort#:~:text=elements%20that%20are%20equal%20to%20the%20pivot%20can%20go%20either%20way):

```c++ caption="location 1"
quicksort(a, low, p) // [0, 2, 1]
quicksort(a, p + 1, high) // [3, 5]
```

or

```c++ caption="location 2"
quicksort(a, low, p - 1) // [0, 2]
quicksort(a, p, high) // [1, 3, 5]
```

Great. Now which one do we choose? Well it depends. What does it depend on? It depends on the whether we return `i` or `j` as the pivot index and whether we choose to use the last or first value of the array as our pivot. I will try to address the last three points of [questions](#more-questions) with the decisions we have to take above.

## Last Three Points

Okay let's tackle returning `i` or `j`. Again, I think these are best explained through an example.

Say we have an array:

```python caption="a simple array"
a = [0, 0] 
```

And we go for the `low, p` variant. We run Hoares on that thing and we get:

- `i = 1`
- `j = 0`

Alright good so far. I wanna return `i`, because why not? Let's just pass this into our sorting function.

```c++ caption="quicksort signature"
quicksort(a, 0, 1) // [0, 0]
```

Oh shit. That's the exact same array. We are now going to go down a **_not very good rabbit hole_** of infinite recursion. There is [this](https://en.wikipedia.org/wiki/Quicksort#:~:text=It%20is%20therefore%20obvious,returned%20instead%20of%20i) mouthful which boils down to:

> pick `j` as the returned index, as the pivot is in the left sub array. It is our job (partition function) to exclude the "tail" (end) of the array in scenarios where infinite recursion can happen.

Yeah okay that makes sense. Let's use `j` to trim this array and avoid infinite recursion, because you don't want to hear the words infinite and recursion together.

In the wiki link above the terms "former" and "latter" are used to describe indices `i` and `j` which I believe is easier to think about as the indices that point to the "start" or "end" of the array initially. These descriptions are important when considering the next point.

## Wikipedia Says We Can't Use High as the Pivot?

You can probably guess what I'm going to say by this point. Let's walk through an example again to illustrate the point. Let's say we've got an array. But this time (plot twist) it is sorted.

```python caption="a simple array, again..."
a = [0, 1]
```

Let's perform blashpemy and pick the last value as the pivot value and go with the `(low, p)` variant. We run Hoares on the thing and get:

- `i = 1`
- `j = 1`
- becuase `i <= j` we return `j`

I think you can see where this is going... pass that to our sort function:

```c++ caption="infinite recursion again..."
quicksort(a, 0, 1) // [0, 1]
```

Same array again. Damn this isn't easy. So it is obvious now that in this case `(low, p), (p + 1, high)` we can't use the last value as the pivot. What we want to happen is that the _end_ index actually crosses the _start_ index and we return `j = 0` (we want the former to cross the latter in wikipedia parlance).

{/* ## Why Have I Seen Implementations that Return $$i$$ */}

Because this article is getting too long, I will leave it up to the reader as an exercise to see when this can become the case.

_Hint: see what happens when you use `(low, p + 1), (p, high)`_ using `i` and `j` etc.

Pretty much it's the reverse of the above. We have to return `i` and never pick the first element as the pivot to avoid infinite recursion.

## Bonus points

Okay that was a lot. As an added bonus I just want to show why Hoares performs better than Lomuto for arrays with duplicate values. Remember how I said that if we don't partition the function evenly then our performace degrades? Well Hoare's deals with this pretty well.

Say we have an array:

```python caption="a simple array, with lots of ones"
a = [1,1,1,1,1,1,1,1] 
```

With Lomuto the pivot `p`, leads to, `a[i] <= p` always evaluating to true, so we perform useless swaps and move `i` to the `n - 1` position, creating a **very** unbalanced array.

On the other hand, with Hoare's `a[i] < p` is always false, so perform useless swaps **but** the pointers always move toward each other and will cross at the mid point, creating a balanced split.

This is the exact behaviour we want to avoid unbalanced splits.

## Conclusion

There is a lot going on with quicksort! I hope I've helped with understanding it a little better. Thanks for reading folks, that's all for today.


quicksort: a deep dive into it's many partition functions

2022-11-29-quicksort.mdx

Quicksort and Partition Algorithms

---
title: "Insertion Sort"
description: "Another fundamental sorting algorithm"
date: "2022-11-27"
slug: "insertion-sort"
head_title: "insertion sort algorithm: time complexity and implementation"
bullets: 
  [
    {
      item_colour: "#76D0BD",
      value: "CS",
      tag: "computer science"
    },
  ]
---

import { Figure } from "../components/mdx/Figure";

This is another post in the sortring algorithms series. Insertion sort is yet another sorting algorithm, similar to selection sort. The concept is that you build the sorted part of the array one element at a time, by inserting it into it's correct place.

## How do we do it?

The idea is:

- You start with the first element and assume it is sorted.
- Compare the next element with the element before it. If it is less than that element, swap them.
- Do this until either the element is at the beginning of the array or at it's correct place (the element before it is no longer larger than it)
- Perform the above until we reach the end of the array.

<Figure caption="insertion sort visualised">
  <img src="../images/posts/insertion-sort/insertion-sort.gif" />
</Figure>

## Time Complexity

Let's think through this for the worst case. We are always comparing the element before the one we are currently processing. What would suck is if at every stage we would have to move the element all the way to the start of the array. This would be the case if the array was sorted in reverse order, like so for example:

```math
[5,4,3,2,1]
```

In this case we would have to travese the array

```math
(n - 1) + (n - 2) + (n - 3) + ... + 1
```

which is

```math
O(n^2)
```

Carrying on with this logic we see that when the array is _sorted_ we get the best case time complexity (O(n)), in which case all we do is compare every adjacent element once and we are done. Obviously this isn't the best sorting algorithm out there but it is still good to know about.

## Implementation

Below is an implementaion in `c++`.

```c++ title="insertion_sort.cpp"
#include <iostream>
#include <vector>

using namespace std;

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

void print(const vector<int> &vec) {
    for (auto &num: vec) {
        cout << num << " ";
    }
    cout << endl;
}

vector<int> insertion_sort(vector<int> &vec) {
    for (int i = 0; i < vec.size() - 1; i++) {
        int j = i + 1;

        // use vec.at(j) so you get an out of bounds error
        while (j > 0 && vec.at(j - 1) > vec.at(j)) {
            swap(vec.at(j - 1), vec.at(j));
            j--;
        }
    }
    return vec;
}

int main() {
    vector<int> test = {7, 5, 4, 3, -1, 5, 4, 2, 0};
    print(test);
    insertion_sort(test);
    print(test);
    return 0;
}
```


insertion sort algorithm: time complexity and implementation

2022-11-27-insertion-sort.mdx

Insertion Sort

---
title: "Selection Sort"
description: "A short post on one of the fundamental sorting algorithms"
date: "2022-11-26"
slug: "selection-sort"
head_title: "what is the selection sort algorithm and it's implementation"
bullets: 
  [
    {
      item_colour: "#76D0BD",
      value: "CS",
      tag: "computer science"
    },
  ]
---

import { Figure } from "../components/mdx/Figure";

Selection sort is a sorting algorithm. It is one of the more inefficient sorting algorithms available. It takes in the worst case $$O(n^2)$$ in time complexity.

## How Does Selection Sort... Sort?

The idea behind selection sort is very simple. We iterate through our array and find the index of the smallest element. Once we pass through the array we swap the first value with current minimum value.

<Figure caption="selection sort visualised">
  <img src="../images/posts/selection-sort/selection-sort.webp" />
</Figure>

I like to think of it as a claw machine grabbing the minumum element at every iteration and placing it in $$n - i^{ith}$$ position.

Now the first position is sorted. We do this for the rest of the $n - i$ elements
(because the first element is now sorted). That's it.

It's easy to see why this is $$O(n^2)$$. For every element $$i$$ we have to iterate through the array $n - i$ times. Let's say we have an array of $$n=5$$. Then we have to iterate:

```math
(n - 1) + (n - 2) + ... + 1
```

Which by arithmetic progression we know to be:

```math
\sum\_{i=1}^{n - 1}i = \frac{(n - 1) + 1}{2}(n-1) = \frac{1}{2}n(n-1) = \frac{1}{2}(n^2 - n)
```

In Big O analysis we can drop the constants and keep the dominant power, which in this case is $$n^2$$, thus having a $$O(n^2)$$.

## Implementation

Below is an implementation.

```c++ title="selection_sort.cpp"
#include <iostream>
#include <vector>

using namespace std;

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

vector<int> selection_sort(vector<int> &nums) {

    for (int i = 0; i < nums.size(); i++) {
        int idx = i;
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[j] < nums[idx]) {
                idx = j;
            }
        }
        swap(nums[i], nums[idx]);
    }

    return nums;
}

void print_vector(const vector<int> &vec) {
    for (auto num: vec) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<int> test = {4, 6, 2, 1, 7, 8, 10, -1, 3, 16};

    print_vector(test);
    selection_sort(test);
    print_vector(test);

    return 0;
}
```


A short post on one of the fundamental sorting algorithms

what is the selection sort algorithm and it's implementation

2022-11-26-selection-sort.mdx

Selection Sort

---
title: "Pointers in C++"
description: What is all this pointer business
date: "2022-11-21"
slug: "pointers"
head_title: "a quick guide to pointers in c++"
---

Pointers are an essential part of the `c/c++` language. They are a powerful, mysterious and arcane tool. Kind of. They are actually quite simple.

> A pointer is a variable the stores the address of another variable.

That's it.

Say we have a variable `x` of type _int_ with value `25` stored at memory location `1004`. Then a pointer to `x` would contain the value `1004`.

_Note\_\_ that a pointer also has an address which again could have a pointer pointing to it_.

## Syntax

So how do we use pointers in **c++**. Well we declare them using the `*`.

```c++
int *my_ptr = nullptr;
char *my_char_ptr = nullptr;
double *my_double_ptr = nullptr;
```

It's easier to read this from right to left as: _a pointer of type integer, called my_ptr_.

> It is important to note that it is best practise to always intiliaze pointers. If we don't they can be pointing _anywhere_ and if we were to use this pointer we could change something in a memory location that we don't want to

## Address

How do we even get the address of a variable, if say, we wanted to store that in a pointer? In `c++` we can use the `&`. This operator is known as the _address-of_ operator.

```c++
int foo = 25 // (address 1004)
int *ptr = nullptr;

ptr = &foo;

cout << ptr // --> 1004
```

## Dereferencing

The next logical thing to think about is whether we can access the _underlying value_ the pointer is pointing to. Of course we can! We do this using the _dereference operator_. This can simply be read as **_the value pointed to by_**.

Using the example from above:

```c++
int foo = 25; // (address 1004)
int *ptr = nullptr;

ptr = &foo;

cout << *ptr // --> 25
```

_Note: do not get confused with using the `_` in different contexts. They do different things depending on where you use them. For example in declaring pointers vs dereferencing them.\*

## Changing values using pointers

We can change the value the pointer is pointing too. This is quite simple.

```c++
double temp = 37.5;
double *temp_ptr = &temp;

cout << temp; // 37.5

*temp_ptr = 10.0;

cout << temp; // 10.0
```

Notice here that we first **dereference** the pointer, that is we say, grab the value pointed to by pointer and then assign `10.0` to that variable.

If we where to try do this _without_ dereferencing, we would get an error as we would be attempting to assign a double to a pointer. This isn't allowed as pointers have to contain **addresses**.

## Pointers relationship to arrays

Pointers and arrays have an interesting relationship. Arrays in `c/c++` are **implemented as pointers to the first element in the array**.

So in other words if define an array and name it `my_array` this is actually just an alias for the memory location of the first element.

```c++
int my_nums[5] = {1, 2, 3, 4, 5};
cout << my_nums << endl; // 0x305384b20

cout << &my_nums[0] << endl;  // 0x305384b20
```

So if I print `my_nums`, I get back the memory location of the first element, which is at `0x305384b20` on my comupter. Indeed, if we print the reference to the first element to the array (the memory location) we get back the same value as when we just print the _name_ of the array. So what happens when we declare a pointer to my array? That's a good question and the answer seems obvious now.

```c++
int *my_nums_ptr = {nullptr};
my_nums_ptr = my_nums;
cout << my_nums_ptr; // 0x305384b20
```

This pointer is just the memory location of the first element, exactly the same thing as what `my_nums` is.

So what happens when we access elements at each index?

## Pointer Arithmetic

How do we access the next element in an array? We usually do this using subscript notation:

```c++
cout << my_nums[2] << endl; // 3
```

But what actually happens here? If we turn back to the fact that an array is just a **contigous collection of homogenous elements in memory**, then the next element should be the size of that data type plus the previous location in memory, right? You would be correct to think that.

For example, we know that an `int` takes up four bytes of memory. If we check the memory locations of the first two elements, we would expect to see something like this:

```c++
cout << "Memory location of the first element: " << &my_array[0] << endl;
cout << "Memory location of the second element: " << &my_array[1] << endl;

Memory location of the first element: 0x30df74b20
Memory location of the second element: 0x30df74b24
```

Indeed these two elements are four bytes away from each other! Awesome. Lets experiment with the pointer to `my_nums`.

What happens when we add, let's say the number one to the `my_nums_ptr`?

```c++
cout << "Increment pointer by 1: " << (my_array_ptr + 1) << endl; // 0x30df74b24
```

Oh okay! It looks like we get back the memory location of the next element back. It seems that adding one to the array actually adds **four bytes** to the memory location.

_This is pointer arithmetic_. When we add 1 to a pointer we move it by the size of the data type it is pointing to. Quite nifty right!

## Subscript notation and pointer arithmetic

Hmm. But I want the value at that next memory location. Wait. Isn't there that dereference operator, maybe I can use that?

```c++
cout << "Increment pointer by 1 and dereference it: " << *(my_array_ptr + 1) << endl; // 2
```

Okay cool! That makes sense. If we shift the pointer by the size of an `int` _then_ dereference that we get back `2`. If we do `my_nums[1]` we get the same thing. So I guess we can say something like:

```c++
my_nums[1] = *(my_nums_ptr + 1);
```


a quick guide to pointers in c++

2022-11-21-pointers.mdx

Pointers in C++

---
title: "Determine Color of a Chessboard Square"
description: Leetcode problem
date: "2022-11-19"
slug: "colour-of-chessboard"
head_title: "solving leetcode problem: determine colour of a chessboard"
bullets: 
  [
    {
      item_colour: "#60399E",
      value: "L",
      font_colour: "white",
      tag: "leetcode"
    },
  ]
---

Today I solved another problem in both python and c++.

> You are given coordinates, a string that represents the coordinates of a square of the chessboard.
>
> Return true if the square is white, and false if the square is black.
>
> The coordinate will always represent a valid chessboard square. The coordinate will always have the letter first, and the number second.

## Inital Stab

This one wasn't very hard when you have a picture of a chessboard in front of you. You just had to determine the pattern in terms of whether the combination of letter and number are in even/odd positions.

I decided to try solve this one in c++. I wanted to use a vector to store all the numbers and then try find the position of the coordinate in the vector to determine if the letter was odd.

This simple task proved to cumbersone which was, in fact, a good thing because it led me to think of characters as integers (i.e their ascii representation).

## Overcomplicating

I then just had a series of if/else statements to determine whether the position was black or white. It looked something ugly like this:

```c++ title="colour_of_chessboard.cpp"
class Solution {
public:
    bool squareIsWhite(string coordinates) {
        // if letter is odd (black if number is odd and white if even)
        // if letter is even (white if number is odd and black if even)

        // a = 97, 98
        int chess_char = coordinates[0];
        int i = coordinates[1];

        if (chess_char % 2 != 0) {
            if (i % 2 != 0) {
                return false;
            }

            else {
                return true;
            }
        }

        else {
            if (i % 2 != 0) {
                return true;
            }

            else {
                return false;
            }
        }
    return false;
    }
};
```

## The better solution

After checking the other solutions it became obvious that I could just add both integers together and then simply check if they were odd/even. That's it.

> _The obvious fact here is that if you add an odd number to an odd number you get an even number, which in this case meant white chess board colour_

The much more pretty python solution:

```python title="colour_of_chessboard.py"
class Solution:
    def squareIsWhite(self, coordinates: str) -> bool:
        letter = ord(coordinates[0])
        number = int(coordinates[1])

        if ((letter + number) % 2 == 0):
            return False

        return True
```

Another one in the books.


solving leetcode problem: determine colour of a chessboard

2022-11-19-colour-of-chessboard.mdx

Determine Color of a Chessboard Square

---
title: "Add Two Numbers"
description: Leetcode problem
date: "2022-11-18"
slug: "add-two-numbers"
head_title: "thinking about solution to leetcode problem: add two numbers"
bullets: 
  [
    {
      item_colour: "#60399E",
      value: "L",
      font_colour: "white",
      tag: "leetcode"
    },
  ]
---

Today I solved another leetcode problem. This one involved adding two numbers which are represented as two `linked lists`.

> You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
>
> You may assume the two numbers do not contain any leading zero, except the number 0 itself.

## Inital Stab

I went for a _hacky_ method. I decided to process the linked lists into a `list` cast them to `strings` reverse it and created a linked list based on that list.

It works. But it wasn't pretty.

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        """
        1. Traverse l1 and l2, store them in a list.
        2. reverse the lists and add them up.
        3. Create a linked list out of the list in step 2.
        4. Return the head.
        """
        def process_ll(head, digit_list):
            while head is not None:
                digit_list.append(str(head.val))
                head = head.next

            return digit_list

        integers = []

        head1, head2 = l1, l2

        integers.append(process_ll(head1, []))
        integers.append(process_ll(head2, []))

        int1 = "".join(integers[0])[::-1]
        int2 = "".join(integers[1])[::-1]

        summation = int(int1) + int(int2)
        node_str = str(summation)[::-1]

        dummy = ListNode()
        head = ListNode(node_str[0])
        dummy.next = head

        for i in range(1, len(node_str)):
            next_node = ListNode(node_str[i])
            head.next = next_node
            head = head.next

        return dummy.next

```

## The better method

The trick here was to imagine that you are performing the addition as you would with pen and paper.

The idea is you can process each digit column wise:

```python
[1, 2]
[2, 4]

2 + 4 = 6
```

As when we do it on pen and paper, we have to account for carry on. To do this we can just extract the last digit in the summation with:

```python
summation % 10
```

And then if there is a carry we can extract that with:

```python
carry = summation // 10
```

_note: carry can only either be 0 or 1, because the maximum that summation can be is 9 + 9 + 1_

Armed with my new knowledge I decided to implement a similar solution but with arrays instead. You can check it out.

## Array Solution

```python
class Solution:
    def multiply(self, arr1, arr2):
        """Multiply two arrays using paper and pen method

        Args:
            arr1: first operand
            arr2: second operand
        """

        ptr1, ptr2 = len(arr1) - 1, len(arr2) - 1
        res = []
        carry = 0

        while ptr1 >= 0 or ptr2 >= 0:
            _sum = 0 + carry

            if ptr1 >= 0:
                _sum += arr1[ptr1]
                ptr1 -= 1

            if ptr2 >= 0:
                _sum += arr2[ptr2]
                ptr2 -= 1

            # take the first digit
            res.append(_sum % 10)

            # determine carry (can only either be 1 or 0)
            # because largest digits can be is 9 + 9 + 1 (carry) = 19
            carry = _sum // 10

        # edge case
        if carry > 0:
            res.append(1)

        res.reverse()
        return res

s = Solution()
test = [[1, 2, 3],
        [9, 9, 9]]

print(s.multiply(test[0], test[1]))
```


thinking about solution to leetcode problem: add two numbers

2022-11-18-add-two-numbers.mdx

Add Two Numbers

---
title: "Ugly Number"
description: Leetcode problem
date: "2022-11-18"
slug: "ugly-number"
head_title: "exploring the process to solve leetcode problem: ugly number"
bullets: 
  [
    {
      item_colour: "#60399E",
      value: "L",
      font_colour: "white",
      tag: "leetcode"
    },
  ]
---

Today I solved another `c++` leetcode problem. This one was an _easy_. and asked us to determine whether a number was an _ugly number_. The idea is, a number is ugly if **it's prime factorisation** only consists of `2, 3, 5`.

_One way to factorise a number into it's primes is to just pick the smallest possible prime number and divide this number by that prime and do the same and so on until the number is 1._

## Wrong way to go

I originally went ahead and tried to find an algorithm that could produce all prime factors of a number and check to see if it only consisted of `2, 3, 5`. This was not the right way to go.

## The simple solution

It was simple to realise that all we needed to do was continually check if this number `n` was divisable with `mod = 0` for any of those primes. If we eventually got to `1` it meant that we could factorise `n` with only `2, 3, 5` if this check broke and `n` was not equal to one, that meant other factors exist for `n` and it isn't ugly (which isn't the worst thing for a number. Nobody likes being called ugly).

```cpp title="ugly_number.cpp"
#include<vector>

class Solution {
public:
    bool isUgly(int n) {
        vector<int> primes = {2, 3, 5};
        if (n == 0) return false; // edge case

        for (int p: primes) {
            while (n % p == 0) {
                n /= p;
            }
        }
        return n == 1;
    }
};
```

```python title="ugly_number.py"
class Solution:
    def isUgly(self, n: int) -> bool:
        if n == 0: return False
        primes = (2, 3, 5)

        for p in primes:
            while (n % p == 0):
                n /= p

        return n == 1
```


exploring the process to solve leetcode problem: ugly number

2022-11-18-ugly-number.mdx

Ugly Number

---
title: "Finding Data Structures and Algorithms in Art"
slug: "dsa-in-art"
description: Discovering a popular algorithm displayed in art at the Copenhagen Contemporary.
date: "2022-06-30"
head_title: "finding the breadth first search algorithm in art"
bullets: 
  [
    {
      item_colour: "#76D0BD",
      value: "CS",
      tag: "computer science"
    },
  ]
---

import { Figure } from "../components/mdx/Figure";

## Art and Science

The **intersection** of art and science has always been an area that is of great interest to me. Finding both, in unfamiliar and unsuspecting places, can be a delightful experience. For the past couple of weeks I have been travelling around Europe and stopped over in Copenhagen, Denmark.
Being both big fans of contemporary art, my partner and I decided to take ourselves to København to visit Copenhagen Contemporary and see the [Light and Space](https://copenhagencontemporary.org/light-space/) 🔦 exhibit.

> Light & Space features both historical and new works from the American light and installation art movement that emerged in Los Angeles in the 1960s. At the time, a number of young artists were experimenting with making art out of light and new materials inspired by Los Angeles’ mix of sun, surf culture, Hollywood glamour, spirituality, and endless traffic jams.

## Moving into Tech

In June of 2022 I decided I wanted to move to London from Sydney to have more oppurtunities in tech. An inauguration, as part of this search, involves being able to solve _data structure and algorithm_ (DSA) problems. Quickly and efficiently. Anyone in my position can relate to the struggle. Having a keen intuition for these concepts is key.

## Breadth Fist Search

One of the popular algorithms used to solve graph or tree based problems is the _Breadth First Search_ (BFS) algorithm. This involves traversing a tree type structure using a queue, starting at some node. There are many problems that can be solved using a BFS algorithm.

Say we have some data structure, perhaps a 2D grid. We have two nodes on this grid and we are interested in finding the shortest path between these two nodes. How can we determine this path? We can use BFS. The concept goes (we won't go into proving this) is that any time we reach a node using BFS that is one the shortest paths to that node.

Somewhere online somebody explained how to visualise this best, in my opinion. Imagine being at the starting node. It catches fire and this fire spreads to all the reachable nodes from this node and does the same for every other node. It plays out like the below animation. Whenever I think of BFS I think of this animation and the analogy of the 🔥.

<Figure caption="Finding the shortest path using Breadth First Search">
  <img
    src="../images/posts/bfs-art/bfs.gif"
    alt="breadth-first-search algorithm animation"
  />
</Figure>

## Algorithms and Art

The brain is a _remarkable_ pattern recognition machine. The sense of familiarity that we get when we look at something for a second and we don't know why. I think the name for this is intuition. I had one of these experiences at the exhibit. As we made our way through the diffferent rooms we entered into a space full of different installations and a wall of framed drawings. I make my way around the walls and stumble upon a frame that seems familiar in an unknown way, at first.

<Figure caption="BFS on 2D Grid with the Tally System representing distance from the top left corner.">
  <img src="../images/posts/bfs-art/bfs-art.jpg" />
</Figure>

I realise this is nothing but the BFS catching fire animation! It's represented
using the Tally System to numerate the distance from the top left corner. It's a
simple and beautiful way to represent a BFS. As we move further from the top left
corner the tally's become inelligable. These areas represent a longer path (distance)
from the top left corner. The drawing almost becomes like a heat map, with darker
areas representing further distances.

It was quite a suprise to bump shoulders with a concept from my software engineering studies in a contemporary art musuem. These are the moments I cherish and will remember forever. I believe great things happen at the intersection of <span style={{color:"#364ce3"}}>**science**</span> and <span style={{color:"#364ce3"}}>**art**</span>.

I am writing this while on the bus to Gothenburg, taking in the picturesque landscapes. I hope to find some more of these momments in 🇸🇪


Discovering a popular algorithm displayed in art at the Copenhagen Contemporary.

finding the breadth first search algorithm in art

2022-06-30-breadth-first-search-art.mdx

Finding Data Structures and Algorithms in Art

---
title:	"Learning C++"
slug: "learning-c-plus-plus"
description: Time to learn a low-level language 🤔
date: "2022-06-30"
author: Kostya Farber
skip: true
head_title: ""
---

# The Idea Is
This is a place where I can record all stuff `c++` and how I'm progressing and learning. This includes everything from general syntax of the language, general problem solving and everything else.

## Classes
### Constructors
Today I learnt that you can't name initalisation variables as you would in Python:

```python
def __init__(self, a, b):
    self.a = a
    self.b = a
```

They have to be different. For example (refer to example [here](https://learn.microsoft.com/en-us/cpp/cpp/constructors-cpp?view=msvc-170)):

```c++
class myObject:
    private:
        int m_a{0}; // initialise to zero so we don't have garbage values.
        int m_b{0};

    public:
        myObject(int a, b): m_a(a), m_b(b) {}
```

## Standard Library 
### String Stream
Today I learnt about the `std::ssstream` object. This allows you to treat a string just like a stream for I/O operations.

```c++
// i/o stream
string name;
cout << "Please enter your name: ";
cin >> name;

string nums = "1,30,50,60";
sstream ss(nums);

vector<int> nums;
while (ss) {
    char buff;
    int num;

    cin >> num >> buff;
    nums.push_back(num);
    
}
```

The above is an example of reading in a comma separated list of integers in a string into a vector of integers using a stream like object. Similar to what you would do with I/O.

*note: the reason we can do `while (ss)` is because [here](https://cplusplus.com/reference/ios/ios/operator_bool/*) the boolean operator is overloaded, making the stream return `false` if there is any error in the stream.*

## Leetcode
### Guessing Game
Today I solved an easy question, that involved performing a binary search. This was the first time doing a problem like this in `c++` and naturally I got the dreaded integer overflow. 

#### Integers
The largest number that can fit into a 32 bit *unsigned (non negative)* integer is $$2^{32}$$. It follows that if we want to represnt a *signed* integer we half this space. The first bit will determine whether a value is positive or negative and then the rest will be the digits. 

So then we have $$-(2^{31})$$ for the negative portion and $$2^{31} - 1$$ for the positive portion.

#### The Problem
Back to the problem.

```c++
/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * int guess(int num);
 */

class Solution {
public:
    int guessNumber(int n) {
        unsigned long int start = 1;
        unsigned long int end = n;
        unsigned long int res = 1;

        while (guess(res) != 0) {
            res = (start + end) / 2;
            
            if (guess(res) == -1) {
                end = res - 1;
            }

            else {
                start = res + 1;
            }
        }

        return res;
    }
};
```

This `res = (start + end) / 2;` was causing an overflow. The `start + end` portion was evaluating to a number that could not fit in a regular 32 bit integer (i.e $$2^{32}$$).

To avoid this you often see:

```math
mid = start + \frac{(end - left)}{2}
```

#### Deriving the formula
Naturally I was curious. Where the hell this formula come from? Scrawling Google as developers do I find out it involved some simple algebra. To demonstrate let's say that the mid point is some arbitrary value $$x$$ away from $$l$$:

```math
mid = l + x 
```


Substitute into our mid and perform some algebra:

```math
l + x = \frac{l + r}{2} 

x = \frac{l + r}{2} - l 


2x = (l + r) -2l 


2x = (r - l) 

x = \frac{r - l}{2} 
```

Substitute $$x$$ back into $$1$$ and we get:

$$mid = l + \frac{r - l}{2}$$

There it is! We have that formula that you see everywhere when performing a binary search and you need to have `start + end` fit into a 32 bit integer. 

I think it's always nice to know where something is coming from when using it. It helps make sense of *how* and *why* I'm using something. 

2022-11-14-learning-cplusplus.mdx

Learning C++

---
title:	"Creating Executable Jupyter Notebooks with Binder on macOS"
slug: "executable-juypter-notebooks"
description: A discussion of why Jupyter Notebooks are useful and how to fix errors with Binder builds online. 
date: "2021-06-03"
author: Kostya Farber
head_title: "creating executable jupyter notebooks with binder on macos"
bullets:
  [
    { item_colour: "#996633", value: "D", font_colour: "white", tag: "data" },
    { item_colour: "#0039a6", value: "P", font_colour: "white", tag: "python" },
  ]
---

One of the foundational pillars of the scientific method is **reproducibility**. One of the advantages of reproducibility is transparency and the ability for other experimenters to attempt to verify your results or play around with the experiment that you created. The analogous method in which we create reproducibility in a computing context is by creating virtual environments. This tutorial will be using [**Conda**](https://docs.conda.io/en/latest/), a package, dependency and environment management system that is popular in the data science community.
## Jupyter Notebooks
[Jupyter Notebooks](https://jupyter.org/) are a popular way for scientists to explore their data. It provides a way to show your results alongside your code. Users may download your notebook and play around with your code and try replicate your results. 

The key for this to work however, is making sure the user is able to run the notebook on their machine (Windows, Mac or Linux). The first step in the process is making sure you create a virtual environment and download all the packages and dependencies for your project there. This is mainly to ensure that the user is able to determine exactly what packages and versions they need to run your notebook. They can install those packages into their environment easily with this information. 

However, we can take this one step further. Instead of making the user replicate the environment on their machine, we may host our environment online and create a fully executable notebook. This makes it even easier and more accessible for others to experiment with your code and reproduce your computing environment and results.

## The Binder Project
[Binder](https://jupyter.org/binder) is exactly that. The Binder project offers an easy place to share computing environments to everyone. It allows users to specify custom environments and share them with a single link. Use-cases involve workshops, scientific workflows and streamline sharing among teams. 

![](/img/1*FEiQ3UjmMmpYY3t9m5Pf1g.gif)

The Binder Project builds tools that reward best-practices in reproducible data science by utilizing community-developed standards for reproducibility. When repositories follow these best-practices and are hosted in an online repository, then Binder automatically builds a linkable environment anybody can access.Binder offers a way to extend that reproducibility and make it even easier to recreate computing environments with a single link. Binder conveniently is able to use repositories with Jupyter Notebooks hosted on [GitHub](https://github.com/) to create shareable environments. **It is as easy as copying the link into a web browser. However your operating system might make it a tad harder.**


## Docker, Operating Systems and Dependencies

Binder uses a tool called repo2docker which fetches a repository (from GitHub, GitLab, Zenodo, Figshare, Dataverse installations, a Git repository or a local directory) and builds a container image in which the code can be executed. The image build process is based on the configuration files found in the repository. As mentioned earlier we can use conda to produce those configuration files.

![](/img/1*8K9TOg-66VYhfWcUEAHs2g.gif)How to create a YAML configuration file from conda.However creating the environment.yml as is, will likely cause issues depending on which operating system your machine is running on. The docker container is built on a Ubuntu (Linux operating system) when Binder runs repo2docker. When we create the environment.yml the export actually lists dependencies that are *too**** ***specific. For example an entry might look like matplotlib==3.0.2=py36h54f8f79\_. The py=36xxxxxx suffix is actually **OS-dependent.** During export, packages are included in the configuration file that are specific to the operating system. This will cause the build to fail and our environment will *not be able to run.*

## How Do We Fix the Issue?

The problem consists of packages that are too specific and OS-dependent. For the first problem conda has flags that we can add to the export command that will tone done the specificity of the packages in the current environment during export. We can run the export as usual and add the --no-builds flag at the end. This will remove the OS related suffixes.

For the second problem, on Mac OS specifically, there are a few packages that are known to cause problems. These include:

* `libcxxabi=4.0.1`
* `appnope=0.1.0`
* `libgfortran=3.0.1`
* `libcxx=4.0.1`

For example, `appnope=0.1.0` exists only on Mac OS so when Ubuntu tries to find this package; it won’t be able to and the build will fail. So we need to manually prune the configuration file for these packages. Unfortunately `--no-builds` doesn’t remove all these packages nor any conda command for that matter at the time of writing.

Manually finding these packages, whilst not too tedious, is better made to be automatically removed. I created a python script below that will remove these packages from a **YAML** configuration file.

A simple script to remove those pesky packages. A couple of things about this script:

* Make sure that the `script.py` file is in the directory that includes your `environment.yml` file.
* Your second command-line argument should be the name of your environment file (i.e `python script.py` environment.yml).
* This will overwrite the current existing `environment.yml`. If you need to recover the original you can just run the conda commands again.

```python
import sys
import yaml
import re

with open(sys.argv[1], mode='r') as file:
    environment = yaml.safe_load(file)

    pattern = '.*libgfortran.*|.*appnope.*|.*libcxx.*'

    for package in environment['dependencies']:
        if isinstance(package, str):
            if re.search(pattern, package):

                environment['dependencies'].remove(package)

                print("Match found, {} removed".format(package))

with open(sys.argv[1], mode='w') as yml:
    yaml.dump(environment, yml)
```

## Conclusion

Binder is a wonderful tool for reproducibility. Better yet, the process can be as easy as copying a link; provided that you create the correct configuration file. This was the problem I came across when trying to create my own hosted environment and these are the steps I took to make the tool work on Mac OS. I hope this will help anyone that is stuck wondering why their build is always failing! Thanks for reading.

  

A discussion of why Jupyter Notebooks are useful and how to fix errors with Binder builds online.

creating executable jupyter notebooks with binder on macos

2021-06-03-creating-executable-jupyter-notebooks-with-binder-on-macos.mdx

Creating Executable Jupyter Notebooks with Binder on macOS

---
title: Why Should I Start a Blog?
date: "2021-01-28"
description: A post about why I should start a blog.
author: Kostya Farber
slug: first-post
head_title: Why Should I Start a Blog?
---

import { Figure } from "../components/mdx/Figure"

Writing and documenting my experiences programming may be the best way for me to really make things stick.

As a student I always preferred doing assignments rather than sitting exams. Something about writing on topics I found
hard to understand helped consolidate that information in my head. Doing research and organising my ideas into a structured
prose that explains a topic or concept to a reader has always made things 'stick'. I think this approach meshes well with the concept of _Contempative Pedagogy_.

> Contemplative Pedagogy is an approach to teaching and learning with the goal of encouraging deep learning through focused attention, reflection, and heightened awareness. Learners are encouraged to engage deeply with course material through contemplation and introspection.[^1]

It is this approach that I believe will improve my skills in programming. I like to code everyday. I usually learn something new, or discover a new technique.
Having a place where I can share these discoveries and contemplate and reflect on them will encourage **deeper** learning and
ultimately understanding. It also gives me an excuse to write whilst producing actionable and measurable goals, such as a blog post.

Thus, my foray into blogging begins with a simple objective. **To gain a deeper understanding of topics I find interesting.** To finish off I will share why I chose the picture I used as the feature image. The painting,

<Figure caption="De Stamtafel: storytelling in a cafe, by David Oyen(Amsterdam 1842-1902 Brussels)">
    <img src="/images/posts/first-post/storytelling.jpg" />
</Figure>

depicts men sitting around a table listening to someone tell a story. Storytelling is an integral aspect of humanity. Being able to communicate ideas in an interesting way to the world is an
important skill. As I write more I hope I can emulate something similar to this picture. Learning by telling stories of my experiences whilst learning too. Not a bad combo!


Why Should I Start a Blog?

2021-01-28-first-post.mdx

---
title: Using Regular Expressions to Preprocess a Text File in Python
date: "2021-01-28"
description: How to use Regular Expressions and Python to wrangle an iPhones Notes text file for data analysis.
slug: text-processing
head_title: ""
bullets:
  [
    { item_colour: "#996633", value: "D", font_colour: "white", tag: "data" },
    { item_colour: "#0039a6", value: "P", font_colour: "white", tag: "python" },
  ]
---

An integral part of the Data Science process is _data wrangling_. This essentially means modifying data in such a way that makes it '_programming language friendly_'. What I mean by this is transforming the data, so it works well with the libraries that we want to use to manipulate, visualise and model the data with. In more specific terms, data wrangling is the:

> process of transforming and mapping of data from one 'raw' data form into another format with the intent of making it more
> appropriate and valuable for a variety of downstream purporses such as analytics.

For my questionable movies project, me and my friends compiled a large list of all the movies we had watched over the years.
These lists were stored and updated in a note in the Notes app on the iPhone. I copied the contents to a txt file with the raw format seen below.

![](../images/posts/trashlist.png)

## Data Wrangling

Immediately after looking at the structure of this file a few things that I needed to do became obvious:

1. I did not need the **numbers** of each film.
2. I did not need the **run time**.
3. I did not need the **actors**.

I needed to format this file to have only the film title on each line of this file. I could find all the other relevant metadata
for each film later by merging it with an existing dataframe with IMDB data or later, I discovered, using the wonderful [IMDbPY](https://imdbpy.github.io/)
package. \
The data wrangling task at hand required pattern matching string manipulation. Enter **Regular Expressions**.

## Regular Expressions

A **regular expression** or better known as **regex** is:

> a sequence of characters that define a search pattern.

It is like a language that we can use to search for really specific and complicated patterns in strings that contain any characters. This is indispensable in working with data structures that have elements that are described by characters. Think phone numbers, emails, contact information, addresses and so on.
In our case we want to write a regular expression that leaves **only the titles** on each line.

I want to first construct the skeleton of the pattern in words to create a guide for the search pattern. Looking at the text file I want to remove all characters after and including the dash. This will remove all the run times and actors. \
Next is to remove all leading digits and periods. Finally, at the end of the file the movies are recorded with some pretty rogue whitespaces, which need to be dealt with, as problems with libraries such as **pandas** pop up when there are erraneous whitespaces.

![](../images/posts/trash_whitespace.png)

The next step is to actually write the search pattern. There are numerous examples online for writing the syntax for regular expressions. They can be quite complicated. It is out of the scope of this article to cover all the syntax. I will however do
my best to explain my search pattern step by step.

## The Search Pattern

```python
\-.*|^\d*.
```

The first character, known as a **metacharacter**, are characters that serve special functions. The dash needs to be escaped by the backslash **`\`** to match the dash **`-`** character, otherwise regex will interpret the dash as signifying a range of characters.

The period **`.`** metacharacter is a **wildcard** character. A wildcard is a placeholder represented by a single character which can be interpreted as a number of literal characters. This will match any character but the newline character `\n`.

The next character is also a wildcard **`*`** and will match the character to its left zero or more times. This first search pattern will therefore match everything including and after the dashes and solves the first part of the pattern.

The **`|`** character is a logical operator that signifies **either or**. This will match the expression to its left **or** the expression to its right. The **`^`** tells regex to start the search at the start of the string or line, whilst the metacharacter `/d` will match any digits, followed by the wildcard **`*`** for zero or more occurrences. Finally, the **`.`** will match any single character after all the digits, in our case the period.

That's it! We have the regular expression to format our text file. Fortunately, Python has a useful module [re](https://docs.python.org/3/library/re.html#module-re) to wrangle our text file with regex.

## Re

Now to the juicy part. The code. First we import re and read in our file with the open context manager, write a list comprehension that strips the leading and trailing whitespaces for each line in the text file and save it to a list object.

```python
import re

with open("trash-movie-list.txt", ) as file:
    # read txt file, convert to list
    lines = [x.strip() for x in file.readlines()]

```

We save the regex search pattern as a string and create another variable to replace matched patterns with an empty string. We use the sub method from the re module to replace all matched sequences with an empty string. We wrap this in another list comprehension and strip the lines again.

```python
# replace all numberings and everything in front the dashes
pattern = '\-.*|^\d*.'
replace = ""

# store cleaned titles as specified by regex in a new list
trash_list = [re.sub(pattern, replace, x).strip() for x in lines]

```

That's it! We can save the results to a Pandas DataFrame and check it out to see the processed movie titles.

```python
# store list in dataframe
bad_movies_df = pd.DataFrame(trash_list, columns=['Titles'])

test_df = bad_movies_df.head(10)

print(test_df)

```

![](../images/posts/trashdf.png)

## Wrapping Up

As you can see a lot of work goes into getting our data ready for future use in downstream applications. Data doesn't always come in a
useful or helpful format. Being able to spot and have the tools to wrangle data is thus essential for any aspiring data scientist
like myself! I hope you found this article interesting and helpful. You can find the source code [here](https://github.com/kostyafarber/trash-movie-classifier).


How to use Regular Expressions and Python to wrangle an iPhones Notes text file for data analysis.