Computer science textbooks use Eight Queens as an introduction to recursion. The problem concerns the placement of eight queens on a chessboard such that no queen attacks another. I remember trying to find a solution on paper but failing miserably.

Ten years later, I decide to ‘complete’ my computer science education by implementing a solution that combines recursion with a back-tracking approach. The code produces the correct solutions but may benefit from optimisation.

I intend to revise my solution at a later date, but for now, I thought I’d share my approach with my readers.

The Javascript Solution

function copyOf(arrTemp) {
  var arrCopy = [];
  for (var nSlot = 0; nSlot < arrTemp.length; ++nSlot) {
    arrCopy.push({row: arrTemp[nSlot].row, col: arrTemp[nSlot].col,
                  front: arrTemp[nSlot].front, back: arrTemp[nSlot].back,
                  queen: arrTemp[nSlot].queen});
  }
  return arrCopy;
}

function isSolution (arrCandidate) {
  function isSingleMatch(arrCandidate, strProperty){
    var nCount = 2 * arrCandidate.length - 1;
    var arrHits = [];
    for (var nSlot = 0; nSlot < nCount; ++nSlot)
      arrHits.push(0);
    for (var nSlot = 0; nSlot < arrCandidate.length; ++nSlot)
      arrHits[arrCandidate[nSlot][strProperty]]++;
    for (var nSlot = 0; nSlot < arrHits.length; ++nSlot)
      if (arrHits[nSlot] > 1)
        return false;
    return true;
  }
  return isSingleMatch(arrCandidate, "row") &&
         isSingleMatch(arrCandidate, "col") &&
         isSingleMatch(arrCandidate, "front") &&
         isSingleMatch(arrCandidate, "back");
}

function buildBoard (nRows, nCols) {
  var tablePositions = [];
  for (var nRow = 0; nRow < nRows; ++nRow) {
    var arrRow = [];
    for (var nCol = 0; nCol < nCols; ++nCol)
      arrRow.push({row: nRow, col: nCol,
                   front: (nRow + nCol), back: (nRows - 1 - nRow + nCol),
                   queen: false});
    tablePositions.push(arrRow);
  }
  return tablePositions;
}

function getMatches (tblPositions, nCol, arrMatches, arrCandidate, nRows) {
  if (nCol == nRows) {
    if (isSolution (arrCandidate))
      arrMatches.push (copyOf(arrCandidate));
  } else {
    for (var nRow = 0; nRow < nRows; ++nRow) {
      tblPositions[nRow][nCol].queen = true;
      arrCandidate.push(tblPositions[nRow][nCol]);
      getMatches (tblPositions, nCol + 1, arrMatches, arrCandidate, nRows);
      tblPositions[nRow][nCol].queen = false;
      arrCandidate.pop();
    }
  }
  return arrMatches;
}

function showResults (arrMatches) {
  console.log ("Found " + arrMatches.length + " matches");
  for (var nSlot = 0; nSlot < arrMatches.length; ++nSlot) {
    var strBuf = "R C\n";
    for (var i = 0; i < arrMatches[nSlot].length; ++i) {
      strBuf += (arrMatches[nSlot][i].row);
      strBuf += " ";
      strBuf += (arrMatches[nSlot][i].col);
      strBuf += (i == arrMatches[nSlot].length - 1) ? "\n\n" : "\n";
    }
    console.log(strBuf);
  }
}

function main () {
  showResults(getMatches(buildBoard(8, 8), 0, [], [], 8));
}

Eight Queens in Clojure

Posted: May 26, 2012 in Clojure

Computer science textbooks use Eight Queens as an introduction to recursion. The problem concerns the placement of eight queens on a chessboard such that no queen attacks another. I remember trying to find a solution on paper but failing miserably.

Ten years later, I decide to ‘complete’ my computer science education by implementing a solution that combines recursion with a back-tracking approach. The code produces the correct solutions but may benefit from optimisation.

I intend to revise my solution at a later date, but for now, I thought I’d share my approach with my readers.

