Skip to content

Instantly share code, notes, and snippets.

Avatar

Reg Braithwaite raganwald

View GitHub Profile
@raganwald
raganwald / pyramid_problem.js
Created January 14, 2022 15:07
Sketching out some solutions to the Pyramid Problem
View pyramid_problem.js
// handles primitives like integers and arrays of simple primitives
// all other behaviour is undefined
function superSimpleEquivalent(a, b) {
if (a instanceof Array && b instanceof Array) {
if (a.length != b.length) return false;
for (let i = 0; i < a.length; ++i) {
if (!superSimpleEquivalent(a[i], b[i])) return false;
}
@raganwald
raganwald / out.md
Last active May 4, 2020 18:19
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.
@raganwald
raganwald / pushdown.oop.es6
Created September 21, 2019 21:46
Pushdown Automata
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 March 9, 2019 20:28
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 March 1, 2019 03:13
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 February 16, 2019 16:39
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 February 15, 2019 08:31
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 February 12, 2019 13:01
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;
}