c++misc
bubble-sort.cppmath.cppmultithreading.cppnamespace.cppsignals.cppsmart-pointers.cppvectors.cpp

c++algos
binary-search.cppfind-adjacent.cppfor-each.cpp

pythonmisc
alu-in-python.pybubble-sort.pycombinations-with-replacement.pycomposing-functions.pyenumerate.pyerlang-b-formula.pyforeign-function-library.pyfunction-wrappers.pyfunctools-cache.pyglide-typing-problem.pylinked-list-using-recordclass.pynumpy-operators.pypandas-operators.pypartial-functions.pyregular-expression.pysobel-filter-using-opencl.py

pythonci
genetic-algorithm-optimization.pyparticle-swarm-optimisation.py

pythonml
backpropagation.pyconvolutional-neural-network.pydelta-learning-algorithm.pygradient-descent-algorithm.pyk-nearest-neighbors-classifier.pylinear-threshold-unit.pynumpy-linear-relu.pywidrow-hoff-learning-algorithm.py

pythoneuler
#1-multiples-of-3-and-5.py#2-even-fibonacci-numbers.py#3-largest-prime-factor.py#4-largest-palindrome-product.py#5-smallest-multiple.py#6-sum-square-difference.py#7-10001st-prime.py#8-largest-product-in-a-series.py#9-special-pythagorean-triplet.py#10-summation-of-primes.py#11-largest-product-in-grid.py#12-highly-divisible-triangular-number.py#13-large-sum.py#14-longest-collatz-sequence.py#15-lattice-paths.py#16-power-digit-sum.py#17-number-letter-counts.py

pythoncompilers
ast-constant-folding.pyast-to-tac-to-llvm.pydsl-in-python.pyfor-loop-implementation.pyloop-tiling-optimization.pyopencl-in-python.pyoperator-fusion-on-parse-tree.pyparallelization-optimization.pyshunting-yard-algorithm.pytokenizer-using-generator-in-python.pyvectorization-optimization.py

assemblyx86
hello-x86.asm

verilogmisc
intro.v

veriloggates
and16.vand.vdmux4way.vdmux8way.vdmux.vmux4way16.vmux8way16.vmux16.vmux.vnand.vnot16.vnot.vor8way.vor16.vor.vxor.v

cmisc
header-files.clinked-list.cmacros.cmemory.cpointers.cvalist.c

c++miscalgos^

misc^

bubble-sort.cppmath.cppmultithreading.cppnamespace.cppsignals.cppsmart-pointers.cppvectors.cpp

[bubble-sort.cpp]

#include <iostream>
#include <vector>

constexpr void print_elements_in_vector(std::vector<int> numbers) {
    for (int number : numbers) {
        std::cout << number << std::endl;
    }
}

int main() {
    std::vector<int> numbers = { 14, 33, 27, 35, 10 };
    // print unsorted
    print_elements_in_vector(numbers); // 14 33 27 35 10

    // bubble sort
    for (int i = 0; i < numbers.size(); i++) {
        for (int j = 0; j < numbers.size() - 1; j++) {
            if (numbers[j] > numbers[j + 1]) {
                int temp = numbers[j];
                // swap positions
                numbers[j] = numbers[j + 1];
                numbers[j + 1] = temp;
            }
        }
    }
    // print sorted
    print_elements_in_vector(numbers); // 10 14 27 33 35
}

[math.cpp]

#include <iostream>
#include <cmath>

int main() {
    std::cout << INFINITY << std::endl; // inf
    std::cout << NAN << std::endl; // nan
    std::cout << isgreater(42, 10) << std::endl; // 1
    std::cout << isless(42, 10) << std::endl; // 0
    std::cout << isnan(NAN) << std::endl; // 1
    std::cout << isinf(INFINITY) << std::endl; // 1
    std::cout << isfinite(42) << std::endl; // 1

    // trigonometric
    std::cout << cos(42) << std::endl; // -0.399985
    std::cout << sin(42) << std::endl; // -0.916522
    std::cout << tan(42) << std::endl; // 2.29139

    // exponential and logarithmic
    std::cout << log10(10) << std::endl; // 1
    std::cout << log2(8) << std::endl; // 3
    std::cout << exp(2) << std::endl; // 7.38906

    // binary exponential function
    std::cout << exp2(2) << std::endl; // 4

    // natural logarithm
    std::cout << log(10) << std::endl; // 2.30259

    // power and root
    std::cout << pow(2, 3) << std::endl; // 8
    std::cout << sqrt(16) << std::endl; // 4
    std::cout << cbrt(27) << std::endl; // 3

    // rounding and remainder
    std::cout << ceil(41.5) << std::endl; // 42
    std::cout << floor(42.5) << std::endl; // 42
    std::cout << trunc(42.5) << std::endl; // 42
    std::cout << round(41.5) << std::endl; // 42
    std::cout << remainder(142, 100) << std::endl; // 42

    // round to nearest integer
    std::cout << rint(42.5) << std::endl; // 42

    // round to nearby integer
    std::cout << nearbyint(42.5) << std::endl; // 42

    // manipulation
    std::cout << copysign(42, -1) << std::endl; // -42
    std::cout << nan("42") << std::endl; // nan

    // minimum, maximum, difference
    std::cout << fdim(52, 10) << std::endl; // 42
    std::cout << fmax(42, 10) << std::endl; // 42
    std::cout << fmin(42, 10) << std::endl; // 10

    // absolute value (can handle floating-point)
    std::cout << fabs(-12.5) << std::endl; // 12.5

    // absolute value (only for integers)
    std::cout << abs(-42) << std::endl; // 42

    // fused multiply-add
    std::cout << fma(42.5, 10, 200) << std::endl; // 625
}

[multithreading.cpp]

#include <iostream>
#include <pthread.h>

constexpr int max_threads = 5;

void *print(void *thread_id) {
    long tid = (long) thread_id;
    std::cout << "thread_id: " << tid << std::endl;
    // terminate
    pthread_exit(NULL);
};

int main() {
    pthread_t threads[max_threads];
    int thread[max_threads];

    for (int i = 0; i < max_threads; i++) {
        thread[i] = i;
        std::cout << "creating thread:" << thread[i] << std::endl;
        // create thread using pthread_create(thread, attr, start_routine, arg)
        if (pthread_create(&threads[i], NULL, print, (void*) &thread[i]) != 0) {
            std::cout << "unable to create thread: " << thread << std::endl;
            // fail
            exit(-1);
        }
    }
    // terminate
    pthread_exit(NULL);
    // creating thread:0
    // creating thread:1
    // thread_id: 140701949382784
    // thread_id: 140701949382788
    // creating thread:2
    // creating thread:3
    // thread_id: 140701949382792
    // creating thread:4
    // thread_id: 140701949382796
    // thread_id: 140701949382800
}

[namespace.cpp]

#include <iostream>

// define namespace
namespace my_functions {
    void function() {
        std::cout << "called: my_functions::function" << std::endl;
    }
}

int main() {
    my_functions::function(); // called: my_functions::function
}

[signals.cpp]

#include <iostream>
#include <csignal>
#include <unistd.h>

// signal handler
void terminate(int sig) {
   std::cout << "\nsignal: " << sig << std::endl;
   exit(sig);
}

int main() {
   // register signal
   signal(SIGINT, terminate);  

   // keyboard interrupt
   while(1) {
       std::cout << "stuck doing something really hard... (press ^C to exit)" << std::endl;
       sleep(5);
   }
   // stuck doing something really hard... (press ^C to exit)
   // ^C
   // signal: 2
}

[smart-pointers.cpp]

// smart pointers handle allocation and deletion of memory

#include <memory>
#include <iostream>
#include <vector>

class MyClass {
    std::unique_ptr<std::vector<int>> data; // unique_ptr is a smart pointer
public:
    MyClass(const int size) { data = std::make_unique<std::vector<int>>(size); } // allocate memory with make_unique
    void print_data() {
        for (auto i : *data) { std::cout << i << std::endl; }
    }
};

void function_using_data() {
    MyClass my_class(5); // lifetime tied to scope
    my_class.print_data();
} // my_class is destroyed here

int main() {
    function_using_data(); // 0 0 0 0 0
}

[vectors.cpp]

#include <iostream>
#include <vector>
#include <string>
#include <format>

int main() {
    // vector of ints
    std::vector<int> numbers;
    // size
    std::cout << numbers.size() << std::endl; // 0
    // push values
    for (int i = 1; i <= 5; i++) {
        numbers.push_back(i);
    }
    std::cout << numbers.size() << std::endl; // 5
    std::cout << numbers[3] << std::endl; // 4

    // vector of strings
    std::vector<std::string> strings = { "hello", "c++" };
    std::cout << strings[0] << " " << strings[1] << std::endl; // hello c++
}

algos^

binary-search.cppfind-adjacent.cppfor-each.cpp

[binary-search.cpp]

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = { 1, 2, 3, 4, 5 };
    // binary_search
    bool found = std::binary_search(numbers.begin(), numbers.end(), 4);
    if (found) {
        std::cout << "found value" << std::endl;
    } else {
        std::cout << "not found" << std::endl;
    }
    // found value
}

[find-adjacent.cpp]

#include <algorithm>
#include <vector>
#include <iostream>

bool twice (int a, int b) { return a * 2 == b; }

int main() {
    std::vector<int> numbers = { 50, 40, 10, 20, 20 };
    // adjacent_find
    auto iter = std::adjacent_find(numbers.begin(), numbers.end(), twice);
    if (iter != numbers.end()) {
        std::cout << *iter << ", " << *(iter + 1) << std::endl;
    } else {
        std::cout << "no adjacent pairs" << std::endl;
    }
    // 10, 20
}

[for-each.cpp]

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = { 1, 2, 3, 4, 5 };
    // multiply each element in numbers using for_each
    std::for_each(numbers.begin(), numbers.end(), [](int &number) {
        number *= 2;
    });
    // for_each
    std::for_each(numbers.begin(), numbers.end(), [](int number) {
        std::cout << number << std::endl;
    });
    // 2 4 6 8 10
}

pythonmisccimleulercompilers^

misc^

alu-in-python.pybubble-sort.pycombinations-with-replacement.pycomposing-functions.pyenumerate.pyerlang-b-formula.pyforeign-function-library.pyfunction-wrappers.pyfunctools-cache.pyglide-typing-problem.pylinked-list-using-recordclass.pynumpy-operators.pypandas-operators.pypartial-functions.pyregular-expression.pysobel-filter-using-opencl.py

[alu-in-python.py]

"""
An ALU is a combinational logic circuit that performs
arithmetic and bitwise operations on input bits. This
is a 16-bit implementation.
"""

# binary to signed decimal
def binary_to_signed(lst):
    binary_str = ''.join(map(str, lst))
    if (binary_str[0] == '1'):
        # invert bits
        inverted_str = ''.join(['1' if c == '0' else '0' for c in binary_str[1:]])
        decimal = -int(inverted_str, 2) - 1
    else:
        decimal = int(binary_str, 2)
    return decimal

assert binary_to_signed([1,1,1,1,1,1,1,1]) == -1

# https://en.wikipedia.org/wiki/Two%27s_complement
def twos_complement_addition(a, b):
    # convert to binary strings
    a_bin = ''.join(map(str, a))
    b_bin = ''.join(map(str, b))
    # number of bits
    bits = max(len(a_bin), len(b_bin))
    # convert to twos complement
    a_twos = int(a_bin, 2)
    b_twos = int(b_bin, 2)
    # addition
    result_twos = a_twos + b_twos
    # convert result to binary string
    result = bin(result_twos & (2 ** bits - 1))[2:]
    # convert result to list of ints
    result = list(map(int, result))
    # padding (if needed)
    if (len(result) < bits):
        # insert 0s to front
        for bit in range(bits - len(result)): result.insert(0, 0)
    return list(map(int, result))

assert twos_complement_addition([0,1,0,1], [0,1,0,1]) == [1,0,1,0]

"""
if (zx == 1)  set x = 0           : 16-bit
if (nx == 1)  set x = ~x          : 16-bit bitwise not
if (zy == 1)  set y = 0           : 16-bit constant
if (ny == 1)  set y = ~y          : 16-bit bitwise not
if (f == 1)   set out = x + y     : 16-bit twos complement addition
if (f == 0)   set out = x & y     : 16-bit bitwise and
if (no == 1)  set out = ~out      : 16-bit bitwise not
if (out == 0) set zr = 1          : 1-bit
if (out < 0)  set ng = 1          : 1-bit
"""
def ALU(x, y, zx=0, nx=0, zy=0, ny=0, f=0, no=0):
    """
        x   : input x       : 16-bit
        y   : input y       : 16-bit
        zx  : zero x        : 1-bit
        nx  : negate x      : 1-bit
        zy  : zero y        : 1-bit
        ny  : negate y      : 1-bit
        f   : function      : 1-bit
        no  : negate out    : 1-bit
    """
    # init output
    out = [0] * len(x)
    zr=0
    ng=0
    # if (zx == 1)  set x = 0
    if zx == 1:
        for i in range(len(x)):
            x[i] = 0
    # if (nx == 1)  set x = ~x
    if nx == 1:
        for i in range(len(x)):
            if x[i] == 1: x[i] = 0
            else: x[i] = 1
    # if (zy == 1)  set y = 0
    if zy == 1:
        for i in range(len(y)):
            y[i] = 0
    # if (ny == 1)  set y = ~y
    if ny == 1:
        for i in range(len(y)):
            if y[i] == 1: y[i] = 0
            else: y[i] = 1
    # if (f == 1)   set out = x + y
    if f == 1: out = twos_complement_addition(x, y)
    # if (f == 0)   set out = x & y
    if f == 0:
        for i in range(len(x)):
            if x[i] and y[i]: out[i] = 1
            else: out[i] = 0
    # if (no == 1)  set out = ~out
    if no == 1:
        for i in range(len(out)):
            if out[i] == 1: out[i] = 0
            else: out[i] = 1
    # if (out == 0) set zr = 1
    if all(bit == 0 for bit in out): zr = 1
    # if (out < 0)  set ng = 1
    if binary_to_signed(out) < 0: ng = 1

    return out, zr, ng

# test cases

"""
|       x        |       y        |zx|nx|zy|ny|f|no|      out       |zr|ng|
|0000000000000000|1111111111111111| 1| 0| 1| 0|1| 0|0000000000000000| 1| 0|
|0000000000000000|1111111111111111| 1| 1| 1| 1|1| 1|0000000000000001| 0| 0|
|0000000000000000|1111111111111111| 1| 1| 1| 0|1| 0|1111111111111111| 0| 1|
|0000000000000000|1111111111111111| 0| 0| 1| 1|0| 0|0000000000000000| 1| 0|
|0000000000000000|1111111111111111| 1| 1| 0| 0|0| 0|1111111111111111| 0| 1|
|0000000000000000|1111111111111111| 0| 0| 1| 1|0| 1|1111111111111111| 0| 1|
|0000000000000000|1111111111111111| 1| 1| 0| 0|0| 1|0000000000000000| 1| 0|
|0000000000000000|1111111111111111| 0| 0| 1| 1|1| 1|0000000000000000| 1| 0|
|0000000000000000|1111111111111111| 1| 1| 0| 0|1| 1|0000000000000001| 0| 0|
|0000000000000000|1111111111111111| 0| 1| 1| 1|1| 1|0000000000000001| 0| 0|
|0000000000000000|1111111111111111| 1| 1| 0| 1|1| 1|0000000000000000| 1| 0|
|0000000000000000|1111111111111111| 0| 0| 1| 1|1| 0|1111111111111111| 0| 1|
|0000000000000000|1111111111111111| 1| 1| 0| 0|1| 0|1111111111111110| 0| 1|
|0000000000000000|1111111111111111| 0| 0| 0| 0|1| 0|1111111111111111| 0| 1|
|0000000000000000|1111111111111111| 0| 1| 0| 0|1| 1|0000000000000001| 0| 0|
|0000000000000000|1111111111111111| 0| 0| 0| 1|1| 1|1111111111111111| 0| 1|
|0000000000000000|1111111111111111| 0| 0| 0| 0|0| 0|0000000000000000| 1| 0|
|0000000000000000|1111111111111111| 0| 1| 0| 1|0| 1|1111111111111111| 0| 1|
|0000000000010001|0000000000000011| 1| 0| 1| 0|1| 0|0000000000000000| 1| 0|
|0000000000010001|0000000000000011| 1| 1| 1| 1|1| 1|0000000000000001| 0| 0|
|0000000000010001|0000000000000011| 1| 1| 1| 0|1| 0|1111111111111111| 0| 1|
|0000000000010001|0000000000000011| 0| 0| 1| 1|0| 0|0000000000010001| 0| 0|
|0000000000010001|0000000000000011| 1| 1| 0| 0|0| 0|0000000000000011| 0| 0|
|0000000000010001|0000000000000011| 0| 0| 1| 1|0| 1|1111111111101110| 0| 1|
|0000000000010001|0000000000000011| 1| 1| 0| 0|0| 1|1111111111111100| 0| 1|
|0000000000010001|0000000000000011| 0| 0| 1| 1|1| 1|1111111111101111| 0| 1|
|0000000000010001|0000000000000011| 1| 1| 0| 0|1| 1|1111111111111101| 0| 1|
|0000000000010001|0000000000000011| 0| 1| 1| 1|1| 1|0000000000010010| 0| 0|
|0000000000010001|0000000000000011| 1| 1| 0| 1|1| 1|0000000000000100| 0| 0|
|0000000000010001|0000000000000011| 0| 0| 1| 1|1| 0|0000000000010000| 0| 0|
|0000000000010001|0000000000000011| 1| 1| 0| 0|1| 0|0000000000000010| 0| 0|
|0000000000010001|0000000000000011| 0| 0| 0| 0|1| 0|0000000000010100| 0| 0|
|0000000000010001|0000000000000011| 0| 1| 0| 0|1| 1|0000000000001110| 0| 0|
|0000000000010001|0000000000000011| 0| 0| 0| 1|1| 1|1111111111110010| 0| 1|
|0000000000010001|0000000000000011| 0| 0| 0| 0|0| 0|0000000000000001| 0| 0|
|0000000000010001|0000000000000011| 0| 1| 0| 1|0| 1|0000000000010011| 0| 0|
"""

with open("_alu_tests.txt", "r") as tests:
    for test in tests.read().split('\n')[1:]:
        test = test.split('|')[1:-1]
        values = [col.strip() for col in test]
        out, zr, ng = ALU(
            # input x
            list(map(int, list(values[0]))),
            # input y
            list(map(int, list(values[1]))),
            # control bits
            zx=int(values[2]),
            nx=int(values[3]),
            zy=int(values[4]),
            ny=int(values[5]),
            f=int(values[6]),
            no=int(values[7])
        )
        assert out == list(map(int, list(values[8])))
        assert zr == int(values[9])
        assert ng == int(values[10])

[bubble-sort.py]

# https://en.wikipedia.org/wiki/Bubble_sort

unsorted_list = [14, 33, 27, 35, 10]
for i in range(len(unsorted_list)):
    for j in range(len(unsorted_list) - 1):
        if unsorted_list[j] > unsorted_list[j + 1]:
            temp = unsorted_list[j]
            # swap
            unsorted_list[j] = unsorted_list[j + 1]
            unsorted_list[j + 1] = temp

print(unsorted_list) # [10, 14, 27, 33, 35]

[combinations-with-replacement.py]

from itertools import combinations_with_replacement

my_list = ['A', 'B']
combinations = []

for item in list(range(len(my_list))):
    combinations.append(list(combinations_with_replacement(my_list, item + 1)))

print(combinations)
# [[('A',), ('B',)], [('A', 'A'), ('A', 'B'), ('B', 'B')]]

# flatten
combinations = [a for b in combinations for a in b]
print(combinations)
# [('A',), ('B',), ('A', 'A'), ('A', 'B'), ('B', 'B')]

[composing-functions.py]

import functools
import operator

def compose(a, b): return lambda x: a(b(x))

def square(x): return x * x

def double(x): return x * 2

# double then square
op = compose(square, double)
print(op(5)) # 100

# passing operator as argument
numbers = [1, 2, 3, 4, 5]
print(functools.reduce(operator.add, numbers)) # 15

[enumerate.py]

my_list = ["Zero", "One", "Two", "Three", "Four", "Five"]

