## Protected: Another Chess Database

January 5, 2015## Coding challenge

November 2, 2011Here’s my brute-force clojure solution to Cedric Beust’s latest coding challenge. The code maintains a count of how many weights each combination can measure before iterating through the map and returning the maximum – which of course turns out to be all 40!

(def total 40) (defn check ([a target] (if (= a target) 1 0)) ([a b target] (if (or (= 1 (check a target)) (= 1 (check b target)) (= (+ a b) target) (= (- a b) target) (= (- b a) target)) 1 0)) ([a b c target] (if (= 0 (+ (check a b target) (check a c target) (check b c target) (check (+ a b) c target) (check (+ a c) b target) (check (+ b c) a target))) 0 1)) ([a b c d target] (if (= 0 (+ (check a b c target) (check a b d target) (check b c d target) (check (+ a b) c d target) (check (+ a c) b d target) (check (+ a d) b c target) (check (+ b c) a d target) (check (+ b d) a c target) (check (+ c d) a b target))) 0 1))) (defn numberOfWeights [combo] (loop [x 1 sum 0] (if (> x total) sum (recur (inc x) (+ sum (check (first combo) (second combo) (nth combo 2) (nth combo 3) x)))))) (defn run ([a b c d result] (let [combo [a b c d]] (if (= total (+ a b c d)) (assoc result combo (numberOfWeights combo)) result))) ([a b c result] (let [d (- total (+ a b c))] (if (< d 0) result (run a b c d result)))) ([a b result] (loop [c b r result] (if (>= (+ a b c) total) r (recur (inc c) (run a b c r))))) ([a result] (loop [b a r result] (if (>= (+ a b) (- total 1)) r (recur (inc b) (run a b r))))) ([] (loop [a 1 result {}] (if (>= a (- total 2)) result (recur (inc a) (run a result)))))) (def main (let [result (run)] (loop [resultKeys (keys result) maxKey nil maxValue 0] (let [candidate (first resultKeys)] (if (nil? candidate) {maxKey maxValue} (if (or (nil? maxKey) (> (get result candidate) maxValue)) (recur (next resultKeys) candidate (get result candidate)) (recur (next resultKeys) maxKey maxValue)))))))

Running it on the clojure console gives me:

user=> (load-file "/home/raghav/spikes/clojure/weights.clj") #'user/main user=> main {[3 9 27 1] 40}

## Parallel Sudoku

August 15, 2011Following on from my previous post where I wrote a Sudoku solver in Clojure, I tried to improve the performance of the algorithm by having each branch of my search tree execute in a separate thread. I first tried using the **ref** construct and while it solved the easy puzzle, there was a non-trivial bug which went into some infinite loop with the hard one. I finally gave up on it and decided to use the **agent** construct to notify the main thread when the puzzle was solved. The main thread just hangs around waiting for the agent state to change to the right solution.

While performance between the two solutions is interchangeable on the easy puzzle, there is a noticeable difference in the performance on the hard one – the parallel solution is consistently 3.5-4 times slower! I have tried changing around some of the parameters (increasing thread pool size to 1000, decreasing it to 4 – the number of cores on my laptop, increasing the sleep interval on the main thread to try and reduce the amount of processor time it grabs etc), all to no avail. I can’t believe context switching between threads costs so much more than the benefits of a parallel search.

**So, why is this slower (and by this magnitude)?** Alternatively, how could I profile this application (it takes approximately 4 seconds to run) to get some hints?

Here is the relevant additional code:

(def executors (java.util.concurrent.Executors/newFixedThreadPool 100)) (defn solve-in-parallel-worker [grid counter solution-agent] (if (>= counter (* size size)) (send-off solution-agent conj grid) (if (grid counter) (solve-in-parallel-worker grid (inc counter) solution-agent) (let [row-number (quot counter size) col-number (rem counter size) sub-grid-number [(quot row-number sqrt) (quot col-number sqrt)] ] (loop [possibles (seq (missing (clojure.set/union (row grid row-number) (col grid col-number) (sub-grid grid (sub-grid-number 0) (sub-grid-number 1))))) dummy nil] (if (nil? (first possibles)) nil (recur (next possibles) (.submit executors (fn[] (solve-in-parallel-worker (assign grid row-number col-number (first possibles)) (inc counter) solution-agent)))))))))) (defn solve-in-parallel [grid] (let [solution-agent (agent [])] (.submit executors (fn[] (solve-in-parallel-worker grid 0 solution-agent))) (while (= @solution-agent []) (Thread/sleep 1)) (first @solution-agent)))

