Hi, there!

For the last few days I’ve been participating in the Tuenti Challenge, a coding competition organized by the engineering team of Tuenti. There are a total of 20 problems that you need to solve in order with the possibility of skipping 3. Most of them are related with algorithmic search and optimization, but there are also some nice ones related with security.

This was my first time participating and I have to say that it was a really cool experience and I’m happy with what I’ve done: started 11 problems, solved 9, and finished the 66th out of at hundreds of participants. And most important, it has been very useful to remember things and learn new ones, as well as get faster scripting in Python.

So I since I paid for the domain of this blog I may as well post my solutions in here. Will try to put code snippets if needed, but I’ll better not show the full raw code I used during the challenge, because it is not pretty. And the explanation of the original problem will be linked in each title.

All the different posts will be grouped here.

Let’s go with the first 4 problems!

Challenge 1: Onion wars

Well, that was easier than expected… I guess an early win keeps participants engaged later(?).

Anyway, in order to know the total amount of tortillas just divide by 2 the number of people who want it with or without onion, round up and sum. Yey!

number_tortillas = math.ceil( people_with / 2 ) + math.ceil( people_without / 2 )

Challenge 2 - Help Battlestar Galactica and save humanity

As you go through the exercises you realize that the engineering team of Tuenti is geek as hell. And it is really funny and cool!

So we have a graph representing all the space routes between planets and we need to find the number of paths that go from Galactica to New Earth. This implies that we need to traverse the whole tree of possible routes and not much optimization is possible (if you only wanted to find the shortest path you could use something more efficient like the Dijikstra’s algorithm). I used a simple recursive approach:

'''
Parameter graph is a dictionary which keys are the planets and values 
are lists of the possible destinations from that planet. Example:
graph = {'Galactica': [ 'A', 'B', 'C' ],
        'A': [ 'D', 'E' ],
        'B': [ 'D' ],
        etc...
        }
'''
def count_paths(graph, start, end, visited = None):
    if not visited:
        visited = []
    
    visited += [ start ]
    
    if start == end:
        # We found a path
        return 1
        
    paths_number = 0
    # Check possible paths from the neighbours of the starting point
    for node in graph[ start ]:
        # Check if that planet is already visited to avoid loops
        if node not in visited:
            paths_number += count_paths( graph, node, end, visited )
            
    return paths_number

Bonus Python tip

There is a detail about Python that I discovered during these days and that is present in the snippet.

If you use a default value for some of the parameters of a function, this will be created once at the initialization fo the function and then be used in each call. This means that if that value is an object that can be modified, such as a list, the content of it will be preserved between calls, even though you expected the ‘visited’ param to be an empty list each time.

To have the expected behaviour of an empty list in each call, you need to do as I did and initialize the variable when the value is None.

On the other hand, this behaviour of default params is an extremely easy way to implement memoization

Challenge 3 - Origami Punchout

We have a folded paper with holes. Every time we unfold the coordinates origin moves to the upper left corner and then new holes are created symmetric to the old ones. We have two kinds of situations:

  • Unfolding to the right or the bottom: the old upper left corner remains, so there is no change in the coordinates origin. Therefore, the coordinates of the original holes are the same.

  • Unfolding to the left or the top: the old upper left corner is now in the middle of one of the two axises, so we move the coordinates origin. as a result, the coordinates of the original holes are increased by the length of the old folded paper in that axis.

Here you have the calculation for each scenario. Note that since the upper left corner is the postion (0,0), the maximum coordinate value in one axis is width - 1 or height - 1.

for punch in punches:
    if fold == 'L':
        new_punch_1 = ( width - 1 - punch[0] , punch[1] )
        new_punch_2 = ( width + punch[0] , punch[1] )
        
    elif fold == 'R':
        new_punch_1 = punch
        new_punch_2 = ( 2 * width - 1 - punch[0] , punch[1] )
    
    elif fold == 'B':
        new_punch_1 = punch
        new_punch_2 = ( punch[0] , 2 * height - 1 - punch[1] )
    
    elif fold == 'T':
        new_punch_1 = ( punch[0] , height - 1 - punch[1] )
        new_punch_2 = ( punch[0] , height  + punch[1] )

Challenge 4 - Candy patterns

Oh, boy, this problem was the first that made me sweat a bit to understand the solution path. Well, to be honest, a big part of the struggle was understanding the problem itself. So let’s go step by step.

People come and ask for an amount of candies, and then that number N gets writen N times. Examples:

  • One person asks for 3 candies: 3 3 3
  • Two people ask for 3 candies and other asks for 2 candies: 3 3 3 3 3 3 2 2 or 3 3 3 2 2 3 3 3 or 2 2 3 3 3 3 3 3

