# Sorting algorithm: Partitioning

Before:

After:

## The algorithm

1. Select a random pivot (ours is the number `3`)

2. Pick the left pointer and the right pointers

• Left pointer must be the first element of the array.
• Right pointer must be the last element of the array (exclude the pivot element)

If true (that the element value is less or equal to the pivot’s value), move the pointer to the right:

If false, the left pointer stops (loses its turn).

4. Right pointer’s turn

True. If element value is greater than the pivot’s value, move right pointer to the left:

Else false:

Switch the values between the two pointers. This moves the lesser number to the left and the greater number to the right:

Right pointer stops (loses its turn).

5. Left pointer’s turn

Move left pointer to the right:

If true, move pointer to the right and make the comparison again:

6. If left pointer’s value is not lesser than pivot’s value

Switch the values between the left pointer’s value with the pivot’s value :

7. This first pass is done. Notice that the values to the left of the pivot are sorted but the right side are not.

As long as this is the case, you have to do steps 1 to 6 again and again until both sides are properly sorted.

# Algorithm: First index of ‘x’

Here, the index of `x` given the string `abcxcxyz` is `2`.

## Python

#recursion

``````def index_of(str, idx=0) -> int:
is_current_element = (len(str) == 1)
current_element = str[-1]
char = str[0]
remaining_chars = str[1:]

if is_current_element:
return current_element

if char == 'x':
return idx

return index_of(remaining_chars, idx+1)

assert index_of('abxcxyz') == 2
``````

# Algorithm: Triangular Numbers

## Python

#recursion

``````def triangular_number(n):
if n == 1:
return 1
return n + triangular_number(n-1)

assert triangular_number(9) == 45
``````

# Algorithm: Return even numbers from array of numbers

## Python

#recursion

``````def even_num(n: list) -> list:
curr = [n[0]]
succ = n[1:]
is_even = (curr[0] % 2 == 0)
is_current_element = (len(n) == 1)

if is_current_element:
if is_even:
return curr
else:
return []

return even_num(curr) + even_num(succ)

assert even_num([3,2,4,5,8,6,12,11]) == [2, 4, 8, 6, 12]
``````

# Algorithm: Count number of characters in array of string

## Python

#recursion

``````def num_of_strs(arr) -> int:
"""Accepts an array of strings and returns the total number of characters in the array."""
if len(arr) == 1:
return len(arr[0])
return num_of_strs(arr[1:]) + len(arr[0])

assert num_of_strs(['x']) == 1
assert num_of_strs(['xy']) == 2
assert num_of_strs(['xy','z']) == 3
assert num_of_strs(['xy','z', 'abc', 'xyz']) == 9
assert num_of_strs(['ab','cx','yz']) == 6, num_of_strs(['ab','cx','yz'])
``````

# Algorithm: Count how many ‘z’ is in a string

## Python

#recursion

``````def count_z(txt):
if len(txt) == 0:
return 0

remaining_chars = count_z(txt[1:])
if txt[0] == 'z':
return 1 + remaining_chars

return remaining_chars

txt = 'xyzabzbzzbzzzt'
assert count_z(txt) == 7
``````

# Algorithm: Reverse a string

## Python

#recursive

``````def reverse_str(txt):
if len(txt) == 1:
return txt[0]

return reverse_str(txt[1:]) + txt[0]

assert reverse_str('abcxyz') == 'zyxcba'
``````

## Javascript

#recursive

``````const assert = require('assert');

function reverseStr(txt) {
if (txt.length == 1) {
return txt[0];
}

return reverseStr(txt.substr(1)) + txt[0];
}

assert.equal(reverseStr('abcxyz'), 'zyxcba');
``````

# Algorithm: Sum all the elements of an array

## Python

#recursion

``````def total_sum(arr: list) -> int:
if len(arr) == 1:
return arr[0]
return arr[0] + total_sum(arr[1:])

assert total_sum([1,2,3,4,5]) == 15
``````

