mgritter’s gists

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 / 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 / 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 / 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:

mgritter / combinatorial_game.json

Last active September 6, 2020 19:54

Soffit grammar for creating combinatorial games (and labeling some games.)

	{
	"version": "0.1",
	"start": "G[game]",

	"G[game]": [
	"G[game]; Z[game]; G->Z [left];",
	"G[game]; Z[game]; G->Z [right];"
	],
	"G[game]; L[game]; G->L[left]": "G[game]; L2[0]; G->L2[left]",
	"G[game]; R[game]; G->R[right]": "G[game]; R2[0]; G->R2[right]",

mgritter / recursive_vs_iterative_dfs.go

Created September 2, 2020 01:28

Demonstrating recursion vs. iteration

	package main

	import (
	"fmt"
	"time"
	)

	type TreeNode struct {
	Goal bool
	Children map[string]*TreeNode

mgritter / busy_beaver_4.json

Created August 24, 2020 01:23

Soffit grammar implementing the Busy-Beaver Turing machine with four states and tape symbols 0/1.

	{
	"E->TAPE; E[end];\nH[head]; H->TAPE": "NE[end]; NE->E->TAPE;\nE->ZERO; ZERO[0];\nH[head]; H->TAPE;",
	"E<-TAPE; E[end];\nH[head]; H->TAPE": "NE[end]; NE<-E<-TAPE;\nE->ZERO; ZERO[0];\nH[head]; H->TAPE;",
	"HEAD[head]; STATE[a]; HEAD->STATE [state];\nHEAD->TAPE; TAPE->VAL; VAL[0];\nTAPE->RIGHT;": "HEAD[head]; STATE[b]; HEAD->STATE [state];\nHEAD->RIGHT; TAPE->VAL; VAL[1];\nTAPE->RIGHT;",
	"HEAD[head]; STATE[a]; HEAD->STATE [state];\nHEAD->TAPE; TAPE->VAL; VAL[1];\nLEFT->TAPE;": "HEAD[head]; STATE[b]; HEAD->STATE [state];\nHEAD->LEFT; TAPE->VAL; VAL[1];\nLEFT->TAPE;",
	"STATE[b]; VAL[0];\nHEAD[head]; HEAD->STATE [state];\nHEAD->TAPE; TAPE->VAL; LEFT->TAPE;": "VAL[1]; HEAD->LEFT; STATE[a];\nHEAD[head]; HEAD->STATE [state];\nTAPE->VAL; LEFT->TAPE;",
	"STATE[b]; VAL[1];\nHEAD[head]; HEAD->STATE [state];\nHEAD->TAPE; TAPE->VAL; LEFT->TAPE;": "VAL[0]; HEAD->LEFT; STATE[c];\nHEAD[head]; HEAD->STATE [state];\nTAPE->VAL; LEFT->TAPE;",
	"STATE[c]; VAL[0];\nHEAD[head]; HEAD->STATE [state];\nHEAD->TAPE; TAPE->V

mgritter / rgb_graph_101.json

Created August 22, 2020 04:23

Soffit grammar demonstrating a DPO guard

	{
	"C[hundred]; D[guard]; D->C": "T1[ten]; T2[ten]; T3[ten]; T4[ten]; T5[ten]; T6[ten]; T7[ten]; T8[ten]; T9[ten]; T10[ten]; D[guard];\nD->T1; D->T2; D->T3; D->T4; D->T5; D->T6; D->T7; D->T8; D->T9; D->T10;",
	"X[ten]; D[guard]; D->X": "N1[one]; N2[one]; N3[one]; N4[one]; N5[one]; N6[one]; N7[one]; N8[one]; N9[one]; N10[one]; D[guard];\nD->N1; D->N2; D->N3; D->N4; D->N5; D->N6; D->N7; D->N8; D->N9; D->N10;",
	"N; COUNT[one]; D[guard]; D->COUNT;": "N->NN; D[guard]",
	"D[guard];": "E[color];",
	"E[color]; N": [
	"E[color]; N[style=filled; fillcolor=red; label=\"\"]",
	"E[color]; N[style=filled; fillcolor=blue; label=\"\"]",
	"E[color]; N[style=filled; fillcolor=green; label=\"\"]"
	],

mgritter / tree-101.json

Created August 21, 2020 06:05

Soffit grammar: 101-node tree

	{
	"version": "0.1",
	"C[hundred];": "T1[ten]; T2[ten]; T3[ten]; T4[ten]; T5[ten]; T6[ten]; T7[ten]; T8[ten]; T9[ten]; T10[ten];",
	"X[ten];": "N1[one]; N2[one]; N3[one]; N4[one]; N5[one]; N6[one]; N7[one]; N8[one]; N9[one]; N10[one];",
	"N; COUNT[one];": "N->NN",
	"start": "C[hundred]; R;"
	}

mgritter / binary_tree_with_color.json

Last active August 21, 2020 05:53

Soffit grammar: binary tree with colored nodes

	{
	"version" : "0.1",

	"N[leaf]" :
	"N[internal]; L1[leaf]; L2[leaf]; N->L1; N->L2",

	"N[leaf]; N1[leaf]; N2[leaf];" :
	"N[style=filled; fillcolor=green; label=\"\"; shape=circle]; N1[leaf]; N2[leaf];",

	"X[internal]":

Mark Gritter mgritter