Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- _input = {
- ["Item1"] = {
- min = 1,
- max = 1,
- pos = {
- [1] = nil,
- [2] = {--[[somedata]]},
- [3] = nil,
- [4] = {--[[somedata]]},
- [5] = nil,
- [6] = {--[[somedata]]},
- [7] = nil,
- [8] = {--[[somedata]]},
- },
- },
- ["Item2"] = {
- min = 1,
- max = 1,
- pos = {
- [1] = nil,
- [2] = nil,
- [3] = nil,
- [4] = {--[[somedata]]},
- [5] = {--[[somedata]]},
- [6] = {--[[somedata]]},
- [7] = nil,
- [8] = nil,
- },
- },
- ["Item3"] = {
- min = 1,
- max = 2,
- pos = {
- [1] = nil,
- [2] = {--[[somedata]]},
- [3] = nil,
- [4] = {--[[somedata]]},
- [5] = {--[[somedata]]},
- [6] = {--[[somedata]]},
- [7] = nil,
- [8] = nil,
- },
- },
- ["Item4"] = {
- min = 1,
- max = 3,
- pos = {
- [1] = {--[[somedata]]},
- [2] = {--[[somedata]]},
- [3] = {--[[somedata]]},
- [4] = nil,
- [5] = nil,
- [6] = nil,
- [7] = {--[[somedata]]},
- [8] = {--[[somedata]]},
- },
- },
- }
- _output = {
- [1] = {
- type = "Item4",
- data = {--[[the data from _input["Item4"].pos[1] ]]},
- },
- [2] = {
- type = "Item1",
- data = {--[[the data from _input["Item1"].pos[2] ]]},
- },
- [3] = {
- type = "Item4",
- data = {--[[the data from _input["Item4"].pos[3] ]]},
- },
- [4] = {
- type = "Item3",
- data = {--[[the data from _input["Item3"].pos[4] ]]},
- },
- [5] = nil,
- [6] = {
- type = "Item2",
- data = {--[[the data from _input["Item2"].pos[6] ]]},
- },
- [7] = {
- type = "Item4",
- data = {--[[the data from _input["Item4"].pos[7] ]]},
- },
- [8] = nil,
- }
- local _output = {
- [1] = nil,
- [2] = nil,
- [3] = nil,
- [4] = nil,
- [5] = nil,
- [6] = nil,
- [7] = nil,
- [8] = nil,
- }
- for key in pairs(_input) do
- local _item = _input[key]
- for i=0,math.random(_item.min, _item.max),1 do
- -- I omit deepCopy() for readability
- local _possibleCopy = deepCopy(_item.pos)
- for i=1,8,1 do
- if _output[i] ~= nil then
- _possibleCopy[i] = nil
- end
- end
- local _possibleSlots = {}
- for i=1,8,1 do
- if _possibleCopy[i] ~= nil then
- _possibleSlots[#_possibleSlots+1] = i
- end
- end
- local _slot = _possibleSlots[math.random(1,#_possibleSlots)]
- if _slot then
- _output[_slot] = {
- type = key,
- data = _item.pos[_slot],
- }
- end
- end
- end
- math.randomseed(os.time())
- local _input = {
- ["Item1"] = {
- min = 1,
- max = 1,
- pos = {
- [1] = nil,
- [2] = {--[[somedata]]},
- [3] = nil,
- [4] = {--[[somedata]]},
- [5] = nil,
- [6] = {--[[somedata]]},
- [7] = nil,
- [8] = {--[[somedata]]},
- },
- },
- ["Item2"] = {
- min = 1,
- max = 1,
- pos = {
- [1] = nil,
- [2] = nil,
- [3] = nil,
- [4] = {--[[somedata]]},
- [5] = {--[[somedata]]},
- [6] = {--[[somedata]]},
- [7] = nil,
- [8] = nil,
- },
- },
- ["Item3"] = {
- min = 1,
- max = 2,
- pos = {
- [1] = nil,
- [2] = {--[[somedata]]},
- [3] = nil,
- [4] = {--[[somedata]]},
- [5] = {--[[somedata]]},
- [6] = {--[[somedata]]},
- [7] = nil,
- [8] = nil,
- },
- },
- ["Item4"] = {
- min = 1,
- max = 3,
- pos = {
- [1] = {--[[somedata]]},
- [2] = {--[[somedata]]},
- [3] = {--[[somedata]]},
- [4] = nil,
- [5] = nil,
- [6] = nil,
- [7] = {--[[somedata]]},
- [8] = {--[[somedata]]},
- },
- },
- }
- local function deepCopy(tbl)
- -- insert your implementation here
- end
- local input_keys = {} -- [input_key_idx] = input_key
- local available = {} -- [input_key_idx][1..8] = true/false
- local avail_counters = {} -- [input_key_idx][n] = count of available data items from 1 to n-1
- local min, max = {}, {} -- [input_key_idx] = min, max
- local spent_data_items = {} -- [input_key_idx] = number of data items included in _output
- local selected_data_items = {} -- [1..8] = input_key_idx/0
- local cache = {}
- local _output
- for k, v in pairs(_input) do
- table.insert(input_keys, k)
- local pos_avail = {}
- local avail_ctrs = {}
- local ctr = 0
- for i = 1, 8 do
- pos_avail[i] = not not v.pos[i]
- avail_ctrs[i] = ctr
- ctr = ctr + (pos_avail[i] and 1 or 0)
- end
- available[#input_keys] = pos_avail
- avail_counters[#input_keys] = avail_ctrs
- spent_data_items[#input_keys] = 0
- min[#input_keys] = v.min
- max[#input_keys] = v.max
- assert(ctr >= v.min and v.min <= v.max, "Solution does not exist")
- end
- local function enum_solutions(solution_no, n)
- -- returns the quantity of good selections
- n, solution_no = n or 8, solution_no or -1
- local cache_idx = n..";"..table.concat(spent_data_items, ";")
- local result = cache[cache_idx]
- if not result or solution_no >= 0 and solution_no < result then
- if n == 0 then
- -- found good selection (that satisfies the rules) in selected_data_items[1..8]
- if solution_no == 0 then
- _output = {}
- for n = 1, 8 do
- local key = input_keys[selected_data_items[n]]
- if key then
- _output[n] = {type = key, data = deepCopy(_input[key].pos[n])}
- end
- end
- end
- result = 1
- else
- local must_be_selected = {}
- for input_key_idx = 1, #input_keys do
- if available[input_key_idx][n] and avail_counters[input_key_idx][n] + spent_data_items[input_key_idx] < min[input_key_idx] then
- table.insert(must_be_selected, input_key_idx)
- end
- end
- if #must_be_selected == 1 then
- local input_key_idx = must_be_selected[1]
- local spent = spent_data_items[input_key_idx]
- spent_data_items[input_key_idx] = spent + 1
- selected_data_items[n] = input_key_idx
- result = enum_solutions(solution_no, n-1)
- spent_data_items[input_key_idx] = spent
- elseif #must_be_selected == 0 then
- -- selecting nil for position n
- selected_data_items[n] = 0
- result = enum_solutions(solution_no, n-1)
- solution_no = solution_no - result
- for input_key_idx = 1, #input_keys do
- if available[input_key_idx][n] then
- local spent = spent_data_items[input_key_idx]
- if spent < max[input_key_idx] then
- -- selecting _input[input_keys[input_key_idx]].pos[n] for position n
- spent_data_items[input_key_idx] = spent + 1
- selected_data_items[n] = input_key_idx
- local delta_result = enum_solutions(solution_no, n-1)
- result = result + delta_result
- solution_no = solution_no - delta_result
- spent_data_items[input_key_idx] = spent
- end
- end
- end
- else
- result = 0
- end
- end
- cache[cache_idx] = result
- end
- return result
- end
- local number_of_solutions = enum_solutions()
- assert(number_of_solutions > 0, "Solution does not exist")
- print("There are "..number_of_solutions.." solutions exist")
- -- generate 5 random solutions
- for _ = 1, 5 do
- local k = math.random(number_of_solutions)
- print("Solution #"..k)
- enum_solutions(k-1)
- -- now _output is initialized with k-th variant of solution
- for i = 1, 8 do
- local v = _output[i]
- if v then
- print(i, v.type, v.data)
- else
- print(i, "-")
- end
- end
- end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement