Cthulhi in the bank: how we solved ICFPC 2015
A small report on how we solved the ICFP Contest 2015 . We participated in this competition for the first time, but the result was pretty good. You can search us in the table of intermediate results under the name "WILD BASHKORT MAGES". The final results are expected in the next few weeks, when the organizers will test all solutions on the full test suite.
This year, as a task, it was proposed to write a solver (or AI, as it is more convenient for someone) for the hexagonal tetris. Just like in the usual Tetris - we put the figures, remove the filled lines, get points for it. The solution should work for different sizes of the playing field and stacked figures of arbitrary configuration. Action commands with figures (movements and turns) are encoded with ordinary characters, as a result the decision is a string of commands. For special secret sequences of characters in the decision string, called power words, additional bonus points are given. In the story - these lines were called davar , and the organizers collected it in order to delay the awakening of Cthulhu.
There were three of us in the team, except for two cats - Damir, Maxim and me. Damir and I are retired olympiadists; Maxim has a lot of experience in writing compilers. As a preliminary preparation, we raised a git-repository, read some information about cryptography (because it was mentioned for some reason in the announcement ), I checked that my Ubuntu was working on a virtual machine (I'm a Windows host, unlike teammates). And, of course, we slept well before the performance.
')
Although the competition lasted for three days, in this narrative everything will be divided into 4 days in connection with our time zone. In our local time, the contest began on Friday at 17:00, ending on Monday at 17:00. That is, day 1 and day 4 will be slightly curtailed, which in the end will give exactly three days. The time in the narrative is approximate, nobody recorded it specifically, it was restored from the git repository.
If you do not want to delve into the technical subtleties - you can safely skip, if you are interested in the implementation details, it will be easier to find them. This whole thing was not hidden in spoilers because of the pictures, which still makes sense to catch a glimpse.
So, the contest started at 17:00. The guys have already gathered, I am still at work at this time, I am already going to leave. Before leaving, I ran through the condition of the problem . At first, it didn’t come to the point that it was a question of tetris, except that it was clear that we were dealing with a hexaconal field in which some units moved. “Is there a need to write an AI for a strategy?” - I thought. I approached the team at about 6:00 pm, looking on the way to the store for provisions and such a strategically important resource as coffee.
About an hour, we discuss the condition of the problem, Damir simultaneously writes a visualizer in Python. It is clear that Python may be too slow for a final solution, so I am starting to write basic operations with a field and figures in C ++.
Maxim decides to write the same thing, only on OCaml. It was supposed to go in several directions at once, and then weed out the obviously unpromising ones. And there was nothing special to do anything at the beginning of the contest. As a utopian option, you could then combine several heuristics in different languages, run everything on each test, and then choose the best option.
At about 19:30 the first version of the visualizer is ready, you can see what tests the organizers have prepared there. On the field in some of them strange messages are visible, aren’t it power words?
We also found it there:
In the meantime, I tinker with the execution of basic commands on the figures. Shifting something on a hexagonal grid can be easy, but turning it is not quite trivial.
The code had to be slightly patched, by 22:00 everything was tested, at the same time the function of inserting and positioning new figures on the field was added, as well as checking for intersection with the walls and occupied cells. Damir takes my code and rewrites it in Python to insert it into the visualizer. Maxim also rewrites my OCaml code for use in his version of the solution.
Dinner, as such, was not. Interrupted by sandwiches with sausage and tea / coffee without departing from jobs. Maksim remembered that there was a chicken in the fridge and it had to be cooked and eaten until it had deteriorated. But we decided that nothing would happen to her until the morning.
Midnight. Damir fastened the ability to play decisions to the visualizer: now you can feed him davar, and then follow the moves to keep track of what is happening on the board. True, so far we have no dawar, nothing to watch.
By 03:00, I added a code for finding all positions where you can stick a figure before “freezing”. Together with the sequence of commands that leads to this position. Maxim implemented all the basic operations on OCaml, fixing a couple of bugs in my code along the way. Damir added the ability to interactively control figures from the keyboard to the visualizer: now you can play this Tetris naturally! And save decisions.
Unfortunately, the game is not enough power - it's time to sleep. On this day we decided not to save on a dream.
We wake up around 11 o'clock in the morning. Morning coffee - and again for work.
Damir gets a library for working with JSON from the C ++ bins, I fasten it, add a pseudo-random number generator, stupid move choice heuristics (choose the one where the figure will end up below). And here it is - a solution that makes at least something is ready! There is a bit of testing, debugging and testing of qualification tests - and by 14:00 we have the first davar.
During this time, Damir also does not sit idle - pumps the visualizer, fixes bugs. Now it is possible to scroll back and forth decisions in it, including step by step. Maxim has been picking his OCaml solution all this time.
Dinner time. For dinner, the chicken is too lazy to cook, so we order two pizzas. Yes, and time, in fact, especially not - at 17:00 ends the so-called Lightning Division. This is a special nomination, in which decisions were made that were written in just a day, which solve something already without taking into account power-words. And I really wanted to send something there, especially since something was already on hand.
As soon as the first decisions were received, Maxim began to sort out the question “How is it possible to send davar and solutions at all?”, And Damir and I look at the visualizer what our stupid solver told us. In principle, it behaves quite adequately, it even gets some points. On some tests, there are amusing quantum tunnel effects for figures, in which the turning point is far from the actual figure:
By 3:45 pm, parallel with the absorption of pizza, I added a heuristic to the solution, which additionally takes into account the disappearing lines, Damir screwed up the command line according to the specification to my decision, Maxim wrote an automated sending of solutions directly to the server.
It's time to prepare the archive for the Lightning Division. Maxim writes Makefile and README, collects tarball. Damir and I are reviewing davar, obtained from the last decision. It seems to be no particular errors, the tarball is compiled and tested, and at 16:47 we send the archive to the server of the organizers along with the latest solutions.
Here Damir finds obviously inadequate davar. Starting from a certain moment, the decision begins to behave very strangely - to miss the holes and sculpt the figures to the ceiling. And this ugliness happens after the two adjacent lines are completely filled and deleted! Almost immediately it became clear that this is nothing more than a bug in my C ++ code in the place where the deletion of the filled lines occurs. That is, in the visualizer, it deletes all the lines correctly, but in my implementation one of the lines remains - hence the desynchronization.
Then everything happens as in Hollywood cinema (approximate timings):
Wow, had time! 3 seconds before the deadline. Moral: the use of unfamiliar tools can create problems out of the blue, at the crucial moment.
A little later, we still asked the organizers whether we had time or not. The answer came:
Well, one of the most tense moments behind, it's time to come up with a normal solution. For example, which takes into account the use of power-word. In fact, the idea was already in the air for a long time, almost in the first hours of the contest, but we decided to develop it after the Lightning round - for him the use of power-words was not necessary. We sat down for an hour, formalized the idea, and the result was the following:
Somewhere by 19:00 the decision was formalized, it remains only to write it. Damir sat down to write a finite state machine, and I write dynamics itself (more precisely, most of the time was spent on registering the limitations that the state of dynamics gives us). Maxim continues to pick his OCaml implementation.
By 20:45, Damir appends the automaton, and a couple of minutes later I finish the dynamics. Merge code, see what happened. It turned out Stack Overflow. Well, I nakosyachil somewhere in the dynamics, so it cycles. It took quite a lot of time to search for the bug (it turned out to be a silly typo). After that, I started to run all sorts of tests and check that the solution does not fall anywhere else. I make commit with the corrected decision at 23:45 with davar for test 0. We send it to the server ... and we leave on the first line on this test!
At this time we change the name of the team. In fact, initially we were called “Team Bashkortostan ” . And when they came out on the first line of test 0, they thought that the name was somehow non-creative. Renamed to "WILD BASHKORT MAGES". They remembered the chicken, thinking what to do with it. We decided: if we do not throw it away tomorrow, then we throw it out the day after tomorrow.
While I was stupid with searching for a bug in dynamics, Damir didn’t sit idle: I twirled the construction of the machine a little, added support for power-words to the visualizer, wrote a module for counting the number of points that should be given for davar (this module was further used as in the visualizer, and from the outside for automatic scoring and generation of tablets for comparison). There is no place to work with a visualizer more comfortable:
Maxim continued to mess with his OCaml solution until the moment when we sent davar of test 0 to the server. After that, he made a volitional decision to score on his development and focus on testing solutions (in order to keep track of whether we had broken the solution after some “improvements”), as well as searching for new power-words. Not to say that writing a solution on OCaml was a big waste of time - rather, it was an insurance in case I blunted with my C ++ solution.
Somewhere at 00:15 I added another heuristic to the evaluation function. Namely - fines for creating “holes” in the filled part of the field. The essence of heuristics is very simple: we consider the number of such neighboring cells that one of them is filled and the other is empty. Then the lonely “hole” left on the field gives a penalty of 6. After this, the decision began to work much better.
Although the solution for test 0 was good, there were some difficulties with other tests. The fact is that the current solution was inhibited . For test 14, it worked 3 hours. Funny point: I actually wanted to launch a solution for test 13, which is much smaller in size and only 100 turns (and test 14 is the pentagram in the picture above with 500 moves), but I confused the numbers of tests a little. Well, I sit waiting for it to count. And it all does not count. After half an hour of the program, it has become a matter of principle to wait for completion. And an hour after launch, it finally came to the conclusion that I had launched 14 tests, and not 13. Apparently, fatigue had already affected. It counted only by 03:45.
While I was waiting for the end of the ill-fated 14th test (I didn’t have any strength left to expect but I didn’t fall asleep), Maxim drove some more tests with the correct solution and tried to send them to the server. They managed to check a couple, but the latter does not want to be checked. More precisely, it is not clear what is there with it - the table of results is simply not updated. In addition, for some of the tests that were already sent, the score in the results table and our own did not coincide a bit. Damir is looking for an error in the account evaluation module. Already sort of rechecked everything - there is no error. After this, the table of results completely falls - it turned out that someone sent an incorrect davar (bad davar, poor quality) to the server and thus broke the testing system. The organizers soon fixed the bug, restored the table, and told the participants not to send more bad davar:
The bug fix with the table happened around the same time when I had the 14th test. In the updated table, the score for each test coincided with our locally calculated - i.e. The bug was not with us and we were looking for it in vain.
They sent 14 tests and he also gave a very good result. After that, until 06:00, we were engaged in sending freshly considered davar, Maxim tried to check-search for new power-words with his hands. Unfortunately, no new ones were found, but all those words that were found in the tests (“Ei!”, “Ia! Ia!”, “R'lyeh” and “Yuggoth”) really turned out to be power-words.
The goal for tomorrow has become clear: to speed up the current decision. Fortunately, there was quite a lot of room for optimizations.
Woke up at about 15:30. Maxim woke up a little earlier and finally cooked a chicken. With potatoes. Just by the time we woke up with Damir. We had breakfast (although it was probably better to have lunch (or had dinner?)).
At 16:00 we return to our decision. It turned out that Damir did not sleep yesterday, and he didn’t go to bed at 6 am All this time he has optimized my solution. Carried out the calculation of the values ​​of the evaluation function in a separate procedure and cached (which greatly reduced the number of calculations of the same). ( std::map) int64. , power-. , - . , , .
, . . 17:00. 14 , 3 , 5 !
. «apocalypse_1».
, git . , , . , . , . git Dropbox , - 2 : «solution_%PROBLEM_ID%_%TAG%_%TAG_INDEX%.json» ( ). . : , , Dropbox « - » . !
Dropbox. - . i5, i3, — - . — . . , , , . , — ( ). Dropbox . No sooner said than done. , Dropbox . Beauty!
. . !
, , . : std::map - ( O( ), O( )). -, . , «» — power-. . 22:30 . - 14 3.
«» power-word'. :
. , , — power-word'. , , , , , . - , . , 4, 9, 13 23. 2 .
«Hack the pool» «Hack the loop». … «Hack the poop». , :
irc- « ?», . «WILD BASHKORT MAGES». — .
03:00. 2 . , , , . — , ! , - . , — . — .
4 . , , . , random seed, : «, ». : «, ». , - 3 . , 2 , . : .
2 , , 9. , , , , . - :
At the same time, it fell on 35 of the 400 possible moves. Unfortunately, Damir did not invent anything working that late evening.
Maxim collected all this time suspicious words and tested them for the fact that they are power-words. By 3:00 it was found either 6, or 8 such words (along with those 4 that we found earlier). In parallel, he launched our solution with more and more “magic” words found and sent the resulting davar to the server. Thus, 3 more apocalypses have passed, i.e. The last mass testing tag was "apocalypse_4".
3 ( - + + , ) (- ), , .
O( ) O( ) 5:00. — , 3 . , 3-4 .
- 9-10 , .
( ). «» , , . power-word' 10. :
, , . , «Yog-Sothoth» , . , «YogSothoth» ( !) power-word'! , . : «laundry», «the laundry». «ph'nglui mglw'nafh cthulhu r'lyeh wgah'nagl fhtagn.». «», - .
10 «» .
, ( ), .
: 3 , 9 ( - ), , , /seed' .
12:30 , 9: 110 400, 35, . , , 2 : , . , . README .
3 14:00. : , . , ( ), : , . «», . 10 «»: 10 .
, , 4 . random seed 200 200. :
14:40 . . . «panopticum», .
. (17:00) .
: , , ? , , ? , , + . . , — . - .
, , , . . 4, 6 24. , 4 6 , 3 . , 50 ( random seed) 150 200 . 3 , , , , 4 3 . 3 ! 24 : 1 , 1620 — 3 .
6 24 , 4 5 ( 10 ), , . No sooner said than done. . 16:00 ( ) . , , , 2 5 . , — . , 2 . 16:20 , . , int64, 64- , 32- .
, , . README , , ( - ).
— . Unagi .
(, , ), — .
( , ). / /. , 18 power-word' , .
, !
This year, as a task, it was proposed to write a solver (or AI, as it is more convenient for someone) for the hexagonal tetris. Just like in the usual Tetris - we put the figures, remove the filled lines, get points for it. The solution should work for different sizes of the playing field and stacked figures of arbitrary configuration. Action commands with figures (movements and turns) are encoded with ordinary characters, as a result the decision is a string of commands. For special secret sequences of characters in the decision string, called power words, additional bonus points are given. In the story - these lines were called davar , and the organizers collected it in order to delay the awakening of Cthulhu.
Introduction
There were three of us in the team, except for two cats - Damir, Maxim and me. Damir and I are retired olympiadists; Maxim has a lot of experience in writing compilers. As a preliminary preparation, we raised a git-repository, read some information about cryptography (because it was mentioned for some reason in the announcement ), I checked that my Ubuntu was working on a virtual machine (I'm a Windows host, unlike teammates). And, of course, we slept well before the performance.
')
Although the competition lasted for three days, in this narrative everything will be divided into 4 days in connection with our time zone. In our local time, the contest began on Friday at 17:00, ending on Monday at 17:00. That is, day 1 and day 4 will be slightly curtailed, which in the end will give exactly three days. The time in the narrative is approximate, nobody recorded it specifically, it was restored from the git repository.
| The technical details of our solution are highlighted in such a frame. |
If you do not want to delve into the technical subtleties - you can safely skip, if you are interested in the implementation details, it will be easier to find them. This whole thing was not hidden in spoilers because of the pictures, which still makes sense to catch a glimpse.
Day 1. Start
So, the contest started at 17:00. The guys have already gathered, I am still at work at this time, I am already going to leave. Before leaving, I ran through the condition of the problem . At first, it didn’t come to the point that it was a question of tetris, except that it was clear that we were dealing with a hexaconal field in which some units moved. “Is there a need to write an AI for a strategy?” - I thought. I approached the team at about 6:00 pm, looking on the way to the store for provisions and such a strategically important resource as coffee.
About an hour, we discuss the condition of the problem, Damir simultaneously writes a visualizer in Python. It is clear that Python may be too slow for a final solution, so I am starting to write basic operations with a field and figures in C ++.
Maxim decides to write the same thing, only on OCaml. It was supposed to go in several directions at once, and then weed out the obviously unpromising ones. And there was nothing special to do anything at the beginning of the contest. As a utopian option, you could then combine several heuristics in different languages, run everything on each test, and then choose the best option.
At about 19:30 the first version of the visualizer is ready, you can see what tests the organizers have prepared there. On the field in some of them strange messages are visible, aren’t it power words?
We also found it there:
In the meantime, I tinker with the execution of basic commands on the figures. Shifting something on a hexagonal grid can be easy, but turning it is not quite trivial.
In the end, after some hard work on a piece of paper and the analysis of cases, the following code came out:This is a very important feature. She shifts the point that she slipped on d cells in the direction of dir. After this, parallel shift operations become quite trivial, and turns are very easy to make. For this, for each cell in the figure, it is necessary to calculate its shifts relative to the point of rotation in two non-collinear directions, and then find the cell shifted relative to the point of rotation to the same displacements, only in slightly different directions:  |
The code had to be slightly patched, by 22:00 everything was tested, at the same time the function of inserting and positioning new figures on the field was added, as well as checking for intersection with the walls and occupied cells. Damir takes my code and rewrites it in Python to insert it into the visualizer. Maxim also rewrites my OCaml code for use in his version of the solution.
Dinner, as such, was not. Interrupted by sandwiches with sausage and tea / coffee without departing from jobs. Maksim remembered that there was a chicken in the fridge and it had to be cooked and eaten until it had deteriorated. But we decided that nothing would happen to her until the morning.
Midnight. Damir fastened the ability to play decisions to the visualizer: now you can feed him davar, and then follow the moves to keep track of what is happening on the board. True, so far we have no dawar, nothing to watch.
By 03:00, I added a code for finding all positions where you can stick a figure before “freezing”. Together with the sequence of commands that leads to this position. Maxim implemented all the basic operations on OCaml, fixing a couple of bugs in my code along the way. Damir added the ability to interactively control figures from the keyboard to the visualizer: now you can play this Tetris naturally! And save decisions.
Unfortunately, the game is not enough power - it's time to sleep. On this day we decided not to save on a dream.
Day 2. Episode 1: Lightning Division
We wake up around 11 o'clock in the morning. Morning coffee - and again for work.
Damir gets a library for working with JSON from the C ++ bins, I fasten it, add a pseudo-random number generator, stupid move choice heuristics (choose the one where the figure will end up below). And here it is - a solution that makes at least something is ready! There is a bit of testing, debugging and testing of qualification tests - and by 14:00 we have the first davar.
During this time, Damir also does not sit idle - pumps the visualizer, fixes bugs. Now it is possible to scroll back and forth decisions in it, including step by step. Maxim has been picking his OCaml solution all this time.
Dinner time. For dinner, the chicken is too lazy to cook, so we order two pizzas. Yes, and time, in fact, especially not - at 17:00 ends the so-called Lightning Division. This is a special nomination, in which decisions were made that were written in just a day, which solve something already without taking into account power-words. And I really wanted to send something there, especially since something was already on hand.
As soon as the first decisions were received, Maxim began to sort out the question “How is it possible to send davar and solutions at all?”, And Damir and I look at the visualizer what our stupid solver told us. In principle, it behaves quite adequately, it even gets some points. On some tests, there are amusing quantum tunnel effects for figures, in which the turning point is far from the actual figure:
By 3:45 pm, parallel with the absorption of pizza, I added a heuristic to the solution, which additionally takes into account the disappearing lines, Damir screwed up the command line according to the specification to my decision, Maxim wrote an automated sending of solutions directly to the server.
It's time to prepare the archive for the Lightning Division. Maxim writes Makefile and README, collects tarball. Damir and I are reviewing davar, obtained from the last decision. It seems to be no particular errors, the tarball is compiled and tested, and at 16:47 we send the archive to the server of the organizers along with the latest solutions.
Here Damir finds obviously inadequate davar. Starting from a certain moment, the decision begins to behave very strangely - to miss the holes and sculpt the figures to the ceiling. And this ugliness happens after the two adjacent lines are completely filled and deleted! Almost immediately it became clear that this is nothing more than a bug in my C ++ code in the place where the deletion of the filled lines occurs. That is, in the visualizer, it deletes all the lines correctly, but in my implementation one of the lines remains - hence the desynchronization.
Then everything happens as in Hollywood cinema (approximate timings):
16:50 I quickly, but accurately correct the bug, retesting all the tasks with the new version.
16:54 commits changes to git, Damir tries to pull away my corrections to check in the visualizer. But he made some changes and forgot to commit them when he parked, as a result, after pull'a, he gets some kind of porridge and we have to solve a terrible merge. Damir just sat on hg all his life, and didn’t get a git on his hand.
16:55 Maxim hurries to help Damir, realizes that he has some kind of tin there, hurries back to his computer. In the meantime, I’m running a problem test in my room - there’s no more glitches.
16:56 Maxim draws down my edits and quickly assembles a new tarball.
16:58 starts the script for sending the last solution to the server.
16:59 loads the tarball on the server, in the meantime I am watching the time here . In the script for sending dawar, we have a delay between separate tests so that we are not banned accidentally (it spoiled our nerves!), So sending slows down. The score is already in seconds: 5, 4, 3 ...
Wow, had time! 3 seconds before the deadline. Moral: the use of unfamiliar tools can create problems out of the blue, at the crucial moment.
A little later, we still asked the organizers whether we had time or not. The answer came:
<galois_kiniry> We see two tarballs submitted by your team, at 11:47 and 11:59. Both are well-formed.
<galois_kiniry> But is it a C ++? ;)
Day 2. Episode 2: Snakes, Cylinders and Finite Automaton
Well, one of the most tense moments behind, it's time to come up with a normal solution. For example, which takes into account the use of power-word. In fact, the idea was already in the air for a long time, almost in the first hours of the contest, but we decided to develop it after the Lightning round - for him the use of power-words was not necessary. We sat down for an hour, formalized the idea, and the result was the following:
| Let us somehow put the figure in the final position and “freeze”. You can come to this position in a very large number of ways - initially we can even smash our figure across the entire field by stuffing power-words before putting it in the right place. We can search for this optimal path using dynamic programming . We need to push all the information about the position of the figure into the state of dynamics. Namely: the position of the pivot point, the current turn, as well as information about which commands we have already entered to catch the appearance of new power-words in the sequence of commands. The finite automaton constructed as follows will perfectly cope with the second part of the state. Suppose we have n power-words, then the state of the automaton can be represented as a vector of length n, the i-th element of which denotes the length of the i-th power-word prefix, which we have already typed. Transitions between states occur when we add a new letter to the command line. At the same time, some prefixes already typed are extended by one; others are shortened or even reset to zero length. When power-word is typed completely, we also mark this information in the machine, and as the prefix we indicate the longest one that matches the suffix. An example of building an automaton can be seen in the picture below. Three words are used here: aba , acac and bc . On the edges are the characters that we are going to, the number of the word that we have just typed is indicated in brackets.  We have few power-words, there are not so many letters in them either, so the machine can be built head-on, not really worrying about the effectiveness of the solution - it will still be fast. With the first part of the state of the dynamics had to sweat. The fact is that when we move a figure to its destination, we cannot come to the same states. In total, we have 6 options for action with a figure: move it to the left, move it to the right, move it down-and-left, move it down-and-right, turn clockwise, turn counterclockwise. Everything is clear with “move down-and-left” and “move down-and-right” - as soon as we move the figure down, we can no longer drag it back up. Repetitions can be when we move the figure left and right in the same line and at the same time rotate. It turns out the next thing. All positions of the figures in the line can be represented as a rectangular table. Its width is the width of the field, and the height is the number of possible turns (1, 2, 3, or 6 depending on the symmetry of the figure). In this case, the upper side of the table is glued to the bottom - it turns out a kind of cylinder. And we move our cells from neighboring cells along the edge. As a result, all the moves on one line of the playing field can be represented as a snake, which crawls on our cylinder and tries not to bite off its tail:  Unfortunately, with this approach we would have to keep in a state of dynamics all the visited cells of each cylinder. In this case, the total number of states grows exponentially. We had to do something about it. We decided to limit the movement of the snake in the following way: if we left with a line, then we never visit it again. Then all sorts of snake paths degenerate into squiggles of the following form:  All already visited lines form a certain segment (a snake cannot teleport, say, through a line). Hence, in order to remember which lines we visited, we need a maximum of 36 states. Add one more parameter here: where we come from - left, right or top / bottom / c-another-line-playing-field - and this will be enough so that the snake itself does not chop off the tail. Of course, we will now go through far from all possible sequences of commands, and not all possible words we can then take into account. But, we drew all the potential power-words found so far and saw that only the word watermelon cannot be typed . We decided that while we manage without it. Total state of the dynamics: x, y // position of the figure, or rather its point of rotation In each state, we considered a weighted evaluation function according to three parameters: the evaluation of the playing field when we “freeze” the figure, the maximum length of the used power-word and the total length of all the words used. The second parameter was added for the future: so that it was possible to force the dynamics to choose a path with previously unused words (the organizers gave 300 points for each power-word if it occurs at least once and additional points (double the number of letters in the word) for each reiteration). The essence of the dynamics: for each state, we consider the maximum of the evaluation function, which we can get by making some moves from the current state to some “frozen” state. We try to do all sorts of moves, recursively process them, update the evaluation function if we have finished some words with the current move, select the maximum and save. A rather subtle point for reflection: it would seem that information about what words we ended up with comes from direct passage through recursion, but in fact all the necessary information is stored in the state of dynamics itself. Well, all the found words we consider in the reverse order of their end. Dynamics can be considered lazy with the use of memoization (well, finally, at least some hint of functionalism!). We simply start it from the initial position of the figure and ... freeze it, we calculate all the positions of the figure, where it can be “frozen”. If you add a symbol to each state that you need to go through to achieve the optimum, then you can easily restore the desired sequence of commands. |
Somewhere by 19:00 the decision was formalized, it remains only to write it. Damir sat down to write a finite state machine, and I write dynamics itself (more precisely, most of the time was spent on registering the limitations that the state of dynamics gives us). Maxim continues to pick his OCaml implementation.
By 20:45, Damir appends the automaton, and a couple of minutes later I finish the dynamics. Merge code, see what happened. It turned out Stack Overflow. Well, I nakosyachil somewhere in the dynamics, so it cycles. It took quite a lot of time to search for the bug (it turned out to be a silly typo). After that, I started to run all sorts of tests and check that the solution does not fall anywhere else. I make commit with the corrected decision at 23:45 with davar for test 0. We send it to the server ... and we leave on the first line on this test!
At this time we change the name of the team. In fact, initially we were called “Team Bashkortostan ” . And when they came out on the first line of test 0, they thought that the name was somehow non-creative. Renamed to "WILD BASHKORT MAGES". They remembered the chicken, thinking what to do with it. We decided: if we do not throw it away tomorrow, then we throw it out the day after tomorrow.
While I was stupid with searching for a bug in dynamics, Damir didn’t sit idle: I twirled the construction of the machine a little, added support for power-words to the visualizer, wrote a module for counting the number of points that should be given for davar (this module was further used as in the visualizer, and from the outside for automatic scoring and generation of tablets for comparison). There is no place to work with a visualizer more comfortable:
Maxim continued to mess with his OCaml solution until the moment when we sent davar of test 0 to the server. After that, he made a volitional decision to score on his development and focus on testing solutions (in order to keep track of whether we had broken the solution after some “improvements”), as well as searching for new power-words. Not to say that writing a solution on OCaml was a big waste of time - rather, it was an insurance in case I blunted with my C ++ solution.
Somewhere at 00:15 I added another heuristic to the evaluation function. Namely - fines for creating “holes” in the filled part of the field. The essence of heuristics is very simple: we consider the number of such neighboring cells that one of them is filled and the other is empty. Then the lonely “hole” left on the field gives a penalty of 6. After this, the decision began to work much better.
Although the solution for test 0 was good, there were some difficulties with other tests. The fact is that the current solution was inhibited . For test 14, it worked 3 hours. Funny point: I actually wanted to launch a solution for test 13, which is much smaller in size and only 100 turns (and test 14 is the pentagram in the picture above with 500 moves), but I confused the numbers of tests a little. Well, I sit waiting for it to count. And it all does not count. After half an hour of the program, it has become a matter of principle to wait for completion. And an hour after launch, it finally came to the conclusion that I had launched 14 tests, and not 13. Apparently, fatigue had already affected. It counted only by 03:45.
While I was waiting for the end of the ill-fated 14th test (I didn’t have any strength left to expect but I didn’t fall asleep), Maxim drove some more tests with the correct solution and tried to send them to the server. They managed to check a couple, but the latter does not want to be checked. More precisely, it is not clear what is there with it - the table of results is simply not updated. In addition, for some of the tests that were already sent, the score in the results table and our own did not coincide a bit. Damir is looking for an error in the account evaluation module. Already sort of rechecked everything - there is no error. After this, the table of results completely falls - it turned out that someone sent an incorrect davar (bad davar, poor quality) to the server and thus broke the testing system. The organizers soon fixed the bug, restored the table, and told the participants not to send more bad davar:
The bug fix with the table happened around the same time when I had the 14th test. In the updated table, the score for each test coincided with our locally calculated - i.e. The bug was not with us and we were looking for it in vain.
They sent 14 tests and he also gave a very good result. After that, until 06:00, we were engaged in sending freshly considered davar, Maxim tried to check-search for new power-words with his hands. Unfortunately, no new ones were found, but all those words that were found in the tests (“Ei!”, “Ia! Ia!”, “R'lyeh” and “Yuggoth”) really turned out to be power-words.
The goal for tomorrow has become clear: to speed up the current decision. Fortunately, there was quite a lot of room for optimizations.
Day 3. Optimization and improvements
Woke up at about 15:30. Maxim woke up a little earlier and finally cooked a chicken. With potatoes. Just by the time we woke up with Damir. We had breakfast (although it was probably better to have lunch (or had dinner?)).
At 16:00 we return to our decision. It turned out that Damir did not sleep yesterday, and he didn’t go to bed at 6 am All this time he has optimized my solution. Carried out the calculation of the values ​​of the evaluation function in a separate procedure and cached (which greatly reduced the number of calculations of the same). ( std::map) int64. , power-. , - . , , .
, . . 17:00. 14 , 3 , 5 !
. «apocalypse_1».
, git . , , . , . , . git Dropbox , - 2 : «solution_%PROBLEM_ID%_%TAG%_%TAG_INDEX%.json» ( ). . : , , Dropbox « - » . !
Dropbox. - . i5, i3, — - . — . . , , , . , — ( ). Dropbox . No sooner said than done. , Dropbox . Beauty!
. . !
, , . : std::map - ( O( ), O( )). -, . , «» — power-. . 22:30 . - 14 3.
«» power-word'. :
- , power.
- , .
- .
- , .
- «» .
. , , — power-word'. , , , , , . - , . , 4, 9, 13 23. 2 .
«Hack the pool» «Hack the loop». … «Hack the poop». , :
irc- « ?», . «WILD BASHKORT MAGES». — .
03:00. 2 . , , , . — , ! , - . , — . — .
- : : « , — ...». . : « , — ...». . , : « , !». , power-word'. « »: , - , , . |
4 . , , . , random seed, : «, ». : «, ». , - 3 . , 2 , . : .
2 , , 9. , , , , . - :
At the same time, it fell on 35 of the 400 possible moves. Unfortunately, Damir did not invent anything working that late evening.
Maxim collected all this time suspicious words and tested them for the fact that they are power-words. By 3:00 it was found either 6, or 8 such words (along with those 4 that we found earlier). In parallel, he launched our solution with more and more “magic” words found and sent the resulting davar to the server. Thus, 3 more apocalypses have passed, i.e. The last mass testing tag was "apocalypse_4".
3 ( - + + , ) (- ), , .
O( ) O( ) 5:00. — , 3 . , 3-4 .
4.
- 9-10 , .
( ). «» , , . power-word' 10. :
ei!
yuggoth
ia! ia!
r'lyeh
necronomicon
planet 10
monkeyboy
john bigboote
in his house at r'lyeh dead cthulhu waits dreaming.
yoyodyne
, , . , «Yog-Sothoth» , . , «YogSothoth» ( !) power-word'! , . : «laundry», «the laundry». «ph'nglui mglw'nafh cthulhu r'lyeh wgah'nagl fhtagn.». «», - .
10 «» .
, ( ), .
: 3 , 9 ( - ), , , /seed' .
12:30 , 9: 110 400, 35, . , , 2 : , . , . README .
3 14:00. : , . , ( ), : , . «», . 10 «»: 10 .
, , 4 . random seed 200 200. :
14:40 . . . «panopticum», .
. (17:00) .
: , , ? , , ? , , + . . , — . - .
, , , . . 4, 6 24. , 4 6 , 3 . , 50 ( random seed) 150 200 . 3 , , , , 4 3 . 3 ! 24 : 1 , 1620 — 3 .
6 24 , 4 5 ( 10 ), , . No sooner said than done. . 16:00 ( ) . , , , 2 5 . , — . , 2 . 16:20 , . , int64, 64- , 32- .
, , . README , , ( - ).
Epilogue
— . Unagi .
(, , ), — .
( , ). / /. , 18 power-word' , .
, !
Source: https://habr.com/ru/post/264567/
All Articles