Styjun

The problem

You are given a board of size a by a. There're n components on the board, which have to be connected to the edges of the board with minimal length of wires possible.

Wires are straight and can't overlap.

Find the algorithm to do connect the components to the edges with these constraints.

Contstraints are:

time: 1s

space: infinity

1 <= a <= 30

1 <= n <= 38

Example:

Input:
4
3
2 1
2 3
3 3

Output:
5
DOWN
UP
UP

What I've already tried

I found a kind of recursion, let me show the idea with data provided above.

I have a n-bit mask, where 1 on i-th position represents, that we take this component into account, while 0 not.

When I start recursion I have n ones:

 111
 / | 
 / | 
 011 101 110
 / / / 
001 010 001 100 010 100

When I came to the lowest level, I have exactly one 1. I find optimal solution (shortest way) for this simple problem and then I just use it for further computations.

However, I have a problem, that this optimal solution may lead to overlapping.

For now I can't really see something better or more clever than a branch and bound approach to solve that. It is somehow similar to what you have proposed, but does not have redundant calculations.

Here it is briefly described as a pythonic pseudocode:

def BnB(grid, components):
 queue = new_priority_queue() # classic priority queue
 empty_sol = [None for i in range(len(components))] # we create an 'empty' solution
 queue.push((0, 0, empty_sol)) # we push an initial empty solution on the queue (a tuple total len, index, solution)
 best_length_so_far = infinite # we keep track of the best solution seen so far
 best_sol_so_far = None
 while not queue.is_empty():
 length, index, solution = queue.pop()
 if index == len(components): # it is a feasible solution
 if best_len_so_far > length:
 best_len_so_far = length
 best_sol_so_far = solution
 elif length < best_len_so_far:
 # check if components[index] can have its wire 'DOWN'
 if can_put_wire(grid, components, index, 'DOWN'):
 length_to_add = path_len(grid, component, index, 'DOWN')
 new_sol = copy(solution)
 new_sol[index] = 'DOWN'
 queue.push((length + length_to_add, index + 1, new_sol))
 # do the same thing for the other directions
 if can_put_wire(grid, components, index, 'UP'):
 ....
 if can_put_wire(grid, components, index, 'LEFT'):
 ....
 if can_put_wire(grid, components, index, 'RIGHT'):
 ....
return best_sol_so_far

The exploration of the solutions tree would depend on how you set the priorities on your queue. The choice of the component to consider (rather than to take them in the order like in the code above) could also help to have solutions faster.
This will not be efficient (complexity in time exponential w.r.t the number of components), but it can find the solution.

Another possibility is to use ILP (integer linear programming) to solve the problem. It can be rather easily described with linear constraints, and would enjoy all the optimizations offered by a LP solver.