Solving Sudoku with Clojure core.logic

Recently I had some fun solving Sudoku using Clojure.core.logic. Afterwards figuring out that it would actually be the example on the Wiki, but hey fun non the less and my solution actually is very close to the Wiki one, especially after cleaning it up.

I find core.logic fascinating as it allows to express logic problems in a very straight forward fashion, and given I will not learn Prolog anytime soon, it get me to some understanding of the ideas.

Solving a puzzle like Sudoku basically breaks down towards the following steps:

  1. Break down the puzzle according to the rules, in case of Sudoku this means defining rows, columns and squares
  2. Defining the variables for the pieces to be computed, in my case this means replacing input zeros with core.logic lvars.
  3. Define the rules, in case of Sudoku there are only, constraint on the numbers to 1-9, constraint on rows, columns and squares to have each number show up only once.
(defn solve
  "Takes a sudoku as a vector, with all empty cells set to 0 and returns
  a solved sudoku as a vector.

    [0 0 0 2 6 0 7 0 1
     6 8 0 0 7 0 0 9 0
     1 9 0 0 0 4 5 0 0
     8 2 0 1 0 0 0 4 0
     0 0 4 6 0 2 9 0 0
     0 5 0 0 0 3 0 2 8
     0 0 9 3 0 0 0 7 4
     0 4 0 0 5 0 0 3 6
     7 0 3 0 1 8 0 0 0])
  (let [board (vec (map #(if (zero? %) (lvar) %) sudoku))
        rows (indexed-sub-board board row-indexes)
        cols (indexed-sub-board board column-indexes)
        squares (indexed-sub-board board square-indexes)]

     (run 1 [q]
       (== q board)
       ;; only 1 - 9 are allowed
       (everyg #(fd/in % (fd/interval 1 9)) board)

       ;; every number can appear only once per row
       (everyg fd/distinct rows)
       ;; every number can appear only once per column
       (everyg fd/distinct cols)
       ;; every number can appear only once per square
       (everyg fd/distinct squares)))))

Overall the whole solution ended up very straight forward, the only problem I faced was the very macro heavy definition of core.logic, making debugging not as straight forward and I ended up reading a log of library code to figure out how things were supposed to work. But I guess this also comes from my general lack of knowledge in this specific kind of programming, and therefore having to read up on very basic concepts along the way.

The full code is available on github.

A Lisp in Clojure? How useless! But fun non the less.

Having found a nice post on how to built a simple lisp like (scheme like) language (How to Write a (Lisp) Interpreter (in Python)) I was wondering what would this look like in Clojure. Writing a lisp in Clojure sounded very useless and fun so here we go the result in on Github.

A couple interesting observations:

Since Clojure lends itself to using immutable datastructures the inital implementation of the evaluation seemed a little complex as it needs to receive the environment along with the next token. But as soon as I was implementing function calls this suddenly made the stacking of environments trivial. No complex chain maps etc. needed, nice!

clojure.core.match is a very nice little lib, I wish it was part of core Clojure by default. I had first implemented a giant cond statement, match made it much more concise and robust, as it not only asserts the matching symbol but also the parameters to it.

(defn lclj-eval
  "Eval a expression X in the context of environment ENV, defaults to
  ([x] (lclj-eval x lclj-base-env))
  ([x env]
   (match [x]
          [(_ :guard symbol?)] {:result ((keyword x) env) :env env}
          [(_ :guard number?)] {:result x :env env}
          [['if _ _ _]] (lclj-eval (if-branch x env) env)
          [['define _ _]] {:env (define-in-env x env)}
          [['quote _]] {:env env :result (-> x rest first)}
          [['lambda _ _]] {:env env :result (lclj-fn x env)}
          :else (lclj-fn-call x env))))

Obviously this can all be done better but it was a fun (I guess in total) afternoon for sure, having never written a lisp interpreter before.

Reversing collection vs Java Array in Clojure

How big is the overhead of using Clojure datastructures vs native Java Arrays? I was rather suprised to find it is lower than I expected, and the implementation looks much better using Clojure native vectors and lists than Java Arrays.

First an essentail when doing something like this

(set! *warn-on-reflection* true)

Without that it is easy to accidentally create arrays very inefficient calls via the array accessor and setter methods by having to rely on reflection. Now for the code

(defn hn-reverse
  (reduce #(conj %1 %2) '() coll))

Simple basic clojure implementation walking the incoming collection and prepending to a list.

Using criterium for a quick benchmark on my machine gives me

(let [v (vec (range 1000))]
  (bench (hn-reverse v)))

On my little XPS 13 gives me

Evaluation count : 2370120 in 60 samples of 39502 calls.
             Execution time mean : 26.090496 microsecond
    Execution time std-deviation : 832.330358 ns
   Execution time lower quantile : 25.220196 microsecond ( 2.5%)
   Execution time upper quantile : 28.154777 microsecond (97.5%)
                   Overhead used : 11.468971 ns

Found 5 outliers in 60 samples (8.3333 %)
  low-severe     5 (8.3333 %)
 Variance from outliers : 18.9765 % Variance is moderately inflated by outliers

Now how would an array perform here? (and yes I assumed it would be faster hence the name)

(defn fast-reverse
  [^ints array]
  ;; ^ints type annotation is essential here, otherwise this will be very slow
  ;; due to reflection on aget and aset
  (let [l (alength array)]
    (loop [i (dec l)
           j 0
           a (int-array l)]
      (if (= j l) a
            (aset a i (aget array j))
            (recur (dec i) (inc j) a))))))

Again quick criterium test

(let [a (int-array (range 1000))]
  (bench (fast-reverse a)))

This time

Evaluation count : 5851680 in 60 samples of 97528 calls.
             Execution time mean : 10.561515 microsecond
    Execution time std-deviation : 336.219142 ns
   Execution time lower quantile : 10.240088 microsecond ( 2.5%)
   Execution time upper quantile : 11.385153 microsecond (97.5%)
                   Overhead used : 11.468971 ns

Found 3 outliers in 60 samples (5.0000 %)
  low-severe     3 (5.0000 %)
 Variance from outliers : 18.9721 % Variance is moderately inflated by outliers

Using native Java Arrays is about 2.5x faster than clojure vector and list implentation in this case.

I somehow expected a bigger difference given the jump from immutable to mutable datastructures and the less allocations needed but it seems like this kind of optimization only really makes sense in the edge cases.

Counting vowels, in a more declerative manner

Playing with some clojure code while solving some of karan/Projects I discovered my solutions differ a lot when thinking in a functional way doing programming in Clojure than doing the same in Ruby some time ago. almost arriving at a declerative style in this case

(defn count-vowels
  "Take string S count vowels return map of vowel to count."
  (let [up-inc (fnil inc 0)
        counts (reduce #(update %1 (string/lower-case %2) up-inc) {} s)
        vowels #{"a" "e" "i" "o" "u"}]
    (select-keys counts vowels)))

 (generators/string generators/printable-ascii-char 1000))

Not sure why the concept of building a dataset and selecting what is relevant felt more natural than imperativly building up the data here, but it did for me somehow and the code reads quite nicely.

Playing with lazy-seq

Played a little with lazy-seq vs loop recur today, and got a suprise that lazy-seq is not as slow as I would have thought. Most likely the usecases are very different so by no means is this interchangably for most applications, but I assumed that a lazy-seq carries a lot of overhead. Don’t know why I thought that so, but playing around with it and timing the output I realized it seems to be a wrong assumption. By no means this is a real benchmark but it makes me read up more for sure.

(defn fib
  "Return the Nth fibonacci number."
  (loop [i n
         p 0
         pp 1]
    (if (zero? i)
      (recur (dec i) (+ pp p) p))))

(defn lazy-fib
  "Return the fibonacci sequence as a lazy sequence."
  ([] (lazy-fib 0 1))
  ([p pp] (lazy-seq (cons p (lazy-fib pp (+ p pp))))))

(let [n 60]
  (println "Nth number:")
  (time (fib n))
  (println "Non lazy:")
  (time (last (take n (map fib (range)))))
  (println "Lazy:")
  (time (last (take n (lazy-fib)))))

;; Nth number:
;; "Elapsed time: 0.022058 msecs"
;; Non lazy:
;; "Elapsed time: 0.133195 msecs"
;; Lazy:
;; "Elapsed time: 0.026575 msecs"

Seems like lazy-seq is at least same order of magnitude to just calculating N for fibonacci here, and creating a non lazy seq seems much slower. No optimization what so ever here, and also being pretty brute force about the recursion in the lazy-fib.

Clojure + Ring + API Gateway + Lambda

Serverless is all the rage right now, so I’ve been playing with AWS Lambda, and just by the name itself what could possibly be a better fit for lambda than using Clojure on it? Since I’m mostly interested in webapps I decied to give API Gateway a spin with lambda, sadly it does not immedialty work with the awesome Ring library for building web applications in clojure. Luckily it is reasonably easy to map between the two, and inspired by ring-aws-lambda-adapter some time later I now have a working version of Ring + API Gateway. Together with AWS SAM and AWS SAM CLI this makes for quite a nice, local or cloud, development and hacking experience. And all it took is about 90 lines of Clojure

(ns playground.core
  (:require [ :as json]
            [ :as io]
            [clojure.string :as s]
            [ring.util.codec :as codec]
            [ring.util.response :as r])
   :name playground.core.Handler
   :implements [])
  (:import [ RequestStreamHandler]
           [ InputStream File]
           [clojure.lang ISeq]))

(defn sample-handler
  (r/response "Hello Lambda, from ring!"))

(defn stream->event
  (json/read (io/reader in) :key-fn keyword))

(defn str->int
    (Integer/parseInt s)
    (catch NumberFormatException _)))

(defn maybe-remote-address
  "Take a guess at the remote client ip based on the X-FORWARDED-FOR header.
  This is not perfect as the X-FORWARDED-FOR can easily be spoofed. "
  (some-> x-forwarded-for
          (s/split #"," 2)

(defn maybe-http-version
  "Take http version frim VIA header if present"
  (some-> via
          (s/split #" " 2)

(defn api-gw-event->ring-request
  ([ev] (api-gw-event->ring-request ev nil))
  ([ev ctx]
   (let [headers (get ev :headers {})]
     {:server-port (str->int (:X-Forwarded-Port headers))
      :body (:body ev)
      :server-name (:Host headers)
      :remote-addr (maybe-remote-address (:X-Forwarded-For headers))
      :uri (:path ev)
      :query-string (codec/form-encode (get ev :queryStringParameters {}))
      :scheme (maybe-http-version (:Via headers))
      :request-method (:httpMethod ev)
      :protocol (:X-Forwarded-Proto headers)
      :headers headers
      :event ev
      :context ctx})))

(defmulti wrap-body class)
(defmethod wrap-body String [body] body)
(defmethod wrap-body ISeq [body] (s/join body))
(defmethod wrap-body File [body] (slurp body))
(defmethod wrap-body InputStream [body] (slurp body))

(defn ring-response->api-gw-response
  {:statuCode (:status response)
   :headers (:headers response)
   :body (wrap-body (:body response))})

(defn handle-request
  "Handle an api-gateway request from IN via a RING-HANDLER writing
  response to OUT."
  [ring-handler in out ctx]
  (let [event (stream->event in)
        request (api-gw-event->ring-request event ctx)
        response (ring-handler request)
        event-response (ring-response->api-gw-response response)]
    (with-open [w (io/writer out)]
      (json/write event-response w))))

(defn -handleRequest
  "Implementation for RequestStreamHandler handleRequest using IN
  instream OUT outstream and CTX context object, delegating to
  handle-request to handle request using ring"
  [_ in out ctx]
(handle-request sample-handler in out ctx))

All I want for XMas … is a Brainfuck interpreter in Clojure?

Over the holidays I felt it was time to play with a little Clojure, and since I recently became interested in compilers and interpreters I felt like it was a good idea to start extremly simple, it is the holidays after all. So I built the simplest possible interpreter, a Brainfuck interpreter. It is quite a need excercise and most certainly made me more interesting in building more complex ones.

So here it goes clojure-brainfuck for anyone interested.

First class functions over channels


Inspired by reading go-cache and reading about core.async I was interested how well sending functions over a channel can work, here is the quick hacky result.


Clojure with its access to a very concise way to construct functions lends itself very nicely to the idea of using CSP with first class functions as messages passed over a channel.

(let [c (chan)]
  (>!! c #(zero? %)))

Given that a channel is only consumed by one thread, this provides an interesting way to sync on a data structure without the need for explicit locking as the channel with by itself serialize the operations. This could be quite performant depending on the consumer as multiple operations could be pipelined for example by polling the channel for a batch of operations to be dispatched to different workers.

Why not?

This is mainly an idea taken from playing with go-lang and implemented in clojure, for access to a basic data structure like a map, even so it can now be a transient map, the built in transactions will provide much better performance.