Shortest 11 Editorial

And once again, we come to an end to yet another shortest solution competition.
It was a very close call until the very end, including a lot of turn arounds as well as a lot of plot twists and not a clear winner until the very end.
You can see all of the solutions here, as well as an editorial of the best and most creative solutions to follow. Please note that if there are multiple solutions that are exact copies of each other, a solution will be chosen by the time it had been submitted as the winning one (as in, the first time it has been submitted). Here are some general reminders of things used in shortest solution contests to avoid repetition in the editorial:

Whenever possible to squish the solution into one line, writing

name = lambda __self__, param1, param2: "insert code here"

is shorter than writing

def name(__self__, param1, param2):
  return "insert code here"

In shortest solution contests, writing something like

def name(__self__, param1, param2):

is the same as writing

def name(_, a, b):

(the _ for __self__ can be anything else)

100 Transform

Short description: Get from one array to another by either decrementing/decrementing an element or shifting the array to the right.

The winning solution is: (anikov)

class Transform:
  minTransformations = lambda _,a,b: min(i + sum(abs(j - k) for j,k in zip(a,b[i:] + b)) for i in range(51))

The solution breakdown is as follows:

• The solution revolves around simulating all of the possible combinations of changes to the array we might trigger so that we get the desired result
• This includes the sum of absolute differences between the corresponding elements in the lists plus the number of shifts the array had received previously
• min(list)

is the way of getting a minimum in a list in Python (keep in mind that the list provided to the method does not have to consist of integers)
• zip(a, b)

is a way to get a list of tuples of the like of (a[i], b[i]) for each i from 0 to the length of either of the lists, assuming the lists are of same length
• if a and b do not have the same length however, zip(a, b) will provide a list of (a[i], b[i]) tuples for each in in the natural number range of [0, min(len(a), len(b)) ]
• Instead of shifting list a around, having
  
zip(a[-k:] + a[:-k], b)

we can shift list b and get rid of the negative sign, having
  
  zip(a, b[k:] + b[:k])

  or while taking the previous point into account we would get
  
zip(a, b[k:] + b)


• It is enough to do range(51) to go through every possible combination of operations because the length of the array is at most 50 (meaning anything above it would just cycle through combinations over and over)
• Doing something along the lines of:
  
for i, j in list_of_tuples

will provide us with the first (i) and second (j) value of each tuple in list_of_tuples correspondingly (more commonly known as unpacking values)

110 GreaterOrEqual

Short description: Given an array of integers, find a the smallest possible positive integer X, for which exactly K elements from the array are greater than or equal to it - or return -1 if there no such X exists

The winning solution is: (Lepluto)

class GreaterOrEqual:
  def getMinimumX(_, l, k):
    b, *s = sorted(l + [0])[~k:]
    return -(b in s or ~b)


The solution breakdown is as follows:

• It's very important to note that instead of brute forcing the solution we can find one doing a few very simple operations. Instead of running through all of the elements for every possible integer within the constraints (which will still pass the time constraints), we can simply sort the array and look for an element for which we know the condition is satisfied implicitly. Given a sorted version of the array called sorted_list, this would leave us with three options:
  • If the (k - 1)th number from the back of sorted_array (let us call it S) is not equal to the kth one (let us call it T), then the answer is S + 1
  • If S is equal to T on the other hand, the answer is always -1
  • If K equals zero, the answer is sorted_array[sorted_array.length() - 1] + 1
  The first two options should be fairly obvious - having S and T be the same means that trying to surpass S and finding the next integer that satisfies the condition would break, since we would surpass T as well. Having them been different however - due to the condition that the numbers we are looking for have to be greater or equal to X, we will always be able to find such a number. For K == 0 we simply handle an edge case of trying to find an integer that is out of the range of the array.
• Writing ~k is the same as writing -k - 1 in Python
• sorted(l) provides us with an inline sorted copy of the list
• The trick covered by writing sorted(l + [0]) is to add one more element to the list, or in this case the number 0. We add 0 because the constraints strictly specify we will have positive integers only in the array. Adding another seemingly arbitrary integer to the list takes care of our K == 0 problem entirely since now the list will not go out of bounds
• Writing something along the lines of
  head, *tail = some_arbitrary_list
  is the same as writing
  head = some_arbitrary_list[0]
tail = some_arbitrary_list[1:]
  in Python. It is called unpacking and it is a very neat trick used in code golfing.
• some_arbitrary_list[-k:] is the same as writing some_arbitrary_list [len(some_arbitrary_list) - k:], or essentially giving us a range of elements from len(some_arbitrary_list) - k to len(some_arbitrary_list) - 1 inclusive
• Instead of checking if b == s[0], we can simply check if b in s - and this will be the same due to the sorted nature of the list (if b exists in s, then it is exclusively equal to s[0], since otherwise the sort would be broken)
• In the event that the condition b in s does not go through, calculating the negative of ~b is precisely b + 1, whereas if it is true then the answer would be -1

200 BeautifulString

Short description: Find the minimal distance between two identical characters in a given string

The winning solution is: (martinkozle)

class BeautifulString:
  remove = lambda s, t: min(min(map(len, ('                                                                                                  %s                                                                                                  ' % t).split(i))) + 1 for i in t) % 99 - 1

The solution breakdown is as follows:

