From e1f3fd5fcd45efdb223ebaa16524ed7c821caa39 Mon Sep 17 00:00:00 2001
From: Tyler Wardhaugh <tyler.wardhaugh@gmail.com>
Date: Sat, 14 Nov 2020 10:09:50 -0800
Subject: Ch86 (Lua): Task 1 and 2

For the Sudoku puzzle solver, I ported Peter Norvig's solver[1] from Python
to Lua. On that page there are submissions for other ports as well.

--

[1] Solving Every Sudoku Puzzle, http://norvig.com/sudoku.html
---
 challenge-086/tyler-wardhaugh/lua/README.md |   1 +
 challenge-086/tyler-wardhaugh/lua/ch-1.lua  |  28 ++++
 challenge-086/tyler-wardhaugh/lua/ch-2.lua  | 250 ++++++++++++++++++++++++++++
 challenge-086/tyler-wardhaugh/lua/run.lua   |   9 +
 challenge-086/tyler-wardhaugh/lua/test.lua  |  23 +++
 5 files changed, 311 insertions(+)
 create mode 100755 challenge-086/tyler-wardhaugh/lua/ch-1.lua
 create mode 100755 challenge-086/tyler-wardhaugh/lua/ch-2.lua
 create mode 100755 challenge-086/tyler-wardhaugh/lua/run.lua
 create mode 100755 challenge-086/tyler-wardhaugh/lua/test.lua

