I think you could get a square-root reduction in the memory requirements by splitting the resistor networks in half. That's possible (with combinatorial corrections for multiple-counting), because you can topologically sort your network, oriented to the source- and sink- nodes. For a size-2N network, you can enumerate the two, size-N halves: two directed (1,k) resistor graphs (one source node + k nodes to join on); and zip together the (1,k) + (k,1) sets. (Correcting for the permutations of the k join nodes, and for source/sink symmetry)
Naively, it'd take O(n^2) memory to count all the NxN pairs; but, actually, you can do it in just O(n) space! You sort both half-networks by their resistance values, and then iterate the (implicit) sorted list of their Cartesian sums, in order, counting unique values. You can do that in O(n) space, using an O(n) min-heap and O(n^2 log n) time. The heap only goes up to O(n) because that's the number of possible "next" values at any step. Think of it as the NxN matrix M[i,j] = a[i]+b[j], with the rows and columns sorted (a,b sorted); the size of the "advancing front" from the min-corner to the max-corner is O(n).
4 comments
[ 1.4 ms ] story [ 7.4 ms ] threadhttps://intenex.github.io/personhood/posts/2026-10-12-resist...
(Surely there's a more efficient dynamic-programming solution?)
There's definitely room to discuss how slop-like any of this is - but I do like the wholesome vibes.
https://intenex.github.io/personhood/posts/2026-10-12-resist...
I think you could get a square-root reduction in the memory requirements by splitting the resistor networks in half. That's possible (with combinatorial corrections for multiple-counting), because you can topologically sort your network, oriented to the source- and sink- nodes. For a size-2N network, you can enumerate the two, size-N halves: two directed (1,k) resistor graphs (one source node + k nodes to join on); and zip together the (1,k) + (k,1) sets. (Correcting for the permutations of the k join nodes, and for source/sink symmetry)
Naively, it'd take O(n^2) memory to count all the NxN pairs; but, actually, you can do it in just O(n) space! You sort both half-networks by their resistance values, and then iterate the (implicit) sorted list of their Cartesian sums, in order, counting unique values. You can do that in O(n) space, using an O(n) min-heap and O(n^2 log n) time. The heap only goes up to O(n) because that's the number of possible "next" values at any step. Think of it as the NxN matrix M[i,j] = a[i]+b[j], with the rows and columns sorted (a,b sorted); the size of the "advancing front" from the min-corner to the max-corner is O(n).