kleemans.ch

Code golfing is a fun activity where you try to write the smallest possible program for a given problem.

Some languages were specifically created for golfing, like GolfScript or 05AB1E, but also languages like Perl or APL naturally allow for very small programs.

There exist several dedicated pages for code golfing, like the StackExchange:

There are also others like code.golf or codegolf.codidact.com with include many golfing problems (and solutions).

Discovering Pyth

Most of the languages used are stack-based, which means that they work with some kind of stack - pushing elements to the stack, reading from it, and executing operations on them. (There are also array-based languages like J or APL, though.)

As I'm not that familiar with stack-based languages, I didn't really get into "regular" golfing languages mentioned above.

But then I discovered Pyth, a procedural language, which essentially allows to write very compact Python code - so perfect for me to get started!

Let's dive into a simple example program:

+2 3

This starts with the + operator which takes 2 arguments (2 and 3), and adds them together. The program, if run, will output 5. Note that the operator (here +) always comes first, and the arguments come after it.

Now a slightly more elaborate program:

s.Q

What does this do?

• s (with collection as parameter): reduce with +, so basically the sum function
• .Q: Evaluate input and return as a list

This was my answer to the Code Golf "Add two numbers". If run on the inputs 13 and 28, it will print 41 as a result.

How it works: For two inputs 13 and 28, it first generates the list [13, 28] and then sums them up. Note that we need the "evaluation" of .Q to get numbers, if we would use .z to get a list of the inputs we would just get a list of strings. It then adds them together to get the result of 41.

Now that we have a program, how can we run it (and test it)? Unfortunately, the hosted heroku instance wasn't working, so I forked the repo and deployed a webapp on azure.

You can find the live version here: https://pyth-docker.azurewebsites.net/.

On the left, the upper input is for the program, and the lower for input parameters provided to the program.

Here's a link with the program and example input of the above program: https://pyth-docker.azurewebsites.net/?code=s.Q&input=13%0A28&debug=0

Golfing a problem

But how do you actually start with solving a problem in Pyth? I often find myself doing the following:

1. Come up with a concept on how to solve the problem
2. Implement it in regular Python code (or pseudocode)
3. Re-write it in Pyth
4. Optimize Pyth code
5. Iterate & re-think approach

Let's try and implement "Find the newest element" from the screenshot at the top of this post.

The problem statement is to find the letter which appears last. For example, in the string A-BANAL-BANANA-LAB, the letter L has the latest appearance (at position 6). All letters after that already appeared before L.

Now one simple solution approach would be to keep a string of already seen letters. If a new one appears, we add it to the end of the string, and if we've already seen it, we check the next character. This way after processing all the input, the last letter will be the one we're looking for.

In Python, this would be as follows:

input_word = 'A-BANAL-BANANA-LAB'
seen = ''
for letter in input_word:
    if not letter in seen:
        seen += letter
print(seen[-1])

Now Pyth works with one-letter variables, so we can already adapt the variable names (but still have valid Python code!):

z = 'A-BANAL-BANANA-LAB'
k = ''
for N in z:
    if not N in k:
        k += N
print(k[-1])

Now we can rewrite this almost exactly the same way in Pyth:

FNzI!}Nk=k+kN;ek  # 16 bytes

The code works exactly like our Python code:

FNz                  Loop over input string
   I!}Nk             If not N in k
        =k+kN        Assign k = k+N (string concatenation)
             ;       End of loop
              ek     Print last element of k

You can also try it here.

Improving byte count

Now we have our baseline of 16 bytes. How can we improve this?

One useful feature of Pyth is the debug mode, which we can enable when running a program. The code above then looks like this:

assign('z',input())
for N in num_to_range(z):
 if Pnot(Pin(N,k)):
  assign('k',plus(k,N))
imp_print(end(k))

That almost looks like our Python code before! All operators and keywords are functions (for example Pin() instead of in, or assign() instead of =), but apart from that, it's almost the same. At the end, there is an implicit print which prints the last element of k.

But back to improving the code!

Looking through the language reference, we find V: It is shorthand for the often used FN, a for-loop with variable N. So our solution becomes:

VzI!}Nk=k+kN;ek  # 15 bytes - replace FN by V

Somehow the assignment takes up quite some space. First, we add N to k (the seen elements) and then we assign it again to k: =k+kN. Let's use a list instead of a string, so we can append (a) directly, without an assignment: aYN.

We find in the reference that there's a variable Y which is already initialized with an empty list:

VzI!}NY aYN;eY  # 14 bytes - append instead of assignment

We need an extra space though, because else it will print implicitly everytime we append to Y. But we still save 1 byte!

Re-thinking the approach

Now if we get stuck optimizing existing code, it is often worth thinking about new ways to do something. Looking through the character reference, we find a handy operator:

Exactly what we need! We can remove all the duplicates and print the last element and we're done:

'e{z'  # 3 bytes. Deduplicate & print last character

3 bytes - I don't think we can get any lower than this :)

This is also the program which I submitted, you can see it here:

If you want to get started, I can highly recommend checking out the docs & tutorial. Another helpful resource is the post "Tips for Golfing in Pyth".

Happy golfing!