CV
This article can be read in English here.
Del 13 al 20 de diciembre de 2021, el Telefonica Code Challenge https://codechallenge.0x14.net (evolución del Tuenti Challenge) ocupó mis pocas horas libres.
Había intentado participar en los Tuenti Challenges en el pasado, pero siempre se me pasaba la fecha, o me pillaba en época de examenes, o de vacaciones en el extranjero. Esta vez, en cuanto me enteré me apunté por lo que esta es mi primera experiencia en un evento de este tipo.
El Challenge tuvo 20 retos de programación, algoritmia, reversing, hacking … Fui capaz de resolver los primeros 13. Fue una semana de alta carga en el trabajo y solo pude disponer de unas pocas horas a las tardes y noches por lo que estoy orgulloso de haber sido capaz de solventar esos 13 retos.
Quedé en la posición 49 tal y como se puede comprobar en https://codechallenge.0x14.net/Stats
Decidí participar en este Challenge utilizando Python. Echando un ojo a los resultados creo que fue una gran idea, la grandísima cantidad de librerías existentes para python y los tipos de dato (listas, diccionarios y tuplas) de este lenguaje fueron realmente muy útiles y me facilitaron el trabajo.
Para todo aquel que quiera probarse en este tipo de eventos, le recomiendo la web https://www.codingame.com/multiplayer/clashofcode
Todos los programas codificados por mi para este concurso están disponibles en https://github.com/botmakerdvd/code_challenge_2021
Dado que el concurso fue íntegro en inglés no voy a traducir los enunciados
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.
InputThe 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 ‘:’.
OutputFor 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
Este fue realmente sencillo, asi que vayamos al siguiente.
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.
InputThe 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.
OutputFor each case, there should be a line starting with “Case #x: ” followed by the result of the map without the Pokémon.
Limits1 ≤ 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
Este segundo, utilizando las listas de Python también resulto realmente sencillo.
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
En este caso, inicialmente se ha trasladado toda la información que se da sobre el valor de las letras a diccionarios.
Esto facilita mucho la segunda parte del programa ya que lo simplifica al extremo.
Se ha utilizado la librería Fraction, para evitar problemas de precisión realizando operaciones con 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.
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.
InputThe 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.
OutputFor 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
Resolví este desafío generando 2 diccionarios, uno para el siguiente tono de cada tono y otro para el siguiente semitono de cada tono.
Challenge 5 – Invictus
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
Este fue el primer reto de reversing/hacking . Utilizé un visor hexadecimal y descubrí que habia algo oculto en el Invictus.txt
Descubrí que utilizando caracteres ascii no imprimibles, se estaba ocultando información.
Por lo que parecia cada dato era una tupla de 4 bytes, con la información en el 3º y 4º byte.
Una vez que tuve dichos valores, descubrí que habia 2 tipos, unos con el valor 0x81 en el primer byte y otras que no.
Como sabía que la solución tenia que contener el nombre completo de NELSON ROLIHLAHLA MANDELA, descubrí que un cifrado por sustitución se había usado.
Fue facil de resolver buscando 3 valores que se repitiesen estando separados 2 elementos entre si, ya que eso serían las L de ROLIHLAHLA.
A continuación calculé la diferencia entre el valor ASCII de la letra L y el valor que yo tenía y aplicando esa diferencia resolví el problema.
O no… Finalmente descubrí que habia 2 tipos diferentes de sustitución, dependiendo del primer byte de cada valor, si el primer byte era 0x81 había que restar 110 al segundo, si no, 302.
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: slovakOutput
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
Utilizando locales y la libreria locale para Python, este reto fue muy sencillo.
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
InputNo input needed
OutputA 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
En este caso después de mucho leer, utilicé el algoritmo Dijkstra’s para resolverlo, integrando una librería telnet en mi código python. La explicación de este algoritmo se puede ver en 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.
OutputFor 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
Este reto fue muy sencillo de resolver utilizando Teoria de Grafos y la librería networkx. En la Teoría de Grafos las ciudades críticas se les llama puntos de articulación, y la librería networkx los encuentra facilmente.
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 ≤ 100000Input
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.
OutputFor 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
IEn este caso lo complicado no fue desarrollar el algoritmo de detección de colisiones, sino optimizarlo para que fuera más veloz sabiendo cuando podia parar de buscar colisiones.
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
OutputThe password hidden on the pcap file
Resolution code: https://github.com/botmakerdvd/code_challenge_2021/blob/master/10/10.py
Este es el 2º reto que involucra hacking/reversing.
Inicialmente al abrir la captura en whireshark observé que el campo ID se repetia bastante, por lo que cogí sus valores , los traduje a ASCII y obtuve una frase indicandome que reordenase los paquetes.
A continuación obtuve la carga de la capa ICMP y la ordené basandome en el numero de secuencia ICMP.
Detecté que era una imagen PNG ya que descubrí su cabecera por lo que al abrirlo con un visor de imágenes… apareció un QR.
Por último decodifiqué el QR code en https://online-barcode-reader.inliteresearch.com y obtuve la solución.
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.
InputThe 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.
OutputFor 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.
LimitsT = 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
Este algoritmo es bastante simple, y utilizando listas ordenadas en python, este reto es bastante asequible.
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.
InputAfter 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
De nuevo la Teoria de Grafos aparece por aquí, y de nuevo utilizo la librería networkx para resolver este problema.
Inicialmente todas las conversiones se añaden como vertices al grafo, siempre que tengan un tipo de cambio diferente de 0 claro.
A continuación se obtienen todos los caminos desde BTC a BTC y se incluyen en una lista. Lista que ordenamos basandonos en lo largo de cada camino.
Por último se calcula la ganancia en cada uno de esos caminos ordenados y una vez que obtienes una ganancia > 1, el programa termina.
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
OutputA 15 digit string of numbers
Example:
123456789012345
Resolution code: https://github.com/botmakerdvd/code_challenge_2021/blob/master/13/13.py
Otro reto de Hacking
Metí “uhznaf to text” en google y el segundo resultado hablaba sobre ROT13, por lo que introduje plyba:xvyy_nyy_uhznaf en https://codebeautify.org/rot13-to-text-converter y obtuve:
cylon:kill_all_humans
con este usuario y contraseña pude entrar al sitio web de donde descargué un fichero que descomprimí.
Finalmente un pequeño código convirtió ese fichero en el string de 15 números.
Sé el primero en comentar