# Algorithm: Flatten a multidimensional array

## Python

Using recursion:

``````def flatten(nested_array):
for e in nested_array:
if type(e) == list:
flatten(e)
else:
print(e, end=" ")

flatten([
1,2,3,[4, 5, 6],7,[8,[9, 10, 11,[12, 13, 14]]],
[15, 16, 17, 18, 19,[20, 21, 22,[23, 24, 25,[26, 27, 29]], 30, 31], 32],
33
])

#-> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30 31 32 33
``````

# Data Structure: Queue

## Python

``````class Queue:

def __init__(self):
self.data = []

def enqueue(self, element):
self.data.append(element)

def dequeue(self):
return self.data.pop(0)

return self.data[0]

queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

assert queue.dequeue() == 1
assert len(queue.data) == 2
assert queue.dequeue() == 2
assert len(queue.data) == 1
assert queue.dequeue() == 3
assert len(queue.data) == 0
``````

# Data Structure: Stack

## Python

``````class Stack:

def __init__(self):
self.data = []

def push(self, element):
self.data.append(element)

def peek(self):
return self.data[-1]

def pop(self):
return self.data.pop()

stack = Stack()
stack.push(1)
assert stack.peek() == 1

stack.push(5)
assert stack.peek() == 5
assert len(stack.data) == 2

assert stack.pop() == 5
assert len(stack.data) == 1
``````

# Algorithm: Find the first non-duplicate character in a string

## Python

`O(n)`:

``````def non_dupe_char(some_word):
table = dict()
for c in some_word:
table[c] = table.get(c, 0) + 1

for (k,v) in table.items():
if v == 1:
return k

return None

assert non_dupe_char('minime') == 'n'
assert not non_dupe_char('minime') == 'm'
``````

# Algorithm: Find the missing alphabet from a string

## Python

Solution 1 (`O(n)`):

``````def missing_alphabet(line):
alphabet = 'abcdefghijklmnopqrstuvwxyz'

for c in line:
alphabet = alphabet.replace(c, '')

return alphabet

assert missing_alphabet("the quick brown frog jumps over the lazy dog") == 'x'
``````

Variation (`O(26)` / `O(1)`):

``````def missing_alphabet(line):
alphabet = 'abcdefghijklmnopqrstuvwxyz'

for c in alphabet:
if c in line:
continue
else:
return c

assert missing_alphabet("the quick brown frog jumps over the lazy dog") == 'x'
``````

# Algorithm: Return the first duplicate value in an array

## Python

`O(n)`:

``````def duplicate_value(str_arr):
"""A duplicate must appear in str_arr"""
tally = dict()
for c in str_arr:
tally[c] = tally.get(c, 0) + 1
if tally[c] == 2:
return c

assert duplicate_value(['a','b','z','x','y','z']) == 'z'
assert duplicate_value(['z','b','c','x','y','z']) == 'z'
assert duplicate_value(['a','z','z','x','y','z']) == 'z'
``````

# Algorithm: Is array1 a subset of array2

## Python

`O(n)`:

``````def is_subset(arr1, arr2) -> bool:
"""Where arr1 <= arr2"""

if len(arr1) > len(arr2):
return False

for i in arr1:
if i in arr2:
continue
else:
return False

return True

arr1, arr2 = [1, 3, 2, 7, 4], [5, 1, 3, 6, 8, 7, 4, 2]

assert is_subset(arr1, arr2) == True, "arr1 is a subset of arr2"
assert is_subset([11] + arr1, arr2) == False, "arr1 is not a subset of arr2"
assert is_subset(arr1 + [66], arr2) == False, "arr1 is not a subset of arr2"
assert is_subset(arr2, arr1) == False, "First array is > second array"
``````

# Algorithm: Finding the intersection between two arrays

## Python

``````arr1, arr2 = [1, 3, 2, 7, 4], [12, 1, 3, 6, 8, 7, 4]
``````

Solution 1 (`O(n*m)`):