diff --git a/challenge-086/tyler-wardhaugh/lua/README.md b/challenge-086/tyler-wardhaugh/lua/README.md
index 5a776b300d..ad70c646d1 100644
--- a/challenge-086/tyler-wardhaugh/lua/README.md
+++ b/challenge-086/tyler-wardhaugh/lua/README.md
@@ -21,3 +21,4 @@ Run the project's tests (all the samples from the task descriptions plus some ot
 *   [Lua](https://www.lua.org/) 5.3
 *   [LuaRocks](https://luarocks.org/)
 *   [busted](https://olivinelabs.com/busted/) (a unit testing framework)
+*   [Moses](https://yonaba.github.io/Moses/) (a Lua utility-belt library)
diff --git a/challenge-086/tyler-wardhaugh/lua/ch-1.lua b/challenge-086/tyler-wardhaugh/lua/ch-1.lua
new file mode 100755
index 0000000000..8e9eda4572
--- /dev/null
+++ b/challenge-086/tyler-wardhaugh/lua/ch-1.lua
@@ -0,0 +1,28 @@
+#!/usr/bin/env lua
+
+local t1 = {}
+
+function t1.pair_difference(target, coll)
+  local freq = {}
+  for _, v in ipairs(coll) do freq[v] = (freq[v] or 0) + 1 end
+
+  for k, v in pairs(freq) do
+    if (freq[k + target]) and ((target ~= 0) or (v > 1)) then
+      return 1
+    end
+  end
+
+  return 0
+end
+
+function t1.run(args)
+  local target = tonumber(args[1])
+  table.remove(args, 1)
+
+  local coll = {}
+  for _, v in ipairs(args) do table.insert(coll, tonumber(v)) end
+
+  print(t1.pair_difference(target, coll))
+end
+
+return t1
diff --git a/challenge-086/tyler-wardhaugh/lua/ch-2.lua b/challenge-086/tyler-wardhaugh/lua/ch-2.lua
new file mode 100755
index 0000000000..2b3a453fdb
--- /dev/null
+++ b/challenge-086/tyler-wardhaugh/lua/ch-2.lua
@@ -0,0 +1,250 @@
+#!/usr/bin/env lua
+
+--[[
+    This is a Lua implementation of Peter Novig's excellent sudoku solver,
+    originally written in Python:
+      [Solving Every Sudoku Puzzle](http://norvig.com/sudoku.html)
+--]]
+
+local M = require('moses')
+
+local t2 = {}
+
+
+--[[ utility ]]--
+function t2.contains(tbl, elem)
+  for _, v in pairs(tbl) do
+    if v == elem then return true end
+  end
+  return false
+end
+
+function t2.slurp(input)
+  local fh = assert(io.open(input, "r"))
+  local text = fh:read("*all")
+  fh:close()
+  return text
+end
+
+function t2.deep_copy(tbl)
+  local copy = {}
+  for k, v in pairs(tbl) do
+    copy[k] = v
+  end
+  return copy
+end
+
+function t2.dict(tbl)
+  local result = {}
+  for _, v in pairs(tbl) do
+    result[v[1]] = v[2]
+  end
+  return result
+end
+
+function t2.cross(a, b)
+  local result = {}
+  for _, aa in ipairs(a) do
+    for _, bb in ipairs(b) do
+      table.insert(result, aa .. bb)
+    end
+  end
+  return result
+end
+
+function t2.build_unitlist(rows, cols)
+  local result = {}
+  for _, c in ipairs(cols) do table.insert(result, t2.cross(rows, {c})) end
+  for _, r  in ipairs(rows) do table.insert(result, t2.cross({r}, cols)) end
+
+  for rs in M.partition(rows, 3) do
+    for cs in M.partition(cols, 3) do
+      table.insert(result, t2.cross(rs, cs))
+    end
+  end
+
+  return result
+end
+
+function t2.center(s, width)
+  local space = width - #s + 1
+  local n = math.floor(space/2)
+  local lead = ((n > 1) and (' '):rep(n)) or ''
+  return lead .. s .. (' '):rep(space - n)
+end
+
+--[[ unit tests ]]--
+function t2.test()
+    assert(#t2.squares == 81)
+    assert(#t2.unitlist == 27)
+    assert(M.all(M.map(t2.squares, function (v) return #t2.units[v] == 3 end), M.identity))
+    assert(M.all(M.map(t2.squares, function (v) return #t2.peers[v] == 20 end), M.identity))
+
+    assert(M.isEqual(t2.units['C2'], {
+      {'A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'},
+      {'C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'},
+      {'A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3'}}))
+
+    local c2_peers = {'A2', 'B2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2', 'C1',
+      'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9', 'A1', 'A3', 'B1', 'B3'}
+    assert(M.isEqual(
+      M.symmetricDifference(t2.peers['C2'], c2_peers),
+      M.symmetricDifference(c2_peers, t2.peers['C2'])))
+end
+
+--[[ parse a grid ]]--
+function t2.grid_values(grid)
+  local chars = M.tabulate(grid:gsub(';.-[\r\n]',''):gmatch'[%d_.]')
+  assert(#chars == 81)
+  return t2.dict(M.zip(t2.squares, chars))
+end
+
+function t2.parse_grid(grid)
+  local values = {}
+  for _, s in pairs(t2.squares) do values[s] = table.concat(t2.digits) end
+
+  for s, d in pairs(t2.grid_values(grid)) do
+    if t2.contains(t2.digits, d) and not t2.assign(values, s, d) then
+      return false
+    end
+  end
+  return values
+end
+
+--[[ constraint propagation ]]--
+function t2.assign(values, s, d)
+  local other_values = values[s]:gsub(d, '')
+  for d2 in other_values:gmatch'%d' do
+    if not t2.eliminate(values, s, d2) then
+      return false
+    end
+  end
+
+  return values
+end
+
+function t2.eliminate(values, s, d)
+  if not values[s]:match(d) then
+    return values
+  end
+  values[s] = values[s]:gsub(d, '')
+
+  -- (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
+  if values[s]:len() == 0 then
+    return false
+  elseif values[s]:len() == 1 then
+    local d2 = values[s]
+    for _, s2 in ipairs(t2.peers[s]) do
+      if not t2.eliminate(values, s2, d2) then
+        return false
+      end
+    end
+  end
+
+  -- (2) If a unit u is reduced to only one place for a value d, then put it there.
+  local dplaces
+  for _, u in ipairs(t2.units[s]) do
+    dplaces = {}
+    for _, v in ipairs(u) do
+      if values[v]:match(d) then table.insert(dplaces, v) end
+    end
+    if #dplaces == 0 then
+      return false
+    elseif #dplaces == 1 then
+      -- d can only be in one place in unit; assign it there
+      if not t2.assign(values, dplaces[1], d) then
+        return false
+      end
+    end
+  end
+
+  return values
+end
+
+--[[ display as 2-D grid ]]--
+function t2.display(values)
+  local width = 1 + M.max(t2.squares, function (v) return #values[v] end)
+  local line = table.concat(M.rep(string.rep('-', (width * 3)), 3), '+')
+
+  local closer
+  for _, r in ipairs(t2.rows) do
+    for _, c in ipairs(t2.cols) do
+      if ((c == '3') or (c == '6')) then closer = '|' else closer = '' end
+      io.write(t2.center(values[r .. c], width) .. closer)
+    end
+    print()
+    if ((r == 'C') or (r == 'F')) then print(line) end
+  end
+  print()
+end
+
+--[[ search ]]--
+function t2.choose_unfilled(values)
+  local min_len
+  local min_val
+  local cur_len
+  for _, v in pairs(t2.squares) do
+    cur_len = values[v]:len()
+    if cur_len > 1 then
+      if not min_len or ((cur_len <= min_len) and (v <= min_val)) then
+        min_len = cur_len
+        min_val = v
+      end
+    end
+  end
+
+  return min_val
+end
+
+function t2.search(values)
+  if not values then
+    return false --failed earlier
+  end
+  if M.all(t2.squares, function (v) return values[v]:len() == 1 end) then
+    return values --solved
+  end
+  -- chose the unfilled square s with the fewest possibilities
+  local s = t2.choose_unfilled(values)
+
+  local result
+  for d in values[s]:gmatch'%d' do
+    result = t2.search(t2.assign(t2.deep_copy(values), s, d))
+    if result then return result end
+  end
+end
+
+function t2.solve(grid)
+  return t2.search(t2.parse_grid(grid))
+end
+
+--[[ Setup ]]--
+do
+  t2.digits = M.map(M.range(9), tostring)
+  t2.rows = M.tabulate(('ABCDEFGHI'):gmatch '.')
+  t2.cols = t2.digits
+  t2.squares = t2.cross(t2.rows, t2.cols)
+  t2.unitlist = t2.build_unitlist(t2.rows, t2.cols)
+
+  t2.units = {}
+  t2.peers = {}
+  for _, s in ipairs(t2.squares) do
+    t2.units[s] = M.filter(t2.unitlist, function (v) return t2.contains(v, s) end)
+    t2.peers[s] = M.symmetricDifference(M.union(table.unpack(t2.units[s])), {s})
+  end
+end
+
+function t2.run(args)
+  --t2.test()
+
+  local filename = args[1]
+  local grid = t2.slurp(filename)
+  local values = t2.solve(grid)
+
+  if values then
+    t2.display(values)
+  else
+    print("Can't solve!")
+  end
+end
+
+return t2
diff --git a/challenge-086/tyler-wardhaugh/lua/run.lua b/challenge-086/tyler-wardhaugh/lua/run.lua
new file mode 100755
index 0000000000..c6e7473bee
--- /dev/null
+++ b/challenge-086/tyler-wardhaugh/lua/run.lua
@@ -0,0 +1,9 @@
+#!/usr/bin/env lua
+
+local filename = arg[1]
+local run_args = table.move(arg, 2, #arg, 1, {})
+
+io.write(string.format("Running task from '%s' with {%s}:\n",
+  filename, table.concat(run_args, ", ")))
+
+require(filename).run(run_args)
diff --git a/challenge-086/tyler-wardhaugh/lua/test.lua b/challenge-086/tyler-wardhaugh/lua/test.lua
new file mode 100755
index 0000000000..1c0e7f7964
--- /dev/null
+++ b/challenge-086/tyler-wardhaugh/lua/test.lua
@@ -0,0 +1,23 @@
+#!/usr/bin/env lua
+
+require 'busted.runner'()
+
+describe("Task 1, Triplet Sum", function()
+  local t1 = require'ch-1'
+  it("produces correct results for the examples", function()
+    assert.are.same(t1.pair_difference(7, {10, 8, 12, 15, 5}), 1)
+    assert.are.same(t1.pair_difference(6, {1, 5, 2, 9, 7}), 1)
+    assert.are.same(t1.pair_difference(15, {10, 30, 20, 50, 40}), 0)
+    assert.are.same(t1.pair_difference(0, {100, 1, 2, 3, 4, 5, 100, 999, 999}), 1)
+    assert.are.same(t1.pair_difference(0, {100, 1, 2, 3, 4, 5, 101}), 0)
+  end)
+end)
+
+describe("Task 2, Sudoku Puzzle", function()
+  local t2 = require'ch-2'
+  it("produces correct results for the examples", function()
+    assert.truthy(t2.solve(t2.slurp('../clojure/resources/sudoku-1')))
+    assert.truthy(t2.solve(t2.slurp('../clojure/resources/sudoku-2')))
+    assert.truthy(t2.solve(t2.slurp('../clojure/resources/sudoku-3')))
+  end)
+end)
-- 
cgit