## Clojure

July 27, 2011After ages and ages, I finally got into a new language. On the pretext of preparing for a brown bag session with the team, I started reading about Clojure and all of its benefits. The brown bag went off decently enough – I re-used Rich Hickey’s slides and talked about functional programming, Java inter-op and mainly the concurrency mechanisms. While preparing, I copy-pasted several bits of code, ran them etc and started getting a feel for the language. But the penny really dropped at the very end of the session when I was asked to write a simple hello world…and couldn’t! I later found (def hello (fn [] “Hello world”)) on the clojure website and promptly sent it off to the guys :)

Since I wasn’t totally put off by the language and even somewhat impressed by it, I decided I needed to do some hands-on development to learn the intricacies of the language. To begin with, I stayed away from all the concurrency constructs and picked a problem to try and tackle the functional elements – a sudoku problem solver. Its most likely not the most efficient algorithm though I might try to parallelize it.

- My “grid” is actually just a vector of 81 elements.
- Rows, columns and sub-grids are views of the appropriate indices on the vector.
**setup-grid**sets up the problem.**solve**uses brute-force in a depth-first manner to solve the puzzle.

**Easy**

3 - 8 2 9 1 - - - 1 7 9 - - - 2 6 - - - - - - 6 1 - - 8 - 5 1 - - 6 - - - - - 6 3 9 - - - - - 6 - - 8 3 - 2 - - 1 5 - - - - - - 5 4 - - - 8 1 7 - - - 8 1 7 4 - 6

**Evil**

- - 2 - - - - - 6 5 4 - 9 - - 2 - - - - - 8 2 - - - - - 5 - - - - 7 - - - - 4 7 1 6 5 - - - - 1 - - - - 8 - - - - - 9 2 - - - - - 9 - - 7 - 4 8 4 - - - - - 1 - -

(def size 9) (def sqrt (Math/sqrt size)) (def values (loop [c 1 v (set [])] (if (> c size) v (recur (inc c) (conj v (str c)))))) (defn index [x y] (+ (* x size) y)) (defn place [grid x y] (-> grid (nth (index x y)))) (defn assign [grid x y val] (assoc grid (index x y) (str val))) (defn setup-base-grid [] (vec (take (* size size) (cycle [nil])))) (defn setup-grid [init-setup] (loop [grid (setup-base-grid) ks (keys init-setup) vs (vals init-setup)] (if (and ks vs) (recur (assign grid ((first ks) 0) ((first ks) 1) (first vs)) (next ks) (next vs)) grid))) (defn row [grid x] (let [start (* x size) end (+ start size)] (subvec grid start end))) (defn col [grid y] (loop [c 0 v []] (if (>= c size) v (recur (inc c) (conj v (place grid c y)))))) (defn sub-grid [grid x y] (let [startx (* x sqrt) endx (+ startx sqrt) starty (* y sqrt) endy (+ starty sqrt)] (loop [c startx v []] (if (>= c endx) (vec v) (recur (inc c) (concat v (subvec (row grid c) starty endy))))))) (defn pretty-print [grid] (loop [c 0 out ""] (if (>= c size) (println (.replace (.replace (.replace out "nil" "-") "[" "") "]" "")) (recur (inc c) (str out (println-str (row grid c))))))) (defn missing [section] (clojure.set/difference values (set section))) (defn solve ([grid] (solve grid 0)) ([grid counter] (if (>= counter (* size size)) grid (if (grid counter) (solve grid (inc counter)) (let [row-number (quot counter size) col-number (rem counter size) sub-grid-number [(quot row-number sqrt) (quot col-number sqrt)]] (loop [possibles (seq (missing (clojure.set/union (row grid row-number) (col grid col-number) (sub-grid grid (sub-grid-number 0) (sub-grid-number 1)))))] (if (nil? (first possibles)) nil (let [possible-grid (solve (assign grid row-number col-number (first possibles)) (inc counter))] (if (nil? possible-grid) (recur (next possibles)) possible-grid)))))))))

