Haskell part 2, much better solution

Okay, here's the outline again - this one ran instantly.

Rather than probing with example values, I took a different approach, debugging the structure. I only really care about inputs and outputs, so I wrote something that turns the "wiring diagram" into a map of label -> Expr, where

data Expr = EInput String
          | EAnd Expr Expr
          | EOr Expr Expr
          | EXor Expr Expr
  deriving (Show, Ord)

(the Eq instance is stable in symmatric expressions, eg (==) (EAnd a b) (Eand c d) = a == c && b == d || a == d && b == c)

The expressions are grounded in "inputs" ("x00".."x44", "y00".."y44") - that is, they just expand out all of the intermediary labelled things.

Then I constructed a circuit that I was after by building a non-swapped 44/45-bit full adder, and produced the same set of expressions for those.

Then: for each output, z00..z45, check the "spec" expression against the actual one. If they're identical, move on.

Otherwise, find some candidate pairs to swap. For these, I considered all possible labelled outputs except "stable" ones - that is, those that were input depdendencies of z_(i-1) - ie, don't swap any outputs involved in the computation that's validated thus far.

searchForSwap :: Exprs -> Layout -> String -> Set.Set String -> [(String, String, Layout, Exprs)]
searchForSwap eSpec actual zz stable =
  let
    vals = Map.keysSet actual & (`Set.difference` stable) & Set.toList
    ds = dependencies actual
  in do
    k1 <- vals
    k2 <- vals
    guard $ k1 < k2
    guard $ k1 `Set.notMember` (ds Map.! k2)    -- don't create any loops
    guard $ k2 `Set.notMember` (ds Map.! k1)
    let actual' = swapPair k1 k2 actual
        eAct' = exprsForLayout actual'
    guard $ eSpec Map.! zz == eAct' Map.! zz
    pure (k1, k2, actual', eAct')

Taking the new layout with swapped outputs and its corresponding set of expressions, carry on searching as before.

A linear scan over the output bits was all that was required - a unique answer poped out without any backtracking.

Anyway, happy Christmas all.

PS. My other version worked (eventually) - it was following this approach that led me to realise that my "spec" full adder was broken too :-D Never skip the unit tests.

(@[email protected] you were asking about alternatives to graphviz-style approaches I recall)