# [Hexagony](https://github.com/mbuettner/hexagony), <s>218</s> <s>92</s> 58 bytes

    )}?}.=(..]}}={.=.&~./=}..=.=&{.<......*|>(<..=%....}!\[.&@

The first ever non-trivial (i.e. non-linear) Hexagony program! It is based on the same squared-factorial approach as [Sp3000's Labyrinth answer](http://codegolf.stackexchange.com/a/57672/8478). After starting out with a hexagon of size 10, I managed to compress it down to size 5. However, I was able to reuse some duplicate code and there are still quite a bunch of no-ops in the code, so size 4 might *just* be possible.

## Explanation

To make sense of the code, we first need to unfold it. Hexagony pads any source code to the next centred hexagonal number with no-ops (`.`), which is `61`. It then rearranges the code into a regular hexagon of the corresponding size:

         ) } ? } .
        = ( . . ] }
       } = { . = . &
      ~ . / = } . . =
     . = & { . < . . .
      . . . * | > ( <
       . . = % . . .
        . } ! \ [ .
         & @ . . .

This is quite heavily golfed with crossing and overlapping execution paths and multiple instruction pointers (IPs). To explain how it works, let's first look at an ungolfed version where control flow doesn't got through the edges, only one IP is used and the execution paths are as simple as possible:

                 . . . . . . . . . . . . .
                . . . . . . . . . . @ . . .
               . . . . . . . . . . ! . . . .
              . . . . . . . . . . % . . . . .
             . . . . . . . . . . = . . . . . .
            . . . . . . . . . . { . . . . . . .
           . . . . . . . . . . = . . . . . . . .
          . . . . . . . . . . & . . . . . . . . .
         . . . . . . . . . . { . . . . . . . . . .
        . . . . . . . . . . * . . . . . . . . . . .
       . . . . . . . . . . = . . . . . . . . . . . .
      . . . . . . . . . . } . . . . . . . . . . . . .
     ) } ? } = & { < . . & . . . . . . . . . . . . . .
      . . . . . . . > ( < . . . . . . . . . . . . . .
       . . . . . . = . . } . . . . . . . . . . . . .
        . . . . . } . . . = . . . . . . . . . . . .
         . . . . | . . . . | . . . . . . . . . . .
          . . . . * . . . ) . . . . . . . . . . .
           . . . . = . . & . . . . . . . . . . .
            . . . . > } < . . . . . . . . . . .
             . . . . . . . . . . . . . . . . .
              . . . . . . . . . . . . . . . .
               . . . . . . . . . . . . . . .
                . . . . . . . . . . . . . .
                 . . . . . . . . . . . . .

<sup>Side note: the above code starts with executing the first line, which is full of no-ops. Then, when the IP hits the north east edge, it wraps to the left-most corner (the `1`), where the actual code begins.</sup>

Before we start, a word about Hexagony's memory layout. It's a bit like Brainfuck's tape on steroids. In fact, it's not a tape, but it's a hexagonal grid itself (an infinite one), where each *edge* has an integer value, which is initially 0 (and as opposed to standard Brainfuck, the values are signed arbitrary-precision integers). For this program, we'll be using four edges:

[![enter image description here][1]][1]

We'll compute the factorial on edge **A**, count down our input on edge **C** and store another copy of the input (for the modulo) on edge **D**. **B** is used as a temporary edge for computations.

The memory pointer (MP) starts out on edge **A** and points north (this is important for moving the MP around). Now here is the first bit of the code:

    )}?}=&{

`)` increments edge **A** to `1` as the basis of the factorial. `}` makes the MP take a right-turn, i.e. move to edge **C** (pointing north-east). Here we read the input as an integer with `?`. Then we take another right-turn to edge **D** with `}`. `=` reverses the MP, such that it points at the vertex shared with **C**. `&` copies the value from **C** (the input) into **D** - the value is copied from the left because the current value is non-positive (zero). Finally, we make the MP take a left-turn back to **C** with `{`.

Next, `<` is technically a branch, but we know that the current value is positive, so the IP will always turn right towards the `>`. A branch hit from the side acts as a mirror, such that the IP moves horizontally again, towards the `(`, which decrements the value in **C**.

The next branch, `<` is *actually* a branch now. This is how we loop from `n-1` down to `1`. While the current value in **C** is positive, the IP takes a right-turn (to execute the loop). Once we hit zero, it will turn left instead.

Let's look at the loop "body". The `|` are simple mirrors, the `>` and `<` are also used as mirrors again. That means the actual loop body boils down to

    }=)&}=*}=

`}` moves the MP to edge **B**, `=` reverses its direction to face the vertex **ABC**. `)` increments the value: this is only relevant for the first iteration, where the value of **B** is still zero: we want to ensure that it's positive, such that the next instruction `&` copies the *right* neighbour, i.e. **A**, i.e. the current value of the factorial computation, into **B**.

`}` then moves the MP to **A**, `=` reverses it again to face the common vertex. `*` multiplies both neighbours, i.e. edges **B** and **C** and stores the result in **A**. Finally, we have another `}=` to return to **C**, still facing the vertex **ABC**.

I hope you can see how this computes the factorial of `n-1` in **A**.

So now we've done that, the loop counter in **C** is zero. We want to square the factorial and then take the modulo with the input. That's what this code does:

    &}=*{&={=%!@

Since **C** is zero, `&` copies the left neighbour, i.e. the factorial in **A**. `}=*` moves to **B** and stores the product of the two copies of the factorial (i.e. the square) in **B**. `{` moves back to **C**, but doesn't reverse the MP. We know that the current value is now positive, so `&` copies input from **D** into **C**. `={=` reverses the MP, moves to **A** and reverses the MP again. Remember, the square of the factorial is in **B** and the input is in **C**. So `%` computes `(n-1)!^2 % n`, exactly what we're looking for. `!` prints the result as an integer (0 or 1) and `@` terminates the program.

  [1]: http://i.stack.imgur.com/bh4T0.png