for item in enumerate(my_list): print(item)
# (0, 'First')
# (1, 'Second')
# (2, 'Third')
# (3, 'Fourth')
# (4, 'Fifth')

[erlang-b-formula.py]

# https://en.wikipedia.org/wiki/Erlang_(unit)#Erlang_B_formula

from math import factorial

def erlang(A, m):
    L = (A ** m) / factorial(m)
    sum_ = 0
    for n in range(m + 1): sum_ += (A ** n) / factorial(n)
    return (L / sum_)

print(erlang(90, 107)) # 0.008799105244742682

[foreign-function-library.py]

"""
A foreign function library is a library written in
languages other than the language it is being called
from. E.g., a Python program calling function from C
library.
"""

"""
// _square.c
#include <stdio.h>

int square(int num) {
    return num * num;
}
// compile into shared library:
// $ gcc -shared -o _square.so -fPIC _square.c
"""

import ctypes

# load the shared library
square_lib = ctypes.CDLL('./_square.so')

# specify function return and argument types
square_lib.square.restype = ctypes.c_int
square_lib.square.argtypes = [ctypes.c_int]

# call the foreign function
num = 5
result = square_lib.square(num)

print(f"the square of {num} is {result}")
# the square of 5 is 25

# using C standard library functions
# https://gist.github.com/PewZ/8b473c2a6888c5c528635550d07c6186

libc = ctypes.CDLL('libc.dylib')
libc.printf(b"hello world\n") # hello world

[function-wrappers.py]

"""
Function wrappers can be used to modify behavior of function
or method. The wraps decorator copies over the function name,
docstring, and arguments list to the wrapper function. This
is very useful for debugging and logging.
"""

from functools import wraps

def logging(func):
    @wraps(func)
    def wrapper(*args, **kwargs):
        print(f"call to {func.__name__}, args: {args}, kwargs: {kwargs}")
        return func(*args, **kwargs)
    return wrapper

@logging
def power(base, exp): return base ** exp

power(2, 3) # call to power, args: (2, 3), kwargs: {}

[functools-cache.py]

"""
The lru_cache decorator caches the results of a function
call with a given set of arguments. This is useful for
functions that are computationally expensive and have a
limited set of arguments.
"""

from functools import lru_cache
import timeit

def fib(n): return n if n < 2 else fib(n - 1) + fib(n - 2)

# fibonacci with cache
@lru_cache(maxsize=128)
def fib_cache(n): return n if n < 2 else fib_cache(n - 1) + fib_cache(n - 2)

print(format(timeit.timeit('fib(30)', globals=globals(), number=1), '.17f'))
# 0.12468479387462139
print(format(timeit.timeit('fib_cache(30)', globals=globals(), number=1), '.17f'))
# 0.00001071766018867

print(fib_cache.cache_info())
# CacheInfo(hits=28, misses=31, maxsize=128, currsize=31)

[glide-typing-problem.py]

"""
Glide typing is the feature on mobile devices that allows
users to type by swiping across the keyboard. The keyboard
will predict the word based on the path of the swipe.
"""

input_ = "hgferyjkllkop"
words = ["coffee", "coding", "happy", "hello", "hop"]
chars = list(input_)

matches = []
for word in words:
    cidx = 0
    col = 0
    while col < len(chars):
        # print(chars[col], col)
        if chars[col] == word[cidx]:
            cidx += 1
            if cidx == len(word):
                matches.append((word, col))
                break
        col += 1

# all matches
print(matches) # [('hello', 11), ('hop', 12)]

# first match
print(matches[0][0]) # hello

[linked-list-using-recordclass.py]

"""
A linked list is a linear data structure where each element
is the data and reference to next element. The last element
reference to None and an empty linked list has a None head.
"""

from recordclass import recordclass

# recordclass is a mutable namedtuple
Element = recordclass("Element", ["value", "next"])

class LinkedList:
    # linked list constructor
    def __init__(self): self.head = None
    # string representation of linked list
    def __str__(self):
        if self.head is None: return "[]"
        current = self.head
        values = []
        while current is not None:
            values.append(current.value)
            current = current.next
        return str(values)
    # insert element at tail
    def insert(self, value):
        # insert at head
        if self.head is None: self.head = Element(value, None)
        else:
            current = self.head
            # iterate until last element
            while current.next is not None: current = current.next
            # insert element
            current.next = Element(value, None)
    # remove element
    def remove(self, value):
        # remove head
        if self.head.value == value: self.head = self.head.next
        else:
            current = self.head
            # iterate until last element
            while current.next is not None:
                # remove element if found
                if current.next.value == value:
                    current.next = current.next.next
                    return
                current = current.next

ll = LinkedList()

ll.insert(5)
ll.insert(10)
ll.insert(15)
ll.insert(20)
ll.insert(25)
ll.insert(30)

print(ll) # [5, 10, 15, 20, 25, 30]

ll.remove(15)
ll.remove(30)

print(ll) # [5, 10, 20, 25]

[numpy-operators.py]

import numpy as np

# numpy array basics

a = [60, 28, 49, 81]
b = [55, 634, 704, 2020]

A = np.array(a, dtype='i') # [60 28 49 81]

AB = np.array([a, b])
# [[  60   28   49   81]
#  [  55  634  704 2020]]

print(AB.ndim) # 2
print(AB.shape) # (2, 4)

arr_zero = np.zeros(4) # [0. 0. 0. 0.]

arr_ones = np.ones((2, 3))
# [[ 1.  1.  1.]
#  [ 1.  1.  1.]]

arr_range = np.arange(0, 10)
# [0 1 2 3 4 5 6 7 8 9]

arr_linspace = np.linspace(0, 1, 5)
# [0.   0.25 0.5  0.75 1.  ]

arr_log = np.logspace(0, 1, 5)
# [ 1.          1.77827941  3.16227766  5.62341325 10.        ]

# slicing

print(A[1:3])
# [28 49]
print(AB[0:2, 2:4])
# [[  49   81]
#  [ 704 2020]]

# reverse order
print(A[::-1]) # [81 49 28 60]

print(arr_range.mean()) # 4.5
print(arr_range.sum()) # 45
print(AB.min()) # 28
print(AB.max()) # 2020

print(np.sin(AB))
# [[-0.30481062  0.27090579 -0.95375265 -0.62988799]
#  [-0.99975517 -0.56605794  0.27947339  0.04406199]]

print(np.multiply(a, b))
# [  3300  17752  34496 163620]

print(np.sqrt(b))
# [ 7.41619849 25.17935662 26.53299832 44.94441011]

# min value in each column
print(np.minimum(a, b)) # [55 28 49 81]

# sum of axis (columns)
print(np.sum(AB, axis=1)) # [ 218 3413]

# numpy indexing

# create array with 8 integers
A = 2 * np.arange(8)**2 + 1
# [ 1  3  9 19 33 51 73 99]

# create array with 16 integers
B = np.arange(16)
B.shape = (4, 4)
# [[ 0  1  2  3]
#  [ 4  5  6  7]
#  [ 8  9 10 11]
#  [12 13 14 15]]

print(A[[3, -1, 1]])
# [19 99  3]
print(B[:, [2, -1, 0]])
# [[ 2  3  0]
#  [ 6  7  4]
#  [10 11  8]
#  [14 15 12]]

# elements from A at indices given by fibonacci sequence
fibseq = np.array([0, 1, 1, 2, 3])
print(A[fibseq]) # [ 1  3  3  9 19]

# diagonal
i = np.arange(4)
print(B[i, i]) # [ 0  5 10 15]

# diagonal of part
print(B[i[:3], i[:3] + 1]) # [ 1  6 11]

# numpy masking

# create array with 16 integers
C = np.arange(16)
C.shape = (4, 4)
# [[ 0  1  2  3]
#  [ 4  5  6  7]
#  [ 8  9 10 11]
#  [12 13 14 15]]

# create mask with True
mask = np.ones(4, dtype=bool) # [ True  True  True  True]

# diagonal
print(C[mask, mask]) # [ 0  5 10 15]

# conditional mask
conditional = (C >= 9)
print(C[conditional]) # [ 9 10 11 12 13 14 15]

# get all values smaller than 9
print(C[C < 9]) # [0 1 2 3 4 5 6 7 8]

# get all values smaller than 5 or larger than 10
print(C[(C < 5) | (C > 10)])
# [ 0  1  2  3  4 11 12 13 14 15]

# where
print(C[np.where(C > 10)]) # [11 12 13 14 15]

# get all columns with a value less than 3
print(C[:, np.where(C < 3)[1]])
# [[ 0  1  2]
#  [ 4  5  6]
#  [ 8  9 10]
#  [12 13 14]]

# numpy operations

A = np.arange(6) # [0 1 2 3 4 5]
print(A + A) # [ 0  2  4  6  8 10]
print(A - 1) # [-1  0  1  2  3  4]
print(A * 6) # [ 0  6 12 18 24 30]

# gradient
X = np.array([2, 4, 5])
Y = np.array([6, 2, 8])
print(np.gradient(X))
# [ 2.   1.5  1. ] => (4 - 2) / 1, (5 - 2) / 2, (5 - 4)/ 1
print(np.gradient(Y))
# [-4.  1.  6.] => (2 - 6) / 1, (8 - 6) / 2, (8 - 2)/ 1

# numerical derivative
print(np.gradient(Y) / np.gradient(X))
# [-2.          0.66666667  6.        ]

B = np.arange(4)
B.shape = (2, 2)
# [[0 1]
#  [2 3]]

v = np.array([[2],[4]])
# [[2]
#  [4]]

# scalar (multiplication)
print(B * v)
# [[ 0  2]
#  [ 8 12]]

# dot product
print(np.dot(B, v))
# [[ 4]
#  [16]]

# operations on higher dimensions
M = np.arange(12)
M.shape = (4, 3)
# [[ 0  1  2]
#  [ 3  4  5]
#  [ 6  7  8]
#  [ 9 10 11]]

v = np.array([16, 17, 18])

print(M + v)
# [[16 18 20]
#  [19 21 23]
#  [22 24 26]
#  [25 27 29]]

[pandas-operators.py]

import pandas as pd

# creating series (one-dimensional array)
simple_series = pd.Series([42, 55, 73], dtype='f8')
# 0     42.0
# 1     55.0
# 2     73.0
# dtype: float64

# creating series with specified index
index_series = pd.Series([42, 55, 73], index=["electron", "proton", "neutron"], dtype='f8')
# electron      42.0
# proton        55.0
# neutron       73.0
# dtype: float64

# accessing value in series
print(index_series["electron"])
# 42.0

# accessing multiple values in series (range)
print(index_series["electron":"neutron"])
# electron      42.0
# proton        55.0
# neutron       73.0
# dtype: float64

# accessing multiple values in series using indexing
print(index_series[1:])
# proton        55.0
# neutron       73.0
# dtype: float64

# creating series from dictionary
dict_series = pd.Series({ "electron": 6, "neutron": 28, "proton": 496, "neutrino": 8128 })
# electron      6
# neutrino      8128
# neutron       28
# proton        496
# dtype: int64

# combining two series into one column
print(index_series + dict_series)
# electron      48.0
# neutrino      NaN
# neutron       101.0
# proton        551.0
# dtype: float64

# combining two series as dataframe
combined_series = pd.DataFrame({ "A": index_series, "B": dict_series })
#               A       B
# electron      42.0    6
# neutrino      NaN     8128
# neutron       73.0    28
# proton        55.0    496

# accessing columns as series
print(combined_series["A"])
# electron      42.0
# neutrino      NaN
# neutron       73.0
# proton        55.0
# Name: A, dtype: float64

# add new row with index
append_series = combined_series._append(pd.DataFrame({ "A": [-8128] }, index=["antineutrino"]))
#               A       B
# electron      42.0    6.0
# neutrino      NaN     8128.0
# neutron       73.0    28.0
# proton        55.0    496.0
# antineutrino  -8128.0 NaN

# drop row
append_series = append_series.drop("neutron")
#               A       B
# electron      42.0    6.0
# neutrino      NaN     8128.0
# proton        55.0    496.0
# antineutrino  -8128.0 NaN

# transpose
print(combined_series.T)
#       electron    neutrino    neutron     proton
# A     42.0        NaN         73.0        55.0
# B     6.0         8128.0      28.0        496.0

# masking
print(combined_series > 120)
#               A       B
# electron      False   False
# neutrino      False   True
# neutron       False   False
# proton        False   True

# add masking as column (e.g. larger than 120)
combined_series["large"] = (combined_series["A"] > 120) | (combined_series["B"] > 120)
#               A       B       large
# electron      42.0    6       False
# neutrino      NaN     8128    True
# neutron       73.0    28      False
# proton        55.0    496     True

# delete a column
del combined_series["large"]
#               A       B
# electron      42.0    6
# neutrino      NaN     8128
# neutron       73.0    28
# proton        55.0    496

[partial-functions.py]

"""
A partial function is a function with some arguments already
filled in. This is useful for creating new functions from
existing functions.
"""

from functools import partial

def power(base, exp): return base ** exp

# partial functions
square = partial(power, exp=2)
cube = partial(power, exp=3)

print(square(2)) # 4
print(cube(2)) # 8

# partial functions with map
numbers = [1, 2, 3, 4, 5]

print(list(map(square, numbers)))
# [1, 4, 9, 16, 25]
print(list(map(cube, numbers)))
# [1, 8, 27, 64, 125]

[regular-expression.py]

import re

text = "some random text to test regular expressions"
date = "2017-07-16"

# create pattern -> four letter word ending with "st"
pattern_text = "..st"
pattern = re.compile(pattern_text)

# search for pattern in text
re_search = re.search(pattern, text)
if (re_search): print(re_search.group()) # test

# separate text
print(re.split(pattern, text))
# ['some random text to ', ' regular expressions']

# substitute word in text
print(re.sub(pattern, "learn", text, 1))
# some random text to learn regular expressions

# match
print(re.match("20[01][0-9].*[0-9][0-9].*[0-9][0-9]", date) != None)
# True

[sobel-filter-using-opencl.py]

"""
A Sobel filter is an edge detection filter. It's a 3x3
convolution commonly used in image processing.
"""

import numpy as np
import pyopencl as cl
from PIL import Image, ImageFilter

# load image
input_image = Image.open('_images/photo.png').convert('L')
input_array = np.array(input_image).astype(np.uint8)

# input_image.show()

# sobel kernel
# sobel_x_kernel = np.array([[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]]).astype(np.float32)
# sobel_y_kernel = np.array([[-1, -2, -1], [0, 0, 0], [1, 2, 1]]).astype(np.float32)

# opencl
platform = cl.get_platforms()[0]
device = platform.get_devices()[2] # AMD Radeon Pro 5500M Compute Engine
ctx = cl.Context([device])
queue = cl.CommandQueue(ctx)

# buffers
input_buffer = cl.Buffer(ctx, cl.mem_flags.READ_ONLY | cl.mem_flags.COPY_HOST_PTR, hostbuf=input_array)
output_buffer = cl.Buffer(ctx, cl.mem_flags.WRITE_ONLY, input_array.nbytes)

# compile kernel
program = cl.Program(ctx, """
    __kernel void sobel_filter(__global const uchar* input, __global uchar* output, const int width, const int height) {
        int x = get_global_id(0);
        int y = get_global_id(1);

        if (x > 0 && x < width - 1 && y > 0 && y < height - 1) {
            float sum_x = 0;
            float sum_y = 0;

            const float sobel_x_kernel[3][3] = { {-1, 0, 1}, {-2, 0, 2}, {-1, 0, 1} };
            const float sobel_y_kernel[3][3] = { {-1, -2, -1}, {0, 0, 0}, {1, 2, 1} };

            for (int i = -1; i <= 1; ++i) {
                for (int j = -1; j <= 1; ++j) {
                    sum_x += input[(y + i) * width + (x + j)] * sobel_x_kernel[i + 1][j + 1];
                    sum_y += input[(y + i) * width + (x + j)] * sobel_y_kernel[i + 1][j + 1];
                }
            }

            float gradient_magnitude = sqrt(sum_x * sum_x + sum_y * sum_y);
            gradient_magnitude = gradient_magnitude > 255 ? 255 : gradient_magnitude;

            output[y * width + x] = (uchar)gradient_magnitude;
        } else {
            output[y * width + x] = 0;
        }
    }
""").build()

program.sobel_filter(queue, input_array.shape, None, input_buffer, output_buffer, np.int32(input_array.shape[1]), np.int32(input_array.shape[0]))

# read result
output_array = np.empty_like(input_array)
cl.enqueue_copy(queue, output_array, output_buffer).wait()

# save image
output_image = Image.fromarray(output_array, 'L')
output_image.save('_images/edges.png')

# show image
# output_image.show()

ci^

genetic-algorithm-optimization.pyparticle-swarm-optimisation.py

[genetic-algorithm-optimization.py]

# https://en.wikipedia.org/wiki/Genetic_algorithm
import random
import math
# https://pypi.org/project/tabulate/
from tabulate import tabulate

random.seed(42)

# helper function to print as table
def print_as_table(population):
    table = tabulate(
        population,
        headers=['n', 'encoding', 'decoded x, y', 'cost'],
        floatfmt=".3f",
        tablefmt="simple"
    )
    print(table, end="\n\n")

def encode(x, x_low, x_high, m):
    """Encode decimal number into binary

    x (int)                 : decimal number
    x_low (int)             : lower bound of x
    x_high (int)            : upper bound of x
    m (int)                 : number of bits
    """
    decimal = round((x - x_low) / ((x_high - x_low) / (2 ** m - 1)))
    binary = []
    while decimal >= 1:
        if decimal % 2 == 1:
            binary.append(1)
        else:
            binary.append(0)
        decimal = math.floor(decimal / 2)
    while len(binary) < 4:
        binary.append(0)

    return list(reversed(binary))

assert encode(9, -10, 14, 5) == [1, 1, 0, 0, 1]

def decode(B, x_low, x_high, m):
    """Decode binary into decimal number

    B (list)                : binary number
    x_low (int)             : lower bound of x
    x_high (int)            : upper bound of x
    m (int)                 : number of bits
    """

    return x_low + int((''.join(map(str, B))), 2) * ((x_high - x_low) / ((2 ** m) - 1))

assert int(decode([1, 1, 0, 0, 1], -10, 14, 5)) == 9

def generate_population(f, n_pop, x_range, y_range, m_bits):
    """Generate initial population

    f (function)            : cost function
    n_pop (int)             : number of population
    x_range (list)          : range of x
    y_range (list)          : range of y
    m_bits (int)            : number of bits
    """
    pop_lst = []
    for i in range(n_pop):
        x = random.randint(x_range[0], x_range[1])
        y = random.randint(y_range[0], y_range[1])
        # encoded values
        x_encoded = encode(x, x_range[0], x_range[1], m_bits)
        y_encoded = encode(y, y_range[0], y_range[1], m_bits)
        # decoded values
        x_decoded = round(decode(x_encoded, x_range[0], x_range[1], m_bits), 2)
        y_decoded = round(decode(y_encoded, y_range[0], y_range[1], m_bits), 2)
        # determine initial cost
        cost = round(f(x_decoded, y_decoded), 2)
        # append to list
        pop_lst.append([i, x_encoded + y_encoded, [x_decoded, y_decoded], cost])
    # sort on cost
    pop_lst.sort(key = lambda x: x[3])
    # update index
    for i in range(len(pop_lst)):
        pop_lst[i][0] = i

    return pop_lst

# example_population = generate_population(
#     f,
#     n_pop=6,
#     x_range=[5, 20],
#     y_range=[-5, 15],
#     m_bits=4
# )
# print_as_table(example_population)
#   n  encoding                  decoded x, y       cost
# ---  ------------------------  --------------  -------
#   0  [0, 0, 1, 0, 1, 1, 1, 0]  [7.0, 13.67]     22.160
#   1  [0, 0, 1, 1, 1, 1, 0, 1]  [8.0, 12.33]     30.680
#   2  [0, 0, 1, 1, 0, 0, 0, 0]  [8.0, -5.0]     100.000
#   3  [1, 0, 0, 0, 0, 1, 0, 1]  [13.0, 1.67]    119.140
#   4  [0, 1, 1, 1, 0, 0, 1, 1]  [12.0, -1.0]    126.000
#   5  [1, 1, 0, 1, 0, 0, 0, 1]  [18.0, -3.67]   213.030

