Ghostbusters 2

We can simplify this problem up front by asking "is there a solution given a stream length of X." We can find the maximum X later using binary search.

So how do we determine the stream length?

This is a bit of a logic problem.

say two points conflict if the streams are vertical for the length X. This means we have an implication:

vertical(a) => horizontal(b)

meaning, if point a is in the vertical configuration, then in a valid solution, b must be horizontal. So vertical-a "implies" horizontal-b.

If we consider the boolean expression that is true when the above implication holds, we get !vertical(a) || horizontal(b). (note that !vertical(x) == horizontal(x) for all x). Take a second to convince yourself that it's true. If horizontal(a) e, then it doesn't matter what b is because the implication ends up not applying. If horizontal(b), then it doesn't matter what a is, since the implication will apply.

So anyway, this gives us a bunch of boolean literals (just say horizontal == true, vertical == false) of the form a || b or !a || !b, and for the whole thing to be a valid arrangement, all of them must be true. So we just have to find an assignment of all the variables such that the expression evaluates to true!

This is known as 2SAT (2-satisfiability). Here's how the solution works:

create graph nodes for each boolean literal and it's inverse (a, !a, b !b...etc). This would represent a node each representing a point being horizontal or vertical. For each implication, add a directed edge to the graph. So for our implication above, we'd have an edge going from !a -> b (since a being vertical "forces" b to be horizontal). Compute the strongly connected components of that graph, and if any strongly connected component contains both a variable and its inverse (meaning that a-> !a, and !a->a), we know there is no solution!

So the full algorithm is

1. start with length = 1
2. while evaluate(length) succeeds, double length
   1. calculate all implications (conflicts) for the length
   2. create the graph of all those implications as described above
   3. run SCC
   4. evaluate each SCC to see if it contains a literal and its inverse, if so, fail
3. binary search over length to find the longest length for which evaluate(length) returns true

evaluate takes n^2 to build the graph (can be optimized, but not necessary), and SCC linear in the number of nodes (2n). binary search adds log(n) factor, so solution is fast enough.