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)
  3. Start with the left pointer

    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)

    def read(self):
        return self.data[0]


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

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

Abstract Data Type: 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:
        addend1 = n - 1
        addend2 = n - 2

    return fibb(addend1) + fibb(addend2)

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;
    
    return fibb(addend1) + fibb(addend2);
}

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
        .headers()
        .get("hello")
        .and_then(|v| v.to_str().ok())
        .unwrap_or_else(|| "world");

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

The MessageApp class

Associated function and instance method

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()
    }

The handler index

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.











2 Configuring the home page

  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











4 Adding CSS file

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











6 Admin dashboard

We don’t have access to the admin dashboard (Django doesn’t allow anonymous logins to the admin page) so we create a user with all permissions enabled.











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:detail3
  • 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.











12 Displaying all posts in the home page

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

Refactoring exercises

Using list comprehension