def generate_offsprings(population, crossover):
    """Generate offsprings

    population (list)       : population
    crossover (list)        : crossover points
    """
    n = 0
    offsprings_lst = []
    while n < len(population):
        offsprings_lst.append(
            population[n][1][0:crossover[0]] +
            population[n + 1][1][crossover[0]:crossover[1]] +
            population[n][1][crossover[1]:]
        )
        offsprings_lst.append(
            population[n + 1][1][0:crossover[0]] +
            population[n][1][crossover[0]:crossover[1]] +
            population[n + 1][1][crossover[1]:]
        )
        # pair-wise
        n += 2

    return offsprings_lst

def mutate(offsprings, mu, m_bits):
    """Mutate offsprings

    offsprings (list)       : offsprings
    mu (float)              : mutation rate
    m_bits (int)            : number of bits
    """
    nbits = round(mu * (len(offsprings) * m_bits * 2))
    for i in range(nbits):
        offspring = random.randint(0, len(offsprings) - 1)
        bit = random.randint(0, m_bits * 2 - 1)
        # flip bits
        if offsprings[offspring][bit] == 1:
            offsprings[offspring][bit] = 0
        else:
            offsprings[offspring][bit] = 1

    return offsprings

def update_population(f, current_population, offsprings, keep, x_range, y_range, m_bits):
    """Update population

    f (function)                : cost function
    current_population (list)   : current population
    offsprings (list)           : offsprings
    keep (int)                  : number of population to keep
    x_range (list)              : range of x
    y_range (list)              : range of y
    m_bits (int)                : number of bits
    """
    offsprings_lst = []
    for i in range(len(offsprings)):
        # decoded values
        x_decoded = round(decode(offsprings[i][:4], x_range[0], x_range[1], m_bits), 2)
        y_decoded = round(decode(offsprings[i][4:], y_range[0], y_range[1], m_bits), 2)
        # determine initial cost
        cost = round(f(x_decoded, y_decoded), 2)
        # append to list
        offsprings_lst.append([i, offsprings[i], [x_decoded, y_decoded], cost])
    # sort on cost
    offsprings_lst.sort(key = lambda x: x[3])
    # update index
    for i in range(len(offsprings_lst)):
        offsprings_lst[i][0] = i
    # discard current population
    current_population[keep:] = offsprings_lst[:keep]
    # sort on cost
    current_population.sort(key = lambda x: x[3])
    # update index
    for i in range(len(current_population)):
        current_population[i][0] = i

    return current_population

M_BITS = 4
N_POP = 4
N_KEEP = 2
MUTATE_RATE = 0.1
# max number of generations
MAX_GEN = 10000
# crossover points
crossover = [3, 6]

# cost function to minimize
def f(x, y): return -x * ((y / 2) - 10)
# bounds
x_range = [10, 20]
y_range = [-5, 7]

current_population = generate_population(f, N_POP, x_range, y_range, M_BITS)
print_as_table(current_population)
#   n  encoding                  decoded x, y       cost
# ---  ------------------------  --------------  -------
#   0  [0, 0, 0, 0, 1, 1, 1, 0]  [10.0, 6.2]      69.000
#   1  [0, 1, 0, 0, 0, 0, 1, 0]  [12.67, -3.4]   148.240
#   2  [0, 1, 1, 0, 0, 1, 0, 0]  [14.0, -1.8]    152.600
#   3  [1, 1, 1, 1, 0, 0, 0, 1]  [20.0, -4.2]    242.000

for i in range(MAX_GEN):
    # generate offsprings
    offsprings = generate_offsprings(current_population, crossover)
    # mutate
    offsprings = mutate(offsprings, MUTATE_RATE, M_BITS)
    # update population
    current_population = update_population(
        f,
        current_population,
        offsprings,
        N_KEEP,
        x_range,
        y_range,
        M_BITS
    )

print_as_table(current_population)
#   n  encoding                  decoded x, y      cost
# ---  ------------------------  --------------  ------
#   0  [0, 0, 0, 0, 1, 1, 1, 1]  [10.0, 7.0]     65.000
#   1  [0, 0, 0, 0, 1, 1, 1, 1]  [10.0, 7.0]     65.000
#   2  [0, 0, 0, 0, 1, 1, 1, 1]  [10.0, 7.0]     65.000
#   3  [0, 0, 0, 0, 1, 1, 1, 1]  [10.0, 7.0]     65.000

[particle-swarm-optimisation.py]

# https://en.wikipedia.org/wiki/Particle_swarm_optimization
import random

random.seed(42)

# feel free to change this to stop at convergence
MAX_ITERATIONS = 50

# constant inertia weight
weight = 0.5
# cognative constant
c_1 = 1
# social constant
c_2 = 2

def generate_swarm(x_0, n_par):
    """Generate swarm of particles

    x_0 (list)              : initial position
    n_par (int)             : number of particles
    """
    dimensions = len(x_0)
    swarm = []
    # generate particles
    for i in range(0, n_par):
        position = []
        # best position
        position_best = -1
        # particle velocity
        velocity = []
        # particle error (cost)
        error = -1
        # best error (cost)
        error_best = error
        # position and velocity
        for i in range(0, dimensions):
            position.append(x_0[i])
            velocity.append(random.uniform(-1, 1))
        # append particle
        swarm.append({
            "dimensions": dimensions,
            "position": position,
            "position_best": position_best,
            "velocity": velocity,
            "error": error,
            "error_best": error_best
        })

    return swarm

def update_velocity(velocity, position, position_best, global_pos):
    """Update particle velocity

    velocity (float)        : particle velocity
    position (float)        : particle position
    position_best (float)   : best position
    global_pos (float)      : global best position
    """
    # random bias
    r_1 = random.random()
    r_2 = random.random()
    # update velocity
    velocity_cognative = c_1 * r_1 * (position_best - position)
    velocity_social = c_2 * r_2 * (global_pos - position)
    velocity = weight * velocity + velocity_cognative + velocity_social

    return velocity

def update_position(position, velocity):
    """Update particle position

    position (float)        : particle position
    velocity (float)        : particle velocity
    """
    position = position + velocity
    return position

def iterate_swarm(f, swarm, bounds=None, global_best=-1, global_pos=-1):
    """Iterate swarm

    f (function)            : cost function
    swarm (list)            : list of particles
    bounds (list)           : list of bounds for each dimension
    global_best (float)     : global best error
    global_pos (float)      : global best position
    """
    for j in range(0, len(swarm)):
        dimensions = swarm[j]["dimensions"]
        position = swarm[j]["position"]
        error_best = swarm[j]["error_best"]
        # evaluate new error (cost)
        error = swarm[j]["error"] = f(position)
        # update local best position if current position gives
        # better local error
        if (error < error_best or error_best == -1):
            swarm[j]["position_best"] = position
            swarm[j]["error_best"] = error
        position_best = swarm[j]["position_best"]
        velocity = swarm[j]["velocity"]
        # update global best if position of current particle gives
        # best global error
        if (error < global_best or global_best == -1):
            global_pos = list(position)
            global_best = float(error)
        # update particle velocity and position
        for i in range(0, dimensions):
            velocity[i] = update_velocity(
                velocity[i],
                position[i],
                position_best[i],
                global_pos[i]
            )
            position[i] = update_position(
                position[i],
                velocity[i]
            )
            # max value for position
            if bounds and (position[i] > bounds[i][1]):
                position[i] = bounds[i][1]
            # min value for position
            if bounds and (position[i] < bounds[i][0]):
                position[i] = bounds[i][0]
    # return
    return swarm, round(global_best, 2), [round(pos, 2) for pos in global_pos]

# minimize x^5 - 3x^4 + 5 over [0, 4]
def f(x): return x[0] ** 5 - 3 * x[0] ** 4 + 5
# reset global
global_best = -1
global_pos = -1
# initial swarm
swarm = generate_swarm(x_0=[5], n_par=15)
# iterate swarm
for i in range(MAX_ITERATIONS):
    swarm, global_best, global_pos = iterate_swarm(
        f,
        swarm,
        bounds=[(0, 4)],
        global_best=global_best,
        global_pos=global_pos
    )
assert (global_best, global_pos) == (-14.91, [2.39])

# minimize -(5 + 3x - 4y - x^2 + x y - y^2)
def f(x): return -(5 + 3 * x[0] - 4 * x[1] - x[0] ** 2 + x[0] * x[1] - x[1] ** 2)
# reset global
global_best = -1
global_pos = -1
# initial swarm
swarm = generate_swarm(x_0=[5, 5], n_par=15)
# iterate swarm
for i in range(MAX_ITERATIONS):
    swarm, global_best, global_pos = iterate_swarm(
        f,
        swarm,
        global_best=global_best,
        global_pos=global_pos
    )
assert (global_best, global_pos) == (-9.33, [0.67, -1.67])

ml^

backpropagation.pyconvolutional-neural-network.pydelta-learning-algorithm.pygradient-descent-algorithm.pyk-nearest-neighbors-classifier.pylinear-threshold-unit.pynumpy-linear-relu.pywidrow-hoff-learning-algorithm.py

[backpropagation.py]

# https://en.wikipedia.org/wiki/Backpropagation
import numpy as np

np.random.seed(42)

# https://en.wikipedia.org/wiki/Sigmoid_function
def sigmoid(x): return 1.0 / (1 + np.exp(-x))
assert(sigmoid(0) == 0.5)

# derivative of sigmoid
def sigmoid_dx(x): return x * (1.0 - x)
assert(sigmoid_dx(0.5) == 0.25)

# input
x = np.array([[0,0,1], [0,1,1], [1,0,1], [1,1,1]])
y = np.array([[0], [1], [1], [0]])
# weights
w_1 = np.random.rand(x.shape[1],4)
w_2 = np.random.rand(4,1)
# output
output = np.zeros(y.shape)

def feedforward(x, w_1, w_2, output):
    layer_1 = sigmoid(np.dot(x, w_1))
    output = sigmoid(np.dot(layer_1, w_2))
    return layer_1, w_1, w_2, output

def backpropagation(layer_1, w_1, w_2, x, y, output):
    w_2_dx = np.dot(
        np.transpose(layer_1),
        (2 * (y - output) * sigmoid_dx(output))
    )
    w_1_dx = np.dot(
        np.transpose(x),
        (np.dot(2 * (y - output) * sigmoid_dx(output), np.transpose(w_2)) * sigmoid_dx(layer_1))
    )
    # update weights
    w_1 += w_1_dx
    w_2 += w_2_dx

    return layer_1, w_1, w_2, x, y, output

for i in range(1500):
    layer_1, w_1, w_2, output = feedforward(x, w_1, w_2, output)
    layer_1, w_1, w_2, x, y, output = backpropagation(layer_1, w_1, w_2, x, y, output)

print(output)
# [[0.01043733]
#  [0.97230567]
#  [0.97090151]
#  [0.03501066]]

[convolutional-neural-network.py]

# https://en.wikipedia.org/wiki/Convolutional_neural_network
import os
import numpy as np
import matplotlib.pyplot as plt

from tensorflow.keras.datasets import mnist
from tensorflow.keras.models import Sequential, load_model
from tensorflow.keras.layers import Dense, Dropout, Flatten, Conv2D, MaxPooling2D
from tensorflow.keras.utils import to_categorical
from tqdm.keras import TqdmCallback

# avoid libiomp5 error and less noise
os.environ["KMP_DUPLICATE_LIB_OK"] = "True"
os.environ["CUDA_VISIBLE_DEVICES"] = ""

# configuration
batch_size = 128
n_classes = 10
epochs = 5

# https://keras.io/datasets
(X_train, Y_train), (X_test, Y_test) = mnist.load_data()

# reshape and set type
X_train = X_train.reshape(X_train.shape[0], 28, 28, 1)
X_test = X_test.reshape(X_test.shape[0], 28, 28, 1)
X_train = X_train.astype('float32')
X_test = X_test.astype('float32')

# normalize
X_train = X_train / 255
X_test = X_test / 255

# https://en.wikipedia.org/wiki/One-hot
Y_train = to_categorical(Y_train, n_classes)
Y_test = to_categorical(Y_test, n_classes)
# print(Y_train.shape)
# print(Y_test.shape)

# https://keras.io/models/sequential
model = Sequential()
# layers
model.add(Conv2D(filters=32, kernel_size=(5, 5), activation='relu', input_shape=(28, 28, 1)))
model.add(Conv2D(filters=64, kernel_size=(3, 3), activation='relu'))
model.add(MaxPooling2D(pool_size=(2, 2)))
model.add(Dropout(0.25))
model.add(Flatten())
model.add(Dense(n_classes, activation='relu'))
model.add(Dropout(0.5))
model.add(Dense(n_classes, activation='softmax'))

# https://keras.io/optimizers
model.compile(loss='categorical_crossentropy', metrics=['accuracy'], optimizer='adadelta')

# train model
model.fit(
    X_train,
    Y_train,
    validation_data=(X_test, Y_test),
    epochs=epochs,
    batch_size=batch_size,
    verbose=0,
    callbacks=[TqdmCallback(verbose=1)]
)

# evaluate
metrics = model.evaluate(X_test, Y_test, verbose=2)
# metrics
loss = metrics[0]
accuracy = metrics[1]
print(loss) # 0.029002553918152263
print(accuracy) # 0.9906

[delta-learning-algorithm.py]

# https://en.wikipedia.org/wiki/Delta_rule
import numpy as np
from tabulate import tabulate

# initial weights
w = [1, 0, 0]
# learning rate
n = 1
# iterations
iterations = 12

# dataset
X = [[1, 0, 2],
     [1, 1, 2],
     [1, 2, 1],
     [1, -3, 1],
     [1, -2, -1],
     [1, -3, -2]]
# classes
t = [1, 1, 1, 0, 0, 0]

# https://en.wikipedia.org/wiki/Heaviside_step_function
def transfer_function(w, x):
    wx = np.dot(w, x)
    if (wx > 0):
        return 1
    elif (wx == 0):
        return 0.5
    else:
        return 0

assert (transfer_function([0.1, -0.5, 0.4], [0.1, -0.5, 0.4]) == 1)
assert (transfer_function([0.1, -0.5, 0.4], [0.1, 0.5, 0.4]) == 0)
assert (transfer_function([0, 0, 0], [0, 0, 0]) == 0.5)

# sequential delta learning algorithm
result = []
for o in range(int(iterations / len(X))):
    for i in range(len(X)):
        if ((i + 1 + (len(X) * o)) > iterations): break
        w_prev = w
        x = X[i]
        y = transfer_function(w, x)
        # calculate update part
        update = np.zeros(len(x))
        for j in range(len(x)): update[j] = n * (t[i] - y) * x[j]
        # add update part to w
        w = np.add(w, update)
        # append to result
        result.append([
            # iteration
            i + 1 + (len(X) * o),
            # w
            list(w_prev),
            # x
            x,
            # y = H(wx)
            y,
            # t
            t[i],
            # w_new
            list(w)]
        )

print(tabulate(result, headers=['i', 'w', 'x', 'y = H(wx)', 't', 'w_new'], tablefmt="simple"))
#   i  w                 x              y = H(wx)    t  w_new
# ---  ----------------  -----------  -----------  ---  ----------------
#   1  [1, 0, 0]         [1, 0, 2]              1    1  [1.0, 0.0, 0.0]
#   2  [1.0, 0.0, 0.0]   [1, 1, 2]              1    1  [1.0, 0.0, 0.0]
#   3  [1.0, 0.0, 0.0]   [1, 2, 1]              1    1  [1.0, 0.0, 0.0]
#   4  [1.0, 0.0, 0.0]   [1, -3, 1]             1    0  [0.0, 3.0, -1.0]
#   5  [0.0, 3.0, -1.0]  [1, -2, -1]            0    0  [0.0, 3.0, -1.0]
#   6  [0.0, 3.0, -1.0]  [1, -3, -2]            0    0  [0.0, 3.0, -1.0]
#   7  [0.0, 3.0, -1.0]  [1, 0, 2]              0    1  [1.0, 3.0, 1.0]
#   8  [1.0, 3.0, 1.0]   [1, 1, 2]              1    1  [1.0, 3.0, 1.0]
#   9  [1.0, 3.0, 1.0]   [1, 2, 1]              1    1  [1.0, 3.0, 1.0]
#  10  [1.0, 3.0, 1.0]   [1, -3, 1]             0    0  [1.0, 3.0, 1.0]
#  11  [1.0, 3.0, 1.0]   [1, -2, -1]            0    0  [1.0, 3.0, 1.0]
#  12  [1.0, 3.0, 1.0]   [1, -3, -2]            0    0  [1.0, 3.0, 1.0]

[gradient-descent-algorithm.py]

# https://en.wikipedia.org/wiki/Gradient_descent
import numpy as np
import random

random.seed(42)

def gradient_descent(x, y, theta, alpha, m, num_iterations):
    """Gradient descent algorithm

    x (numpy.ndarray)       : input data
    y (numpy.ndarray)       : target variable
    theta (numpy.ndarray)   : parameters
    alpha (float)           : learning rate
    m (int)                 : number of examples
    num_iterations (int)    : number of iterations
    """
    x_transpose = x.transpose()

    for i in range(0, num_iterations):
        hypothesis = np.dot(x, theta)
        loss = hypothesis - y
        cost = np.sum(loss ** 2) / (2 * m)
        # print
        print("Iteration: %d, Cost: %f" % (i, cost))
        # average gradient per example
        gradient = np.dot(x_transpose, loss) / m
        # update
        theta = theta - alpha * gradient

    return theta

def generate_data(num_points, bias, variance):
    """Generate data

    num_points (int)    : number of points
    bias (int)          : bias
    variance (int)      : variance
    """
    x = np.zeros(shape=(num_points, 2))
    y = np.zeros(shape=num_points)
    # straight line
    for i in range(0, num_points):
        # bias feature
        x[i][0] = 1
        x[i][1] = 1
        # target variable
        y[i] = (i + bias) + random.uniform(0, 1) * variance

    return x, y

# generate data
x, y = generate_data(100, 25, 10)
m, n = np.shape(x)
# configuration variables
num_iterations = 10000
alpha = 0.0005
theta = np.ones(n)
# run gradient descent
theta = gradient_descent(x, y, theta, alpha, m, num_iterations)
print(theta)
# Iteration: 0, Cost: 3417.449751
# Iteration: 1, Cost: 3411.478114
# Iteration: 2, Cost: 3405.518415
# ...
# Iteration: 9997, Cost: 430.137723
# Iteration: 9998, Cost: 430.137723
# Iteration: 9999, Cost: 430.137723
# [39.64610036 39.64610036]

[k-nearest-neighbors-classifier.py]

# https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
import numpy as np
from sklearn import datasets
from tabulate import tabulate

# load iris dataset
iris = datasets.load_iris()
# sample to test classifier
sample = np.array([
    [1, 9, 0, 4, 5, 3, 2],
    [9, 0, 4, 5, 3, 2, 1],
    [0, 4, 5, 3, 2, 1, 9],
    [4, 5, 3, 2, 1, 9, 0]
])
sample = sample / np.array([2.3, 4, 1.5, 4]).reshape(-1, 1)
sample = sample + np.array([4, 2, 1, 0]).reshape(-1, 1)
sample = sample.transpose()

# sklearn
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import classification_report, confusion_matrix, accuracy_score

# split training dataset
X_train, X_test, Y_train, Y_test = train_test_split(iris.data, iris.target, test_size=0.2)

# training and predictions
classifier = KNeighborsClassifier(n_neighbors=3, metric='euclidean')
classifier.fit(X_train, Y_train)

# evaluate
Y_prediction = classifier.predict(X_test)
# print(confusion_matrix(Y_test, Y_prediction))
print(classification_report(Y_test, Y_prediction))
#               precision    recall  f1-score   support

#            0       1.00      1.00      1.00        11
#            1       0.91      0.91      0.91        11
#            2       0.88      0.88      0.88         8

#     accuracy                           0.93        30
#    macro avg       0.93      0.93      0.93        30
# weighted avg       0.93      0.93      0.93        30
print(accuracy_score(Y_test, Y_prediction))
# 0.9333333333333333

# predict sample
Y_prediction = classifier.predict(sample)

table = list(zip([list(np.round(x, 1)) for x in sample], Y_prediction))
print(tabulate(table, headers=['sample', 'label'], tablefmt="simple"))
# sample                  label
# --------------------  -------
# [4.4, 4.2, 1.0, 1.0]        0
# [7.9, 2.0, 3.7, 1.2]        1
# [4.0, 3.0, 4.3, 0.8]        1
# [5.7, 3.2, 3.0, 0.5]        1
# [6.2, 2.8, 2.3, 0.2]        0
# [5.3, 2.5, 1.7, 2.2]        0
# [4.9, 2.2, 7.0, 0.0]        2

