Telefonica Code Challenge 2021 participation

Este artículo se puede leer en castellano aquí.

From December 13th to December 20th, 2021 Telefonica Code Challenge, the evolution of “Tuenti Challenge” occupy my few free hours https://codechallenge.0x14.net .
I tried to take part in Tuenti Challenges in the past but I always forgot about signing up on time for them, so this has been my first experience.

The Challenge had 20 programation, algorithmical and reversing challenges and I was able to do 13 of them. It was a high load work week in the office and I only have few hours in evenings and nights so I am proud of being able to solve 13 of 20. I got 49th position as can be checked in https://codechallenge.0x14.net/Stats

I decide to fight on this Challenge using python and looking at results it has been a great idea. The high amount of libraries that can be easily integrated into a python code and the lists, dictionaries and tuples of python do most part of the work in every challenge.

For anyone that wants to test itself i reccomend https://www.codingame.com/multiplayer/clashofcode website.

All the python scripts used are available at https://github.com/botmakerdvd/code_challenge_2021

Challenge 1: Roll the dice

Let’s play a very simple dice game. In the game, two players throw two dice and the score is the sum of the dice throws. The player with the highest score wins the game. If both players get the same score the game is a draw.
Input

The first line will have an integer N, which is the number of cases for the problem. Each case has the result of the dice roll of the first player represented by two numbers (between 1 and 6) separated by ‘:’.
Output

For each case, there should be a line starting with “Case #x: ” followed by the minimum score the second player needs to win the game, or ‘-‘ when it’s impossible to win (there can only be a draw after scoring all 6 dice).

Resolution code: https://github.com/botmakerdvd/code_challenge_2021/blob/master/1/1.py

This is quite simple so let’s go to the next challenge

Challenge 2 – Catch them all

Something strange has happened. All your pokemons have escaped. Can you catch them all?

You’ve been given a map (shown with rows and columns) so you can find all the Pokémon. The Pokémon’s name can only be found horizontally. But it can be written from left to right or right to left and it can be on more than one line. Once you catch a Pokémon make sure to remove it from the map. Because each Pokémon only appears once and some Pokémon can be hidden within other Pokémon.
Input

The first line will have an Integer N, which is the number of cases for the problem. It is followed by a description of T cases. Every case has an Integer P, which is the number of Pokémon to find, an Integer R, which is the number of rows, and an Integer C, which is the number of columns. Then it has P lines with the names of each Pokémon N. And finally R lines with C characters split by an empty space.
Output

For each case, there should be a line starting with “Case #x: ” followed by the result of the map without the Pokémon.
Limits

1 ≤ T ≤ 20
1 ≤ P ≤ 50
1 ≤ C, R ≤ 100
1 ≤ N ≤ 100

Resolution code: https://github.com/botmakerdvd/code_challenge_2021/blob/master/2/2.py

Using Python lists this challenge is also very easy.

Challenge 3 – The night of the hunter

Love or Hate? True or False? Create or Destroy? Which word would win in a hypothetical fight between antonyms? It depends on the values of the letters, of course.

Input

The first line has an integer N, which is the number of cases for the problem. Each case is a fight between two antonyms. Each line has:

Two opposite words separated by ‘-‘
The character ‘|’
The value of each letter, which can be an integer or a fraction. The list of letters with its values can be in many formats:
As a dictionary:

{‘a’: 2/3, ‘e’: 4, ‘h’: 3, ‘l’: 5, ‘o’: 1, ‘t’: 6, ‘v’: 0}

As a list of tuples:

[(‘a’, 2/3), (‘e’, 4), (‘h’, 3), (‘l’, 5), (‘o’, 1), (‘t’, 6), (‘v’, 0)]

As a list of assignments:

a=2/3,e=4,h=3,l=5,o=1,t=6,v=0

Output

For each case, there should be a line starting with “Case #x: ” followed by the winning word or ‘-‘ when the result is a draw.

Resolution code: https://github.com/botmakerdvd/code_challenge_2021/blob/master/3/3.py

Initially every input information about value of letters has been translated into a dictionary, this makes the second part of the program very easy.

Fraction library has been used to avoid precission problems with floats .

Challenge 4 – Let’s build musical scales

