Skip to content

Instantly share code, notes, and snippets.

View mgritter's full-sized avatar

Mark Gritter mgritter

53 followers · 19 following
View GitHub Profile
@mgritter
mgritter / randomgraph5.json
Last active August 21, 2020 05:56
Soffit grammar: random graph with five nodes, G(5,1/2) model
{
"version": "0.1",
"X--Y [?]": [
"X--Y",
"X; Y"
],
"start": "A--B--C--D--E--A--D--B--E--C--A [?]"
}
@mgritter
mgritter / randomwalk.json
Created June 3, 2020 06:47
Soffit grammar for a random-walk SVG
{
"version" : "0.1",
"start" : "C100[hundred_circles]; PP[+]; PP->HH; HH[100]; PREV[px]; PREV2[py]; PREV->PP; PREV2->PP",
"C[ten_circles]" : "C0[cc]; C1[cc]; C2[cc]; C3[cc]; C4[cc]; C5[cc]; C6[cc]; C7[cc]; C8[cc]; C9[cc]",
"C[hundred_circles]" : "C0[ten_circles]; C1[ten_circles]; C2[ten_circles]; C3[ten_circles]; C4[ten_circles]; C5[ten_circles]; C6[ten_circles]; C7[ten_circles]; C8[ten_circles]; C9[ten_circles]",
"C[cc]" : "C[circle]; C->CX[cx]; C->CY[cy]; C->R[r]; R[10]; CX[rand_x]; CY[rand_y]; C->STROKE[stroke]; STROKE[randcolor]; C->FILL[fill]; FILL[none]",
"X[rand_x]; PREV[px]; PLUS[+]; PREV->PLUS" :
@mgritter
mgritter / grid_coloring.py
Created May 14, 2020 20:04
NxN grids partitioned into two contiguous regions
import itertools
# left is the partitions for zero, right is the partitions for 1
def canonical_label( label ):
left, right = label
nl = [ list(sorted(left_perm)) for left_perm in left ]
nr = [ list(sorted(right_perm)) for right_perm in right ]
nl.sort()
nr.sort()
return (nl,nr)
@mgritter
mgritter / main.go
Created March 22, 2020 20:12
Memory locality profiling example
package main
import (
"fmt"
"math/rand"
)
func randArray(n int, maxVal int) [][]int {
a := make([][]int, n)
for i := range a {
@mgritter
mgritter / results.txt
Last active March 11, 2020 16:44
12x12 knights attacking three knights puzzle
Searching for 4 pieces.
Success!
#W# # # # #
# B # # # #
B B # # # #
#W#W# # # #
#W# # # # #
# B # # # #
# # # # # #
# # # # # #
@mgritter
mgritter / numberchoicegame.py
Created January 16, 2020 04:45
Brute-force solver for a simple number game
import itertools
def top_options( options, player_number ):
options.sort( reverse=True, key=lambda x : x[1][player_number] )
best_score = options[0][1][player_number]
ties = list( itertools.takewhile( lambda x : x[1][player_number] == best_score,
options ) )
return ties
def worst_options_for_me( options, player_number ):
@mgritter
mgritter / output.txt
Last active November 19, 2019 08:00
LP solver for three-card-poker, one round of limit betting
Starting solver...
6669 variables
6669 constraints
hand F CF CC CRF CRC RF RC RR
-------- ------- ------- ------- ------- ------- ------- ------- -------
AKQs 1.00000
KQJs 1.00000
QJTs 1.00000
JT9s 1.00000
T98s 1.00000
@mgritter
mgritter / projection_onto_simplex.py
Created November 13, 2019 05:38
Chen and Ye's algorithm for simplex projection
def project_onto_standard_simplex( y ):
"""Find the nearest neighbor of y on the |y|-element standard simplex
x_1 + ... + x_n = 1
See Yunmei Chen and Xiaojing Ye, "Projection Onto a Simplex",
https://arxiv.org/abs/1101.6081
"""
n = len( y )
y_s = sorted( y, reverse=True )
@mgritter
mgritter / dethilbert.py
Created October 28, 2019 02:13
A sequence of determinants of points along a Hilbert curve
#!/usr/bin/python3
import matplotlib.pyplot as plt
# Code adapted from https://en.wikipedia.org/wiki/Hilbert_curve
def rot( n, x, y, rx, ry ):
if ry == 0:
if rx == 1:
x = (n-1) - x
y = (n-1) - y
@mgritter
mgritter / dethilbert.py
Created October 28, 2019 02:13
A sequence of determinants of points along a Hilbert curve
#!/usr/bin/python3
import matplotlib.pyplot as plt
# Code adapted from https://en.wikipedia.org/wiki/Hilbert_curve
def rot( n, x, y, rx, ry ):
if ry == 0:
if rx == 1:
x = (n-1) - x
y = (n-1) - y