Belt Balancer problem (Factorio)

UTU = Universally throughput unlimited

There exist UTU balancers for 3, 4, and 5 belts, and likely for any number of belts. Examples are given in this Jupyter notebook, along with a Python implementation of an iterative algorithm for computing the flow for any set of belts and splitters.

I will quote some of the notebook here for those who don't wish to follow the link. I refer to splitters as junctions, since that's how they really function.

Each belt is composed of unit length segments, referred to in the game as tiles. In the model, we imagine each belt flowing from left to right along coordinate direction $x$ and each junction uniting two belts at the left edge of a given tile. Note that some balancers used in practice contain loops and could not be represented by our model without an infinite length belt.

The state of a belt tile is represented by a density $0 \le \rho \le 1$ and a velocity $0 \le v \le 1$. The value $v=1$ is the normal belt speed, and $\rho=1$ is the maximum capacity of a belt. Clearly, we can only have $v<1$ if $\rho=1$; this is a state in which the belt is fully loaded and there is not enough outflow downstream.

The inflow upstream is specified by the density $\rho_{up}$ at the left edge of the domain ($x=0$) and the outflow downstream is specified by $v_{down}$ at the right edge of the domain. For the purposes of testing UTU, we are only interested in setting these values to zero or one, but more general values will work with the algorithm below.

The main condition to be satisfied is conservation at each junction. The flux of items along a belt is given by the product $\rho v$, and we require that the flux going into a junction be equal to the flux coming out. It turns out to be much more complicated than I expected to satisfy this condition at each junction in a way consistent with how splitters work, and that is reflected in the code below. When I have time, I will hopefully add a more precise mathematical description of the conditions that are applied in the algorithm in order to achieve conservation.

Briefly: we initially set $\rho=0$ and $v=1$ everywhere except at the boundaries. At each iteration, we only increase $\rho$ and decrease $v$; the iterative values are always lower (respectively upper) bounds on the correct values. At each iteration, we check for junctions where inflow is greater than outflow (due to the conditions in the previous sentence, the opposite situation cannot happen) and adjust them in order to achieve conservation and equal outflow. If possible, outflow densities are increased to achieve this. If that's not possible (because one of the outflow densities reaches 1) then all excess outflow is assigned to the other belt. If that's not possible (because both outflow densities reach 1) then one or both of the inflow belts will fill up and slow down.

Here is a simplified view of one flow through a UTU 3-belt balancer: The numbers are densities and the colors are velocities. Again, flow is left to right, and each black line represents a junction ("splitter"). Here's what it looks like in the game:

This seems pretty simple and obvious; I'm surprised that it hasn't been posted in the Factorio forums already.

Here's a 4-belt UTU balancer:

and one way to construct it in-game:

I think this has already been invented and posted on the Factorio forums, although I came to it independently.

The notebook has a 5-belt balancer too, but I haven't taken the time to build it in-game.

The notebook includes code to generate and test all the required sets of inputs and outputs for the UTU property.

You'll notice that these balancers are built by naively putting as many junctions in as one can fit, and staggering them. I conjecture that if you do enough of this, you'll always get a UTU balancer, but I have no idea how the length of the balancer grows with the number of belts. Interestingly, my 4-belt balancer is shorter (in the model representation, where belts can be combined willy-nilly without worrying about the actual geometry) than the 3-belt balancer. But the 5-belt balancer is much longer.

The algorithm in the notebook could also be used to investigate other scenarios, such as $m$-to-$n$ balancers with $m$ not equal to $n$, or to test the idea put forward in other answers that a $2n$ UTU balancer can be built up from an $n$ UTU balancer. It would be straightforward to attach it to some brute-force or more intelligent search that tries to find the shortest possible balancer with some given properties.

I must say that I am surprised by the complexity of this problem, which I initially thought would be much easier to solve. In particular, I haven't yet been able to come up with an explicit approach to the solution, only the iterative algorithm in the notebook. Thanks for the very interesting problem.

Update: In the comments it is claimed that the 3-belt balancer fails if the top input and bottom output are disabled. Here is the picture for that situation, showing full throughput:

Notice that the splitters are doing exactly what @Rhamphoryncus claims they should. For instance, the splitter connecting the lower two belts on tile 2 (the third tile) pulls exactly 1/2 of a full belt from each of the two upstream belts. The same happens with the splitter joining those two belts on tile 4.

This isn't quite a math-y answer, but it sounds like you're reinventing the nonblocking minimal spanning switch and Clos networks. In this case, a splitter is essentially a 2x2 crossbar switch, and you're using them to build bigger switches.

As a simple example if you have a NxN switch (in this case, a 2x2 splitter), you can use 3N of them (3*2=6) to build a switch that is N²xN² (and thus, the popular 4x4 balancer design that uses 6 splitters).

If you wanted a 16x16, you could then take 12 of those 4x4 balancers, have 4 on the input side, 4 on the output side, and 4 in the middle, with every switch connected to every switch in the next stage with one belt. You could then repeat this process to get a 256x256, etc.

After that, I'm not entirely sure about the math, but I think you'd be able to, eg, cut a design in half to get half the throughput (eg, 6x 4x4 balancers to get a 8x8). You could then get things that aren't powers of 2 by just not connecting some of the inputs/outputs.

This is not a complete answer but

Assumption 1: a unlimited 4:4 balancer is possible. My belief is that this is throughput unlimited.

Take the design of the 4:4 balancer, replace each 2:2 balancer with a 4:4 balancer and you should have a 8:8 balancer which I believe to be unlimited

A bit more general: If we have an n:n balancer, where n is some power of 2, we can get 2n:2n by taking the design of the 4:4 balancer and replacing each 2:2 balancer with a n:n balancer.

This assumes that it is always geometrically possible.

By induction all powers of 2 should have throughput unlimited balancers.

Addendum 1: Assuming that the above holds then as throughput unlimited balancers are possible for powers of 2 a throughput unlimited balancer for a smaller number can be achieved by blocking of the extra inputs/outputs.

Addendum 2: (This is just pure speculation) If we have a set of belts in a certain order all heading in the same direction we should be able to switch place of any 2 belts in the order by having all other belts use underground belts for a few squares. Thus we can permute belts arbitrarily as any permutation of 2 belts is possible. This should mean that we can always build 2n:2n balancers from n:n ones.