collections within collections

[Glen Rubin]

I am working on the following problem:

Find the only Pythagorean triplet, {a, b, c}, for which a + b + c =
1000

My strategy is to produce a series of triplets of a^2 + b^2 and then
filter out the ones where the c^2 is a perfect square, in order to
determine Pythagorean triplets.

I wrote a function to produce triplets that takes a range as input:

(use '[clojure.contrib.math :only (sqrt)])

(defn trips [coll]
(loop [a (first coll) b (rest coll) trip []]
(cond (seq b)
(recur (first b) (rest b) (conj trip (map #(vector a % (sqrt (+ (*
a a) (* % %)))) b)))
true trip)))

,so if I want to see all triplets over the range of 1-7, I just do:

(trips (range 1 7)), which yields the following;

[([1 2 2.23606797749979] [1 3 3.1622776601683795] [1 4
4.123105625617661] [1 5 5.0990195135927845] [1 6 6.082762530298219])
([2 3 3.605551275463989] [2 4 4.47213595499958] [2 5
5.385164807134504] [2 6 6.324555320336759]) ([3 4 5] [3 5
5.830951894845301] [3 6 6.708203932499369]) ([4 5 6.4031242374328485]
[4 6 7.211102550927978]) ([5 6 7.810249675906654])]

Obviously the only Pythagorean triplet burried in there is 3, 4, 5.

Now, I can easily test a single vector for integers as follows:

(map integer? [5 6 7])

However, the output of my trips function yields multiple collections
of vectors inside of a larger vector. I am completely befuddled as to
how to process this behemoth.

I guess I need to use some functions for merging collections?

Any help apprectiated. thanks!!

[Wilson MacGyver]

you can define a function to filter the result

like

(defn answer? [x] (filter #(every? integer? %) x))

and then just call it by doing

user=> (map #(answer? %) (trips (range 1 7)))
(() () ([3 4 5]) () ())

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en

--
Omnem crede diem tibi diluxisse supremum.

[Stuart Halloway]

Hi Glen,

When your are working with infinite sets in Clojure, is it better to
take advantage of laziness as far as possible, instead of passing
limits such as the coll argument to trips. Here's how I would think
about this problem:

(defn pairs-adding-to-n
"Pairs of distinct positive integers that sum to n."
[n]
(for [x (range 1 (quot (inc n) 2))]
[x (- n x)]))

(defn pairs
"Lazy sequence of all pairs of distinct positive integers,
in nondecreasing order by sum of the pair."
[]
(apply concat (map pairs-adding-to-n (iterate inc 1))))

(defn pythagorean-triples
"Lazy sequence of pythagorean triples"
[]
(->> (pairs)
(map (fn [[a b]] [a b (sqrt (+ (* a a) (* b b)))]))
(filter (fn [[a b c]] (integer? c)))))

;; only apply the limit (e.g. first) when asking the final question
(first (filter
(fn [args]
(= 1000 (apply + args)))
(pythagorean-triples)))

Stu

[Michael Gardner]

On Mar 10, 2010, at 12:20 PM, Glen Rubin wrote:

> However, the output of my trips function yields multiple collections
> of vectors inside of a larger vector. I am completely befuddled as to
> how to process this behemoth.

You can merge the structure into a single list of triples by applying concat:

user=> (def squares (apply concat (trips (range 1 7))))
#'user/squares
user=> squares
([1 2 2.23606797749979] [1 3 3.1622776601683795] [1 4 4.123105625617661] [1 5 5.0990195135927845] [1 6 6.082762530298219] [2 3 3.605551275463989] [2 4 4.47213595499958] [2 5 5.385164807134504] [2 6 6.324555320336759] [3 4 5] [3 5 5.830951894845301] [3 6 6.708203932499369] [4 5 6.4031242374328485] [4 6 7.211102550927978] [5 6 7.810249675906654])

Then test for perfect squares with this (assuming a and b are always integers):

user=> (defn perfect-square? [[a b c]] (integer? c))
#'user/perfect-square?
user=> (filter perfect-square? squares)

[Tyler Perkins]

I like Clojure, but as a point of comparison, here's a Haskell
solution, as typed in the REPL:

Prelude> let bOf a = 1000*(500 - a)/(1000 - a)
Prelude> let nearInt x = x - fromInteger(truncate x) < 0.000001
Prelude> head [ ( a, b, sqrt(a^2 + b^2) ) | a <- [1..], b <- [bOf a],
nearInt b ]
(200.0,375.0,425.0)

The numbers in the result add up to 1000, of course. Here, I just
solved b in terms of a, which is function bOf. Predicate nearInt
detects whether its argument is an integer (or close enough). Haskell
is lazy, so even though [1..] and the big list comprehension are
infinite, head just needs the first element.

[Stuart Halloway]

The same strategy works in Clojure, of course:

(defn b-of-a [a] (/ (* 1000.0 (- 500.0 a)) (- 1000.0 a)))
(defn near-int? [x] (< (- x (floor x)) 0.00001))
(first (for [a (iterate inc 1) :let [b (b-of-a a)] :when (near-int? b)]

[a b (sqrt (+ (* a a) (* b b)))]))

Stu

[Glen Rubin]

it seems kind of weird that map would work like that. i understood
map as taking the first item of every collection and applying f to
it. e.g (map + [2 4] [6 8]) -> [8 12]

In this case, since answer? takes a collection as argument I guess map
just applies answer? to each collection? but don't all the
collections have to be the same size or one will be exhausted? And
then it seems that answer is acting independently on each collection.
Is that because answer? only takes one argument, whereas a fcn like +
takes 2 arguments. Sorry, I am a little bit confused. The other
responses seemed very helpful too, but have not yet tried to figure
them out. thx!

[Tyler Perkins]

I'm afraid additional verbosity is required. But thanks to your
excellent book (page 229), I know how to import sqrt and floor:

(use '[clojure.contrib.import-static :only (import-static)])
(import-static java.lang.Math sqrt floor)

;;; ... your Clojure code ...

[Wilson MacGyver]

if you use (map f coll), with only 1 collection. it takes
every item in the collection, and apply f to it.

so what I'm really doing is, taking "1 item" at a time from the collection.
but "1 item" turns out to be a collection. I then apply a filter to it so
it only returns what I want.

[Christophe Grand]

Hi all,

Since I'm fp-phobic when doing arithmetic :-) here is mine:

(defn pythagorean-triples []

  (for [a (iterate inc 1)

        :let [squares (into {} (for [c (range a (* 1.5 a))] [(* c c) c]))]
        b (range 1 a)
        :let [c (squares (+ (* a a) (* b b)))]
        :when c] [a b c]))

Christophe

--
Professional: http://cgrand.net/ (fr)
On Clojure: http://clj-me.cgrand.net/ (en)