Skip to content

Instantly share code, notes, and snippets.

orlp /
Last active Nov 19, 2020
A succint numpy implementation of Vose's Alias Method, an O(n) construction O(1) sampling time algorithm for a fixed, weighted distribution.
import numpy as np
from collections import deque
class VoseAliasMethod:
# Vose's Alias Method as described at
def __init__(self, weights):
pmf = weights / np.sum(weights)
self.n = pmf.shape[0]
self.prob = np.zeros(self.n, dtype=np.float64)
self.alias = np.zeros(self.n, dtype=np.int64)
use std::collections::{HashSet, HashMap};
#[derive(Clone, Debug)]
struct CountBucket {
prev: i64,
next: i64,
indices: HashSet<usize>,
use slotmap::{SlotMap, SecondaryMap, new_key_type, Key};
use std::collections::HashSet;
new_key_type! {
struct BucketKey;
new_key_type! {
struct IndexKey;
import collections
import numpy as np
import scipy.sparse
import scipy.sparse.linalg
import sys
import imageio
import io
import base64
class MazeJudge:
import numpy as np
def expected_time_to_solve(N):
A = np.zeros((4*(N+2), 4*(N+2)))
# (n, forward) => (4n + 0), (n, backward) => (4n + 1), (n, inside) => (4n + 2), (n, facewall) => (4n + 3)
for i in range(4*(N+2)):
if i < 4:
A[i,4] = 1
elif i >= 4*(N+1):
A[i,i] = 1
import itertools as it
import networkx as nx
import math
K = 3
N = math.factorial(K) + K - 1
print("Constructing sets")
left = list(it.permutations(range(N)))
right = sorted({(p[:cloth] + p[cloth+K:], cloth) for p, cloth in it.product(it.permutations(range(N)), range(N-K+1))})

Villager mechanics in 1.14. All this data has been deduced by using the following commands:

/data get entity @e[type=minecraft:villager,limit=1,sort=nearest] Brain.memories
/execute as orlp at orlp run tellraw @s {"nbt":"Brain.memories","entity":"@e[type=villager,sort=nearest,limit=1]"}

A villager is awake from 0-11999 and tries to sleep between 12000 and 23999.

A villager will claim a bed if:

View quantize_with_dither.glsl
// Original idea by Mikkel Gjoel (,
// simplified to one readable function.
// Demo at
// Dithers and quantizes color value c in [0, 1] to the given color depth.
// It's expected that rng contains a uniform random variable on [0, 1].
uint dither_quantize(float c, uint depth, float rng) {
float cmax = float(depth) - 1.0;
float ci = c * cmax;
from collections import namedtuple, defaultdict
EarleyItem = namedtuple("EarleyItem", ["rule", "dot", "origin"])
def item_advance(item):
return EarleyItem(rule=item.rule, + 1, origin=item.origin)
class Generator:
def __init__(self, G, terminals):
self.G = [["S'", G[0][0]]] + list(G)
import sympy as sp
import itertools as it
from sympy.physics.quantum import TensorProduct
def companion_matrix(p):
"""Gives companion matrix for polynomial p."""
p = sp.Poly(p)
assert p.is_monic