Arithmetic Golfing
2017-09-09, post № 179
code golf, mathematics, programming, Python, #byte count, #code golfing, #golfing, #short code
A recent PCG golfing question When do I get my sandwich? asked to find a mapping between seven input strings (sandwich names) and the seven days of the week (indexed by number).
The first answer was made by a user named i cri everytim and utilized a string of characters which uniquely appear at the same position in all seven input strings, enklact, to perform the mapping in Python 2 requiring 𝟤𝟫 bytes. After their answer, a lot of answers appeared using the same magic string in different languages to reduce the number of bytes needed. Yet nobody reduced the byte count in Python.
Trying to solve the problem on my own, my first attempt was using only the input strings’ last decimal digit to perform the mapping, though this approach did not save on bytes (read my PCG answer for more on this 𝟥𝟢 byte solution).
After a few more hours of working on this problem, however, I achieved to bring down the byte count by one entire byte.
I did so by using a simple brute-force algorithm to check for Python expressions which can be used to perform the sought after mapping. To do so, I use Python’s apostrophes (`...`) to turn the found expression into a string — str(...) is three whole bytes longer — and index that string with the input strings’ lengths. It sure is not very readable, but only takes 𝟤𝟪 bytes — and that is all that matters.
lambda S:`6793**164`[len(S)]
After finding the 𝟤𝟪 byte function which uses a 𝟫 byte expression (6793**164), I attempted to find an even shorter expression. And even though I did not yet find one, I did write a more general brute-force Python program (source code shown below; can also be downloaded) than the one I linked to in my PCG answer.
Brute-forcing takes exponentially more time the more digits you have to check, so my brute-forcer still requires the user to decide for themselves which expressions should be tried.
There are three parameters that define the search; a regex pattern that should be contained in the expression’s string, an offset that pattern should ideally have and a target length. If an expression is found that takes as many bytes as or less bytes than the target length, an exclamation point is printed
Though this program did not prove useful in this case, there may come another challenge where an arithmetic expression golfer could come in handy.
My program may not have found shorter expressions, but definitely some impressive ones (the +... at the end refers to an additional offset from the string index which — unsurprisingly — take additional bytes):
2**2**24+8004152**2**27+52265282**7**9+117197507954<<85
I also considered using division to generate long strings of digits which may match; the only problem is that Python floating-point numbers only have a certain precision which does not produce long enough strings. Again, using exponentiation (**) and bitshifting (<<) I could not come up with a working expression that takes less bytes.