Did you know there are really 12 notes and not 7? Don’t forget the sharps and flats. Those are the black keys on a piano or keyboard. A musical scale is just a series of 7 of the 12 notes. Now, we’re going to build some musical scales with different roots.

If we use the English notation notes are represented from A to G (A=La, B=Si, C=Do, etc.). You should also know that the note following most notes, except B and E, is the sharp, for example A and A#. But every sharp note can also be flat for the note after it. So A# can also be called Bb. So, the sequence of notes from A to B can be A-A#-B or A-Bb-B. There is one special rule. Some version of every note must be included in the scale , either natural, flat or sharp. So in some circumstances a modified version of B and E could also be included in the scale.

The root of a musical scale is the first note of the scale. So, if you have a C scale the first note will be C, and so will the 8th one. A sequence of semitone and tone jumps is defined when creating a scale. A semitone jump is just the next note in the sequence of all notes. A full tone jump means 2 semitones. So, you jump 2 notes to find the next note in the scale. For instance, the major scale is built with the sequence tone-tone-semitone-tone-tone-tone-semitone (TTsTTTs). So, the C major scale has the notes CDEFGABC. There are no sharps or flats.

C Major scale

But what happens when a sharp or flat is included in the scale? Should we use the sharp or the flat? It’s easy. Note names can only appear once in any given scale. So, if you already have A, for example, you cannot also have A#, so Bb is used.
Input

The first line will have an integer T, which is the number of cases for the problem. It’s followed by a description of T cases. Every case has two lines. The first line of each case has the root of the scale to generate. It can be a simple note or a modified note (sharp or flat). The second line of each case has a string of 7 characters describing the scale steps. “T” means a tone and “s” means a semitone.
Output

For each case, there should be a line starting with “Case #x: y”, where x is the test case number (starting with 1) and y is a string with the notes of the scale.

Resolution Code: https://github.com/botmakerdvd/code_challenge_2021/blob/master/4/4.py

I solve this challenge by generating 2 dictionaries, one for having next tone of each note, and the other for next semitone of each tone.

Challenge 5 – Invictus

Nelson Mandela

INVICTUS

Out of the night that covers me,
Black as the pit from pole to pole,
I thank whatever gods may be
For my unconquerable soul.

In the fell clutch of circumstance
I have not winced nor cried aloud.
Under the bludgeonings of chance
My head is bloody, but unbowed.

Beyond this place of wrath and tears
Looms but the Horror of the shade,
And yet the menace of the years
Finds and shall find me unafraid.

It matters not how strait the gate,
How charged with punishments the scroll,
I am the master of my fate,
I am the captain of my soul.

William Ernest Henley

Input
Find the PASSWORD hidden in the following file: Invictus.txt
Output
Find the PASSWORD. It contains the SURNAME in UPPERCASE of the famous person in the picture.

Resolution code: https://github.com/botmakerdvd/code_challenge_2021/blob/master/5/5.py

This is the first reversing / hacking challenge. I used a hex viewer to see that there was something hidden on provided Invictus.txt . I discovered that using non printable ascii characters some values were hidden. It seems that each value was a 4 byte tuple, with data on 3rd and 4th bytes of each tuple.

Once I got those values I discovered that there were 2 kinds of values, some of the have 0x81 as the first byte and others do not.

Once I got those values, as I know the solution must contain the full name of NELSON ROLIHLAHLA MANDELA I discovered that a susbtitution cipher has been used. It was easy to reverse that cipher checking which value could be A letter, and then performing a substraction with the A letter ASCII value I got it solved.

Or… not? Finnally I discovered that 2 different substitution ciphers where used, depending on the first byte, if the first byte was 0x81, 110 must be substracted , if not 302 must be substracted

Challenge 6 – What day is it?

Have you ever wondered what day of the week a date is? I’m sure you have. In this challenge, you have to code a program to figure out how to tell anybody the day of the week (from a list of languages) for a given date.

Input

The first line has an integer N, which is the number of cases for the problem. Each case has a date, the character ‘:’ and a two-letter language code.

The date format can be: YYYY-MM-DD or DD-MM-YYYY
All dates are after 1970-01-01
Input cases may have invalid dates, like an invalid month (MM>13) or an invalid day of a month
The weekday of a date can be given in any of these twenty languages:

