1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
function block_char(block_id) local chars = "abcdefghij" return sub(chars, block_id, block_id) end function can_shift(line) return sub(line, #line, #line) == "-" end -- shifts all blocks of the given id or higher rightwards one cell, -- leaving all blocks left of that id unchanged function shift(line, block_id) local char = block_char(block_id) local pos = 1 for i = 1, #line do if sub(line, i, i) == char then pos = i break end end local pre = sub(line, 1, pos-1) local post = sub(line, pos, #line-1) return pre.."-"..post end function find_solutions(blocks, length, min_spaces) -- build and store the leftmost solution local line = "" for block_id = 1, #blocks do for i = 1, blocks[block_id] do line = line..block_char(block_id) end if block_id ~= #blocks then for i = 1, min_spaces do line = line.."-" end end end if (#line > length) return {} -- no solutions, can't fit while #line < length do line = line.."-" end local solutions = {line} find_spreads(solutions, line, 1, #blocks) return solutions end function find_spreads(solutions, line, block_id, num_blocks) local my_line = line while can_shift(my_line) do if block_id < num_blocks then find_spreads(solutions, my_line, block_id + 1, num_blocks) end my_line = shift(my_line, block_id) solutions[#solutions + 1] = my_line end end blocks = {2, 2, 2} length = 8 min_spaces = 0 solutions = find_solutions(blocks, length, min_spaces) |
Let's say we want to find every possible way of placing 3 blocks each of length 2 into a line which is 8 units long. There are 10 possible solutions:
How can we find these? I first encountered this problem during my honours project and the solution involves a nice little recursive function, so I thought I might as well share. We always begin by building the equivalent of the topmost solution above: all blocks adjacent to each other and as far left as possible. From here we take the rightmost block and shift it rightwards one cell at a time, storing the result, until we hit the end of the line. Then we grab the preceding block and shift that by one cell, then continue shifting the last block again. This will find all the configurations in the order given above, top to bottom. Below is a simple implementation in Lua where we're treating the line as a string for which each block has it's own letter and empty cells are '-'. The recursion happens in the find_spreads function.
Notice that this can also handle having a minimum number of spaces between each pair of blocks. I've made a little PICO-8 program to demonstrate the algorithm. Below left you can see the rendering of our example setup: block lengths of 2, 2, 2; line length of 8 and no minimum number of spaces. On the right is every configuration for block lengths 1, 2, 3; line length 11 and at least 1 space between each pair. If you didn't care about preserving block order and simply wanted every configuration of a set of blocks, you could run the above algorithm multiple times with every possible rearrangement of the initial block order.
Comments are closed.
|
THIS WEBSITE IS ABANDONED. GO HERE INSTEAD:
|