SICP exercise 1.12

pascal's-triangle.js

/*
Pascal's Triangle
     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1

The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of
the two numbers above it. Write a procedure that computes elements of Pascal's triangle by means of
a recursive process.

The elements of Pascal's triangle are called the binomial coefficients, because the nth row consists
of the coefficients of the terms in the expansion of (x + y)n. This pattern for computing the
coefficients appeared in Blaise Pascal's 1653 seminal work on probability theory, Traité du triangle
arithmétique. According to Knuth (1973), the same pattern appears in the Szu-yuen Yü-chien
(``The Precious Mirror of the Four Elements''), published by the Chinese mathematician Chu Shih-chieh
in 1303, in the works of the twelfth-century Persian poet and mathematician Omar Khayyam, and in the
works of the twelfth-century Hindu mathematician Bháscara Áchárya.
*/

let {drop, dropLast, map, zip} = require("ramda")

let sumPairs = map(([x1, x2]) => x1 + x2)
let pair = (xs) => zip(dropLast(1, xs), drop(1, xs))

function* makeRow(prevRow) {
  if (prevRow.length) {
    let prevRowX = [0, ...prevRow, 0]
    let res = sumPairs(pair(prevRowX))
    yield res
    yield* makeRow(res)
  } else {
    yield [1]
    yield* makeRow([1])
  }
}

let gen = makeRow([])
console.log(gen.next().value) // [ 1 ]
console.log(gen.next().value) // [ 1, 1 ]
console.log(gen.next().value) // [ 1, 2, 1 ]
console.log(gen.next().value) // [ 1, 3, 3, 1 ]
console.log(gen.next().value) // [ 1, 4, 6, 4, 1 ]
console.log(gen.next().value) // [ 1, 5, 10, 10, 5, 1 ]
console.log(gen.next().value) // [ 1, 6, 15, 20, 15, 6, 1 ]

// 0 1 0
//  1 1

// 0 1 2 1 0
//  1 3 3 1

// 0 1
// 1 2
// 2 1
// 1 0