[linear-threshold-unit.py]

# https://en.wikipedia.org/wiki/Artificial_neuron
import numpy as np
from tabulate import tabulate

# https://en.wikipedia.org/wiki/Heaviside_step_function
def H(x, w, threshold=1):
    wx = np.dot(w, x)
    if (wx >= threshold): return 1
    else: return 0

assert (H([0.1, -0.5, 0.4], [0.1, -0.5, 0.4], 0) == 1)
assert (H([0.1, 0.5, 0.4], [0.1, -0.5, 0.4], 0) == 0)

table = []

# logical AND
threshold = 1.5
table.append(['AND', [0, 0], [1, 1], threshold, H([0, 0], [1, 1], threshold)])
table.append(['AND', [0, 1], [1, 1], threshold, H([0, 1], [1, 1], threshold)])
table.append(['AND', [1, 0], [1, 1], threshold, H([1, 0], [1, 1], threshold)])
table.append(['AND', [1, 1], [1, 1], threshold, H([1, 1], [1, 1], threshold)])

# logical NOT
threshold = -0.5
table.append(['NOT', [0], [-1], threshold, H([0], [-1], threshold)])
table.append(['NOT', [1], [-1], threshold, H([1], [-1], threshold)])

# logical OR
threshold = 0.5
table.append(['OR', [0, 0], [1, 1], threshold, H([0, 0], [1, 1], threshold)])
table.append(['OR', [0, 1], [1, 1], threshold, H([0, 1], [1, 1], threshold)])
table.append(['OR', [1, 0], [1, 1], threshold, H([1, 0], [1, 1], threshold)])
table.append(['OR', [1, 1], [1, 1], threshold, H([1, 1], [1, 1], threshold)])

# combination: (A AND NOT B) OR (A AND C) OR (NOT B AND C)
threshold = 1
table.append(['COMBINATION', [0, 0, 0], [2, -2, 2], threshold, H([0, 0, 0], [2, -2, 2], threshold)])
table.append(['COMBINATION', [1, 0, 0], [2, -2, 2], threshold, H([1, 0, 0], [2, -2, 2], threshold)])
table.append(['COMBINATION', [0, 1, 0], [2, -2, 2], threshold, H([0, 1, 0], [2, -2, 2], threshold)])

print(tabulate(table, headers=['unit', 'x', 'w', 'threshold', 'output'], tablefmt="simple"))
# unit         x          w             threshold    output
# -----------  ---------  ----------  -----------  --------
# AND          [0, 0]     [1, 1]              1.5         0
# AND          [0, 1]     [1, 1]              1.5         0
# AND          [1, 0]     [1, 1]              1.5         0
# AND          [1, 1]     [1, 1]              1.5         1
# NOT          [0]        [-1]               -0.5         1
# NOT          [1]        [-1]               -0.5         0
# OR           [0, 0]     [1, 1]              0.5         0
# OR           [0, 1]     [1, 1]              0.5         1
# OR           [1, 0]     [1, 1]              0.5         1
# OR           [1, 1]     [1, 1]              0.5         1
# COMBINATION  [0, 0, 0]  [2, -2, 2]          1           0
# COMBINATION  [1, 0, 0]  [2, -2, 2]          1           1
# COMBINATION  [0, 1, 0]  [2, -2, 2]          1           0

[numpy-linear-relu.py]

"""
A simple implementation of linear layer followed by a
ReLU activation function.
"""

import numpy as np

dtype = "float32"

# numpy
a_np = np.random.rand(128, 128).astype(dtype)
b_np = np.random.rand(128, 128).astype(dtype)
# matmul -> relu
c_mm_relu = np.maximum(a_np @ b_np, 0)

# implementation
def mm_relu(A: np.ndarray, B: np.ndarray, C: np.ndarray):
    # A, B, C: 128x128
    Y = np.empty((128, 128), dtype=dtype)
    # matmul
    for i in range(128):
        for j in range(128):
            for k in range(128):
                if k == 0: Y[i, j] = 0
                Y[i, j] += A[i, k] * B[k, j]
    # relu
    for i in range(128):
        for j in range(128): C[i, j] = max(Y[i, j], 0)

# test
c_np = np.empty((128, 128), dtype=dtype)
mm_relu(a_np, b_np, c_np)
# check within tolerance
np.testing.assert_allclose(c_mm_relu, c_np, rtol=1e-5)

[widrow-hoff-learning-algorithm.py]

# https://www.cs.princeton.edu/courses/archive/spring13/cos511/scribe_notes/0411.pdf
import numpy as np
from tabulate import tabulate

# initial values
w = [1, 0, 0]
# margin vector
v = [1, 1, 1, 1, 1, 1]
# learning rate
n = 0.1
# iterations
iterations = 12

# dataset
X = [[0, 2], [1, 2], [2, 1], [-3, 1], [-2, 1], [-3, 2]]
Y = [[1, 0, 2], [1, 1, 2], [1, 2, 1], [-1, 3, -1], [-1, 2, 1], [-1, 3, 2]]

# sequential widrow-hoff learning algorithm
result = []
for o in range(int(iterations / len(Y))):
    for i in range(len(Y)):
        w_prev = w
        y = Y[i]
        # calculate wy
        wy = np.dot(w, y)
        # calculate update part
        update = np.zeros(len(y))
        for j in range(len(y)): update[j] = n * (v[i] - wy) * y[j]
        # add update part to a
        w = np.add(w, update)
        # append result
        result.append([
            # i
            i + 1 + (len(Y) * o),
            # w
            [round(x, 3) for x in w_prev],
            # y
            list(y),
            # wy
            round(wy, 3),
            # w_new
            [round(x, 3) for x in w]
        ])

print(tabulate(result, headers=['i', 'w', 'y', 'wy', 'w_new'], tablefmt="simple"))
#   i  w                       y                wy  w_new
# ---  ----------------------  -----------  ------  ----------------------
#   1  [1, 0, 0]               [1, 0, 2]     1      [1.0, 0.0, 0.0]
#   2  [1.0, 0.0, 0.0]         [1, 1, 2]     1      [1.0, 0.0, 0.0]
#   3  [1.0, 0.0, 0.0]         [1, 2, 1]     1      [1.0, 0.0, 0.0]
#   4  [1.0, 0.0, 0.0]         [-1, 3, -1]  -1      [0.8, 0.6, -0.2]
#   5  [0.8, 0.6, -0.2]        [-1, 2, 1]    0.2    [0.72, 0.76, -0.12]
#   6  [0.72, 0.76, -0.12]     [-1, 3, 2]    1.32   [0.752, 0.664, -0.184]
#   7  [0.752, 0.664, -0.184]  [1, 0, 2]     0.384  [0.814, 0.664, -0.061]
#   8  [0.814, 0.664, -0.061]  [1, 1, 2]     1.356  [0.778, 0.628, -0.132]
#   9  [0.778, 0.628, -0.132]  [1, 2, 1]     1.903  [0.688, 0.448, -0.222]
#  10  [0.688, 0.448, -0.222]  [-1, 3, -1]   0.878  [0.676, 0.484, -0.234]
#  11  [0.676, 0.484, -0.234]  [-1, 2, 1]    0.059  [0.581, 0.673, -0.14]
#  12  [0.581, 0.673, -0.14]   [-1, 3, 2]    1.156  [0.597, 0.626, -0.172]

euler^

#1-multiples-of-3-and-5.py#2-even-fibonacci-numbers.py#3-largest-prime-factor.py#4-largest-palindrome-product.py#5-smallest-multiple.py#6-sum-square-difference.py#7-10001st-prime.py#8-largest-product-in-a-series.py#9-special-pythagorean-triplet.py#10-summation-of-primes.py#11-largest-product-in-grid.py#12-highly-divisible-triangular-number.py#13-large-sum.py#14-longest-collatz-sequence.py#15-lattice-paths.py#16-power-digit-sum.py#17-number-letter-counts.py

