Arithmetic Golfing

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 29 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 30 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 28 bytes — and that is all that matters.

lambda S:`6793**164`[len(S)]

After finding the 28 byte function which uses a 9 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+800415
  • 2**2**27+5226528
  • 2**7**9+11719750
  • 7954<<850

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.

# Python 2.7 code; 7th, 8th of September 2017

# import
import re

# =======
# =======

# Best expression found: 6793**164

# expression types
expressions = [
	# finds `-9114**28`
	# finds `6793**164`
	# No smaller results
	# No smaller results
	# No smaller results
	# Takes a long time
	# No smaller results
	# No smaller results
	# No smaller results

# pattern to be matched
pattern = "4......3.2..56..1.......0"

# pattern offset (where in the number the first pattern character should be)
offset = 4

# maximum expression length
targetlength = 8

# possible characters for variables
vars = "abcdefghijklmnopqrstuvwxyz"

# brute force!
def bruteforce(expression):
	# find repeating variables
	expr = [expression[0]]
	for c in expression[1:]:
		if expr[-1][0] == c: expr[-1] += c
		else: expr.append(c)
	# build for loops
	indent = ""
	for e in expr:
		if e[0] in vars: print "%sfor %s in range(%d):" % (indent, e, 10**len(e)); indent += "\t"
	# expression to determine length, print out
	lenexpr = ""
	for e in expr:
		if e[0] in vars: lenexpr += "str(%s)+" % e
		else: lenexpr += "\"%s\"+" % e
	lenexpr += "(\"+\"+str(o))*(o!=0)"
	# build body
	print "%ss = str(%s)" % (indent, expression)
	print "%sr =, s)" % indent
	print "%sif r:" % indent
	print "%s\to = r.span()[0]-offset" % indent
	print "%s\tl = %s" % (indent, lenexpr)
	print "%s\tif o == -1: l = \"-\"+l[:-3]" % indent
	print "%s\tprint \"Found [%%d]; %%s\" %% (len(l), l)" % indent
	print "%s\tif len(l) <= targetlength: print \"!\"" % indent

# main function
def main():
	# setup
	print "import re"
	print "pattern = \"%s\"" % pattern
	print "offset = %s" % offset
	print "targetlength = %s" % targetlength
	# brute force expressions
	for expression in expressions: bruteforce(expression)

# execute if main
if __name__ == "__main__": main()

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.