CA: catalan CZ: czech DE: german DK: danish EN: english
ES: spanish FI: finnish FR: french IS: icelandic GR: greek
HU: hungarian IT: italian NL: dutch VI: vietnamese PL: polish
RO: romanian RU: russian SE: swedish SI: slovenian SK: slovak

Output

For each case, there should be a line starting with “Case #x: ” followed by the weekday IN LOWERCASE of the day in the indicated language, or ‘INVALID_DATE’ if given date is invalid, or ‘INVALID_LANGUAGE’ for an unknown language code.

Resolution code: https://github.com/botmakerdvd/code_challenge_2021/blob/master/6/6.py

Using locales and locale library, this challenge become easy

Challenge 7 – Escape or Die

Hello, dear friend. Do you feel like you’re in some kind of jail? Did you wake up this morning with the feeling that everything was dark?

Well, it isn’t a dream. You’re really here, in a long dark dungeon.

What do you have to do? It’s simple. Try to escape from the dungeon. But, hurry up or something bad will happen to you.

You have to find the shortest path to the exit to escape the maze.

Good luck, my friend. Your dungeon is waiting for you at codechallenge-daemons.0x14.net:4321
Input

No input needed
Output

A list of coordinates with the shortest path to the exit. The list must have the following syntax:

(x0, y0), (x1, y1), (x2, y2), (x3, y3)… (xn, yn)

Where (x0, y0) is the starting position in the maze and (xn, yn) is the final position (the exit).

For example, if your initial position is (3, 4) and the exit is at (5, 6), the following could be a good solution:

(3, 4), (3, 5), (3,6), (4, 6), (5, 6)

Assuming the path is clear, of course.

Resolution code: https://github.com/botmakerdvd/code_challenge_2021/blob/master/7/7.py

I used Dijkstra’s algorithm to solve this, and integrate a telnet library into my python code . Explanation of this algorithm can be seen here https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Challenge 8 – Awesome Sales Inc.!

You’ve been contacted by a company called Awesome Sales Inc. They recently bought some new ultra-modern AI based software for creating travel plans for their sales force. But, it seems to have a huge problem and the developers have gone MIA. So they need you to figure out how to fix it.

The “awesome” software works with two modules. The first module (AICityPicker) picks the best cities to be visited by each employee based on a number of the employee’s records and traits. It also takes another important factor into account, which is that employees can move between cities on an ASCB (Awesome Sales Connection Bus).

Once the cities have been picked by the AI, a plan is generated in the form of bus tickets that can be used multiple times to move between cities. For example, t1: [A, B] is a ticket that can be used to go from city A to city B and vice versa. In the plans, employees can always reach one city from another using their tickets. For example, if an employee has to visit cities A, B and C, there will always be a way to go from A to C, even if they have to go from A to B and then from B to C.

The other module (AICityRemover) is the one with the problems. Once a plan is generated, this module evaluates budgets, costs and other things and picks cities from the initial plan to remove. It cancels the bus tickets for them and everything else – all automatically.

The biggest problem is that this module doesn’t take the ASCB into account. Cities are removed and employees can no longer reach all their destinations. For example, if an employee has to visit A, B and C, the module may remove B, even if none of the ASCB can go from A to C directly. So, when an employee finds themselves in that situation they have to find a way to reach their destination. Sometimes they pay for a regular bus ticket or taxi out of their own pocket or they might even ask a stranger for a ride. Not good.

Of course, you don’t have access to the source code. But, you manage to reverse engineer the AICityRemover module and find the root cause of the problem. A function called currentPlan.getCriticalCitiesThatCannotBeRemoved() wasn’t implemented and always returns an empty list! Luckily, the documentation has some examples so you can work out your own implementation.

You need to write the getCriticalCitiesThatCannotBeRemoved() function so that for each plan it returns a list of cities that can’t be removed. In other words, the list of cities where if any city is removed the initial plan breaks and the employee can’t reach the rest of the cities using their ASCB tickets.

Cities are removed one by one, so when a city is removed from the initial plan, other cities might become critical now but that would be a whole new case. You need to provide the list of cities that are critical from the initial plan.

Input