## My first ever Gruenfeld

March 5, 2011I first looked at playing the Gruenfeld about a year ago. Shockingly, since then I hadn’t had anybody playing me as white, play 1. d4 and follow up with 2. c4! Anyway, it was a double-edged sword to play a new opening on the back of two (almost 3) losses. Replay here.

**1. d4 Nf6 2. c4 g6 3. Nc3 d5 4. cxd5 Nxd55. e4 Nxc3 6. bxc3 Bg7 7. Nf3 O-O **

(7… c5 is the main line)

**8. Qb3 **

(8. Be2)

**8… c5 9. Bb2 Qa510. Nd2 Nc6 **

(10… cxd4 11. cxd4 Nc6 12. d5 Nd4 13. Qd3 Nf3+ 14. Qxf3 Bxb2)

**11. Nc4 Qc7 12. d5 Ne5 13. Ne3 Ng4 **

(13… b5 14. Be2 (14. Bxb5 Rb8) 14…c4 15. Qc2)

**14. Nxg4 Bxg4 15. h3 Bd7 16. Bb5 Bxb5 17. Qxb5 c4 18. O-O a6 19. Qa4 b5 **

(19… f5)

**20. Qc2 Rfe8 21. Rad1 **

(21. a4)

**21… Rad8 22. Qd2 Rd7 23. f4 Red8 24. Ba3 a5**

(24… f5 25. d6 exd6 26. exf5 gxf5 27. Qd5+ Kh8)

**25. e5 Rxd5 **

(25… b4 26. cxb4 c3) (25… Bf8)

**26. Qxd5 Rxd5 27. Rxd5 b4 **

(27…Qb7 28. Rfd1 b4 29. Bb2 b3 30. axb3 cxb3 31. R1d4 Bh6 32. Kf2)

**28. cxb4 Qb6+ 29. Kh2 **

(29. Kh1)

**29… axb4 30. Rb1 Qe3 **

(30… Bh6 31. Bxb4 Bxf4+ 32. Kh1 Kg7)

**31. Bxb4 **

(31. Rd8+ Bf8 32. Bxb4 Qxf4+ 33. Kh1 Kg7)

**31… Qxf4+ 32.Kg1 Bxe5 33. Bxe7 **

(33. Re1)

**33… h5 **

(33… Qh2+ 34. Kf2 Bg3+ 35. Kf3 Bc7)

**34. Bc5 c3 35. Re1 Qh2+ 36. Kf1 Qh1+ **

(36… c2)

**37. Bg1 Bc7 38. Rb5 c2 39. Rc1 **

(39. Kf2 h4)

**39… Bf4 **

(39… Bh2 40. Kf2 Qxg1+ 41. Rxg1 Bxg1+ 42.Kxg1 c1=Q+)

**40. Rxc2 Bh2
**(40… Be3+?? 41. Rf2 Bxf2 42. Kxf2 and the queen is completely trapped!)

**41. a4 Qxg1+ 42. Ke2 Qxg2+ 43. Kd1 Qf1+ 44. Kd2 Bf4+45. Kc3 Qxh3+ 46. Kb4 Bd6+ 47. Kc4 Qe6+ 48. Rd5 Qe4+ 0-1**

## Writing a peer-peer application

February 27, 2011After spending more than a year writing a p2p application, I thought it was time for me to recap some of our experiences and summarise some of the essentials.

**Why p2p?**

**Scaling**

**High Availability/Failover**

**Distributed compute and resources**

**How p2p?**

**Programming paradigms**

**1. Many small services**

**2. Asynchronous behaviour**

**3. Multi-threaded behaviour versus Non-blocking code**

**4. Retry mechanisms**

**5. Idempotence**

**6. Everything is an ID**

**7. Backwards-compatible services**

**8. Shared resources**

**Messaging**

**Data storage and retrieval **

**Data is stored in a Distributed Hash Table**

