Instantly share code, notes, and snippets.

# autotelicum/amb.coffee

Created October 25, 2011 04:06
Show Gist options
• Save autotelicum/1311262 to your computer and use it in GitHub Desktop.
Ambiguous amb function with permutations and eight queens solver
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 # Amb was first proposed by John McCarthy, the inventor of LISP, in 1963. show = console.log copy = (array) -> array.slice() pick = (v) -> v[Math.floor Math.random() * v.length] remove = (array, value) -> array.filter (v,i,o) -> v isnt value fail = -> throw fail amb = (valueList, func, failResult = null) -> values = copy valueList while values.length > 0 try return value if func value = pick values catch ex throw ex unless ex is fail finally values = remove values, value failResult # Find a small integer that doubled gives eight. g = 8 show amb [1..9], (v) -> 2*v is g permutations = (elements) -> N = elements.length result = [] indexes = [] indexes[i] = i for i in [0...N] add = (partial) -> amb indexes, (p) -> for i in [partial.length..0] fail() if partial[i] is p a = partial.concat [p] if a.length == N result.push a.map (i) -> elements[i] else add a fail() add [] result # Generate a list of variations of the argument elements show permutations [1,3,5] queens = (N) -> result = [] indexes = [] indexes[i] = i for i in [0...N] add = (partial) -> amb indexes, (p) -> for i in [partial.length..0] fail() if partial[i] is p or partial.length - i is Math.abs partial[i] - p a = partial.concat [p] if a.length is N then result.push a else add a fail() add [] result # Solve Eight Queens puzzle show solutions = queens 8 show "Found #{solutions.length} solutions" # Repeat a string a number of times rep = (s, n) -> (s for [0...n]).join '' # Display a board with a solution printBoard = (solution) -> board = "\n" end = solution.length for pos, row in solution board += "#{end - row} #{rep ' ☐ ', pos} " + "♕ #{rep ' ☐ ', end - pos - 1}\n" # Using radix 18 hack! board += ' ' + (n.toString 18 \ for n in [10...18]).join(' ').toUpperCase() board + "\n" (solutions.map printBoard).map (b) -> show b