``````inxsn = []
for i in arr1:
for j in arr2:
if i == j:
inxsn.append(i)
break

print(inxsn)
#→ [1, 3, 7, 4]
``````

Solution 2 (`O(n)`):

``````inxsn = []
for i in arr1:
if i in arr2:
inxsn.append(i)

print(inxsn)
#→ [1, 3, 7, 4]
``````

Solution 3: List comprehension

``````print(
[i for i in arr1 if i in arr2]
)
#→ [1, 3, 7, 4]
``````

# Algorithm: Bubble Sort

## Python

`O(n²)`:

``````def bubble_sort(array):
length = len(array) - 1
for _ in range(0, length):
for i in range(0, length):
j = i + 1
bigger, smaller = array[i : j + 1]

if bigger > smaller:
array[i], array[j] = smaller, bigger

return array

assert bubble_sort([1, 2, 3]) == [1, 2, 3], True
assert bubble_sort([3, 2, 1]) == [1, 2, 3], True
assert bubble_sort([2, 3, 1]) == [1, 2, 3], True
assert bubble_sort([1, 2, 3, 4]) == [1, 2, 3, 4], True
assert bubble_sort([4, 3, 2, 1]) == [1, 2, 3, 4], True
assert bubble_sort([1, 3, 2, 4]) == [1, 2, 3, 4], True
assert bubble_sort([4, 2, 7, 1, 3]) == [1, 2, 3, 4, 7], True
assert bubble_sort([1, 2, 3, 4, 7]) == [1, 2, 3, 4, 7], True
assert bubble_sort([4, 2, 7, 1, 3]) == [1, 2, 3, 4, 7], True
assert bubble_sort([1, 2, 3, 4, 7]) == [1, 2, 3, 4, 7], True

``````

# Algorithm: Insertion Sort

## Python

`O(n²)`:

``````def insertion_sort(array):
for rightside in range(len(array) - 1):
rightside += 1

while rightside > 0:
leftside = rightside - 1
if array[leftside] > array[rightside]:
# Switch sides
array[rightside], array[leftside] = (
array[leftside],
array[rightside],
)
rightside -= 1
else:
# Both sides stay as-is
break

return array

assert insertion_sort([1, 2, 3]) == [1, 2, 3], True
assert insertion_sort([3, 2, 1]) == [1, 2, 3], True
assert insertion_sort([2, 3, 1]) == [1, 2, 3], True
assert insertion_sort([1, 2, 3, 4]) == [1, 2, 3, 4], True
assert insertion_sort([4, 3, 2, 1]) == [1, 2, 3, 4], True
assert insertion_sort([1, 3, 2, 4]) == [1, 2, 3, 4], True
``````

# Algorithm: Even numbers from 1 to m

## Javascript

``````function even_nums_to(n) {
let ctr = 0;

while (ctr < n) {
ctr += 2;
console.log(ctr);
}
}

even_nums_to(20)
#-> 2 4 6 8 10 12 14 16 18 20
``````

Variation: Recursion

``````function even_nums_to(n, ctr=2) {
console.log(ctr);

return ctr === n ? n : even_nums_to(n, ctr + 2);
}

even_nums_to(20);
#-> 2 4 6 8 10 12 14 16 18 20
``````

## Python

``````def even_nums_to(n):
ctr = 0

while ctr < n:
ctr += 2
print(ctr, end=" ")

even_nums_to(20)
#-> 2 4 6 8 10 12 14 16 18 20
``````

Variation: Using recursion

``````def even_nums_to(n, ctr=2):
print(ctr, end=" ")

if ctr == n:
return n

return even_nums_to(n, ctr + 2)

assert even_nums_to(20) == 20
#-> 2 4 6 8 10 12 14 16 18 20
``````

Pythonic variation: Using recursion

``````# 2021-07-20

def even_nums_to(n, ctr=2):
print(ctr, end=" ")
return n if ctr == n else even_nums_to(n, ctr + 2)

