Posts Tagged Lisp
Was just responding to a comment on Google+ on my update sharing the post Project Euler in Clojure – Problem 16, and I saw the commenter had his own solution to problem 1. In sharing my solution I realized that I could clean up my results even further, and added a function
has-factors-in?. These updates have also been pushed to my Project Euler in Clojure Github repository for those interested.
(defn has-factors-in? [n coll] (some #(factor-of? % n) coll))
Where before I had:
(defn problem1 ( (problem1 1000)) ([n] (sum (filter #(or (factor-of? 3 %) (factor-of? 5 %))) (range n))))
It now becomes:
(defn problem1 ( (problem1 1000)) ([n] (sum (filter #(has-factors-in? % [3 5]) (range n)))))
This change makes my solution read even more like the problem statement given.
Here is my solution to Problem 16 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.
Problem 16 of Project Euler is:
What is the sum of the digits of the number 2^1000
This problem was straight forward since I already had the function
digits-of defined from problem8. I was able to be very declarative in my problem, so much so, that it reads as the problem statement you are asked to solve.
(defn problem16 ( (problem16 1000)) ([n] (sum (digits-of (expt 2 n)))))
As always, any feedback you have for me is greatly appreciated.
Here is my solution to Problem 15 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.
Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a 2020 grid?
I started this problem, by trying to tracing and counting the routes through grids of 2×2, 3×3, and 4×4, and even setled in and did a 5×5 square. Having these numbers, and knowing I had two choices for ever position I was in, except for when the path got to the far edge and bottom, I had a hint at the growth rate of the problem. I tried some powers of 2 with the relationship of the numbers, and some factorials with the numbers. After seeing some possible relationships with the factorials that might be leading me in the right direction, I tried a number of permutation calculations, and the combination calculations. Having seen the numbers show up in different combination results, I then spent time back-calculating from those numbers into my
ns, and found that the pattern seemed to match 2n Choose n.
The source code to this was the
(defn factorial [n] (multiply (range 1M (inc (bigdec n)))))
And, I could have done it recursively, but I figured I would just operate against the sequence of numbers, especially now that the reducers are available in the Clojure 1.5-Alpha 3 release (at the time of this writing) of Clojure. After I get through a few more problems (of which I am working ahead of these posts), I am thinking it would be interesting to run the same Project Euler Problems against 1.4 and 1.5 using the reducers library, just substituting map/reduce for the reduce/combine functionality, and seeing how much effort it takes to move them over, as well as the differences in the timings of the different problems.
The other base function I needed was a
(defn combination [n k] (cond (zero? n) 0 (zero? k) 1 :else (/ (factorial n) (* (factorial (- n k)) (factorial k)))))
This function just does the basic calculation for combinations, from the formula:
With that, and my stumbling upon the matching of the fact that is the solution to ne number of paths through the square the function
problem15 is defined as:
(defn problem15 ( (problem15 20)) ([n] (combination (+ n n) n)))
As always, any feedback you have for me is greatly appreciated.
I was making some refurbishments on some reporting code in our application that used EF and was suffering from the Select N+1 problem. If truth, it was much worse, as it was an Select N+1 problem up to 6 levels deep depending on where the report was run from.
I was changing the code to use a denormalized view from the database, and then run a SQL Query using Entity Framework. When doing this I was asked to get the timings of the report, both against the new way, and the existing way.
As this is incidental to what I was really trying to do, I did not want to litter timing code, and logging mechanisms into classes that already existed. This smelled of Aspect Oriented Programming (AOP). While I had not done anything using AOP before, I knew that it was great for cross-cutting concerns like logging, timings, etc. Having been digging into Clojure and LISP recently, this also seemed like cases of the
:around methods in Common LISP, or the similar behavior in Eiffel as pointed out in Bertrand Meyer’s Object Oriented Software Construction, not to mention the
time function in Clojure which is a function whose single concern is simply the to manage capturing the timing a function passed into it. My hope was to simplify, or un-complect, the code, and keep those concerns separate.
In our project, we have Castle Windsor setup as the IOC container, and Windsor supports a type of Aspect Oriented Programming using something called Interceptors. I found documentation on setting it up on a post by Ayende, and one Andre Loker. The issue was some of the places I wanted to setup the capturing of the timings were in different areas than where the handlers were registered for Windsor.
After some hunting around, I managed to come up with being able to add an interceptor to an already registered component by using the following line of code, where the
IReportingService is the class I want to time the method calls around, and the
LogTimingInterceptor is the class that captures the timing of the method call and sends it to the logger:
Hope someone else can find this useful,
The assignment statement is the von Neumann bottle-neck of programming languages and keeps us thinking in word-at-a-time terms in much the same way the computer’s bottleneck does.
John Backus, 1977
ACM Turing Award Lecture,
Communications of the ACM
August 1978, Volume 2, Number 8
I had a twisted thought about a potential future thought experiment of using XML and Lisp style languages.
Having used Lisp a very little bit back in college for one semester, and read more about it in Structure and Interpretation of Computer Programs, I started looking into Clojure recently. I did a session of CodeRetreat last year in it, and was hearing more about it this year at SCNA so I started to read up on it more and play a little bit with the language.
Tie that in with that I recently was transferred to a new group at work that is doing some SOA (Service Oriented Architecture) work. Something triggered when I thought about the XML payloads being sent between the SOA Web Services and how that tied into what I am reading about Lisp and Clojure.
In other languages we think about serializing command objects into XML and back and send those messages between Services as a message payload. What made me think was that XML is a tree structure as well as the code in a Lisp type language.
I don’t know if this is a novel idea, or if someone else has already tried it, but to me it seems like an interesting thing to think about and mull over.