Skip to content

Instantly share code, notes, and snippets.

Reg Braithwaite raganwald

Block or report user

Report or block raganwald

Hide content and notifications from this user.

Learn more about blocking users

Contact Support about this user’s behavior.

Learn more about reporting abuse

Report abuse
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.