Ir para navegação Ir para pesquisar

A documentação para este módulo pode ser criada em Módulo:Solucionador de Torres/doc

```-- <pre>
local p = {}

local tableToString = require("Module:StringTables")._tableToString

-- This contains the filters to remove impossible heights. This works in combination with the "filterImpossibleHeights" function.
local firstFilter = {
["0"] = {type = "removeTowers", filter = "0"},
["1"] = {type = "towerFound",   filter = "5"},
["2"] = {type = "removeTowers", filter = {"5", "4"}},
["3"] = {type = "removeTowers", filter = {{"4", "5"}, "5"}},
["4"] = {type = "removeTowers", filter = {{"3", "4", "5"}, {"4", "5"}, "5"}},
["5"] = {type = "towerFound",   filter = {"1", "2", "3", "4", "5"}}
}

-- This contains all possible permutations of the heights and their respective visible towers
local permutations = {
{1,2,3,4,5, visible = 5},
{1,2,3,5,4, visible = 4},
{1,2,4,3,5, visible = 4},
{1,2,4,5,3, visible = 4},
{1,2,5,3,4, visible = 3},
{1,2,5,4,3, visible = 3},
{1,3,2,4,5, visible = 4},
{1,3,2,5,4, visible = 3},
{1,3,4,2,5, visible = 4},
{1,3,4,5,2, visible = 4},
{1,3,5,2,4, visible = 3},
{1,3,5,4,2, visible = 3},
{1,4,2,3,5, visible = 3},
{1,4,2,5,3, visible = 3},
{1,4,3,2,5, visible = 3},
{1,4,3,5,2, visible = 3},
{1,4,5,2,3, visible = 3},
{1,4,5,3,2, visible = 3},
{1,5,2,3,4, visible = 2},
{1,5,2,4,3, visible = 2},
{1,5,3,2,4, visible = 2},
{1,5,3,4,2, visible = 2},
{1,5,4,2,3, visible = 2},
{1,5,4,3,2, visible = 2},
{2,1,3,4,5, visible = 4},
{2,1,3,5,4, visible = 3},
{2,1,4,3,5, visible = 3},
{2,1,4,5,3, visible = 3},
{2,1,5,3,4, visible = 2},
{2,1,5,4,3, visible = 2},
{2,3,1,4,5, visible = 4},
{2,3,1,5,4, visible = 3},
{2,3,4,1,5, visible = 4},
{2,3,4,5,1, visible = 4},
{2,3,5,1,4, visible = 3},
{2,3,5,4,1, visible = 3},
{2,4,1,3,5, visible = 3},
{2,4,1,5,3, visible = 3},
{2,4,3,1,5, visible = 3},
{2,4,3,5,1, visible = 3},
{2,4,5,1,3, visible = 3},
{2,4,5,3,1, visible = 3},
{2,5,1,3,4, visible = 2},
{2,5,1,4,3, visible = 2},
{2,5,3,1,4, visible = 2},
{2,5,3,4,1, visible = 2},
{2,5,4,1,3, visible = 2},
{2,5,4,3,1, visible = 2},
{3,1,2,4,5, visible = 3},
{3,1,2,5,4, visible = 2},
{3,1,4,2,5, visible = 3},
{3,1,4,5,2, visible = 3},
{3,1,5,2,4, visible = 2},
{3,1,5,4,2, visible = 2},
{3,2,1,4,5, visible = 3},
{3,2,1,5,4, visible = 2},
{3,2,4,1,5, visible = 3},
{3,2,4,5,1, visible = 3},
{3,2,5,1,4, visible = 2},
{3,2,5,4,1, visible = 2},
{3,4,1,2,5, visible = 3},
{3,4,1,5,2, visible = 3},
{3,4,2,1,5, visible = 3},
{3,4,2,5,1, visible = 3},
{3,4,5,1,2, visible = 3},
{3,4,5,2,1, visible = 3},
{3,5,1,2,4, visible = 2},
{3,5,1,4,2, visible = 2},
{3,5,2,1,4, visible = 2},
{3,5,2,4,1, visible = 2},
{3,5,4,1,2, visible = 2},
{3,5,4,2,1, visible = 2},
{4,1,2,3,5, visible = 2},
{4,1,2,5,3, visible = 2},
{4,1,3,2,5, visible = 2},
{4,1,3,5,2, visible = 2},
{4,1,5,2,3, visible = 2},
{4,1,5,3,2, visible = 2},
{4,2,1,3,5, visible = 2},
{4,2,1,5,3, visible = 2},
{4,2,3,1,5, visible = 2},
{4,2,3,5,1, visible = 2},
{4,2,5,1,3, visible = 2},
{4,2,5,3,1, visible = 2},
{4,3,1,2,5, visible = 2},
{4,3,1,5,2, visible = 2},
{4,3,2,1,5, visible = 2},
{4,3,2,5,1, visible = 2},
{4,3,5,1,2, visible = 2},
{4,3,5,2,1, visible = 2},
{4,5,1,2,3, visible = 2},
{4,5,1,3,2, visible = 2},
{4,5,2,1,3, visible = 2},
{4,5,2,3,1, visible = 2},
{4,5,3,1,2, visible = 2},
{4,5,3,2,1, visible = 2},
{5,1,2,3,4, visible = 1},
{5,1,2,4,3, visible = 1},
{5,1,3,2,4, visible = 1},
{5,1,3,4,2, visible = 1},
{5,1,4,2,3, visible = 1},
{5,1,4,3,2, visible = 1},
{5,2,1,3,4, visible = 1},
{5,2,1,4,3, visible = 1},
{5,2,3,1,4, visible = 1},
{5,2,3,4,1, visible = 1},
{5,2,4,1,3, visible = 1},
{5,2,4,3,1, visible = 1},
{5,3,1,2,4, visible = 1},
{5,3,1,4,2, visible = 1},
{5,3,2,1,4, visible = 1},
{5,3,2,4,1, visible = 1},
{5,3,4,1,2, visible = 1},
{5,3,4,2,1, visible = 1},
{5,4,1,2,3, visible = 1},
{5,4,1,3,2, visible = 1},
{5,4,2,1,3, visible = 1},
{5,4,2,3,1, visible = 1},
{5,4,3,1,2, visible = 1},
{5,4,3,2,1, visible = 1}
}

-- Make a real copy of a table instead of referencing to the original table
-- @orig = table
-- @return = table
local function deepcopy(orig)
local orig_type = type(orig)
local copy
if orig_type == 'table' then
copy = {}
for orig_key, orig_value in next, orig, nil do
copy[deepcopy(orig_key)] = deepcopy(orig_value)
end
setmetatable(copy, deepcopy(getmetatable(orig)))
else -- number, string, boolean, etc
copy = orig
end
return copy
end

-- Reverse the input table around the center. {1, 2, 3} -> {3, 2, 1}
-- @t = table
-- @return = table
local function reverseTable(t)
local reversedTable = {}
local itemCount = #t
for i = 1, itemCount do
reversedTable[itemCount + 1 - i] = t[i]
end
return reversedTable
end

-- Extract a subsection from the "permutations" table
-- @arr = table
-- @selector = int
-- @pos = int (between 1 and 5)
-- @retrun = table
-- Example: subTable(permutations, 2, 3) returns all permutations with a value of 2 in the third position.
--          So "{5,1,2,4,3, visible = 1}", {3,5,2,4,1, visible = 2}, {1,5,2,3,4, visible = 2}, ... are part of the result
local function subTable(arr, selector, pos)
pos = tonumber(pos)
local subArr = {}
local index = 1

for row = 1, #arr do
if string.find(selector, arr[row][pos]) then
subArr[index] = arr[row]
index = index + 1
end
end

return subArr
end

-- Cleans the input "towers" when a solution "heights" is found at the "row" and "column" indices. When "heigths" is a table with multiple values then a direction "dir" can be given in wich multiple heights are found.
-- @towers = table
-- @row = int (between 1 and 5)
-- @column = int (between 1 and 5)
-- @heigths = int or table
-- @dir = string ("LRHor", "RLHor", "TBVer" or "BTVer"). Optional. "LRHor" stands for "from left to right horizontal"
-- @return = table
-- Example:
-- local towers = {
--     {"12345", "12345", "12345", "12345", "12345"},
--     {"12345", "12345", "12345", "12345", "12345"},
--     {"12345", "12345", "12345", "12345", "12345"},
--     {"12345", "12345", "12345", "12345", "12345"},
--     {"12345", "12345", "12345", "12345", "12345"}
-- }
-- towerFound(towers, 2, 3, {3, 5}, "LRHor")
-- Returns:
-- {
--     {"12345", "12345", "1245", "1234", "12345"},
--     {"124"  , "124"  , "3"   , "5"   , "124"  },
--     {"12345", "12345", "1245", "1234", "12345"},
--     {"12345", "12345", "1245", "1234", "12345"},
--     {"12345", "12345", "1245", "1234", "12345"}
-- }
local function towerFound(towers, row, column, heights, dir)
if type(heights) ~= "table" then
heights = {heights}
end

for i = 0, #heights - 1 do
if dir == "LRHor" then
towers = towerFound(towers, row, column + i, heights[i + 1])
elseif dir == "RLHor" then
towers = towerFound(towers, row, column - i, heights[i + 1])
elseif dir == "TBVer" then
towers = towerFound(towers, row + i, column, heights[i + 1])
elseif dir == "BTVer" then
towers = towerFound(towers, row - i, column, heights[i + 1])
end
end

if dir == nil then
for j = 1,5 do
towers[row][j] = towers[row][j]:gsub(heights[1], "")
end

for j = 1,5 do
towers[j][column] = towers[j][column]:gsub(heights[1], "")
end

towers[row][column] = heights[1]
end

end

-- Cleans the input "towers" by removing "heights" at the "row" and "column" indexes. When "heigths" is a table with multiple values then a direction "dir" can be given in wich multiple heights should be removed.
-- @towers = table
-- @row = int (between 1 and 5)
-- @column = int (between 1 and 5)
-- @heigths = int or table
-- @dir = string ("LRHor", "RLHor", "TBVer" or "BTVer"). Optional. "LRHor" stands for "from left to right horizontal"
-- @return = table
-- Example:
-- local towers = {
--     {"12345", "12345", "12345", "12345", "12345"},
--     {"12345", "12345", "12345", "12345", "12345"},
--     {"12345", "12345", "12345", "12345", "12345"},
--     {"12345", "12345", "12345", "12345", "12345"},
--     {"12345", "12345", "12345", "12345", "12345"}
-- }
-- removeTowers(towers, 2, 3, {{1, 2}, 5}, "LRHor")
-- Returns:
-- {
--     {"12345", "12345", "12345", "12345", "12345"},
--     {"12345", "12345", "345"  , "1234" , "12345"},
--     {"12345", "12345", "12345", "12345", "12345"},
--     {"12345", "12345", "12345", "12345", "12345"},
--     {"12345", "12345", "12345", "12345", "12345"}
-- }
local function removeTowers(towers, row, column, heights, dir)
if type(heights) ~= "table" then
heights = {heights}
end

for i = 1, #heights  do
local rowIndex = row
local columnIndex = column

if dir == "LRHor" then
columnIndex = column + i - 1
elseif dir == "RLHor" then
columnIndex =  column - i + 1
elseif dir == "TBVer" then
rowIndex = row + i - 1
elseif dir == "BTVer" then
rowIndex = row - i + 1
end

if type(heights[i]) == "table" then
towers = removeTowers(towers, rowIndex, columnIndex, heights[i])
else
towers[rowIndex][columnIndex] = towers[rowIndex][columnIndex]:gsub(heights[i], "")
end
end

end

-- Helper function to work together with the "firstFilter" table to remove a bunch of impossible heights to speed up later calculations
-- @towers = table
-- @row = int (between 1 and 5)
-- @column = int (between 1 and 5)
-- @dir = string ("LRHor", "RLHor", "TBVer" or "BTVer"). Optional. "LRHor" stands for "from left to right horizontal"
-- @digit = string ("1", "2", "3", "4", "5"). This is a user input of the total visible towers in a certain row/column
-- @return = table
local function filterImpossibleHeights(towers, row, column, dir, digit)
local filterSettings = firstFilter[digit]

if filterSettings.type == "towerFound" then
towers = towerFound(towers, row, column, filterSettings.filter, dir)
elseif filterSettings.type == "removeTowers" then
towers = removeTowers(towers, row, column, filterSettings.filter, dir)
end

end

-- Helper function for the "filterExlusiveHeights" function. This looks for heigths that only appear once in a row/column
-- @row = table (This is a subtable from "towers")
-- @return = table (this is a table where key, values represent found height, index of found height)
local function findExlusiveHeigths(row)
local lastFoundIndex = {['1'] = 0, ['2'] = 0, ['3'] = 0, ['4'] = 0, ['5'] = 0}
local foundMultiple = {['1'] = false, ['2'] = false, ['3'] = false, ['4'] = false, ['5'] = false}

for i = 1,5 do
for digit in string.gmatch(row[i], "%d") do
if lastFoundIndex[digit] ~= 0 then
foundMultiple[digit] = true
end
lastFoundIndex[digit] = i
end
end

local res = {}
for number,foundMulti in pairs(foundMultiple) do
if foundMulti == false and lastFoundIndex[number] ~= 0 then
res[number] = lastFoundIndex[number]
end
end

return res
end

-- Cleans the input "towers" by finding heights that only appear once in a row/column
-- @towers = table
-- @return = table, boolean
local function filterExlusiveHeights(towers)
local foundExclusion = false
local oldTowers = deepcopy(towers)

for row = 1,5 do
local currentRow = towers[row]
local exlusiveHeights = findExlusiveHeigths(currentRow)

for number,column in pairs(exlusiveHeights) do
towers = towerFound(towers, row, column, number)
end
end

for column = 1,5 do
local currentColumn = {towers[1][column], towers[2][column], towers[3][column], towers[4][column], towers[5][column]}
local exlusiveHeights = findExlusiveHeigths(currentColumn)

for number,row in pairs(exlusiveHeights) do
towers = towerFound(towers, row, column, number)
end
end

-- Check if towers table got changed
local newTowers = deepcopy(towers)
for i = 1,5 do
oldTowers[i] = table.concat(oldTowers[i])
newTowers[i] = table.concat(newTowers[i])
end
oldTowers = table.concat(oldTowers)
newTowers = table.concat(newTowers)

if oldTowers ~= newTowers then
foundExclusion = true
end

end

-- Helper function for the "validateSolution" function. Checks if the remaining heights in a row/column can result in the user given sum
-- @row = table (this is a subtable of "towers")
-- @visibleTowers = table (this table contains the user input)
local function checkVisibleTowerCounts(row, visibleTowers)
visibleTowers = tonumber(visibleTowers)

local posiblePermutations = subTable(permutations, row[1], 1)
posiblePermutations = subTable(posiblePermutations, row[2], 2)
posiblePermutations = subTable(posiblePermutations, row[3], 3)
posiblePermutations = subTable(posiblePermutations, row[4], 4)
posiblePermutations = subTable(posiblePermutations, row[5], 5)

for i = 1, #posiblePermutations do
if posiblePermutations[i].visible == visibleTowers then
return true
end
end

return false
end

-- Checks if the given "towers" table contains at least one solution
-- @towers = table
-- @topRow = table (user input)
-- @bottomRow = table (user input)
-- @leftColumn = table (user input)
-- @rightColumn = table (user input)
-- @return = boolean
local function validateSolution(towers, topRow, bottomRow, leftColumn, rightColumn)
-- Check for empty cells
for row = 1,5 do
for column = 1,5 do
if #towers[row][column] == "" then
return false
end
end
end

-- Check if # of visible towers matches
for i = 1,5 do
local currentRowLR = towers[i]
local currentRowRL = reverseTable(currentRowLR)
local currentColumnTB = {towers[1][i], towers[2][i], towers[3][i], towers[4][i], towers[5][i]}
local currentColumnBT = reverseTable(currentColumnTB)

if checkVisibleTowerCounts(currentRowLR, leftColumn[i]) == false
or checkVisibleTowerCounts(currentRowRL, rightColumn[i]) == false
or checkVisibleTowerCounts(currentColumnTB, topRow[i]) == false
or checkVisibleTowerCounts(currentColumnBT, bottomRow[i]) == false then
return false
end
end

return true
end

-- Checks if the given "towers" table is a single solution or a combination of multiple solutions
-- @towers = table
-- @return = boolean
local function checkIfSingularSolution(towers)
for row = 1,5 do
for column = 1,5 do
if #towers[row][column] > 1 then
return false, row, column
end
end
end

return true
end

-- Helper function for the "expandSolutions" function. Splits the "towers" table at the "row" "column" position, and cleans the subsolution untill all exclusive heights are removed.
-- @towers = table
-- @row = int (between 1 and 5)
-- @column = int (between 1 and 5)
-- @return = table (this contains the split towers table)
local function splitSolution(towers, row, column)
local res = {}

for digit in string.gmatch(towers[row][column], "%d") do
local tempTowers = deepcopy(towers)
tempTowers = towerFound(tempTowers, row, column, digit)
local foundExclusion = false
repeat
tempTowers, foundExclusion = filterExlusiveHeights(tempTowers)
until(foundExclusion == false)

res[#res + 1] = tempTowers
end

return res
end

-- Helper function for the "expandSolutions" function. This allows to append a table at the end of another table
-- @myTable = table (the table to append to)
-- @values = table (the table to be appended)
-- @retunr = table
local function insertMultiple(myTable, values)
local myTableLength = #myTable
for i = 1, #values do
local myTableIndex = myTableLength + i
myTable[myTableIndex] = values[i]
end

return myTable
end

-- Expands a combination of solutions into a table containing all singular solutions
-- @multiSolution = table
-- @return = table
local function expandSolutions(multiSolution)
local res = {}

local isSingular, rowIndex, columnIndex = checkIfSingularSolution(multiSolution)
if isSingular then
return {multiSolution}
else
for _,v in ipairs(splitSolution(multiSolution, rowIndex, columnIndex)) do
res = insertMultiple(res, expandSolutions(v))
end
end

return res
end

-- Used to generates the output of the module
-- @towers = table
-- @return = mw.html.table
local function generateOutputTable(towers)
local htmltable = mw.html.create("table")
:tag("tr")
:tag("td"):wikitext(towers[1][1]):done()
:tag("td"):wikitext(towers[1][2]):done()
:tag("td"):wikitext(towers[1][3]):done()
:tag("td"):wikitext(towers[1][4]):done()
:tag("td"):wikitext(towers[1][5]):done()
:done()
:tag("tr")
:tag("td"):wikitext(towers[2][1]):done()
:tag("td"):wikitext(towers[2][2]):done()
:tag("td"):wikitext(towers[2][3]):done()
:tag("td"):wikitext(towers[2][4]):done()
:tag("td"):wikitext(towers[2][5]):done()
:done()
:tag("tr")
:tag("td"):wikitext(towers[3][1]):done()
:tag("td"):wikitext(towers[3][2]):done()
:tag("td"):wikitext(towers[3][3]):done()
:tag("td"):wikitext(towers[3][4]):done()
:tag("td"):wikitext(towers[3][5]):done()
:done()
:tag("tr")
:tag("td"):wikitext(towers[4][1]):done()
:tag("td"):wikitext(towers[4][2]):done()
:tag("td"):wikitext(towers[4][3]):done()
:tag("td"):wikitext(towers[4][4]):done()
:tag("td"):wikitext(towers[4][5]):done()
:done()
:tag("tr")
:tag("td"):wikitext(towers[5][1]):done()
:tag("td"):wikitext(towers[5][2]):done()
:tag("td"):wikitext(towers[5][3]):done()
:tag("td"):wikitext(towers[5][4]):done()
:tag("td"):wikitext(towers[5][5]):done()
:done()

return htmltable
end

function p.main(frame)
local args = frame:getParent().args
-- local args = {in12 = "2", in13 = "2", in14 = "4", in15 = "3", in16 = "1", in72 = "3", in73 = "3", in74 = "1", in75 = "2", in76 = "2", in21 = "3", in31 = "1", in41 = "2", in51 = "2", in61 = "2", in27 = "1", in37 = "3", in47 = "3", in57 = "2", in67 = "2"}
-- local args = {in12 = "2", in13 = "2", in14 = "3", in15 = "3", in16 = "1", in72 = "3", in73 = "3", in74 = "1", in75 = "2", in76 = "2", in21 = "3", in31 = "1", in41 = "2", in51 = "2", in61 = "2", in27 = "1", in37 = "3", in47 = "3", in57 = "2", in67 = "2"}
-- local args = {in12 = "2", in13 = "2", in14 = "4", in15 = "3", in16 = "1", in72 = "2", in73 = "4", in74 = "1", in75 = "2", in76 = "4", in21 = "3", in31 = "2", in41 = "1", in51 = "4", in61 = "2", in27 = "1", in37 = "3", in47 = "2", in57 = "2", in67 = "3"}
-- local args = {in12 = "3", in13 = "1", in14 = "3", in15 = "2", in16 = "3", in72 = "3", in73 = "2", in74 = "2", in75 = "2", in76 = "1", in21 = "2", in31 = "3", in41 = "1", in51 = "2", in61 = "3", in27 = "3", in37 = "2", in47 = "2", in57 = "3", in67 = "1"}
-- local args = {in12 = "1", in13 = "3", in14 = "4", in15 = "2", in16 = "2", in72 = "3", in73 = "2", in74 = "2", in75 = "1", in76 = "2", in21 = "1", in31 = "3", in41 = "2", in51 = "2", in61 = "2", in27 = "3", in37 = "1", in47 = "3", in57 = "3", in67 = "2"}

local topRow = {
args['in12'] or '0',
args['in13'] or '0',
args['in14'] or '0',
args['in15'] or '0',
args['in16'] or '0'
}

local bottomRow = {
args['in72'] or '0',
args['in73'] or '0',
args['in74'] or '0',
args['in75'] or '0',
args['in76'] or '0'
}

local leftColumn = {
args['in21'] or '0',
args['in31'] or '0',
args['in41'] or '0',
args['in51'] or '0',
args['in61'] or '0'
}

local rightColumn = {
args['in27'] or '0',
args['in37'] or '0',
args['in47'] or '0',
args['in57'] or '0',
args['in67'] or '0'
}

local towers = {
{"12345", "12345", "12345", "12345", "12345"},
{"12345", "12345", "12345", "12345", "12345"},
{"12345", "12345", "12345", "12345", "12345"},
{"12345", "12345", "12345", "12345", "12345"},
{"12345", "12345", "12345", "12345", "12345"}
}

-- Apply first filter: remove impossible heights
for i = 1,5 do
towers = filterImpossibleHeights(towers, 1, i, "TBVer", topRow[i])
towers = filterImpossibleHeights(towers, 5, i, "BTVer", bottomRow[i])
towers = filterImpossibleHeights(towers, i, 1, "LRHor", leftColumn[i])
towers = filterImpossibleHeights(towers, i, 5, "RLHor", rightColumn[i])
end

-- Apply second filter: find exlusive heights
towers = filterExlusiveHeights(towers)

-- Apply third filter: contrain propagation
repeat
for row = 1,5 do
for column = 1,5 do
if #towers[row][column] > 1 then
for digit in string.gmatch(towers[row][column], "%d") do
local tempTowers = deepcopy(towers)
tempTowers = towerFound(tempTowers, row, column, digit)
local foundExclusion = false

repeat
tempTowers, foundExclusion = filterExlusiveHeights(tempTowers)
until(foundExclusion == false)

if validateSolution(tempTowers, topRow, bottomRow, leftColumn, rightColumn) == false then
towers = removeTowers(towers, row, column, digit)
end
end
end
end
end

-- return an error if the inputs don't have a solution
if validateSolution(towers, topRow, bottomRow, leftColumn, rightColumn) == false then
-- towers = {
--     {"", "", "", "", ""},
--     {"", "", "", "", ""},
--     {"", "", "", "", ""},
--     {"", "", "", "", ""},
--     {"", "", "", "", ""}
-- }
end

-- Split the combined result in individual solutions
local singularResults = expandSolutions(towers)

-- Return all solutions
local res = {}
for _,v in ipairs(singularResults) do
if validateSolution(v, topRow, bottomRow, leftColumn, rightColumn) == true then
res[#res + 1] = tableToString(generateOutputTable(v))
end
end

return table.concat(res)
end

return p
```