{- |
Description: Universal logic gates
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Part of Ninety-Nine Haskell "Problems".  Some solutions are in "Solutions.P47".
-}
module Problems.P47 where

import qualified Solutions.P47 as Solution

{- |
Consider a logic circuit composed of NAND gates with binary input, specified as follows.

* A list of pairs of numbers for each NAND gate.

* A pair @(i,j)@ in the list denotes that the inputs for the NAND gate
  are the outputs for the @i@th and @j@th gates in the list, respectively,
  with the first element starting at index 1.

    * As a special case, -1 and -2 denote the first and second boolean variables
      fed into the circuit, respectively.

    * An input to a NAND gate can only use output from a NAND gate which appears earlier in the list.

* The output of the last gate in the list is the output of the logic circuit.

Write a function to evaluate a given logic circuit as specified above.

=== Examples

>>> evaluateCircuit [(-1,-2)] True True
False

>>> evaluateCircuit [(-1,-2)] True False
True

>>> evaluateCircuit [(-1,-2), (1,1)] True True
True

>>> evaluateCircuit [(-1,-2), (1,1)] True False
False

>>> evaluateCircuit [(-1,-1),(-2,-2),(1,2)] True False
True

>>> evaluateCircuit [(-1,-1),(-2,-2),(1,2)] False False
False
-}
evaluateCircuit :: [(Int,Int)] -> Bool -> Bool -> Bool
evaluateCircuit :: [(Int, Int)] -> Bool -> Bool -> Bool
evaluateCircuit = [(Int, Int)] -> Bool -> Bool -> Bool
Solution.evaluateCircuit

{- |
Any boolean function can be computed with logic circuits composed solely of NAND gates.
I.e., NAND is a universal logic gate.

Write a function to return a logic circuit composed of NAND gates
which computes a given a binary boolean function.
The logic circuit should be in a form which 'evaluateCircuit' can evaluate.

=== Examples

>>> evaluateCircuit (buildCircuit (&&)) False False
False

>>> evaluateCircuit (buildCircuit (&&)) False True
False

>>> evaluateCircuit (buildCircuit (&&)) True False
False

>>> evaluateCircuit (buildCircuit (&&)) True True
True

=== __Hint__

There are only 16 binary boolean functions, ignoring how they are actually computed,
so it is feasible to devise logic circuits for all of them manually.

To have a computer construct them automatically, which may be more difficult,
take advantage of the fact that a boolean function can be represented by its truth table.
Consider what the inputs must be like for a NAND gate to output a desired truth table.
-}
buildCircuit :: (Bool -> Bool -> Bool) -> [(Int,Int)]
buildCircuit :: (Bool -> Bool -> Bool) -> [(Int, Int)]
buildCircuit = (Bool -> Bool -> Bool) -> [(Int, Int)]
Solution.buildCircuit