[#1-multiples-of-3-and-5.py]

"""
Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples 
of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 
23.

Find the sum of all the multiples of 3 or 5 below 1000.

https://projecteuler.net/problem=1
"""

# solution
result = list()
for n in list(range(1000))[1:]:
    if n % 3 == 0 or n % 5 == 0: result.append(n)

print(sum(result)) # 233168

[#2-even-fibonacci-numbers.py]

# 2020-10

"""
Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by 
adding the previous two terms. By starting with 1 and 2, 
the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 
55, 89, ...

By considering the terms in the Fibonacci sequence whose 
values do not exceed four million, find the sum of the 
even-valued terms.

https://projecteuler.net/problem=2
"""

# test
# seq = list()
# for n in list(range(10)):
#     if n == 0:
#         seq.append(1)
#     if n == 1:
#         seq.append(2)
#     if n > 1:
#         seq.append(seq[n - 2] + seq[n - 1])

# assert(seq == list([1, 2, 3, 5, 8, 13, 21, 34, 55, 89]))

# solution
seq = list()
result = list()
max_value = 4000000
n = 0
while True:
    if n == 0:
        seq.append(1)
    if n == 1:
        seq.append(2)
    if n > 1:
        seq.append(seq[n - 2] + seq[n - 1])

    # break condition
    if seq[n] > max_value:
        seq.pop(n)
        break

    # even
    if seq[n] % 2 == 0:
        result.append(seq[n])

    n += 1

print(sum(result))
# 4613732

[#3-largest-prime-factor.py]

# 2020-10

"""
Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

https://projecteuler.net/problem=3
"""

# test
# number = 13195 
# result = list()

# factor = number - 1
# while factor > 1:
#     if number % factor == 0:
#         # factor
#         subfactor = factor - 1
#         while subfactor > 1:
#             if factor % subfactor == 0:
#                 break

#             subfactor -= 1

#         if subfactor == 1:
#             result.append(factor)

#     factor -= 1

# assert(max(result) == 29)

# solution (too slow)
# number = 600851475143
# result = list()

# factor = number - 1
# while factor > 1:
#   if number % factor == 0:
#       # factor
#       subfactor = factor - 1
#       while subfactor > 1:
#           if factor % subfactor == 0:
#               break

#           subfactor -= 1

#       if subfactor == 1:
#           print(factor)
#           result.append(factor)

#   factor -= 1

# print(max(result))

# solution (faster)
import math

number = 600851475143
result = list()

while number % 2 == 0:
    result.append(2)
    number = number / 2

for i in range(3, int(math.sqrt(number)) + 1, 2):
    while number % i == 0:
        result.append(i)
        number = number / i

if number > 2:
    result.append(number)

print(max(result))
# 6857

[#4-largest-palindrome-product.py]

# 2020-10

"""
Largest palindrome product

A palindromic number reads the same both ways. The 
largest palindrome made from the product of two 2-digit 
numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

https://projecteuler.net/problem=4
"""

# test
# MAX_2 = 100

# nlst = list(range(MAX_2))[80:]
# result = list()
# for i in nlst:
#     for j in nlst:
#         product = i * j
#         if list(str(product)) == list(str(product))[::-1]:
#             result.append(product)

# assert(max(result) == 9009)

# solution
MAX_2 = 1000

nlst = list(range(MAX_2))[800:]
result = list()
for i in nlst:
    for j in nlst:
        product = i * j
        if list(str(product)) == list(str(product))[::-1]:
            result.append(product)

print(max(result))
# 906609

[#5-smallest-multiple.py]

# 2020-10

"""
Smallest multiple

2520 is the smallest number that can be divided by 
each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly 
divisible by all of the numbers from 1 to 20?

https://projecteuler.net/problem=5
"""

# test
# MAX_ITER = 10000

# number = 1
# nlst = list(range(1, 11))
# result = -1
# while number < MAX_ITER:
#     divisible = True

#     for n in nlst:
#         if number % n != 0:
#             divisible = False
#             break

#     if divisible:
#         result = number
#         break

#     number += 1

# assert(result == 2520)

# solution
MAX_ITER = 1000000000

number = 1
nlst = list(range(11, 21))
result = -1
while number < MAX_ITER:
    divisible = True

    for n in nlst:
        if number % n != 0:
            divisible = False
            break

    if divisible:
        result = number
        break

    number += 1

print(result)
# 232792560

[#6-sum-square-difference.py]

# 2020-11

"""
Sum square difference

The sum of the squares of the first ten natural numbers 
is, 1^2 + 2^2 + ... + 10^2 = 385.

The square of the sum of the first ten natural numbers 
is, (1 + 2 + ... + 10^2) = 55^2 = 3025.

Hence the difference between the sum of the squares of 
the first ten natural numbers and the square of the sum 
is 3025 - 385 = 2640.

Find the difference between the sum of the squares of the 
first one hundred natural numbers and the square of the sum.

https://projecteuler.net/problem=6
"""

# test
# nlist = list(range(1, 11))

# sum_square = 0
# for n in nlist:
#     sum_square += (n ** 2)

# square_sum = sum(nlist) ** 2

# assert(square_sum - sum_square == 2640)

# solution
nlist = list(range(1, 101))

sum_square = 0
for n in nlist:
    sum_square += (n ** 2)

square_sum = sum(nlist) ** 2

print(square_sum - sum_square)
# 25164150

[#7-10001st-prime.py]

# 2020-10

"""
10001st prime

By listing the first six prime numbers: 2, 3, 5, 7,
11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

# https://projecteuler.net/problem=7
"""

import numpy as np

# test (too slow)

# algorithm:
# π(n) = (sum from j=2 to n) [ ((j-1)! + 1)/j - [(j-1)!/j] ]
# nth prime = 1 + (sum from m=1 to j=2 ** n) [ [ n/(1 + π(m)) ]1/n ]
# [x] is floor function

# def pi(n):
#   pi_n = 0
#   for j in range(n + 1):
#       if j < 2:
#           pass
#       else:
#           pi_n += math.floor(((math.factorial(j - 1) + 1) // j) - math.floor(math.factorial(j - 1) // j))

#   return pi_n

# def n_prime(n):
#   n_prime = 0
#   for m in range(2 ** n + 1):
#       if m < 1:
#           pass
#       else:
#           n_prime += math.floor(math.floor(n // (1 + pi(m))) ** (1 / n))
#   n_prime += 1
#   return n_prime

# assert(n_prime(6) == 13)

# solution

MAX_SIZE = 1000000

# sieve of eratosthenes
def SOE(primelst):
    is_prime = np.ones(MAX_SIZE)

    prime = 2
    while (prime * prime) < MAX_SIZE:
        if is_prime[prime] == True:
            i = (prime * prime)
            while i < MAX_SIZE:
                is_prime[i] = 0
                i += prime
        prime += 1

    prime = 2
    while prime < MAX_SIZE:
        if is_prime[prime]:
            primelst.append(prime)

        prime += 1

    return primelst

result = SOE([])

n = 10001
print(result[n - 1])
# 104743

[#8-largest-product-in-a-series.py]

# 2020-11

"""
Largest product in a series

The four adjacent digits in the 1000-digit number that 
have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit 
number that have the greatest product. What is the
value of this product?

https://projecteuler.net/problem=8
"""

import numpy as np

str = '''
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
'''

nlist = list(''.join(str.strip().split('\n')))
nlist = list(map(int, nlist))

# test
# adj_digits = 4
# max_product = 0
# for i in range(len(nlist)):
#     if (i + adj_digits > len(nlist)):
#         break
#     product = np.prod(nlist[i:i+adj_digits])
#     if product > max_product:
#         max_product = product

# assert(max_product == 5832)

# solution
adj_digits = 13
max_product = 0
for i in range(len(nlist)):
    if (i + adj_digits > len(nlist)):
        break
    product = np.prod(nlist[i:i+adj_digits])
    if product > max_product:
        max_product = product

print(max_product)
# 23514624000

[#9-special-pythagorean-triplet.py]

# 2020-11

"""
Special Pythagorean triplet

A Pythagorean triplet is a set of three 
natural numbers, a < b < c, for which,
a^2 + b^2 = c^2.

For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet 
for which a + b + c = 1000. Find the product 
abc.

https://projecteuler.net/problem=9
"""

import numpy as np

# it is not pretty, but it works
MAX_N = 500
def brute(MAX_N):
    for a in range(MAX_N):
        for b in range(MAX_N):
            for c in range(MAX_N):
                if (a < b and b < c) and (a ** 2 + b ** 2 == c ** 2) and (a + b + c == 1000):
                    return (a, b, c), a * b * c

    return 0

triplet, result = brute(MAX_N)

print(triplet)
# (200, 375, 425)
print(result)
# 31875000

[#10-summation-of-primes.py]

"""
Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

https://projecteuler.net/problem=10
"""

import numpy as np

# sieve of eratosthenes
def SOE(primelst, MAX_SIZE=10):
    is_prime = np.ones(MAX_SIZE)

    prime = 2
    while (prime * prime) < MAX_SIZE:
        if is_prime[prime] == True:
            i = (prime * prime)
            while i < MAX_SIZE:
                is_prime[i] = 0
                i += prime
        prime += 1

    prime = 2
    while prime < MAX_SIZE:
        if is_prime[prime]: primelst.append(prime)
        prime += 1

    return primelst

assert(sum(SOE([], 10)) == 17)

result = SOE([], 2000000)
print(sum(result)) # 142913828922

[#11-largest-product-in-grid.py]

"""
Largest product in grid

In the 20x20 grid below, four numbers along a diagonal line
have been marked in red.

The product of these numbers is 26 * 63 * 78 * 14 = 1788696.

What is the greatest product of four adjacent numbers in the 
same direction (up, down, left, right, or diagonally) in the 
20x20 grid?

https://projecteuler.net/problem=11
"""

import numpy as np

# solution
GRID = [
    ['08', '02', '22', '97', '38', '15', '00', '40', '00', '75', '04', '05', '07', '78', '52', '12', '50', '77', '91', '08'],
    ['49', '49', '99', '40', '17', '81', '18', '57', '60', '87', '17', '40', '98', '43', '69', '48', '04', '56', '62', '00'],
    ['81', '49', '31', '73', '55', '79', '14', '29', '93', '71', '40', '67', '53', '88', '30', '03', '49', '13', '36', '65'],
    ['52', '70', '95', '23', '04', '60', '11', '42', '69', '24', '68', '56', '01', '32', '56', '71', '37', '02', '36', '91'],
    ['22', '31', '16', '71', '51', '67', '63', '89', '41', '92', '36', '54', '22', '40', '40', '28', '66', '33', '13', '80'],
    ['24', '47', '32', '60', '99', '03', '45', '02', '44', '75', '33', '53', '78', '36', '84', '20', '35', '17', '12', '50'],
    ['32', '98', '81', '28', '64', '23', '67', '10', '26', '38', '40', '67', '59', '54', '70', '66', '18', '38', '64', '70'],
    ['67', '26', '20', '68', '02', '62', '12', '20', '95', '63', '94', '39', '63', '08', '40', '91', '66', '49', '94', '21'],
    ['24', '55', '58', '05', '66', '73', '99', '26', '97', '17', '78', '78', '96', '83', '14', '88', '34', '89', '63', '72'],
    ['21', '36', '23', '09', '75', '00', '76', '44', '20', '45', '35', '14', '00', '61', '33', '97', '34', '31', '33', '95'],
    ['78', '17', '53', '28', '22', '75', '31', '67', '15', '94', '03', '80', '04', '62', '16', '14', '09', '53', '56', '92'],
    ['16', '39', '05', '42', '96', '35', '31', '47', '55', '58', '88', '24', '00', '17', '54', '24', '36', '29', '85', '57'],
    ['86', '56', '00', '48', '35', '71', '89', '07', '05', '44', '44', '37', '44', '60', '21', '58', '51', '54', '17', '58'],
    ['19', '80', '81', '68', '05', '94', '47', '69', '28', '73', '92', '13', '86', '52', '17', '77', '04', '89', '55', '40'],
    ['04', '52', '08', '83', '97', '35', '99', '16', '07', '97', '57', '32', '16', '26', '26', '79', '33', '27', '98', '66'],
    ['88', '36', '68', '87', '57', '62', '20', '72', '03', '46', '33', '67', '46', '55', '12', '32', '63', '93', '53', '69'],
    ['04', '42', '16', '73', '38', '25', '39', '11', '24', '94', '72', '18', '08', '46', '29', '32', '40', '62', '76', '36'],
    ['20', '69', '36', '41', '72', '30', '23', '88', '34', '62', '99', '69', '82', '67', '59', '85', '74', '04', '36', '16'],
    ['20', '73', '35', '29', '78', '31', '90', '01', '74', '31', '49', '71', '48', '86', '81', '16', '23', '57', '05', '54'],
    ['01', '70', '54', '71', '83', '51', '54', '69', '16', '92', '33', '48', '61', '43', '52', '01', '89', '19', '67', '48']
]
GRID = np.array(GRID).astype(int)

WINDOW_SIZE = 4

# largest product
def largest_product(GRID):
    max_product = 0

    for i in range(GRID.shape[0] - (WINDOW_SIZE - 1)):
        for j in range(GRID.shape[1] - (WINDOW_SIZE - 1)):
            window = np.array(GRID[i:WINDOW_SIZE + i, j:WINDOW_SIZE + j])
            windowT = window.T
            # print(window)
            # print(windowT)

            products = []
            # rows and columns
            for n in range(window.shape[0]):
                # rows
                products.append(np.prod(window[n]))
                # columns
                products.append(np.prod(windowT[n]))

            # diagonal
            diagonal = []
            for n in range(window.shape[0]):
                diagonal.append(window[n][n])
            products.append(np.prod(diagonal))

            # diagonal: reversed
            diagonal_reversed = []
            for n in range(windowT.shape[0]):
                diagonal_reversed.append(window[(WINDOW_SIZE - 1) - n][n])
            products.append(np.prod(diagonal_reversed))

            # window max product
            window_max = max(products)
            if window_max > max_product:
                max_product = window_max

    return max_product

result = largest_product(GRID)
print(result) # 70600674

[#12-highly-divisible-triangular-number.py]

"""
Highly divisible triangular number

The sequence of triangle numbers is generated by adding the natural numbers. So the 
7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms 
would be: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1  : 1
3  : 1,3
6  : 1,2,3,6
10 : 1,2,5,10
15 : 1,3,5,15
21 : 1,3,7,21
28 : 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

https://projecteuler.net/problem=12
"""

def triangle_number(number): return sum(list(range(number + 1)))

# test (slow)

def factors(factor_lst, number):
    # append known factors
    factor_lst.append(number)
    factor_lst.append(number / 2)
    factor_lst.append(1)
    # set first factor (no factor larger than number / 2)
    factor = number / 2 - 1
    while factor > 1:
        if number % factor == 0: factor_lst.append(factor)
        factor -= 1
    return len(factor_lst)

assert triangle_number(7) == 28
assert factors([], 28) == 6

# solution

import math

def factors_fast(factor_lst, n):
    factor = 1
    while factor <= math.sqrt(n):
        if n % factor == 0:
            if n / factor == factor: factor_lst.append(factor)
            else:
                factor_lst.append(factor)
                factor_lst.append(int(n / factor))
        factor = factor + 1
    return len(factor_lst)

assert factors_fast([], 28) == 6

MAX_RANGE = 15000
MIN_LEN = 500

result = 0

for n in range(MAX_RANGE):
    tn = triangle_number(n)
    f = factors_fast([], tn)
    if f > MIN_LEN:
        result = tn, f
        break

print(result[0])
# 76576500

[#13-large-sum.py]

# 2022-07

"""
Large sum

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

https://projecteuler.net/problem=13
"""

numbers = """37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
64906352462741904929101432445813822663347944758178
92575867718337217661963751590579239728245598838407
58203565325359399008402633568948830189458628227828
80181199384826282014278194139940567587151170094390
35398664372827112653829987240784473053190104293586
86515506006295864861532075273371959191420517255829
71693888707715466499115593487603532921714970056938
54370070576826684624621495650076471787294438377604
53282654108756828443191190634694037855217779295145
36123272525000296071075082563815656710885258350721
45876576172410976447339110607218265236877223636045
17423706905851860660448207621209813287860733969412
81142660418086830619328460811191061556940512689692
51934325451728388641918047049293215058642563049483
62467221648435076201727918039944693004732956340691
15732444386908125794514089057706229429197107928209
55037687525678773091862540744969844508330393682126
18336384825330154686196124348767681297534375946515
80386287592878490201521685554828717201219257766954
78182833757993103614740356856449095527097864797581
16726320100436897842553539920931837441497806860984
48403098129077791799088218795327364475675590848030
87086987551392711854517078544161852424320693150332
59959406895756536782107074926966537676326235447210
69793950679652694742597709739166693763042633987085
41052684708299085211399427365734116182760315001271
65378607361501080857009149939512557028198746004375
35829035317434717326932123578154982629742552737307
94953759765105305946966067683156574377167401875275
88902802571733229619176668713819931811048770190271
25267680276078003013678680992525463401061632866526
36270218540497705585629946580636237993140746255962
24074486908231174977792365466257246923322810917141
91430288197103288597806669760892938638285025333403
34413065578016127815921815005561868836468420090470
23053081172816430487623791969842487255036638784583
11487696932154902810424020138335124462181441773470
63783299490636259666498587618221225225512486764533
67720186971698544312419572409913959008952310058822
95548255300263520781532296796249481641953868218774
76085327132285723110424803456124867697064507995236
37774242535411291684276865538926205024910326572967
23701913275725675285653248258265463092207058596522
29798860272258331913126375147341994889534765745501
18495701454879288984856827726077713721403798879715
38298203783031473527721580348144513491373226651381
34829543829199918180278916522431027392251122869539
40957953066405232632538044100059654939159879593635
29746152185502371307642255121183693803580388584903
41698116222072977186158236678424689157993532961922
62467957194401269043877107275048102390895523597457
23189706772547915061505504953922979530901129967519
86188088225875314529584099251203829009407770775672
11306739708304724483816533873502340845647058077308
82959174767140363198008187129011875491310547126581
97623331044818386269515456334926366572897563400500
42846280183517070527831839425882145521227251250327
55121603546981200581762165212827652751691296897789
32238195734329339946437501907836945765883352399886
75506164965184775180738168837861091527357929701337
62177842752192623401942399639168044983993173312731
32924185707147349566916674687634660915035914677504
99518671430235219628894890102423325116913619626622
73267460800591547471830798392868535206946944540724
76841822524674417161514036427982273348055556214818
97142617910342598647204516893989422179826088076852
87783646182799346313767754307809363333018982642090
10848802521674670883215120185883543223812876952786
71329612474782464538636993009049310363619763878039
62184073572399794223406235393808339651327408011116
66627891981488087797941876876144230030984490851411
60661826293682836764744779239180335110989069790714
85786944089552990653640447425576083659976645795096
66024396409905389607120198219976047599490197230297
64913982680032973156037120041377903785566085089252
16730939319872750275468906903707539413042652315011
94809377245048795150954100921645863754710598436791
78639167021187492431995700641917969777599028300699
15368713711936614952811305876380278410754449733078
40789923115535562561142322423255033685442488917353
44889911501440648020369068063960672322193204149535
41503128880339536053299340368006977710650566631954
81234880673210146739058568557934581403627822703280
82616570773948327592232845941706525094512325230608
22918802058777319719839450180888072429661980811197
77158542502016545090413245809786882778948721859617
72107838435069186155435662884062257473692284509516
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690"""

result = 0

for line in numbers.split('\n'):
    result = result + int(line[0:12])

print(str(result)[0:10])
# 5537376230

[#14-longest-collatz-sequence.py]

# 2022-07

"""
Longest Collatz sequence

The following iterative sequence is defined for the set of positive integers:

  n -> n / 2 (n is even)
  n -> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

  13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 
10 terms. Although it has not been proved yet (Collatz Problem), it is thought 
that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

https://projecteuler.net/problem=14
"""

def collatz(seq_lst, n):
    # append starting value
    seq_lst.append(int(n))
    while n > 1:
        # even
        if n % 2 == 0:
            n = n / 2
            seq_lst.append(int(n))
        # odd
        else:
            n = 3 * n + 1
            seq_lst.append(int(n))

    return seq_lst

assert collatz([], 13) == [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

# solution (slow)

MAX_RANGE = 1000000

longest = (0, 0)

for n in range(MAX_RANGE):
    seq = collatz([], n)
    if len(seq) > longest[1]:
        longest = (n, len(seq))

print(longest[0])
# 837799

[#15-lattice-paths.py]

# 2022-07

"""
Lattice paths

Starting in the top left corner of a 2×2 grid, and only being able to 
move to the right and down, there are exactly 6 routes to the bottom 
right corner.

How many such routes are there through a 20×20 grid?

https://projecteuler.net/problem=15
"""

import numpy as np

"""
pascal triangle (2x2 -> 3x3 grid line): 6 paths
1 1 1
1 2 3
1 3 6

pascal triangle (3x3 -> 4x4 grid line) : 20 paths
1 1  1  1
1 2  3  4
1 3  6 10
1 4 10 20
"""

# https://en.wikipedia.org/wiki/Pascal%27s_triangle
def pascal_triangle(size):
    grid = np.ones((size, size))
    for i in range(size):
        if i > 0:
            for j in range(size):
                if j > 0:
                    grid[i][j] = grid[i - 1][j] + grid[i][j - 1]
    return grid

assert int(pascal_triangle(3)[2][2]) == 6
assert int(pascal_triangle(4)[3][3]) == 20

print(int(pascal_triangle(21)[20][20]))
# 137846528820

[#16-power-digit-sum.py]

# 2022-07

"""
Power digit sum

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?

https://projecteuler.net/problem=16
"""

def pow_sum(n, p):
    return sum(list(map(int, list(str(n ** p)))))

assert pow_sum(2, 15) == 26

print(pow_sum(2, 1000))
# 1366

[#17-number-letter-counts.py]

# 2022-07

"""
Number letter counts

If the numbers 1 to 5 are written out in words: one, two, three,
four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in
total.

If all the numbers from 1 to 1000 (one thousand) inclusive were
written out in words, how many letters would be used?

https://projecteuler.net/problem=17
"""

words = {
    1: 'one',
    2: 'two',
    3: 'three',
    4: 'four',
    5: 'five',
    6: 'six',
    7: 'seven',
    8: 'eight',
    9: 'nine',
    10: 'ten',
    11: 'eleven',
    12: 'twelve',
    13: 'thirteen',
    14: 'fourteen',
    15: 'fifteen',
    16: 'sixteen',
    17: 'seventeen',
    18: 'eighteen',
    19: 'nineteen',
    20: 'twenty',
    30: 'thirty',
    40: 'forty',
    50: 'fifty',
    60: 'sixty',
    70: 'seventy',
    80: 'eighty',
    90: 'ninety',
    100: 'hundred',
    1000: 'thousand'
}

def parse_number(word_lst, n):
    number = str(n)
    size = len(number) - 1
    for i in range(len(number)):
        digit = number[i]
        # convert to teens
        if size == 1 and int(digit + number[i + 1]) in words:
            if i > 0: word_lst.append('and')
            word_lst.append(words[int(digit + number[i + 1])])
            break
        # convert to tens
        elif size == 1 and int(digit + '0') in words:
            if i > 0: word_lst.append('and')
            word_lst.append(words[int(digit + '0')])
        else:
            if int(digit) > 0:
                word_lst.append(words[int(digit)])
        # thousands
        if size == 3:
            word_lst.append(words[1000])
            break
        # hundreds
        if size == 2:
            word_lst.append(words[100])
        size -= 1
    return word_lst

assert parse_number([], 342) == ['three', 'hundred', 'and', 'forty', 'two']
assert parse_number([], 115) == ['one', 'hundred', 'and', 'fifteen']

assert sum(list(map(len, parse_number([], 342)))) == 23
assert sum(list(map(len, parse_number([], 115)))) == 20

# numbers = []
letters = 0
n = 1
while n < len(range(1000)) + 1:
    # number = parse_number([], n)
    # numbers.append(number)
    letters += sum(list(map(len, parse_number([], n))))
    n += 1

print(letters)
# 21124

compilers^

ast-constant-folding.pyast-to-tac-to-llvm.pydsl-in-python.pyfor-loop-implementation.pyloop-tiling-optimization.pyopencl-in-python.pyoperator-fusion-on-parse-tree.pyparallelization-optimization.pyshunting-yard-algorithm.pytokenizer-using-generator-in-python.pyvectorization-optimization.py

[ast-constant-folding.py]

"""
Constant folding is a form of partial evaluation
that can be applied to constant expressions to
reduce the number of instructions in generated
code.
"""

import ast

program = """
x = 5
y = 10
z = x + y * 2
print(z)
"""

variables = {}

tree = ast.parse(program)
# print(len(ast.dump(tree)))
# 449

folded_tree = ast.Module(body=[], type_ignores=[])

# walk ast
for node in ast.walk(tree):
    if isinstance(node, ast.Assign):
        if isinstance(node.targets[0], ast.Name):
            if isinstance(node.value, ast.Num):
                variables[node.targets[0].id] = node.value.n
            else:
                folded_tree.body.append(node)
    if isinstance(node, ast.BinOp):
        if isinstance(node.left, ast.Name) and node.left.id in variables:
            node.left = ast.Num(n=variables[node.left.id])
        elif isinstance(node.right, ast.Name) and node.right.id in variables:
            node.right = ast.Num(n=variables[node.right.id])
        else:
            folded_tree.body.append(node)
    if isinstance(node, ast.Expr):
        folded_tree.body.append(node)

# print(variables)
# print(ast.dump(folded_tree))
# print(len(ast.dump(folded_tree)))
# 295

# fix missing locations
ast.fix_missing_locations(folded_tree)

# compile and execute folded tree
exec(compile(folded_tree, filename="<ast>", mode="exec"))
# 25

[ast-to-tac-to-llvm.py]

"""
AST is tree representation of source code
TAC is linear representation of ASTs
LLVM IR is linear representation of the TAC
"""

from mako.template import Template

def gen_tac(ast, tmp_counter):
    if isinstance(ast, int):
        return f"t{tmp_counter} = {ast}", f"t{tmp_counter}", tmp_counter + 1
    elif isinstance(ast, list):
        op = ast[0]
        left, left_var, tmp_counter = gen_tac(ast[1], tmp_counter)
        right, right_var, tmp_counter = gen_tac(ast[2], tmp_counter)
        tmp_var = f"t{tmp_counter}"
        result = f"{tmp_var} = {left_var} {op} {right_var}"
        return f"{left}\n{right}\n{result}", tmp_var, tmp_counter + 1
    else:
        raise Exception("unknown node")

def tac_to_llvm(tac):
    code = []
    var_map = {}

    code.append("define i32 @main(i32) {")

    for line in tac.strip().split('\n'):
        parts = line.split(' ')
        destination_var = parts[0]
        operation = parts[1]
        operands = parts[2:]

        if len(parts) == 3 and operation == '=':
            if operands and operands[0].isdigit():
                code.append(f"\t%{destination_var} = add i32 {operands[0]}, 0")
            else:
                code.append(f"\t%{destination_var} = add i32 %{var_map[operands[0]]}, 0")
            var_map[destination_var] = destination_var
        else:
            # replace assignment with operation
            operation = parts[3]
            if operands[0].isdigit():
                op1 = f"{operands[0]}"
            else:
                op1 = f"%{var_map[operands[0]]}"
            if operands[2].isdigit():
                op2 = f"{operands[2]}"
            else:
                op2 = f"%{var_map[operands[2]]}"

            if operation == '+':
                code.append(f"\t%{destination_var} = add i32 {op1}, {op2}")
            elif operation == '-':
                code.append(f"\t%{destination_var} = sub i32 {op1}, {op2}")
            elif operation == '*':
                code.append(f"\t%{destination_var} = mul i32 {op1}, {op2}")
            elif operation == '/':
                code.append(f"\t%{destination_var} = sdiv i32 {op1}, {op2}")
            else:
                raise ValueError(f"Unsupported operation: {operation}")

            var_map[destination_var] = destination_var

    code.append(f"\tret i32 %{var_map[destination_var]}")
    code.append("}")

    return '\n'.join(code)

ast = ["+", 2, ["*", 3, 4]]
tac = gen_tac(ast, 1)[0]
# t1 = 2
# t2 = 3
# t3 = 4
# t4 = t2 * t3
# t5 = t1 + t4

print(tac_to_llvm(tac))
# define i32 @main(i32) {
#     %t1 = add i32 2, 0
#     %t2 = add i32 3, 0
#     %t3 = add i32 4, 0
#     %t4 = mul i32 %t2, %t3
#     %t5 = add i32 %t1, %t4
#     ret i32 %t5
# }

[dsl-in-python.py]

"""
This is how to design and use embedded
domain-specific languages in Python.
"""

import sys

"""
functions
    add     : sum all arguments
    sub     : subtract tail from head
types
    int
    float
arguments
    out     : stdin to use previous output as input
            : stdout to print
"""
program = """
Module add 1 2 3 type=float out=stdin
Module sub stdin 1 2 type=int out=stdout
"""

# Module definition
class Module:
    # Add function
    def add(*args, **kwargs):
        type_ = globals()["__builtins__"].getattr(globals()["__builtins__"], kwargs["type"])
        return sum(map(type_, args))
    # Sub function
    def sub(*args, **kwargs):
        type_ = globals()["__builtins__"].getattr(globals()["__builtins__"], kwargs["type"])
        return float(args[0]) if type_ == 'float' else int(args[0]) - sum(map(type_, args[1:]))

def get_args(tokens, STDIN):
    args = []
    kwargs = {}
    for token in tokens:
        # kwargs
        if '=' in token:
            k, v = token.split('=', 1)
            kwargs[k] = v
        # args
        else:
            # replace stdin with previous output
            if token == "stdin":
                if STDIN != "": args.append(STDIN)
                else: raise Exception("no previous output")
            else:
                args.append(token)
    return args, kwargs

def interpret(program):
    STDIN = ""
    lines = [line for line in program.splitlines() if line]
    # print(lines)
    # ['Module add 1 2 3 type=float out=stdin', 'Module sub stdin 1 2 type=int out=stdout']

    for line in lines:
        tokens = line.split()
        args, kwargs = get_args(tokens[2:], STDIN)

        # print(args, kwargs)
        # ['1', '2', '3'] {'type': 'float', 'out': 'stdin'}
        # [6.0, '1', '2'] {'type': 'int', 'out': 'stdout'}

        # print(getattr(sys.modules[__name__], tokens[0]))
        # <class '__main__.Module'>
        # <class '__main__.Module'>

        # print(getattr(getattr(sys.modules[__name__], tokens[0]), tokens[1]))
        # <function Module.add at 0x1024545e0>
        # <function Module.sub at 0x108ed9620>

        result = getattr(getattr(sys.modules[__name__], tokens[0]), tokens[1])(*args, **kwargs)
        if "out" in kwargs:
            if kwargs["out"] == "stdin": STDIN = result
            if kwargs["out"] == "stdout": print(result)

interpret(program) # 3

[for-loop-implementation.py]

import timeit

def not_for_loop(index = 0, elements = [], operation = None):
    if index < len(elements):
        if operation is not None:
            elements[index] = operation(elements[index])

        not_for_loop(index + 1, elements, operation)

    return elements

def for_loop_using_while(elements = [], operation = None):
    index = 0
    while index < len(elements):
        if operation is not None:
            elements[index] = operation(elements[index])
        index += 1

    return elements

def for_loop(elements = [], operation = None):
    for index in range(len(elements)):
        elements[index] = operation(elements[index])

    return elements

# print(not_for_loop(0, [1, 2, 3, 4, 5], lambda x: x.__add__(1)))
# print(for_loop_using_while([1, 2, 3, 4, 5], lambda x: x.__add__(1)))
# print(for_loop([1, 2, 3, 4, 5], lambda x: x.__add__(1)))

assert not_for_loop(0, [1, 2, 3, 4, 5], lambda x: x.__add__(1)) == [2, 3, 4, 5, 6]
assert for_loop_using_while([1, 2, 3, 4, 5], lambda x: x.__add__(1)) == [2, 3, 4, 5, 6]
assert for_loop([1, 2, 3, 4, 5], lambda x: x.__add__(1)) == [2, 3, 4, 5, 6]

print(timeit.timeit('not_for_loop(0, [1, 2, 3, 4, 5], lambda x: x.__add__(1))', setup = 'from __main__ import not_for_loop', number = 100000))
# 0.10954952286556363
print(timeit.timeit('for_loop_using_while([1, 2, 3, 4, 5], lambda x: x.__add__(1))', setup = 'from __main__ import for_loop_using_while', number = 100000))
# 0.08992556994780898
print(timeit.timeit('for_loop([1, 2, 3, 4, 5], lambda x: x.__add__(1))', setup = 'from __main__ import for_loop', number = 100000))
# 0.08654258819296956

[loop-tiling-optimization.py]

"""
Loop tiling optimization is a technique used
to improve cache efficiency in nested loops.
"""

import random
import timeit

# timeit.template = """
# def inner(_it, _timer{init}):
#     from tqdm import tqdm
#     {setup}
#     _t0 = _timer()
#     for _i in tqdm(_it, total=_it.__length_hint__()):
#         {stmt}
#     _t1 = _timer()
#     return _t1 - _t0
# """

# matrix multiplication
def matmul(A, B):
    m, n, p = len(A), len(A[0]), len(B[0])
    result = [[0 for _ in range(p)] for _ in range(m)]

    for i in range(m):
        for j in range(p):
            for k in range(n):
                result[i][j] += A[i][k] * B[k][j]

    return result

A = [[1, 2, 3],[4, 5, 6],[7, 8, 9]]
B = [[9, 8, 7],[6, 5, 4],[3, 2, 1]]

assert matmul(A, B) == [[30, 24, 18], [84, 69, 54], [138, 114, 90]]

# tiling
TILE_SIZE = 100
def matmul_tiled(A, B):
    m, n, p = len(A), len(A[0]), len(B[0])
    result = [[0 for _ in range(p)] for _ in range(m)]

    for i in range(0, m, TILE_SIZE):
        for j in range(0, p, TILE_SIZE):
            for k in range(0, n, TILE_SIZE):
                for ii in range(i, min(i + TILE_SIZE, m)):
                    for jj in range(j, min(j + TILE_SIZE, p)):
                        for kk in range(k, min(k + TILE_SIZE, n)):
                            result[ii][jj] += A[ii][kk] * B[kk][jj]

    return result

assert matmul_tiled(A, B) == [[30, 24, 18], [84, 69, 54], [138, 114, 90]]

A = [[random.random() for _ in range(200)] for _ in range(200)]
B = [[random.random() for _ in range(200)] for _ in range(200)]

print(timeit.timeit(lambda: matmul(A, B), number=10))
# 6.854414212051779
print(timeit.timeit(lambda: matmul_tiled(A, B), number=10)) # CPU
# 6.588905839016661

[opencl-in-python.py]

"""
OpenCL can be used to run code on GPUs and other
accelerators. It's a C API (kernel code looks like 
C code) and pyopencl is a Python wrapper.
"""

import pyopencl as cl
import numpy as np
import timeit

# init opencl
platform = cl.get_platforms()[0]
device = platform.get_devices()[2] # AMD Radeon Pro 5500M Compute Engine
context = cl.Context([device])
queue = cl.CommandQueue(context)

# print(platform.get_info(cl.platform_info.NAME))
print(platform.get_info(cl.platform_info.VERSION))
# OpenCL 1.2 (Mar  4 2023 12:44:39)
print(device.get_info(cl.device_info.NAME))
# AMD Radeon Pro 5500M Compute Engine

# init data
size = 1000000000

# create arrays
a = np.random.rand(size).astype(np.float32)
b = np.random.rand(size).astype(np.float32)
result = np.zeros(size).astype(np.float32)

# opencl kernel
kernel_code = """
__kernel void add(__global float *a, __global float *b, __global float *result, int size) {
    int idx = get_global_id(0);
    if (idx < size) {
        result[idx] = a[idx] + b[idx];
    }
}
"""
# compile kernel
program = cl.Program(context, kernel_code).build()
# create buffers
a_buffer = cl.Buffer(context, cl.mem_flags.READ_ONLY | cl.mem_flags.COPY_HOST_PTR, hostbuf=a)
b_buffer = cl.Buffer(context, cl.mem_flags.READ_ONLY | cl.mem_flags.COPY_HOST_PTR, hostbuf=b)
result_buffer = cl.Buffer(context, cl.mem_flags.WRITE_ONLY, result.nbytes)

# opencl result
def run_opencl():
    # execute kernel
    program.add(queue, a.shape, None, a_buffer, b_buffer, result_buffer, np.int32(size))
    # copy result
    cl.enqueue_copy(queue, result, result_buffer)

# numpy result to compare with
numpy_result = np.zeros(size).astype(np.float32)
def run_numpy():
    global numpy_result
    numpy_result = a + b

print(timeit.timeit('run_numpy', globals=globals(), number=1))
# 1.0561197996139526e-06
print(timeit.timeit('run_opencl', globals=globals(), number=1))
# 5.420297384262085e-07

assert np.allclose(result, numpy_result)

# free memory
a_buffer.release()
b_buffer.release()
result_buffer.release()
# close opencl
del context
del queue
del program

[operator-fusion-on-parse-tree.py]

"""
Operator fusion is a technique to combine or rearrange
consecutive operations in a parse tree to improve
efficiency of code execution.
"""

def simplify_parse_tree(tree):
    if (isinstance(tree, tuple)):
        # first value in tuple, remaining values in tuple
        operator, *operands = tree
        operands = [simplify_parse_tree(operand) for operand in operands]

        if all(isinstance(operand, int) for operand in operands):
            if operator == '+':
                return sum(operands)
            elif operator == '*':
                return eval('*'.join(map(str, operands)))

    return tree

# (1 + 2) * (3 + 4)
parse_tree = ('*', ('+', 1, 2), ('+', 3, 4))
print(simplify_parse_tree(parse_tree)) # 21

compiled = compile('(1 + 2) * (3 + 4)', '<string>', 'eval')
print(compiled.co_consts[0]) # 21

assert simplify_parse_tree(parse_tree) == compiled.co_consts[0]

[parallelization-optimization.py]

"""
Parallelization optimization is a form of optimization
that aims to improve program performance by parallelizing
it, i.e. by splitting the program into smaller parts that
can be executed at the same time.
"""

import multiprocessing as mp
import timeit

# timeit.template = """
# def inner(_it, _timer{init}):
#     from tqdm import tqdm
#     {setup}
#     _t0 = _timer()
#     for _i in tqdm(_it, total=_it.__length_hint__()):
#         {stmt}
#     _t1 = _timer()
#     return _t1 - _t0
# """

def sum_of_squares(numbers):
    return sum([num * num for num in numbers])

def sum_of_squares_parallel(numbers):
    # use all available cores
    num_processes = mp.cpu_count()
    chunk_size = len(numbers) // num_processes
    # create pool of processes
    pool = mp.Pool(processes=num_processes)
    # divide work into chunks
    chunks = [numbers[i:i + chunk_size] for i in range(0, len(numbers), chunk_size)]
    results = pool.map(sum_of_squares, chunks)
    # close
    pool.close()
    # combine results
    pool.join()

    return sum(results)

if __name__ == '__main__':
    assert sum_of_squares(list(range(1, 10000))) == sum_of_squares_parallel(list(range(1, 10000)))
    # timeit
    n = list(range(1, 10000000))
    print(f"sum_of_squares: {timeit.timeit(lambda: sum_of_squares(n), number=10)}")
    # sum_of_squares: 7.48474136996083
    print(f"sum_of_squares_parallel: {timeit.timeit(lambda: sum_of_squares_parallel(n), number=10)}")
    # sum_of_squares_parallel: 6.641842097043991

[shunting-yard-algorithm.py]

# https://en.wikipedia.org/wiki/Shunting-yard_algorithm
PRECEDENCE = { 'func': 3, '^': 2, '/': 1, '*': 1, '+': 0, '-': 0 }

def parse(input_):
    operator = []
    output = []
    tokens = list(input_)
    while len(tokens) > 0:
        char = tokens[0]
        # number
        if char.isnumeric(): output.append(char)
        # function
        if char.isalpha():
            function = [char]
            i = 1
            while tokens[i].isalpha():
                function.append(tokens[i])
                i += 1
            operator.append(('func', ''.join(function)))
            # advance
            tokens = tokens[i - 1:]
        # operator
        if char in ['+', '-', '*', '/', '^']:
            # precedence
            while len(operator) > 0:
                op = operator.pop()
                if op[0] == 'func':
                    output.append(op[1])
                elif op not in ['(', '^'] and (op in PRECEDENCE and PRECEDENCE[op] >= PRECEDENCE[char]):
                    output.append(op)
                else:
                    # break
                    operator.append(op)
                    break
            operator.append(char)
        # left parenthesis
        if char == '(': operator.append(char)
        # right parenthesis
        if char == ')':
            if '(' not in operator: print("Error: Mismatched parentheses")
            while len(operator) > 0:
                op = operator.pop()
                if op[0] == 'func': output.append(op[1])
                elif op != '(': output.append(op)
                else: break
        tokens = tokens[1:]
    # pop operators
    while len(operator) > 0:
        op = operator.pop()
        if op[0] == 'func': output.append(op[1])
        else: output.append(op)

    return ' '.join(output)

assert parse("3 + 4 * 2 / (1 - 5) ^2 ^3") == "3 4 2 * 1 5 - 2 3 ^ ^ / +"
assert parse("sin(max(2, 3) / 3 * pi)") == "2 3 max 3 / pi * sin"

[tokenizer-using-generator-in-python.py]

import re

token_pattern = r'[a-zA-Z_][a-zA-Z0-9_]*|\d+|<=|>=|==|!=|[<>]=?|=|[+\-*/;(){}]'

tokens = {
    'if': 'IF',
    'else': 'ELSE',
    'number': 'NUM',
    'identifier': 'ID',
    'assignment': 'ASSIGN',
    'operator': 'OP',
    'unknown': '?',
}

# tokenize
def tokenize(code):
    for match in re.findall(token_pattern, code):
        # yield to return generator (lazy evaluation)
        if tokens.get(match):       yield (tokens[match], match)
        elif match.isdigit():       yield (tokens['number'], match)
        elif match.isidentifier():  yield (tokens['identifier'], match)
        elif match in '=':          yield (tokens['assignment'], match)
        elif match in '+-*/<>':     yield (tokens['operator'], match)
        elif match in '()/{/};':    pass
        else:                       yield (tokens['unknown'], match)

code = """if (x < 10) { x = x + 1; }"""

for token in tokenize(code): print(token)
# ('IF', 'if')
# ('ID', 'x')
# ('OP', '<')
# ('NUM', '10')
# ('ID', 'x')
# ('ASSIGN', '=')
# ('ID', 'x')
# ('OP', '+')
# ('NUM', '1')

[vectorization-optimization.py]

"""
Vectorization optimization is a technique for optimizing
programs by transforming sequential operations into
parallel operations (vector operations).
"""

import numpy as np
import timeit
from dis import dis

def add_arrays(a, b):
    result = []
    for i in range(len(a)):
        result.append(a[i] + b[i])
    return result

# vectorized
def add_arrays_vectorized(a, b):
    return np.array(a) + np.array(b)

a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
b = [9, 8, 7, 6, 5, 4, 3, 2, 1]

assert np.array(add_arrays(a, b)).all() == add_arrays_vectorized(a, b).all()

# test data
a = np.random.randint(0, 10, size=1000000)
b = np.random.randint(0, 10, size=1000000)

print(timeit.timeit(lambda: add_arrays(a, b), number=10))
# 2.4067575628869236
print(timeit.timeit(lambda: add_arrays_vectorized(a, b), number=10))
# 0.07865401287563145

dis(add_arrays)
# 4           0 RESUME                   0

# 5           2 BUILD_LIST               0
#             4 STORE_FAST               2 (result)

# 6           6 LOAD_GLOBAL              1 (NULL + range)
#            18 LOAD_GLOBAL              3 (NULL + len)
#            30 LOAD_FAST                0 (a)
#            32 PRECALL                  1
#            36 CALL                     1
#            46 PRECALL                  1
#            50 CALL                     1
#            60 GET_ITER
#       >>   62 FOR_ITER                38 (to 140)
#            64 STORE_FAST               3 (i)

# 7          66 LOAD_FAST                2 (result)
#            68 LOAD_METHOD              2 (append)
#            90 LOAD_FAST                0 (a)
#            92 LOAD_FAST                3 (i)
#            94 BINARY_SUBSCR
#           104 LOAD_FAST                1 (b)
#           106 LOAD_FAST                3 (i)
#           108 BINARY_SUBSCR
#           118 BINARY_OP                0 (+)
#           122 PRECALL                  1
#           126 CALL                     1
#           136 POP_TOP
#           138 JUMP_BACKWARD           39 (to 62)

# 8     >>  140 LOAD_FAST                2 (result)
#           142 RETURN_VALUE

dis(add_arrays_vectorized)
# 11           0 RESUME                   0

# 12           2 LOAD_GLOBAL              1 (NULL + np)
#             14 LOAD_ATTR                1 (array)
#             24 LOAD_FAST                0 (a)
#             26 PRECALL                  1
#             30 CALL                     1
#             40 LOAD_GLOBAL              1 (NULL + np)
#             52 LOAD_ATTR                1 (array)
#             62 LOAD_FAST                1 (b)
#             64 PRECALL                  1
#             68 CALL                     1
#             78 BINARY_OP                0 (+)
#             82 RETURN_VALUE

assemblyx86^

x86^

hello-x86.asm

[hello-x86.asm]

; x86-64 (intel syntax)
    section .text
    global _main

_main:
    mov rax, 0x02000004     ; write (4)
    mov rdi, 1              ; stdout
    mov rsi, message        ; address of output
    mov rdx, 10             ; bytes : "hello x86" + /n = 10
    syscall                 ; invoke write
    mov rax, 0x02000001     ; exit (1)
    xor rdi, rdi            ; 0
    syscall                 ; invoke to exit

    section .data

message:
    db "hello x86", 10      ; define byte : text, \n (10)

; $ nasm -f macho64 hello-x86.asm 
; $ ld hello-x86.o -o _hello -lSystem -L/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/lib
; $ ./_hello
; hello x86

verilogmiscgates^

misc^

intro.v

[intro.v]

/*
    http://www.techep.csi.cuny.edu/~zhangs/v.html
    iverilog -o intro intro.v; vvp intro
*/

// module < filename > (< ports >)
module intro;
    initial 
    begin
        // $display : only useful for debugging
        $display("hello verilog");
        $finish;
    end
endmodule

gates^

and16.vand.vdmux4way.vdmux8way.vdmux.vmux4way16.vmux8way16.vmux16.vmux.vnand.vnot16.vnot.vor8way.vor16.vor.vxor.v

[and16.v]

/*
    And16(a, b) : For i = 0..15 out[i] = And(a[i], b[i])
*/

// gate-level
module and16_gate (output [15:0] out, input [15:0] a, b);
    // operations
    and(out[0], a[0], b[0]);
    and(out[1], a[1], b[1]);
    and(out[2], a[2], b[2]);
    and(out[3], a[3], b[3]);
    and(out[4], a[4], b[4]);
    and(out[5], a[5], b[5]);
    and(out[6], a[6], b[6]);
    and(out[7], a[7], b[7]);
    and(out[8], a[8], b[8]);
    and(out[9], a[9], b[9]);
    and(out[10], a[10], b[10]);
    and(out[11], a[11], b[11]);
    and(out[12], a[12], b[12]);
    and(out[13], a[13], b[13]);
    and(out[14], a[14], b[14]);
    and(out[15], a[15], b[15]);
endmodule

// behavioural-level
module and16_behavioural (output reg [15:0] out, input [15:0] a, b);
    always @ (a or b) begin
        out = a & b;
    end
endmodule

// test
module test;
    reg [15:0] a, b;
    wire [15:0] out;

    // and16_gate Instance0 (out, a, b);
    and16_behavioural Instance0 (out, a, b);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        a[7:0] = 8'b11111111; b[7:0] = 8'b11111111;     // 1, 1, 1, 1, 1, 1, 1, 1
        a[15:8] = 8'b00000000; b[15:8] = 8'b11111111;   // 0, 0, 0, 0, 0, 0, 0, 0
    end

    initial begin
        $printtimescale;
        // Time scale of (test) is 1s / 1s
        #(0) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[0], b[0], out[0]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[1], b[1], out[1]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[2], b[2], out[2]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[3], b[3], out[3]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[4], b[4], out[4]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[5], b[5], out[5]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[6], b[6], out[6]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[7], b[7], out[7]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[8], b[8], out[8]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[9], b[9], out[9]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[10], b[10], out[10]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[11], b[11], out[11]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[12], b[12], out[12]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[13], b[13], out[13]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[14], b[14], out[14]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[15], b[15], out[15]);
        //  0 | a = 1 | b = 1 | out = 1
        //  1 | a = 1 | b = 1 | out = 1
        //  2 | a = 1 | b = 1 | out = 1
        //  3 | a = 1 | b = 1 | out = 1
        //  4 | a = 1 | b = 1 | out = 1
        //  5 | a = 1 | b = 1 | out = 1
        //  6 | a = 1 | b = 1 | out = 1
        //  7 | a = 1 | b = 1 | out = 1
        //  8 | a = 0 | b = 1 | out = 0
        //  9 | a = 0 | b = 1 | out = 0
        // 10 | a = 0 | b = 1 | out = 0
        // 11 | a = 0 | b = 1 | out = 0
        // 12 | a = 0 | b = 1 | out = 0
        // 13 | a = 0 | b = 1 | out = 0
        // 14 | a = 0 | b = 1 | out = 0
        // 15 | a = 0 | b = 1 | out = 0
    end
endmodule

[and.v]

/*
    And(a, b) : If a = b = 1 then out = 1 else out = 0
*/

// gate-level
module and_gate (output out, input a, b);
    // wire : internal pin
    wire w;
    // operations (note: limited to nand-gates)
    nand(w, a, b);
    nand(out, w, w);
endmodule

// test
module test;
    reg a, b;
    wire out;

    and_gate Instance0 (out, a, b);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        #(0) a = 0; b = 0; // 0
        #(1) a = 0; b = 1; // 0
        #(1) a = 1; b = 0; // 0
        #(1) a = 1; b = 1; // 1
    end

    initial begin
        $printtimescale;
        // Time scale of (_nand_test) is 1s / 1s
        $monitor ("%1d | a = %d | b = %d | out = %d", $time, a, b, out);
        // 0 | a = 0 | b = 0 | out = 0
        // 1 | a = 0 | b = 1 | out = 0
        // 2 | a = 1 | b = 0 | out = 0
        // 3 | a = 1 | b = 1 | out = 1
    end
endmodule

[dmux4way.v]

/*
    DMux4way(in, sel) :
        If sel = 00 then { a = in, b = c = d = 0 } else if
           sel = 01 then { b = in, a = c = d = 0 } else if
           sel = 10 then { c = in, a = b = d = 0 } else if
           sel = 11 then { d = in, a = b = c = 0 }
*/

// dmux.v
module dmux_gate (output a, b, input in, sel);
    // wire : internal pin
    wire w1;
    wire w2;
    wire notsel;
    // operations
    not(notsel, sel);
    and(a, in, notsel);
    and(b, in, sel);
endmodule

// gate-level
module dmux4way_gate (output a, b, c, d, input in, input [1:0] sel);
    wire ao, bo;

    dmux_gate Instance0 (ao, bo, in, sel[0]);
    dmux_gate Instance1 (a, b, ao, sel[1]);
    dmux_gate Instance2 (c, d, bo, sel[1]);
endmodule

// behavioural-level
module dmux4way_behavioural (output reg a, b, c, d, input in, input [1:0] sel);
    always @ (in or sel) begin
        a = 1'b0;
        b = 1'b0;
        c = 1'b0;
        d = 1'b0;
        // note: 2'b : 2-bit
        if (sel == 2'b00) begin
            a = in;
        end
        else if (sel == 2'b10) begin
            b = in;
        end
        else if (sel == 2'b01) begin
            c = in;
        end
        else begin
            d = in;
        end
    end
endmodule

// test
module test;
    reg [1:0] sel;
    reg in;
    wire a, b, c, d;

    // dmux4way_gate Instance0 (a, b, c, d, in, sel);
    dmux4way_behavioural Instance0 (a, b, c, d, in, sel);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        #(0) in = 1; sel[0] = 0; sel[1] = 0; // { a = 1, b = c = d = 0 }
        #(1) in = 1; sel[0] = 0; sel[1] = 1; // { b = 1, a = c = d = 0 }
        #(1) in = 1; sel[0] = 1; sel[1] = 0; // { c = 1, a = b = d = 0 }
        #(1) in = 1; sel[0] = 1; sel[1] = 1; // { d = 1, a = b = c = 0 }
    end

    initial begin
        $printtimescale;
        // Time scale of (test) is 1s / 1s
        $monitor ("%1d | in = %d | sel = [%d, %d] | a = %d | b = %d | c = %d | d = %d", $time, in, sel[0], sel[1], a, b, c, d);
        // 0 | in = 1 | sel = [0, 0] | a = 1 | b = 0 | c = 0 | d = 0
        // 1 | in = 1 | sel = [0, 1] | a = 0 | b = 1 | c = 0 | d = 0
        // 2 | in = 1 | sel = [1, 0] | a = 0 | b = 0 | c = 1 | d = 0
        // 3 | in = 1 | sel = [1, 1] | a = 0 | b = 0 | c = 0 | d = 1
    end
endmodule

[dmux8way.v]

/*
    DMux8way(in, sel) :
        If sel = 000 then { a = in, b = c = d = e = f = g = h = 0 } else if
           sel = 001 then { b = in, a = c = d = e = f = g = h = 0 } else if
           sel = 010 then { c = in, a = b = d = e = f = g = h = 0 } else if
           sel = 011 then { d = in, a = b = c = e = f = g = h = 0 } else if
           sel = 100 then { e = in, a = b = c = d = f = g = h = 0 } else if
           sel = 101 then { f = in, a = b = c = d = e = g = h = 0 } else if
           sel = 110 then { g = in, a = b = c = d = e = f = h = 0 } else if
           sel = 111 then { h = in, a = b = c = d = e = f = g = 0 }
*/

// dmux.v
module dmux_gate (output a, b, input in, sel);
    // wire : internal pin
    wire w1;
    wire w2;
    wire notsel;
    // operations
    not(notsel, sel);
    and(a, in, notsel);
    and(b, in, sel);
endmodule

// gate-level
module dmux8way_gate (output a, b, c, d, e, f, g, h, input in, input [2:0] sel);
    wire ao, bo, aoo, boo, coo, doo;

    dmux_gate Instance0 (ao, bo, in, sel[0]);

    dmux_gate Instance1 (aoo, boo, ao, sel[1]);
    dmux_gate Instance2 (coo, doo, bo, sel[1]);

    dmux_gate Instance3 (a, b, aoo, sel[2]);
    dmux_gate Instance4 (c, d, boo, sel[2]);
    dmux_gate Instance5 (e, f, coo, sel[2]);
    dmux_gate Instance6 (g, h, doo, sel[2]);
endmodule

// behavioural-level
module dmux8way_behavioural (output reg a, b, c, d, e, f, g, h, input in, input [2:0] sel);
    always @ (in or sel) begin
        a = 1'b0;
        b = 1'b0;
        c = 1'b0;
        d = 1'b0;
        e = 1'b0;
        f = 1'b0;
        g = 1'b0;
        h = 1'b0;
        // note: 3'b : 3 bit
        if (sel == 3'b000) begin
            a = in;
        end
        else if (sel == 3'b100) begin
            b = in;
        end
        else if (sel == 3'b010) begin
            c = in;
        end
        else if (sel == 3'b110) begin
            d = in;
        end
        else if (sel == 3'b001) begin
            e = in;
        end
        else if (sel == 3'b101) begin
            f = in;
        end
        else if (sel == 3'b011) begin
            g = in;
        end
        else begin
            h = in;
        end
    end
endmodule

// test
module test;
    reg [2:0] sel;
    reg in;
    wire a, b, c, d, e, f, g, h;

    // dmux8way_gate Instance0 (a, b, c, d, e, f, g, h, in, sel);
    dmux8way_behavioural Instance0 (a, b, c, d, e, f, g, h, in, sel);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        #(0) in = 1; sel[0] = 0; sel[1] = 0; sel[2] = 0; // { a = 1, b = c = d = e = f = g = h = 0 }
        #(1) in = 1; sel[0] = 0; sel[1] = 0; sel[2] = 1; // { b = 1, a = c = d = e = f = g = h = 0 }
        #(1) in = 1; sel[0] = 0; sel[1] = 1; sel[2] = 0; // { c = 1, a = b = d = e = f = g = h = 0 }
        #(1) in = 1; sel[0] = 0; sel[1] = 1; sel[2] = 1; // { d = 1, a = b = c = e = f = g = h = 0 }
        #(1) in = 1; sel[0] = 1; sel[1] = 0; sel[2] = 0; // { e = 1, a = b = c = d = f = g = h = 0 }
        #(1) in = 1; sel[0] = 1; sel[1] = 0; sel[2] = 1; // { f = 1, a = b = c = d = e = g = h = 0 }
        #(1) in = 1; sel[0] = 1; sel[1] = 1; sel[2] = 0; // { g = 1, a = b = c = d = e = f = h = 0 }
        #(1) in = 1; sel[0] = 1; sel[1] = 1; sel[2] = 1; // { h = 1, a = b = c = d = e = f = g = 0 }
    end

    initial begin
        $printtimescale;
        // Time scale of (test) is 1s / 1s
        $monitor ("%1d | in = %d | sel = [%d, %d, %d] | a = %d | b = %d | c = %d | d = %d | e = %d | f = %d | g = %d | h = %d", $time, in, sel[0], sel[1], sel[2], a, b, c, d, e, f, g, h);
        // 0 | in = 1 | sel = [0, 0, 0] | a = 1 | b = 0 | c = 0 | d = 0 | e = 0 | f = 0 | g = 0 | h = 0
        // 1 | in = 1 | sel = [0, 0, 1] | a = 0 | b = 1 | c = 0 | d = 0 | e = 0 | f = 0 | g = 0 | h = 0
        // 2 | in = 1 | sel = [0, 1, 0] | a = 0 | b = 0 | c = 1 | d = 0 | e = 0 | f = 0 | g = 0 | h = 0
        // 3 | in = 1 | sel = [0, 1, 1] | a = 0 | b = 0 | c = 0 | d = 1 | e = 0 | f = 0 | g = 0 | h = 0
        // 4 | in = 1 | sel = [1, 0, 0] | a = 0 | b = 0 | c = 0 | d = 0 | e = 1 | f = 0 | g = 0 | h = 0
        // 5 | in = 1 | sel = [1, 0, 1] | a = 0 | b = 0 | c = 0 | d = 0 | e = 0 | f = 1 | g = 0 | h = 0
        // 6 | in = 1 | sel = [1, 1, 0] | a = 0 | b = 0 | c = 0 | d = 0 | e = 0 | f = 0 | g = 1 | h = 0
        // 7 | in = 1 | sel = [1, 1, 1] | a = 0 | b = 0 | c = 0 | d = 0 | e = 0 | f = 0 | g = 0 | h = 1
    end
endmodule

[dmux.v]

/*
    DMux(in, sel) : If sel = 0 then { a = in, b = 0 } else { a = 0, b = in }
*/

// gate-level
module dmux_gate (output a, b, input in, sel);
    // wire : internal pin
    wire w1;
    wire w2;
    wire notsel;
    // operations
    not(notsel, sel);
    and(a, in, notsel);
    and(b, in, sel);
endmodule

// behavioural-level
module dmux_behavioural (output reg a, b, input in, sel);
    always @ (in or sel) begin
        // note: 1'b : 1 bit
        if (sel == 1'b0) begin
            a = in;
            b = 1'b0;
        end
        else begin
            a = 1'b0;
            b = in;
        end
    end
endmodule

// test
module test;
    reg in, sel;
    wire a, b;

    // dmux_gate Instance0 (a, b, in, sel);
    dmux_behavioural Instance0 (a, b, in, sel);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        #(0) in = 0; sel = 0; // 0, 0
        #(1) in = 1; sel = 0; // 1, 0
        #(1) in = 0; sel = 1; // 0, 0
        #(1) in = 1; sel = 1; // 0, 1
    end

    initial begin
        $printtimescale;
        // Time scale of (test) is 1s / 1s
        $monitor ("%1d | in = %d | sel = %d | a = %d | b = %d", $time, in, sel, a, b);
        // 0 | in = 0 | sel = 0 | a = 0 | b = 0
        // 1 | in = 1 | sel = 0 | a = 1 | b = 0
        // 2 | in = 0 | sel = 1 | a = 0 | b = 0
        // 3 | in = 1 | sel = 1 | a = 0 | b = 1
    end
endmodule

[mux4way16.v]

/*
    Mux4Way16(a, b, c, d, sel) :
        If sel = 00 then out = a else if
           sel = 01 then out = b else if
           sel = 10 then out = c else if
           sel = 11 then out = d
*/

// mux.v
module mux_gate (output out, input a, b, sel);
    // wire : internal pin
    wire w1;
    wire w2;
    wire notsel;
    // operations
    not(notsel, sel);
    and(w1, a, notsel);
    and(w2, b, sel);
    or(out, w1, w2);
endmodule

// mux16.v
module mux16_gate (output [15:0] out, input [15:0] a, b, input sel);
    mux_gate Instance0 (out[0], a[0], b[0], sel);
    mux_gate Instance1 (out[1], a[1], b[1], sel);
    mux_gate Instance2 (out[2], a[2], b[2], sel);
    mux_gate Instance3 (out[3], a[3], b[3], sel);
    mux_gate Instance4 (out[4], a[4], b[4], sel);
    mux_gate Instance5 (out[5], a[5], b[5], sel);
    mux_gate Instance6 (out[6], a[6], b[6], sel);
    mux_gate Instance7 (out[7], a[7], b[7], sel);
    mux_gate Instance8 (out[8], a[8], b[8], sel);
    mux_gate Instance9 (out[9], a[9], b[9], sel);
    mux_gate Instance10 (out[10], a[10], b[10], sel);
    mux_gate Instance11 (out[11], a[11], b[11], sel);
    mux_gate Instance12 (out[12], a[12], b[12], sel);
    mux_gate Instance13 (out[13], a[13], b[13], sel);
    mux_gate Instance14 (out[14], a[14], b[14], sel);
    mux_gate Instance15 (out[15], a[15], b[15], sel);
endmodule

// gate-level
module mux4way16_gate (output [15:0] out, input [15:0] a, b, c, d, input [1:0] sel);
    wire [15:0] ab, cd;

    mux16_gate Instance0 (ab, a, b, sel[1]);
    mux16_gate Instance1 (cd, c, d, sel[1]);
    mux16_gate Instance2 (out, ab, cd, sel[0]);
endmodule

// behavioural-level
module mux4way16_behavioural (output reg [15:0] out, input [15:0] a, b, c, d, input [1:0] sel);
    always @ (a or b or c or d or sel) begin
        // note: 2'b : 2 bit
        if (sel == 2'b00) begin
            out = a;
        end
        else if (sel == 2'b10) begin
            out = b;
        end
        else if (sel == 2'b01) begin
            out = c;
        end
        else begin
            out = d;
        end
    end
endmodule

// test
module test;
    reg [15:0] a, b, c, d;
    reg [1:0] sel;
    wire [15:0] out;

    // mux4way16_gate Instance0 (out, a, b, c, d, sel);
    mux4way16_behavioural Instance0 (out, a, b, c, d, sel);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        a[15:0] = 8'b11111111;
        b[15:0] = 8'b00000000;
        c[15:0] = 8'b11111111;
        d[15:0] = 8'b00000000;

        #(0) sel[0] = 0; sel[1] = 0; // out = a = 1
        #(1) sel[0] = 0; sel[1] = 1; // out = b = 0
        #(1) sel[0] = 1; sel[1] = 0; // out = c = 1
        #(1) sel[0] = 1; sel[1] = 1; // out = d = 0
    end

    initial begin
        $printtimescale;
        // Time scale of (test) is 1s / 1s
        $monitor ("%2d | a = %d | b = %d | c = %d | d = %d | sel = [%d, %d] | out = %d", $time, a[0], b[0], c[0], d[0], sel[0], sel[1], out[0]);
        // 0 | a = 1 | b = 0 | c = 1 | d = 0 | sel = [0, 0] | out = 1
        // 1 | a = 1 | b = 0 | c = 1 | d = 0 | sel = [0, 1] | out = 0
        // 2 | a = 1 | b = 0 | c = 1 | d = 0 | sel = [1, 0] | out = 1
        // 3 | a = 1 | b = 0 | c = 1 | d = 0 | sel = [1, 1] | out = 0
    end
endmodule

[mux8way16.v]

/*
    Mux8Way16(a, b, c, d, e, f, g, h, sel) :
        If sel = 000 then out = a else if
           sel = 001 then out = b else if
           sel = 010 then out = c else if
           sel = 011 then out = d else if
           sel = 100 then out = e else if 
           sel = 101 then out = f else if 
           sel = 110 then out = g else if
           sel = 111 then out = h
*/

// mux.v
module mux_gate (output out, input a, b, sel);
    // wire : internal pin
    wire w1;
    wire w2;
    wire notsel;
    // operations
    not(notsel, sel);
    and(w1, a, notsel);
    and(w2, b, sel);
    or(out, w1, w2);
endmodule

// mux16.v
module mux16_gate (output [15:0] out, input [15:0] a, b, input sel);
    mux_gate Instance0 (out[0], a[0], b[0], sel);
    mux_gate Instance1 (out[1], a[1], b[1], sel);
    mux_gate Instance2 (out[2], a[2], b[2], sel);
    mux_gate Instance3 (out[3], a[3], b[3], sel);
    mux_gate Instance4 (out[4], a[4], b[4], sel);
    mux_gate Instance5 (out[5], a[5], b[5], sel);
    mux_gate Instance6 (out[6], a[6], b[6], sel);
    mux_gate Instance7 (out[7], a[7], b[7], sel);
    mux_gate Instance8 (out[8], a[8], b[8], sel);
    mux_gate Instance9 (out[9], a[9], b[9], sel);
    mux_gate Instance10 (out[10], a[10], b[10], sel);
    mux_gate Instance11 (out[11], a[11], b[11], sel);
    mux_gate Instance12 (out[12], a[12], b[12], sel);
    mux_gate Instance13 (out[13], a[13], b[13], sel);
    mux_gate Instance14 (out[14], a[14], b[14], sel);
    mux_gate Instance15 (out[15], a[15], b[15], sel);
endmodule

// gate-level
module mux8way16_gate (output [15:0] out, input [15:0] a, b, c, d, e, f, g, h, input [2:0] sel);
    wire [15:0] ab, cd, ef, gh, abcd, efgh;

    mux16_gate Instance0 (ab, a, b, sel[2]);
    mux16_gate Instance1 (cd, c, d, sel[2]);
    mux16_gate Instance2 (ef, e, f, sel[2]);
    mux16_gate Instance3 (gh, g, h, sel[2]);

    mux16_gate Instance4 (abcd, ab, cd, sel[1]);
    mux16_gate Instance5 (efgh, ef, gh, sel[1]);

    mux16_gate Instance6 (out, abcd, efgh, sel[0]);
endmodule

// behavioural-level
module mux8way16_behavioural (output reg [15:0] out, input [15:0] a, b, c, d, e, f, g, h, input [2:0] sel);
    always @ (a or b or c or d or sel) begin
        // note: 3'b : 3 bit
        if (sel == 3'b000) begin
            out = a;
        end
        else if (sel == 3'b100) begin
            out = b;
        end
        else if (sel == 3'b010) begin
            out = c;
        end
        else if (sel == 3'b110) begin
            out = d;
        end
        else if (sel == 3'b001) begin
            out = e;
        end
        else if (sel == 3'b101) begin
            out = f;
        end
        else if (sel == 3'b011) begin
            out = g;
        end
        else begin
            out = h;
        end
    end
endmodule

// test
module test;
    reg [15:0] a, b, c, d, e, f, g, h;
    reg [2:0] sel;
    wire [15:0] out;

    // mux8way16_gate Instance0 (out, a, b, c, d, e, f, g, h, sel);
    mux8way16_behavioural Instance0 (out, a, b, c, d, e, f, g, h, sel);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        a[15:0] = 8'b11111111;
        b[15:0] = 8'b00000000;
        c[15:0] = 8'b11111111;
        d[15:0] = 8'b00000000;
        e[15:0] = 8'b11111111;
        f[15:0] = 8'b00000000;
        g[15:0] = 8'b11111111;
        h[15:0] = 8'b00000000;

        #(0) sel[0] = 0; sel[1] = 0; sel[2] = 0; // out = a = 1
        #(1) sel[0] = 0; sel[1] = 0; sel[2] = 1; // out = b = 0
        #(1) sel[0] = 0; sel[1] = 1; sel[2] = 0; // out = c = 1
        #(1) sel[0] = 0; sel[1] = 1; sel[2] = 1; // out = d = 0
        #(1) sel[0] = 1; sel[1] = 0; sel[2] = 0; // out = e = 1
        #(1) sel[0] = 1; sel[1] = 0; sel[2] = 1; // out = f = 0
        #(1) sel[0] = 1; sel[1] = 1; sel[2] = 0; // out = g = 1
        #(1) sel[0] = 1; sel[1] = 1; sel[2] = 1; // out = h = 0
    end

    initial begin
        $printtimescale;
        // Time scale of (test) is 1s / 1s
        $monitor ("%2d | a = %d | b = %d | c = %d | d = %d | e = %d | f = %d | g = %d | h = %d | sel = [%d, %d, %d] | out = %d", $time, a[0], b[0], c[0], d[0], e[0], f[0], g[0], h[0], sel[0], sel[1], sel[2], out[0]);
        // 0 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [0, 0, 0] | out = 1
        // 1 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [0, 0, 1] | out = 0
        // 2 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [0, 1, 0] | out = 1
        // 3 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [0, 1, 1] | out = 0
        // 4 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [1, 0, 0] | out = 1
        // 5 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [1, 0, 1] | out = 0
        // 6 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [1, 1, 0] | out = 1
        // 7 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [1, 1, 1] | out = 0
    end
endmodule

[mux16.v]

/*
    Mux16(a, b, sel) : If sel = 0 then for i = 0..15 out[i] = a[i] else for i = 0..15 out[i] = b[i]
*/

// mux.v
module mux_gate (output out, input a, b, sel);
    // wire : internal pin
    wire w1;
    wire w2;
    wire notsel;
    // operations
    not(notsel, sel);
    and(w1, a, notsel);
    and(w2, b, sel);
    or(out, w1, w2);
endmodule

// gate-level
module mux16_gate (output [15:0] out, input [15:0] a, b, input sel);
    mux_gate Instance0 (out[0], a[0], b[0], sel);
    mux_gate Instance1 (out[1], a[1], b[1], sel);
    mux_gate Instance2 (out[2], a[2], b[2], sel);
    mux_gate Instance3 (out[3], a[3], b[3], sel);
    mux_gate Instance4 (out[4], a[4], b[4], sel);
    mux_gate Instance5 (out[5], a[5], b[5], sel);
    mux_gate Instance6 (out[6], a[6], b[6], sel);
    mux_gate Instance7 (out[7], a[7], b[7], sel);
    mux_gate Instance8 (out[8], a[8], b[8], sel);
    mux_gate Instance9 (out[9], a[9], b[9], sel);
    mux_gate Instance10 (out[10], a[10], b[10], sel);
    mux_gate Instance11 (out[11], a[11], b[11], sel);
    mux_gate Instance12 (out[12], a[12], b[12], sel);
    mux_gate Instance13 (out[13], a[13], b[13], sel);
    mux_gate Instance14 (out[14], a[14], b[14], sel);
    mux_gate Instance15 (out[15], a[15], b[15], sel);
endmodule

// behavioural-level
module mux16_behavioural (output reg [15:0] out, input [15:0] a, b, input sel);
    always @ (a or b or sel) begin
        // note: 1'b : 1 bit
        if (sel == 1'b0) begin
            out = a;
        end
        else begin
            out = b;
        end
    end
endmodule

// test
module test;
    reg [15:0] a, b;
    reg sel;
    wire [15:0] out;

    // mux16_gate Instance0 (out, a, b, sel);
    mux16_behavioural Instance0 (out, a, b, sel);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        #(0) a[15:0] = 8'b11111111; b[15:0] = 8'b00000000; sel = 0; // out = 1
        #(1) a[15:0] = 8'b11111111; b[15:0] = 8'b00000000; sel = 1; // out = 0
    end

    initial begin
        $printtimescale;
        // Time scale of (test) is 1s / 1s
        $monitor ("%2d | a = %d | b = %d | sel = %d | out = %d", $time, a[0], b[0], sel, out[0]);
        // 0 | a = 1 | b = 0 | sel = 0 | out = 1
        // 1 | a = 1 | b = 0 | sel = 1 | out = 0
    end
endmodule

[mux.v]

/*
    Mux(a, b, sel) : If sel = 0 then out = a else out = b
*/

// gate-level
module mux_gate (output out, input a, b, sel);
    // wire : internal pin
    wire w1;
    wire w2;
    wire notsel;
    // operations
    not(notsel, sel);
    and(w1, a, notsel);
    and(w2, b, sel);
    or(out, w1, w2);
endmodule

// behavioural-level
module mux_behavioural (output reg out, input a, b, sel);
    always @ (a or b or sel) begin
        // note: 1'b : 1 bit
        if (sel == 1'b0) begin
            out = a;
        end
        else begin
            out = b;
        end
    end
endmodule

// test
module test;
    reg a, b, sel;
    wire out;

    // mux_gate Instance0 (out, a, b, sel);
    mux_behavioural Instance0 (out, a, b, sel);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        #(0) a = 0; b = 0; sel = 0; // 0
        #(1) a = 0; b = 1; sel = 0; // 0
        #(1) a = 1; b = 0; sel = 0; // 1
        #(1) a = 1; b = 1; sel = 0; // 1
        #(1) a = 0; b = 0; sel = 1; // 0
        #(1) a = 0; b = 1; sel = 1; // 1
        #(1) a = 1; b = 0; sel = 1; // 0
        #(1) a = 1; b = 1; sel = 1; // 1
    end

    initial begin
        $printtimescale;
        // Time scale of (test) is 1s / 1s
        $monitor ("%1d | a = %d | b = %d | sel = %d | out = %d", $time, a, b, sel, out);
        // 0 | a = 0 | b = 0 | sel = 0 | out = 0
        // 1 | a = 0 | b = 1 | sel = 0 | out = 0
        // 2 | a = 1 | b = 0 | sel = 0 | out = 1
        // 3 | a = 1 | b = 1 | sel = 0 | out = 1
        // 4 | a = 0 | b = 0 | sel = 1 | out = 0
        // 5 | a = 0 | b = 1 | sel = 1 | out = 1
        // 6 | a = 1 | b = 0 | sel = 1 | out = 0
        // 7 | a = 1 | b = 1 | sel = 1 | out = 1
    end
endmodule

[nand.v]

/*
    Nand(a, b) : If a = b = 1 then out = 0 else out = 1
*/

// gate-level
module nand_gate (output out, input a, b);
    // wire : internal pin
    wire w;
    // operations
    and(w, a, b);
    not(out, w);
endmodule

// behavioural-level
module nand_behavioural (output reg out, input a, b);
    always @ (a or b) begin
        // note: 1'b : 1 bit
        if (a == 1'b1 & b == 1'b1) begin
            out = 1'b0;
        end
        else begin
            out = 1'b1;
        end
    end
endmodule

// test
module test;
    reg a, b;
    wire out;

    // nand_gate Instance0 (out, a, b);
    nand_behavioural Instance0 (out, a, b);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        #(0) a = 0; b = 0; // 1
        #(1) a = 0; b = 1; // 1
        #(1) a = 1; b = 0; // 1
        #(1) a = 1; b = 1; // 0
    end

    initial begin
        $printtimescale;
        // Time scale of (_nand_test) is 1s / 1s
        $monitor ("%1d | a = %d | b = %d | out = %d", $time, a, b, out);
        // 0 | a = 0 | b = 0 | out = 1
        // 1 | a = 0 | b = 1 | out = 1
        // 2 | a = 1 | b = 0 | out = 1
        // 3 | a = 1 | b = 1 | out = 0
    end
endmodule

[not16.v]

/*
    Not16(in) : For i = 0..15 out[i] = Not(in[i])
*/

// gate-level
module not16_gate (output [15:0] out, input [15:0] in);
    // operations
    not(out[0], in[0]);
    not(out[1], in[1]);
    not(out[2], in[2]);
    not(out[3], in[3]);
    not(out[4], in[4]);
    not(out[5], in[5]);
    not(out[6], in[6]);
    not(out[7], in[7]);
    not(out[8], in[8]);
    not(out[9], in[9]);
    not(out[10], in[10]);
    not(out[11], in[11]);
    not(out[12], in[12]);
    not(out[13], in[13]);
    not(out[14], in[14]);
    not(out[15], in[15]);
endmodule

// behavioural-level
module not16_behavioural (output reg [15:0] out, input [15:0] in);
    always @ (in) begin
        out = ~in;
    end
endmodule

// test
module test;
    reg [15:0] in;
    wire [15:0] out;

    // not16_gate Instance0 (out, in);
    not16_behavioural Instance0 (out, in);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        in[7:0]     = 8'b11111111; // 0, 0, 0, 0, 0, 0, 0, 0
        in[15:8]    = 8'b00000000; // 1, 1, 1, 1, 1, 1, 1, 1
    end

    initial begin
        $printtimescale;
        // Time scale of (test) is 1s / 1s
        #(0) $monitor ("%2d | in = %d | out = %d", $time, in[0], out[0]);
        #(1) $monitor ("%2d | in = %d | out = %d", $time, in[1], out[1]);
        #(1) $monitor ("%2d | in = %d | out = %d", $time, in[2], out[2]);
        #(1) $monitor ("%2d | in = %d | out = %d", $time, in[3], out[3]);
        #(1) $monitor ("%2d | in = %d | out = %d", $time, in[4], out[4]);
        #(1) $monitor ("%2d | in = %d | out = %d", $time, in[5], out[5]);
        #(1) $monitor ("%2d | in = %d | out = %d", $time, in[6], out[6]);
        #(1) $monitor ("%2d | in = %d | out = %d", $time, in[7], out[7]);
        #(1) $monitor ("%2d | in = %d | out = %d", $time, in[8], out[8]);
        #(1) $monitor ("%2d | in = %d | out = %d", $time, in[9], out[9]);
        #(1) $monitor ("%2d | in = %d | out = %d", $time, in[10], out[10]);
        #(1) $monitor ("%2d | in = %d | out = %d", $time, in[11], out[11]);
        #(1) $monitor ("%2d | in = %d | out = %d", $time, in[12], out[12]);
        #(1) $monitor ("%2d | in = %d | out = %d", $time, in[13], out[13]);
        #(1) $monitor ("%2d | in = %d | out = %d", $time, in[14], out[14]);
        #(1) $monitor ("%2d | in = %d | out = %d", $time, in[15], out[15]);
        //  0 | in = 1 | out = 0
        //  1 | in = 1 | out = 0
        //  2 | in = 1 | out = 0
        //  3 | in = 1 | out = 0
        //  4 | in = 1 | out = 0
        //  5 | in = 1 | out = 0
        //  6 | in = 1 | out = 0
        //  7 | in = 1 | out = 0
        //  8 | in = 0 | out = 1
        //  9 | in = 0 | out = 1
        // 10 | in = 0 | out = 1
        // 11 | in = 0 | out = 1
        // 12 | in = 0 | out = 1
        // 13 | in = 0 | out = 1
        // 14 | in = 0 | out = 1
        // 15 | in = 0 | out = 1
    end
endmodule

[not.v]

/*
    Not(in) : If in = 0 then out = 1 else out = 0
*/

// gate-level
module not_gate (output out, input in);
    // operations (note: limited to nand-gates)
    nand(out, in, in);
endmodule

// test
module test;
    reg in;
    wire out;

    not_gate Instance0 (out, in);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        #(0) in = 0; // 1
        #(1) in = 1; // 0
    end

    initial begin
        $printtimescale;
        // Time scale of (_nand_test) is 1s / 1s
        $monitor ("%1d | in = %d | out = %d", $time, in, out);
        // 0 | in = 0 | out = 1
        // 1 | in = 1 | out = 0
    end
endmodule

[or8way.v]

/*
    Or8Way(in) : out = Or(in[0], ..., in[7])
*/

// gate-level
module or8way_gate (output out, input [7:0] in);
    // operations : or
    or(out, in[0], in[1], in[2], in[3], in[4], in[5], in[6], in[7]);
endmodule

// behavioural-level
module or8way_behavioural (output reg out, input [7:0] in);
    always @ (in) begin
        out = in[0] | in[1] | in[2] | in[3] | in[4] | in[5] | in[6] | in[7];
    end
endmodule

// test
module test;
    reg [7:0] in;
    wire out;

    // or8way_gate Instance0 (out, in);
    or8way_behavioural Instance0 (out, in);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        #(0) in[0] = 1; in[1] = 0; in[2] = 1; in[3] = 0; in[4] = 1; in[5] = 0; in[6] = 1; in[7] = 0; // out = 1
        #(1) in[0] = 0; in[1] = 0; in[2] = 0; in[3] = 0; in[4] = 0; in[5] = 0; in[6] = 0; in[7] = 0; // out = 0
    end

    initial begin
        $printtimescale;
        // Time scale of (_nand_test) is 1s / 1s
        $monitor ("%1d | in = [%d, %d, %d, %d, %d, %d, %d, %d] | out = %d", $time, in[0], in[1], in[2], in[3], in[4], in[5], in[6], in[7], out);
        // 0 | in = [1, 0, 1, 0, 1, 0, 1, 0] | out = 1
        // 1 | in = [0, 0, 0, 0, 0, 0, 0, 0] | out = 0
    end
endmodule

[or16.v]

/*
    Or16(a, b) : For i = 0..15 out[i] = Or(a[i], b[i])
*/

// gate-level
module or16_gate (output [15:0] out, input [15:0] a, b);
    // operations
    or(out[0], a[0], b[0]);
    or(out[1], a[1], b[1]);
    or(out[2], a[2], b[2]);
    or(out[3], a[3], b[3]);
    or(out[4], a[4], b[4]);
    or(out[5], a[5], b[5]);
    or(out[6], a[6], b[6]);
    or(out[7], a[7], b[7]);
    or(out[8], a[8], b[8]);
    or(out[9], a[9], b[9]);
    or(out[10], a[10], b[10]);
    or(out[11], a[11], b[11]);
    or(out[12], a[12], b[12]);
    or(out[13], a[13], b[13]);
    or(out[14], a[14], b[14]);
    or(out[15], a[15], b[15]);
endmodule

// behavioural-level
module or16_behavioural (output reg [15:0] out, input [15:0] a, b);
    always @ (a or b) begin
        out = a | b;
    end
endmodule

// test
module test;
    reg [15:0] a, b;
    wire [15:0] out;

    // or16_gate Instance0 (out, a, b);
    or16_behavioural Instance0 (out, a, b);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        a[7:0] = 8'b11111111; b[7:0] = 8'b00000000;     // 1, 1, 1, 1, 1, 1, 1, 1
        a[15:8] = 8'b00000000; b[15:8] = 8'b00000000;   // 0, 0, 0, 0, 0, 0, 0, 0
    end

    initial begin
        $printtimescale;
        // Time scale of (test) is 1s / 1s
        #(0) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[0], b[0], out[0]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[1], b[1], out[1]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[2], b[2], out[2]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[3], b[3], out[3]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[4], b[4], out[4]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[5], b[5], out[5]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[6], b[6], out[6]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[7], b[7], out[7]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[8], b[8], out[8]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[9], b[9], out[9]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[10], b[10], out[10]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[11], b[11], out[11]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[12], b[12], out[12]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[13], b[13], out[13]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[14], b[14], out[14]);
        #(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[15], b[15], out[15]);
        //  0 | a = 1 | b = 0 | out = 1
        //  1 | a = 1 | b = 0 | out = 1
        //  2 | a = 1 | b = 0 | out = 1
        //  3 | a = 1 | b = 0 | out = 1
        //  4 | a = 1 | b = 0 | out = 1
        //  5 | a = 1 | b = 0 | out = 1
        //  6 | a = 1 | b = 0 | out = 1
        //  7 | a = 1 | b = 0 | out = 1
        //  8 | a = 0 | b = 0 | out = 0
        //  9 | a = 0 | b = 0 | out = 0
        // 10 | a = 0 | b = 0 | out = 0
        // 11 | a = 0 | b = 0 | out = 0
        // 12 | a = 0 | b = 0 | out = 0
        // 13 | a = 0 | b = 0 | out = 0
        // 14 | a = 0 | b = 0 | out = 0
        // 15 | a = 0 | b = 0 | out = 0
    end
endmodule

[or.v]

/*
    Or(a, b) : If a = b = 0 then out = 0 else out = 1
*/

// gate-level
module or_gate (output out, input a, b);
    // wire : internal pin
    wire w1, w2;
    // operations (note: limited to nand-gates)
    nand(w1, a, a);
    nand(w2, b, b);
    nand(out, w1, w2);
endmodule

// test
module test;
    reg a, b;
    wire out;

    or_gate Instance0 (out, a, b);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        #(0) a = 0; b = 0; // out = 0
        #(1) a = 0; b = 1; // out = 1
        #(1) a = 1; b = 0; // out = 1
        #(1) a = 1; b = 1; // out = 1
    end

    initial begin
        $printtimescale;
        // Time scale of (_nand_test) is 1s / 1s
        $monitor ("%1d | a = %d | b = %d | out = %d", $time, a, b, out);
        // 0 | a = 0 | b = 0 | out = 0
        // 1 | a = 0 | b = 1 | out = 1
        // 2 | a = 1 | b = 0 | out = 1
        // 3 | a = 1 | b = 1 | out = 1
    end
endmodule

[xor.v]

/*
    Xor(a, b) : If a<>b then out = 1 else out = 0
*/

// gate-level
module xor_gate (output out, input a, b);
    // wire : internal pin
    wire w1;
    wire w2;
    wire nota;
    wire notb;
    // operations
    not(nota, a);
    not(notb, b);
    and(w1, a, notb);
    and(w2, nota, b);
    or(out, w1, w2);
endmodule

// behavioural-level
module xor_behavioural (output reg out, input a, b);
    always @ (a or b) begin
        // note: 1'b : 1 bit
        if ((a == 1'b1 & b == 1'b0) | (a == 1'b0 & b == 1'b1)) begin
            out = 1'b1;
        end
        else begin
            out = 1'b0;
        end
    end
endmodule

// test
module test;
    reg a, b;
    wire out;

    // xor_gate Instance0 (out, a, b);
    xor_behavioural Instance0 (out, a, b);

    // note: #(n) : delay by n timestep (check time scale with $printtimescale)
    initial begin
        #(0) a = 0; b = 0; // 0
        #(1) a = 0; b = 1; // 1
        #(1) a = 1; b = 0; // 1
        #(1) a = 1; b = 1; // 0
    end

    initial begin
        $printtimescale;
        // Time scale of (test) is 1s / 1s
        $monitor ("%1d | a = %d | b = %d | out = %d", $time, a, b, out);
        // 0 | a = 0 | b = 0 | out = 0
        // 1 | a = 0 | b = 1 | out = 1
        // 2 | a = 1 | b = 0 | out = 1
        // 3 | a = 1 | b = 1 | out = 0
    end
endmodule

cmisc^

misc^

header-files.clinked-list.cmacros.cmemory.cpointers.cvalist.c

[header-files.c]

#include <stdio.h>

// filename.h
/*
    #ifndef FILENAME_H
    #define FILENAME_H

    const int number = 10;

    #endif
*/

#include "filename.h"

int main() {
    printf("%d\n", number); // 10
}

[linked-list.c]

// linked list implementation in C
#include <stdio.h>
#include <stdlib.h>

// element is struct with a value and a pointer to the next element
struct Element {
    int value;
    struct Element *next;
};

// allocate memory for element
struct Element *create_element(int value) {
    struct Element *element = (struct Element*) malloc(sizeof(struct Element));

    element->value = value;
    element->next = NULL;

    return element;
}

// insert
void ll_insert(struct Element **element, int value) {
    struct Element *new_element = create_element(value);
    // list is empty
    if (*element == NULL) { *element = new_element; }
    // list is not empty
    else {
        struct Element *current = *element;
        // iterate until last element
        while (current->next != NULL) {
            current = current->next;
        }
        // insert new element
        current->next = new_element;
    }
}

// remove
void ll_remove(struct Element **element, int value) {
    struct Element *current = *element;
    struct Element *previous = NULL;
    // iterate until last element
    while (current != NULL) {
        // value is found
        if (current->value == value) {
            // value is first element
            if (previous == NULL) {
                *element = current->next;
            }
            // value is not first element
            else {
                previous->next = current->next;
            }
            // free memory
            free(current);
            return;
        }
        // update pointers
        previous = current;
        current = current->next;
    }
}

// print
void print(struct Element *element) {
    struct Element *current = element;
    // iterate until last element
    while (current != NULL) {
        printf("%d\n", current->value);
        current = current->next;
    }
}

int main() {
    struct Element *ll = NULL;

    // insert
    ll_insert(&ll, 5);
    ll_insert(&ll, 10);
    ll_insert(&ll, 15);
    ll_insert(&ll, 20);
    ll_insert(&ll, 25);
    ll_insert(&ll, 30);
    print(ll); // 5 10 15 20 25 30

    // remove
    ll_remove(&ll, 15);
    ll_remove(&ll, 30);
    print(ll); // 5 10 20 25
}

[macros.c]

#include <stdio.h>
#include <stddef.h>

// stringify error messages
#define  error_message(error) \
   printf("error: " #error "\n")

// if not defined (used in header files to avoid multiple inclusion)
#ifndef MESSAGE
#define MESSAGE "This is the message if not already defined."
#endif

// parameterized macros
#define square(x) ((x) * (x))
#define max(x, y) ((x) > (y) ? (x) : (y))

int main() {
   printf("%s\n", __FILE__); // macros.c
   printf("%s\n", __DATE__); // Aug 21 2019
   printf("%s\n", __TIME__); // 01:22:18
   printf("%d\n", __LINE__); // 12
   printf("%d\n", __STDC__); // 1

   error_message("This is an error.");
   // error: "This is an error."

   printf("%s\n", MESSAGE);
   // This is the message if not already defined.

   printf("%d\n", square(2)); // 4
   printf("%d\n", max(4,5)); // 5
}

[memory.c]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
    - allocate an array of n elements of size s
        void *calloc(int n, int s);

    - release a block of memory at address
        void free(void *address);

    - allocate an array of b bytes (uninitialised)
        void *malloc(int b);

    - re-allocate memory at address (extending to new size s)
        void *realloc(void *address, int s);
*/

int main() {
    char name[36];
    char *description; // pointer to char without size limit

    // copy string of 35 bytes into buffer of 36 bytes
    strcpy(name, "Wolfeschlegelsteinhausenbergerdorff");

    // allocate memory dynamically (can result in fragmented memory)
    // description = malloc(10 * sizeof(char));
    // strcpy(description, "A too long text to store in only 10 bytes...");
    // printf("%s\n", description);
    // malloc(): corrupted top size
    // Aborted

    description = malloc(100 * sizeof(char));
    strcpy(description, "A too long text to store in only 10 bytes...");
    printf("%s\n", description);
    // A too long text to store in only 10 bytes...

    // free memory
    free(description);
}

[pointers.c]

#include <stdio.h>
#include <stddef.h>

int main() {
    int num = 5;
    int *ip = NULL; // null pointer

    printf("%p\n", ip); // 0x0 (nil)

    // point to address of num
    ip = &num;

    printf("%p\n", &num); // 0x7ffdb78c2664
    printf("%p\n", ip); // 0x7ffdb78c2664

    // dereference (get value at address)
    printf("%d\n", *ip); // 5
}

[valist.c]

#include <stdio.h>
#include <stdarg.h>

// declare function (normally in header file)
double average(int n, ...);
// define function
double average(int n, ...) {
    va_list valist; /* stdarg.h */
    // return value
    double sum = 0.0;
    // init valist for n arguments
    va_start(valist, n);
    // access arguments
    for (int i=0; i<n; i++) {
        sum += va_arg(valist, int);
    }
    // free memory
    va_end(valist);
    // success
    return sum / n;
}

int main() {
    printf("average of {1,2,3,4,5}: %f\n", average(5, 1, 2, 3, 4, 5));
    // average of {1,2,3,4,5}: 3.000000
}