{{ message }}

Instantly share code, notes, and snippets.

robotlolita/0-instructions.md

Last active Aug 29, 2015
BECAUSE TYPE SYSTEMS ARE SUPPOSED TO RUN COMPUTATIONS!!1!1!

Write a program in your favourite programming language to compute the sum of the first N even numbers in the Fibonacci sequence, then display the sum of its digits.

E.g.: Where N = 5, the answer is 17, since:

1. The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...;
2. The first 5 even numbers are 0, 2, 8, 34, and 144;
3. The sum of these numbers is 188;
4. The sum of the digits of this answer is 17 (1 + 8 + 8).

The implementation below is written in typo: https://github.com/seliopou/typo, a Scheme dialect that runs on Haskell's type system.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ;; Co-recursive definition of Fibonacci for K index ;; N N N → N (define (fib k a b) (if (== k 0) a (fib (- k 1) b (+ a b)))) ;; Sums the digits of a number ;; N → N (define (sum_digits n) (if (== n 0) 0 (+ (% n 10) (sum_digits (/ n 10))))) ;; Tests if a number is even ;; N → B (define (isEven n) (== 0 (% n 2))) ;; Sums the first even KK elements of Fibonacci ;; N N N → N (define (sum_seq kk k) (if (== kk 0) 0 (let (a (fib k 0 1)) (if (isEven a) (+ a (sum_seq (- kk 1) (+ k 1))) (sum_seq kk (+ k 1)))))) (sum_digits (sum_seq 5 0)) ;; Run with: cat 1-fibs.typo.scm | typo