The Clojure Solution

(ns org-debugme-eight-queens.core
  (:use [clojure.contrib.combinatorics :as comb :only [cartesian-product]])
  (:use [clojure.string :as str :only [join]])
  (:gen-class))
  
(defrecord Cell [row col front back queen])

(defn buildboard [rows cols]
  (vec (for [row (range rows)]
    (vec (for [col (range cols)] 
      (Cell. row col (+ row col) (+ (- rows 1 row) col) false))))))
    
(defn- solution? [cells]
  (let [valid? (fn [key] (= (count cells) (count (distinct (map #(key %) cells)))))]
    (every? true? (map valid? [:row :col :front :back]))))
    
(defn- describe [cells]
  (str/join "\n"
    (for [cell cells]
      (str "[R=" (:row cell) ",C=" (:col cell) "]"))))
 
(defn -main [& args]
  (let [board (buildboard 8 8)
        permutes (apply comb/cartesian-product board)
        solution (filter solution? permutes)
        as-words (map describe solution)]
        (println as-words)))

As a child I was fascinated by vending machines. The idea that you could pop in a few shiny coins and be presented with a chocolate bar was great. As an adult I wondered what logic was used to determine how a vending machine gave out change.

It would have to factor in what coins were available as well as what the best combination of coins to return would be. Ideally it would degrade gracefully based on the number and type of coins in the machine at any time. Thinking about a problem only gets you so far and in my case I had a sudden itch to see what a solution would look like.

The Clojure Solution

(ns org-debugme-change-generator.core
  (:use [clojure.contrib.combinatorics :as comb :only [cartesian-product]])
  (:use [clojure.string :as str :only [join]])
  (:gen-class))  

; Represents a coin which is in stock
(defrecord Coin [label value count])

(defn- describe [coins]
  "Provide a simple string description of coins"
  (str/join "," 
    (for [coin coins :when (> (:count coin) 0)]
      (str (:label coin) "*" (:count coin)))))

(defn- coin-box []
  "Create a box of coins as demo data for this program"
  (let [value-count [[20 2][10 3][5 2][2 4][1 12]]
        create-coin (fn [[v c]] (Coin. (str v "p") v c))
        all-coinage (map create-coin value-count)]
        all-coinage))
  
(defn- filter-coins [coins change]
  "Calculate the set of coins which can be used to provide change"
  (for [coin coins :when (<= (:value coin) change)]
    (let [in-stock-coins (:count coin) 
          required-coins (quot change (:value coin))
          relevant-coins (Math/min in-stock-coins required-coins)]
          (assoc coin :count relevant-coins))))
          
(defn- expand-coins [coins]
  "Find all possible permutations of count for each coin"
  (for [coin coins]
    (for [new-count (reverse (range (inc (:count coin))))]
      (assoc coin :count new-count))))
      
(defn- total-value [coins]
  "Find sum of product of each coin count and value"
  (reduce + (map #(* (:count %) (:value %)) coins)))
  
(defn- solve-combos [expanded-coins change]
  (filter #(= (total-value %) change) (apply comb/cartesian-product expanded-coins)))

(defn -main [& args]
  "Calculate permutations of change based on stocked coins"
  (let [[payment cost] (map #(Integer/parseInt %) args)
        change (- payment cost)
        filtered-coins (filter-coins (coin-box) change)
        expanded-coins (expand-coins filtered-coins)
        coinage-combos (solve-combos expanded-coins change)]
        (map describe coinage-combos)))

Number Pronouncer in Clojure

Posted: May 5, 2012 in Clojure
Tags:

Before credit cards and online banking, cheques were the usual way in which to transfer funds. Your bank would supply you with a special booklet called a cheque book, on whose pages you could specify a payee and an amount in numbers and in words. Watching my mother fill out a cheque once made me think.

When you see the number “123” how do you derive the word description of “one hundred and twenty three”? What happens with larger numbers? Is there a method with which a person could arrive at the pronounced form of a number? How difficult would it be to capture that logic as a set of discrete steps that a computer could follow?

The code below implements an algorithm which attempts to answer this question.

Enjoy.


(ns org-debugme-pronounce.core
  (:use [clojure.string :as str :only [join blank?]])
  (:use [clojure.pprint :as pp :only [cl-format]])
  (:use [clojure.contrib.seq-utils :as su :only [indexed]])
  (:gen-class))
  
(defn- as-integers [str-value]  
  "Builds sequence of digits from characters in string
   For example: (as-integers "123") => (1 2 3)"
  (let [str-number (str (Integer/parseInt str-value 10))
        seq-number (map #(Character/getNumericValue %) str-number)]
        seq-number))

(defn- pad-number [seq-number size]
  "Builds sequence prefixed with enough zeroes to make its length divisible by size
   For example: (pad-number '(1 2 3 4) 3) => '(0 0 1 2 3 4)"
  (let [length (count seq-number)
        remainder (rem length size)
        padded-length (if (zero? remainder) length (+ length (- size remainder)))
        leading-zeros (take (- padded-length length) (repeat 0))
        padded-number (concat leading-zeros seq-number)]
        padded-number))
        
(defn- conjunction [indexed-tuple]
  "Returns conjunction that should preceed tuple or blank if none needed"
  (let [index (first indexed-tuple)
        tuple (second indexed-tuple)
        is-first-tuple (zero? index)
        all-zeroes  (every? zero? tuple)
        starts-with-zero (zero? (first tuple))
        avoid-conjunction (or is-first-tuple all-zeroes (not starts-with-zero))
        conjunction (if avoid-conjunction "" "and")]
        conjunction))
        
(defn- describe [number]
  "Builds a non-conjunction resolved word description of the passed in number
   For example: (describe 12) => \"Twelve\""
  (if (zero? number) "" (pp/cl-format false "~R" number)))
  
(defn- magnitude [indexed-tuple]
  "Returns a magnitude based on index of tuple
   For example, (magnitude '(0 (1 2 3))) => \"\"
                (magnitude '(1 (1 2 3))) => \"thousand\"
                (magnitude '(2 (1 2 3))) => \"million\""
  (let [index (first indexed-tuple)
        size (count (second indexed-tuple))
        number (Math/pow 10 (* index size))
        description (describe number)
        magnitude (if (zero? index) "" (second (.split description " ")))]
        magnitude)) 

(defn- describe-tuple [[v1 v2 v3]]
  "Builds a string describing the numbers whose digits are passed in
   For example: (describe-tuple '(1 2 3)) => \"one hundred and twenty three\""
  (let [tens-delimiter (if (or (zero? v1) (every? zero? [v2 v3])) "" " and ")
        units-delimiter (if (or (zero? v2) (= 1 v2) (zero? v3)) "" \space)
        build (comp (partial str tens-delimiter) describe)
        hundreds (describe (* 100 v1))
        tens (if (= 1 v2) (build (+ 10 v3)) (build (* 10 v2))) 
        units (if (= 1 v2) "" (str units-delimiter (describe v3)))
        description (str hundreds tens units)]
        description))

(defn- description [indexed-tuple]
  "Builds a conjunction resolved, word description of the passed in tuple
   For example, (description (1 2 3)) yields 'one hundred and twenty three'"
  (let [index (first indexed-tuple)
        tuple (second indexed-tuple)
        is-zero (and (zero? index)(every? #(= 0 %) tuple))
        str-description (if is-zero "zero" (describe-tuple tuple))]
        str-description))

(defn- connective [operand1 operand2]
  "Returns a connective appropriate for the passed in operands"
  (if (or (empty? operand1) (empty? operand2)) 
    "" 
    \space))

(defn- as-string [conjunction connective1 description connective2 magnitude]
  "Builds string description of arguments"
  (if (blank? description) 
    "" 
    (apply str conjunction connective1 description connective2 magnitude)))
    
(defn- as-indexed-tuples [str-value size]
  "Builds tuples based on the passed in value and size
   For example: (as-indexed-tuples "123456" 3) => '((1 2 3)(4 5 6))"
  (let [cleaned-number (as-integers str-value)
        padded-number (pad-number cleaned-number size)
        tuples (partition size padded-number)
        indexed-tuples (su/indexed tuples)]
        indexed-tuples))
        
(defn- spoken-form [conjunctions descriptions magnitudes]
  "Joins the passed in arguments using appropriate connectives into a descriptive string"
  (let [connectives1 (map connective conjunctions descriptions)
        connectives2 (map connective descriptions magnitudes)
        values (map as-string conjunctions connectives1 descriptions connectives2 magnitudes)
        pronounced (.trim (str/join \space values))]
        pronounced))

(defn pronounce [str-value]
  "Returns conjunction resolved pronounced form of the passed in value"
  (let [indexed-tuples (as-indexed-tuples str-value 3)
        conjunctions (map conjunction indexed-tuples)
        descriptions (map description indexed-tuples)
        magnitudes  (map magnitude (reverse indexed-tuples))
        pronounced (spoken-form conjunctions descriptions magnitudes)] 
        pronounced))

(defn -main [& args]
  (if (pos? (count args))
    (pronounce (first args))))

Recently I wanted to learn about back-tracking as a problem solving strategy. Although I had read about how it could be applied to solve certain types of textbook problem (e.g. Eight Queens, Knights Tour) I had never tried to use the ideas to solve my own problem.

An opportunity arose whilst visiting my sister and hearing her remark how she and her husband sometimes played Sudoku. Sudoku? Hmm. Surely that would be amenable to a back-tracking approach? I have never found the prospect of Sudoku interesting, despite seeing my fellow commuters avidly getting their daily fix in the morning commute. But as a problem to solve, it suddenly became much more appealing.

Solving the problem yielded the solution below:

Acknowledgements: The elegant getBoxInfo() implementation was suggested by my good friend Mark Holland

The Javascript Solution

function buildBoard (arrPartial) {

  function getBoxInfo (nRow, nCol) {
    return (3 * parseInt(nRow / 3)) + parseInt(nCol / 3);
  }
  
  function getOptions (nValue) {
    var arrOptions = [];
    if (nValue == 0) {      
      for (var nSlot = 1; nSlot < 10; ++nSlot)
        arrOptions.push({value: nSlot, active: true});
      return arrOptions;
    } else {
      return arrOptions;
    }
  }
  
  function getRowSlot (nRow, nSlot, nSize) {
    var arrSlots = [];
    for (var nIndex = 0; nIndex < nSize; ++nIndex) {    
      var nNewRow = parseInt (nIndex / 9);
      if ((nNewRow == nRow) && (nIndex != nSlot))
        arrSlots.push(nIndex);
    }
    return arrSlots;
  }
  
  function getColSlot (nCol, nSlot, nSize) {
    var arrSlots = [];
    for (var nIndex = 0; nIndex < nSize; ++nIndex) {
      var nNewCol = (nIndex % 9);
      if ((nNewCol == nCol) && (nIndex != nSlot))
        arrSlots.push(nIndex);
    }
    return arrSlots;
  }
  
  function getBoxSlot (nBox, nSlot, nSize) {
    var arrSlots = [];
    for (var nIndex = 0; nIndex < nSize; ++nIndex) {
      var nNewRow = parseInt (nIndex / 9);
      var nNewCol = nIndex % 9;
      var nNewBox = getBoxInfo(nNewRow, nNewCol);
      if ((nNewBox == nBox) && (nIndex != nSlot))
        arrSlots.push(nIndex);
    }
    return arrSlots;
  }
  
  function getMapInfo (nSlot, arrPartial) {
    var mapInfo = {};
    mapInfo["rawIndex"] = nSlot;
    mapInfo["rowIndex"] = parseInt (nSlot / 9);
    mapInfo["colIndex"] = nSlot % 9;
    mapInfo["boxIndex"] = getBoxInfo (mapInfo.rowIndex, mapInfo.colIndex);
    mapInfo["rawValue"] = arrPartial [nSlot];
    mapInfo["rowSlots"] = getRowSlot (mapInfo.rowIndex, nSlot, arrPartial.length);
    mapInfo["colSlots"] = getColSlot (mapInfo.colIndex, nSlot, arrPartial.length);
    mapInfo["boxSlots"] = getBoxSlot (mapInfo.boxIndex, nSlot, arrPartial.length);
    mapInfo["optValue"] = getOptions (mapInfo.rawValue);
    return mapInfo;
  }
  
  function makeABoard () {
    if (!arrPartial) {
      arrPartial = [];
      for (var nSlot = 0; nSlot < 81; ++nSlot)
        arrPartial.push(0);
    }
    var arrBoard = [];
    for (var nSlot = 0; nSlot < arrPartial.length; ++nSlot)
      arrBoard.push(getMapInfo(nSlot, arrPartial));
    return arrBoard;   
  }
  
  return makeABoard (arrPartial);
}

function solveBoard (nFrom, nUpto, arrBoard, tblBoard) {

  function isValid (nValue, nIndex, arrBoard) {
    var arrRowSlots = arrBoard[nIndex].rowSlots;
    for (var nSlot = 0; nSlot < arrRowSlots.length; ++nSlot) 
      if (nValue == arrBoard[arrRowSlots[nSlot]].rawValue)
        return false;

    var arrColSlots = arrBoard[nIndex].colSlots;
    for (var nSlot = 0; nSlot < arrColSlots.length; ++nSlot) 
      if (nValue == arrBoard[arrColSlots[nSlot]].rawValue) 
        return false;
        
    var arrBoxSlots = arrBoard[nIndex].boxSlots;
    for (var nSlot = 0; nSlot < arrBoxSlots.length; ++nSlot) 
      if (nValue == arrBoard[arrBoxSlots[nSlot]].rawValue) 
        return false;
        
    return true;
  }
  
  function cloneOf (arrBoard) {
    var arrCopy = [];
    for (var nSlot = 0; nSlot < arrBoard.length; ++nSlot) {
      var mapInfo = {};
      mapInfo.rawIndex = arrBoard[nSlot].rawIndex;
      mapInfo.rowIndex = arrBoard[nSlot].rowIndex;
      mapInfo.colIndex = arrBoard[nSlot].colIndex; 
      mapInfo.boxIndex = arrBoard[nSlot].boxIndex;
      mapInfo.rawValue = arrBoard[nSlot].rawValue;
      mapInfo.rowSlots = arrBoard[nSlot].rowSlots;
      mapInfo.colSlots = arrBoard[nSlot].colSlots;
      mapInfo.boxSlots = arrBoard[nSlot].boxSlots;
      mapInfo.optValue = arrBoard[nSlot].optValue;
      arrCopy.push(mapInfo);
      
    }
    return arrCopy;
  }
  
  function resolve (nFrom, nUpto, arrBoard, tblBoard) {
    if (nFrom == nUpto) {
      tblBoard.push(cloneOf(arrBoard));
    } else if (arrBoard[nFrom].rawValue != 0) {
        resolve (nFrom + 1, nUpto, arrBoard, tblBoard);
    } else {
       var arrOption = arrBoard[nFrom].optValue;       
       var nOldValue = arrBoard[nFrom].rawValue;
       for (var nSlot = 0; nSlot < arrOption.length; ++nSlot) {
         var nNewValue = arrOption[nSlot].value;
         if (isValid (nNewValue, nFrom, arrBoard)) {
           arrBoard[nFrom].rawValue = nNewValue;
           resolve (nFrom + 1, nUpto, arrBoard, tblBoard);
         }
       }    
       arrBoard[nFrom].rawValue = nOldValue;
    }
  }
  
  resolve (nFrom, nUpto, arrBoard, tblBoard);
}

function printBoard (arrBoard) {
  var strBuf = "\n";
  var nLastIndex = arrBoard.length - 1;
  for (var nIndex = 0; nIndex < arrBoard.length; ++nIndex) {
    var value = arrBoard[nIndex].rawValue;
    strBuf += ((value == 0) ? " " : value);
    var slot = nIndex + 1;
    if (slot % 3 == 0 && slot % 9 != 0)
      strBuf += "|";
    if (slot % 9 == 0)
      strBuf += "\n";
    if (slot % 27 == 0 && nIndex < nLastIndex)
      strBuf += "---+---+---\n";
  }
  console.log(strBuf);
}

function main () {
  function testSolver () {
    var arrPartial = [
      0,0,2,5,0,0,0,0,3,
      0,4,0,0,6,7,0,0,0,
      1,5,0,0,0,3,0,0,0,
      0,0,8,0,0,0,0,0,4,
      5,6,0,0,0,0,0,1,7,
      4,0,0,0,0,0,8,0,0,
      0,0,0,6,0,0,0,8,1,
      0,0,0,1,8,0,0,2,0,
      2,0,0,0,0,5,7,0,0   
    ]; 
    
    var tblBoard = [];
    var arrBoard = buildBoard (arrPartial);
    solveBoard (0, arrBoard.length, arrBoard, tblBoard);
    var nSols = tblBoard.length;
    console.log("Found " + nSols + " solution" + (nSols == 1 ? "" : "s"));
    for (var nSlot = 0; nSlot < nSols; ++nSlot)
      printBoard (tblBoard[nSlot]);
  }
  
  testSolver();
}

main ();

Clojure vs Java(script)

Posted: April 24, 2012 in Clojure
Tags: ,

Clojure claims to eliminate the boilerplate code and ceremony required by mainstream languages. We have been interviewing for developer roles recently and to make the process more interactive, I wrote a small problem for applicants to solve. It occurred to me that I could solve this problem in Java and Javascript (mainstream languages) and then compare those solutions to a Clojure one. Surely that would be a reasonable way of establishing the veracity of the earlier claim?

The Problem
Write a program that accepts a range of integers and a user defined predicate. The program should sum up all integers which satisfy the predicate and return the total to the caller.

So for example, you could write a program that took the values from 1 to 10, a predicate which matched odd numbers only and returned the sum of all the values which passed the predicate i.e. in this case the total would be sum of the odd numbers between 1 and 10 which comes to 25 .

We then added one simplifying condition and two bounding constraints
(*) The user could assume that the set of integers would be from 1 to 100 inclusive
(*) The user was not allowed to use loops i.e. no for, while, do..while loops
(*) The solution would need to be in Java or Javascript

The solutions I came up with are listed below.

The Java Solution

public class RunProgram {

	interface Predicate {
		boolean isValid (int nValue);
	}

	private static int sum (int nTotal, int nFrom, int nUpto, Predicate predicate) {
		if (nFrom > nUpto) 
			return nTotal;
		else if (predicate.isValid (nFrom))
			return sum (nTotal + nFrom, nFrom + 1, nUpto, predicate);
		else
			return sum (nTotal, nFrom + 1, nUpto, predicate);
	}

	public static void main (String[] args) {
		Predicate predicate = new Predicate () {
			public boolean isValid (int nValue) {
				return (nValue % 2 == 1);
			}
		};
		System.out.println (sum (0, 1, 10, predicate));
	}
}

The Javascript Solution

function sum (nTotal, nFrom, nUpto, predicate) {
    if (nFrom > nUpto)
      return nTotal;
    else if (predicate (nFrom))
      return sum (nTotal + nFrom, nFrom + 1, nUpto, predicate);
    else
      return sum (nTotal, nFrom + 1, nUpto, predicate);
}

var predicate = function (n) { return (n % 2 == 1); };
console.log (sum (0, 1, 10, predicate));

The Clojure Solution

(println (reduce + (filter odd? (range 1 10))))

Guess which language I intend to read up on.