The first time we heard about the Apple Watch and the possibility to develop apps with the WatchKit we thought: “we’ll be creating a .Tuenti App for the Watch here sooner or later”.
We are a team that loves challenges and being challenged, so we started to play and develop with the new WatchKit SDK, and then we understood the importance of how .Tuenti on the Apple Watch could be useful for our customers.
Juanma Jiménez, Alejandro Velasco, Wiljan Arias and I were very enthusiastic about the idea of creating a simple and useful app. We knew the Apple Watch users would interact with the device just for a few seconds, so any information on the screen should be always accessible in a quick and easy way. For a first version of .Tuenti, bringing all the mobile account information to the Apple Watch met our requirements, for example to solve a use case such as having updated information from VozDigital minutes, data, or the expiration day of your tariff. All this information would be available on your wrist.
Besides the .Tuenti Apple Watch App, we have created a Glance. A Glance is a supplementary way for the user to view relevant information from the app. We designed and implemented the Glance in a way customers could have a look at the account information quickly in just one screen.
The Apple Watch will be available in Spain and Mexico on June 26th, and we can say that .Tuenti would be already available for our customers.
For sure we will continue bringing more functionalities to the Apple Watch. Apple just announced a new watchOS 2 on the WWDC 2015 and we are currently investigating how we can integrate with Apple Watch more closely here at .Tuenti. For us, for you, this is just the beginning...
You can already download the app on the App Store.
All good things must come to an end. The final phase of this edition of our programming contest has finalized today at our Madrid office far exceeding our expectations. But it couldn’t be any other way, considering that this was the most difficult of the five so far.
The 10 Tuenti Challenge 5 finalists came in yesterday to meet the team, so we received them by celebrating with a barbecue at our CTO’s home, as is the Tuenti style.
In spite of not having finished the 20 problems that we initially posed in the first phase, they are the top 10 challengers, those that have solved the largest number of problems and with better code quality. As expected, we were impressed by the technical quality of the workshops and interviews we shared with them all throughout the day. The formative workshops were:
As a finishing touch to this meeting with our finalists, they received different prizes. And as of just a few minutes ago, we have announced the final ranking. The podium is taken by:
The following are the rest of the participants who also reached this second phase:
We have been left speechless. This edition has been enormous and we are extremely grateful to the more than 2,300 registered participants, the almost 900 participants that solved at least one problem, the top 50, the top 10, and the champions for having made all of this possible. Thank you very much from everybody on the Tuenti engineering team! And to all of those who didn’t make it to our office today, we hope to see you next year. See you at the #TuentiChallenge6, mates!
604,800 seconds, 226,246 lines of code —this is more than a new line every 3 seconds—, 2,342 participants, 2,395 problems solved —nearly a hundred lines per participant, and per solved problem too!—, 1,687 problems solved correctly… but you want more details.
839 people passed the first challenge, but only 1 made it to the 19th one. Nobody was able to solve the last 2 problems during the contest this year, making it probably the toughtest one so far. There were three stoppers —problems with less solvers that the next one—. Kudos to you if you were one of the participants that didn’t hit the skip button when you faced challenges 12, 13 and 15.
The number of correctly solved problems is not as big as the amount of solved problems, since most problems included several incorrect solutions. The problems with the biggest fail rate were challenges 12, 11 and 17 (this last one only had 2 submissions).
The average time to solve each problem varies from nearly 2.5 hours (problem 18), to nearly 29 hours (problem 17). The average time invested per problem has been around 12.5 hours.
Most used ones can be seen here, but in total 28 different programming languages were used to solve, at least, one problem. The languages used to solve just one problem were AutoIt, AWK, Lua, OCaml, Pascal, TCL and even the esoteric language Aheui.
Not all languages were equally popular as the challenge evolved, as you can see in the following graph:
The shortest code —not considering those oneliners in problems that just echoed the solution— is a solution to the first problem in 2 lines of Python. The largest solution has a total number of 3396 lines of C# code, to solve problem 3, including external code that adds support for bignums.
Here they are the total number of lines by each language.
Out of the 28 programming languages, only 12 were used by the 50 winners of the first phase.
If you didn’t make it this year, you may want to upgrade your tool belt with some new fancy languages from this set!
An interesting metric to measure the efficiency of a language is the number of lines needed to solve a task. As this may vary largely due to both problems and solvers, we have measured this metric among the top 50 winners. You can see both total number of lines per language and the average lines of code per solution and language.
The first time I saw this problem I loved it. It was one year ago while we were preparing the Tuenti Challenge 4, proposing different problems for it and Jorge told me his idea. I didn’t even know about the existence of Glagol or the RANDU algorithm, and that gave even more points to the problem, but last year we already had 20 problems for the Challenge, so I decided to recover it this year.
The problem tells us the story of a man who owes a lot of money to Teddy KGB, part of the well-known Russian mob. This man has a privileged information: he has a photo of the algorithm that a Russian casino uses in order to shuffle cards in a blackjack game machine. The algorithm itself is written in Glagol and your mission is to win enough money at that casino in order to pay the money you owe.
Glagol is a programming language based on Pascal and Oberon that uses Russian keywords and its code is written in Cyrillic alphabet. It’s a bit difficult to find detailed information about it, you can find some wiki pages about it here and there and all of them link to the official site hosted on a free Russian hosting, but when you try to visit it you discover that the page is no longer accessible. Same happens with forums about it, and after investigating for a while you can discover that the forum was hacked some time ago by some hackers (looks like the war between Russian-based programming languages is pretty serious). Thank God, we have the archive.org and you can find there a snapshot of the official page from few years ago. So now that you can read the program on the photo, you need to understand the algorithm.
The shuffling algorithm implemented in Glagol uses RANDU as the random number generator, and it also imports randomize function from some TurboPascal library. If you search for some information about RANDU, you’ll find that it’s a very bad random number generator, it can be defined as:
Vj+1 = 65539 · Vj mod 231
The first important thing to notice here is that the first number that RANDU generates is the seed itself.
The second thing to notice in the problem is that the machine that runs the game reboots once a day, and it reproduces the Windows 2000 boot sound when it boots. So probably the randomize() function may take its value from GetTickCount function in Windows, which is the number of milliseconds since machine boot, and rebooting once a day it will have a maximum value of 86,400,000. So you only can have 86,400,000 deck shuffles in this game machine (which is way less than the 52! possible forms of shuffling a Poker Deck: that number has more than 60 digits).
Having all that data gathered we can start solving the problem. We want to win money, so we want to win our bets. It doesn’t matter if we lose some hand if we don’t bet hard on that one, what we need is to know which hands we’ll win, so we can bet on those, and for that we have to know how that deck is shuffled. In order to know how the hand is shuffled, you need to know the seed, i.e., the number of milliseconds since that machine has started, but you can’t know that; the only knowledge you have is about the cards you are given, and you also know that it takes only 2 minutes (120,000 milliseconds) between different plays.
So let’s suppose that the dealer gives us these cards: 4♠-A♠. We want to know which seed could generate that first hand, so we have to shuffle the deck in all possible ways (in a day, of course, 86,400,000) and check out there. In this case, there are 134,440 different seeds which deck’s shufflings begin with those cards.
Next play starts exactly 120,000 milliseconds after the first one (after one of the 134,440 ones that start with 4♠-A♠) and the dealer gives us the next hand: K♣-5♠. From all those first 134,440 possible hands generated by their seeds, if we sum 120,000 to the seed there are only 41 hands that start with K♣-5♠. If we make the same with the third play, we’ll find that only one seed generates the three hands (with 120,000 offsets, of course) and it is 288 (288 is always the answer, you know what I’m talking about).
You’ve just identified the seed of this machine and you can play on it safely because you know when to bet, as you know, for example, that the fifth hand (which is the solution to this test case) that the dealer will give you will be the 7♣-9♠.
On the other hand, if the hands that the dealer gives to you are 10♦-7♥, 7♥-9♣, 4♠-J♥ and A♣-J♥, you can check that there are 3422 seeds that generate decks that begin with those hands, so it makes no sense to keep playing on that machine and you should simply WITHDRAW and try your “luck” on another one.
As you can see, the problem itself is not how to play blackjack, you can find an algorithm on your favourite web, the only way to really win is to know which deck you’re playing with.
With all the information about what we want to do, it’s time to decide how we want to do it.
In this problem, you need to check if a sequence of different numbers matches a pattern, but you don’t need to regenerate the sequence each time, as the sequence generated by a seed is always the same, so it’s a pretty good idea to precalculate all possible sequences and just query it when you need it (also, you can reuse it for the different cases). Having that said, you may not want to store 24*60*60*1000 + 120000*4 decks of 52 elements each (4.5 * 10⁹ elements) in memory, 4.18 GB if each element is stored in a byte (we know that it can be compressed further), as you only need two elements of each deck for the comparison, reducing its memory footprint to only 165MB.
Once you have all the required info about the decks, you only need to iterate over the cases, seeds and rounds, just counting the coincidences and breaking the loop early when you are sure about the outcome. You may want to consider reducing the % (modulus), ** (power) and / operations in the deck shuffle, though, as they are some of the slowest operations and sometimes they can be switched with other operations.
Some days have passed and we have compiled some published solutions and write-ups of the challenge that we want to share with all of you. However, there are no write-ups of the problem 15, and we know that a lot of you are probably interested in reading an explanation on how to solve that problem, so we’ll publish a write-up of the problem on this same blog.
Stay tuned! ;)
Updated May 13th.