Archive for June, 2012

Furnace/Heat Exchange Problem

About 7 years ago in one of my master program courses at The University of Texas at Dallas we were assigned a project that involved the simulation of a furnace. The requirement was that it would be solved three different ways, in process, RPC, and forks.

The main crux of the problem though was a simulation of a furnace and the heat dissipation. The problem was down to a grid of cells, each with its own temperature, and the temperature would change based off of the neighbor cells. There was also a burner in the simulation, that would turn on when the temperature of cells would get below a set threshold.

I figured that this would be a good problem to try solving in Clojure, but I can not remember the overall problem description in order to make an attempt at it.

If anybody knows the problem I am describing, please let me know, as I haven’t been able to find the right terms to search against, so now I am asking for help from the Hive-Mind.

Thanks,
–Proctor

Advertisements

,

1 Comment

Project Euler in Clojure – Problem 8

This is my solution to Problem 8 of Project Euler. If you would like to track my progress you can follow my repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  Here is my solution to Problem 7.

Problem 8 of Project Euler is described as:

Find the greatest product of five consecutive digits in the 1000-digit number.
          73167176531330624919225119674426574742355349194934
          96983520312774506326239578318016984801869478851843
          85861560789112949495459501737958331952853208805511
          12540698747158523863050715693290963295227443043557
          66896648950445244523161731856403098711121722383113
          62229893423380308135336276614282806444486645238749
          30358907296290491560440772390713810515859307960866
          70172427121883998797908792274921901699720888093776
          65727333001053367881220235421809751254540594752243
          52584907711670556013604839586446706324415722155397
          53697817977846174064955149290862569321978468622482
          83972241375657056057490261407972968652414535100474
          82166370484403199890008895243450658541227588666881
          16427171479924442928230863465674813919123162824586
          17866458359124566529476545682848912883142607690042
          24219022671055626321111109370544217506941658960408
          07198403850962455444362981230987879927244284909188
          84580156166097919133875499200524063689912560717606
          05886116467109405077541002256983155200055935729725
          71636269561882670428252483600823257530420752963450

