Skip to content

Instantly share code, notes, and snippets.

@mgritter
mgritter / henneberg.json
Last active July 25, 2021 01:50
Soffit grammar for Henneberg sequences generating minimal generically rigid graphs
{
"version": "0.1",
"start": "A--B",
"A; B": "B--N--A",
"A--B; C": "A--D; B--D; C--D"
}
@mgritter
mgritter / akita_capture_daemonset.yaml
Created July 13, 2021 17:58
Akita CLI Daemonset for production use
apiVersion: extensions/v1beta1
kind: DaemonSet
metadata:
name: akita-capture
namespace: superstar
spec:
selector:
matchLabels:
name: akita-capture
template:
@mgritter
mgritter / grid_coloring_z3.py
Created July 5, 2021 17:37
Grid problem solver with Z3
from z3 import *
import itertools
# A color type
num_colors = 8
Color, color_consts = EnumSort( 'Color',
[ f"{c}" for c in range(num_colors) ] )
# Edges
# --0,0-- --0,1-- --0,2-- horizontal
{
"version": "0.1",
"start": "K[kind]; K->N [name]; N",
"K[kind];": [
"K[kind]; K2[kind]; K2->N2 [name]; ",
"K[kind]; K2[category]; K2->N2 [name]; K2->K2[depth 0]",
"K[kind]; K2[category]; K2->N2 [name]; K2->K2[depth 1]",
"K[kind]; K2[category]; K2->N2 [name]; K2->K2[depth 2]",
"K[kind]; K2[mixin]; K2->N2 [name]; K2->K2[depth 0]",
"K[kind]; K2[mixin]; K2->N2 [name]; K2->K2[depth 1]",
@mgritter
mgritter / primes_mod_6.cpp
Last active May 9, 2021 04:20
Use primesieve to find the primes where the Chebyshev bias mod 6 is zero
#include <primesieve.hpp>
#include <iostream>
// Compile with: g++ -Wall -O3 -o primes_mod_6 primes_mod_6.cpp -lprimesieve
int main( int argc, char *argv[] ) {
primesieve::iterator it;
uint64_t prime = it.next_prime();
uint64_t count_mod_1 = 0;
uint64_t count_mod_5 = 0;
@mgritter
mgritter / euler_circuit.json
Created May 8, 2021 18:43
Soffit rule to generate Euler Circuits
{
"version": "0.1",
"start": "X[node]; Y[node]; Z[node]; XY[edge]; XY->X; XY->Y; YZ[edge]; YZ->Y; YZ->Z; ZX[edge]; ZX->X; ZX->Z; XY->YZ->ZX->XY [cycle]",
"Z[node]; PZ[edge]; PZ->Z; ZS[edge]; ZS->Z; PZ->ZS[cycle]":
"Z[node]; PZ[edge]; PZ->Z; ZS[edge]; ZS->Z; A[node]; ZA[edge]; ZA->Z; ZA->A; PZ->ZA [cycle]; B[node]; AB[edge]; AB->A; AB->B; ZA->AB [cycle]; BZ[edge]; BZ->B; BZ->Z; AB->BZ [cycle]; BZ->ZS[cycle]",
"A[node]; PA[edge]; PA->A; AS[edge]; AS->A; PA->AS[cycle]; B[node]; C[node];" :
"A[node]; PA[edge]; PA->A; AS[edge]; AS->A; B[node]; AB[edge]; AB->A; AB->B; PA->AB [cycle]; C[node]; BC[edge]; BC->B; BC->C; AB->BC [cycle]; CA[edge]; CA->C; CA->A; BC->CA [cycle]; CA->AS [cycle];"
}
@mgritter
mgritter / simple-boolean-proof.rkt
Last active March 16, 2021 21:09
Pie proof that (A OR B) = (NOT A IMPLIES B)
#lang pie
;; Define a boolean type
(claim Boolean U)
(define Boolean (Either Trivial Trivial))
(claim false Boolean)
(define false (left sole))
(claim true Boolean)
@mgritter
mgritter / berlekamp_massey.py
Created March 8, 2021 04:37
Example of Berlekamp-Massey algorithm
def linear_sequence( modulus, a_i, x_i, length ):
if len( a_i ) > len( x_i ):
raise Exception( "not enough seed elements" )
x_i = list( x_i )
n = len( x_i )
while n < length:
x_n = sum( c * x_i[n-i-1] for i, c in enumerate(a_i) ) % modulus
x_i.append( x_n )
n += 1
@mgritter
mgritter / kingplacement_dp.py
Created February 23, 2021 23:46
King placement problem, dynamic programming
import itertools
# A solution state is:
# number of rows placed
# location of kings in the bottom row
# total count of kings within each column
# (n,k1,k2,x_k)
def kingPositionsInRow( availableColumns ):
for k1, k2 in itertools.combinations( availableColumns, 2 ):
@mgritter
mgritter / kingplacement.py
Created February 23, 2021 23:22
King placement problem, brute force version
import itertools
# How many kings can be placed on an NxN board such that there are
# 2 kings in each row
# 2 kings in each column?
# No pair of attacking kings?
def kingPositionsInRow( availableColumns ):
for k1, k2 in itertools.combinations( availableColumns, 2 ):
if k2 == k1 + 1: