Code Trip
  • Blog
  • Archive
  • Projects
  • Portfolio
  • CV

Finding every configuration of blocks in a line

20/6/2016

0 Comments

 
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:
Picture
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.
 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)
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.
Picture
Picture
0 Comments



Leave a Reply.

    Author

    Connor Halford. Studied Computer Games Technology at Abertay, worked as a Games Programmer at MediaTonic, then Programmer at Climax, now Senior Gameplay Programmer at Failbetter.
    ​

    Useful Sites

    hilite.me converts source code into formatted, embeddable HTML without the need for CSS or Javascript.

    tablesgenerator.com performs a similar task as hilite.me but for tabular data.

    Archives
    All posts

    June 2017
    December 2016
    September 2016
    August 2016
    June 2016
    May 2016
    April 2016
    February 2016
    January 2016
    October 2015
    September 2015
    August 2015
    July 2015
    May 2015
    March 2015
    February 2015
    January 2015
    December 2014
    September 2014
    August 2014
    July 2014
    March 2014
    February 2014
    August 2013
    June 2013
    December 2012

    Categories

    All
    Advice
    AI
    Algorithms
    AMPS
    Audio
    Boost
    Box2D
    Coursework
    DirectX
    Flash
    Game Boy Advance
    Game Jam
    Graphics Programming
    Honours Project
    Maths
    Nonograms
    Oh God Why
    OpenGL
    PICO-8
    Pixel Art
    PlayStation 4
    PlayStation Vita
    Procedural Generation
    SFML
    Shaders
    Spirit Shift
    Twine
    Unity
    XAudio2
    Year 1
    Year 2
    Year 3
    Year 4

    RSS Feed

Powered by Create your own unique website with customizable templates.