There's a link at the very bottom to a fully annotated, commented copy of the full source code, and a fairly good summary of what was going on in the footnote.

Seriously. This is the first entry in the x-ing the interview series where I understood literally 0% of the code

Prolog is... different, it's going to take some getting used to. The Art of Prolog is a great resource, reading the first few chapters should get you far enough that you can then roughly understand what the code is doing and Google (or skim forward though the rest of the book) to look up the unfamiliar syntax for things like arithmetic. You should probably ignore the cut (the ! Aisha adds) for a while and come back to it once you've written some Prolog and gotten a feel for how it works. cuts are simple, but only once you've wrapped your head around Prolog's execution strategy. A good way to know that you get it is that you no longer accidentally write infinite loops.

Of course, once you understand logic programming you still have most of this essay left to go through. Even if you've used lisp you've probably never had to implement one! And of course, after you've gotten through all that, now you need to read code written in this strange lisp. A microKanren. almost Prolog, but different in some key ways; it uses a different execution strategy which prevents those infinite loops. The Reasoned Schemer is the second half of this essay but expanded out to book form, it would make a great explanation if you're down for a nice read and you have a free Saturday.

Once you've gotten through all that the syntax has become completely unrecognizable but the final solution is fun, and makes all the ceremony worth it:

  balanceo, [lambda, [tree, balanced],
    [conde, [[rotso, tree, balanced],
             [balancedo, balanced]]]]

`balanceo` is a relation which is only satisfied if `tree` is a tree and `balanced` is the balanced form. If you pass in `tree` it returns the correct `balanced`. I'm not sure, but it looks like it probably also works if you only pass in `balanced`, in which case it will return the unbalanced `trees` which correspond to that balanced tree. You might even be able to pass in nothing, in which case it will return a bunch of pairs of unbalanced trees and their balanced forms.

The definition of `balanceo`, essentially, says that "[balanceo tree balanced] is only true if balanced can be formed by performing rotations on tree, and balanced is balanced." MicroKanren figures out the rest. That's declarative programming! Pretty great! Though, it only works for small trees, which does tarnish the magic a little.

If you’ve never implemented a Lisp, here’s a relevant thing to give a read: https://sep.yimg.com/ty/cdn/paulgraham/jmc.ps

I don't know if I should feel embarrassed or not too - I'm a lead C++ programmer and I don't understand any of the code or what they are trying to do. It's like learning a language, only to discover people speaking such a dialect of it that you don't understand a word.

I don't see any reason why you should be embarrassed - if you haven't seen Prolog (or anything similar) it is very different to more conventional languages. It's arguable that Prolog is closer to SQL than C++.

the two (Prolog and SQL) even have something of a middle ground - Datalog (https://en.wikipedia.org/wiki/Datalog)