Euler Project: Problem 5 in Clojure

I solved the fifth problem from Euler project in Clojure.

My first approach was not successful:

	(def positive-integers (iterate inc 1))
	(def evenly-divisible?
	(comp zero? rem))
	(defn evenly-divisible-by-numbers? [from to number]
	(let [numbers (range from (+ to 1))]
	(every? (partial evenly-divisible? number) numbers)))
	(defn positive-numbers-evenly-divisible-by-numbers [from to]
	(filter (partial evenly-divisible-by-numbers? from to)
	positive-integers))
	(first
	(positive-numbers-evenly-divisible-by-numbers 1 10)) ; 2520
	;(first
	; (positive-numbers-evenly-divisible-by-numbers 1 20))
	; java.lang.OutOfMemoryError: GC overhead limit exceeded

view raw euler-5-1.clj hosted with ❤ by GitHub

Even though it could compute the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder, it didn't work for 1 to 20.
It consumed to much memory.

So I used pen and paper to devise a better approach to solve the problem.

I saw that the numbers from 1 to 10 which multiplied produce 2520 are 9, 8, 7 and 5.
What these numbers have in common is that they all have one prime factor with the highest possible multiplicity in the 1 to 10 range.

This is the code that I derived from those two facts:

	(def factor?
	(comp zero? rem))
	(defn prime-factors [n]
	(loop [n n prime 2 factors []]
	(cond
	(= n 1) factors
	(factor? n prime) (recur (/ n prime) prime (conj factors prime))
	:else (recur n (inc prime) factors))))
	(defn unique-factor? [factors]
	(and (not (empty? factors))
	(apply = factors)))
	(defn extract-divisors [numbers-with-unique-factor]
	(loop [numbers-with-unique-factor numbers-with-unique-factor
	divisors [] factors []]
	(if (empty? numbers-with-unique-factor)
	divisors
	(let [factor (first (second (first numbers-with-unique-factor)))]
	(if (some #{factor} factors)
	(recur (rest numbers-with-unique-factor)
	divisors
	factors)
	(recur (rest numbers-with-unique-factor)
	(conj divisors (first (first numbers-with-unique-factor)))
	(conj factors factor)))))))
	(extract-divisors
	(filter #(unique-factor? (second %))
	(map #(vector % (prime-factors %))
	(reverse (range 1 10))))) ; [9 8 7 5]
	(extract-divisors
	(filter #(unique-factor? (second %))
	(map #(vector % (prime-factors %))
	(reverse (range 1 20))))) ; [19 17 16 13 11 9 7 5]
	(defn smallest-evenly-divisible-by-all [from to]
	(reduce
	*
	(extract-divisors
	(filter #(unique-factor? (second %))
	(map #(vector % (prime-factors %))
	(reverse (range from (+ to 1))))))))
	(smallest-evenly-divisible-by-all 1 10) ; 2520
	(smallest-evenly-divisible-by-all 1 20) ; 232792560

view raw euler-5-2.clj hosted with ❤ by GitHub

which yields the right result.

Update:

As Leo pointed out in his comment, the answer is the least common multiple of the numbers from 1 to 20.

This is the final (more elegant and much simpler than the previous one) solution to the problem:

	(defn greatest-common-divisor [a b]
	(if (zero? b)
	a
	(greatest-common-divisor b (rem a b))))
	(defn least-common-multiple [a b]
	(/ (* a b) (greatest-common-divisor a b)))
	(defn smallest-positive-number-evenly-divisible-by-all [from to]
	(reduce
	least-common-multiple
	(range from (+ to 1))))
	(smallest-evenly-divisible-by-all 1 10) ; 2520
	(smallest-evenly-divisible-by-all 1 20) ; 232792560

view raw euler-5-3.clj hosted with ❤ by GitHub

Euler Project: Problem 4 in Clojure

This is my solution in Clojure to the fourth problem from Euler project:

	(reverse (range 100 1000)) ; (999 998 997 996 995 994 ...)
	(defn palindrome? [number]
	(let [num-str (str number)]
	(= num-str (apply str (reverse num-str)))))
	(palindrome? 9009) ; true
	(palindrome? 9008) ; false
	(apply
	max
	(filter
	palindrome?
	(let [numbers (reverse (range 10 100))]
	(for [x1 numbers x2 numbers]
	(* x1 x2))))) ; 9009
	(defn products [lower higher]
	(let [numbers (reverse (range lower (+ higher 1)))]
	(for [x1 numbers x2 numbers]
	(* x1 x2))))
	(defn largest-palindrome-product [lower higher]
	(apply max (filter palindrome? (products lower higher))))
	(largest-palindrome-product 10 99) ; 9009
	(largest-palindrome-product 100 999) ; 906609

view raw euler-4.clj hosted with ❤ by GitHub

It was nice to practise with for.

Books I read (January - August 2014)

January
- Pan, educación, libertad (Ψωμί, παιδεία, ελευθερία), Petros Márkaris
- NW London, Zadie Smith
- 101 cuentos clásicos de la China, Chang Shiru, Ramiro A. Calle
- Mr. Neighborly's Humble Little Ruby Book, Jeremy McAnally

February
- Blankets, Craig Thompson

March
- Practical Object-Oriented Design in Ruby, Sandi Metz
- Modern C++ Programming with Test-Driven Development, Jeff Langr

April
- Learning PHP, MySQL & JavaScript, Robin Nixon
- Measuring the world, Daniel Kehlmann

May
- El hombre que plantaba árboles, (L'homme qui plantait des arbres), Jean Giono
- Extreme Programming Explained, Embrace Change, Kent Beck
- Adiós, Chunky Rice, (Good-bye, Chunky Rice), Craig Thompson

June
- Eloquent Ruby, Russ Olsen
- Implementing Domain-Driven Design, Vaughn Vernon

July
- JavaScript Allongé, Reginald Braithwaite
- JavaScript: The Good Parts, Douglas Crockford

August
- Programming Clojure, (2nd edition), Stuart Halloway and Aaron Bedra
- Introduction to Computing, Explorations in Language, Logic and Machines, David Evans
- JavaScript Allongé, Reginald Braithwaite (2nd time)

Interesting Talk: "Test-Driven JavaScript in Practice"

I've just watched this wonderful talk by Christian Johansen:

• Test-Driven JavaScript in Practice

Exercism: "Raindrops in Clojure"

I solved the Raindrops problem in Clojure.

This is my solution:

	(ns raindrops)
	(declare prime-factors convert-factor)
	(defn convert [n]
	(let
	[factors (apply sorted-set (prime-factors n))]
	(if (some #(or (= % 3) (= % 5) (= % 7)) factors)
	(apply str (map convert-factor factors))
	(str n))))
	(defn- convert-factor [factor]
	(cond
	(= factor 3) "Pling"
	(= factor 5) "Plang"
	(= factor 7) "Plong"
	:else ""))
	(def ^:private factor?
	(comp zero? rem))
	(defn- prime-factors [n]
	(loop [n n prime 2 factors []]
	(cond
	(= n 1) factors
	(factor? n prime) (recur (/ n prime) prime (conj factors prime))
	:else (recur n (inc prime) factors))))

view raw raindrops.clj hosted with ❤ by GitHub

Where I used the code I wrote for the Prime factors kata in Clojure

You can nitpick my solution here or see all the exercises I've done so far in this repository.

Exercism: "Prime Factors in Clojure"

I solved the Prime factors problem in Clojure.

You can check my solution in my previous post:

• Kata: Prime factors in Clojure

You can nitpick my solution here or see all the exercises I've done so far in this repository.

Exercism: "Roman Numerals in Clojure"

I solved the Roman Numerals problem in Clojure.

You can check my solution in my previous post:

• Kata: Roman Numerals in Clojure

You can nitpick my solution here or see all the exercises I've done so far in this repository.

Kata: Roman Numerals in Clojure

I've just done the Roman Numerals kata in Clojure.

I used this description of roman numerals, On Roman Numerals, and continued the kata to also convert numbers over 3000.

These are the tests using Midje that I wrote to test-drive the solution:

	(ns roman-numerals.core-test
	(:use midje.sweet)
	(:use [roman-numerals.core]))
	(facts
	"about arabic to roman numerals conversion"
	(fact "it converts numbers until 10"
	(arabic-to-roman 1) => "I"
	(arabic-to-roman 2) => "II"
	(arabic-to-roman 3) => "III"
	(arabic-to-roman 4) => "IV"
	(arabic-to-roman 5) => "V"
	(arabic-to-roman 8) => "VIII"
	(arabic-to-roman 9) => "IX"
	(arabic-to-roman 10) => "X")
	(fact "it converts numbers from 10 to 39"
	(arabic-to-roman 13) => "XIII"
	(arabic-to-roman 14) => "XIV"
	(arabic-to-roman 25) => "XXV"
	(arabic-to-roman 28) => "XXVIII"
	(arabic-to-roman 39) => "XXXIX")
	(fact "it converts numbers from 40 to 89"
	(arabic-to-roman 40) => "XL"
	(arabic-to-roman 49) => "XLIX"
	(arabic-to-roman 50) => "L"
	(arabic-to-roman 89) => "LXXXIX")
	(fact "it converts numbers from 90 to 199"
	(arabic-to-roman 90) => "XC"
	(arabic-to-roman 99) => "XCIX"
	(arabic-to-roman 100) => "C"
	(arabic-to-roman 199) => "CXCIX")
	(fact "it converts numbers from 200 to 1000"
	(arabic-to-roman 200) => "CC"
	(arabic-to-roman 250) => "CCL"
	(arabic-to-roman 400) => "CD"
	(arabic-to-roman 499) => "CDXCIX"
	(arabic-to-roman 500) => "D"
	(arabic-to-roman 899) => "DCCCXCIX"
	(arabic-to-roman 900) => "CM"
	(arabic-to-roman 999) => "CMXCIX"
	(arabic-to-roman 1000) => "M")
	(fact "it converts numbers from 1001 to 3999"
	(arabic-to-roman 1100) => "MC"
	(arabic-to-roman 1200) => "MCC"
	(arabic-to-roman 2250) => "MMCCL"
	(arabic-to-roman 3400) => "MMMCD"
	(arabic-to-roman 3499) => "MMMCDXCIX"
	(arabic-to-roman 3500) => "MMMD"
	(arabic-to-roman 3899) => "MMMDCCCXCIX"
	(arabic-to-roman 3900) => "MMMCM"
	(arabic-to-roman 3999) => "MMMCMXCIX"
	(arabic-to-roman 3000) => "MMM")
	(fact "it converts numbers over 3999"
	(arabic-to-roman 4000) => "--\nIV"
	(arabic-to-roman 4001) => "--\nIVI"
	(arabic-to-roman 3999005) => "---------\nMMMCMXCIXV"
	(arabic-to-roman 4000000) => "--\n--\nIV"
	(arabic-to-roman 4000025) => "--\n--\nIVXXV"))

view raw roman-numerals.core-test.clj hosted with ❤ by GitHub

and this is the code:

	(ns roman-numerals.core)
	(declare huge-roman-numeral convert roman-symbols)
	(defn arabic-to-roman [arabic]
	(cond
	(<= arabic 10) (convert arabic :until-10)
	(<= arabic 100) (str (convert (quot arabic 10) :until-100)
	(arabic-to-roman (mod arabic 10)))
	(<= arabic 1000) (str (convert (quot arabic 100) :until-1000)
	(arabic-to-roman (mod arabic 100)))
	(<= arabic 3999) (str (convert (quot arabic 1000) :until-3999)
	(arabic-to-roman (mod arabic 1000)))
	:else (huge-roman-numeral arabic)))
	(def ^:private roman-symbols
	{:until-10 "IVX"
	:until-100 "XLC"
	:until-1000 "CDM"
	:until-3999 "M "})
	(defn- convert [arabic in-range]
	(let [[from medium to] (roman-symbols in-range)]
	(cond
	(= arabic 0) ""
	(= arabic 10) (str to (convert (- arabic 10) in-range))
	(= arabic 4) (str from medium)
	(>= arabic 9) (str from to (convert (- arabic 9) in-range))
	(>= arabic 5) (str medium (convert (- arabic 5) in-range))
	:else (str from (convert (- arabic 1) in-range)))))
	(defn- thousand-bar [size]
	(str (apply str (repeat (count size) "-")) "\n"))
	(defn- times-thousand [arabic]
	(loop [n arabic times 0]
	(if (<= n 3999)
	times
	(recur (quot n 1000) (+ times 1)))))
	(defn- pow [m n]
	(reduce * (repeat n m)))
	(defn- huge-roman-numeral [arabic]
	(let [times (times-thousand arabic)
	div (pow 1000 times)
	thousand-multiple (arabic-to-roman (quot arabic div))
	horizontal-bar (thousand-bar thousand-multiple)]
	(str
	(apply str (repeat times horizontal-bar))
	thousand-multiple
	(arabic-to-roman (mod arabic div)))))

view raw roman-numerals.core.clj hosted with ❤ by GitHub

It's possible to convert numbers over 3999:

	user=> (println (arabic-to-roman 3999005))
	---------
	MMMCMXCIXV
	nil
	user=> (println (arabic-to-roman 3999050))
	---------
	MMMCMXCIXL
	nil
	user=> (println (arabic-to-roman 3999150))
	---------
	MMMCMXCIXCL
	nil
	user=> (println (arabic-to-roman 4000150))
	--
	--
	IVCL
	nil
	user=> (println (arabic-to-roman 3999000150))
	---------
	---------
	MMMCMXCIXCL
	nil

view raw roman-numerals-repl.sh hosted with ❤ by GitHub

To document the TDD process I commited the code after every passing test and every refactor.
You can find the commits step by step here.

It's been difficult to derive this recursive algorithm only using strict TDD, but it was also a lot of fun.

You can find the resulting code in GitHub.


Update: Recently I revisited the Roman Numerals kata and got to a simpler solution.

Exercism: "Scrabble Score in Clojure"

This is my solution to the Scrabble Score problem in Clojure.

	(ns scrabble_score
	(:require [clojure.string :as str]))
	(def ^:private score-by-letter
	{"A" 1 "E" 1 "I" 1 "O" 1 "U" 1 "L" 1 "N" 1 "R" 1 "S" 1 "T" 1
	"D" 2 "G" 2
	"B" 3 "C" 3 "M" 3 "P" 3
	"F" 4 "H" 4 "V" 4 "W" 4 "Y" 4
	"K" 5
	"J" 8 "X" 8
	"Q" 10 "Z" 10})
	(defn score-letter [letter]
	(get score-by-letter (str/upper-case letter)))
	(defn score-word [word]
	(reduce + (map #(score-letter %) word)))

view raw scrabble-score.clj hosted with ❤ by GitHub

I added some extra tests to complete the provided ones:

	(ns scrabble-score.test (:require [clojure.test :refer :all]))
	(load-file "scrabble_score.clj")
	(deftest lower-case-letter
	(is (= 1 (scrabble_score/score-letter "a"))))
	(deftest upper-case-letter
	(is (= 1 (scrabble_score/score-letter "A"))))
	(deftest letters-scoring-1
	(is (= 10 (scrabble_score/score-word "AEIOULNRST") (scrabble_score/score-word "aeioulnrst"))))
	(deftest letters-scoring-2
	(is (= 4 (scrabble_score/score-word "DG") (scrabble_score/score-word "dg"))))
	(deftest letters-scoring-3
	(is (= 12 (scrabble_score/score-word "BCMP") (scrabble_score/score-word "bcmp"))))
	(deftest letters-scoring-4
	(is (= 20 (scrabble_score/score-word "FHVWY") (scrabble_score/score-word "fhvwy"))))
	(deftest letters-scoring-5
	(is (= 5 (scrabble_score/score-word "K") (scrabble_score/score-word "k"))))
	(deftest letters-scoring-8
	(is (= 16 (scrabble_score/score-word "JX") (scrabble_score/score-word "jx"))))
	(deftest letters-scoring-10
	(is (= 20 (scrabble_score/score-word "QZ") (scrabble_score/score-word "qz"))))
	(deftest two-letter-word
	(is (= 2 (scrabble_score/score-word "at"))))
	(deftest bigger-word-1
	(is (= 6 (scrabble_score/score-word "street"))))
	(deftest bigger-word-2
	(is (= 22 (scrabble_score/score-word "quirky"))))
	(deftest all-upper-case-word
	(is (= 20 (scrabble_score/score-word "MULTIBILLIONAIRE"))))
	(run-tests)

view raw scrabble-score-tests.clj hosted with ❤ by GitHub

You can nitpick my solution here or see all the exercises I've done so far in this repository.

Euler Project: Problem 3 in Clojure

This is my solution in Clojure to the third problem from Euler project:

	(def factor?
	(comp zero? rem))
	(defn prime-factors [n]
	(loop [n n prime 2 factors #{}]
	(cond
	(= n 1) factors
	(factor? n prime) (recur (/ n prime) prime (conj factors prime))
	:else (recur n (inc prime) factors))))
	(prime-factors 35) ; #{5 7}
	(prime-factors 24) ; #{2 3}
	(prime-factors 600851475143) ; #{71 839 6857 1471}
	(apply max (prime-factors 600851475143)) ; 6857
	(defn largests-prime-factor [n]
	(apply max (prime-factors n)))
	(largests-prime-factor 600851475143) ; 6857

view raw euler-3.clj hosted with ❤ by GitHub

The largests-prime-factor function can be also written in this alternative way using Clojure's ->> macro:

	(defn largests-prime-factor [n]
	(->>
	n
	(prime-factors)
	(apply max)))

view raw euler-3-b.clj hosted with ❤ by GitHub

Kata: Prime factors in Clojure

I've just done the Prime factors kata in Clojure.

These are the tests using Midje:

	(ns prime-factors.core-test
	(:use midje.sweet)
	(:use [prime-factors.core]))
	(facts
	"about prime factors computation"
	(fact "1 has no factors"
	(factorize 1) => [])
	(fact "a prime has only one factor: itself"
	(factorize 2) => [2]
	(factorize 3) => [3])
	(fact "any power of primes has only one factor repeated as many times as the exponent"
	(factorize 8) => [2 2 2]
	(factorize 81) => [3 3 3 3])
	(fact "any other positive integer has more than one factor"
	(factorize 10) => [2 5]
	(factorize 60) => [2 2 3 5]))

view raw prime-factors-tests.clj hosted with ❤ by GitHub

and this is the code:

	(ns prime-factors.core)
	(def ^:private factor?
	(comp zero? rem))
	(defn factorize [n]
	(loop [n n prime 2 factors []]
	(cond
	(= n 1) factors
	(factor? n prime) (recur (/ n prime) prime (conj factors prime))
	:else (recur n (inc prime) factors))))

view raw prime-factors.clj hosted with ❤ by GitHub

You can find the commits step by step here.

Interesting Talk: "What does it mean to be Reactive?"

I've just watched this interesting talk by Erik Meijer:

• What does it mean to be Reactive?

Interesting Talk: "Being Human"

Yesterday I watched this very interesting talk by Brian J Brennan:

• Being Human

Interesting Talk: "SOLID Ruby"

I've just watched this wonderful talk by Jim Weirich:

• SOLID Ruby

Interesting Talk: "SOLID JavaScript In A Wobbly (World Wide Web)"

I've just watched this wonderful talk by Derick Bailey:

• SOLID JavaScript In A Wobbly (World Wide Web)

Interesting Talk: "A Little This, a Little _that: Understanding Scope in JavaScript"

I've just watched this interesting talk by David Aragon:

• A Little This, a Little _that: Understanding Scope in JavaScript

Interesting Talk: "Programming Style & Your Brain"

I've just watched this great talk by Douglas Crockford:

• Programming Style & Your Brain

Interesting Talk: "Introduction to F#, 1 of 3"

I've just watched this interesting tutorial by Don Syme:

• Introduction to F#, 1 of 3

Interesting Talk: "Domain Specific Languages, the functional way"

I've just watched this great talk by Tomas Petricek:

• Domain Specific Languages, the functional way

Interesting Talk: "SICP Lecture 3B: Symbolic Differentiation; Quotation"

I've just watched this wonderful class by Gerald Jay Sussman:

• SICP Lecture 3B: Symbolic Differentiation; Quotation

Interesting Talk: "SICP Lecture 3A: Henderson Escher Example"

I've just watched this wonderful class by Harold Abelson:

• SICP Lecture 3A: Henderson Escher Example

Pascal's triangle

Here is another exercise from David Evans book Introduction to Computing, Explorations in Language, Logic, and Machines.

This is a possible solution for the Pascal's triangle exploration at the end of chapter 5:

	#lang racket
	(require rackunit)
	(define (pascal-triangle-number row col)
	(if (or (= col 0)
	(= col row))
	1
	(+ (pascal-triangle-number (- row 1) col)
	(pascal-triangle-number (- row 1) (- col 1)))))
	(check-equal?
	(pascal-triangle-number 0 0) 1)
	(check-equal?
	(pascal-triangle-number 1 0) 1)
	(check-equal?
	(pascal-triangle-number 1 1) 1)
	(check-equal?
	(pascal-triangle-number 2 0) 1)
	(check-equal?
	(pascal-triangle-number 2 1) 2)
	(check-equal?
	(pascal-triangle-number 2 2) 1)
	(check-equal?
	(pascal-triangle-number 3 1) 3)
	(check-equal?
	(pascal-triangle-number 3 2) 3)
	(check-equal?
	(pascal-triangle-number 4 1) 4)
	(check-equal?
	(pascal-triangle-number 4 2) 6)
	(check-equal?
	(pascal-triangle-number 4 3) 4)
	(define (pascal-triangle-row n)
	(define (helper n i)
	(if (< i 0)
	null
	(cons (pascal-triangle-number n i)
	(helper n (- i 1)))))
	(helper n n))
	(check-equal? (pascal-triangle-row 0) (list 1))
	(check-equal? (pascal-triangle-row 1) (list 1 1))
	(check-equal? (pascal-triangle-row 2) (list 1 2 1))
	(define (range from to)
	(if (> from to)
	null
	(cons from
	(range (+ from 1) to))))
	(define (pascal-triangle n)
	(map
	pascal-triangle-row
	(range 0 n)))
	(check-equal?
	(pascal-triangle 0)
	(list (list 1)))
	(check-equal?
	(pascal-triangle 1)
	(list (list 1) (list 1 1)))
	(check-equal?
	(pascal-triangle 2)
	(list (list 1) (list 1 1) (list 1 2 1)))
	(check-equal?
	(pascal-triangle 4)
	(list (list 1) (list 1 1) (list 1 2 1) (list 1 3 3 1) (list 1 4 6 4 1)))

view raw pascal-triangle.rkt hosted with ❤ by GitHub

It's a nice exercise to practise recursion.

Practising recursion with accumulate, filter and map for deeply nested lists

I'm practising recursion going through some of the exercises in David Evans book Introduction to Computing, Explorations in Language, Logic, and Machines.

These are the solutions to three of those exercises:

1. An accumulate (reduce) function for a list which can contain arbitrarily deeply nested lists.
   
   

   	#lang racket
   	(require rackunit)
   	(define (deep-list-accumulate comb base dls)
   	(if (null? dls)
   	base
   	(let [(first-dls (first dls))]
   	(comb (deep-list-accumulate comb base (rest dls))
   	(if (list? first-dls)
   	(deep-list-accumulate comb base first-dls)
   	first-dls)))))
   	(define (deep-list-sum dls)
   	(deep-list-accumulate + 0 dls))
   	(define (deep-list-prod dls)
   	(deep-list-accumulate * 1 dls))
   	(check-equal?
   	(deep-list-sum '()) 0)
   	(check-equal?
   	(deep-list-sum (list (list 1))) 1)
   	(check-equal?
   	(deep-list-sum (list (list 1) (list 1))) 2)
   	(check-equal?
   	(deep-list-sum (list 1 (list 1))) 2)
   	(check-equal?
   	(deep-list-prod (list 1 (list 2 (list 3 (list 4))))) 24)

   view raw deep-list-accumulate.rkt hosted with ❤ by GitHub
2. A map function for a list which can contain arbitrarily deeply nested lists.
   
   

   	#lang racket
   	(require rackunit)
   	(define (deep-list-map f dls)
   	(if (null? dls)
   	null
   	(let [(first-dls (first dls))]
   	(cons
   	(if (list? first-dls)
   	(deep-list-map f first-dls)
   	(f first-dls))
   	(deep-list-map f (rest dls))))))
   	(define (deep-list-square dls)
   	(deep-list-map (lambda (x) (* x x)) dls))
   	(define (deep-list-double dls)
   	(deep-list-map (lambda (x) (* 2 x)) dls))
   	(check-equal?
   	(deep-list-square (list 2))
   	(list 4))
   	(check-equal?
   	(deep-list-square (list 1 (list 2 (list 3))))
   	(list 1 (list 4 (list 9))))
   	(check-equal?
   	(deep-list-double (list 1 (list 2 (list (list 2 3 4) 3 (list 4)))))
   	(list 2 (list 4 (list (list 4 6 8) 6 (list 8)))))

   view raw deep-list-map.rkt hosted with ❤ by GitHub
3. A filter function for a list which can contain arbitrarily deeply nested lists.
   
   

   	#lang racket
   	(require rackunit)
   	(define (deep-list-filter pred dls)
   	(if (null? dls)
   	null
   	(let [(first-dls (first dls))
   	(rest-dls (rest dls))]
   	(if (list? first-dls)
   	(cons (deep-list-filter pred first-dls)
   	(deep-list-filter pred rest-dls))
   	(if (pred first-dls)
   	(cons first-dls
   	(deep-list-filter pred rest-dls))
   	(deep-list-filter pred rest-dls))))))
   	(define (even? x)
   	(zero? (modulo x 2)))
   	(define (evens-in dls)
   	(deep-list-filter even? dls))
   	(define (odds-in dls)
   	(deep-list-filter
   	(lambda (x) (not (even? x)))
   	dls))
   	(check-equal?
   	(evens-in (list 2 3 4))
   	(list 2 4))
   	(check-equal?
   	(odds-in (list 2 3 4))
   	(list 3))
   	(check-equal?
   	(odds-in (list 1 (list 2 (list 3))))
   	(list 1 (list (list 3))))
   	(check-equal?
   	(evens-in (list 1 (list 2 (list 3))))
   	(list (list 2 (list))))
   	(check-equal?
   	(evens-in (list 1 (list 2 (list (list 2 3 4) 3 (list 4)))))
   	(list (list 2 (list (list 2 4) (list 4)))))
   	(check-equal?
   	(odds-in (list 1 (list 2 (list (list 2 3 4) 3 (list 4)))))
   	(list 1 (list (list (list 3) 3 (list)))))

   view raw deep-list-filter.rkt hosted with ❤ by GitHub

You can find these and other exercises and examples from the book in this GitHub repository.

I'm loving the book.

Interesting Talk: "SICP Lecture 2B: Compound Data"

I've just watched this wonderful class by Harold Abelson:

• SICP Lecture 2B: Compound Data

Interesting Talk: "SICP Lecture 2A: Higher-order Procedures"

I've just watched this wonderful class by Gerald Jay Sussman:

• SICP Lecture 2A: Higher-order Procedures

Kata: Find indexes of all upper-case letters in a word

Last Friday I went to a kata of Barcelona Software Craftsmanship facilitated by Carlos Blé at Runroom.

We had to write a function using TDD that when given a word will produce an array containing the positions of all the capital letters in the word.

The most interesting part of the exercise came during the second interaction in which we had the constraint of not mutating any value.

Although we didn't managed to finish the exercise, we had a very interesting debate about recursion, baby steps and TDD.

Once back at home I started to grow the code again in tiny steps, trying to make explicit the problem patterns before taking the leap of faith of recursion.

This is the code passing all the tests right before being refactored to be recursive:

	'use strict';
	function findCapitalLetterPositions(word) {
	var res = [];
	if(word.length === 0) {
	return res;
	}
	if(isUpperCase(word[0])) {
	res = res.concat([0]);
	}
	if (word.length == 1) {
	return res;
	}
	if(isUpperCase(word[1])) {
	res = res.concat([1]);
	}
	return res;
	}
	function isUpperCase(letter) {
	return letter.toUpperCase() == letter[0];
	}
	describe("Upper case letters finder", function() {
	it("an empty word contains no capital letters", function() {
	expect(findCapitalLetterPositions("")).toEqual([]);
	});
	it("finds the index of a word with one letter that is upper case", function() {
	expect(findCapitalLetterPositions("A")).toEqual([0]);
	});
	it("produces no index for a one letter word containing no capital letters", function() {
	expect(findCapitalLetterPositions("a")).toEqual([]);
	});
	it("produces the index of a capital letter not at the beginning of the word", function() {
	expect(findCapitalLetterPositions("aA")).toEqual([1]);
	});
	it("produces the indexes of a two capital letters word", function() {
	expect(findCapitalLetterPositions("BA")).toEqual([0,1]);
	});
	});

view raw findCapitalLetterPositionsBeforeRecursion.js hosted with ❤ by GitHub

In the repetition that existed in this code, it was possible to see two emerging patterns:

1. The base case of the recursion which happens when the word length is equal to the current index.
2. The use of concat to make the result grow when the character at the current index is a capital letter

Using that information I refactored the code to get to this recursive solution, (after a pair of failed attempts...):

	'use strict';
	function findCapitalLetterPositions(word) {
	return f(word, 0);
	function f(word, index) {
	if(word.length == index) {
	return [];
	}
	if(isUpperCase(word[index])) {
	return [index].concat(f(word, index + 1));
	}
	return f(word, index + 1);
	}
	}
	function isUpperCase(letter) {
	return letter.toUpperCase() == letter[0];
	}
	describe("Upper case letters finder", function() {
	it("an empty word contains no capital letters", function() {
	expect(findCapitalLetterPositions("")).toEqual([]);
	});
	it("finds the index of a word with one letter that is upper case", function() {
	expect(findCapitalLetterPositions("A")).toEqual([0]);
	});
	it("produces no index for a one letter word containing no capital letters", function() {
	expect(findCapitalLetterPositions("a")).toEqual([]);
	});
	it("produces the index of a capital letter not at the beginning of the word", function() {
	expect(findCapitalLetterPositions("aA")).toEqual([1]);
	});
	it("produces the indexes of a two capital letters word", function() {
	expect(findCapitalLetterPositions("BA")).toEqual([0,1]);
	});
	});

view raw findCapitalLetterPositionsRecursion.js hosted with ❤ by GitHub

In it you can still distinguish the similarities with the previous non-recursive version.

The base case now returns an empty array and concat is used again when a capital letter is found at the current index, only that the concatenation is now with a one-element list containing the current index.

In any other case, no element is concatenated to the result and the function is called again with the next index.

Later, I refactored the code and the tests a bit more to get to these final versions of the tests:

	'use strict';
	var findCapitalLetterPositions = require('./UpperCaseFinder.js').findCapitalLetterPositions;
	describe("Upper case letters finder", function() {
	it("produces no index for an empty word", function() {
	expect(findCapitalLetterPositions("")).toEqual([]);
	});
	it("produces the indexes of capital letters in a word", function() {
	expect(findCapitalLetterPositions("BAsrwQMPaZ")).toEqual([0, 1, 5, 6, 7, 9]);
	});
	it("ignores characters that are not letters", function() {
	expect(findCapitalLetterPositions("3As5wQ6PaZ")).toEqual([1, 5, 7, 9]);
	});
	});

view raw findCapitalLetterPositionsRecursiveTests.js hosted with ❤ by GitHub

and the code:

	'use strict';
	function findCapitalLetterPositions(word, index) {
	if (index === undefined) {
	return findCapitalLetterPositions(word, 0);
	}
	if (word.length == index) {
	return [];
	}
	if (isNotLetter(word[index]) || isNotUpperCase(word[index])) {
	return findCapitalLetterPositions(word, index + 1);
	}
	return [index].concat(
	findCapitalLetterPositions(word, index + 1)
	);
	function isNotUpperCase(letter) {
	return letter.toUpperCase() != letter[0];
	}
	function isNotLetter(char) {
	return !char.match(/[a-z]/i);;
	}
	}
	module.exports.findCapitalLetterPositions = findCapitalLetterPositions

view raw findCapitalLetterPositionsRecursive.js hosted with ❤ by GitHub

You can check the code in this GitHub repository.

All in all, I'm under the impression that I wrote the before-recursion code that way because I already had an insight of how the recursive solution was going to be.

Had I written it in a different way, might it have made more difficult to find a recursive solution?
What would have happened with a more difficult problem?

I'm not sure if TDD alone will help me to find recursive solutions.

I will keep working on it.

Some home-made implementations of map

This post originated in a conversation we had during the last Barcelona Software Craftsmanship event.

We talked about a technique to recursively processing list elements once at a time in which you have to focus on two things:

1. How to process an empty list (the base case of the recursion)
2. How to process a non empty list in terms of the result of processing the tail of the list (the list except the first element)

To illustrate it, let's see a possible implementation of map in SML:

	fun mapUsingListFunctions(f, ls) =
	if null ls
	then []
	else f(hd ls)::mapUsingListFunctions(f, tl ls)
	val test = mapUsingListFunctions(
	(fn x => x * x),
	[1, 2, 3])
	(* val test = [1,4,9] : int list *)

view raw myMapUsingListFunctions.sml hosted with ❤ by GitHub

It uses the following list functions:

• hd to extract the head of the list (its first element)
• tl to extract the tail of the list (the list except the first element)
• null that returns true if the list is empty and false otherwise

The :: operator adds an element at the beginning of a list.

We can use a similar approach to write map in Racket:

	#lang racket
	(define (map-using-list-functions f ls)
	(if (empty? ls)
	'()
	(cons (f (first ls))
	(map-using-list-functions f (rest ls)))))
	(map-using-list-functions
	(lambda (x) (* x x))
	'(1 2 3))
	; '(1 4 9)

view raw myMapUsingListFunctions.rkt hosted with ❤ by GitHub

Here the name of the functions are a bit more expressive: first, rest and empty?.
The cons function adds an element at the beginning of a list.

A more idiomatic way to write map in SML would be using pattern matching:

	fun mapUsingPatternMatching(f, ls) =
	case ls of
	[] => []
	| head::tail => f(head)::mapUsingPatternMatching(f, tail)
	val test = mapUsingPatternMatching(
	(fn x => x * x),
	[1, 2, 3])
	(* val test = [1,4,9] : int list *)

view raw myMapUsingPatternMatching.sml hosted with ❤ by GitHub

This version is using the same approach but pattern matching makes the code more concise and expressive.

As a bonus here is a beautiful way to append two lists in SML using the same technique and pattern matching:

	fun append(xs, ys) =
	case xs of
	[] => ys
	| head::tail => head::append(tail, ys)
	val testAppend1 = append([1, 2, 3, 4], [5, 6, 7])
	(* val testAppend1 = [1,2,3,4,5,6,7] : int list *)
	val testAppend2 = append([], [5, 6, 7])
	(* val testAppend2 = [5,6,7] : int list *)
	val testAppend3 = append([1, 2, 3, 4], [])
	(* val testAppend3 = [1,2,3,4] : int list *)

view raw myAppendUsingPatternMatching.sml hosted with ❤ by GitHub

This is very well explained in the first unit of of the Programming Languages course from Washington University at Coursera that I completed last year.

There is going to be a new edition starting up Oct 2. I cannot recommend it highly enough.

Interesting Talk: "The Birth & Death of JavaScript"

I've just watched this interesting talk by Gary Bernhardt:

• The Birth & Death of JavaScript

Interesting Talk: "Code that fits your brain"

I've just watched this very interesting talk by Adam Tornhill:

• Code that fits your brain

Exercism: Revisiting "Space Age in Clojure"

I used metaprogramming as I did in the Meetup problem to simplify the code of the Space Age problem (you can find my previous versions here):

	(ns space-age)
	(def planets
	['mercury
	'venus
	'mars
	'jupiter
	'saturn
	'uranus
	'neptune])
	(def orbital-periods-in-earth-years
	(zipmap
	planets
	[0.2408467
	0.61519726
	1.8808158
	11.862615
	29.447498
	84.016846
	164.79132]))
	(defn on-earth [seconds]
	(let
	[seconds-per-earth-year 31557600.0]
	(/ seconds seconds-per-earth-year)))
	(defn make-on-planet-function [orbital-period-in-earth-years]
	(fn [seconds]
	(/ (on-earth seconds) orbital-period-in-earth-years)))
	(doall
	(map
	#(intern
	'space-age
	(symbol (str "on-" (name %)))
	(make-on-planet-function
	(% orbital-periods-in-earth-years)))
	planets))

view raw space-age4.clj hosted with ❤ by GitHub

This version has less repetition than the previous ones.

You can nitpick my solution here or see all the exercises I've done so far in this repository.

Exercism: "Triangle in Clojure"

This is my solution to the Triangle problem in Clojure.

	(ns triangle)
	(defn- equilateral? [a b c]
	(= a b c))
	(defn- isosceles? [a b c]
	(or (= a b) (= b c) (= a c)))
	(defn- triangle? [a b c]
	(and
	(< a (+ b c))
	(< b (+ a c))
	(< c (+ b a))))
	(defn type [a b c]
	(cond
	(not (triangle? a b c)) :illogical
	(equilateral? a b c) :equilateral
	(isosceles? a b c) :isosceles
	:else :scalene))

view raw triangle.clj hosted with ❤ by GitHub

This was an easy one.

You can nitpick my solution here or see all the exercises I've done so far in this repository.

Euler Project: Problem 2 in Clojure

This is my solution in Clojure to the second problem from Euler project:

	(def fibonaccis
	(map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
	(def evens-in (partial filter even?))
	(defn fibonaccis-below [num]
	(take-while (partial > num) fibonaccis))
	(reduce + 0 (evens-in (fibonaccis-below 4000000)))

view raw euler2.clj hosted with ❤ by GitHub

I created some helpers just to make the solution a bit more readable.

Exercism: "Gigasecond in Ruby"

I solved the Gigasecond exercise in Ruby a month ago but I forgot to post it.

Since my previous post was about the solution to this exercise using Clojure, I'll post here its solution in Ruby:

	class Gigasecond
	GS_IN_DAYS = (10**9)/(60*60*24)
	def initialize (birth_date)
	@birth_date = birth_date
	end
	def date
	@birth_date + GS_IN_DAYS
	end
	end

view raw gigasecond.rb hosted with ❤ by GitHub

In this case life is much easier in Ruby :)

Exercism: "Gigasecond in Clojure"

This is my solution to the Gigasecond problem in Clojure.

	(ns gigasecond
	(:require [clojure.string :as str])
	(:import [java.util Calendar]
	[java.text SimpleDateFormat]))
	(defn- date [year month day]
	(let
	[calendar (Calendar/getInstance)]
	(.setTime
	calendar
	(.parse
	(SimpleDateFormat. "yyyy-MM-dd")
	(str year "-" month "-" day)))
	calendar))
	(defn- add-days [date days]
	(.add date (Calendar/DATE) days)
	date)
	(defn- date-to-vec [date]
	[(.get date (Calendar/YEAR))
	(+ (.get date (Calendar/MONTH)) 1)
	(.get date (Calendar/DATE))])
	(def GS_IN_DAYS
	(/ (reduce * (repeat 9 10))
	(* 60 60 24)))
	(defn from [year month day]
	(->
	(date year month day)
	(add-days GS_IN_DAYS)
	date-to-vec))

view raw gigasecond.clj hosted with ❤ by GitHub

To solve it I had to learn first how to add days to a date in Java by having a look to the SimpleDateFormat and Calendar classes.

Then I learned a bit about how to use Java from Clojure in the Clojure Java Interop documentation and this other useful post: Calling java from Clojure.

Finally, once I had it working on the REPL, I added some private helper functions and used the -> macro in the implementation of the from function to make the code more readable.

You can nitpick my solution here or see all the exercises I've done so far in this repository.

Interesting Talk: "Becoming an Outlier: Career Reboot for the Developer Mind"

I've just watched this interesting talk by Cory House:

• Becoming an Outlier: Career Reboot for the Developer Mind

Using jQuery Validation plugin with a custom rule and HTML5 data attributes

This is a small example from something I did recently at work.

We needed to apply some custom validation rules to some form fields using the jQuery Validation Plugin.

The decision of which fields were contained in a given form was taken dynamically, so instead of dynamically creating a rules object to pass it to the validate method, we decided to use HTML5 data attributes.

In the following example, I'll show you a way to do it.

Imagine that we'd like to validate that the first name introduced in a form is a palindrome.

To do it you could add a custom rule palindrome to the jQuery Validation plugin using its addMethod method and then validate the form, as shown in this JavaScript code:

	var customValidations = (function() {
	function reverse(word) {
	var i, reversedLetters = [];
	for (i = word.length - 1; i >= 0; i--) {
	reversedLetters.push(word[i]);
	}
	return reversedLetters.join('');
	}
	return {
	isPalindrome: function(word) {
	return reverse(word) === word;
	}
	}
	})();
	$.validator.addMethod("palindrome", function(value) {
	return customValidations.isPalindrome(value);
	});
	$("#exampleForm").validate();

view raw validation.js hosted with ❤ by GitHub

In the form we can refer to this custom rule using HTML5 data attributes:

	<!DOCTYPE html>
	<html>
	<body>
	<form id="exampleForm" action="" autocomplete="on">
	First name:
	<input type="text" name="fname" required
	data-rule-palindrome="true"
	data-msg-palindrome="Please introduce a palindrome"><br>
	Last name:
	<input type="text" name="lname" required><br>
	<input type="submit">
	</form>
	<script
	src="http://code.jquery.com/jquery-1.11.1.min.js">
	</script>
	<script
	src="http://jqueryvalidation.org/files/dist/jquery.validate.min.js">
	</script>
	<script
	src="validation.js">
	</script>
	</body>
	</html>

view raw formValidation.html hosted with ❤ by GitHub

We used data-rule-palindrome="true" to state that the fname field must contain a palindrome and data-msg-palindrome="Please your name must be a palindrome" to set the message that is shown in case it's not a palindrome.

In a nutshell, using jQuery Validation plugin with a custom rule and HTML5 data attributes is as easy as adding a custom rule with addMethod and then adding in the field you want to validate with the custom rule:

• data-rule + custom_rule_name="true" to apply the rule to a given field
• data-msg- + custom_rule_name = "message" to set the error message

I hope you might find this useful

Exercism: Revisiting "Grains in Clojure"

Recently I solved the Grains problem using a home-made stream both using Clojure and Racket (check the the Clojure's solution and the Racket's solution).

As I said then, the solution in Clojure was not idiomatic at all. I just wanted to write a stream in Clojure similar to the ones I had studied in the Coursera Programming Languages course.

This new version is a much more simple and Clojurist way of solving the same problem using the iterate function:

	(ns grains)
	(def grains (iterate #(* 2 %) 1N))
	(defn square [sqr-num]
	(nth grains (- sqr-num 1)))
	(defn total []
	(reduce + 0 (take 64 grains)))

view raw grains2.clj hosted with ❤ by GitHub

The iterate function generates a lazy sequence containing the number of grains in each square. The square and total functions realize that lazy sequence to get the content of a given square and the sum of the 64 squares of the chess board, respectively.

You can nitpick my solution here or see all the exercises I've done so far in this repository.