406337: GYM102365 G Infinity Plus One

As children, David and Henry used to play "who can name the biggest number?"

Henry: "Twenty!"

David: "Nine thousand!"

Henry: "A million trillion!"

David: "A googolplex squared!"

Henry: "Infinity!"

Determined to win, David takes the game to the next level: "Infinity plus one!"

Lucca, passing by, objects: "How can you count to infinity, let alone past it?"

To give his winning move a mathematical basis, David invokes an ordered set $$$\mathcal S$$$. Only two properties of $$$\mathcal S$$$ are relevant:

• $$$\mathcal S$$$ is well-ordered: every non-empty subset of $$$\mathcal S$$$ has a unique smallest element.
• $$$\mathcal S$$$ is uncountably big: even if we take and name infinitely many elements from $$$\mathcal S$$$, there will always be more.

By taking one smallest element at a time, David identifies numbers with elements of $$$\mathcal S$$$:

• $$$0 = \min(\mathcal S)$$$, the unique smallest element of $$$\mathcal S$$$,
• $$$1 = \min(\mathcal S \setminus \{0\})$$$, the smallest element in the subset that remains when $$$0$$$ is removed from $$$\mathcal S$$$,
• $$$2 = \min(\mathcal S \setminus \{0, 1\})$$$, and so on...

By naming elements in this way, David can get all the natural numbers $$$\mathbb N = \{0, 1, 2, \ldots\} \subsetneq \mathcal S$$$.

In order to go beyond, he defines $$$\infty = \min(\mathcal S \setminus \mathbb N)$$$. To get a "number" that's even bigger than $$$\infty$$$, he chooses $$$\min(\mathcal S \setminus (\mathbb N\cup\{\infty\}))$$$.

To make this idea general, David represents a "number" by a counting program P, which takes as input a (countable, possibly infinite) subset $$$T\subsetneq\mathcal S$$$. Its output, denoted by P($$$T$$$), satisfies $$$T\subseteq\text{P}(T)\subsetneq\mathcal S$$$. Counting programs belong to a context-free language:

• The empty program does nothing to $$$T$$$, returning it as-is.
• + takes the smallest unused element of $$$\mathcal S$$$ and puts it in $$$T$$$. Formally, $$$+(T) = T\cup \{\min(\mathcal S \setminus T)\}$$$.
• PQ runs the program P, followed by the program Q. Formally, $$$(\text{PQ})(T) = Q(\text{P}(T))$$$.
• [P] runs the program P in an "infinite loop". Formally, $$$[\text{P}](T) = \text{P}(T)\cup (\text{PP})(T)\cup (\text{PPP})(T)\cup\ldots$$$

Let $$$T_1 = \text{P}_1(\emptyset)$$$ and $$$T_2 = \text{P}_2(\emptyset)$$$ be the subsets constructed by the counting programs $$$\text{P}_1$$$ and $$$\text{P}_2$$$, respectively. The following conditions are equivalent, and when they hold we'll say that $$$\text{P}_1 < \text{P}_2$$$:

• $$$\min(\mathcal S \setminus T_1) < \min(\mathcal S \setminus T_2)$$$
• $$$T_1 \subsetneq T_2$$$

Thanks to his general definition, David can be mathematically precise about what he means by "infinity plus one": he means the program [+]+, which constructs the subset ([+]+)$$$(\emptyset) = \mathbb N\cup\{\infty\}$$$.

To decide who won their game, the children need you to compare numbers that are described by counting programs. Given a list of $$$M$$$ counting programs, sort them from smallest to biggest.

The first line contains an integer $$$M$$$ $$$(M \le 100)$$$.

Line $$$i+1$$$ contains a string $$$\text{P}_i$$$ $$$(1 \le |\text{P}_i| \le 100)$$$. $$$\text{P}_i$$$ is guaranteed to be a counting program in the described language: all characters are +, [, or ], and every [ is matched with a corresponding ].

Print the list of counting programs in sorted order, from smallest to biggest. Counting programs that are equal may be printed in any order.

8
+
[+]+
[+][+]
+++++++
+++[+++]
+[+[+]+]+
[+][[+]][+]
[][[][]][]

[][[][]][]
+
+++++++
+++[+++]
[+]+
[+][+]
+[+[+]+]+
[+][[+]][+]

The symbols $$$\subseteq$$$, $$$\subsetneq$$$, $$$\cup$$$, $$$\setminus$$$, $$$\emptyset$$$ mean "is equal to or contained in", "is strictly contained in", set union, set difference, and the empty set, respectively.

The sample numbers are all distinct; study them carefully using the definitions. Intuitively, you might think of the smallest entries as zero, one, seven, infinity, infinity plus one, and infinity times two, respectively. But don't let names fool you: the usual rules of arithmetic no longer apply!