# Objective Given a string consisting of printable ASCII characters (`!`0x21 ― `~`0x7E), treat it as an element in the **free idempotent monoid** (as defined below) over the printable ASCII characters, and output the same element represented in the fewest characters as possible. # Free idempotent monoid Recall that the **free monoid** over a set is essentially the collection of lists over the set, endowed with concatenation. The **free idempotent monoid** is the quotient object of the free monoid that identifies the lists up to idempotency. In laymen's terms, if the list has two or more contiguous sub-lists that compare equal, the sub-lists can be replaced by one sub-list, while retaining overall equivalence of the list. # Proof of uniqueness We want to show that, for two strings \$x\$ and \$y\$ that belong to the same equivalence class, if \$x\$ and \$y\$ both have the fewest characters in the class, \$x\$ and \$y\$ actually are the same string. It's obvious that \$x\$ and \$y\$ consist of the same set of characters. If \$x\$ and \$y\$ both have length zero, we are done. Otherwise, let \$\alpha\$ be the first character in \$x\$, and let \$\beta\$ be the first character in \$y\$. Since every member of the class \$x\$ belongs has \$\alpha\$ as the first character, and likewise for \$y\$ and \$\beta\$, it follows that \$\alpha = \beta\$. If \$x\$ and \$y\$ both have length one, we are done. Otherwise, let \$\alpha'\$ be the second character in \$x\$, and let \$\beta'\$ be the second character in \$y\$. It's obvious that \$\alpha' \neq \alpha\$ and \$\beta' \neq \beta\$. Now, every member of the the class \$x\$ belongs has \$\alpha'\$ as the first character when the longest prefix consisting of \$\alpha\$ is stripped off, and likewise for \$y\$ and \$\beta'\$, it follows that \$\alpha' = \beta'\$. If \$x\$ and \$y\$ both have length two, we are done. Otherwise, let \$\alpha''\$ be the third character in \$x\$, and let \$\beta''\$ be the third character in \$y\$. It's obvious that the strings \$\alpha\alpha'\alpha''\$ and \$\beta\beta'\beta''\$ are irreducible. Now, every member of the the class \$x\$ belongs has \$\alpha''\$ as the first character when the longest prefix being equivalent to the string \$\alpha\alpha'\$ is stripped off, and likewise for \$y\$ and \$\beta''\$, it follows that \$\alpha'' = \beta''\$. The proof is recursive until exhausting all characters in \$x\$ and \$y\$. # Examples Here, the strings are double-quoted. ``` Input -> Output "" -> "" "x" -> "x" "xx" -> "x" "xy" -> "xy" "!!?" -> "!?" "+/+/" -> "+/" "1+1+1" -> "1+1" "1+2+1" -> "1+2+1" "~~~" -> "~" "TheThem" -> "Them" "thethem" -> "them" "cOUgh" -> "cOUgh" "XIXAXA" -> "XIXA" "IXIXAXA" -> "IXA" "Xx" -> "Xx" "198034034" -> "198034" "...!...!" -> ".!" "...!...?" -> ".!.?" "Ook!Ook?" -> "Ook!Ook?" "<o><oo>" -> "<o>" ```