• The winning solution uses a simple concept combined with a very clever manipulation of empty spaces not being counted in code golfing to avoid using conditions whenever an answer is not available. The approach is a simple brute force one, splitting the modified string by every character and calculating the residual length of characters that are left after the split.
• map(function, list) creates a mapped_list of elements, such that each element mapped_list[i] == function(list[i])
• The solution revolves around putting exactly 98 spaces on each side of the string, so that when it is split by a particular character we get 98 + len(substring), or 98 characters at a minimum (likely more) to which we later on add 1
• This way, calculating the result modulo 99 later on does two things:
  • If a solution exists, result % 99 - 1 will cut off any residual length in the string (since we specifically added 98 spaces to each side of the string) and provide us with the correct solution
  • If a solution does not exist, it is guaranteed that the minimum would be exactly 99 (since the string would be split on the first character during the first iteration and the residue would be exactly 98 + 1), providing us with 99 % 99 - 1 == -1, which is the correct solution to the problem

Although this is an extremely cool and unconventional way of solving this problem, I would like to point out two other solutions who had the same amount of points but entertained a bit of a different approach:

• The solution by anikov:

  class BeautifulString:
  remove = lambda _,a: min(a[i:].find(a[i],1) % 99 for i in range(len(a))) % 98 - 1

• The solution by haris:

  class BeautifulString:
  def remove(_, s):
    m = -1
    for c in s:
      s = s[1:]
      f = s.find(c)
      if f % 99 < m % 99:
        m = f
    return m

• Both of the solutions rely on modular arithmetics to normalize the result returned by the find method in Python - the nearest index if one exists or -1 if it does not
• Essentially, normalizing it like this would guarantee that the result of finding the minimum would be in the integer range of [0, 98], meaning using modulo 98 afterwards would allow us to find -1 without wasting characters on unnecessary conditionals
• The caveat in haris' solution is that he normalizes the values themselves while checking instead of normalizing and recalculating the result, which ends up being the same amount of characters

210 WorldOfWarcraft

Short description: Find the smallest sum of consecutive numbers from an array (starting at the beginning) that is larger than a number X

The winning solution is: (Lepluto)

class WorldOfWarcraft:
  def getExperience(_,r, n, d):
    for i in d:
      r -= i
    if r < 0:
      return -r

The solution breakdown is as follows:

• This was a very easy problem to golf. The solution is a complete brute force simulation of the requirements and is short enough as it is.
• There are no particular tricks used in this solution, apart from the fact that n is never used anywhere because there is no need

300 WordPuzzle

Find the length of the most reoccurring substring consisting of consecutive dots ('.') across all rows of the input list of strings

The winning solution is: (martinkozle)

class WordPuzzle:
  getMostReoccuringLength = lambda s, b: -max(range(-99, 0), key=[i.count('.') / ~('.X.' in i) for i in b].count)

The solution breakdown is as follows:

• The solution itself does not use any particular properties to solve the problem in a faster way, it's just a normal bruteforce done in a very, very clever way
• max(list, key = function) is a way of getting the logical maximum of a list based on a certain function to calculate the key under which we get the maximum
• Instead of counting each length of the consecutive character strings, we can go through each possible length (so basically a range from 0 to 99) and check how many times each possible length appears. The way max() works in Python is that if there are multiple values that appear that satisfy the key function, it takes the first one that appears. With this said, instead of going from 0 to 99 we can go from 99 to 0 and make sure that the maximum value would be acknowledged every time.
• The more intuitive way to get this range would be to go through it with range(99, 0, -1), however the optimal way for this particular problem would be to run something similar to -range(-99, 0) which will become evident a bit later in the explanation
• max(range(x), key = list.count) is the same as writing max([list.count(i) for i in range(x)])
• The cool part of this solution relies completely on the fact that the test cases happened to be very weak - in particular for all test cases but 1, each string row has 'X' characters only at the beginning or at the end of the string - meaning we can completely abuse this fact to gain more characters
• If this had been true for all of the test cases, it is obvious that a simple count of '.' of each row would grant us a correct solution. Fortunately, the only case that this solution does not work for provides double the length of the actual solution, so dividing the answer by ~('.X.' in i) gives us two cases:
  
  • If 'X' does exist in a certain line, we will divide by -1 -1 = -2, which provides us with the correct solution for the only test case that can't be abused
  • If 'X' does not exist in a certain line, we will divide by -1, meaning we get the correct length for that row
• Since the solution is obviously negative now due to the division, we can use the range through the negative symmetric values of the range so that the count function works (it will search for negative values
• Finally, since the max function would also return a negative value now (from range(-99, 0)), to get the correct solution we just need to write a minus sign before the entire snippet and it will be done

Keep in mind that there are countless counter examples to this solution - however since it works for these test cases in particular it's completely valid and very creative.

Following is also a solution (that is 2 characters longer) but would work for any test case:

class WordPuzzle:
  getMostReoccuringLength = lambda _, b: max(('X'.join(b).split('X').count("." * i), i) for i in range(1, 99))[1]

The short explanation for this one would be:

• string.join(list_of_strings) is basically a concatenation of every element in list_of_strings with string between each concatenation
• 'X'.join(b).split('X') simply converts the entire list of strings to a list of strings containing only consecutive '.' characters
• We then count every value of '.' * i for every i in range(1, 99) to go through all of the possible strings that could appear inside and create tuples of the format (length_count, length) for every possible value
• Running a max() function over a list of tuples finds the maximum by the first value of the tuple - and if multiple maxima exist it finds the maximum between them by the second tuple value as a break rule
• We then pick the second value of the maximum tuple as this is the answer to our problem

To sum everything up, very big congratulations to martinkozle for the extraordinary and proficient solutions, as well as to everyone else involved and dedicated to this huge community event. It was a really close call until the very end and fun and interesting for everyone trying to escape their everyday and monotonous problems.

With that said, we really hope we can organize a lot more of these types of competitions in the future.