jix

Wilson’s algorithm uses loop-erased random walks to generate a uniform spanning tree — an unbiased sample of all possible spanning trees. Most other maze generation algorithms, such as Prim’s, random traversal and randomized depth-first traversal, do not have this beautiful property.

The algorithm initializes the maze with an arbitrary starting cell. Then, a new cell is added to the maze, initiating a random walk (shown in magenta). The random walk continues until it reconnects with the existing maze (shown in white). However, if the random walk intersects itself, the resulting loop is erased before the random walk continues.

Initially, the algorithm can be frustratingly slow to watch, as the early random walks are unlikely to reconnect with the small existing maze. However, as the maze grows, the random walks become m

jix

#!/usr/bin/env python3
import os
import sys

argv = sys.argv[1:]

try:
    pkg_name = os.environ['CARGO_PKG_NAME']
except KeyError:
    pass

jix

import networkx as nx
import itertools


def transitive_closure_compression(g):
    # For a given DAG return a smaller (edge count) DAG with additional nodes
    # and a transitive closure that has the transitive closure of the original
    # DAG as induced subgraph.

    # It does this by generating a contraction hierachy (CH) and building a new

jix

# Copyright 2020 Jannis Harder
#
# Permission to use, copy, modify, and/or distribute this software for any
# purpose with or without fee is hereby granted.
#
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
# REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
# AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
# INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
# LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR

jix

# Copyright 2020 Jannis Harder
#
# Permission to use, copy, modify, and/or distribute this software for any
# purpose with or without fee is hereby granted.
#
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
# REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
# AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
# INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
# LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR

jix

import random

def draw_hand():
    hand = set()
    while len(hand) < 8:
        hand.add(random.randrange(40000))
    return list(hand)

def encode_perm(l, x):
    l = list(l)

jix

#include <pulse/simple.h>
#include <pulse/error.h>
#include <array>
#include <stdexcept>
#include <memory>
#include <iostream>
#include <complex>
#include <functional>
#include <GLFW/glfw3.h>
#include <fftw3.h>

jix

# Return a representative of each conjugacy class of maximal subgroups of a
# permutation group that stabilize a block or point. These are the maximal
# subgroups whose orbit parition is a strict refinement of the whole groups
# orbit partition.
#
# The result is a list of pairs containing the representative subgroup and the
# block or point for which it is the stabilizer. A point is returned as a block
# of size 1.
MaximalBlockStabilizerClassReps := function ( G )
    local i, pt, pt2, orb, lorb, on_lorb, l2g, block_reps, block_rep,

jix

# Copyright 2020 Jannis Harder
#
# Permission to use, copy, modify, and/or distribute this software for any
# purpose with or without fee is hereby granted.
#
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
# REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
# AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
# INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
# LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR

jix

#!/usr/bin/env python3
from livereload import Server, shell
import shlex
import sys
import os
import toml

config = toml.load('Cargo.toml')
cmd = 'cargo +nightly doc ' + shlex.join(sys.argv[1:])
server = Server()