Post History

Idetifying returning paths.

Let's imagine a point in three dimensional space. We will start it located at \$(0,0,0)\$. Then we will receive a series of instructions. `x`, `y`, and `z` indicate moving unit distance in the positive \$x\$, \$y\$, and \$z\$ directions respectively. The capital letters `X`, `Y`, and `Z` indicate moving the same distance in the opposite directions. This way we perform a walk on the cubic lattice.

I want to know if a given path returns to the origin, *and* for each edge in the lattice the number of times the walk crosses it in the positive direction and the negative direction are the same. In other words, every step that you take is done in reverse at a future point.

We give some examples at the end.

Your task is to write a computer program which takes a string containing only `xyzXYZ` and outputs one of two distinct values. The first value if the input satisfies the condition the second if it fails the condition.

This is code-golf, so the goal is to minimize the size of your source code as measured in bytes.

# Math

This puzzle doesn't come out of nowhere, it actually emerges out of some group theory. This isn't at all necessary to solve the problem, but I think it's interesting.

We first observe that the set of valid paths *almost* forms a group. If we concatenate two valid paths we always get a valid path, but we lack inverses. This can be fixed by allowing cancellation. We say that e.g. `xX` and <code></code>&nbsp;are the same. That is immediately undoing and edge is the same as having never crossed it in the first place. With this equivalence notion we see that every valid path has an inverse, simply trace the path backwards.

This might be recognizable as homotopy equivalence. Two valid paths are equivalent if you can continuously deform one into the other and vice versa.

It is possible to jump the gun here and say that this is the fundamental group of the cubic lattice. Afterall these are loops in the cubic lattice considered up to homotopy. However, not everything in the fundamental group is equivalent to a valid path. For example `xyXY` is a loop, but it's not a valid path. So this is a *subgroup* of the fundamental group.

I think figuring out a description for the subgroup on your own is a fun exercise, so I will put the rest of this in spoilers. Once you've figured this out.

<details><summary>Spoilers</summary>
This subgroup is precisely the commutator subgroup of the fundamental group!

This is especially interesting if you are already aware that the fundamental group of the cubic lattice is the commutator subgroup of the free group on three generators, \$F_3\$. Thus this question can really be stated as:

> Identify if an element of \$F_3\$ is in the second derived subgroup \$[[F_3,F_3],[F_3,F_3]]\$.

Of course this is a normal subgroup, so identifying its elements is the same as solving the word problem for \$F_3\setminus G\$. This group is the free metabelian group on three generators, \$M_3\$. Thus this question can really be stated as:

> Identify if a word is equal to the identity in \$M_3\$. 

These aren't just cool, but they offer a small insight. For this we use a theorem of Fox:

> ### Theorem (Fox)
> Let \$N\lhd F_r\$ with the natural map \$\mu : F_r\rightarrow F_r\setminus N\$.
> A word \$w\in F_r\$ is in \$[N,N]\$ if and only if the Fox derivative of \$w\$ with respects to every generator of \$F_r\$, is zero under \$\mu\$. That is:
> \begin{equation}
\forall i \left(\dfrac{\partial w}{\partial x_i}\right)^\mu = 0
\end{equation}

Since in our case \$N\$ is the commutator subgroup of the initial group itself. Thus our puzzle is equivalent to the following:

> Check if all the second Fox derivatives of a word are trivial. i.e.
> \begin{equation}
\forall i,j \dfrac{\partial^2}{\partial x_i\partial x_j} w = 0
\end{equation}

</details>

# Examples

* `xyXY` <details>this path returns to the origin tracing out a square in the anticlockwise direction. However it crosses 4 edges of the lattice and each exactly once. While it makes the same number of steps in the positive direction as in the negative direction (this is required to return to the origin), those steps are across different edges. Thus this fails.
![xyXY](https://codegolf.codidact.com/uploads/tmo47zsky69g23lta7gvywzig70k)</details>
* `xyXYzxyXYZyxYXzyxYXZ` <details>this path is more complicated. We can break it down as follows:
  1. `xyXY`: it traces an anticlockwise square returning to the origin. The same as above.
  2. `z`: it takes a step in the positive \$z\$ direction.
  3. `xyXY`: it traces the same square as before but at this new location.<br>![xyXYzxyXY](https://codegolf.codidact.com/uploads/j20yzqjs1qlrewambyhjfnkn0va8)
  4. `Z`: it returns to the origin.<br>![Z](https://codegolf.codidact.com/uploads/xethv2r7jmxvih94p9v1qc0skh9j)
  5. `yxYX`: it traces a *clockwise* square. This is the reverse of the square it traced in step 1.
  6. `z`: it takes a step in the positive \$z\$ direction.
  5. `yxYX`: it reverses the square taken in step 3.<br>![yxYXzyxYX](https://codegolf.codidact.com/uploads/56647nxckbcfbuhzvj4cxvfurfqs)
  6. `Z`: it returns to the origin.<br>![Z](https://codegolf.codidact.com/uploads/xethv2r7jmxvih94p9v1qc0skh9j)

  This passes.</details>

# Test cases

```
xxYZ -> False
xyXY -> False
yXYxYXyyxYXYxy -> True
YXyxxYXyXYxxyX -> True
xyXXYxyxYXXyxY -> True
yXYxzXZyxYXzxZ -> True
XyxYxYXyyXYxYxyX -> True
xyXYzxyXYZyxYXzyxYXZ -> True
xyXzxYXZxzyZXYzxyXZxYXyxzYZXYzyZxxzXXYZyzxxZXX -> True
```