Skip to content

Instantly share code, notes, and snippets.

@pkhuong
pkhuong / yannakakis.md
Last active October 30, 2023 16:55
A minimal version of Yannakakis's algorithm for mostly plain Python
#!/usr/bin/env sed -re s|^|\x20\x20\x20\x20| -e s|^\x20{4}\x23\x23{(.*)$|<details><summary>\1</summary>\n| -e s|^\x20{4}\x23\x23}$|\n</details>| -e s|^\x20{4}\x23\x23\x20?|| -e s|\x0c|\x20|
license, imports
# Yannakakis.py by Paul Khuong
#
# To the extent possible under law, the person who associated CC0 with
# Yannakakis.py has waived all copyright and related or neighboring rights
# to Yannakakis.py.

@mitchellh
mitchellh / heap.zig
Last active September 14, 2023 08:44
Zig implementation of an intrusive heap based on pairing heaps
const std = @import("std");
const assert = std.debug.assert;
/// An intrusive heap implementation backed by a pairing heap[1] implementation.
///
/// Why? Intrusive data structures require the element type to hold the metadata
/// required for the structure, rather than an additional container structure.
/// There are numerous pros/cons that are documented well by Boost[2]. For Zig,
/// I think the primary benefits are making data structures allocation free
/// (rather, shifting allocation up to the consumer which can choose how they
# I happened to be looking at some of Cranelift's code, and I noticed that their constant-time dominates()
# check was using a somewhat more ad-hoc version of a hidden gem from the data structures literature called the
# parenthesis representation for trees. As far as I know, this was invented by Jacobson in his 1989 paper
# Space-Efficient Static Trees and Graphs. I first learned about it from the slightly later paper by Munro and Raman
# called Succinct Representations of Balanced Parentheses and Static Trees. I figured I'd give it an extremely
# quick intro and then show how it leads to a (slightly better) version of Cranelift's algorithm.
#
# This parenthesis representation of trees is surprisingly versatile, but its most striking feature is that
# it lets us query the ancestor relationship between two nodes in a tree in constant time, with a few instructions.
# And the idea is extremely simple and intuitive if you just draw the right kind of picture.
@lynaghk
lynaghk / taxes.smt2
Created August 1, 2022 18:34
S-Corp tax optimization with the Z3 Theorem Prover
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Solo freelancer's S-Corp tax optimization
;;
;; Assumes an unmarried single-shareholder and tons of other stuff.
;; I'm not a tax professional, no guarantees here, probably typos, etc. Come on!
;; Run with https://github.com/Z3Prover/z3
;;
;; See also my notes at https://kevinlynagh.com/financial-plan/
@redblobgames
redblobgames / sfc32.ts
Created May 10, 2022 16:21
sfc32 random number generator, typescript
// SFC32 random number generator, public domain code adapted
// from https://github.com/bryc/code/blob/master/jshash/PRNGs.md
function PRNG(seed: number): {
nextInt(): number;
nextFloat(): number;
getState(): number[];
setState(state: number[]): void
} {
let a = 0, b = seed, c = 0, d = 1;
function sfc32() {
@mitchellh
mitchellh / Atlas.zig
Last active March 8, 2024 03:10
Bin-packed texture atlas implementation in Zig. https://en.wikipedia.org/wiki/Texture_atlas
//! Implements a texture atlas (https://en.wikipedia.org/wiki/Texture_atlas).
//!
//! The implementation is based on "A Thousand Ways to Pack the Bin - A
//! Practical Approach to Two-Dimensional Rectangle Bin Packing" by Jukka
//! Jylänki. This specific implementation is based heavily on
//! Nicolas P. Rougier's freetype-gl project as well as Jukka's C++
//! implementation: https://github.com/juj/RectangleBinPack
//!
//! Limitations that are easy to fix, but I didn't need them:
//!
@pervognsen
pervognsen / shift_dfa.md
Last active January 27, 2024 19:54
Shift-based DFAs

A traditional table-based DFA implementation looks like this:

uint8_t table[NUM_STATES][256]

uint8_t run(const uint8_t *start, const uint8_t *end, uint8_t state) {
    for (const uint8_t *s = start; s != end; s++)
        state = table[state][*s];
    return state;
}
@lmcinnes
lmcinnes / doc_embeddings_with_vectorizers.ipynb
Last active November 9, 2023 04:31
Document Embeddings with the Vectorizers Library
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@rmitton
rmitton / hipparchus.c
Created August 30, 2020 02:27
Mandelbrot set rendered from a first-person viewpoint
// I don't know what I'm looking at here.
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>
#define OUTPUT "hipparchus.pgm"
#define WIDTH 1024
@pkhuong
pkhuong / dynamic-variance.py
Last active January 9, 2023 21:03
Fully dynamic variance for a bag of observations
import math
import struct
import unittest
import hypothesis.strategies as st
from hypothesis.stateful import Bundle, RuleBasedStateMachine, consumes, invariant, multiple, precondition, rule
class VarianceStack:
def __init__(self):
self.n = 0