**Replication**

**Optimistic concurrency**

**Transaction-less**

## Much better, but still losing…

February 27, 2011Playing white against a higher rated player who is on quite a hot streak, I played well for a long time and the game was quite drawish. Then I missed a chance to get a slight advantage and then misplayed the ending further, allowing my opponent to win quite easily in the end. Replay here.

**1. e4 c6 2. d4 d5 3. Nc3 dxe4 4. Nxe4 Nf65. Nxf6+ gxf6 6. Nf3 **

(6. c3)

**6… Bg4 7. Be2 e6 8. h3 **

(8. O-O)

**8… Bh5 9. Be3 Bd6 10. Qd2 Nd7 11. O-O-O Qc7 12. g4 Bg6 13. Bd3 O-O-O 14. Qe2 **

(14. c4)

**14…Kb8 15. Kb1 Nb6 16. Bxg6 hxg6 17. Nd2 **

(17. c4)

**17… f5 18. Nc4 f4 19. Bc1 **

(19.Nxd6 Qxd6 20. Bd2) (19. Nxb6 Qxb6 20. Bd2)

**19… g5 20. Nxb6 Qxb6 21. Qe4! Qb5 22. h4 Qd5 **

(22… Rxh4 23. Rxh4 gxh4 24. Bxf4 Qd5 25. Qxd5 cxd5 26. Bxd6+ Rxd6 27. Rh1 e5 28. dxe5 Rh6)

**23. Qxd5 cxd5 24. h5?! **

(24. hxg5 Rhg8 25. Rh5 Rg6 26.Rdh1) The idea here was to get a passed pawn of my own to counter my opponent’s passer on f4. I briefly considered 24. hxg5 but was worried that my doubled g-pawns were too weak and could be rounded up, perhaps remembering the fiasco from my previous game where I blundered with my 24th(!) move with 24… bxa4. This time around it was in fact the better move. Black could still round it up but f4 is now weaker and I could pick up black’s king-side pawns in the process. Whereas hxg5 would have given me a slight advantage, the move played still leaves the game balanced evenly.

**24… f5 25. f3 **

(25. Rdg1 fxg4 26. Rxg4 Be7 27. f3)

**25… fxg4 26. fxg4 e5 27. dxe5 Bxe5 28. b3 **

(28. Rhe1 Bf6 29. Re6 Rhf8 30. c4 d4 31. Kc2)

**28… Kc7 29. Ba3 Rd7 30. Bb2 **

(30. Rhe1)

**30… Bxb2 31. Kxb2 Rf8 32. Rd2 f3 33. Rf2 Rf4 34. h6 **

(34. Rh3 Rxg4 35. Rfxf3 Rh7 36. Rf5 Kd6 37. Rf6+ Ke5 38. Rg6)

**34… Rh7 35. Rh5 Kd6 36. Rxg5?**

(36. Kc3). I have perhaps played a couple of inaccuracies until this point but the game was still even. My next couple of moves however are enough to give black a winning advantage.

**36… Rxh6 37. Rf5? **

(37. Kc3)

**37… Rf6?! **

37…Rxf5! 38. gxf5 Rh3 39. f6 Ke6 40. Kc3 Kxf6 41. Kd4 Kf5 is an easier win.

**38. Rxf6+ Rxf6 39. g5 Rf4 40. Kc3 Ke5 41. Kd2 Kf5 42. g6 Ke4 43. Ke1 **

(43. Rf1 Rg4 44. Re1+ Kf4 (44…Kf5 45. Ke3) 45. Re6)

**43… Rg4 44. Rh2 Rxg6 45. Kf2 **

(45. Rh7)

**45… Rg2+ 46.Rxg2 fxg2 47. Kxg2 Kd4 48. Kf2 Kc3 49. Ke3 b5 50. b4 a6 51. Kf4 Kxb4 52. Ke5Kc4 53. a3 a5 54. Kd6 b4 55. a4 d4 56. Kc6 b3 57. cxb3+ Kxb3 58. Kb5 d3 59.Kxa5 d2 60. Kb5 d1=Q 61. a5 Qd8 62. a6 Qb8+ 0-1**