An ace up in your sleeve

Publicado el 19/5/2015 por Oleg Zaytsev, Lead Engineer

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.

Introduction to the problem

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

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.

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).

Solving the problem

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.

Implementation considerations

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.

Credits

I’d like to give all the credits of the idea and the original development of this problem to Jorge Rodríguez, one of the winners of the first edition of the Tuenti Challenge, 4 years ago.

#TuentiChallenge5: Recopilation of solutions and write-ups

Publicado el 12/5/2015 por Daniel Pañeda, Software Engineer

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! ;)

Solutions

Writeups

Updated May 13th.

#TuentiChallenge5: First round!

Publicado el 06/5/2015 por Alfredo Beaumont, Senior Software Engineer

The first round of the fifth edition of Tuenti Challenge ended as scheduled on Monday at 13:37 hours. With 2342 registered people in this first phase, 893 people were able to solve at least one problem, after spending the whole week on them, and 617 people were able to solve, at least, one of them correctly. This year the challenges were pretty hard and no one was able to reach the final problem. You can see the full final ranking of the first round here.

The most used languages by the contestants of this edition were Python, C, Java and C++, as you can see in the graph.

Graph with rank of solutions per language

Tuenti Challenge is a competition for showing our technical skills and allowing people with technical interests to have a good time while giving visibility to Tuenti as a company that is firmly based on technology in order to find especially qualified individuals for our team. The problems are a combination of programming, security and ingenuity challenges.

To continue hacking or to complete any unfinished exercises, the webpage for the Challenge will remain available until next year ;) We would like to congratulate the 50 classified contenders and thank everyone for participating! Now, for the second round. This is becoming more and more exciting!

The #TuentiChallenge5 registration is open!

Publicado el 09/3/2015 por Daniel Pañeda and Alfredo Beaumont, Software Engineers

No more waiting. The fifth edition of the annual programming contest is finally here, Tuenti Challenge. Today we are opening the registration for participants to begin warming up by solving the problems and overcoming the challenges from previous editions.

The contest, like every year, will consist of 2 phases: The first phase, which will last from the 27th of April to the 4th of May, is on-line and the participants will have to solve the 20 problems posed by Tuenti's engineering team. The 50 finalists from this phase will be those that solve the greatest number of posed challenges in the shortest amount of time. The responses from the 50 initial winners will be manually reviewed by Tuenti's engineering team, who will take into account variables such as the chosen algorithm or the clarity and quality of the implemented code.

The second phase which will take place on the 28th and 29th of May at Tuenti's offices in Madrid, the 10 best participants from the first phase will have the opportunity of spending a day working directly with the team and participate in training sessions at the office. Also, they will all receive a prize and some of them will be offered a job.

Therefore, Tuenti Challengers, lets start writing code. Registration will begin today at 13.37 hours (GMT+1) and will remain open until the same hour on the 4th of May, at which moment the first phase of the contest will have been completed. All the information is available on the Tuenti Challenge 5 Website, contest.tuenti.net, as well as the legal rules of the contest.

Creating Apple Watch Apps: App, Glance and Notifications

Publicado el 05/3/2015 por Eduardo González, Mobile Apps Lead

Last Saturday we held another theEvnt workshop at Tuenti Offices. Víctor Corugedo, César Estébanez and Eduardo González (Tuenti iOS Team members) gave a complete workshop about WatchKit SDK and how to develop Apple Watch Apps.

Starting with a brief review about the Apple Watch and the internal device specifications, they continued presenting the Apple Watch development kit, the UI components already available to create apps and the internal framework architecture.

During the second part of the event, they configured a WatchKit project from scratch, dealing with common problems a developer will face once he decides to create a Watch app. Finally, they presented a toy project they were working on and explained how to create an Apple Watch App, a Glance and how to create custom interface notifications supported by the Watch.

If you could not attend for any reason, you can always check the slides and the project they used on the workshop.

We never stop and we are already preparing the next workshop. As usual, you can check all the updates in the workshops web, and follow theEvnt or the Tuenti Engineering accounts on Twitter.

Pages