Problem proposal - Encoding numbers using dots and parenthesis
Back to General discussions forum
Good evening Rodion!
One I've the things that genuinely surprised me among the various problems on this site are the ones dealing with ways to encode data that I wouldn't have even considered to be "a thing". (Not that I could locate said problems on a whim, but I digress). In this light, this particular Youtube short "Encoding numbers using dots and parentheses" caught my attention because it deals with a "toy" numerical encoding that I think lends itself perfectly for a new Codeabbey problem, and I hadn't seen it anywhere before. In no way would I propose to have the reader guess the logic behind the encoding, cause frankly it's nuts. It's by no means a practical way to represent a number, and it's a first class way to waste space.
It's actually an exercise in factorization, where each factor is implied, but the exponent of the factor and every single one before it is very much explicit. Of course this results in some ridiculous dot infested strings for primes (the bigger the better), and some pretty wild parenthesis nesting for composite numbers, that would probably make Lisp blush.
Plus, because you've mentioned that variation and randomness of input data is necessary, I think that it's not an issue in this case. I think any positive integer would do.
The problem could require encoded strings to be reverted to decimal numbers, or vice versa. It could be a "good enough" use case to introduce a new language, as has happened with some suggestions in the past, or if you're feeling particularly sadist..., eh, "playful", you could give the test data as RLE encoded strings that need to be unpacked first, since I think it is a good fit, due to just three repeating characters.
Tell me what you think!
Konstantine, Hi!
Thanks for sharing this idea! As much as I understand, in its straight form it would be too similar to "Integer Factorization" problem, so probably the "backward" conversion makes more sense. About unpacking RLE it is also curious :)
I too feel somewhat unsatisfied about these "long dot-strings" for large primes and also the fact that exponent uses two characters (left and right parentheses) for single unit. Thus the dot is a kind of "singularity" (simply because we can't conveniently write "zero" parentheses) and chains of right parentheses are somewhat unused except the first in the chain.
Thus it feels more like starting point to invent some modification of the proposed encoding. I can't at once get upon something brilliant, but overall numeral system based upon factorization sounds fruitful theme. So let me ponder on this for a while and hopefully come back with some implementation :)