The naive collision detection algorithm takes O(n^2) by checking pairwise intersection. To improve the performance, sort the objects by x coordinates, scan from left to right and only check intersection if a.right < b.left. This method can be extended into 2D to further eliminate the necessary comparisons. Finally, note that insertion sort is more performant on mostly sorted lists than quick sorts, so it's more suitable in this case.

An interactive introduction to four-color problem and zero-knowledge proof.

Pratt parsing is a parsing algorithm that solves the awkward handling of left-recursion in a recursive descent parser. It elegantly handles both operator precedence and associativity using a single "binding power" concept. The core algorithm is as simple as follows:

fn expr(input: &str) -> S {
    let mut lexer = Lexer::new(input);
    expr_bp(&mut lexer, 0) 
}

fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S { 
    let mut lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),
        t => panic!("bad token: {:?}", t),
    };

    loop {
        let op = match lexer.peek() {
            Token::Eof => break,
            Token::Op(op) => op,
            t => panic!("bad token: {:?}", t),
        };

        let (l_bp, r_bp) = infix_binding_power(op);
        if l_bp < min_bp { 
            break;
        }

        lexer.next(); 
        let rhs = expr_bp(lexer, r_bp);

        lhs = S::Cons(op, vec![lhs, rhs]); 
    }

    lhs
}

fn infix_binding_power(op: char) -> (u8, u8) {
    match op {
        '+' | '-' => (1, 2),
        '*' | '/' => (3, 4),
        _ => panic!("bad op: {:?}"),
    }
}

An interger hash function is a bijection in the domain of N-bit unsigned integers with hashing properties. To make a good hash function, for each flip in input bit, roughly 1/2 of the output bit should flip (known as "high avalanche effect"). Furthermore, there should be no correlation between flipped input bits and output bits (known as "low bias"). The author of this article describes an algorithm to generate integer hash functions by composing reversible functions, and test the two hashing properties on the function to find the best ones.

TIL A* with fixed iteration depth.

This article talked about three data structures for efficient text editing (a.k.a. text buffer data structure): Rope, Gap Buffer, and Piece Table. It's first time I learned about Piece Table, it works like this:

• Store the text in an append-only fashion in two buffers known as original file and add file
• Store the information about segments of the files as a list of reference to the slices into the two buffers (known as "piece table")

The inserting/deleting in this data structure would simply need to breaking up items in the piece table. It seems like a good candidate as a basis to implement CRDT in a collaborative editor.

From my preliminary understanding of the nature of this data structure, it doesn't seem necessary to have two buffers, a single append-only buffer preloaded with the file should be sufficient.

UPDATE: I found this post on vscode blog extremely helpful: https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation

The author wrote a program that solves Mario levels by exploring the state space with a path-finding algorithm with a guiding heuristic. This is a nice demo of how you sometimes don't need sophisticated algorithm or machine learning to tackle complex problems.

Oxford's publications on algorithms, functional programming, and category theories. I peeked through a few articles. From those I learned novel ideas and enjoyed them.

An article on dithering techniques.

An interesting approach towards procedurely generated level/room/dungeon: specify various constraints and use a solver to place the objects on the tiles.

This is a not-so-short article teeming with "Aha!" moments.

1. reduce all branching in the solution to a math expression
2. converted to a lookup algorithm
3. we need a perfect hash function
4. use multiplication + shr as bit mixer
5. store answers directly in a single u32 integer
6. cram the answers even tighter with overlaps

The post shows off lot of tricks, very interesting read.

A collection of seemingly interesting data structure and algorithms.

A document by OpenAI on Deep Deterministic Policy Gradient (DDPG), a Q-learning like algorithm that works for continuous action space.

A fast path finding on square grid that exploits of certain properties to avoid scanning unecessary cells. There is a nice interactive visual demo on the webpage.

A simple and fast lossless image compression algorithm that achieves similar compression ratio but significantly faster than png.

An interesting and simple algorithm to blend two images seamlessly.

TL;DR: do not copy-paste the pixel itself, copy-paste the gradient of the pixel, and then solve for the optimal pixel's value subjecting to an energy function, which takes into account the boundary of background image and the gradient of the source image.

More articles on the topic:

• https://www.ctralie.com/Teaching/PoissonImageEditing/
• http://graphics.cs.cmu.edu/courses/15-463/2019_fall/lectures/lecture9.pdf

A short introduction to the idea behind the LSM tree.

Oversimplified:

1. The period of x mod N, x2 mod N, x3 mod N, x4 mod N, … sequence can reveal the factors of the product of two prime numbers.
2. The period is very difficult to find for large numbers.
3. Quantum Fourier Transform enables the extraction the period in a fast way. (the only part that quantum mechanics involved and I still can't understand how)

A discussion about unconventional data structures and algorithms.

<blockquote>starting point and ending point are</blockquote>