assert even_nums_to(20) == 20
#-> 2 4 6 8 10 12 14 16 18 20
``````

# Algorithm: Fibonacci Series

## Python

`O(2^n)`

``````def fibb(n):
if n == 1 or n == 0:
return n
else:

assert fibb(0) == 0; assert fibb(1) == 1, fibb(1); assert fibb(2) == 1, fibb(2);
assert fibb(3) == 2, fibb(3); assert fibb(4) == 3, fibb(4); assert fibb(5) == 5, fibb(5);
assert fibb(6) == 8, fibb(6); assert fibb(7) == 13, fibb(7); assert fibb(8) == 21, fibb(8);
assert fibb(9) == 34, fibb(9); assert fibb(10) == 55, fibb(10)
``````

Variation:

``````def fibb(n):
return n if (n <= 1) else fibb(n - 2) + fibb(n - 1)

``````

Memoized version `O(n)`:

``````def fibb(n, mem={}):
if n == 1 or n == 0:
return n

if not mem.get(n):
mem[n] = fibb(n - 2) + fibb(n - 1)

return mem[n]

``````

## Javascript

#2021.07.22

``````function fibb(n) {
if (n <= 1) {
return n;
}

const addend1 = n - 1;
const addend2 = n - 2;

}

assert.equal(fibb(0), 0); assert.equal(fibb(1), 1); assert.equal(fibb(2), 1); assert.equal(fibb(3), 2);
assert.equal(fibb(4), 3); assert.equal(fibb(5), 5); assert.equal(fibb(10), 55);
``````

Variation:

``````function fibb(n) {
return (n <= 1) ? n : fibb(n - 1) + fibb(n - 2);
}

assert.equal(fibb(0), 0); assert.equal(fibb(1), 1); assert.equal(fibb(2), 1); assert.equal(fibb(3), 2);
assert.equal(fibb(4), 3); assert.equal(fibb(5), 5); assert.equal(fibb(10), 55);
``````

# Creating a web app in Rust

1. Create the project using `cargo`
2. List all the dependencies in `Cargo.toml`
3. Set up the web app in `src/main.rs`:
``````use messages::MessageApp;

fn main() -> std::io::Result<()> {
std::env::set_var("RUST_LOG", "actix_web=info");
env_logger::init();
let app = MessageApp::new(8080);

app.run()
}
``````

In a new file `src/lib.rs`, create the `MessageApp` class:

``````#[macro_use]
extern crate actix_web;

use actix_web::{middleware, web, App, HttpRequest, HttpServer, Result};
use serde::Serialize;

#[derive(Serialize)]
struct IndexResponse {
message: String,
}

pub struct MessageApp {
port: u16,
}

impl MessageApp {
pub fn new(port: u16) -> Self {
MessageApp { port }
}

pub fn run(&self) -> std::io::Result<()> {
println!("Starting http server: 127.0.0.1:{}", self.port);
HttpServer::new(move || {
App::new()
.wrap(middleware::Logger::default())
.service(index)
})
.bind(("127.0.0.1", self.port))?
.workers(8)
.run()
}
}

#[get("/")]
fn index(req: HttpRequest) -> Result<web::Json<IndexResponse>> {
let hello = req
.get("hello")
.and_then(|v| v.to_str().ok())
.unwrap_or_else(|| "world");

Ok(web::Json(IndexResponse {
message: hello.to_owned(),
}))
}
``````

### Rust closure

``````HttpServer::new(
move || {
App::new()
.wrap(middleware::Logger::default())
.service(index)
}
)
``````

### The `move` keyword in a closure

The move keyword is … used to allow the closure to outlive the captured values, such as if the closure is being returned or used to spawn a new thread.
The Rust Reference

### The `?` operator

Makes error handling more pleasant by reducing the visual noise involved. Instead of an entire match statement, now we are just using the single `?` character to indicate that here we are handling errors in the standard way, by passing them up the call stack.