(defn digits-of [n]
  (map #(Integer/parseInt (str %)) (str n)))

(defn problem8 []
  (let [n 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450]
    (apply max (map
                 #(apply * %) (partition 5 1 (digits-of n))))))

The digits-of function takes a number and creates a sequence of the digits of the number, in the same way a string can be treated as a sequence of characters. I then call partition on that stream of digits to get the digits in groups of five. Those groups of five get multiplied together, and we find the max of those results.

Again, I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Update**
I have posted my solution to Problem 9.

–Proctor

, ,

5 Comments

Smelly matrix diagonals

As I am working on Problem 11 in Project Euler, I am trying to use a matrix and some functions against that matrix to help me solve the problem. I spent a bit of time browsing incanter and its documentation, but did not see anything that would give me what I was looking for.

The particularly nasty function I am encountering is finding all of the diagonals in a matrix. Given a matrix of

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

I am would expect the following sequence of vectors:

[1 6 11 16] [2 7 12] [3 8] [4] [5 10 15] [9 14] [13]

Where I think the nasty-ness is coming from is that function is seeming very imperative, and it seems like there should be a much more elegant solution to this, but I am currently not seeing it. In addition to what seems to be a large smell in the code, what makes me think I am doing something “wrong” for Clojure is having seen the elegant solution to Conway’s Game of Life in Programming Clojure which can be found at Github. In the book they take an imperative implementation from another language into Clojure, and then they show a functional solution which turns the imperative version on its head and spins it like a top.

Here is what I came up with, and I can only assume that others would think there is a large smell to this as well.

(defn diagonals [m]
  (let [rdim (count m)
        cdim (count (first m))]
      (loop [diags []
             roff 0
             coff 0]
          (cond (>= coff cdim) (recur diags (inc roff) 0)
                (>= roff rdim) diags
                :else (recur
                        (concat diags
                                (conj []
                                      (for [i (range 0 (min (- rdim roff) (- cdim coff)))]
                                           (matrix-get m (+ roff i) (+ coff i)))))
                        roff
                        (if (zero? roff) (inc coff) cdim))))))

Even as I was writing this function, I could tell that it is doing way to much work in it, and that it is not very composable, nor does it seem to take advantage of much composability. As a side note, one of the things that was also a large sign that I was doing something “wrong” for Clojure, was that it was difficult to incrementally develop, modify, and debug in the REPL.

I would love some suggestions on how to give this code a good scrubbing, and clean up this function.

Thanks in advance,
–Proctor

5 Comments

Sieve of Eratosthenes in Clojure using sets

Working through the Project Euler problems, and with the comment from Arcane Sentiment about filtering based off of a set of primes, I was trying to program the Sieve of Eratosthenes. I also realized that the Sieve becomes a set based problem, so I went about trying to solve it using sets.

My first approach was simply using the difference function given in clojure.set.

(defn primes-under [n]
  (loop [sieve (set (cons 2 (range 3 n 2)))
         f 3]
    (if (> (square f) n)
      sieve
      (recur (difference sieve (range (square f) n f)) (inc f)))))

I start with the set of numbers starting by cons-ing 2 onto the range from 3 to n, skiping every other number, to get the odd numbers up to n.

The new sieve becomes the the difference between the current sieve, and the multiples of the factor f. I use (range (square f) n f) as a subset of the factors of f up to the number n. I start the range at the square of the factor, as any multiples below the square of the factor would already have been sieved out from the factors below it. So for multiples of 5, I can ignore (10, 15, 20) as they are multiples of 2 and 3, the other primes below 5, and as a result I only need to get multiples of 5 starting at 25.

When timing this solution by using:

(time (dorun (primes-under 1000000)))

The timing for the primes under 1,000,000 is around 2.1 seconds, and anywhere from 6 to 10 seconds for the primes under 2,000,000.

I wasn’t happy with this performance, especially after seeing Christophe Grand’s solution and timing on his blog post Everybody loves the Sieve of Eratosthenes.

I decided to try my hand at solving this using a transient set. After many missteps in using a transient set, due to not having used them before, I came up with the following solution:

(defn primes-under2 [n]
  (let [sieve (transient (set (cons 2 (range 3 n 2))))]
    (loop [s sieve
           f 3]
      (cond (> (square f) n) (persistent! s)
            :else (recur (reduce disj! s (range (square f) n f)) (inc f))))))

I define sieve as a transient set, and instead of using difference, I call reduce on the sieve using the function disj! for the ranges of numbers to filter out. I need to use disj! to remove that number from the sieve, as this is now a transient set I am working against.

The timing of this solution is now down to 1.1 seconds for primes under 1,000,000, and primarily in the 3 second range for the primes under 2,000,000.

I am still not quite satisfied with this solution, and would love suggestions as to how to avoid those numbers which have been filtered out of the sieve already.  As I just do a (inc f), I would still get the numbers 4, 6, 8, 9, 25, etc, that are multiples of other primes, but I could not figure out how to skip these numbers.  I tried the functions contains?, get, superset?, subset?, difference, but these were not giving me the result when dealing with the transient set.

If someone could tell me if I have missed anything I should try for filtering out non-prime numbers as factors, I would love to get your suggestions to try it out, and I will post a follow up with the results.

–Proctor

, ,

4 Comments

Project Euler in Clojure – Problem 7

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  My approach to Problem 6 can be found here.

Problem 7 of Project Euler is described as:

What is the 10 001st prime number?
(defn is-prime? [n]
  (cond (<= n 1) false
        (= n 2) true
        :else (loop [f 2]
                (cond (zero? (rem n f)) false
                      (> f (Math/sqrt n)) true
                      :else (recur (inc f))))))

(defn problem7
  ([] (problem7 10001))
  ([n] (first (skip-n (dec n) (filter is-prime? (iterate inc 1))))))

The is-prime? function check to see if the number is prime by checking if any of the numbers from 2 to the square root of the number is a divisor of the number.

The problem7 function is finds the n-th number in the sequence by skiping n-1 items, and then taking the first item of that sequence. This was before a previous post in which someone pointed out that the drop function was available instead of my home rolled skip-n function, so that can be replaced on the update.

Again, I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Update**
My solution to Problem 8 has been posted.

–Proctor

, ,

5 Comments

Project Euler in Clojure – Problem 6

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  My approach to Problem 5 can be found here.

Problem 6 of Project Euler is described as:

Find the difference between the sum of the squares of the
first one hundred natural numbers and the square of the sum.

This is another problem that seems to translate almost directly from the problem statement into the operations that need to be performed.

I find the square of the sums from 1 to the (inc n), where n is bound to 100 for the problem definition, as I want the number that n is bound to to be included in the range. This is coded as:

(Math/pow (reduce + (range 1 (inc n))) 2)

As well as I find the sum of the squares from 1 to the (inc n).

(reduce + (map #(Math/pow % 2) (range 1 (inc n))))

I then pieced these two solutions together, subtracting the two values. When doing this at the REPL, it gave the result as an exponent, which I didn’t like the look of, so I put the function bigint around the subtraction function, giving the full solution as:

(defn problem6
  ([] (problem6 100))
  ([n] (bigint (-
         (Math/pow (reduce + (range 1 (inc n))) 2)
         (reduce + (map #(Math/pow % 2) (range 1 (inc n))))))))

Again, I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Update**
My solution to Problem 7 can be found here.

–Proctor

, ,

4 Comments

Project Euler in Clojure – Problem 5

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  My approach to Problem 4 can be found here.

Problem 5 of Project Euler is described as:

What is the smallest positive number that is evenly
divisible by all of the numbers from 1 to 20?

In reading this problem I realized that this is just another way to state:

Find the Least Common Multiple of all of the numbers between 1 and 20.

The solution I came up with is:

(ns project-euler.core
  (:require [clojure.string :as string]
            clojure.math.numeric-tower))

(defn problem5
  ([] (problem5 20))
  ([n] (reduce lcm 1 (range 2 (inc n)))))

I found that previous to Clojure 1.2 there was a math library in Clojure-Contrib, which after 1.2 is now been moved to clojure.math.numeric-tower, so that now gets included in the vector of libraries in the :require of the ns function.

Once I had this, it was now just as simple as calling the reduce function with the function lcm, feeding it a initialization value of 1 to the reduce function and having that operate on the range of numbers from 2 to the number bound to the var n, which when called without parameters will use the value of twenty as specified in the problem definition. By defining the different arities for the function problem5, it allowed me to call the function with different numbers to the results of the function, as the full description gave the solution for the numbers in the range of 1 through 10.

Again, I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Update**
My solution to Problem 6 has been posted here.

–Proctor

, ,

3 Comments