Skip to content

Instantly share code, notes, and snippets.

View tuzz's full-sized avatar

Chris Patuzzo tuzz

View GitHub Profile
@tuzz
tuzz / superpermutation-spiral.html
Created March 6, 2019 04:04
A very quick experiment to draw superpermutations as colored spirals moving out from the center.
<center>
<canvas id="canvas" width="1000" height="1000"></canvas>
</center>
<script>
var canvas = document.getElementById("canvas");
var context = canvas.getContext("2d");
var done = false;
function circle_around(callback) {
@tuzz
tuzz / simplesupersat.rb
Created January 4, 2019 13:36
A greatly simplified version of https://github.com/tuzz/supersat
# This is a greatly simplified version of https://github.com/tuzz/supersat
# It reduces the superpermutation problem to boolean satisfiability.
#
# To generate a SAT problem for N=3, LENGTH=9:
# ruby simplesupersat.rb 3 9
#
# And to run a SAT solver on it:
# lingeling 3-9.dimacs
N = Integer(ARGV[0])
@tuzz
tuzz / subset.snt
Last active October 22, 2018 17:25
A proof-of-concept Sentient program for a set membership problem.
# A proof-of-concept Sentient program for a set membership problem.
# $ sentient subset.snt --assign '{ target: [1, 1, 0, 1], max_selections: 2 }'
#
# Outputs: {"members":[false,false,false,false,true,false,false,false,true,false,false,false]}
# Corresponding to: uk - scotland
# Given: a set of all the countries in the world, and a set of possible
# groupings of those countries (e.g. “Scandinavia” or “Central America”, or
# “All”), given a set of arbitrary countries, I want to compute the most concise
@tuzz
tuzz / superpermutation.rb
Created October 19, 2018 14:07
Reduce the problem of finding superpermutations of N digits to SAT
# Attempts to find a superpermutation for a given number of digits that fit into a given string length.
# https://en.wikipedia.org/wiki/Superpermutation
#
# Run: ruby superpermutation.rb | lingeling -f
#
# The program will be satisfiable if it is possible, but won't actually print the solution.
# I need to add some code to decode the output.
digits = 4
length = 33
@tuzz
tuzz / zip_if.rs
Last active September 17, 2018 12:01
An attempt to write a function 'zip_if' in Rust
// Implements: https://gist.github.com/jcoglan/adc4ec173017e48f5ce68d6568fc5860
//
// The basic idea is we store a vector of cursors that advance through the
// nested list and build up the result. If the predicate for the current
// element is false we append a row padded with zeroes, otherwise we move
// along to the next nested list until we reach the last one. When we do,
// we append the fully saturated row to the result and move to the next
// element in each of the nested lists.
//
// At the end we need to check if there are any elements that matched the
@tuzz
tuzz / state-transitions.rs
Created August 6, 2018 19:10
A Rust proof-of-concept from the August 2018 Rust meeting in London.
/* This is a proof-of-concept, inspired by clojure, that stores just the
* transitions between multiple Foo structs, rather than copying the entire
* struct's fields each time.
*/
#[derive(Default)] // <-- this derives Foo::default() which creates a Foo struct
// with a and b initialized to zero.
struct Foo {
a: u8,
b: u8,
// A simple implementation of a Markov Model in Rust
#[derive(Debug, PartialEq)]
struct State {
name: &'static str,
}
struct Transition<'a> {
from: &'a State,
to: &'a State,
@tuzz
tuzz / puzzle.jpg
Last active February 8, 2018 08:23
A quick attempt to solve a Sliding puzzle problem with Sentient.
puzzle.jpg
(set-option :pp.bv-literals false)
(define-sort I () (_ BitVec 300))
(declare-const a I)
(declare-const b I)
(declare-const c I)
(declare-const d I)
(declare-const e I)
(declare-const f I)
(declare-const g I)
@tuzz
tuzz / isbn_magic_square_mashup.snt
Last active July 31, 2017 18:37
Exploring the overlap between ISBNs and magic squares
# A Sentient program to encode ISBN-10s, ISBN-13s, their check
# digits and how they relate.
# Declare all parts of the ISBN including check digits.
int5 ten0, ten1, ten2, ten3, ten4, ten5, ten6, ten7, ten8;
int5 ten_check_digit, thirteen_check_digit;
# State that all digits must be between 0 and 9 inclusive aside
# from ISBN-10 check digits which can include 10.
invariant ten0 >= 0, ten0 <= 9;