The first line will have an integer C, which is the number of cases for the problem. The description of the C cases follows. For each case, the first line is an integer T showing the number of tickets. Then T lines follow, each describing a ticket. Each ticket is described in the form “City A,City B”, which means the ticket can be used to go from City A to City B and vice versa.
Output

For each case, there should be a line starting with “Case #x: y”, where x is the test case number (starting from 1) and y is the list of the critical cities, in the form “City A,City B”. The list should be ordered alphabetically. If none of the cities are critical a dash (-) should be printed instead.

Resolution code: https://github.com/botmakerdvd/code_challenge_2021/blob/master/8/8.py

This challenge can ve very easily solved with Graphs theory and the networkx library. In Graphs theory the critical cities are called articulation points, and the networkx library help us a lot finding them.

Challenge 9 – Collisions

We’re building the collision detection module for our 2D game engine. We want to be able to process a lot of sprites at the same time and detect all the collisions. We’ll provide the bitmask for each sprite, where 0 indicates transparency and 1 indicates a solid part of the sprite. If two solid parts of different sprites share the same location then it’s counted as a collision. If two sprites collide at different points a single collision is counted. A sprite can collide with multiple other sprites.

Given a set of sprites, return how many collisions are detected.

Limits

T ≤ 10
D ≤ 10
W, H ≤ 512
P ≤ 50000
X, Y ≤ 100000

Input

The first line will have an integer T, which is the number of cases for the problem. The next line has an integer D, which is the number of sprite definitions. D sprite bitmask definitions follow. Each sprite bitmask definition starts with a line with two integers W, H, which are the width and height of the sprite followed by H lines of length W of 0’s or 1’s. T test cases follow. Each case starts with an integer P, which is the number of sprite positions in the test. P lines follow and each line has 3 integers: I, X, Y, where I is the sprite identifier (from 0 to D-1), and X, Y are the coordinates of the sprite.

The (0,0) coordinate is the top-left corner of the display and sprites.
Output

For each case, there should be a line starting with “Case #x: ” followed by the number of collisions for that test case.

Resolution code: https://github.com/botmakerdvd/code_challenge_2021/blob/master/9/9.py

In this case, the algorithm behind detection of collissions was not very difficult, the difficult part of this challenge was to optimice and speed up the code so when you can discard that there will not be more collisions.

Challenge 10 – Packets delivery

We’ve discovered a security hole in the enemy communication system and we need your help to move forward.

Thanks to our secret agent, we found out the enemy was using a quite exotic physical transport layer described in the experimental RFC 1149. However, you don’t need to be an expert in that RFC, since we’ve already been able to do a MITM attack on the communication system (with a shotgun) and extract the packets.

What do we need from you? Because we’ve heard you’re a forensics expert, we need you to extract the information from the intercepted packets. You can download them from this URL: ICMPs pcap.

The test and submission passwords are the same.
Input
No input needed
Output

The password hidden on the pcap file

Resolution code: https://github.com/botmakerdvd/code_challenge_2021/blob/master/10/10.py

This is the 2nd challenge that involves hacking/reversing. Initially I readed ID from ICMP layer of each frame, translate it to ASCII character and it tells to reorder the frames so that is what i did.

Then I read the load of ICMP layer and reorder them based on ICMP sequence number.

I detected that it was a PNG image due to the PNG in header so I opened it … and a QR code appeared.

I decode de QR code on https://online-barcode-reader.inliteresearch.com and I got the KEY!

Challenge 11 – ALOT Another library of tools

Our team is writing a new JS utils library. The project has N functions. We want to split and distribute the functions in different files so every file exposes the same K number of functions. But we want to do it in a very specific way.

We have a linting tool that gives a score to our project and we want to maximize our score.

How is the score computed? The score of the project is the sum of the scores of its files.

How is the score for a file computed? The score for a file is the length of the longest common prefix of all the function names the file exposes. Let’s see an example. A file that exposes the following three functions – getHeight, getWidth and getDepth – will score 3 points, because their longest common prefix is “get”, which has three characters

However, a file that exposes the following functions – pairs, invert and invoke – will score no points because the names have no common prefix.

So given a set of function names and K, the number of functions a file should contain, what would be the maximum score possible by spreading the functions into N/K files, with K functions in each file?

