Arrival Pt. 2 [solution]
Solution for the week of 5/25
Two weeks back we were introduced to a new alien language…
Each Signal is composed of a combination of pulses and phrases and is structured as follows:
The most basic element is a "Pulse." It's a complete, indivisible unit, which we'll represent with a dot.
More complex structures, called "Phrases," are formed by a specific modulator followed by a sequence of other complete signals (each of which can be a pulse or another phrase).
An Alpha-Modulator (symbol A): This modulator always precedes exactly two subsequent Signals. We can visualize this as
A(Signal₁, Signal₂)or as a tree:A Beta-Modulator (symbol B): This modulator always precedes exactly three subsequent signals. Visualized as
B(Signal₁, Signal₂, Signal₃)[…]
How many distinct signal structures have exactly two modulators in total? These two modulators can be any combination of Alpha or Beta types (e.g., two Alphas, or one Alpha and one Beta, or two Betas).
Big thanks to Peter Ji, Izumihara Ryoma, and Lise Andreasen for their solutions and for bearing with this experimental puzzle.
Everyone got the first part correct which isn’t terribly surprising. The answer—10— was sufficiently small that solvers could easily enumerate all possibilities. A more careful puzzle writer (whoever that might be) would have started with this question and then asked a follow up with a much larger number of modulators to hopefully force the solver into finding a more general formulation and draw out the relationship with the hyper-Catalan numbers presented in the previous week’s puzzle.1 For example, what if I had asked for the number of combinations of 10 modulators? One can certainly use a generating function approach to this question but my intention was to highlight that we could use the hyper-Catalan formulation from last week here.
This was meant to prime us for the next section
The xenolinguists are now trying to estimate the total computational decoding cost for the entire Lullaby language. This is a theoretical measure representing the sum of efforts required to decode every conceivable signal structure. Here's how the cost is modeled:
A basic Pulse
•is trivial to decode, having a computational cost of 1 unit.Decoding an Alpha-Modulator itself involves a certain overhead, represented by a cost factor A. The overall computational cost to decode a Phrase
A(S₁, S₂)is a multiplicative function of this overhead and the costs of its sub-signals: A×(cost of S1)×(cost of S2).Similarly, a Beta-Modulator has a cost factor B, and a Phrase
B(S₁, S₂, S₃)has an overall decoding cost of B×(cost of S1)×(cost of S2)×(cost of S3).Recall we want to compute the sum S of the individual decoding costs of all possible distinct signal structures. You’re about to start approximating S by enumerate all possibilities but the lead—on his way out for the evening—researcher tells you there’s a much easier way to compute S. You yell back in confusion, “How?” but he’s already gone. What was he talking about? In other words, can you find a simpler way to express and compute S(A,B)?
The trick to finding the “simpler” formulation for S(A,B) it to recognize its recursive structure. Every signal is of arbitrary complexity but it must either be a single pulse or start with either an Alpha or Beta-modulator. The signals that follow are also signals of arbitrary complexity so we can speak about them in exactly the same as we are for the signal as a whole. Algebraically we can write it as
Recall (1) that a pulse has computational cost of 1 unit (thus the 1+ in the equation), (2) that an Alpha-modulator contributes multiplicatively a value A as well as 2 ‘sub-signals’ (thus the A*S^2) term, and (3) that the Beta-modulator contributes multiplicatively a value B as well as 3 ‘sub-signals’ (thus the B*S^3) term. So to find the overall computational complexing, we just need to solve for S in this cubic equation. I’m not going to write out the expression for S since the exact form is rather messy. Plus, the exact expression for S wasn’t really the point of the puzzle. Rather, the point was to draw the connection between polynomials and the hyper-Catalan numbers. If you would like the full expression for S and some of the details that expression, I’ll point you to Izumihara’s lovely solution write-up.
Taking a step back, this puzzle was meant to draw out the key observation of the A Hyper-Catalan Series Solution to Polynomial Equations, and the Geode paper. In the paper, the authors use the idea of combining together polygons into subdigons in a “panelling” process to help draw out the link between polynomials and hyper-Catalan numbers. Like our alien language, the subidgon has a similar recursive structure making it amenable to a polynomial description while the hyper-Catalan number are able to count the number of different possible subdigons.
It should be noted that there is a bit of an oopsie with this puzzle from a logic/common-sense perspective. Izumihara rightfully points out that this formulation only really works when A<1 and B<1—otherwise S is unbounded (he has a more precise expression for when S is bounded in his write-up). But if A and B are less than zero, than the computational complexity of a signal would get smaller as the signal gets larger, which doesn’t really make sense. A more careful puzzle writer would have come up with a more appropriate puzzle scenario than ‘computational complexity’ to motivate constructing the problem as a polynomial 🥴.
Anyway, thanks to those readers for venturing along on this experimental set of puzzles. Let me know what you thought of them. Did you like the idea of attempting to mirror a real paper? Do you prefer the more standard puzzles? Your feedback is invaluable! As always, thanks for reading!
Admittedly, a more careful puzzle writer would also have had that week’s solution available to solvers while they were working on this puzzle so that my Hint would have been more meaningful.