Editorial for Andyman's Golf Course - Hole 5 - Collatz Conjecture


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: AndyMan68

This problem was designed to make use of lambda recursion, which is something that is not so well known.

A lambda function is essentially a special function (which may or may not take in input) that can be defined by a variable, and is mainly used for short and simple tasks. They can be used without having an identifier in certain situations that don't require one, such as sorting by a customized comparator or with the map() function. An example follows below:

a = lambda x: x+2
print(a(5))

which outputs

7

This lambda function takes in a value x as the input to the function, and returns x+2.

Interestingly, we can call a lambda function recursively, however it usually can only handle simple tasks since it is one line long.

79 bytes

We can implement a simple recursive lambda function with the use of if-else statements as such:

c=lambda n:0 if n<2 else n+c(3*n+1 if n%2 else n//2);print(*map(c,range(1,51)))

We then use the map() function to apply the lambda function variable c on all integers from 1 to 50 inclusive.

74 bytes

We can improve the if-else statement within the recursive call using a list of integers 3n+1 and n/2 and using the value at index n%2.

c=lambda n:0 if n<2 else n+c([n//2,3*n+1][n%2]);print(*map(c,range(1,51)))

Unfortunately, we cannot use this trick for the other if-else statement, as the list would then be initialized with the recursive call, and so Python will execute it no matter what.

72 bytes

One other optimization is that in certain cases, we can remove the space between if-else statements as long as it doesn't interfere with a variable.

c=lambda n:0if n<2else n+c([n//2,3*n+1][n%2]);print(*map(c,range(1,51)))

71 bytes or less

To achieve 71 bytes or less (in one case even 64) can be done by optimizing the if-else statement in various ways (one of which uses the ~ operator in Python).

These optimizations are left as an exercise to the reader.


Comments

There are no comments at the moment.