The Edition Guide

``````    pub fn run(&self) -> Result {
println!();
HttpServer::new(move || {
})

.bind(("127.0.0.1", self.port))?  👈🏻👀

.workers(8)
.run()
}
``````

## Summary

The web app has one simple functionality so far. It listens for a `GET` request with a `hello` header. If it receives such request, it sends back a response consisting of the value of the `hello` header. However, if it receives non-hello header, the value of the response will be `world`.

Source code on GitHub: github.com/islandjoe/messages

# Use “flake8” line length on “black”

Context

Developing in Python with VS Code using flake8 for linting and black for auto-formatting.

Problem

Solution

# Autoselect the first item from the drop down menu

Context

Vim autocomplete using coc.nvim plugin.

Get a behavior similar to VS Code where the first item in the suggestion drop down menu is auto-selected:

#### Before

Pressing the `Enter` key results in a new line:

#### After

Pressing the `Enter` key results in the selection of the item:

## The solution

1. Open vim and type: `:CocConfig`, this will open `coc-settings.json`
2. Enter this line:

``````{
"suggest.noselect": false
}
``````

Enjoy!

#vim #coc.nvim #autocomplete

# Creating a web app in Django

Prerequisites:

• You’ve installed Django. If not, `\$ pip install django`.
• You’ve created the project directory, like so:
• `\$ mkdir webapp`
• `\$ cd webapp`
• You’ve created the Django project directory structure.
• `\$ django-admin startproject webapp .`

## 1 Creating the `blog` app

We name our app within the `webapp` project as `blog`.

1. Add the blog app to the
2. Configure the home URL in
3. To create the home view, add the `home` view function in
4. That function must refer to the home template (`home.html`) in `templates` directory
5. Because the `templates` directory was newly created, Django doesn’t know anything about it, so let’s register it at

Our `blog` folder should contain the following:

• `admin.py`: Gives access to the admin dashboard for configuring our models
• `models.py`: Create and configure our models (a.k.a. database entities)
• `views.py`: Create the views as functions that renders the template file

## 3 Creating the View

We first create the base template so that the succeeding templates can use it as their base page template (this is known as template inheritance)

A view function takes a request and returns a response. 1

Static files such as images, assets, CSS, scripts, etc. are placed in their own folder inside a folder named `static`. This folder doesn’t exist so let’s create it. Then we let Django know about it through an environment variable in `settings.py`.

## 5 Creating the Model

Models define the structure and the behavior of our data2. In order for it to be shown in the admin dashboard, we must register it first in

The `__str__()` method returns a human-readable representation of our model (usually text).

## 7 Creating a slug

To generate our slug automatically, we override the `save()` method and place our slug generator code in it.

## 8 Setting the URL to use the newly generated slug

• `app_name` is the namespace for our URLs here. For example, to reference a detail page we can use `blog:detail`3
• To capture our URL values (i.e. the slug), we surround the ‘slug’ keyword with angle brackets (`<slug>`)4

## 9 Set the blog app URL

We want to view the blog detail page using this pattern: `/blog/the-interesting-post.html`.

## 10 Continuing with the details view

Now that we’ve set the URL to the pattern that we like, let’s create the `details` handler to take care of the logic such that if the page can not be found, we display a corresponding page (i.e. 404 page).

## 11 Creating the template

Best case scenario, the page should exist. We create the actual page that the users will see.

And finally, we list all our blog posts in the home page.

## Part 2 coming soon

1. We return HTML contents coming from the `home.html` template. [return]
2. Defined as objects and in the database [return]
3. `blog:detail` where `blog` is the namespace and `detail` is the name of the path. [return]
4. In `<slug:slug>` the second `slug` specifies a type to match. [return]

# List element comparison exercises

Given an instance of a class and an instance of an object, how do they differ from each other.

So the class instance and the object instance has 23 properties and/or methods in common. Which three extra properties does the class instance have over the object instance?

First attempt

Solution