JavaScript
ProjectEuler
関数型プログラミング
ramda

関数型で Project Euler を解く

#001: こてしらべ

1000 未満の 3 もしくは 5 の倍数の合計R.range で1..1000の配列を作って、filter して sum:

const app = R.pipe(
  R.range,
  R.filter(x => x % 3 === 0 || x % 5 === 0),
  R.sum,
);

app(1, 1000); // -> 233168

#002: ジェネレータ + takeWhile

400万以下で偶数のフィボナッチ数の総和。フィボナッチ数はジェネレータで生成。R.takeWhile をつかって打ち切る:

function* fib() {
  yield 1;
  yield 1;
  for (let [a, b] = [1, 1]; ; [a, b] = [b, a + b]) yield a + b;
}

const xForm = R.compose(
  R.takeWhile(x => x < 4e6),
  R.filter(x => x % 2 === 0),
);

const app = R.transduce(xForm, R.add, 0);

app(fib()); // -> 4613732

#003: 再帰

N = 600851475143 の最大素因数。これを app(N) とおこう。1..√N までに N を割り切る数が存在しなければ、N は素数なので app(N) = N 。もし存在する場合、それを x とおくと(注:この手順だとx は素数) app(N) = max(x, app(N/x)) と、再帰に帰着。なお、1..√N は配列だと少し大きいので、ジェネレータ rangeG で持つことにした:

function* rangeG(start, end, step = 1) {
  for (let i = start; i < end; i += step) yield i;
}

const app = (n) => {
  const reducer = (_, x) => (n % x === 0 ? R.reduced(R.max(x, app(n / x))) : null);
  const reduced = R.reduce(reducer, null, rangeG(2, Math.ceil(Math.sqrt(n) + 1)));
  return reduced || n;
};

app(600851475143); // -> 6857

#004: ジェネレータ + take

3桁×3桁で作られる最大の回文数 (注: 回文数とは前から読んでも後ろから読んでも同じ数字を表す数)。999 * 999 から 1 ずつ小さくしていった数字のうち、回文数条件を満たし、かつ 100...999 で割り切れてその商も 100..999 になるという条件で filter して、 take(1) する:

function* gen() {
  for (let i = 999 * 999; i > 100 * 100; i -= 1) yield i;
}

const isPalindromic = n => n === R.pipe(R.toString, R.reverse, parseInt)(n);

const isComposedBy3digits = n => R.range(100, 1000)
  .some(x => n % x === 0 && n / x > 99 && n / x < 1000);

const app = R.into('', R.compose(
  R.filter(isPalindromic),
  R.filter(isComposedBy3digits),
  R.take(1),
));

app(gen()); // -> 906609

#005: 再帰

1..20の各数で割り切れる最小の数。これは最小公倍数を求めるという算数の問題で、プログラム上の工夫はあんまりない。ユークリッドの互除法という最大公約数を求めるアルゴリズムは再帰構造をとる、くらいか:

const gcd = (a, b) => {
  if (a < b) return gcd(b, a);
  if (a % b === 0) return b;
  return gcd(b, a % b);
};

const gcm = (a, b) => a * b / gcd(a, b);

const app = R.pipe(
  R.range,
  R.reduce(gcm, 1),
);

app(1, 21); // -> 232792560

#006: こてしらべ

1..100の和の二乗と、二乗の和の差。特にいうことはないね:

const app = R.pipe(
  R.range,
  arr => R.sum(arr) ** 2 - R.sum(arr.map(x => x ** 2)),
);

app(1, 101); // -> 25164150

#007: ジェネレータ + drop

10001番目の素数。素数を出力するジェネレータに、先頭から 10000 個をdrop して take(1) する:

const isPrime = n => R.range(2, Math.ceil(Math.sqrt(n)) + 1).every(x => n % x !== 0);

function* primes() {
  yield 2;
  for (let i = 3; ; i += 2) {
    if (isPrime(i)) yield i;
  }
}

const app = R.into('', R.compose(R.drop(10000), R.take(1)));

app(primes());  // -> 104743

#008: aperture

連続する13数値の積の最大値。この操作は aperture と呼ばれ、R.aperture が使える:

const DATA = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450';

const app = R.pipe(
  R.aperture,
  R.map(R.product),
  R.reduce(R.max, 0),
);

app(13, DATA); // -> 23514624000

#009: 組み合わせ

足して1000となるピタゴラス数。1..1000 の数を二つ選んで直角三角形ができるかを判定する。一般性を失わずに a <= b とできるので、組み合わせ総数は 1000 * 1000 よりも少し小さくできる:

const isSquare = n => n === Math.floor(Math.sqrt(n)) ** 2;

const app = R.pipe(
  () => R.range(1, 1000),
  R.map(a => R.range(a, 1000).map(b => [a, b])),
  R.unnest, // -> [[a, b]]
  R.find(([a, b]) => {
    const c2 = a ** 2 + b ** 2;
    return isSquare(c2) && a + b + Math.sqrt(c2) === 1000;
  }),
  ([a, b]) => a * b * Math.sqrt(a ** 2 + b ** 2),
);

app(); // -> 31875000

#010: やや複雑なジェネレータ

200万以下の素数の総和。#007 の方法で基本いけるが、わずかに改良して 数秒で終わるようにする。改良点は以下

  • ジェネレータ内で評価する素数候補を 1, 5 mod 6 の整数に限定
    • それ以外の数値は2 または 3 で割り切れるので候補たりえない
const isPrime = n => R.range(3, Math.ceil(Math.sqrt(n)) + 1, 2).every(x => n % x !== 0);

function* primes() {
  yield 2;
  yield 3;
  yield 5;
  for (let base = 6; ; base += 6) {
    if (isPrime(base + 1)) yield base + 1;
    if (isPrime(base + 5)) yield base + 5;
  }
}

app = R.reduceWhile((acc, x) => x < 2e6, R.add, 0);

app(primes()); // -> 142913828922

このサイズになるとエラトステネスのふるいが正着だろうが、まあよい。