Advent of Code 2018 day 5 part 1 in rust's type system.

day5.rs

// 100,000 isn't actually required unless you're trying to compile with relatively large inputs
// such as the input from AoC
#![recursion_limit="100000"]
#![allow(dead_code)]
#![allow(non_camel_case_types)]

/// The General Idea
///
/// Associated types in traits can be used to make type level functions. A trait of the form shown
/// below can be viewed as a function that takes one type, `Self` and returns a new type, `O`. To
/// apply this function to some type, we would simply write `<SomeType as Tr>::O`.
/// ```
/// trait Tr {
///     type O;
/// }
/// ```
/// If we want a function that takes more than one type, we can either add them as type parameters
/// to the trait, or make Self a tuple.
/// ```
/// trait Concat<Other> {
///     type O;
/// }
/// ```
///
/// The Algorithm
///
/// This uses the stack based approach to the problem, where for every unit in the polymer, you
/// push it onto the stack, and then check if the top two items of the stack should react or not
/// and remove them if they do.
///
/// What's with Xx and Xs, why not X and Xs?
///
/// The name `X` is taken by one of the structs generated in the zst! macro. In fact, A-Z and a-z
/// are all taken, so I can't really use single letter type parameters.

// Lists that should look familiar if you've done any sort of functional programming ;)
struct Cons<Item, Next>(std::marker::PhantomData<(Item, Next)>);
struct Nil;

// Concatenates two lists, what else can I say?
trait Concat<Other> {
    type O;
}
impl<Other> Concat<Other> for Nil {
    type O = Other;
}
// Translated to Haskell:
//
// concat (x:xs) other = x : (concat xs other)
impl<Xx, Other, Xs: Concat<Other>> Concat<Other> for Cons<Xx, Xs> {
    type O = Cons<Xx, Xs::O>;
}

// Janky method of branching
trait React<Other> {
    // Contains [] if the two units reacted, otherwise it contains [Self, Other]
    // This gets pushed to the stack
    type O;
}

// Length of a list
trait Count {
    const N: usize;
}
impl<Item, Next: Count> Count for Cons<Item, Next> {
    const N: usize = Next::N + 1;
}
impl Count for Nil {
    const N: usize = 0;
}

// This is the trait/function that actually solves the problem.
trait Go {
    type O;
}
// If the input is empty, there's nothing to do.
impl Go for Nil {
    type O = Nil;
}
// If the input is not empty, create the stack
impl<Xx, Xs> Go for Cons<Xx, Xs>
where
    (Cons<Xx, Nil>, Xs): Go,
{
    // Create the stack and start solving
    type O = <(Cons<Xx, Nil>, Xs) as Go>::O;
}
// Translated to haskell (yes argument order is backwards but there's no currying so it doesn't
// matter :P)
//
// go (stack, (x:xs)) = go (push stack x) xs
impl<Stack, Xx, Xs, StackO> Go for (Stack, Cons<Xx, Xs>)
where
    Stack: Push<Xx, O = StackO>,
    (StackO, Xs): Go,
{
    type O = <(StackO, Xs) as Go>::O;
}
// If there's nothing left in the input, return the stack. The length of the stack is really what
// we need.
impl<Stack> Go for (Stack, Nil) {
    type O = Stack;
}

// Push a unit to the stack and attempt to react the top two elements.
trait Push<Item> {
    type O;
}
// If the stack is empty, there's no reacting to do.
impl<Item> Push<Item> for Nil {
    type O = Cons<Item, Nil>;
}
impl<ItemA, ItemB, Xs> Push<ItemA> for Cons<ItemB, Xs>
where
    ItemA: React<ItemB>, // ItemA::O will either be [] or [ItemA, ItemB] depending on the reaction.
    ItemA::O: Concat<Xs>, // The tail is concatenated to the result of the reaction.
{
    type O = <ItemA::O as Concat<Xs>>::O;
}

// macro to make defining the 52 units and reactions between each one more concise
macro_rules! zst {
    () => ();
    // $mat is $this with flipped capitalization, $other is every unit that isn't $mat (including
    // $this) since negative trait bounds don't exist in Rust.

    ($this:tt $mat:tt : $($other:tt)|* ; $($tail:tt)*) => {
        struct $this;
        impl React<$mat> for $this {
            type O = Nil;
        }
        $(impl React<$other> for $this {
            type O = Cons<$this, Cons<$other, Nil>>;
        })*
        zst!($($tail)*);
    }
}

macro_rules! polymer {
    ($x:tt) => (Cons<$x, Nil>);
    ($x:tt $($xs:tt)*) => (Cons<$x, polymer!($($xs)*)>);
}

fn main() {
    type Input = polymer!(a a B c C c b B C d D f);
    println!("{}", <Input as Go>::O::N);
}

// I love vim
zst! {
    a A: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z;
    b B: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z;
    c C: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z;
    d D: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z;
    e E: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z;
    f F: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z;
    g G: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z;
    h H: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z;
    i I: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z;
    j J: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z;
    k K: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z;
    l L: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z;
    m M: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|N|O|P|Q|R|S|T|U|V|W|X|Y|Z;
    n N: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|O|P|Q|R|S|T|U|V|W|X|Y|Z;
    o O: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|P|Q|R|S|T|U|V|W|X|Y|Z;
    p P: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|Q|R|S|T|U|V|W|X|Y|Z;
    q Q: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|R|S|T|U|V|W|X|Y|Z;
    r R: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|S|T|U|V|W|X|Y|Z;
    s S: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|T|U|V|W|X|Y|Z;
    t T: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|U|V|W|X|Y|Z;
    u U: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|V|W|X|Y|Z;
    v V: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|W|X|Y|Z;
    w W: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|X|Y|Z;
    x X: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|Y|Z;
    y Y: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Z;
    z Z: a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y;

    A a: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z;
    B b: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z;
    C c: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z;
    D d: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z;
    E e: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z;
    F f: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z;
    G g: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z;
    H h: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z;
    I i: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z;
    J j: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z;
    K k: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z;
    L l: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|m|n|o|p|q|r|s|t|u|v|w|x|y|z;
    M m: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|n|o|p|q|r|s|t|u|v|w|x|y|z;
    N n: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|o|p|q|r|s|t|u|v|w|x|y|z;
    O o: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|p|q|r|s|t|u|v|w|x|y|z;
    P p: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|q|r|s|t|u|v|w|x|y|z;
    Q q: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|r|s|t|u|v|w|x|y|z;
    R r: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|s|t|u|v|w|x|y|z;
    S s: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|t|u|v|w|x|y|z;
    T t: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|u|v|w|x|y|z;
    U u: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|v|w|x|y|z;
    V v: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|w|x|y|z;
    W w: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|x|y|z;
    X x: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|y|z;
    Y y: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|z;
    Z z: A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y;
}