---
title: "My First Contribution to Ladybird"
description: My first contribution to ladybird, my experience and how it relates to open source software development
date: "2024-09-29"
author: Kostya Farber
slug: "first-contribution-to-ladybird"
skip: false
head_title: "Browser Development: My First Contribution to Ladybird"
og_image: "posts/first-contribution-ladybird/og.png"
bullets:
  - item_colour: "#fccc0a"
    value: "S"
    font_colour: "black"
    tag: "systems"
  - item_colour: "#00933c"
    value: "C"
    font_colour: "white"
    tag: "c++"
reviewers:
  - Deirdre Murray-Wallace
  - Sam Atkins
---

I love hacking away at side projects. Anybody that has visited this site or knows me personally can safely assume I'm working on _something_ in my spare time. I think it's one of the best ways to learn programming and — it's just fun! However, sometimes hacking alone can get pretty isolating. For me anyway. Well, how can you get the best of both worlds? Hack away but _with_ people. I personally think one of the most satisfying ways to do this is to contribute to open source projects.

## The Again Bit
What do I mean by the journey begins again? This would suggest I did contribute to open-source at some point in time, which turns out is a true statement.[^imdby] When I started wanting to become a software engineer, I came across all these cool tools that people/companies built and gave out for others to use. I thought, that was so empowering. I wanted to help contribute to the open source tools that I use, and if it make me a better software engineer in the process then awesome!

## The Second Beginning
But what about this new beginning? Let me explain. I've always enjoyed systems programming and low-level computer concepts. I thought loads of systems software is written in c++ so why not learn that. As I do when I learn any language, I buy a textbook[^a-tour-of-cpp] and try read about the basics and then do some exercises.

I also like to start a project, as programming is not a spectator sport. You gain the most from doing. But I didn't want to start hacking alone again. So I thought why not find a cool open source project to contribute to as a way to learn? I decided [Ladybird](https://ladybird.org/), an independent browser built from scratch, might be a good option.

## Why Ladybird?
Nailing down the why of doing something usually leads to good results. There are a few facets to the "why" of choosing to work on this project. The most uninteresting part of it is that by day, I'm a full stack software engineer. Well, I suppose by night I also do the same thing, as I constantly hack on this site. Nonetheless, it's clear I work with web technologies _a lot_. 

Being able to peel another layer off the onion and understand how a browser works by contributing to a project trying to build one will undoubtedly make me a better software engineer when it comes to web technologies. I'll get first hand experience revealing exactly _how_ these technologies interact with the browser. 