The list is shuffled and cut so that if you repeat X times the fragment, you obtain the original list. Examples:

  • Original list is 3 3 3 3 3 3 2 2 and X = 2, the fragment can be: 3 3 3 2 or 3 2 3 3 …
  • Original list is 4 4 4 4 4 4 4 4 4 4 4 4 6 6 6 6 6 6 3 3 3 3 3 3 and X = 3, the fragment can be: 4 4 4 4 6 6 3 3 …

All of this is easier to understand if we look to a counter instead of the raw lists. However, in order to keep things readable I’ll use the following terms:

  • i: amount of candies given to one person. For example i=2 represent everything related to the situations in which the amount of candies given to each individual was 2.
  • L(i): number of times that i appeared in a fragment or original list.
  • P(i): number of people who were given i candies each.
  • A(i): total number of candies given to all the people who were given i candies each.
  • X: the multiplier used to restore the original list from a fragment.

A counter is something like

{ i: L(i) , i+1: L(i+1) ... }

which is equivalent in the original list to

{ i: i * P(i) , i+1: (i+1) * P(i+1) ... }

and finally also equivalent in the original list to

{ i: A(i) , i+1: A(i+1) ... }

We know too the relation between original list and fragmented lists

original_counter == X * fragment_counter = { i: X * L(i) , i+1: X * L(i+1) ... }

So our previous examples become:

# Counter when one person asks for 3 candies (1 * 3 = 3)
counter_a = { 3: 3 }

# Counter when two people ask for 3 candies (2 * 3 = 6) and other 
# asks for 2 candies (1 * 2 = 2)
counter_b = { 2: 2 , 3: 6 }

# Counter when three people ask for 4 candies (3 * 4 = 12), one 
# person asks for 6 candies (1 * 6 = 6) and two people ask for 3 
# candies (2 * 3 = 6)
counter_c = { 3: 6 , 4: 12, 6: 6 }

# Counter of the fragment 4 4 4 4 6 6 3 3 with X = 3 from the example c
X_f1 = 3
counter_f1 = { 3: 2 , 4: 4, 6: 2 }

# Counter of the fragment 4 4 6 3 with X = 6 from the example c
X_f2 = 6
counter_f2 = { 3: 1 , 4: 6, 6: 1 }

# We see that it is true
counter_c == X_f1 * counter_f1 == X_f2 * counter_f2

Now, the answer of the exercise is the average number of candies given by person, for which we need the total number of candies and people, so we have to find the value of X for the fragments that we receive. But how?

We know that given a fragment, for each i

L(i) * X = i * P(i)

therefore we know that

( L(i) * X ) % i == 0

where % represents the remainder of the division.

So X is a number that validates the previous equation for every i present in our counter. And how do we get a number that can be divided by a bunch of different amounts? Obtaining a common multiple of those amounts. Note that even though I use the least common multiple, any common multiple will lead to the same result, because it will be simplified in the last step.

With X being the least common multiple we can reconstruct the counter of the original list in which L(i) == A(i) and directly obtain the total amount of candies served by doing the sum of all the A(i).

Then we find the people in each group i with P(i) = A(i) / i and sum all the P(i) to obtain the total amount of people.

Once we have those two numbers we only need to simplify the fraction by dividing both candies and people by their greatest common divisor and there you have the average number of candies given to each person as an irreductible fraction.

In case the explanation may be a bit hard to follow, here you have the code:

import math
from collections import Counter

# Function to calculate least common multiple of a list of numbers
def lcm(numbers):
    lcm = numbers[0]
    for x in numbers[1::]:
        lcm = lcm * x // math.gcd(lcm, x)
    return lcm

numbers = # do some magic to read from file

# Create a counter of the fragment
counter = Counter(numbers)
# Get the different amounts of candies given to people
amounts = list(counter.keys())
# Least common multiple of all the amounts
x = lcm(amounts)
# Reconstruct counter of original list
orig_counter = { amount: x * counter[ amount ] for amount in amounts }
# Total amount of candies in original list
candies = sum([ orig_counter[ amount ] for amount in amounts ])
# Total amount of people in original list
people = sum([ orig_counter[ amount ] // amount for amount in amounts ])
# Use greatest common divisor to simplify the fraction
d = math.gcd( candies, people )
simp_candies = candies // d
simp_people = people // d

print(f'Average candies/person: {simp_candies}/{simp_people}')

And that was all for today. In next posts I’ll talk about problems 5 to 10.

See you!