# Codegolf

I have been running a lot of clashofcode lately and quite a few of the challenges are about making the shortest code possible.

First I disliked them but I feel that you really get to know the language and the standard libraries when trying to push for as few chars as possible. You also get to push yourself to find what is truly the essence of the problem.

Here is an task I did the other day which I think is particularly instructive.

The task is that you are given a weight `c` and a bunch of items with individual weights. How many items can you carry while not going over the weight limit `c`.

Here are the various steps I took during the challenge. I always start with just solving the problem. Once I have a correct solution only then do I try to make it shorter. Below is my first working solution. With comments added after the fact.

``````# Waximum allowed weight.
c = int(input())
# Sorted list of item weights from lightest to heaviest.
items = sorted(map(int,input().split()))

used = []
for item in items:
if item <= c:
used.append(item)
# Update how much weight left we are allowed
c -= item
else:
break
if c == 0:
break
print(len(used))
``````

Same code but compressed slightly. Since weights are always positive the final `if c == 0:break` was unecessary so that was removed as well.

``````c=int(input())
U=[]
for x in sorted(map(int,input().split())):
if x<=c:
U+=[x]
c-=x
else:break
print(len(U))
# 144 chars (as codinggame counts them)
``````

More compressions. But still the same general solution.

``````c=int(input())
U=[]
for x in sorted(map(int,input().split())):
if x<=c:U+=[x];c-=x
print(len(U))
# 97
``````

Now lets count items added directly in the loop. We lose information about which items are added but thats not needed anyways.

Also at this point during the challenge I knew that often sum over a comprehension is the shortest so here I tried to go in that direction step by step. The crux of the problem is that we cannot do the assignment in our curren inner loop as a list comprehension. Comprehensions only allow for expressions, not statements and assignment is a statement.

``````c=int(input())
U=0
for x in sorted(map(int,input().split())):
c-=x
U+=c>=0
print(U)
# 85
``````

Again above we only count the number of items we can add. But never do we in fact add the items to any type of collection.

The original problem statement was about adding items to a backpack. So its easy to get stuck thinking we need to actually mimic that in the code. The domain influences the code.

But since all that was asked for was the number of items then we can skip that. Another way to look at it is that previously all we did with the list was to calculate the length of it, which indicates that we dont need the list at all.

Btw is the type of things I have come to love with code golf. You have a clear goal/loss function and while the goal in itself (compression) is quite silly it does help us find the essence of the problem as a byproduct. The connection between compression and both information and intelligence is quite a profound one as well so its not a coincidence that code golf is so rewarding.

While we try to compress the code here we might say we are closing in on the true minimal but sufficient essence of the solution.

I feel like if we were forced to make the solutions in lambda calculus or with some other fundamental model of computation minimal golf solutions to problems would actually tell us something about the problem. Finding minimal solutions them is another matter.

Using python however dilutes because for instance it has builint libraries so a few chars might hide a deluge of complexity behind the scenes. But if we were forced to implement everything from the ground up then comparing how short the shortest known code golf solution is to two given problems would probably tell us something about the nature of the problem itself. But with python it tells us more about python than the problem I think.

Thats just my gut feeling however and its not relevant to the code at hand, so lets get back to the code!

``````c=int(input())
U=0
for x in sorted(map(int,input().split())):c-=x;U+=c>=0
print(U)
# 82
``````

Again the goal for me at this point in the challenge was to get to a list comprehenssion.

Next I made a small detour and stored the function `input` to a variable `I` and used that instead. Its always shorter if its used 3 times. And in codinggame we can replace `print` with an `input` in some cases since it will in fact write to `stdout`. It will cause an exception since there is no more input to get, but that is allowed by the platform, it only cares you get the right output on `stdout`. So consider this an ugly hack.

``````I=input
c=int(I())
U=0
for x in sorted(map(int,I().split())):c-=x;U+=c>=0
I(U)
# 78
``````

Here finally with the walrus operator we can see the end in sight! Once we get only one expression (like here below) we can inline it.

The walrus operator `:=` is like the ordinary assignment operator `=` but the expression also evaluates to the value you assigned to. So `c = 10` assigns 10 to c and so does `c := 10` but with the difference that we can chain the second like this `(c := 10) == 10` which would evaluate to `True`.

``````I=input
c=int(I())
U=0
for x in sorted(map(int,I().split())):U+=(c:=c-x)>=0
I(U)
# 80 longer!
``````

The solution is a bit longer, but it has the potential to become a list comprehension which should give us a net benefit in the end.

Below I can now remove the variable `U` and inline the whole expression. We need to add `sum` but in total this saved us 2 chars compared to the previous best result of 78.

``````I=input
c=int(I())
I(sum((c:=c-x)>=0 for x in sorted(map(int,I().split()))))
# 76
``````

Finally swapping the order of the comparison allows us to remove a whitespace.

``````((c:=c-x)>=0 for ... ) # original
(0<=(c:=c-x)for ... ) # 1 shorter
``````

``````I=input
c=int(I())
I(sum(0<=(c:=c-x)for x in sorted(map(int,I().split()))))
# 75
``````

A final note on how the chars are counted. I use the count from codingame which might differ how your editor counts. A newline is only 1 char, while on windows you might get 2. This means that the solution below would not have been shorter, only harder to read.

``````I=input;c=int(I());I(sum(0<=(c:=c-x)for x in sorted(map(int,I().split()))))
# 75 (Not shorter and uneccesarily hard to read.)
``````

If you are looking form some closing words this is it.

Written on November 17, 2022