Note that you don’t need to say which functions go into which files. You just need to know the score they would have.
Input

The first line will have an integer T, which is the number of cases for the problem. It is followed by a description of T cases. Every case has a line with two integers N and K. There are N lines following that each have a function name as a string.
Output

For each case, there should be a line starting with “Case #x: y”, where x is the test case number (starting with 1) and y is the maximum score that can be achieved.
Limits

T = 100
1 ≤ K ≤ N ≤ 1000
N mod K == 0
function names length ≤ 50

Resolution code: https://github.com/botmakerdvd/code_challenge_2021/blob/master/11/11.py

The algorithm here is quite simple, and using sorted lists in python is easy to solve this challenge

Challenge 12 – The crypto bubble

We all know that cryptocurrencies is a market that is growing exponentially. That’s why your friend Jonathan got the idea of trying to scrape several crypto trading websites to find a bug he can profit from.

His idea is to find out whether you can increase the amount of the coins you initially invested by exchanging different cryptocurrencies between different websites. Your friend Jonathan is a very good programmer, but algorithms aren’t his strong suit. That’s why he’s asking for your help.

He agrees to create a file with all the cryptocurrency exchange information from the different websites. And he’s asking you to develop an algorithm to figure out whether it’s possible to get rich by exchanging coins.

Jonathan only has one BTC and he wants to get more. Exchanges must start and end in BTC, but any other cryptocurrency can be used in the intermediate steps. Exchanging a cryptocurrency can take a very long time, so you should try to do as few exchanges as possible. If there are multiple paths with the same number of exchanges, you should choose the most profitable one. In other words, you need to find the shortest exchange loop that gives you more bitcoin than when you started even if another longer loop may be more profitable.
Input

After some tough negotiating you reach an agreement on what the file format will be like.

The first line has the number N of different cases
The N cases start after that line:
Each case starts with a number M, which is the number of websites in the case.
Then the websites datai starts:
Each website data block starts with a line that has the website name (a string of characters without white space) and K (the number of available trades).
The K available trades are described after the name.
Each trade is declared on one line with the crypto acronym followed by a dash then an integer D, another dash and finally the other crypto acronym.
An example trade line would be: BTC-2-ETH
What does a trade line mean? In the example above one BTC is exchanged for two ETH. But it doesn’t mean two ETH can be exchanged for one BTC.

Output

For each case, there should be a line starting with “Case #N: Z”, where N is the case number and Z is a number. Z must be the final amount of BTC you end up with after doing one iteration on the chosen path. If there are no paths that generate a profit the final amount must be the starting amount, in this case “1”.

Resolution code: https://github.com/botmakerdvd/code_challenge_2021/blob/master/12/12.py

Graphs theory appears again here and with Python library networkx it is easier to solve this.

Initially all conversion paths are added as edges when they have a good change rate (not 0)

Then, all paths from BTC to BTC are found and they are included into a list and then sorted by its length.

Finnally the winning on each of those paths is calculated and once you have one with a winning > 1 the program can end.

Challenge 13 – Find the New Earth

— So, where are we going now, Captain? — asked the young soldier.
— You know where, answered Adama. Let’s go to our New Earth.
— Yes, Sir. But what are the coordinates?

After a long fight, Battlestar Galactica and its crew deserve to reach New Earth, the new home they’ve chosen for themselves. And to get there, all they need is the position. The coordinates (15 numbers in a row) are somehow hidden here. But the only hint they have is this:

plyba:xvyy_nyy_uhznaf

Will you help the young soldiers find the coordinates so they can reach New Earth?
Input
No input needed
Output

A 15 digit string of numbers

Example:

123456789012345

Resolution code: https://github.com/botmakerdvd/code_challenge_2021/blob/master/13/13.py

Another hacking challenge.

I entered uhznaf to text in google and the second result speaks about ROT13 so I enter plyba:xvyy_nyy_uhznaf into https://codebeautify.org/rot13-to-text-converter and I got

cylon:kill_all_humans

with this user and password I could enter into website, and I download a file which the I unzip.

Finally a little code here to convert that file into a 15 numbers string

One Comment

Leave a Reply to Participación en el Telefonica Code Challenge 2021 – David Esteban Muñoz Cancel reply

Your email address will not be published. Required fields are marked *