He is using the classic AI method of heuristic-guided graph search with search-space pruning. That still doesn't make the worst case tractable, but it does improve a lot on brute force enumeration.

Would there be AI methods that would produce deterministic results for code formatting? Deterministic output seems to be the main draw of a code formatter.

The code formatter described in the article is not deterministic either. The author admits the search space is far too large for him to brute-force it, so his formatter does the best it can, which might not get the optimal results:

"If the line splitter tries, like, 5,000 solutions and still hasn't found a winner yet, it just picks the best it found so far and bails."

This sounds like it would give no more guarantees of a deterministic result than AI methods would. They also try their best, only search a subset of the search space, and bail when user-defined criteria such as time, iteration, or space limits are reached.

Another approach could be to use both the author's hand-crafted algorithm and an AI method. There are at least two ways to go about that. The first would be to run the hand-crafted algorithm and pass its evaluation of the best solutions to seed an AI method (for example, as the seed populations in an evolutionary algorithm). The second would be to do the opposite, and run the AI method first, and seed the hand-crafted algorithm with the best solutions the AI method discovered.

I doesn't look like that stopping time is user-defined, it's a compiled in constant.

Given that, I don't see any reason why the algorithm should be non-deterministic just because it gives up after a set number of iterations. As long every time it sees a given string it tries the possibilities in the same order, scores them the same way, and stops at the same place then it should be deterministic.

By "user-defined", I meant to refer to the user of the algorithm (AI or not), who is the developer.

You're right that if the algorithm described in the article will always get the same result given the same input it will be deterministic in a way that the kinds of AI methods I'm thinking of (the stochastic kind) will not. That sort of non-determinism will be a problem if you expect your code to be formatted the same way every time it goes through the formatter.

...But if, for the same input, it always tries the same candidates in the same order, then it is deterministic.

The chosen quote doesn't indicate whether or not it's deterministic.

There are lots of "AI methods" that can be used to produce deterministic results. In general, this sounds like a problem where combinatorial optimization techniques can be useful. For example, constraint programming, mixed integer programming, and various local search methods. For all techniques, there are both deterministic and non-deterministic approaches.

Set the random seed?

I was thinking along similar lines, like some kind of reinforcement learning model that penalized lines that seem ugly to humans... but probably hard to get enough humans looking at enough code.

I wonder if well-respected real-world code samples could be used as a training and testing set.

For example, one could use a subset of the Linux kernel source code as training, and another (unseen) subset as testing.

Highly rated projects on github might work too.

An active learning approach would be cool, where the formatter process a large corpus of code and asks a human operator for advice when it is especially uncertain about the best place to split.

Even if training the splitting policy from scratch is too hard, learning would be a good way to establish cost weights on different kinds of rule violations.