This to me is the obvious, utilitarian answer. The more interesting reason, is simply that I think the project and its history is fucking awesome. Ladybird was originally part[^forked] of [SerenityOS](https://serenityos.org/), an operating system built from scratch by Andreas Kling whilst aiding his recovery from drug addiction. The fact that its humble beginning's started in a cabin in the woods[^cabin-in-the-woods] with Andreas hacking the thing together over a six month period, makes the story all the much more legendary. I also loved that the project's genesis was driven by an aesthetic component too. I love design and I thought trying to capture the zeitgeist of the nineties through the medium of an OS was a great way to give character to the project. 

Now SerenityOS is a large open source project with thousands of contributors and has been in my opinion a success. I truly believe one of the best parts of being a hacker, is living the hacker ethic and the success of this project has been a direct application of principle six[^hacker-ethic]. I wanted to get involved and try work on something with the people associated with this area of software.

So given that I'd figured out the why it was time to step off the sidelines and get into it!

## How I Made My First Contribution
I'd like to preface this with: I am a complete beginner on how browsers are built and c++. Given these two pretty important facts meant that this was/is an intimidating project for me. But we all start somewhere — I thought I'd take it one step at a time. I cloned the repo, joined the Discord channel and built Ladybird and just started playing around with it. 

I watched YouTube videos about browser internals, tracked the GitHub issues and engaged with discussion on the Discord with any questions I had. Everybody on the channel was responsive, nice and helpful. I'd try explore the code, figure out how all the parts interact and day after day it got a _little_ bit clearer.

I'd always been interested with typography, so I was exploring the code related to fonts and I came across a comment:

```c++ {5} 
// https://drafts.csswg.org/css-font-loading/#dom-fontfaceset-add
WebIDL::ExceptionOr<JS::NonnullGCPtr<FontFaceSet>>
FontFaceSet::add(JS::Handle<FontFace> face)

  // FIXME: Do the actual spec steps
```

and I thought why not. One of the great things about the Ladybird code is that it's really clear what is referencing the spec[^spec]. The next step was to get stuck in! I fired up the spec docs and tried to figure out how to implement those steps in the context of the codebase and after some review it culminated in my first [PR](https://github.com/LadybirdBrowser/ladybird/pull/1539).

It was exciting and rewarding to see my change go in. I was happy I was able to make progress quicker than I anticipated. People often say open-source can be addictive[^cabin-in-the-woods] (in a good way!) and I'm keen to keep trying to gain more experience and understanding in this strange new world of browser hacking.

## What Next?
Well, more hacking. But I also wanted to make this post as a way to track and document my progress. Maybe I'll make a post after my 50th commit (if I get there) or a feature I implement or a really nasty (but interesting) bug I helped fix. Whatever and whenever that moment is I'll know and I'll feel the need to write about it.

If you are reading this and you don't know if you want to contribute to open source or don't think you can do it, screw that! Find something that nags at your curiosity, get stuck in and after some hard work you'll get there. Or just come join the Ladybird community. Happy hacking :) 


[^imdby]: One of my first memorable (for me) [PRs](https://github.com/cinemagoer/cinemagoer/pull/406) was to a project called [Cinemagoer](https://github.com/cinemagoer/cinemagoer) which I used for my [bad movies](https://kostyafarber.com/project/bad-movies) project to obtain movie data. It was before I had my first software engineering job and taught me to navigate codebases I knew nothing about. A valuable skill that proved useful :).
[^a-tour-of-cpp]: For c++, I highly recommend [A Tour of C++](https://www.stroustrup.com/tour2.html) if you already know how to program. It's written by the creator of the language (always a good sign) and has everything you need to get started.
[^forked]: Ladybird got forked out of SerenityOS as it's own project. Read more about it [here](https://awesomekling.substack.com/p/forking-ladybird-and-stepping-down-serenityos).
[^cabin-in-the-woods]: Read through [this](https://corecursive.com/serenity-os-with-andreas-kling/#the-summer-cabin) where it's mentioned. Another snippet from the interview I _really_ liked was by Andreas therapist: “If you get addicted to cooking or to hiking, I don’t care. It’s so much better. Go do that. Eventually, you’ll get bored of it and find other things to do. Just don’t get back into the drugs.”. I feel like coding has been my saviour in that respect, I myself have an addictive personality and I'm glad programming has been my "addiction". There is always other things to get healthier things to get addicted to, my most recent being reading manga!
[^hacker-ethic]: Principle 6: ["Computers can change your life for the better"](https://en.wikipedia.org/wiki/Hacker_ethic)., if you want to learn more about hackers read Stephen Levy's great book: [Hackers: Heroes of the Computer Revolution](https://en.wikipedia.org/wiki/Hackers:_Heroes_of_the_Computer_Revolution).
[^spec]: When I refer to the spec I mean the [W3C web standards](https://www.w3.org/standards/) that guide the technical specifications of the internet. 






My first contribution to ladybird, my experience and how it relates to open source software development

Browser Development: My First Contribution to Ladybird

2024-09-28-first-contribution-to-ladybird.mdx

My First Contribution to Ladybird

---
title: "Building an Interactive Pokédex with LRU Cache (Part III)"
description: "Building a retro Pokédex with 60s-era hardware constraints: 10-slot memory limit using our WebAssembly LRU cache. Interactive demo showing cache eviction with Signetics 8-bit RAM and real Pokémon data."
date: "2024-08-29"
tags: react interactive demo pokemon visualization
author: Kostya Farber
slug: "lru-cache-part-3"
skip: false
og_image: "posts/lru-cache/og.png"
head_title: "Building an Interactive Pokédex with LRU Cache"
bullets:
  - item_colour: "#fccc0a"
    value: "S"
    font_colour: "black"
    tag: "systems"
  - item_colour: "#76D0BD"
    value: "CS"
    tag: "computer science"
reviewers:
  - Deirdre Murray-Wallace
  - Joe Eid
  - Spike Jensen
  - Martin Rabone
---

Welcome to the final part of our LRU cache journey! In [Part 1](/posts/lru-cache-part1), we explored the theory and fundamental data structures. In [Part 2](/posts/lru-cache-part2), we implemented our cache in Rust and compiled it to WebAssembly. Now it's time for the fun part - putting our WebAssembly LRU cache to work in a practical, interactive application.

## Using The Cache
I'm going to posit an interesting application of an LRU cache that includes Pokémon. Yes those things. Remember the Pokédex? It's pretty much a device that acts as an encyclopedia of Pokémon. But it only applies to ones you've caught or seen.

<Figure caption="Pokédex in action">
    <img className="w-full" src="../images/posts/lru-cache/pokedex-anim.webp" />
</Figure>

We are going to implement a special spec of a Pokédex.

## The Spec
Since obviously the technology in the Pokémon universe is still stuck in the 60s[^old-chip] our Pokédex can only hold a maximum of __10__ Pokémon, using the Signetics 8-bit RAM chip.

<Figure caption="Cover of Electronics Magazine Showcasing the Signetics 8-bit RAM">
    <img className="w-full" src="../images/posts/lru-cache/8bit-ram-magazine.jpg" />
</Figure>

As we explore Pokémon, we want to make wise choices on how we store and get rid of Pokémon once we find more. Let's say that Pokémon that we look up a lot are more important than ones we don't. In other words we want to scrap the Pokémon __accessed the least__.

The LRU Cache seems like a perfect data structure to use behind the scenes of our Pokédex.

## Implementation
We will need a way to represent this problem in terms of an LRU cache. I suppose we would need a way to map a Pokmeon to an item in the cache. One way to do this is to assign a uuid and map that to a Pokémon. The map then has keys as uuids that point to the underlying data structure that contains the Pokémon. It would like _something_ like this:

<Figure caption="data item in the Pokédex">
    <img className="w-full" src="../images/posts/lru-cache/pokedex-item.png" />
</Figure>

Great! Then our cache can handle the size by setting it's capacity and also the eviction of Pokémon we don't really view that much. Cool, but what does it look like in action?

## Pokédex
I decided to build this ~~React component~~ Pokédex using the wonderful `react-flow` library[^react-flow] to model what the inside of this Pokédex might look like. This is an MDX component that is running the wasm module we built earlier as the LRU cache along with some other React magic.

Try play around with it and see what happens! You can adjust the cache size, explore Pokémon, and retrieve the Pokémon. All these actions affect the underlying data structures[^ds] so we can see how adding, accessing and removing Pokémon work in practice and in relation to the LRU cache. You can drag, zoom in and out, and move the nodes around.

It will[^help-me-find-bugs] obey all the rules of an LRU cache as you perform the actions above. Use it to learn and visualise what happens under the hood of an LRU cache.

<PokemonCache />

As you can see, LRU caches have some real-life applications. Whilst Pokémon are arguably not real, building devices with constraints that match an LRU cache are.

## Real-World Applications

While our Pokédex example is fun, LRU caches have numerous practical applications in computing:

### Web Browser Caches
Browsers use LRU-like policies to manage cached web resources. When storage is full, the least recently accessed pages, images, and scripts are removed to make room for new content.

### Database Buffer Pools
Database management systems use LRU caches to keep frequently accessed pages in memory. This dramatically improves query performance by reducing disk I/O operations.

### Operating System Page Replacement
Operating systems employ LRU algorithms when managing virtual memory. When physical memory is full, the least recently used pages are moved to disk storage.

### CPU Caches
Modern processors use variants of LRU algorithms in their cache hierarchies to decide which cache lines to evict when new data needs to be loaded.

### Content Delivery Networks (CDNs)
CDNs use LRU policies to manage which content to keep cached at edge servers, ensuring popular content stays readily available.

## Performance Considerations

Our implementation using a deque has some trade-offs:

**Advantages:**
- Simpler to implement in Rust than linked lists
- Good for educational purposes and moderate-sized caches
- Integrates well with WebAssembly

**Disadvantages:**
- O(n) complexity for updates due to index shifting
- Higher memory overhead for index management

For production systems with high performance requirements, you might consider:
- Using language-specific optimized implementations
- Approximate LRU algorithms like LRU-K or Clock
- Hardware-accelerated cache implementations

## Lessons Learned

This project taught me several valuable lessons:

1. **Choose the right tool for the job**: Rust's ownership model makes certain data structures challenging to implement, but adapting the approach led to a working solution.

2. **WebAssembly integration complexity**: While powerful, integrating WebAssembly with modern web frameworks requires careful consideration of build processes and type safety.

3. **Educational value of visualization**: Building an interactive demo helped solidify understanding of how LRU caches behave in practice.

4. **Real-world constraints drive design**: The 60s-era Pokédex constraint provided a relatable context for understanding cache capacity limits.

## The End
This project took a lot longer than I thought it would. I ran into loads of obstacles with Rust, Linked Lists, WebAssembly, Next.js and all the things we covered in this post. Was it frustrating as hell? Yes. But did I learn a lot from it? Also yes.

This is what software engineering is all about, banging your head against the wall and building something for the sake of it, and sharing it with the world. I hope this post inspires you to go build random stuff and reap the joy of figuring stuff out along the way.

## Series Recap

Over this three-part series, we've covered:

- **Part 1**: The theoretical foundations of LRU caches and the data structures that power them
- **Part 2**: Implementing an LRU cache in Rust, tackling ownership challenges, and compiling to WebAssembly
- **Part 3**: Building a practical, interactive application that demonstrates LRU cache behavior

Whether you're working on system optimization, building web applications, or just curious about how caches work under the hood, I hope this series has provided valuable insights into both the theory and practice of LRU caches.

[^old-chip]: One of the [first](https://www.computerhistory.org/timeline/1966/#169ebbe2ad45559efbc6eb35720af51c) chips to use semi-conductors
[^react-flow]: I recommend this [library](https://reactflow.dev/) for anything graph and node based. Even Stripe use them for their [docs](https://reactflow.dev/showcase)!
[^ds]: The uuids represent the hashmap and the pokemon cards represent the deque.
[^help-me-find-bugs]: If you find any bugs let me know!

Building a retro Pokédex with 60s-era hardware constraints: 10-slot memory limit using our WebAssembly LRU cache. Interactive demo showing cache eviction with Signetics 8-bit RAM and real Pokémon data.

Building an Interactive Pokédex with LRU Cache

2024-08-29-lru-cache-part3.mdx

Building an Interactive Pokédex with LRU Cache (Part III)

---
title: "Implementing LRU Cache in Rust and WebAssembly (Part II)"
description: "When linked lists meet Rust's borrow checker: adapting LRU cache implementation using deques instead. From ownership battles to WebAssembly compilation - Part 2 of the journey into systems programming."
date: "2024-08-28"
tags: rust webassembly wasm systems programming
author: Kostya Farber
slug: "lru-cache-part-2"
skip: false
og_image: "posts/lru-cache/og.png"
head_title: "Implementing LRU Cache in Rust and WebAssembly"
bullets:
  - item_colour: "#fccc0a"
    value: "S"
    font_colour: "black"
    tag: "systems"
  - item_colour: "#00933c"
    value: "G"
    font_colour: "white"
    tag: "go"
reviewers:
  - Deirdre Murray-Wallace
  - Joe Eid
  - Spike Jensen
  - Martin Rabone
---

Welcome back! In [Part 1](/posts/lru-cache-part1), we explored the theory behind LRU caches and the fundamental data structures that make them tick. Now it's time to get our hands dirty with implementation. But here's the twist - we're going to implement it in Rust and then compile it to WebAssembly for use in web applications.

## An Implementation in Rust
Firstly, why Rust? I enjoy systems programming and I have wanted to experiment with WebAssembly (Wasm) and thought this would be a good idea. Boy was I wrong. Before we dive in, let's quickly sidestep and ask ourselves _why_ this was a bad idea.

## Linked Lists and Rust
Apparently these two don't mesh well together. You can find discussions on linked lists in Rust[^disc-ll], tutorials on how create them in Rust[^create-ll] and why they are hard to write in Rust[^hard-ll]. For a hobby and educational project I clearly bit off more than I can chew. I didn't want to use a crate[^no-crate] for the linked list because I wanted to implement something myself to maximise my learnings.

If I wanted to continue to use Rust for this project, I'd have to adapt and find new ways to implement the cache. Moments like these teach you more deeply about what a programming language is well suited for. Rust clearly is not well suited[^not-suited] for linked lists.

This leaves no choice but to explore different data structures for the implementation in Rust. Enter: double ended queues (deque).

## Deques
A deque is a data structure similar to a queue[^deque] but it allows inserting and deleting at _both_ ends of the queue. This allows for the same functionality as having accesss to the head and tail of a doubly linked list.

<Figure caption="a deque, showing a pop and push operations on both ends">
<img src="../images/posts/lru-cache/double-ended-queue.svg" alt="" />
</Figure>

However, what does the hashmap point to now? The items in the deque are not nodes anymore with left and right pointers. You might be thinking: _"we can just store the indexes of each item in the hashmap for constant access!"_.

You'd be right to think that we are going to store the indexes and _slightly_ right in thinking that we maintain our constant time. Because we have introduced indexes, we are going to have to shift all of these indexes by 1 up until the node we are processing, a worst case $$O(n)$$ operation.

Some of you will probably be raging into the screen thinking that there are better ways to do this. You'd be absolutely correct but at this point I didn't want to get bogged down into making this ultra efficient. It is after all an educational project and meant to be somewhat fun. Plus, we've got Pokémon to attend to!

## Implementation in Rust... Again
Before we dive into the code, let's zoom out. What kind of API should our cache have? Fortunately it's pretty simple. Only two operations:

* `get(value) -> value`
* `put(value)`

We want to get values from the cache and put values into the cache. So, without further ado, let's get started!

## The Code

We want to define a struct that will hold the model of our cache. It will have a capacity defined by the user, hence the only public field is `pub capacity: usize{:rust}`.


```rust title="lib.rs" caption="a struct that represents the LRU cache"
pub struct LRU {
    pub capacity: usize,
    map: HashMap<String, usize>,
    q: VecDeque<String>,
}
```

I've chosen to simply map a `String{:rust}` to the index as I'm going to go with uuids[^uuid] to link any arbitrary item in the cache.

I've defined two helper methods to manage the state of the cache as we `get` and `put` into it.

```rust title="lib.rs" caption="helper methods"
fn update_map_values(&mut self) {
    for (idx, key) in self.q.iter().enumerate() {
        self.map.insert(key.to_string(), idx);
    }
}

fn make_node_head(&mut self, idx: usize, key: &str) {
    self.q.remove(idx);
    self.q.push_front(key.to_string());

    self.update_map_values();
    self.map.insert(key.to_string(), 0);
}
```

The first, lazily updates all the hashmap indexes with the new state of the queue. The second will make the value that has just either been `put` or `get` into the head node[^node-semantics].

The final methods are the actual user facing `get` and `put`.

```rust title="lib.rs" caption="the juicy stuff"
pub fn get(&mut self, key: &str) -> Option<String> {
    if let Some(&idx) = self.map.get(key) {
        self.make_node_head(idx, key);
        return Some(key.to_string());
    } else {
        return None;
    }
}

pub fn put(&mut self, key: &str) {
    if self.q.len() == self.capacity {
        let remove_key = self.q.pop_back().unwrap();
        self.map.remove(&remove_key);
    }

    self.q.push_front(key.to_string());
    self.update_map_values();
    self.map.insert(key.to_string(), 0);
}
```

The `get` simply gets the value if it's there and makes it the head, otherwise it will return `None{:rust}`. Performing a `put` will, if the capacity is full, remove the tail node[^lru] and then put the item in the cache and make it the head node. That's it!

All together it looks like this:

```rust title="lib.rs"
#[wasm_bindgen]
pub struct LRU {
    pub capacity: usize,
    map: HashMap<String, usize>,
    q: VecDeque<String>,
}

#[wasm_bindgen]
impl LRU {
    #[wasm_bindgen(constructor)]
    pub fn new(capacity: usize) -> LRU {
        utils::set_panic_hook();
        LRU {
            capacity,
            map: HashMap::new(),
            q: VecDeque::new(),
        }
    }

    fn update_map_values(&mut self) {
        for (idx, key) in self.q.iter().enumerate() {
            self.map.insert(key.to_string(), idx);
        }
    }

    fn make_node_head(&mut self, idx: usize, key: &str) {
        self.q.remove(idx);
        self.q.push_front(key.to_string());

        self.update_map_values();
        self.map.insert(key.to_string(), 0);
    }

    #[wasm_bindgen(getter, skip_typescript)]
    pub fn queue(&self) -> JsValue {
        serde_wasm_bindgen::to_value(&self.q).unwrap()
    }

    #[wasm_bindgen(getter, skip_typescript)]
    pub fn map(&self) -> JsValue {
        serde_wasm_bindgen::to_value(&self.map).unwrap()
    }

    pub fn get(&mut self, key: &str) -> Option<String> {
        if let Some(&idx) = self.map.get(key) {
            self.make_node_head(idx, key);
            return Some(key.to_string());
        } else {
            return None;
        }
    }

    pub fn put(&mut self, key: &str) {
        if self.q.len() == self.capacity {
            let remove_key = self.q.pop_back().unwrap();
            self.map.remove(&remove_key);
        }

        self.q.push_front(key.to_string());
        self.update_map_values();
        self.map.insert(key.to_string(), 0);
    }
}
```
You may have noticed that there are some extra methods and macros[^bindgen-macros] I haven't talked about. Not to worry, these link into the next part of the puzzle: WebAssembly.

## WebAssembly
WebAssembly (Wasm) is a type of code that compiles to a binary that can run in your browser[^what-wasm] at native speeds[^fast-wasm]. It can compile from C, C++, Go and Rust amongst others in the ecosystem. This sounds like a great deal for those looking to improve performance on compute heavy tasks _but_ it seems the jury is still out[^jury-wasm].

Nonetheless, I thought trying to run my Rust LRU code in this project could be a cool thing to experiment with. Curiosity is the name of the game here. But how do I go about doing this? Luckily, there is quite a handy crate that can help us out: `wasm-pack`.

## Wasm-Pack
Wasm-pack is a great open-source tool that helps compile Rust code to Wasm and package it so we can use it in our web applications. It's recommended on the mdn web docs[^mdn-wasm] and makes the process of using wasm in your application a lot easier. This is one of the major benefits of using Rust as the language of choice to compile into Wasm. The ecosystem is more mature and supported than some of the other languages[^mature].

It works by packaging your Rust code as an npm package that we can directly install into our web app by adding it into the `package.json`. Easy as that! Running `wasm-pack build --target bundler` will yield something similar to:

```ansi caption="running the wasm-pack tool to generate an npm package"
$ wasm-pack build --target bundler
[INFO]: 🎯  Checking for the Wasm target...
[INFO]: 🌀  Compiling to Wasm...
   Compiling lru-wasm v0.1.0 (/repos/wasm-lru)
    Finished `release` profile [optimized] target(s) in 2.17s
[INFO]: ⬇️   Installing wasm-bindgen...
[INFO]: Optimizing wasm binaries with `wasm-opt`...
[INFO]: Optional fields missing from Cargo.toml: 'description', 'repository', and 'license'. These are not necessary, but recommended
[INFO]: ✨   Done in 3.72s
[INFO]: 📦   Your wasm pkg is ready to publish at /repos/wasm-lru/pkg.
```

You may be asking: _"why am I setting the target as bundler"_. Well, in my case I am using Next.js which uses webpack so I could target a bundler and secondly it makes using our package much simpler[^simple].

It's all well and good that `wasm-pack` bundles our code ready to be imported into a web app but how does it interface with Rust when you are writing Rust code, and for that matter TypeScript?

## Using Wasm with TypeScript
Wasm-pack greatly simplifies the process of compiling Rust to Wasm and using it in a Javascript or TypeScript project.

Remember those macros I said I'd talk about, the ones labelled `#[wasm_bindgen]{:rust}`? Let's revisit them in this section. They are what expose the functions that will be accessible to both Rust and Javascript[^important-bindgen]. They can not only be applied to functions but also to structs as per the Rust code above.

So it's as easy as that! Slap on `#[wasm_bindgen]{:rust}` and reap the rewards of using those Rust functions in Javascript. Well... not exactly.

You see, the LRU struct has the `HashMap<String, usize>{:rust}` and `VecDeque<String>{:rust}` fields which aren't supported types in `wasm-pack`[^non-supported-types].


```rust title="lib.rs", caption="problematic map and q fields" {4,5}
#[wasm_bindgen]
pub struct LRU {
    pub capacity: usize,
    map: HashMap<String, usize>,
    q: VecDeque<String>,
}
```

However we aren't entirely stuck here, instead we can use the `serde`[^serde] package, which handles sending arbitrary data to Javascript[^arbitrary-serde] for use.

```rust title="lib.rs" caption="how we choose to expose the deque and map"
#[wasm_bindgen(getter, skip_typescript)]
pub fn queue(&self) -> JsValue {
    serde_wasm_bindgen::to_value(&self.q).unwrap()
}

#[wasm_bindgen(getter, skip_typescript)]
pub fn map(&self) -> JsValue {
    serde_wasm_bindgen::to_value(&self.map).unwrap()
}
```

You might be wondering why I've added this new macro ```#[wasm_bindgen(getter, skip_typescript)]{:rust}``` that looks like it's telling the packager to skip TypeScript when the heading of this section suggests an explanation of how to use TypeScript _with_ Wasm.

Creating seamless automated typing from Rust to TypeScript with the current ecosystem is hard[^typing-hard]. `wasm-bindgen` does provide lots of attributes[^attributes] that can help export some useful typing for us but it lacks when it comes to the non standard data types I'm using here. If you run `wasm-pack` you'll get the file:

```typescript title="lru_wasm.d.ts" caption="the current typing"
/* tslint:disable */
/* eslint-disable */
/**
*/
export class LRU {
  free(): void;
/**
* @param {number} capacity
*/
  constructor(capacity: number);
/**
* @param {string} key
* @returns {string | undefined}
*/
  get(key: string): string | undefined;
/**
* @param {string} key
*/
  put(key: string): void;
/**
*/
  capacity: number;
}
```

Evidently, the `map: HashMap<String, usize>{:rust}` and `q: VecDeque<String>{:rust}` are missing from the type definitions, as we specified to skip them with `skip_typescript{:rust}`. If we chose to include these (i.e removing the `skip_typescript{:rust}`) then our types would look like this:

```typescript title="lru_wasm.d.ts" caption="the current typing"
/* tslint:disable */
/* eslint-disable */
/**
*/
export class LRU {
  free(): void;
/**
* @param {number} capacity
*/
  constructor(capacity: number);
/**
* @param {string} key
* @returns {string | undefined}
*/
  get(key: string): string | undefined;
/**
* @param {string} key
*/
  put(key: string): void;
/**
*/
  capacity: number;

  readonly queue: any; // [!code ++]
  readonly map: any; // [!code ++]
}
```

which isn't very useful in TypeScript. How do we get around this? It's not very straightforward. I tried multiple solutions using different crates[^different-crates], using ```typescript_type{:rust}```[^ts-type] but nothing suited what I needed.

Instead I chose to generate what I could with the bindings (as seen in the first `lru_wasm.d.ts`) and extend the class on the frontend.

```typescript caption="a bit janky but it worked"
export class LRU extends WasmLru {
  readonly map: Map<string, number>;
  readonly queue: Array<string>;
}
```

Finally, we have packaged the wasm module and have it typed. What's next is to actually use it.

## Wasm and MDX
I use [MDX](https://mdxjs.com/) to write blog posts. It allows for more interesting posts that can utilise the magic of React components and embed them into your markdown. It's awesome. I decided to try my hand at including a React component that uses the wasm module built above in an interesting way.

As has been the central theme to this project, _it wasn't easy_ to integrate the wasm module into MDX on Next.js. Thankfully I came across an article[^wasm-workaround] that explains a workaround for using wasm on Next.js, however this wasn't the end of the woes.

Since MDX is rendered on the server, I was getting an error when bundling[^error-bundling] my wasm component with my MDX files. The solution here was to load the module dynamically and to not render it on the server.

```typescript caption="dynamic imports that then get bundled with mdx"
import dynamic from "next/dynamic";

const DynamicWasmModule = dynamic(
  () =>
    import("@components/mdx/WasmModule").then(
      (mod) => mod.WasmComponent
    ),
  {
    ssr: false,
  }
);
```

Now the show can finally begin: running wasm code on the client used in this very mdx file.

## What's Next?
We've successfully implemented an LRU cache in Rust and compiled it to WebAssembly for use in web applications. We've overcome the challenges of Rust's ownership system by adapting our approach with deques, and we've navigated the complexities of TypeScript integration.

In **Part 3**, we'll put our WebAssembly LRU cache to work in a practical and fun application: building an interactive Pokédex! We'll explore how LRU caches apply to real-world scenarios and create a visual demonstration that brings together everything we've learned.

[^disc-ll]: They are quite [contentious](https://news.ycombinator.com/item?id=16442743) apparently
[^hard-ll]: This is [one](https://rust-unofficial.github.io/too-many-lists/) way to learn a new languge
[^create-ll]: [Further reading](https://rcoh.me/posts/rust-linked-list-basically-impossible/)
[^no-crate]: Rust's internal package manager
[^not-suited]: Simply anyways
[^deque]: If you want to know more about queues, just visit [wikipedia](https://en.wikipedia.org/wiki/Queue_(abstract_data_type))
[^uuid]: [Pretty much a unique identifier](https://en.wikipedia.org/wiki/Universally_unique_identifier)
[^node-semantics]: They aren't really nodes as we are using a deque now, but thought I'd keep the semantics consistent
[^lru]: The least recently used node!!!
[^bindgen-macros]: More on macros [here](https://doc.rust-lang.org/book/ch19-06-macros.html)
[^what-wasm]: [The official docs](https://webassembly.org/)
[^fast-wasm]: Apparently not [too](https://news.ycombinator.com/item?id=30156437) bad
[^jury-wasm]: [A great critical read about why maybe performance isn't the best feature of wasm](https://nickb.dev/blog/the-webassembly-value-proposition-is-write-once-not-performance/)
[^mdn-wasm]: See [here](https://developer.mozilla.org/en-US/docs/WebAssembly/Rust_to_Wasm#wasm-pack) for the full tutorial
[^mature]: I'm loooking at you Go
[^simple]: Pretty much you have to manually `init` the module in a `useEffect` instead of simply importing and using the package if you [don't target a bundler](https://rustwasm.github.io/wasm-bindgen/examples/without-a-bundler.html).
[^important-bindgen]: [They are one of the most important things to know about `wasm-pack`](https://rustwasm.github.io/wasm-pack/book/tutorials/npm-browser-packages/template-deep-dive/src-lib-rs.html#1-wasm_bindgen-functions)
[^non-supported-types]: See [here](https://rustwasm.github.io/wasm-bindgen/reference/types.html) for supported types
[^serde]: Useful for serialising and deserialising Rust data structures
[^arbitrary-serde]: [Here](https://rustwasm.github.io/wasm-bindgen/reference/arbitrary-data-with-serde.html) are the docs that explain how to do it
[^typing-hard]: I was banging my head with `tsify` and `ts-rust` and searching online and using Claude and couldn't really find something that worked easy
[^attributes]: For instance I used `skip_typescript`, `getter` and `constructor`, see the docs [here](https://rustwasm.github.io/wasm-bindgen/reference/attributes/index.html)
[^different-crates]: Libraries include [tsify](https://github.com/madonoharu/tsify) and [ts-rs](https://github.com/Aleph-Alpha/ts-rs)
[^ts-type]: This did look **promising** however going with this [approach](https://rustwasm.github.io/wasm-bindgen/reference/attributes/on-js-imports/typescript_type.html) would mean just re-writing the whole type from scratch, I wanted to use a mix of automated and patched
[^wasm-workaround]: Thank god for [this](https://implfuture.dev/blog/building-a-blog-like-its-2022)
[^error-bundling]: I use Kent Dodds blazingly fast [mdx bundler](https://github.com/kentcdodds/mdx-bundler)

When linked lists meet Rust's borrow checker: adapting LRU cache implementation using deques instead. From ownership battles to WebAssembly compilation - Part 2 of the journey into systems programming.

Implementing LRU Cache in Rust and WebAssembly

2024-08-28-lru-cache-part2.mdx

Implementing LRU Cache in Rust and WebAssembly (Part II)

Cache 'Em All: From MMORPG treasure chests to computer science, exploring LRU caches through the lens of Pokémon. A journey into data structures, Rust, and WebAssembly implementation.

Cache 'Em All: Creating a Pokédex with Rust and WebAssembly

2023-09-29-lru-cache.mdx

Creating a Pokédex with Rust and WebAssembly

---
title: "Understanding LRU Caches: Theory and Data Structures (Part I)"
description: "From MMORPG treasure chests to computer science: understanding LRU caches from the ground up. Part 1 of a 3-part series exploring theory, implementation, and how they connect to Rust, WebAssembly, and Pokémon."
date: "2024-08-27"
tags: data-structures algorithms cache computer-science
author: Kostya Farber
slug: "lru-cache-part-1"
skip: false
og_image: "posts/lru-cache/og.png"
head_title: "Understanding LRU Caches: Theory and Data Structures"
bullets:
  - item_colour: "#fccc0a"
    value: "S"
    font_colour: "black"
    tag: "systems"
  - item_colour: "#76D0BD"
    value: "CS"
    tag: "computer science"
reviewers:
  - Deirdre Murray-Wallace
  - Joe Eid
  - Spike Jensen
  - Martin Rabone
---

When I think of the word cache, it evokes images of mystical inventory items found in an MMORPG. Think Diablo[^diablo], Runescape[^runescape] or maybe even Star Wars: The Old Republic[^star-wars] for those fans of space operas.

<Figure caption="The flesh raiders must have some pretty cools stuff in there">
  <img
    src="../images/posts/lru-cache/swotr-weapons-cache.jpg"
    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.

If this article isn't about those then what is it about? Well it's about understanding LRU caches from the ground up. This is Part 1 of a 3-part series where we'll explore the theory, implementation, and practical applications of LRU caches. By the end of this series, I'll show you how LRU caches, Rust, WebAssembly, and Pokémon all connect in an interesting way!

## 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[^type-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-process.svg"/>
</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 **E** is replaced with **F** as **E** 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 vein TL;DR, we will only explore one of them. 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*.

<Figure caption="a doubly linked list">
  <img src="../images/posts/lru-cache/doubly-linked-list.svg"/>
</Figure>

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 and next nodes relative to the current node. We need this information when removing nodes.

The code[^python-ddl] below in Python, which is pretty simple, would look something like this:

```python title="ddl.py" caption="a simple way to delete a node in a doubly linked list"
def delete_node(self, dele):
        # Base Case
        if self.head is None or dele is None:
            return

        # If node to be deleted is head node
        if self.head == dele:
            self.head = dele.next

        # Change next only if node to be deleted is NOT
        # the last node
        if dele.next is not None:
            dele.next.prev = dele.prev

        # Change prev only if node to be deleted is NOT
        # the first node
        if dele.prev is not None:
            dele.prev.next = dele.next
```

Putting it all together, we have something that resembles the diagram below, with our first sighting of Pokémon. Here we have a map of Pokémon pointing to linked list nodes that can contain any relevant data that we need.

<Figure caption="an lru cache, with a hashmap and linked list">
  <img src="../images/posts/lru-cache/lru-cache.svg"/>
</Figure>

## What's Next?
Now that we understand the theory behind LRU caches and the fundamental data structures involved, we're ready to dive into implementation. In **Part 2**, we'll explore how to implement this in Rust, the challenges we'll face with linked lists in Rust's ownership system, and how we'll adapt our approach using different data structures. We'll also discover how to compile our Rust code to WebAssembly for use in web applications.

Stay tuned for the next part where theory meets practice!

[^diablo]: [One type of cache you might find in Diablo 4](https://diablo.fandom.com/wiki/Horadric_Cache)
[^runescape]: [This one is more pertinent to the type of cache we are talking about](https://runescape.fandom.com/wiki/Jagex_cache)
[^star-wars]: [Maybe a time not to raid a weapons cache](https://starwars.fandom.com/wiki/Raid_on_the_Flesh_Raider_weapons_cache)
[^type-cache]: More specifically we say the eviction [policy](https://en.wikipedia.org/wiki/Cache_(computing)#Policies) tells us what type the cache is
[^python-ddl]: Good old [GFG](https://www.geeksforgeeks.org/delete-a-node-in-a-doubly-linked-list/)

From MMORPG treasure chests to computer science: understanding LRU caches from the ground up. Part 1 of a 3-part series exploring theory, implementation, and how they connect to Rust, WebAssembly, and Pokémon.

Understanding LRU Caches: Theory and Data Structures

2024-08-27-lru-cache-part1.mdx

Understanding LRU Caches: Theory and Data Structures (Part I)

---
layout:	post
title: Bit Vectors
description: "Exploring bit vectors: compact data structures for efficient set operations and memory optimization. Understanding how bits can represent complex data with minimal overhead."
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.

Exploring bit vectors: compact data structures for efficient set operations and memory optimization. Understanding how bits can represent complex data with minimal overhead.

2023-09-29-bit-vectors.mdx

Bit Vectors

---
layout:	post
title: Contexts in Golang
description: "Understanding Go contexts: managing request lifecycles, cancellation, and timeouts in concurrent applications. Essential patterns for robust Go development."
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

Understanding Go contexts: managing request lifecycles, cancellation, and timeouts in concurrent applications. Essential patterns for robust Go development.

2023-08-13-golang-contexts.mdx

Contexts in Golang

---
layout:	post
title: Abstract Methods On a Property	
description: "Exploring abstract methods applied to properties in object-oriented programming. Design patterns and implementation techniques for flexible class hierarchies."
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

Exploring abstract methods applied to properties in object-oriented programming. Design patterns and implementation techniques for flexible class hierarchies.

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

Abstract Methods On a Property

---
title: Vim Macros
description: "Automating tedious text editing with Vim macros: from recording keystroke sequences to transforming lists into Python-ready data structures. Why these simple tools are incredibly powerful for developers."
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.

<Figure caption="airflow macros">
<img src="../images/posts/vim-macros/airflow_macro.gif" />
</Figure>
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).

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

<Figure caption="navigating quote">
  <img src="../images/posts/vim-macros/quote_macro.gif" />
</Figure>
## Navigating Ticks

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

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

<Figure caption="navigating ticks">
  <img src="../images/posts/vim-macros/tick_macro.gif" />
</Figure>

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

**EDIT**: I can't believe I created macros to navigate ticks and quotes when vim.targets[^targets] exists.

[^targets]: All my macros can do plus more, I'd highly recommend the [plugin](https://github.com/wellle/targets.vim)


Automating tedious text editing with Vim macros: from recording keystroke sequences to transforming lists into Python-ready data structures. Why these simple tools are incredibly powerful for developers.

Why Vim Macros Are Awesome and How to Use Them

2023-05-03-vim-macros.mdx

Vim Macros

---
title: Terminal GIFs
description: "Creating terminal recordings programmatically with VHS by Charm Bracelet. Command line as code for generating GIFs of terminal sessions, complete with ASCII art and neofetch demos."
date: "2023-05-02"
tags: data-structures algorithms breadth-first-search art copenhagen contemporary
slug: "vhs-cli"
head_title: "VHS by Charm Bracelet, Create Terminal GIFs Programmatically"
bullets: 
  [
    {
      item_colour: "#fccc0a",
      value: "S",
      font_colour: "black",
      tag: "systems"
    },
    {
      item_colour: "#00933c",
      value: "G",
      font_colour: "white",
      tag: "go"
    },
  ]
skip: false
---

## 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.


Creating terminal recordings programmatically with VHS by Charm Bracelet. Command line as code for generating GIFs of terminal sessions, complete with ASCII art and neofetch demos.

VHS by Charm Bracelet, Create Terminal GIFs Programmatically

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);
}
```

```ansi 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: "Deleting the Rightmost Bit"
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

Deleting the Rightmost Bit

---
layout:	post
title:	"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 Its 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. These come in the form of binary numbers, and are usually defined as constants.


```c
#define O_RDONLY        0b00000000 
#define O_CREAT         0b00000100 
#define O_TRUNC         0b00001000
```

We can define a combination of these flags using the bitwise `OR` operator.

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

The binary representation of these flags `0b00001100`. How does `open()` use this to intepret what flags we have set? It uses the bitwise `AND` 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, we obtain

```bash
00000100 &
00001100
---
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 to boolean flags.

The open(2) System Call and How Its Flags Are Used

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

Open Flags in UNIX

---
title:	"Checking if a Number is Odd with a Bitwise Operator"
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 asking:

> Are both bits 1?

## Example
For example, take the bitwise and operation below:

```bash
01001001 &
00101000
---
00001000
```

The result has only the 5th position set as both have 1s set in that position.

## 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 `AND` 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.

Take 17. In binary it is `10001`. If we `AND` this with one

```bash
10001 &
00001
-----
00001
```

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

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

```bash
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():
    higher = (2**31) / 2
    lower = -higher
    for _ in range(100):
        time_start = time.time()
     
        arr = np.random.randint(
            lower, 
            higher, 
            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()
    higher = (2**31) / 2
    lower = -higher
    for _ in range(100):
        arr = np.random.randint(
            lower, 
            higher, 
            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

Checking if a Number is Odd with a Bitwise Operator

---
layout:	post
title:	"Replacing Characters in an Array in C"
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

Replacing Characters in an Array in C

---
title:	"Passing Arrays to Functions in C"
description: "Deep dive into C programming: Why arrays lose their size when passed to functions and the two main strategies for iteration - terminal values vs explicit size parameters. Essential concepts for systems programming."
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.

Deep dive into C programming: Why arrays lose their size when passed to functions and the two main strategies for iteration - terminal values vs explicit size parameters. Essential concepts for systems programming.

Passing Arrays to Functions in C and the Terminal Value

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

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 Its 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 Its 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 Its 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 Its 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: Bitcoin Real-Time Streaming Data Pipeline
head_title: ""
description: "Building a real-time Bitcoin trading data pipeline with Kafka and Docker. From Deribit API websockets to order book imbalance calculations - exploring microservices architecture for cryptocurrency market data streaming."
subtitle: "A DevOps project utilising Docker, Kafka and Microservice Architecture Principles"
date: "2022-08-06"
slug: "crypto-kafka-screaming"
skip: false,
bullets:
  [
    { item_colour: "#996633", value: "D", tag: "data" },
    { item_colour: "#0039a6", value: "P", tag: "python" },
  ]
---

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

I originally intended to create an algorithmic trading system based on limit order book (LOB) data. I wanted to trade cryptocurrency **perpetual** futures.

> The Deribit Perpetual is a derivative product similar to a future, however, without an expiry date. The perpetual contract features funding payments. These payments have been introduced to keep the perpetual contract price as close as possible to the underlying crypto price - the Deribit BTC Index.

I also wanted to choose a platform that provides an API where I could access live LOB data. I chose [Deribit](https://www.deribit.com/) as they meet both my needs.

<Figure caption="Deribit Logo">
  <img
    src="../images/projects/kafka-streaming/deribit-logo.png"
    alt="Deribit Logo"
    width="400"
    style={{ margin: "auto" }}
  />
</Figure>

## Python Websocket

Deribit provides three different interfaces to access the API:

- JSON-RPC over Websocket
- JSON-RPC over HTTP
- FIX (Financial Information eXchange)

I decided to use JSON-RPC over Websocket. JSON-RPC is a light-weight remote procedure call (RPC) protocol. The JSON-RPC specification defines the data structures that are used for the messages that are exchanged between client and server, as well as the rules around their processing. JSON-RPC uses JSON (RFC 4627) as data format.

```python caption="An example of a request message"
{
    "jsonrpc": "2.0",
    "id": 8066,
    "method": "public/ticker",
    "params": {
        "instrument": "BTC-24AUG18-6500-P"
    }
}
```

I used [this](https://github.com/ElliotP123/Deribit-API_Authentication-Examples/blob/master/JSON-RPC_Websockets/JSON-RPC_Websockets-AuthenticationExample.py) code as a base to create my websocket client in Python to access the live streaming data for the perpetual futures. It handles the authentication and subsequent subscription of the required data.

## Subscription Management

The subscribe method can be used to subscribe to one or more channels. In most cases the channel name is constructed from a couple of elements. This makes it possible to specify exactly which information is required, and/or the frequency or aggregation level. These elements are considered parameters for the subscription.

For example, when subscribing to the channel `book.BTC-27JUL18.10.20.100ms`, the element `BTC-27JUL18` specifies that the name of the instrument (see naming), 10 means that the results should be grouped to that precision, etc.

## Streaming Order Book Data

For my purporses I subscribe to the `book.{instrument_name}.{group}.{depth}.{interval}`, which notifies the subscriber about changes to the order book for a certain instrument.


```python caption="An example notification for Ethereum (ETH)."
{
  "params" : {
    "data" : {
      "timestamp" : 1554375447971,
      "instrument_name" : "ETH-PERPETUAL",
      "change_id" : 109615,
      "bids" : [
        [
          160,
          40
        ]
      ],
      "asks" : [
        [
          161,
          20
        ]
      ]
    },
    "channel" : "book.ETH-PERPETUAL.100.1.100ms"
  },
  "method" : "subscription",
  "jsonrpc" : "2.0"
}
```

## Limit Order Book

The objective was to obtain an indicator that could point to the state of the market at a certain point in time. An **order book** is the list of orders that a trading venue uses to record the interest of buyers and sellers in a particular financial instrument.

<Figure caption="Limit Order Book Diagram">
  <img
    src="../images/projects/kafka-streaming/lob-diagram.png"
    width="500"
    style={{ margin: "auto" }}
  />
</Figure>

## Order Book Imbalance

The Order Book Imbalance is the difference between the best bid and best ask quantity quotes divided by its sum. Such that,

```math caption="dsa"
Imb*{t} = \frac{V*{t}^b - V*{t}^a}{V*{t}^b + V\_{t}^a}
```

The Order Book Imbalance measures whether the limit order book is buy or sell heavy. In fact, it is a good predictor of price direction.

## Designing the Architecture

Having all the groundwork laid in place I went about deciding on how I wanted to design this system. To make things simpler and get my hands dirty with the current trend of microservices, I wanted to use Docker and Kafka to build a simple and scalable ETL pipeline.

## Docker

Docker is a valuable tool for developers to ship and deploy their apps in an easy and accessible way. We can create _containers_ that are self-contained environments that house our applications. Taking this a step further, we can decouple our system and build a microservices architecture by having our services in their own docker containers. I will use Docker to containerize a few services used for the data pipeline built using Kafka.

## Kafka

Apache Kafka is an open-source distributed event streaming platform used by thousands of companies for high-performance data pipelines, streaming analytics, data integration, and mission-critical applications.

It uses a publisher and subscriber architecture, both of which are decoupled from the core functionality of Kafka. Apache Kafka has an API in Python called `kafka-python`. Using `kakfa-python` I am able to build the data pipeline using Python.

## Data Pipeline

The image below demonstrates the data pipeline utilising Docker and Kafka. We have seperate containers containing each microservice and Kafka itself. The Deribit producer container connects to the Derbit API and streams JSON records and publishes them to Kafka in a channel called _prices_.

Seperately, the consumer connects to the _prices_ topic and transforms the raw JSON into order flow imbalance and mid-price variables.

## Microservices

Each service is unaware of the other but communicate through docker networking. By using Docker and Kafka we are able to create a scalable and fault tolerant architecture were each service is decoupled from one another. This is at the heart of modern day software engineering and enables large distributed systems to work efficiently.

## Wrapping Up

The purporse of this project was to get my hands dirty with real-time streaming data and containizeration technologies.
I was able to write code that consumed an API delivering JSON over websocket.
I designed a small distributed (capable) data pipeline using Kafka and containerized my services to adhere to microservice principles.
I was able to transform raw data to obtain useful Market Microstructure variables such as order flow imbalance and the mid-price.

Make sure to check out my GitHub for the source code and how to run it yourself!


Building a real-time Bitcoin trading data pipeline with Kafka and Docker. From Deribit API websockets to order book imbalance calculations - exploring microservices architecture for cryptocurrency market data streaming.

2022-08-06-crypto-perpetual-futures-kafka-streaming.mdx

A DevOps project utilising Docker, Kafka and Microservice Architecture Principles

Bitcoin Real-Time Streaming Data Pipeline

---
title: Car Sales Scraper
head_title: ""
description: "How I built a car price monitoring system with BeautifulSoup and AWS before moving to London. Daily scraping of carsales.com.au with Lambda, DynamoDB, and SNS to get the perfect selling price for my Mazda 3."
bullets:
  [
    {
      item_colour: "#ff6319",
      value: "A" ,
      tag: "aws",
      font_colour: "white",
    },
    {
      item_colour: "#0039a6",
      value: "P",
      tag: "python",
      font_colour: "white",
    },
    {
      item_colour: "#996633",
      value: "D", 
      tag: "data",
      font_colour: "white",
    },
  ]
skip: false
date: "2022-07-03"
subtitle: "Web scraper that helped sell my car using a data-driven approach"
slug: "car-sales-scraper"
---

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

In mid-2022 I made the move to relocate to London. An inevitable part of moving overseas is getting rid of any belongings you don't need to take with you. One of these belongings was my _2013 Mazda 3 Sedan_. A fundamental question that needs to be answered is:

> How much is my car worth on the second hand market?

I've found myself an interesting problem that I needed to solve to help me get a fair price for my car. I decided to create an application that would give me a data-driven answer to my problem.

## How Did I Do It?


A popular site, [carsales.com.au](https://www.carsales.com.au/) allows users to sell their second-hand cars. This acts as a marketplace for buyers and sellers. 

<Figure caption="car sales website">
  <img src="../images/projects/car-sales/car-sales-mockup.png" /> 
</Figure>

I searched for cars that fit the description of my Mazda. From here I could grab all the prices of the cars on the market (on carsales.com.au) and base my price of this. I used [BeautifulSoup](https://beautiful-soup-4.readthedocs.io/en/latest/) to scrape the html of the page and find the sales prices.


## Code

Using Google Chrome's inspect, I isolated the correct class, aptly named `title` in the `h1` tags. I used a class to implement my scraper called `CarSalesScraper`. It performs all the scraping tasks and data cleansing needed for ingestion into my database. You can find the source code in the GitHub link above.

## AWS
I employed Amazon Web Services (AWS) to manage my database solution, daily execution of the code and email notifications.

<Figure caption="aws services used">
  <img src="../images/projects/car-sales/tech-stack.png" />
</Figure>

- **AWS Lambda** managed the daily execution side.
- **AWS DynamoDB** was used to store the average, median and raw sales price
- Finally **AWS Simple Notification Service (SNS)** was used to send email notifications when my DynamoDB was written to.

## Challenges

One challenge I ran into was using packages that aren't available in the off the shelf Lambda. To make matters slightly more difficult my solution locally is on a **_Mac OS X_**. Lambda runs on **_Linux_**. So I couldn't simply package my implementation of BeautifulSoup onto a lambda layer as it's coming from a Mac.

## Solution
After some research online I found an easy solution within the AWS ecosystem. Cloud9.

<Figure caption="cloud9 and linux logos">
  <img src="../images/projects/car-sales/cloud9-linux.png" />
</Figure>

> AWS Cloud9 is a cloud-based integrated development environment (IDE) that lets you write, run, and debug your code with just a owser.

We can spin up this environment run on top of Linux and create a zip `deployment.zip` and use it to install packages into this zip.

```sh caption="installing pip packages into a target directory"
pip3 install -t . your_packages
```

Adding this zip to Lambda as a layer allows the managed service to access our package and our script can execute.

## Outcome

Using this solution I was able to get a gauge on the market. Every morning I got updates on the average, median and raw prices. I was able to adjust the prices accordingly day to day. Eventually I successfully sold my car for a good price. Being able to have data to inform my decision put me at ease and allowed me to set prices confidently. Using the cloud made creating this application a eeze and the joy from using technology to help others and myself is priceless!

source: [https://github.com/kostyafarber/car-sales](https://github.com/kostyafarber/car-sales)


How I built a car price monitoring system with BeautifulSoup and AWS before moving to London. Daily scraping of carsales.com.au with Lambda, DynamoDB, and SNS to get the perfect selling price for my Mazda 3.

2022-07-03-car-sales-scraper.mdx

Web scraper that helped sell my car using a data-driven approach

Car Sales Scraper

---
title: "Finding Data Structures and Algorithms in Art"
slug: "dsa-in-art"
description: "When preparing for tech interviews meets Copenhagen Contemporary art: discovering the Breadth First Search algorithm visualized in an unexpected gallery piece. How DSA preparation and contemporary art intersect."
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 🇸🇪


When preparing for tech interviews meets Copenhagen Contemporary art: discovering the Breadth First Search algorithm visualized in an unexpected gallery piece. How DSA preparation and contemporary art intersect.

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: "Learning notes and discoveries while diving into C++: from constructor gotchas and naming conventions to string streams and the standard library. A developer's journey into systems programming."
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. 

Learning notes and discoveries while diving into C++: from constructor gotchas and naming conventions to string streams and the standard library. A developer's journey into systems programming.

2022-11-14-learning-cplusplus.mdx

Learning C++

---
title:	"Creating Executable Jupyter Notebooks"
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[^conda], 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 title="strip.py" caption="stripping the unwanted dependencies"
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.

 [^conda]: [The great package manager](https://docs.conda.io/en/latest/)

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

---
title: B-Movie Text Generator
head_title: ""
description: "From Video Ezy nostalgia to data science: creating a B-movie text generator using 200+ terrible films. Inspired by the 'How Did This Get Made?' podcast and a love for hilariously bad cinema."
subtitle: What if a robot could write b-movies?
bullets:
  [
    {
      item_colour: "#0039a6",
      value: "P", 
      tag: "Python",
      font_colour: "white"
    },
    {
      item_colour: "#996633",
      value: "D", 
      tag: "data",
      font_colour: "white"
    },
  ]
date: "2021-01-29"
slug: 'bad-movies'
skip: false
---

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

## Motivation

One of my fond memories of a bygone era was visiting the local video store, the now ancient ***Video Ezy***, to pick up a movie with my friends. We would go
to each others houses and have a movie marathon and watch all types of films. Some good, some bad.

<Figure caption="video ezy logo">
  <img className="rounded-xl" src="../images/projects/bad-movies/video-ezy.jpg" />
</Figure>

Over the years we all naturally became avid *cinephiles*. Analysing films while watching them became a favourite pastime and
surprisingly, the bad films had plenty of (hilarious) things to analyse. What followed was uncovering a giant underground cult following of all things
bad.

One particularly brilliant medium that explored this sub-genre of movie, was the podcast *How Did This Get Made*.

> How Did This Get Made? is a podcast on the Earwolf network. It is hosted by Paul Scheer, June Diane Raphael and Jason Mantzoukas. Each episode, which typically has a different guest, features the deconstruction and mockery of outlandish and bad films.

After listening to this podcast religiously, me and my friends decided, why not create our own corpus of bad movies. So the bad
movie club is born, and 200+ movies later a rather interesting (to me at least) dataset is produced.

I've always had the idea to create a data science project from our long and silly list, so here it is.

source: [https://github.com/kostyafarber/b-movie-text-generator](https://github.com/kostyafarber/b-movie-text-generator)


From Video Ezy nostalgia to data science: creating a B-movie text generator using 200+ terrible films. Inspired by the 'How Did This Get Made?' podcast and a love for hilariously bad cinema.

2021-01-29-bad-movies.mdx

What if a robot could write b-movies?

B-Movie Text Generator

---
title: Sydney Property Prices Dashboard
head_title: ""
description: "Building an interactive Sydney property dashboard from scratch with Dash Plotly and Python. Analyzing 100,000+ real estate entries to create a data-driven solution deployed on Heroku."
subtitle: "Sydney property market dashboard across different suburbs using a dataset from Kaggle."
bullets: 
  [
    {
      item_colour: "#b933ad",
      value: "F", 
      tag: "frontend",
      font_colour: "white"
    },
    {
      item_colour: "#0039a6",
      value: "P", 
      tag: "python",
      font_colour: "white"
    },
    {
      item_colour: "#996633",
      value: "D",
      tag: "data",
      font_colour: "white"
    },
  ]
date: "2021-01-28"
slug: 'sydney-house-prices'
skip: false
---

## The Motivation

As the old adage goes, for pragmatists anyway, you learn by doing. This especially applies to learning programming. 
So I set off into the virtual world to find real world data that wasn't curated to make the coders life easier. 

I first scoured [Kaggle](https://www.kaggle.com/) for data I could use to build an interesting project. My first instinct
was to find data that was close to me in terms of proximity.  

>Kaggle allows users to find and publish data sets, explore and build models in a web-based data-science environment, work with other data scientists and machine learning engineers, and enter competitions to solve data science challenges.

A simple search of *'Sydney'* into the search bar yielded 
a few results, but being the typical Sydney resident, data of property prices seemed like an obvious option.

## The Result
- A fully custom built interactive dashboard programmed from scratch using **Dash Plotly**, a Python framework for building web analytic applications. 
- The front end application is deployed on **Heroku**, a cloud platform that makes it easy to deploy and manage Flask applications. 
- The data was obtained from Kaggle, a dataset with over 100,000 entries scraped from realestate.com.
- Data wrangling, Exploratory Data Analysis and Data Visualisations were performed using Python and documented in both static and executable (using Binder) Jupyter Notebook for reproducibility.
- All code and project details are open-source and shared on GitHub. 

source: [https://github.com/kostyafarber/sydneyhouseprices-dashboard](https://github.com/kostyafarber/sydneyhouseprices-dashboard)

Building an interactive Sydney property dashboard from scratch with Dash Plotly and Python. Analyzing 100,000+ real estate entries to create a data-driven solution deployed on Heroku.

2021-01-28-sydney-house-prices.mdx

Sydney property market dashboard across different suburbs using a dataset from Kaggle.

Sydney Property Prices Dashboard

---
title: Using Regular Expressions to Preprocess a Text File
date: "2021-01-28"
description: "Transforming a chaotic iPhone Notes list of 200+ terrible movies into clean data using Python and regex. Data wrangling meets pattern matching in this preprocessing adventure for the B-movie text generator project."
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.

<Figure caption="trash list" className="p-0">
  <img src="/images/posts/text-processing/trashlist.png" />
</Figure>

## 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).


Transforming a chaotic iPhone Notes list of 200+ terrible movies into clean data using Python and regex. Data wrangling meets pattern matching in this preprocessing adventure for the B-movie text generator project.

2021-02-01-textprocessing.mdx

Using Regular Expressions to Preprocess a Text File

---
title: Why Should I Start a Blog?
date: "2021-01-27"
description: "From contemplative pedagogy to storytelling: why writing about programming discoveries leads to deeper learning. The philosophy behind starting this blog and the art that inspired it."
author: Kostya Farber
slug: why-to-blog
head_title: Why Should I Start a Blog?
---

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_.[^1]

> 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.

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!

[^1]: If you want to read more about it, I liked [this](https://ctl.columbia.edu/resources-and-technology/resources/contemplative-pedagogy/) excerpt from Columbia University


From contemplative pedagogy to storytelling: why writing about programming discoveries leads to deeper learning. The philosophy behind starting this blog and the art that inspired it.