Shortest 10 Editorial

This CodeFu shortest competition was quite interesting and thrilling until the very end.
As a reminder, in shortest competition a solution need to pass all the 100 test cases, but in the end is the number of characters that counts, the shortest the solution, more points it gets.
You can see all the solutions here and following is a recap of the problems and their solutions.

100 MorseCode

Short description: Decode 5 character digit morse codes into numbers.

There were multiple solutions to the problem, with counting the dots '.', mathematically converting them and then recursively calling the function itself for further processing.

The winning solution is: (hsilomedus)

class MorseCode:
  decode = f = lambda _,s: s and str(8-'---.....-----'.find(s[:5])) + _.f(s[5:])

Let us dive into the solution

  • decode = f = lambda _,s: is the same as def decode(_,s): but takes less characters.
  • decode = f f is to be used later in the recursive call, so this trick saves 3 characters
  • '---.....-----'.find(s[:5]) returns the position of the requested string (first 5 characters of it) into the string, and returning a number different for each morse string combination
  • 8-'---.....-----'.find(s[:5]) converts the previous number to the exact morse number detected
  • str(8-'---.....-----'.find(s[:5])) + _.f(s[5:]) converts only the first 5 characters and recursivaly calls the same function with the rest of the string
  • s and str(8-'---.....-----'.find(s[:5])) + _.f(s[5:]) here "s and" used to stop the recursion. if s is "" it will return s and stop. If s is not "" it will return the second part, continuing the recursion. In python (and many other programming languages) the logical expressions are evaluated until a specific return value is certain. e.g. "a and b", if a is false, the total expression is false, so b is not evaluated.

200 RGB

Short description: Given unlimited number of red, green, blue balls, count the number of ways possible arrangements of N of them so that red are before green and green are before blue.

Very quickly many people noticed the formula for the solution: (N + 1) * (N + 2) / 2

There are two interesting optimized solutions in the results:

  • N * (N + 3) // 2 + 1 (//2 is a integer division by two)
  • 2 + x*x + 3*x >> 1 (>>1 is a division by two and it takes smaller precedent over the rest of the expression so braces are not needed)

One of the winning solutions (MTrajk)

class RGB:
   countWays = lambda _,N: 1+N*(N+3)//2

300 PlanetTemperature

Short description: Given a string in format "i1;i2 j1;j2" and f, compute the average of the i2-i1 multiplied by f.

The solution comes to summing all the pairs (i2-i1)+(j2-j1), dividing by their count and multiplying by f

One neat trick is to replace ';' and ' ' with '-' and '+' respectively, modifying the string to "i1-i2+j1+j2" and then using python function "eval" to calculate the result.

One of the solutions

class PlanetTemperature:
getTemperature = lambda _, i, f: round(-eval(f)*eval(i.replace(";","-").replace(" ","+"))/i.count(';')+.01)

But then, the whole replacing can be done much more efficiently by using translate() function and instead of

i.replace(";","-").replace(" ","+")

use

y.translate({32:43,59:45})

The final solution: (Dekacc)

class PlanetTemperature:
  getTemperature = lambda x, y, z: round(.01 - eval(y.translate({32:43,59:45})) * float(z) / y.count(';'))

The .01 is added for the round() differences in python than the problem description (Round down and round up)

400 MergeNames

Short description: Given an array of strings, sort the array and merge the last to first, second last to second and so forth, repeat the process until there is only one string left

The solution is straightforward, but there were some very interesting techniques used to get the shortest solution

One of the two shortest:

class MergeNames:
  def merge(_,l):
    for k in l:
      l.sort()
      for x in range(len(l)//2):
        l[-x-1] += l[0]
        l = l[1:]
    return l[0]

In this solution hsilomedus is sorting only once, and then adding the smallest to the biggest string, in the process removing the first element with "l = l[1:]"

There is one possible solution mixed between hsilomedus and Dekacc which includes Dekacc's trick to remove the first element

_, *l = l - very neat trick, the _ gets the first element and the rest are assigned back to l

The best solution would then be with score 402

class MergeNames:
  def merge(_,l):
    for k in l:
      l.sort()
      for x in range(len(l)//2):
        l[-x-1] += l[0]
        _, *l = l
    return l[0]

500 Serpent

Short description: Find a number at a corresponding position in a grid where the numbers are spread in a snail like fashion.

The formula for this problem is easy to invent:

find the distance to the closest border x = min(c, r, n-c+1, n-r+1)

return 4*x*(n-x) + (r+c-1 - 2*x) if c >=r or (4*n - 6*x - 3 - r - c) if r > c

The winning solution is: (Dekacc)

class Serpent:
  def findNumber(z, n, r, c):
    x = min(c, r, n+~c, n+~r)
    return 4*x*(n-x) + (r-~c - 2*x, 4*n - 6*x - 3 - r - c)[r > c]

Here two additional trick are used for the shortest solution

-c+1 is replaced with ~c

(a,b)[r>c} will return a if the condition (r>c) is false or b if the condition is true

All in all congratulations to Dekacc for the superb solutions, as well as to everyone else involved. This shortest competition was really very interesting.

We hope to make them more frequent in the future.