Skip to content

Instantly share code, notes, and snippets.

Avatar

Reg Braithwaite raganwald

View GitHub Profile
@raganwald
raganwald / out.md
Last active May 4, 2020
Computing fib(7) with FRACTRAN
View out.md

We wish to compute fib(7).

This is a FRACTRAN program for computing any Fibonacci number: 17/65, 133/34, 17/19, 23/17, 2233/69, 23/29, 31/23, 74/341, 31/37, 41/31, 129/287, 41/43, 13/41, 1/13, 1/3.

The seed n is computed n = 78 * 5^(x - 1). Therefore, we start with n = 78 * 5^(7-1), which is 1,218,750.

  • The first fraction in the program is 17/65. 1,218,750 multiplied by 17/65 is 318,750, so we replace 1,218,750 with 318,750 and begin again.
  • The first fraction in the program is 17/65. 318,750 leaves a remainder when divided by 65, so we move on.
  • The next fraction in the program is 133/34. 318,750 multiplied by 133/34 is 1,246,875, so we replace 318,750 with 1,246,875 and begin again.
  • The first fraction in the program is 17/65. 1,246,875 leaves a remainder when divided by 65, so we move on.
View pushdown.oop.es6
const END = Symbol('end');
class PushdownAutomaton {
constructor(internal = 'start', external = []) {
this.internal = internal;
this.external = external;
this.halted = false;
this.recognized = false;
}
@raganwald
raganwald / enumerations.es6
Last active Mar 9, 2019
Code from "Enumerations, Denumerables, and Cardinals"
View enumerations.es6
// See: http://raganwald.com/2019/02/27/enumerability.html
// combinators
function slice (generator, n, limit = Infinity) {
return function * sliced () {
let i = 0;
for (const element of generator()) {
if (i++ < n) continue;
View parentheses-and-palindromes.es6
// Inspired by:
//
// "Eh, have another semi-periodic reminder that ()() is not a palindrome but ())( is"
//
// --https://twitter.com/_julesh_/status/1101262745092218882
const END = Symbol('end');
class PushdownAutomaton {
constructor(internal = 'start', external = []) {
@raganwald
raganwald / generate-balanced-parentheses.es6
Last active Mar 1, 2019
A generator function that enumerates all finite balanced parentheses strings
View generate-balanced-parentheses.es6
// memoizes ordinary functions
const memoized = (fn, keymaker = JSON.stringify) => {
const lookupTable = new Map();
return function (...args) {
const key = keymaker.call(this, args);
return lookupTable[key] || (lookupTable[key] = fn.apply(this, args));
}
};
@raganwald
raganwald / balanced-dpa.es6
Last active Feb 16, 2019
A Deterministic Pushdown Automaton ("DPA") that recognizes balanced parentheses
View balanced-dpa.es6
// The Deterministic Pushdown Automata Engine
const END = Symbol('end');
const RECOGNIZED = Symbol('recognized');
const UNRECOGNIZED = Symbol('unrecognized');
const POP = Symbol('pop');
function DPA (start) {
return string => {
const stack = [];
@raganwald
raganwald / implicit.js
Last active Feb 15, 2019
Balanced parentheses solution with implicit state
View implicit.js
function balanced (string) {
const iterator = string[Symbol.iterator]();
return balancedIterator(iterator) === true;
}
const CLOSE = {
'(': ')',
'[': ']',
'{': '}'
@raganwald
raganwald / why-indeed.js
Last active Feb 12, 2019
Recursive Pattern Matching using the Why Combinator
View why-indeed.js
const just =
target =>
input =>
input.startsWith(target) &&
target;
const cases =
(...patterns) =>
input => {
const matches = patterns.map(p => p(input)).filter(m => m !== false);
View slice.es6
//
// http://raganwald.com/2019/01/14/structural-sharing-and-copy-on-write.html
// http://raganwald.com/2019/01/26/reduce-reuse-recycle.html
//
const SliceHandler = {
has (slice, property) {
if (property in slice) {
return true;
}
@raganwald
raganwald / lisp.js
Last active Jan 11, 2019
A very leaky abstraction that Greenspuns Lisp's CAR/CDR, plus support for [first, ...rest]
View lisp.js
const ComposableCarCdr = {
has (target, name) {
if (name in target) {
return true;
}
if (name === Symbol.isConcatSpreadable) {
return true;
}
You can’t perform that action at this time.