Unexpected EOF
Какое-то время тому назад этот журнал сузился до постов про icfpc и дни рождения.

День рождения я в этом году не праздновал, т.к. на фоне войны настроение не праздничное.

Судя по тому, что творится в "топе ЖЖ" (зато теперь я знаю, где искать всех тех, кто рад нападению на Украину), закрытым кросспостам с других платформ и т.п., постов про icfpc тут тоже больше не будет. Если и буду писать, то в dreamwidth, ищите меня там.

(Read Comments |Comment on this)

ICFPC-2021: There is only one thing only I am interested in: bent figures
This is part two of the writeup, part one could be found here.

Day 3 (morning of Sunday)

Before we all went to sleep, our position on the leaderboard was 7th(!), but by morning (T+44h) we slipped to 14th

As before, Alex was the first to get up and by the time I had my morning coffee, he added an FPS counter to show the current speed of the solver and did some speedups for the solver code.

When coffee kicked in and brain fog lifted, I mentally went through the experience of manually solving the puzzles on the previous day.

In lots of the big ones figure looked like a big jumble of edge that would have to be "spread" to cover a relatively large hole. For example, here is Problem 125:



Our solver was of no help here, as it was also usually trying to bunch up all the free edges together. To aid in untangling the mess we made it so AWSD would move just the unfrozen nodes around. Now you would be able to "freeze" some of the nodes and move the rest away, rinse and repeat, and hope that tangle would start to look more intelligible and you would be able to "pin" it to the hole corners. It was still pretty hard manual work, but thankfully help was on the way.

At T+47h, Tom checked in implementation of "spring physics", in which edges that are too short would push nodes they are connected to, and edges that are too long would pull, and nodes would move around affected by these forces. "Spring physics" could be toggled on and off, and it greatly simplified the process of manual solving.

Sadly, other teams were going ahead full steam and we kept sliding down. By T+48h we were 19th.

Here is a quick demo of all the tools we had at this point based on problem 106. First I ask the solver to find me a unique edge from the figure that lines up with some hole edge. Them I run brute-force solved that places some neighbouring nodes for me. I freeze them, move the rest of the problem, and invoke several steps of "sprint physics" to untangle the problem a bit:



As you can see, movement is rather sluggish, and "sprint physics is not particularly fast either". Still, this enabled us to submit improved solutions to several problems. Despite that, by T+51h we were 18th, having gained back just one place.

At the end of the lightning round, organizers published the updated spec that added the concept of "bonuses" - special points that, if you were to cover them by the node in your solution, would grant you special powers for some other task. Special powers included: the ability to "break" any edge in half, the ability to have a single aggregate "elasticity budget" for your problem instead of an individual "elasticity limit" per edge or the ability to stretch a single edge without any limits at all.

We made a plot of the graph that showed which problems give bonuses to which other problems and realized that "has bonus for" relationship splits problems into three cycles of different sizes, where 1st problem will give bonuses for 2nd, which will give bonuses for 3rd, and so on, and Nth problem will give bonuses for the 1st.

So not only bonuses were hard to implement in our automatic solvers, but they also required us to temporarily sacrifice some points in a chosen single problem so that we could get the bonus, apply it to the next problem in the cycle and so on until we manage to close the cycle and recoup the points we sacrificed in the very beginning.

This sounded too complicated, plus we had lots of potential for improvement in lots of problems as it were, so we completely ignored the bonuses until the end of the contest (even though our solver is showing bonus nodes on screen).

By T+53h, Tom refactored and sped up "spring physics" and that was a game-changer. We were now able to drag nodes around with their neighbours following them, spring physics simulation was no longer glacial, and this led to a rather quick manual solution, especially for problems where the best score was zero (and so all hole corners were covered by nodes).

In the next video, you can see me solving problem 97 from scratch. I choose this problem because the initial figure is pretty spread out and you can readily see which nodes would go where, but even more, clumped-up problems were easily "spreadable" and then solved the same way.



Unfortunately, despite all this, by T+54.5h we were in 21st place. Evidently, other teams either had better solvers or used bonuses or both.

For the rest of the day, we were mostly solving puzzles with some cosmetic improvements to the solvers and visualizer. In particular, we solved 125 with a score of zero (remember, the lower the score the better):


I think that all of us called it a day by T+62h, give or take. We were in 19th place on the scoreboard, and I went to sleep thinking that surely tomorrow we will wake up to find ourselves in 45th place, or maybe even 100th

Day 3

Despite my fears, the next morning we were 25th, which I initially took to be good news, but then I realized that this probably means that getting extra points is getting harder and harder, and we probably have no chance of getting above 20th place.

My teammates kept solving the problems, and it looked like this is how the rest of the remaining time will be spent.

But on T+70h (two hours until the end of the context) Tom committed "optimizer", which will try to jiggle the points around their current position and will keep doing that as long as it improves the overall score.

All the solutions were pushed through that, and some of them were significantly improved (by 30%+). It seemed that unless we already had an optimal solution, the optimizer was able to squeeze some improvements out of what we had.

Tom also added "repulsion physics", where nodes behaved like the charged particles and repel their neighbours, which helped to untangle clumps that our solver oftentimes produced.

Unfortunately, soon after the optimizer was added scoreboard was frozen (1 hour till the end of the contest). Lots of our solutions were improved after that, but we no longer knew just by how much this improves our standing, which was 23rd at the time of the freeze. Nevertheless, optimization attempts were running all the way until the end, and the last solution was submitted 5 minutes before the deadline.

When organizers published final scoreboard, it became evident that these efforts paid off - we gained two places and finished 21st.

Our scoreboard standing vs time:


Conclusions

I rather enjoyed this ICFPC. The task was short and clean. The server-side infrastructure provided by organizers worked without a hitch (as far as I know). They even provided a very cute visual replay of your solution, complete with judges awarding you dislikes (picture taken from team "codingteam" writeup):



My teammates were amazing, and I secretly hope that next year they might be interested in teaming up together again. OCaml, I felt, was a decent choice as a language, and even the fact that we used graphics primitives library and not a UI toolkit did not hamper us that much.

I am happy with the 21st place we got, and while this is not the best result I personally hard, it is definitely far from the worst :)

See you all next year!

Links and resources

• Source code
  
• All videos from this writeup as a playlist
  
• other writeups
  

This entry was originally posted at https://dastapov.dreamwidth.org/132836.html. Please comment there using OpenID.

(Read Comments |Comment on this)

ICFPC-2021: You gotta know when to hold'em and when to fold'em
Gather round and settle down for the next instalment of the ICFPC write-ups.

ICFPC stands for ICFP Contest (and ICFP, in turn, stands for International Conference on Functional Programming), and I have been participating in them since early 2000s and writing up my adventures here. My most famous writeup (in Russian) about the best ICFPC so far -- 2006 -- could be found here.

TL;DR: This year, our team name was "Folding at home", there were three of us + my wife who solved a bunch of puzzles manually (but did not write code). We wrote an interactive computer-aided solver in OCaml and finished 36th in the Lightning Round and 21st in the Main Round. I liked this year's contest more than 2020 (but less than 2006 :). Puzzle was somewhat similar to the Origami puzzle from ICFPC-2016.

And if you want to know more than just TLDR, prepare for the wall of text :)

Day one

This year ICFPC started at 13:00 in my time zone. I was working but took a moment to check the contest website and saw that a)there is a nice, neat and rather small spec and b)there is a scoreboard! Excitement!

However, only at 18:30 I was able to sit down and read the spec.

It seems that all past ICFPCs could be roughly divided into two piles: "puzzle-solving" and "game bot writing". Last year was (mostly) "game bot writing", so it was only fitting that this year would be "puzzle-solving", which I secretly liked.

This year's puzzle went like this: you are given a planar figure that is drawn on the grid with integer coordinates. The figure consists of vertices lying on the grid intersections, and edges that connect some of the vertices.

You are also given a polygonal hole drawn on the same grid. Your task is to rearrange the figure so that it will fit inside the hole without any parts sticking out. To this end, you can rearrange vertices of the figure, making sure that edges that connect them roughly keep their length. I say "roughly" because edges have some "elasticity", and could be shrunk and stretched a little bit.

This is what has been the inspiration for the task:



Here is red figure drawn over the black hole:


And here is the same figure deformed so that it would fit into the hole:


Have you ever played "World of Goo"? Then you would have a really good intuition for how the figure would behave. If there are triangles or triangle meshes, they would be "rigid" and keep their shape. Any other part of the figure that forms a polygon with more than 3 sides would be freely twistable and deformable (provided that edge lengths allow it).

Obviously, for a sufficiently pliable figure, there would be many ways to fold it into the hole, so there is a scoring function that incentivizes you to cover all the corners of the hole (rather than, say, scrunch up your figure in a "ball" and set it in the middle of the hole).

I finished reading the spec (at T+6h) and got in touch with the rest of my team. Turned out that Tom is not feeling well, but will hopefully join us tomorrow. Alex though had been busy and wrote a visualizer that was able to show us both "figure" and "hole".

I don't remember who was the first to propose extending the visualizer into an interactive editor, but we both thought that this sounds like a good idea. We decided to make a module called "Pose" that would serve as the state that the interactive editor modifies. After a brief discussion of the API, I started to write Pose and Alex started to integrate it into the visualizer.

After several rounds of bug-fixing and API extension, we got something working around the T+8h mark. The editor would show you the figure and the hole, and you would be able to drag nodes around with the editor restricting your movements when you are trying to violate the elasticity limits of the edges.

We quickly realized that enforcement of the elasticity limits gets in the way: when a figure has lots of triangles, you will not be able to quickly move them about, instead, you would be forced to move each vertex one by one in small increments, which is very slow and infuriating.

So instead we allowed the user to move nodes around without any restrictions, but edges that violate elasticity limits would be coloured red, the redder the colour the more stretched (or compressed) is the edge. That was way better than before, and at T+9h we added the ability to save solutions to the file and tried to post them. At T+9.5h we scored our first points!

This is how our solved looked like (on problem 13):


For the next couple of hours, until T+12h, we have solved a bunch of problems by hand (which, surprisingly, got us to the 27th place) and discussed the next steps. One of the ideas we had was to exploit the fact that the figure has to be drawn of the grid with integer coordinates. There is only a limited number of ways to draw a segment of length L if the coordinates of its start and end have to be integer numbers. Alex extended the editor with the ability to draw circles that show you just how far you can stretch the edge and started to implement the beginnings of a solver based on this idea, and I kept solving the problems manually.

By T+13h I realized that a whole host of problems could be solved easier if you could shift the figure around and then "tuck in" the parts that stick out. The ability to move the figure around with "AWSD" was added and I solved a bunch of other problems this way. We moved to 20th place!

Here is how our (still fully manual) solver looked like at T+13h on problem 72:


At this point, I went to sleep, but Alex worked on solver up to T+15.5h. The idea was to allow the user to "freeze" the positions of a bunch of nodes, and then try and place all the remaining nodes in a way that does not violate elasticity constraints and does not put parts of the figure outside of the hole boundaries. To speed the search up, the solver would start with the nodes that have as many connections to "frozen" nodes as possible and will utilize the knowledge of the potential "integer" endpoint for each edge to limit the search even further.

We went to sleep, but other teams sadly did not. While we slept, we slid down to 39th place on the leaderboard.

Day 2

At T+20.5h, Alex was awake again and finished the solver that would perform the placement of the nodes without checking intersections with the hole. This would not allow us to solve problems without manual intervention yet. But we were able to display all the additional pieces of data precomputed for the solver, in particular - all the placement points for the node you are currently moving that will not violate the elasticity constraints of the edges connected to it.

This allowed us to manually solve a bunch of problems that had fiddly node placement, like problem 27:


By T+22 I was also awake and trying to speed up computations of "integer placements" for all edges. Our third teammate, Tom, also joined us and started to work on geometry primitives so that we would be able to implement "hole intersection" checks and make our solver respect hole boundaries.

By T+23.5 we had rudimentary geometry checking working, and added undo to the editor. Our position on the leaderboard was 42nd, and it was clear that there is no need to rush trying to solve more problems by the end of the Lightning Round.

By T+24.5h, we were on a roll. Our editor got a bunch of features: 1)ability to "snap" currently moved node to the closes hole corner, 2)solver that respects hole boundaries (with some minor issues), 3)ability to rotate figure by 90 degrees and reflect it relative to the line going through the centre of the hole and 4)ability to see solver progress in realtime and abort it, keeping current progress.

Features demonstrated on problem 1 (as you can see, solver avoids corners and edges of the hole):


Despite all the current flaws of the solver, we rose back to 29th place and kept slowly climbing. Alex and Tom were fixing the geometry bugs, I was solving problems for which we had no solutions yet and adding small bits to the editor (like a display of the score of the current solution state).

By T+26h I started to write the code that would try to pair edges of the hole with edges of the figure that could be perfectly placed to cover them. Geometry bugs were fixed, and solver improvements started to go in. We've changed the order in which the solver considers potential node placements to favour the spots on or near the yet-uncovered hole corners.

We also wrote the shell script which would wait for you to close the editor, and after checking that the new saved solution is better than the old one will submit it and commit it into the version control.

By T+28h the code that matches hole edges to figure edges was complete. Solved was also sped up in several ways. We went over a bunch of problems with bad solutions and improved them. By T+29.5h we were 25th.

The scoring model in the contest was giving the "perfect solution score" to each problem based on the number of nodes and edges in the figure and the number of corners in the hole. This perfect score was only available to those who managed to cover all the corners of the hole with nodes of the figure. Any other solution was penalized, proportional to the distance between uncovered hole corners and figure nodes nearest to them.

Organizers were publishing the score of the best solution found by all participants, per problem. If your solution had worse than the best, you received a percentage-based penalty. If your solution was 2x worse, you got about 75% of the points. If your solution was 10x worse, you were getting less than 10% of the points. It was therefore imperative to try and solve problems for the perfect score.

For a bunch of problems, the perfect score was zero, which mean that solution managed to cover all hole corners. We added a bunch of "quality of life" improvements to the editor (visual indicators for hole corners, ability to freeze all nodes, ability to zoom the problem and pan it around etc) and kept pushing for the perfect solutions on all medium and small problems.

This took a while, but by T+38h we were 7th!

This is how our solver looked at this stage, on problem 78:


To be continued in part two.

This entry was originally posted at https://dastapov.dreamwidth.org/132539.html. Please comment there using OpenID.

(Read Comments |Comment on this)

ICFPC-2020: Gravity is a habit that is hard to shake off
This is part three of the ICFPC-2020 write up. Part one is here.

Part two ended at T+35h when we managed to draw the first image extracted from interacting with galaxy.txt (and our team name is Just No Pathfinding, for reasons that would be explained later).

Alien message #39, "Interaction protocol", explained that every time you do "interact galaxy", you need to feed in a pair of numbers, and from reading discord we knew, that every time you got an image, you were supposed to "click" on it, and send click coordinates back, thus starting the next iteration cycle.

We made trivial UI, consisting of the single window with some debugging info splashed right across the bottom of the screen and rudimentary mouse support. We knew that interaction results in multiple images, and we are supposed to draw them on top of each other, so we chose different colors for each layer to be able to separate them visually.

After a bunch of small images were designed to test our ability to precisely click on pixels, we finally got to what should've been the "main screen" of the galaxy.txt.

This is how it looks like:



Unfortunately, organizers posted this image to their twitter some hours ago, spoiling the wonderful moment, but it was still an achievement.

We clicked on various items that display pictures of aliens (read wonderful writeup by tonsky to see a video of him exploring them)

This was an achievement that -- we sure -- would allow us to finally start scoring points and advance on the leaderboard.

Clicking on aliens sometimes led to some sort of mini-games the purpose of which was not clear. Two aliens led to the weird static pictures like this one:



Clicking on the center of the galaxy led you to some sort of mural, depicting the Galactic Tournament between civilizations, in which two ships face off and one of them advances to the next round and the other one dies:



Each stage of the tournament was clickable, displaying the "replay" of the battle between two ships, circling the weird square planet. Unfortunately, our evaluator really struggled with this part, taking 2-10 seconds per battle frame.

Still, we scored no points.

Going back to Discord, we realized that we should've paid more in the last 10 hours or so. Minigames were giving points during the lightning round (first 24h) only, so we were too late. Now points were awarded for driving the "ship" and competing against ships controlled by other teams.

To control the ship, you still had to send "alien messages", and you could do that either via your "galaxy UI", or by sending appropriate messages from any other program.

Since our galaxy interpreter was sometimes too slow, we decided to write a separate piece of code to drive the ship.

Protocol to drive the ship was only partially specified:



You were supposed to explore the "galaxy UI" to fill in the gaps in the protocol and figure out what the missing pieces are, and this is where we made our biggest blunder.

It was not a single big mistake, but rather a combination of several smaller ones.

1. We printed out information everything we sent to the server and everything we received but did not show it in the UI
   
2. Console logs were very verbose and noisy
   
3. We printed out "alien language" representation of the messages sent and received
   
4. We thought that we would be able to "reverse engineer" missing pieces of the protocol from interacting with the server.
   
5. Every screen of "galaxy UI" has some numeric glyphs on it. We did not have an image decoder, and we were not able to read them from memory
   
6. We were sad that lightning round is over and galaxy UI does not give you points anymore, and we wanted to be on the leaderboard.
   

Look at our logs. Can you easily see that newState, received from the server, is a tuple with numbers in it? Yeah, we neither.


Interact:
protocol: "galaxy"
state: ap (ap "cons" "3") (ap (ap "cons" (ap (ap "cons" "0") (ap (ap "cons" (ap (ap "cons" "0") (ap (ap "cons" "0") (ap (ap "cons" "0") (ap (ap "cons" "0") (ap (ap "cons" "0") (ap (ap "cons" "0") (ap (ap "cons" "0") (ap (ap "cons" "0") (ap (ap "cons" "0") "nil")))))))))) (ap (ap "cons" "nil") (ap (ap "cons" "0") "nil"))))) (ap (ap "cons" "0") (ap (ap "cons" "nil") "nil")))
vector: ap (ap "cons" "1") "0"
res = ap (ap "cons" "0") (ap (ap "cons" (ap (ap "cons" "3") (ap (ap "cons" (ap (ap "cons" "0") (ap (ap "cons" (ap (ap "cons" "0") (ap (ap "cons" "1") (ap (ap "cons" "0") (ap (ap "cons" "0") (ap (ap "cons" "2") (ap (ap "cons" "0") (ap (ap "cons" "0") (ap (ap "cons" "0") (ap (ap "cons" "0") "nil")))))))))) (ap (ap "cons" "nil") (ap (ap "cons" "0") "nil"))))) (ap (ap "cons" "0") (ap (ap "cons" "nil") "nil"))))) (ap (ap "cons" (ap (ap "cons" (ap (ap "cons" (ap (ap "cons" "1") "0")) "nil")) (ap (ap "cons" (ap (ap "cons" (ap (ap "cons" "0") "0")) (ap (ap "cons" (ap (ap "cons" "1") "0")) (ap (ap "cons" (ap (ap "cons" "2") "0")) (ap (ap "cons" (ap (ap "cons" "0") "1")) (ap (ap "cons" (ap (ap "cons" "2") "1")) (ap (ap "cons" (ap (ap "cons" "0") "2")) (ap (ap "cons" (ap (ap "cons" "1") "2")) (ap (ap "cons" (ap (ap "cons" "2") "2")) "nil"))))))))) (ap (ap "cons" (ap (ap "cons" (ap (ap "cons" "2") "-4")) (ap (ap "cons" (ap (ap "cons" "1") "-4")) (ap (ap "cons" (ap (ap "cons" "2") "-6")) (ap (ap "cons" (ap (ap "cons" "1") "-6")) (ap (ap "cons" (ap (ap "cons" "0") "-4")) (ap (ap "cons" (ap (ap "cons" "0") "-5")) "nil"))))))) "nil")))) "nil"))
flag = "0"
newState = ap ap cons 3 ap ap cons ap ap cons 0 ap ap cons ap ap cons 0 ap ap cons 1 ap ap cons 0 ap ap cons 0 ap ap cons 2 ap ap cons 0 ap ap cons 0 ap ap cons 0 ap ap cons 0 nil ap ap cons nil ap ap cons 0 nil ap ap cons 0 ap ap cons nil nil
pictures = (((1 0)) ((0 0) (1 0) (2 0) (0 1) (2 1) (0 2) (1 2) (2 2))
((2 -4) (1 -4) (2 -6) (1 -6) (0 -4) (0 -5)))
Shifting by 5, 7
waiting for click
clicked: (23,26) => (0,1)


As a result, we completely missed on the fact that mini-games in which you were supposed to control the ship use the same protocol as the one you are supposed to use to control the ship - complete with ship stats, commands that are issued when you click on "buttons" in the UI and so on.

If we played at least one ship tutorial mini-game with good debug output in front of our eyes, we would've noticed this, I am sure. But we did not.

Also, ship control tutorials unlocked "special abilities" that you could've activated via "JOIN GAME" message - like more efficient propulsion - and we completely missed this as well.

We were tired of alien glyphs and did not bother to decode "ship UI" in the tutorial mini-games, and moved straight to the ship control reverse-engineering.

Ship control protocol

Ship control protocol worked like this: you send the "JOIN GAME" message with the stats of your ship.

Stats are four integer numbers with undisclosed meanings, and the server could reject you if you request a non-sensical combination of stats.

The server responds with the "GAME STATE" message that describes whether you are the attacker or the defender, stats of all ships, and then in a loop, you send one of the available ship commands and receive new GAME STATE in return.

The attacker's goal is to kill the defender in the limited number of moves (255 or less).

The defender's goal is to survive until the end of the game or until the attacker dies, whichever comes first.

Ship commands included "accelerate", "shoot" and "detonate", and you could've sent more than one type of command per game tick -- so you can "accelerate" and "shoot" at the same time.

The battle is waged in the square field 255x255 units (there is no third dimension) in the middle of which there is a square planet, 32x32 units. If you crash into the planet, you die. Planet has gravity (attracts all ships).

You can fly out beyond the borders of the field, but you start to sustain damage (kinda like being outside of a safe zone in Fortnite/PUBG).

We started working on Ship Controller at T+46h (after some sleep).

By T+50h, we finally had something working. Something that could join the game and do nothing.
We submitted this version to the organizers and it even started winning some games for us.

The quick investigation had shown that those were the games where equally inept opponents managed to fall to the planet ahead of us.

Gravity is a contributing factor in nearly 73 percent of all accidents involving falling objects

We quickly realized that a weird square planet has equally weird gravity - each "side" of the planet exerted a pull on all points of space that was closer to it than to any other side. This effectively means that diagonals drawn through the square planet separated space into four regions in which vector of gravity was always oriented in the same way (and not directed to the center of the planet as we originally expected).

I marked gravity vectors on the picture below:



The first order of business was to figure out how to generate thrust to combat the pull of gravity and stop falling to our death.

Even though we messed up vectors and directions a couple of times, soon we got a ship that most of the time managed to avoid the fatal fall: battle replay, our ship is orange.

Pretty soon we got to a point where we were able to hover in the same position. That is, until we run out of fuel: again, we are orange

This is how we discovered that the first number in ship stats is the amount of fuel, and you can't have too much fuel: 200-250 seemed to be the max, or the server failed to let you into the game.

We also discovered that you can only generate 1 unit of trust - just enough to counteract gravity. But if you failed to engage your engines on the first turn of the game, you would've acquired a vector of speed directed towards the planet, and then your trust will be enough to counteract further acceleration, but will not be enough to stop you.

Now we started to win against opponents that did not steer at all (enough to get us to the 29th place), but started to discover that there is a more dangerous enemy out there: they shoot to kill.

Getting damage seemed to deplete your stats, mostly fuel, and eventually, your stats will reach zero and you will die.

Foretold is forewarned

We now had two ideas:

1. It would be nice to shoot back. We get the current position and velocity of the enemy ship, and we can compute gravity at its location. So we could precisely predict where he would be if it would decide not to accelerate. Shooting command just needed coordinates of the target. Seem easy.

2. It would be nice to conserve fuel. Just like we can predict the position of the enemy ship, we can predict the position of our ship (if we stop accelerating and will just coast). Moreover, we could extend this prediction arbitrary number of steps in the future, and thus compute how soon we will crash into the planet or run out of game zone bounds. If this number is large enough, we could stop accelerating and coast for a bit, saving fuel.

At T+56h, collision detection change was complete first. We marveled at the massive improvement in the test game played against ourselves: this time, we are both colors

We started "winning" even more, and for a while just sat back and watched games that were unfolded on the server, until we came across a shocking discovery: RGBTeam blew its ship ... and won the game, in which they were attacking and we were defending.

Ooookay. Two can play this game. I screenshotted the final state of the game, measured pixels, and computed that the "radius" of the blast was 10 pixels. Now, whenever we were attacking and found ourselves closer than 8 pixels from the enemy ship (just to be sure), we would blow up.

This would not happen too often, because we were not steering towards (or from) enemy ship, so we were just keeping an eye out for the game in which it will happen.

We still did not know what are the rest of the ship stats, so we resorted to playing games against the top of the leaderboard, which will allow us to observe their ship stats, and we copied them.

This way we discovered that more successful teams will have "attacker loadout" and "defender loadout", and we started doing the same.

Me, at T+58h in the team chat: "I think that tutorials in the Galaxy UI were probably telling you about ship capabilities, but who has time for that?"

Finally, we managed to find ourselves near the enemy ship and blew it up. As luck happened, it was the ship of RGBTeam. Revenge!

And then we had another match against "Cat is #1", where we detonated, and detonation covered their ship, but we did not blow them up.

I tried to estimate the amount of detonation damage from that one game (which was a mistake, as detonation damage fell off with distance, and depended on your ship configuration) and estimated that detonation yields 180-190 damage. We adjusted the detonation code to blow up only when the opposite ship is "weaker" than that.

Since we still haven't had the shooting code, we focused on developing something that would allow us to more reliably get the ship into the blast radius when attacking (and keep our distance when defending).

The solution that we quickly whipped out at T+59h was rather trivial: consider all 8 possible acceleration directions. Compute distance from the enemy ship right now and after the next move. When attacking, strive to reduce the distance. When defending, try to increase it.

This threw fuel efficiency out of the airlock, but we saw a clear improvement in our standings -- 23rd place.

New challenger appears

I already mentioned that the only contained data structure that alien language had was list/tuple. Game state contained a lot of information, including ship stats -- in a list. In our code, we split this list into two elements and called them our_ship and their_ship, to simplify coding.

Suddenly, at T+59.5h, we played a game on the server in which we ... timed out?!

Debug log ended with "assert failed: More than two ship?!"

Indeed, there seemed to be three ships in the last game state received. Alex set out to write a decoder of the last command submitted by enemy ship - it was part of the game state, but we never bothered to decode them before.

This yielded two improvements:

1)Now that we decoded enemy commands from the previous turn, we started to incorporate their thrust vector into our prediction code, which somewhat improved steering

2)We discovered undocumented command emitted by the enemy ship, which allowed you to "split off" part of the stats of your ship to create a new ship. The fourth number in the ship stats was clearly the number of "clones" you can make.

At T+60.5h, we were in a weird state. We knew how the ship splitting worked, but haven't incorporated it into our code. We had nice steering, but it was super inefficient and quite often we would run out of fuel and die. We still did not manage to start shooting back. Sometimes our steering code seemed to get into weird "fixpoint" and made us a sitting duck, like in this game here.

And yet, we were 19th on the leaderboard.

Our biggest worry was opponents that shoot us: despite our nice steering, we were unable to run sufficiently far away

At T+61h, we started to shoot back but somehow failed to inflict enough damage to kill the enemy.

Because we have so many issues that looked solvable and were quite tired, we made another mistake here: good move would be to print out as much stats about shooting as possible: our position, their positions, stats, commands, the damage inflicted, etc, and figure out why they seem to kill us and we are unable to.

Now I know that damage depends on the shooting direction, and it is best to shoot along the principal axis, or at 45 degrees to it. Also, shooting heats up the gun/ship, and you need to let it cool down, otherwise you will damage your own ship (which will look like rapidly decreasing fuel).

Instead, we concluded that guns are useless, disabled them, and moved to solve other better-understood problem.

We decided to ignore game information about 3rd, 4th, and subsequent ships. Our code still only knew our_ship and their_ship, we just stopped crashing if there are more than two ships in play.

Then, when defending, we started to split off ships with 1 fuel and other stats at 0 every time we were being hit: and it worked!

We improved steering code to better avoid enemy ship and game zone boundaries

We noticed that some teams just mirrored our commands, but were unable to think about the effective counter for that, and did see a way to employ this strategy ourselves.

At T+62, we noticed that we set the undocumented parameter in the "shoot" command at all times. Maybe this is "firepower"? We quickly confirmed that and started to cause some damage with our shots.

We quickly discovered, that shooting at every turn overheats your ship and causes catastrophic damage. There was ship stat that rapidly went up every time you shoot, and then slowly decreased down - by 10 units per tick if you coast, and by 2 units per tick if you under power. This was some sort of "heat" or something, and we tried to shoot with max power as often as we can, cooling down in between the shots, and risking the shots when we are not fully cooled down if the enemy ship was close to overheating.

Finally! Finally we started to land some damage. Not as much as enemy ships, but still.

At some point before T+62h, orgs amended the leaderboard to prank team "Cat is #1" - now their team name was displayed as "Cat is #N", where N was their position on the leaderboard :)

We also implemented "aggressive planet evasion mode" - if we found ourselves in less than 10 ticks from the projected crash into the planet, we will choose a side relative to the vector of movement ("left" or "right") that promises the quickest increase in the crash projection, and accelerate hard in that direction for several turns, achieving a close "flyby" of the planet instead of trying to push against the gravity.

Then we noticed the game in which our opponent seemingly split their ship into lots of ships in semi-stable orbits, which were really hard to shoot down: like this.

We quickly adopted the same strategy: if we were defending, and current planet crash projection was more than 100 ticks, we would split a "drone", and started to carry 10 drones when defending.

At T+68h, we changed our defensive loadout to have 100 potential drones, which greatly increased efficiency of this strategy.

We even had enough drones to win against enemies that were splitting their attacking ship to detonate all of them, trying to kill several of our drones at once.

Some enemies were really good at shooting down our drones, though. In this game we were just 3 ticks shy of winning as defenders, but they shot up all our ships.

Sometimes, though, we were lucky. In this game enemy splits their ship multiple time, but they all fly in lockstep, looking like a single point on the map. We managed to shoot and kill them all.

So in the end, our strategy was this:

- When attacking, start with 134 fuel, 64 guns, 10 coolers and 1 "ship"

- When defending, start with 158 fuel, no guns, 8 coolers and 100 "ships"

- Steer towards or away from the enemy ship, depending on the role, while avoiding the planet and going out of bounds of the game area.

- If no direction will move us closer to (or away from) our target, see if we can just coast for 100 turns. If not, correct in the direction that would avoid planet collision.

- If we hit the planet in the next 10 ticks, aggressively accelerate to achieve close flyby.

- Split off ships with 1 fuel when defending, if they have a chance to coast for at least 100 ticks

- Shoot when attacking, as long as we don't overheat. We did not know that direction matters, so we don't account for that

- When attacking, detonate if the opposing ship could be killed with 190 damage and is in range (again, we did not know the proper damage formula).

This allowed us to get 26th place on the final leaderboard, and the highest place we had during contest was 14th, in round 4.

In total, 95 teams were participating in the battles, of which only 65 scored some points.

Still, we scored better than some teams that I recognized: TDB, THIRTEEN, WILD BASHKORT MAGES, Skobochka.

All things considered, this is a solid win in my book.

Especially considering what we did not know or did not do:

- That blast damage rapidly decreases with distance

- That shooting damage depends on direction (remember the mysterious picture from the start of the post? That was the explanation of how shooting damage works)

- That is is possible to get 128 coolers by completing minigame in the Galaxy

- That it is possible to get x2 acceleration by completing minigame in the Galaxy

- That it was possible to figure out the meaning of all the ship stats AND observe ship splitting command in the tutorial missions in the Galaxy

- That there was a formula that describes the relationship between different ship stats and the max number you can have for each

- That ship stats defined detonation damage

- We only steered one ship and ignored all the enemy ships but first

What is in the name?

I promised to explain the team name. Before contest, we agreed that we don't want to solve yet another bot programming problem that devolves to finding the best routes on the map or in some search space with A* algorithm or something similar. Our commitment was so strong and we codified it in the team name :)

And here is why fictitious observatory was called Pegovka : пегий is an equine coat color, dark color with large white patches. Пеговка (Pegovka) is a traditional way to construct a village name from that word, very much like German "-ingen". Коурый is another equine coat color, somewhat reddish. Коуровка (Kourovka) is a very real observatory near Ekaterinburg, Russia

Word from the organizers

While we were programming ship battles, we largely ignored discord, and it seems that lots of other teams did so as well, so I have no interesting quotes from you.

However, after the contest others and I managed to speak with the organizers who said the following:



Participant: I feel sorry for the organizers who have clearly put in an immense amount of work and are now faced with all this negativity.

Organizer: but we probably deserve it for failing to meet expectations of so many people, experienced and new participants alike. That's the hard truth.

me: I really liked the contest, and I do think it is one of the best ever, but at the same time I am really sad about how the lightning part went. I think that small teams (esp. single-person teams) and those who did not participate on Discord since Jul 1 were at a huge disadvantage. Happy to explain


Organizer: actually, the whole pre-contest teaser thing was a result of a very worrying test. We kinda knew that the whole decoding thing was too hard for an average participant to crack in just 24hrs. So we decided to publish some messages in pre-contest teasers to give all participants some head start and a general idea of what we expect. We were sure that was not a big advantage to the teams that could participate in the pre-contest activities, because:
1. We carefully selected 15 messages that did not give out any idea of the task nature.
2. We tried to publish all the pre-contest "findings" in a neat organized way to be easily consumed by the new participants. "Condensed version" was intended to be self-sufficient (albeit mysterious and incomplete, as intended) problem specification. We probably failed that :-(
3. We did not require new participants to be familiar with any Haskell/Rust/Python code that was created before contest: all the new messages were published decoded, and having experience with the scripts gave no advantage. We did not expect anybody to adapt the scripts to decode new glyphs. We probably failed to communicate that.
4. We expected everyone to dedicate 1-2 hours before the contest to study everything already published. We failed to communicate that, because it felt so obvious :frowning: That was the most severe mistake probably.
5. We failed to realize that a chat of 500+ members trying to decode a large mass of messages will become an unmanageable mess. In hindsight, that should have been obvious.

Me: But at the same time:
- dockerized builds(future is here)
- organizers responding in the chat (almost unheard of)
- the infrastructure that remained up and stable throughout the contest
- the live scoreboard that updates without delay
- puzzle-like problem (i adore puzzle hunts -- and I think that if this was ran as puzzle hunt, it would've been awesome)
- hints in tutorials were really neat
- same for "replay battles"
- ability to run submissions locally
...
All of this was so go. SO GOOD. It was just awesome. It felt smooth, and effortless, and neat, and positively 21st century.

Organizer:
We also clinged too hard to the whole astronomer legend:

1. All the message images were generated exactly as if we generated them using the code written by the participants of pre-contest teasers.
2. We gave names to all the operators based on the suggestions from this chat. WHY DID YOU CALL BACKTICK OPERATOR ap?! Aliens even made it look like a backtick in images!! :-D
3. We did not disclose any internal knowledge that was not available to the "astronomer" or clearly stated by some participant in the chat. We pretended that our team of ICFPC organizers studied the message at a pace of an "average team" and published our results to help weaker teams to keep up and stay in the contest. That was a controversial desicion too: we got much hate because some teams spent tens of hours inventing a VM implementation only to see pseudocode published for everyone.

Many of the things we could communicate clearer just "broke the story" of "spoiled the lore", and you can blame this entirely on me, the mastermind of the whole Ivan Zaitsev character

Organizer: I think, in the end we designed a contest that would best fit an imaginary team that we strive to become...

Best played:
1. With a team of 4-5+ engineers.
2. With people that are ready to dedicate the entire 72 hours, each member sleeping only for 6-8 hours total during the contest.
3. For people considerably smarter than us.

We didn't intend it to turn out that way. But in the end it did :(


I can't begin to imagine how hard is it to organize and run ICFPC, and despite all my ranting, I am really happy that we got a chance to play with the novel idea, and not something that got done dozen of times before.

Code

If you want to see the code, it is here: https://github.com/adept/icfpc2020

Expect contest-qualify code :) This entry was originally posted at https://dastapov.dreamwidth.org/132184.html. Please comment there using OpenID.

(Read Comments |Comment on this)

ICFPC-2020: To boldly go ... where?
This is part two of the ICFPC-2020 write up. Part one is here.

(reminder that our team name was Just No Pathfinding, for reasons that would be explained later)

One particular message from aliens, #38, was rather long and convoluted. It mentioned "encoding" and "decoding" primitives, and another function that earlier was tentatively named "send", so the consensus was that message was describing some way to communicate with aliens.

Message #38


Believe it or not, but it was eventually decoded to mean this:

let f38 protocol (flag, newState, data) = if flag == 0
                then (modem newState, multipledraw data)
                else interact protocol (modem newState) (send data)

let interact protocol state vector = f38 protocol (protocol state vector)

As you can see, crowdsourcing on Discord eventually hit a wall with helper function here, which ended up being named "f38" even in the official docs :)


So, this is a way to apply some hitherto unknown function called "protocol" to some "state" and "vector" and results will either have to be "drawn" or "sent" to aliens. Separately, there were alien messages to explain that "drawing" is just plotting points defined by (X, Y):

Message #32, Drawing.
It shows (draw 1 1), (draw 1 2), (draw 2 5), etc



Finally, the last message we had, #42, means "interact = ....", where meaning of "galaxy" was unknown:



As I mentioned in the previous part, Alex wrote decoder and I wrote encoder for the data according to alien "specs". The only data supported were integers (positive and negative) and cons-encoded lists, so that [1,2,3] will be written as (cons 1 (cons 2 (cons 3 nil))).

I also mentioned that organizers provided REST API that supported one method: "/alien/send". You could send an encoded list "to the aliens" and receive encoded data back.

So far, we knew that aliens will respond to '(0)' with '(1, 81744)', where the second number will decrement over time, and would respond to pretty much anything else with '(0)'

Overall, that looked like a clock that probably counts down to the contest end. We had no other ideas and feeble attempts to send other messages to aliens were soon abandoned.

They were abandoned because finally, at T+4.5 hours the long-awaited HUGE MESSAGE from space had arrived.

It contained a definition for the 'galaxy'!

galaxy = :1338
:1338 = ap ap c ap ap b c ap ap c ap ap b c :1342 :1328 :1336
:1328 = 0
:1342 = ap ap b ap c ap ap b b ap ap b s ap ap b c ap c :1343 ...
...

Ok, FINALLY: some clarity.

We do need an interpreter for this language.

We don't seem to need a decoder for alien pictures. And we definitely don't need to produce alien pictures.

And once we have an interpreter for the alien language, we could "interact galaxy", and hopefully something new will happen afterward. But first, we will need an interpreter.

Alien language was clearly based on Lambda Calculus: minimalistic computation formalism that has just three constructs:

• Variables (and, in our case, numbers)
  
• Application of the function to its arguments : (f arg1 arg2 arg3 ...)
  
• Function definition (more formally called "lambda-abstraction"): (λx.BODY) or more conventionally (\x -> body) or (fun x -> body)
  

The alien language was even more minimalistic: they had a bunch of pre-defined functions like "add", "mul", "neg" etc, but no symbols for lambda abstraction (function definition).

So new functions were defined only via the composition of pre-defined functions given to us in alien images, which seemingly simplified things.

However, lambda-calculus itself is pretty far removed from anything that typical programmer encounters in the daily life, and due to its sheer simplicity, even most trivial things end up being quite obscure and non-intuitive (those who know lambda calculus could skip to the next occurrence of the word "ANYWAY").

For example, how do you define "true" and "false" in a language that has no built-in boolean type, and by default - no numbers? Well, OBVIOUSLY, you define them like this:

let true x y = x  (or λx. λy. x)
let false x y = y  (or  λx.  λy. y)

Because then, you see, you can define "and" like this:

and x y ifTrue ifFalse = x (y ifTrue ifFalse) ifFalse (or: λx.λy.λt.λf.x (y t f) f)

And will take two boolean values and two expressions to evaluate depending on the result of "and". You can check for yourself that supplying true/false values as defined above would yield expected results.

As you might imagine, things like lists, numbers, conditional execution, and conditional recursion require even more trickery due to the simplicity of the tools you have to work with. You can build higher-level primitives, and a good deal of theoretical articles explore the subject of what should those primitives be and what is the smallest number of them you need to have to semi-comfortably use lambda calculus for something resembling real-life computations. Those sets of primitives are called "combinator basis" as they allow you to build pretty much anything by combining lambdas.

Most famous basis is called S,K,I calculus, but there are others, for example B, C, K, W system.

We got "lucky" - alien messages described combinators S, K, I, B, and C and galaxy.txt used all of them.

ANYWAY, first attempt to write evaluator for galaxy.txt quickly displayed the tendency to go into endless loop, seemingly unable to deal with the value ":1141", one of the many recursive values to be found in galaxy.txt (here "ap" is a function application, (ap f x) is (f x)):

:1141 = ap ap c b ap ap s ap ap b c ap ap b ap b b ap eq 0 ap ap b ap c :1141 ap add -1

This was a clear sign that alien language has lazy evaluation semantics, where you don't rush to eagerly evaluate all the expressions that you have because some of them could be self-referential and you will end up expanding and evaluating them forever. Instead, you evaluate as little as necessary to compute the result.

Alex and I worked with languages with lazy evaluation in the past (Haskell, anyone?), but neither of us had any recent experience implementing a lazy lambda evaluator.

This quickly started to shape like our downfall. Our evaluator was alternating between something that loops forever and something that stops evaluating too early. Annoyingly, we had 80+ tests for the evaluator, mostly derived from alien images, and they seemed to pass all the time, even though galaxy.txt stubbornly refused to be evaluated. Attempts to reduce failures to something resembling minimal test cases failed, and attempts to produce more tests by hand just yielded tests that were always passing.

I tried to translate galaxy.txt to OCaml code so that we would not have to write our evaluator, but this turned out to be harder than I expected, plus we were not sure that there would not be more alien code incoming.

Time for my favorite ICFPC-related gif:



We had, probably, 4 to 6 different evaluator rewrites, until finally, I was ready to give up altogether. We even tried to use an existing library that implemented a lambda calculus evaluator, with little to no success. I vented my frustration in the chat with Alexey Shchepin, winner of several lightning rounds in the previous years, with whom we often get in touch during ICFPC (hi!), and he said that I probably messed up rules for cons/car/cdr (list construction and deconstruction), because people often get them wrong.

His crystal ball was right on the money and finally, we had evaluator that churned through galaxy.txt and emitter a list of numbers. Based on alien instructions, we should've had a list of number pairs (so we can plot them). Instead, I got a list of number pairs AND numbers. Obviously, there was a bug somewhere.

After reading and re-reading the code (which was tantalizingly small, almost too small to have a bug somewhere) I finally spotted "ifnil nil = false", which should've been "ifnil nil = true". Rookie mistake, easy fix. I swapped true to false, any evaluator promptly went into an infinite loop.

You know all these complaints about interview questions that focus on linked lists, and how nobody implements them in real life, because every language out there has native support for lists?

Well, I am here to tell you that linked lists are HARD. At least, when they are done using lambda calculus and should behave lazily (that is, you never evaluate more than fist element of the list until you consumed it).

It took us the longest time to realize that in our implementation lists either behaved as strict (that is, fully evaluated) and we ended up trying to evaluate infinite self-referential lists, or they had lazy semantics, and then at the end of the evaluation, we ended up with a partially-evaluated list of coordinates with just the first element ready.

We needed lazy lists, but once we had the final list of coordinates, we had to strictly evaluate all of it, "forcing" all its elements.

It is embarrassing to admit this after all my years of programming in Haskell, but otherwise, I would've had to write "and for the second day, we did absolutely nothing" :)

A rough timeline of the long slog towards evaluator:
T+5h: number encoder and decoder
T+6h: list encoder and decoder
T+7h: aborted attempt to convert galaxy.txt to OCaml
T+8h: parser for galaxy.txt
T+8.5h: we communicated with alien proxy (and, I think, scored the only point in the lightning round)
T+9h: the first buggy version of the evaluator
T+11h: organizers upload to youtube a series of three videos that explain what is a partial application, lazy evaluation, and common subexpression elimination - all in alien/galactic terms.
Somewhere here we slept
T+26h: evaluator finally works, but is very, very slow

While we were fighting with the evaluator, we missed this little gem of a message in the discord, which to my knowledge was not documented anywhere else:



Participant: alien proxy has method /aliens/{responceId}, but when are we supposed to use it?

Organizers: It's a part of our long-polling protocol - we don't know how long aliens would respond to us. You will receive responseId in Location header. I will write the docs for this. But you see - now aliens respond fast enough.



We would hit this in the next 24 hours and waste approximately 30 minutes scouring Discord for answers :( (As you can probably tell, web development is not my cup of tea)

Meanwhile, other people had other problems.

At T+7h, this exchange took place on discord:


Participant A: Is there a task description somewhere public, or is this only available to registered teams? I always enjoy reading the task description, even when I don't have the time to participate.

Participant B: the task: interact with UFO and score points by learning how to score points.
Sup dawg we heard you like ICFPC so we put ICFPC in your ICFPC so you can struggle while you struggle



At T+12h, we learned the new etymology for the word modem:


XXX: Hmm...I thought "modem" hinted at some sort of transmission but according to the discord history it just means "modulate -> demodulate" :/

YYY: the word "modem" in real life means modulator/demodulator

ZZZ: My girlfriend guessed "modern data ejaculation machine" and imho that was pretty close and way funnier



Sooner or later everyone was hit by the infinite loop:

so how long did the program run for you guys
mine hasnt crashed yet, so something must be working
kinda hard to know tho
(5 minutes later) ok nevermind thats definitely wrong


At T+19h, when it was 6 am in the organizers time zone, people were incredulous that "Ivan Zaitsev" is still awake and on Discord, so he had to post a "proof of life":




While we were busy working on the interpreter, two teams seemingly took the lead in the lightning round (and as it turned out, there were only 5 teams to score more than 2 points in the lightning round) and were posting pretty pictures:

https://twitter.com/icfpcontest2020/status/1284413782937280512





At this point, we realized that our evaluator uses 63-bit ints, and galaxy.txt contains numbers that don't fit in 63 bits, so we had to add Big_int into our code, and add some rudimentary UI to plot the set of points returned by "interact galaxy".

We also realized that we don't do a common subexpression evaluation for S combinator properly, so our evaluator is very very slow, and we tried to speed it up, which took way longer than expected.

Finally, at T+35h, we executed "interact galaxy", received two sets on points, plotted them on the same image in two different colors and saw this:



This is an alien glyph for 0, followed by a galaxy symbol.

To be continued here. This entry was originally posted at https://dastapov.dreamwidth.org/132037.html. Please comment there using OpenID.

(Read Comments |Comment on this)

ICFPC-2020: Space, The Final Frontier
Time to break the long radio silence to treat you to another tale of my ICFPC adventures. For uninitiated, ICFPC stands for ICFP Contest (and ICFP, in turn, stands for International Conference on Functional Programming), and I have been participating in them since ... well, since time immemorial (2004? 2003?) and writing up my adventures here. My most famous writeup (in Russian) about the best ICFPC so far -- 2006 -- could be found here.

This time I am going to do the write-up in English because there would be lots of English text quoted, and because I want my teammate (Hi, Alex!) and colleagues to read it.

TLDR: I liked this contest. A lot. Many aspects of it were nothing but stellar, and would serve as a yardstick against which future contests will be measured. However, the decision to trickle-feed task description through discord during lightning round was very controversial, in my opinion. It meant that you can't just print out the task description and mull it over with a cup of tea. For the longest time, task description was effectively updated every couple of minutes in a small way and periodically there would be large-ish "bulk updates". They would happen ad-hoc, without any schedule, so you had to devote significant time and effort to monitoring Discord. I have no idea what effect this had had on single-person teams, but it was probably not great. In this first post, I will rant about this A LOT (hopefully, in the first post only), because I need to get this off my chest. Then it will get better, I promise. Stick with me...


So, let me tell you a story about ICFPC-2020.

Do you know who else broke radio silence? Some aliens - they were allegedly contacting fictional Pegovka Observatory, sending them mysterious radio signals, which were decoded to zeroes and ones, and further decoded to a series of mysterious images. At least this is how the story went in the teasers of this year's contest.

First mysterious message, containing numbers 0 to 9 (first column)




I missed all this fun, but it seems that starting from Jul 1, 2020 (16 days before contest start) organizers have been posting an image per day, and more active participants flocked to the Discord chat set up by organizers to mull them over.

Organizers posed as scientists from Pegovka observatory and tried to direct the discussion about images and their possible meaning. Over two weeks, fourteen images were posted, seemingly containing the rules for encoding positive and negative numbers, incrementing, decrementing, adding and multiplying them, comparing them, and encoding true and false values and testing them.

Rules for integer multiplication, message #9 (4 * 2 = 8, 3 * 4 = 12, 3 * -2 = -6 ...)



As Discord chat was making sense of the images, organizers were updating documentation hosted on ReadTheDocs that contained all the images and their current perceived meaning. More active participants even wrote some Haskell code to decode the images into numbers and pseudocode like "inc", "dec", "add", etc. Organizers incorporated suggestions from participants in the docs, urged them to submit pull requests, and accepted them.

On the day before the contest, this image was posted (message #15), and was subject to heated debate:




Now, those who participated in ICFPC in the past are used to the over-the-top mysterious back-story that gets published before the contest. It usually contains hints that you can understand only in retrospect after the contest is over. It is always mysterious and incomprehensible. Also, you are free to ignore it - it serves to build up the anticipation of the upcoming contest, but is not part of the task, contains no important information, and serves no practical purpose as far the actual contest is concerned. It was never required nor needed to immerse yourself before the contest begins. Well, at least this was the case in all the years that I can remember back to 2004.

This year, everything was different. When the time came, I eagerly refreshed the website to see the problem specification, but what I found instead was that the backstory continues and the problem specification is nowhere to be seen.

Site contained just this:
"Dear participants of the ICFP Contest 2020. We have prepared a great
contest for you! But we have strong reasons to throw it out and ask
you to put your efforts into something else.

Our friend Ivan Zaitsev, a staff astronomer at Pegovka Observatory,
has recently become a part of a very peculiar story. During the last
two weeks, he has received many messages from an unidentified source
which was later recognized as a spacecraft. Ivan has made some
progress in decoding and understanding the messages but recently the
spacecraft has transmitted a lot more.

Please help to decode the messages! The humankind needs your help.

Ivan will be right here with the ICFP Contest organizers. Reach out to
him on Discord."

So, for people who were busy decoding "alien messages" for the past two weeks, nothing much have changed: there was still fictional Pegovka Observatory website with its blog about alien messages, Discord channel on which they were having daily chats, and documentation on ReadTheDocs that they were slowly creating. Nothing new was added to the context with which they were already familiar.

Organizers just posted more images, bringing the total to 42 (hah!), and all the "old-timers" that participated in the back story were ready to start decoding them.

I urge you to see the message posted on discord when contest have started. Scroll a bit up and down and see how all the people active on the channel for the past weeks just took it in stride and got down to work.

From the Discord, T+9 minutes after the start of the contest, one of the active decoders:

Suggestion: things are going to get lost/repeated here unnecessarily, and filing a PR will take time. Instead, let's open an issue corresponding to each message and track ideas about each there.


Remember: I reconstructed all this today, well after the contest had ended. Back then I was just confused that there is no problem description, the Pegovka Observatory site seemingly contained just old messages.

ReadTheDocs site did not look the way it looks like right now: there were just 42 pages with 42 messages, first fifteen of them decoded, and the rest were not -- pages for those were titled "???" and contained just "???" as the description, and there was no indication about their purpose or any direction for participants except "go to Discord and help us decode alien messages".

So, I did just that, arriving with other confused participants.


Participant: so, there's no task and we've got to piece stuff together from the readthedocs site?

Organizers: Yes you are. We know the meaning of the first 15 messages. Now it’s time to decode the rest.

Our team hasn't been keeping up with the messages and their meaning over the last week. How far behind are we in this contest?

Organizers: about 10-15 minutes of careful reading behind I think


I think that "10-15 minutes of careful reading" was an understatement of truly galactic proportions. Yes, you could probably catch up in half an hour if the information was organized in a somewhat linear fashion and if you could ignore the chat.

However, the chat was the only place that promised some answers. Among the throngs of confused, more clued-up people were writing "#17 could be associativity rules" or "#20 could be function composition" or "Ha! Booleans are church-encoded".

I was very confused. How do they know this at 14 minutes after the start of the contest? Did they manage to decode THIS so quickly?

Image 17:
ap inc ap inc 0 = 2
ap inc ap inc ap inc 0 = 3
ap inc ap dec x0 = x0
ap dec ap inc x0 = x0
....


Image 20:
ap ap ap b x0 x1 x2 = ap x0 ap x1 x2
ap ap ap b inc dec x0 = x0


Organizers were just repeating "Decode messages! Collaborate!", and the thing is: people who where active for the past two weeks knew exactly what to do and engaged with the organizers, and organizers engaged with them.

Many, many other participants were the living embodiment of this meme:


Imagine joining discord on T+27 minutes to see this being posted:

BTW, parser fails for #24: it recognizes block of four dots as x0


Huh? What? Which parser? Where did they get that? In 25 minutes? I started looking at the images. Oh, the first one looks like it encodes numbers! Well, duh - it clearly says that on the docs page. I browsed through the rest of the decoded images and finally reached #16 - the first undecoded one:



Oh, the right-hand column looks like numbers, 0, -1, 1, -2, 2 (it took me a minute to write them down, checking the docs page for numbers). And before that, "c" thing - that is "=". And right before that: numbers, 0, 1, -1, 2, -2.

Oh, so this is negation! Excitement! I switched to discord to share my find. I scrolled through unread messages first, only to see that this was already suggested several times. Furthermore, one of the suggestions had a reply: "yeah, reload the docs page - it is already decoded". I reloaded the page, and indeed, it now said 'Negation' with image decoded into neat numbers.

Organizers were simulating "excited scientist from Pegovka", who was reading the chat and incorporating suggestions into the documentation. As documentation was held in GitHub repo, some people suggested that we need to open PRs to update the docs.

Early doc pages were referencing the Haskell script for decoding the images, so I decided to update it to include suggestions being posted to the chat. I made a PR to submit the changes in the decoder, and kept it updated for a while, eventually realizing that it would be silently ignored, and there is no intention to merge it.

For our team of two, there was no point to try and decode images. Those who were busy decoding pre-contest left everyone else in the dust. Whatever idea you had - they had it earlier already. Everyone was sending suggestions, seemingly at once. Orgs were busy sifting through them and updating the docs accordingly, picking suggestions according to some unknown criteria, and giving little feedback. Updates to docs were steadily streaming in. Every time you pressed "F5" or Ctrl-R, there would be something new on the doc pages. This was quite demoralizing: why try decoding something when there are dozens of people who will beat you to it. This reminded me of the first time I participated in MIT puzzle hunt in a team of 15+ more experienced participants. They tore through all the starter puzzles faster than I was able to make sense of them, and I was able to catch up only when they got to harder puzzles and the tempo slowed down.

Bottom line: as a small team, we were better off just refreshing the docs page and trying to make sense of what is being written there.

But this still left the million-dollar question: why are we doing this at all?. What is the end-goal?

Are we supposed to write a decoder for images like this (with more images incoming)?

Are we supposed to communicate with aliens somehow?

Are we supposed to write code in the alien language (using pictures) for the task that would be revealed soon?

When you registered your team, you were issued a "team key" and directed to a small GitHub repo that contained sample code in many languages that will establish communication with the server that organizers provided, send the key and check if server replied "OK". This seemed to suggest that we will be communicating with organizers somehow, but so far there were no hints on when, how, or why it would happen.

This was certainly unlike any ICFPC I saw before, and I certainly did not like it :)

At T+2.5h organizers posted this message: We're really amused by the great progress you're making with decoding the messages. We're monitoring the chat in Discord for your suggestions on the meaning of messages and names for unknown symbols appearing in these messages. We're updating the documentation accordingly. Keep going!

At the same time, we have more news from Pegovka Observatory! Our friend Ivan Zaitsev says that a new message which appears to be REALLY HUGE is being received right now. We don't really know if we'll be able to render this message as an image. In this case, we'll post this message as text. That is why it is very important that you give names to unknown symbols in the messages.

We'll make a new post when this REALLY HUGE message is ready.

Well, think clears things up ... not.

Will it be text? Will it be an image? Seems likely that it will be text. What are we going to do with it? What are we supposed to do meanwhile? I don't know about you, but I find working while following an active chat to be quite impossible - but once again, I found the chat to be the only source of _some_ clarity, so you had to keep an eye on it.

Chat was all over the place. "- Seems like language is lazy. - What are we doing? - Hi, I just joined - where is the task description? - #31 looks like syntax for lists - Yeah, we already know this - I don't know any Haskell, what is cons, car, and cdr? - When does the contest begin? - What is a church-encoded boolean?". The signal from this noise was slowly filtered into docs by organizers, and it looked like they were getting overwhelmed, despite four of them working on filtering chat:



xxx: Are suggestions from the chat no longer getting accepted by organizers? If not then I don't even know what we should be working on


yyy: At least it seems like quite some solutions which have been mentioned here multiple times already have not found their way into the docs, which makes it tough to read the last couple messages and also makes me wonder whether taking a walk in the sun now is a safe idea or things are about to start for real soon-ish?


Organizers: We are working. Right now 4 my teammates is merging it. And last message we are get great suggestions until 35 message. Is there any ideas about #36?




Thing is, re-reading the Discord history now I have this strange sense of duality: I still remember being utterly confused back then. But now, when alien pictures are no longer a mystery and I know the goal of the contest, a good deal of Discord messages make sense - yes, this guy is right, and this guy's suggestion was not bad either. Good job, chaps, both of you.

Now I can easily put myself in the organizers' shoes and see how Discord looked like "people are getting it! we are doing great!".

My teammate Alex and I meanwhile were mostly waiting for the REALLY HUGE message.

At T+3.5h organizers said: "FINALLY! We have finished to receive the HUGE MESSAGE and we're processing it now. So, we can try to send them something. What I should choose: the some big number or ( 0 )?"

People in the chat: "Send 0! Send (0)! Send 42! Send 1000! Don't send it! Let's discuss!"

Organizers, two minutes later: "Well, we are sending (0) then!" :)

Immediately after, this post went up: When Ivan Zaitsev read the suggestion to transmit something to the spacecraft again in regard to the message #36 in Discord, he was energized. We modulated a list of a single zero element for Ivan, and he transmitted that message with his antenna at Pegovka Observatory.

And… he got the response! This one: 110110000111011111100001001111110101000000.

When Ivan repeated the transmission after approximately 10 seconds, he received another response: 110110000111011111100001001111110100110000.

Neither Ivan, nor we have any idea about the meaning of these responses. That's why now we're going to create a proxy so any team is able to transmit something and get something in return.

Can't wait to share this proxy with you!

Did I mention already that you had to keep an eye out for updates in the chat or on twitter at all times? :)

At this point, I posted that messages obviously decode to the gliders from the Game of Life, but very few people rose to the bait :)

Glider:


Shortly after, information about accessing the "proxy to radiotelescope" went up:
"We've added a few AlienApi methods to the API we've already prepared for the contest and glued them to the antenna at Pegovka Observatory. Hope it'll be working flawlessly.

All you need is the API key from your team profile."

Proxy was HTTP server that organizers ran, responding to POST requests. You could've POSTed "(0)" there, and it will reply with the long string of ones and zeroes, or you could send something else, and it will reply with "1101000", which was alien encoding for (0).

Alex and I decided to work on encoder/decoder for these numbers (at this point organizers already released enough information about encoding and decoding schemes for simple numbers and lists of them) to do SOMETHING.

It was still not clear what lightning round will be about. "Lightning round" is the first 24 hours of the contest that is usually restricted to a subset of the full task and has a separate set of prizes. This message on Discord got 29 likes and 1 dislike:


So hooray for a very involved background story and all, and I don't want to sound ungrateful, but I actually traveled to another country to meet my team members to do some coding together and while I understand that there is fun to be found in everybody decoding stuff together we are really uncertain since some hours now whether and when our expected experience of coding together and competing against others will start.

Is this the format of the lightning round and the conclusion will be that discord is very suitable for rapid prototyping?
Or are we about to get into the coding vs others part any moment now?



At T+4h there was still no HUGE MESSAGE to be had...

To be continued here (and it will get better, and I will rant less, I promise) This entry was originally posted at https://dastapov.dreamwidth.org/131798.html. Please comment there using OpenID.

(Read Comments |Comment on this)

0x29
It is this time of the year again :)

Борода еще седее, но совсем чуть-чуть. Внезапно обнаружил себя родителем школьника. Проекты с детьми сложнее, чем проекты на github. Плюс один иностранный язык, хоть и со скрипом. На работе учил интерна, который моложе, чем мой .emacs. Внезапно понял, что в текущей индустрии уже столько же, сколько до этого провел в предыдущей. Один год - это больше, чем 1 миллион шагов, но меньше, чем два. Планов еще больше, а времени для них еще меньше (но это по-прежнему лучше, чем наоборот).

This entry was originally posted at https://dastapov.dreamwidth.org/131497.html. Please comment there using OpenID.

(Read Comments |Comment on this)

ICFPC-2018: видео
А вот как оно работало.

Сборка:


Разборка и переделка:


This entry was originally posted at https://dastapov.dreamwidth.org/131321.html. Please comment there using OpenID.

(Read Comments |Comment on this)

ICFPC-2018
В этом году ICFPC был про футуристическую 3D печать.

Коротко задачу можно описать так:

Вам дается описание 3d-модели, составленой из кубиков одинакового размера. Все кубики или стоят на земле или одной из сторон соединены с каким-то другим кубиком. У вас есть "нанобот", который может перемещаться в пространстве (наплевав на гравитацию) и "печатать" кубики в непосредственной близости от себя. Кроме того, от бота можно "отпочковать" нового бота (и так до 20 штук) и кроме того, можно временно "включить антигравитацию" в зоне печати, и тогда кубики, не прикрепленные к чему-то, будут висеть в том месте, в котором их напечатали. При отключенной антигравитации висящие в воздухе кубики считаются фатальной ошибкой и вызывают завершение программы.

Зона печати - это куб со стороной R, от 20x20x20 до 250x250x250 в зависимости от модели. Все операции с ботами имеют какую-то цену в виде затрат воображаемой "энергии", причем цены варьируются от 1-15 единиц за перемещение бота в пространстве до 30*R*R*R за каждый "ход" (в рамках которого каждый бот выполняет одну операцию) при включенной антигравитации. Ваша задача - свести затраты энергии на печать конкретной модели к минимуму.

Вам дается описание 186 моделей, и "стандартная программа печати" для каждой из них. "Стандартная программа" всегда одинакова - включаем антигравитацию и ездим одним ботом туда-сюда "змейкой" по всем клеткам на высоте 1, 2, 3 ..., печатая кубик непосредственно под ботом (если он там должен быть). В конце обхода антигравитация выключается и бот возвращается в (0,0,0) -- вернуться "домой" было необходимо по условиям соревнования.

Понятное дело, что на это уходило громадное количество энергии - для моделей 200х200х200 каждый ход стоил 240 миллионов единиц энергии из-за дополнительных расходов на антигравитацию, а ходов могло быть несколько десятков тысяч...

Отдельно стоит упомянуть структуру программы для печати, которую вы должны были сформировать. Программа - это простая последовательность команд без каких-либо возможностей ветвления, организации циклов и т.п. У каждого бота был уникальный идентификатор (число от 1 до 20), и на очередном ходу каждый бот по порядку (по возрастанию ID) получал из последовательности команд в программе рвно одну инструкцию и выполнял ее.

День первый, lightning round

Для меня первый день начался в 17:00 по местному времени, но освободился я только к 18:00.

Организаторы любезно предоставили визуализатор моделей и визуализатор процесса печати, но они были написаны на JS. Я JS только читаю (со словарем), и мне не очевидно, можно ли найти способ запускать визуализаторы из командной строки, а не через форму в браузере. Писать свой (нетривиальный) визуализатор - это по опыту прошлых лет почти всегда время, потраченное впустую.

Учитывая, что все входные форматы были бинарными (и все, что можно, было в них представлено наименьшим количеством бит), то первым делом я написал декодер и энкодер для програм, а так же код, который считает общее количество энергии, затраченное программой -- чтобы меньше зависеть от организаторов и их кода, который я мог запустить только в браузере.


Поиск оптимальной программы для печати был, очевидно, NP-полной задачей и хорошие эвристики для нее были мне неизвестны. Но по по опыту в lighning round зачастую побеждает тот, кто "берет больше, кидает дальше и продолжает кодить, пока оно летит", а не тот, кто придумал самый классный алгоритм. В результате я реализовал первое, что пришло в голову - берем программу тупой печати, предоставленную организаторами, и слегка ее оптимизируем. Вместо того, чтобы отключать гравитацию в самом начале, будем проверять, будет ли к чему-то прикреплен следующий печатаемый кубик, и если нет - то включим антигравитацию, напечатаем кубик и постараемся отключить ее как можно скорее.

На этом месте часы показали 0:50, и я пошел спать. Отослать решения можно и завтра -- тем более, что я еще даже не прочитал о том, что и как надо засылать.

День второй, окончание lighning round

Так как я "сова", то на второй день утром я сладко спал. Проснувшись, я выловил несколько мелких багов, поразмышлял о том, что делать дальше и наконец-то сгенерировал решения для всех имеющихся задач, собрал архив с решениям и отослал его. На часах было 11:18. Тем временем организаторы сказали, что за 6 часов до окончания lightning они отключают обновление таблицы с результатами, и я опоздал на 18 минут :)

Своей позиции в lightning я в результате не знаю.

Следующим очевидным шагом на выбранном мной пути было продолжать оптимизировать тупую программу для печати. Напомню, что тупая программа была последовательным обходим всего объема печати с помощью перемещений бота на одну соседнюю клетку, перемежаемая командами печети кубика. Если зона печати была большой, а модель - мелкой, то большую часть времени бот планомерно "утюжил" пустое пространство по одной клетке за раз, тратя на это кучу времени и энергии. Естественно было бы пропускать все ненужные перемещения и передвигаться к следующему печатаемому кубику наиболее оптимальным образом. Плюс, естественно, включать антигравитацию (командой Flip) только тогда, когда без нее было никак.

Где-то к 15:00 я заслал все оптимизированные таким образом решения. До конца lighning было еще два часа, но я решил, что больше я ничего радикального не придумаю, и сел писать декодер описания модели из бинарного файла. В процессе я понял, что если кубики находятся по соседству, то можно переместиться к первому из них, и, никуда не сдвигаясь, напечатать и соседний (или может даже несколько). Это, как мне кажется, и было финальным вариантом решения, отправленного на момент окончания lighning round.

Дальше я сел писать свою реализацию обхода модели. Идея была в том, что если я придумаю, как обходить модель более-менее оптимальным способом (например, чтобы не нужно было использовать антигравитацию в принципе), то дальше можно было бы думать, как разделить модель на части, и построить каждую часть отдельным ботом.

Со старта, естественно, надо было идти к ближайшему опирающемуся на что-то кубику, который, естественно, мог быть только из самого нижнего слоя. Дальше начинались варианты - можно было забираться вертикально вверх и строить "столб" поверх этого кубика, или можно было идти в ширину, или комбинировать движения вверх и в сторону, учитывая что бот мог построить до 18 кубиков вокруг себя, не сходя с места.

За этими экспериментами незаметно подошел к концу lightning round.

День второй, начало основного соревнования

По окончании lightning организаторы опубликовали изменения к условию задачи - максимально возможное количество ботов увеличилось до 40, и боты получили возможность коллективно строить группы кубиков за один ход. Два бота могли построить "отрезок" из кубиков (длиной до 30 штук). Четыре бота, расположенных по углам, могли построить прямоугольную "плитку". Восемь ботов могли построить параллелепипед (с длиной стороны, опять таки, до 30 кубиков). Затраты энергии на рисование были совершенно такими же, как при рисовании поштучно, но зато можно было нарисовать много кубиков за один ход. Кроме того, была добавлена команда Void, позволяющая разрушать кубик и превращать его обрано в энергию, и групповые варианты команды Void, аналогичные описаным выше.

Все это я поначалу пропустил, так как пытался продолжать оптимизировать свой алгоритм построения одним ботом. Но все эксперименты упирались в то, что чаще всего на сложных моделях бот замуровывал себя в угол и оказывался в позиции, из которой не было выхода.

В конце-концов я плюнул и прочел обновленное условие. Кроме новых команд организаторы добавили два новых типа задач: "разобрать модель" -- начиная со стартовой модели разрушить все кубики и закончить программу с полностью пустой рабочей областью, и "перестроить модель" -- в которой тебе даны стартовая модель и целевая модель, и тебе надо превратить стартовую модель в целевую с минимальными затратами энергии.

После прочтения документации на групповые команды я начал фантазировать - ведь можно пытаться собирать модель из максимально возможных параллелепипедов и потом дорисовывать нужное. Или рисовать объемлющие параллелепипеды и отсекать ненужное. Или делать то же самое "плитами", и рисовать модель слоями снизу вверх. Но может быть так, что плиты максимальной площади ориентированы в вертикально плоскости. И вообще - задача оптимального разбиения модели на плиты или параллелепипеды наверняка или сводится к задаче раскроя прямоугольника, или к чему-то подобному, но тоже NP-полному. А подбирать/перебирать эвристики можно очень долго, и не факт, что к концу соревнования получится что-то стоящее.

На этом месте я взял свой код для оптимизации тупых решений от организаторов, добавил туда поддержку Void (для одного кубика), и "оптимизировал" все имеющиеся решения для всех трех типов задач, и заслал решения. На часах было 22:00.

При этом я понял, что для целого ряда задач разборки и переделки мое решение работать не должно, так как при удалении кубиков я не проверял, не отвалится ли от модели какой-то кусок и антигравитацию не использовал никогда.

Я посмотрел мои решения для сложных моделей визуализатором от организаторов и сосредоточился на двух основных проблемах, которые у меня явно бросались в глаза. Во-первых, для задач на сборку я явно иногда пропускал момент, в который уже можно отключить антигравитацию, и держал ее включенной на шаг-два-три дольше, чем нужно. Во-вторых, некоторые задачи на разборку ужасно тормозили. В коде отключения антигравитации нашелся обидный баг в месте, которое должно было перебирать ранее неприкрепленные кубики и прикреплять их к вновь построенным до тех пор, пока это возможно. В тормозящих задачах на разборку вылез баз в pathfinding.

В час ночи у меня был код, способный за разумное время решить все имеющиеся в наличии задачи и не упасть :)

Я заслал решения и пошел спать. Обновление турнирной таблицы жутко тормозили (на протяжении всего соревнования) и я так и не увидел, на каком я месте. К двум часам ночи сервер организаторов прочихался и я оказался восьмым (в основном потому, что мало кто вообще к этому времени что-то заслал).

День третий, воскресенье.

На следующий день утром я обнаружил себя на 13-м месте и проснулся с мыслью, что надо же наконец научиться что-то делать одним ботом и браться за несколько. Особо светлых идей у меня не было, и я решил начать с того, чтобы сделать свой генератор обхода модели снизу вверх (для конструирования) или сверху вниз (для разборки), и дальше может в процессе что-то придумается.

Генератор написался где-то к 11:00 (я уже говорил, что я сова?) и неожиданно оказалось, что для некоторых задач на разборку он работает заметно лучше, чем оптимизированная тупая программа от организаторов. Которая должна была, по идее, делать ровно то же самое. Тут стоит отвлечься и заметить, что мой код сохранял в отдельные файлы кол-во эниергии, затраченной на решение задачи, и процентное отношение этого количества к стандартной программе от организаторов и к предыдущей моей попытке решения этой задачи. Это здорово помогало видеть, улучшается код или нет.

При ближайшем рассмотрении оказалось, что я и организаторы обходим слои в разных направлениях. Ок, - подумал я. Раз других идей нет, будем копать в этом направлении.

Всего возможных способов обхода каждого слоя было восемь - можно начать в одном из четырех углов, идти из него в одну из двух возможных сторон, а далее "змейкой" по всем оставшимся рядам. Первым делом я стал выбирать лучших вариант обхода из восьми возможных для все модели в целом, при этом после выбора направления для первого слоя направления для всех остальных были предопределены. В конце слоя бот поднимался уровнем выше, меня направление обхода на "противоположное" и так далее.

Результаты улучшились для всех задач. Увы, я не знал, на сколько это улучшило мои позиции, так как турнирная таблица тормозила. Я перестал на нее смотреть и стал возиться дальше.

Дальше я попоробовал выбирать направление обхода каждого слоя из восьми вариантов, и брать наилучший из восьми. Результаты улучшились еще где-то на 10-15%, но код начал ТОРМОЗИТЬ.

Тормозил он в основном потому, что для выбора наилучшего варианта на каждом слое я пересчитывал энергию всей программы с самого начала, так как другого мой код не умел.

Все, что имело отношение к состоянию рабочей области, было сделано число-функциональным и добавление одной команды в программу обновляло общую энергию за линейное время. Проблемы со скоростью почти пропали (ну, кто бы сомневался).

Почти, но не совсем. Некоторые задачи продолжали тормозить, и тормозил там pathfinding. Я потратил какое-то время на улучшение мелочей тут и там, но с pathfinding-ом yичего особо умного не придумал.

Кроме того, решения задач на разборку тормозили из-за того, что мой алгоритм определения, не отвалится ли сейчас кусок модели, был написан в лоб и имел время работы, пропорциональное количеству оставшихся кубиков.

Тут я с женой отправился Гулять По Полям и Считать Зайцев, и в процессе она мне и говорит человеческим голосом: "а зачем ты, добрый молодец, так убиваешься? Ты научись решать задачу сборки так, чтобы тебе не требовалась антигравитация вообще. А как научишься, то для разборки сначала реши, как модель собрать, а потом разбери строго в обратном порядке. И ничего у тебя не будет отваливаться".

Тут у меня случился facepalm, все зайцы испугались и разбежались, и я пошел домой, и поменял свой код так, чтобы он при проходе слоями вверх строил только те кубики, которые гарантировано не отвалятся, затем делал проход вниз и снова строил кубики, которые не отвалятся -- при этом распологая бота не над, а под местом строительства. И так далее до тех пор, пока что-то продолжает строится.

Оказалось, что все модели, кроме пяти, собираются за один проход вверх-вниз. И задача разборки, таким образом, была сведена к задачи сборки.

Дальше я стал смотреть, действительно ли мои решения для разборки работают, и тут оказалось, что несколько моих решений в визуализаторе от организаторов просто не работают -- бот пытается проходить через занятые кубиками клетки.

Оказалось, что у меня банальная ошибка в реализации проверки выполнимости команды LMove, и она была в коде все это время, но на задачах на сборку этот баг не "выстреливал", а вылез только в задачах на разборку.

Все это время я плавно катился вниз по турнирной таблице и скатился до 45-го места.

Я заслал все имеющиеся у меня обновленные решения, попытался дождаться обновления таблицы, но у организаторов все по-прежнему тормозило. Я оставил компьютер считать решения для всех еще нерешенных задач и пошел спать.

Пока я спал, за два часа сервер организаторов "прочихался" и я поднялся до 26-го места.

День последний

Соперники мои не спали и за ночь с 26-го места я скатился обратно до 42-го. Но когда я проснулся, меня ждала куча посчитанных за ночь решений, я заслал их и тут же поднялся до 22-го места (из 95 команд).

После этого я чуть-чуть улучшил свое решение так, чтобы бот при обходе наверх пытался выбирать позиции в текущем ряду, в которых можно зарисовать максимальное количество клеток ниже себя (и аналогично при обходе вниз). Это дало еще 10-15% улучшения.

Как это повлияло на результаты, я уже не знал, т.к. организаторы заморозили таблицу за шесть часов до окончания соревнования.

Дальше я какое-то время улучшал свой код по мелочи -- в основом тем, что прекращал обходы/циклы как можно раньше.

А затем у меня случился второй facepalm. ВНЕЗАПНО я понял, что в задачах на сборку и задачах на разборку используются одни и те же модели. И соответственно с моим подходом задачи на разборку можно вообще не решать - достаточно загрузить имеющееся решение соответствующей задачи на сборку, "развернуть наоборот" и сохранить. Было очень обидно не сообразить это раньше :(

Ну, лучше поздно, чем никогда. Я написал соответствующий кусочек кода и затем до конца соревнования (в течении, наверно, пары часов) только считал решения сложных задач (с большими номерами) и засылал организаторам.

Кроме того, стало понятно, что для задач по переделке моделей часть из них тоже уже встречалась раньше в задачах на сборку, но тут я уже ничего менять не стал.

В сухом остатке у меня были решены все задачи на сборку - и, соответственно, все задачи на разборку -- а также все задачи на переделку, кроме пяти-шести штук.

Хоть турнирная таблица и была вроде бы как заморожена, но организаторы все время что-то досчитывали/пересчитывали (абсолютно непрозрачным образом) и в результате я перемещался по таблице туда-сюда, пока не стабилизировался на 26-м месте.

Я оптимистично ожидаю, что финальный результат будет получше, но узнаем мы это, как всегда, через месяц.

В целом этот год получился, как по мне, ни то, ни се. Организация была не на высоте (хотя с условиями не накосячили, что большой плюс), и 3d я исторически не очень люблю.

Команда моя называлась "Bot the Nanobot in the Race to the Bottom".

Код: bot-the-nanobot-icfpc-2018.zip

Вот как выглядел мой путь по турнирной таблице:



Выводы стандартные: не экономьте на сне, ходите гулять, записывайте мысли на бумажку. Общение с женой рулит, за что ей традиционно большое спасибо :)

This entry was originally posted at https://dastapov.dreamwidth.org/130982.html. Please comment there using OpenID.

(Read Comments |Comment on this)

ICFPC-2018
Тем временем незаметно подкрался очередной ICFPC: https://icfpcontest2018.github.io/

В этом году программируем нано-3D принтеры.

Пока пишу сам, на ocaml-е. Если кто хочет за компанию - пишите :)

This entry was originally posted at https://dastapov.dreamwidth.org/130676.html. Please comment there using OpenID.

(Read Comments |Comment on this)

Работа в UK - считаем деньги
Специально для Макса и Жени и ещё Жени :)

Допустим, вы получили offer на работу в UK. Как понять, насколько он хорош, и во что выльется переезд и жизнь в Великобритании?

Я буду рассчитывать на то, что у вас на руках детальное предложение, расписывающее все benefits.

Сначала надо пересчитать грязную зарплату из предложения в чистую, после налогов. Идем на https://listentotaxman.com/ и не меняя никаких настроек вписываем годовую зарплату в "gross wage per year". Жмем "calculate my wage" и видем чистую годовую/месячную/недельную зарплату (net wage) в окошке справа.

Теперь вы знаете, сколько будете примерно получать на руки (почему примерно - см ниже про пенсию). Теперь посчитаем расходы. Он будут примерно такие (на семью из двух взрослых и двух детей):

Регулярные траты:

• Жилье: 1500-2500 фунтов в месяц, в зависимости от типа (дом или квартира), местоположения, размера и качества
  
• Газ, вода, электричество, телефон/мобильники и интернет: все вместе 150-300 фунтов в месяц. Суммы будут варьировать из-за отопления зимой и его отсутствия летом, а также от того, сколько вы будете платить за мобилки (с субсидированием телефона или без) и интернет (с телевизором или без)
  
• Еда: 500-700 фунтов в месяц на продукты, не считая кафе-ресторанов и т.п.
  
• Местный налог (council tax): 1000-2500 фунтов в год (зависит от размера жилья)
  
• Проезд: 0-3000 в год, скорее всего где-то 1600-2800 в год, в зависимости от того, на чем и как далеко надо будет ездить
  
• Опционально машина: 100-300 фунтов налога в год, 30-100 фунтов на бензин в месяц, 700-2000 страховка. Если работа в Лондоне, то на работу на машине ездить не получится (вся зарплата и нервы уйдут на парковку :), так что машина нужна только чтобы ездить по стране/на выходных/возить детей куда-то и т.п. Страховка дорогая, и надо будет искать страховую, которая "зачтет" украинский стаж, иначе цены получаются конские (для для новых водителей без стажа), но они быстро падают.
  
• Школы и садики: про садики я знаю мало. Вроде бы они бывают платые и на весь день, или же бесплатные и на часть дня, но лучше не слушать меня и поискать самому. Государственные школы бесплатные, но надо жить относительно рядом с ней, чтобы в нее попасть. Частные школы - 10К-40К в год. Вообще школы, садики и прочие социальные аспекты наверное потянут на отдельный большой пост.
  

Нерегулярные траты: довольно хорошо описаны на Numbeo. Я пробежался глазами по Лондонским ценам и не увидел ничего такого, чтобы захотелось исправить.

Разовые траты:

• Депозит при аренде жилья : в размере 1 месяца аренды, возвращается по окончании
  
• Разные комиссии при оформлении аренды: 100 фунтов, оно же при каждом ее продлении
  
• Жилье скорее всего будет без мебели, только с бытовой техникой, поэтому обставить его по-быстрому мебелью из ИКЕИ будет стоить фунтов 700 + матрас (100-1000 футов в зависимости от модности).
  
• Жилье должно быть убрано и приведено в божеский вид, но если вдруг нет, то убрать все включая химчистка ковров, сантехники, и т. п обойдётся в 300-600 футов.
  
• Машина: 1000-14000 (в зависимости от марки, состояния, ...). Через год надо будет сдать на местные права: что-то около 200 фунтов за оформление прав, экзамен и т.п.
  
• Через два-три года (я не в курсе нынешних правил) надо будет продлить рабочую визу, стоимость оформления раньше была такая же, как и у первоначального оформления визы
  
• Переехать в другой дом: 100-600 фунтов (непафосные грузчики)
  

Если работа не в Лондоне, то все вышеприведенные цифры остаются в силе кроме стоимости жилья и проезда.

Как можно сделать эти прикидки более точными:
- Смотрите жилье на rightmove.co.uk, zoopla.co.uk. На зупле есть хорошая статистика по ценам. Моя жена о выборе района: https://yulanta.livejournal.com/56518.html и https://yulanta.livejournal.com/59059.html (по тэгу uk там еще много рассказов про жизнь)
- Еда: смотрим на tesco.co.uk, sainsburys.co.uk, ocado.co.uk, mysupermarket.co.uk и собираем корзину
- Машина: autotrader.co.uk
- Проезд: метро на tfl.gov.uk, поезда на nationalrail.co.uk. Годовые проездные всегда дешевле, недельные и месячные обычно нет.

После того, как вы прикинули приходы и расходы, смотрите на benefits в предожении
- Есть ли годовые бонусы? Если да, приплюсовывайте их к зарплате и пересчитайте чистый доход
- Есть ли медстраховка? Можно и без нее, но с ней значительно лучше. Она только для вас или и для членов семьи?
- Может быть работодатель оплачивает проезд?
- Есть ли одноразовый relocation bonus или что-то подобное?

Отдельно надо поговорить о пенсии. Работодатель будет обязан включить вас в одну из частных пенсионных программ. Вы будете отчислять туда какой-то процент от зарплаты (обычно от 1% до 6%), и, как правило, работодатель будет отчислять туда столько же, сколько и вы (дополнительно к вашей зарплате). То есть, отчисляя в пенсию 6% вы получаете фактически +6% к зарплате за счет взносов работодателя. Ищите в предложении по словам "matching pension contributions". Отчисления в пенсию делаются из "грязных" денег (до налогов) - возвращайтесь в самое начало к listentotaxman и поиграйте там с цифрой "Pension contribution, %". Пенсию можно будет перевезти с собой при переезде в другую страну (но тут надо внимательно читать условия конкретного пенс. фонда.)

Финансовый год в Великобритании начинается 6-го апреля. Если вы переезжаете в январе-марте, то ваш relocation bonus (если есть) и первые зарплаты имеют шанс вписаться в необлагаемый налогом минимум (или совсем чуть-чуть вылезти за него), что может быть немаловажно в самом начале пребывания в стране.

Продолжение рассказа вот тут

This entry was originally posted at https://dastapov.dreamwidth.org/130248.html. Please comment there using OpenID.

(Read Comments |Comment on this)

Работа в UK - здравоохранение, школа, съем жилья
Первая часть рассказа вот тут, в ней было про финансы, а тут мы поговорим про не-финансовые аспекты.

Школы и садики

В садик наши дети не ходили, поэтому про них я не знаю. ничего.

Теперь поговорим про школы. Школы бывают начальные (с 4-5 лет до 11) и средние (с 11ти). Школы бывают частные и государственные. Можно учить ребенка самостоятельно (домашнее образование), это разрешено официально и тебе не могут отказать, если ты хочешь забрать своего ребенка из школы.

В государственные школы ты попадаешь по месту жительства. Если желающих попасть в школу больше, чем мест, то они сортируются по расстоянию от школы (по прямой) и набираются в таком вот порядке. Это естественным образом определят область на карте, из которой реально попасть в ту или иную школу, так называемую catchment area. Соответственно состояние или же рейтинг школы опосредованно являются индикатором того, какой это район (хороший или не очень). Таким же образом состояние и популярность школы влияет на цены на жилье вокруг нее. Если вам не нужна школа, но приглянулся дом рядом с ней, то по факту вы будете за него переплачивать.

В гос школах классы большие -- 30 человек. На уроках будет учитель, 2-4 человека помощников учителей, может быть волонтеры, которые помогают помощникам. Есть единый набор тем/предметов, которым будут учить. но нет единой школьной программы или набора учебников. Соответственно, качественность школы сильно зависит и от директора, и от учителей. Есть организация Ofsted, которая инспектирует школы и пишет довольно развернутые и интересные отчеты. Их надо читать, но обязательно обращать внимание на то, как давно он был сделан -- со времени последнего отчета мог поменяться директор, и все могло измениться в любую сторону.

Любое конкретного места жительства в рамках города обычно попадает в catchment area сразу нескольких школ. Понятно, что какие-то хорошие, какие-то не очень. Понятно, что попасть в хорошие сложно (т.к. как только происходит разделение на хорошая/плохая все сразу начинают ломиться в хорошую). Особенно посреди года, например. А учитывая, что в школы записываются обычно в апреле (чтобы начать следующий учебный год в сентябре уже в новой школе), то с переездом попасть в хорошую школу почти нереально.

В частные начальные школы ты попадаешь по собеседованию. Они обращают внимание на место жительства, но не сильно. Цена отличается от школы к школе и нужно смотреть в каждом конкретном случае. Частные школы обычно имеют меньше класс (в районе 12-20 человек), лучше учителей (и соответственно лучше программу), больше послешкольных кружков и внешкольных активностей. Ценники отличаются от школы к школе и не обязательно напрямую коррелируют с качеством образования.

В начальную школу идут в том году, в котором ребенку исполнится 5 в течении учебного года (подробнее смотри тут). Занятия начинаются в 8.30 и заканчиваются в 15.30. В процессе много перемен, перерывов, прогулка на час. По моему мнению отношение полученных знаний к потраченному времени очень небольшое (это было одной из причин, почему мы выбрали домашнее обучение).

Теперь про средние школы. Средние государственные школы бывают двух видов -- обычные и grammar school. Grammar -- это академически сильная школа. В которую большой конкурс и нужно сдавать экзамены. Попасть сложно. Но если попал -- молодец, можешь начинать готовиться пахать :). Если не попал -- всегда можно пойти в обычную. Они, естественно, тоже бывают хорошие и не очень, и надо смотреть, читать и выбирать.

Средние частные школы бывают обычные, только для мальчиков, только для девочек, и в каждой из этих категорий дополнительно с проживанием (boarding) или без. Бывают школы церковные (catholic or Church of England). Это надо учитывать при выборе.

Бывает так, что начальная и средняя школа находятся в одном здании или по соседству и считаются одной школой. И закончив начальную, ты автоматически переходишь в среднюю. Но бывает и так, что вот эта школа - только начальная, а вот та школа - только средняя, и в нее надо будет записываться/поступать отдельно.

Медицина

Местная медицина бесплатная. Ты регистрируешься в местной NHS (система здравоохранения), они тебе присылают некий номер, с ним ты идешь в поликлинику по месту жительства и регистрируешься у них. Они тебя прикрепляют к одному из своих врачей (GP, терапевт\педиатр), и дальше ты можешь к нему (или к любому другому терапевту из этой клиники) если ты заболел или у тебя какие-то жалобы. Сначала надо записаться к нему на конкретное время. Квалификация врача и уровень загрузки сильно зависит от клиники, но если у тебя несрочно, то можно прождать свободного слота и месяц. Если же тебе срочно, то рано утром ты звонишь и записываешься на сегодня, если получится. Домой врачи не ходят. Скорые приезжают, но только если есть угроза для жизни (тебе по телефону устраивают triage и если это не их случай, то они не поедут). Вообще складывается впечатление, что в случае реальной угрозы/аварии/... тебя спасут - приедет скорая, прилетит вертолет, тебя эвакуируют в госпиталь и т.п.

Но если ты не умираешь и способен передвигаться, то спасение утопающих - дело рук самих утопающих. Температура у ребенка пройдет сама собой или, если хочешь, можешь везти его в госпиталь. Если ты сломал руку, то ты едешь в ближайший госпиталь и попадаешь в Accidents and Emergency (A&E), там тебя регистрируют и сажают в очередь. В очереди можно прождать часы (особенно если в ней есть кто-то, кто сломал что-то посерьезнее). Тоже самое происходит, если тебе срочно нужно показать ребенка -- например, он проглотил что-то или ночью резко поднялась температура. Ты берешь ребенка в охапку, едешь в ближайший госпиталь, ждешь в очереди. Ожидание 3-4 часа -- норма, говорят.

Допустим, ты попал к GP и тебе нужна консультация узкого специалиста. Тут начинаются варианты. Если у тебя есть страховка, ты можешь об этом сказать и тебя отправят к платному специалисту. Ты получаешь добро от страховой, идешь на прием, и если выясниться, что тебе нужные другие специалисты, тесты или анализы, то этот специалист напишет бумажку для страховой, и ты пойдешь дальше -- и так до тех пор, пока страховая "дает добро". Если у тебя нет страховки, то тебя отправят к NHS-ому специалисту, которого тоже можно ждать месяцами. Но чаще всего, тебе скажут:"не парься, само пройдет", выпишут антибиотики и отправят домой.

Есть еще вариант обращаться к частному GP и оплатить визит (25-30 фунтов), и от него получать направление к страховым специалистам.

Зубные врачи - это исключение из правила "медицина бесплатна". Даже NHS-ные зубные чего-то стоят, а частные зубные стоят в разы больше. Зубная страховка обычно делается отдельно от основной медицинской страховки.

Я из местной медицины общался в основном с зубными и ими в принципе доволен. Моя жена общался с врачами больше меня и все плановые осмотры делает Киеве, куда она регулярно приезжает.

Поиск жилья

Обязательно надо приходить и смотреть, как построен дом и что у него внутри. На фотках это не видно. Надо понимать, что фото на сайтах недвижимости делаются обычно широкоформатным объективом и, соответственно, в жизни все сильно меньше. Надо смотреть, где расположен дом, далеко ли он от школы, удобно ли добираться до работы и на чем. Мы искали жилье для съема два раза, оба раза делали это сами (через rightmove), без обращения к агентам/посредникам.

Хозяин жилья всегда будет представлен каким-то агентством, с которым ты и будешь общаться (но можно и нужно получить у них прямой контакт хозяина). Хорошее жилье расходится быстро, поэтому всегда надо смотреть только на объявления, которые появились в последние дни. Все остальное (что не сдалось за неделю, а уж тем более за месяц) будет ужасом. При оформлении договора аренды с тебя возьмут депозит в размере 1 месяца аренды, который должен быть помещен в Deposit Protection Scheme и который тебе вернут по окончании аренды. Договора аренды бычно небольшие (3-4 страницы), их надо внимательно читать. При оформлении агенство будет делать для тебя background check, которые оплатишь ты (~100 фунтов). Договор лучше оформлять на себя и на супругу/супруга, потому что договор аренды может служить proof of address, а он очень часто нужен.

Еще надо помнить, что нельзя снять дом не имея счета в банке; нельзя открыть счет в банке, не имея proof of address; сложно получить proof of address, не имея жилья. В самом начале надо выбить из работодателя документы, достаточные для того, чтобы открыть счет в банке, а потом уже можно снимать дом.

Вообще надо заметить, что отношение к жилью тут спокойно-потребительское, много мелких или плохо построенных домов. Привыкнуть к этому тяжело. Соответственно, поиск жилья может затянуться.

Что еще для меня оказалось другим

Продукты -- в целом лучше, но сильно меньше выбор молокопродуктов. Общественный транспорт хороший, но дорогой. Дороги хорошие. Мы прожили три года без машины (так как для поездок на работу она не нужна), но сейчас я понимаю, что это было зря и машину лучше покупать сразу. С детьми машину лучше иметь, проще добираться в школу/в клинику/на кружки и кроме того можно и нужно поездить по стране. Детские кружки-секции оказались сильно проще, на профессионализм ведущих рассчитывать не приходится и нужно сильно искать места, где учат углубленно или профессионально. Культурная жизнь сильно лучше (говоря про Лондон). Ровные климат, без резких перепадов (зимой теплее, летом прохладнее, можно 7 месяцев ходит в одной куртке). Много дождей, много ветра. Природа (леса, парки, заповедники, маршруты для прогулок и туризма) сильно лучше. Вместо бродячих собак и кошек будут бродячие лисы и белки. Потрясающее отношение к истории и ее сохранению - куча музеев, памятников архитектуры и т.п. Людям в массе своей абсолютно все равно, что ты иммигрант, откуда и когда ты приехал и т.п. - за семь лет я столкнулся с одним довольно-таки средним случаем воспаленного "понаехали тут".

Возможно, продолжение следует.

This entry was originally posted at https://dastapov.dreamwidth.org/130369.html. Please comment there using OpenID.

(Read Comments |Comment on this)

Galactic Puzzle Hunt - 2018
Что-то я давно ничего не писал. Напишу-ка я про то, как мы поучаствовали в Galactic Puzzle Hunt


Я люблю головоломки. Что я люблю больше головоломок - так это игры, построенные на головоломках. Еще лучше - если в эти игры можно играть командно, соревнуясь с кем-то другим. Сто лет тому назад я с громадным удовольствием участвовал в AutoQuest и подобных ему мероприятиях в Киеве, но после переезда в Лондон случился перерыв.

И вот весной этого года коллеги пригласили меня поучаствовать с ними в MIT Mystery Hunt, это было безумно интересно (и заслуживает отдельного рассказа).

Одна из команд, регулярно участвующих в MIT Mystery Hunt, делает свой puzzle hunt. Он длится целую неделю, не требует личного присутствия, и называется Galactic Puzzle Hunt. Воспоминания о MIT Mystery Hunt были еще совсем свежи, и мы с женой тут же решили участвовать.

Я попытался привлечь кого-то из коллег, и в результате с нами было еще 3 человека, но из-за стечения обстоятельств все они были без опыта подобных мероприятий и среди них не было никого из "MIT-шной" команды.

Приборы и материалы

Правила простые - у тебя есть логин на сайте соревнования, в час "Ч" там становятся доступны задачи. Ты решаешь их, отсылаешь ответ (строку латинских символов) через веб-форму и в случае правильного ответа тебе открываются новые задачи.

Объединяющей темой этого puzzle hunt был "Great Galactic Bake-Off", поэтому совершенно не удивительно, что изначально на странице было 0 задач и одна громадная картинка печенья и надпись "Next puzzle unlocks at 200 cookies". Все это очень напоминало Cookie Clicker и мы принялись кликать :)

Счетчик печений перевалил за 200, мы получили первую задачу и надпись "Next puzzle unlocks at 2000 cookies" и "Prize for next solve is 2M cookies". Стало понятно, что вручную далеко не уедешь, но мы вручили компьютер младшему ребенку и он бодро накликал нам 2000 печенек и еще одну задачу. Следующий рубеж был в 20К печенек, поэтому мы бросили кликать и стали читать правила. Выходило так, что для победы надо было набрать миллиард(!) печенек, так что оставалось только надеяться, что в дальнейшем призы за победу будут более щедрыми.

За исключением меня и жены все остальные участники нашей команды были территориально разобщены, поэтому для координации у нас был Slack. Выбран он был из-за того, что мне понравилось использовать его в ходе MIT Mystery Hunt - для каждой задачи заводился отдельный канал в Slack, в канал добавлялся расшаренный документ Google Sheets, и все решение делалось уже в нем.

Вообще Google Sheets был одним из основных инструментов, даже если задачи были полностью текстовыми. В любой задаче нужно было так или иначе возиться с текстом - брать первые/последние буквы, сортировать, читать задом наперед и т.п., и в Sheets это делать на порядок удобнее. Кроме того, у Sheets есть killer feature - в него можно добавлять свои функции, написанные на яваскрипте, и мы сделали себе кучу функций вида "выбрать гласные", "выбрать согласные", "отсортировать символы в строке", "пересечь две строки как множества" и так далее.

Впрочем, обо все по порядку.

The Wepp Perflontus Bake Off

В этой задаче надо было реконструировать рецепты, частично переведенные с "инопланетного" на английский и испечь печенье, добавляя компоненты рецепта по одному в "печку". У нас было целых два любителя что-то приготовить, и поэтому идентификация рецептов прошла довольно споро, и печенье сделать было не очень тяжело. Но затем нам надо было сделать Wepp Jarpagom, и тут мы забуксовали, так как слово Jarpagom было только в одном рецепте, название которого было похоже на "Jarpagom pie" :)

Тут мы застряли где-то на час, пока внимательное чтение примечаний к меню не навело нас на мысль, что это праздничный pie, причем не новогодний (не mince pie). Где-то через минут 15 подобрался Pumpkin pie и ответ Great Pumpkin.

Try and Eat
Эту задачу мы решили задом наперед :) Идея была в том, что ты отгадываешь два списка трехбуквенных слов, а потом слова из одного списка "едят" слова из другого списка, и PIN, "съедающий" DOG, дает DOPING. Для проверки своих ответом есть еще один список подсказок посложнее, дающий шестибуквенные слова.

Мы же начали с того, что решили все шестибуквенные слова, потом решили один список трехбуквенных, потом обнаружили, что можно "вычитать" трехбуквенные слова из шестибуквенных и остаток тоже будет словом! По задумке организаторов финальный ответ получается из списка шестибуквенных слов, но у нас-то этот список был исходным пунктом, а не результатом, так что мы довольно долго протупили, прежде чем вычитать из первых букв шестибуквенных слов заветное "cloud place eats hotel" и отгадать "skinny"

An Eccentric Crossword
Эту задачу решил мой коллега Chen, так что я скажу только, что это был кроссворд, в котором кроме слов по вертикали и горизонтали были слова "по орбитали", вот так:




Math 101
Эта задача мне очень понравилась. Ты решаешь multiple-choice тест по математике, ответы трактуешь как двоичные числа, которые кодируют буквы из алфавита по их номеру. Получаешь слово "HEXADECIMAL" и теперь тебе нужно решить тест еще раз, но в этот раз все числа читать как шестнадцатеричные, причем "A)21, B)31, ..." означают на самом деле 0xA21, 0xB31 и т.д.

Тут я подложил нам громадную свинью, так как в тесте был вопрос "какие из этих чисел в восьмеричной системе являются палиндромами?", и я перевел числа в восьмеричную систему прямо в таблице, где мы записывали ответы. Когда же мы начали решать тест еще раз, читая числа как шестнадцатеричные, я уже об этом забыл. В результате в этом вопросе у нас прочитались совершенно неверные числа и вышло так, что правильных ответов вроде как и нет. До перепроверки у меня дошли руки только на следующий день :(

Emotion Pictures
В этой задаче надо было идентифицировать фильмы по краткому пересказу их сюжета, записанному в emoji, вот это например Scary Movie:



Фильмы мы опознали довольно быстро, и героев (обозначенных знаками вопроса) идентифицировали тоже довольно резво, а потом застряли. Никто из нас не знал, что существует фильм The Emoji Movie (у которого на imdb рейтинг 3.1(!)), и только
шальной запрос в google вывел нас на него. Как и в Math 101, задача была по сути решена быстро, но финальный шаг дался только на следующий день.

Stackables

Мы не поленились нарезать из бумаги два комплекта этажей лабиринта и сложить их независимо друг от друга. И не зря - в процессе сверки было найдено несколько лаж. Дальше надо было зарисовать "ваш путь, вид сбоку", и по задумке авторов надо было рисовать путь линией. Мы же рисовали его, закрашивая клеточки в sheets, и в результате наш путь получился таким толстым, что мы чуть не пропустили слово, которое в результате нарисовалось :)

Sequencing

Теперь я знаю много лишнегонужного и полезного про секвенсирование генов :) Вместо того, чтобы взять BLAS, мы, как настоящие тормоза первооткрыватели, сделали все вручную. Не с первого раза. И только со сторонней помощью :)

В промежуточных результатах после первого шага решения на видном месте лежала фраза NEEDLEMAN WUNSCH ALIGNMENT, но поскольку мы раньше этих фамилий не слыхали, то ссылку пропустили :(

Interstate Commerce

Тут моя жена показала себя человеком действия, а я оказался ленивцем томной неги :) Я подумал о том, что надо найти места пересечения шоссе американской interstate system, но я не нашел удобной карты или сайта для этого и забил. А моя жена сделала карту в google maps, нарисовала на ней все пересечения и шоссе, границы штатов, и выписала штаты, через которые этот маршрут ведет.

Мне осталось прийти с работы вечером на следующий день, увидеть решение и офигеть :)

Parlor

Я ухитрился увидеть faux pas в обведенных лапках лисы (fox paws) до того, как это сделали англичане :) Дальше мы довольно бодро разгадали все ребусы, кроме багета (bag wet), на который ушло довольно много времени. Grand prix нам не дался вообще, но задача решилась и без него.

Everything and More

Суть задачи такова: найдите ответы на список вопросов. Долго тупите над ответами. В конце-концов кто-то заметит, что среди них слишком много аббревиатур и редких букв. Вычеркните из ответов полный английский алфавит, а из остатков сложите новое слово. Сделайте так шесть раз, для шести списков вопросов. Возьмите получившиеся шесть слов, вычеркните из них полный алфавит, а из остатков получится финальный ответ.

Тут нам и пригодилась возможность писать свои функции для sheets - мы сделали функции "какие буквы остаются, если вычеркнуть алфавит" и "каких букв не хватает до алфавита" и после этого довольно быстро разобрались с начальными вопросами. Затем мы застряли на том, что финальные шесть слов никак не хотели покрывать алфавит - все время какие-то буквы оставались пропущенными. В конце-концов Чен написал программу, которая перебирает списки синонимов для всех шести слов, и ищет набор, который покроет-таки алфавит. Увы, ответ таким образом найден не был, и мы читали и перечитывали код несколько раз, пока кто-то не заметил, что у "facing (2, abbr.)" кроме "op" может быть еще решение "vs", и тут наконец паззл сложился.

Trigger

Еще одна задача, которую мы решили наоборот. В тексте было просто-таки уникальное количество намеков на тригонометрию, но мы их все пропустили. Только начав решать задачу как кроссворд мы заметили, что слишком много слов начинаются на "cos" и "tan". "Ааааа!", - сказали мы - "вот к чему был Trigger в названии и SECret COTs в описании, это был намек на тригонометрию, могли бы и сообразить". Надо наверное как-то превратить слова в числа и посчитать значения тригонометрических функций от этих чисел. Вот, например, короткое слово "tank", которое в такой интерпретации будет tan(k). Берем номер буквы "k" в алфавите (11), получаем -225.95..., а структура места для ответа прямо намекает, что должно быть три знака до запятой и много знаком после. Но это получается только в том случае, если это 11 радианов, а не 11 градусов. "Аааааа!", - сказали мы - "вот что значит pretty rad в условии. Могли бы и сообразить".

Дальше мы стали думать, как переводить длинные слова в числа и перебрали какое-то невероятное количество способов, пока случайно не "выстрелило" произведение номеров букв в алфавите. "Аааа!", - сказали мы, - "вот что означало when they go into production, могли бы и догадаться".

Последним сюрпризом было то, что один из вопросов звучал как "dissection puzzles" (во множественном числе) и ответом должен был быть "tangrams", а мы взяли "tangram", из-за чего у нас получилось неправильное число в ответе и совершенно неподходящая буква.

Consolation Prize
После решения предыдущей задачи у нас должно было быть достаточно "печенек" для того, чтобы получить следующую задачу. Вместо этого у нас появилась ссылка на "утешительный приз", а по почте всем нам пришло письмо: "Всем спасибо, команда COOKIECOOKIECOOKIE выиграла соревнование, расходимся. Вам, чтобы вы не грустили - утешительный приз".

Это было очень неожиданно и очень обидно. Как они могли успеть все решить за два дня? Сколько у них в команде человек? Профиль команды неожиданно показал, что в ней всего один участник - "me", и у нее ноль решенных задач.

Сразу после того, как мы посмотрел их профиль, тебе приходит следующее письмо: "We were unable to contact team COOKIECOOKIECOOKIE to claim the one billion cookies that they baked. Moreover, we found that the team did not even solve a single puzzle, which is very much against the spirit of the hunt.
This is an unprecedented situation that we had not foreseen. While we are investigating this suspicious behavior, we would greatly appreciate if you can help us identify who this team is, perhaps by investigating the consolation prize in detail."

Фух. Это всего-навсего следующая загадка :)

При переходе по ссылке "утешительны приз" тебе показывалось окошко с надписью "мы, команда COOKIECOOKIECOOKIE, выиграли соревнование в этом году. Не грустите, вот вам немного нашего печенья". Ниже были фотографии нескольких разных по виду печений.

Мы смотрели на них и так и сяк, читали и перечитывали текст, несколько раз перечитали правила и FAQ, но мыслей не было вообще никаких. Пока внезапно не обнаружилось, что содержимое страницы "утешительный приз" изменилось. Теперь там было другое печенье. Мы стали перебирать в памяти, что мы делали и что могло к этому привести. Скорее всего, это процесс, привязанный ко времени, ведь мы не делали ничего такого особенного. И через минуту-другую страница опять изменилась. А потом 15 минут не было никаких изменений. Если вы смотрели "Пятый элемент", то помните финальную сцену, в которой главгерои пытаются понять, как же использовать "супер оружие".

У нас была совершенно такая же тема: мы что-то сделали, страница изменилась, и никто не понимал, что именно. В конце-концов выяснилось, что один из членов нашей команды в процессе от нечего делать кликал по печенью над списком задач, чтобы набрать пару сотен очков и обогнать ближайшего соперника. Он обогнал их и перестал кликать :)

Содержимое страницы зависело от количества очков! Довольно быстро мы выяснили, что всего печенья - двенадцать видов, и каждое из них появляется на странице с определенным периодом (от 1 до 12). Дальше мы накликали количество очков до ближайшего числа, которое делится на 2...12 без остатка и увидели все виды печенья.

Fun fact: xdotool click --repeat 2051 --delay 140 1 кликнет за вас 2051 раз, а вам надо будет только сидеть и наблюдать :)

Это была так называемая meta puzzle, в которой надо было использовать решения предыдущих задач, чтобы собрать из них ответ для этого "этапа". Но вот беда - у нас не была решена одна из предыдущих 12 задач. Оказалось, что можно обойтись и без нее - если отсортировать печенье в порядке возрастания периода, поставить каждому из них в соответствие ответ на предыдущую задачу (там было тематическое совпадение), и для печенья с периодом N взять из ответа N-ую букву, то получалось "MEWANTC?OKIE". Оставшаяся буква легко угадывалась :)

Если кому интересно посмотреть - вот ссылка на документ с решением

Word Search
Ты даешь отгадку, тебе говорял edit distance до правильного ответа. Чен сделал ее минут за 15, еще до того, как я добрался прочитать условие. Самая незаметная загадка мероприятия.

Layover

Совершенно замечательная задача. По тексту описания надо было выйти на сайт со схемами самолетиков, распечатать картинки вроде вот этой, сложить из нее самолетик и прочитать на нем надпись:


Неожиданно самым большим препятствием для нас стало то, что схемы были рассчитаны на US Letter, а у нас была только A4, и поэтому самолетики приходилось "подгонять по месту".

Anagram Solver

Моя жена взяла эту задачу фактически в одиночку, и хоть в процессе мы и запросили подсказку у организаторов (каждой команде раз в сутки давались два "билетика" для мелкой подсказки) это было очень круто.

Может авторы и видели себе ручное решение 120 анаграм, но мы еще для MIT Hunt наколхозили скрипт для поиска анаграмм в SOWPODS (это словарь для игроков в scabble), и малая механизация тут здорово помогла :)

Destructive Interference
Вычти шум из записи, чтобы услышать ответ. Я сдался, но Чен с помощью audacity и такой-то матери это сделал. Неожиданно сложная задача, как по мне, выбивающаяся из общего уровня.

Make Your Own Fillomino

Задача, в которой код победил интеллект и написанный кем-то на коленке солвер решил все за минуту. Я открыл ее уже после того, как она была решена.

Special Snowflake
Third time is a charm :) Еще одна (третья!) задача решенная нами не то чтобы задом наперед, но тут мы тоже пропустили ряд зашитых в условие намеков и создали себе дополнительные проблемы на ровном месте.

Тут надо было отгадать 15 трехбуквенных слов, вписать их в треугольники так, чтобы в каждой вершине была букв, а затем сложить из треугольников снежинку Коха так, чтобы вокруг нее читались слова. Нам пришлось просить подсказку у организаторов, и только после того, как нам сказали, что все слова будут пятибуквенные, мы сдвинулись с места. Пришлось распечатать несколько снежинок и крутить их вручную. Хоть это и была одна из 12 "стартовых" задач, мы решили ее только ближе к финалу соревнования.

Split the Reference

Приз зрительских симпатий :) Задача состоит из вопросов, ответами на которые могут быть одновременно как герои из вселенной Star Wards, так и персонажи из Harry Potter. Например, "фамилия дяди и тети, у которых главных герой живет в начале повествования". Дальше тебе надо взять определенные буквы из ответов и выбрать букву из алфавита, которая стоит ровно посередине между буквой из Star Wars и буквой из Harry Potter (split the reference -> split the difference).

Missing Pieces

Задача, в которой мы обхитрили сами себя. Это такой гибрид полимино и судоку, который нужно сложить на доске 6х6. Изначально у нас была версия, что полимино можно класть только так, чтобы цифры были правильно ориентированы. Версия была правильной, но почему-то попытка быстро сложить первый набор вручную провалилась. Тут я подумал, что части можно вращать, а поскольку вручную их вращать и складывать было лень, я решил написать програмку. И я ее написал, но вот беда - она выдавала слишком много решений. И мы смотрели на эти решения и так и этак довольно долго времени, пока я не попробовать убрать вращения, и внезапно оказалось, что решений для каждого цвета всего по два, и отличаются они только расположением цифр для судоку.

Тут мы затупили второй раз. На каждой доске было 12 клеток пустого места, и мы решили, что missing pieces - это указание на то, что надо посчитать, как будут выглядеть полимино, закрывающие эти дырки, и из всех таких кусков что-то сложить. У нас же для этого и программа есть! Но вот беда - толком ничего не складывалось.

Потребовалась подсказка о том, что нам нужно искать different kind of missing pieces чтобы начать думать в правильном направлении :)

The Answer to This Puzzle Is...

Тут мы прокололись (чуть-чуть) на нетщательном ведении записей. Ты как бы путешествовал по графу, в котором вершины - это вопросы, а ребра - это ответы, но тебе об этом не рассказывалось - у тебя было поле для ввода, ты вписывал туда ответ (или один из ответов) на текущий вопрос, а тебе говорили "нет, ответ неверный. На самом деле ответ на эту задачу - это (и тут какой-то новый вопрос)". В головоломке было 49 вопросов, и в какой-то момент мы увидели, что у большинства у них ответы только на буквы N/S/W/E. Я попробовал нарисовать карту, но Что-то Пошло не Так, и я убедил себя, что первые буквы ответов не означают north/south/west/east (хоть это было и не так). Мы вели список вопросов и отмечали в нем те, для которых мы уже перебрали все ответы, но умудрились один вопрос пропустить.

В конце-концов вопросы и ответы были засунуты в gtaphviz (точнее в neato) и по получившейся картинке мы нашли все свои пропуски:


Увы, до того, что надо навести все ребра, которые going back to the United Kingdom, мы додумались только после второй подсказки.

Не шмогли

Я брался решать Adventure, но не увидел зашифрованного в игре основного условия задачи, и забил. Мы почти сделали Overtime - коллекцию задач, похожих на Puzzle Hunt прошлого года, но "почти" оказалось недостаточно, и без недостающих кусков код не взялся. В Unusual and strange puzzle collection мы застряли на извлечении текста из решений, и так ничего и не придумали.

Ближе к концу соревнования я затащил в команду коллегу - любителя cryptic crosswords, и он решил нам кроссворд из Earth-shattering, и это было просто потрясающее зрелище. Я бы в жизни не додумался, что "Chunk of wood halted early came back" - это slab, потому что wood - это balsa, "balsa halted early" - это "bals", а "came back" - это наоборот, и соответственно из blas получается slab. А в этом кроссворде плюс ко всему в каждом вопросе одна буква была заменена на "o", и сначала надо было догадаться, какая именно (Big biro eaten by a lemur -> Big bird eaten by a lemur -> emu). Увы, мы застряли на получении ответа из решенного кроссворда и нарисованного поверх него сердца, и даже две подсказки нас не спасли.

У нас были все шансы сделать o ea / Wrd Srch, но не хватило времени. Мое личное достижение - это реконструировать из "aae ae a oao o O, i e ia o O (7)" фразу "Character taken by a tornado to Oz, in the Wizard of Oz", а из "Iae o a Aeia Ee ei a (9)" - "Image on an American Express credit card". Дальше надо было комбинировать гласные и согласные из разных слов и вписывать их в решетку word search, но увы - состязание закончилось раньше.

Результат

Мы заняли 120 место из 450-500 команд, если считать за участников тех, кто хоть раз кликнул по печеньке. Мы были близки к решению еще двух задач, и как-то начали решать еще штуки 3-4, но было видно, что мы упираемся в предел своих возможностей.

Надо больше активных участников, коллективно такие задачи брать проще

Если такая штука будет в следующем году, обязательно участвуем :)

This entry was originally posted at https://dastapov.dreamwidth.org/130008.html. Please comment there using OpenID.

(Read Comments |Comment on this)

0x28
Время идет. Борода стала чуть седее. Дети стали чуть старше. Пережит один переезд и 0.1 ремонта. Пройдено 1400 км. Сменил метро на поезд, а лис - на зайцев. За окном проезжают brexit, MIFID и Трамп. Перезимовали суровую английскую зиму с метелями и снегопадами. Минус две социальные сети. Плюс три настольных игры. Много планов, но мало веремени (но это лучше, чем наоборот :)

Спасибо за поздравления!

This entry was originally posted at https://dastapov.dreamwidth.org/129579.html. Please comment there using OpenID.

(Read Comments |Comment on this)

Как я переезжаю в dreamwidth, часть вторая: фиксим ссылки
У меня в ЖЖ было куча ссылок между постами, и я хотел в DW поправить их так, чтобы они вели на соответствующие посты в DW.

Оказалось, что все велосипеды уже придуманы до нас :) Вот тут человек наколхозил скрипт, который пробегает по архиву, сделанному ljdump, собирает соответствия между URL-ами в ЖЖ и DW, правит посты и обновляет их в DW.

Из коробки скрипт у меня не заработал, пришлось его чуть поправить, чтобы он умел работать с ЖЖ-никами, в которых есть подчеркивания (как это было у меня). Результат на github-е (https://github.com/adept/ljdump/blob/master/fix_links.py), запускать из директории с результатами ljdump.

Оно будет показывать diff для всех поправленных постов и после подтверждения обновлять их. Можно выбрать альтернативную программу для сравнения через переменную окружения DIFF.

Я запускал так: DIFF=patdiff ~/path/to/fix_links.py

Вроде бы как все переехало нормально, ссылки поправлены, ничего не поломалось.

UPD: Заодно, вписав в скрипт пару строк вида url['вот это']='заменить на это', пофиксил все картинки, которые поломались после того, как dropbox закрыл public фолдеры. Красота!

This entry was originally posted at http://dastapov.dreamwidth.org/129372.html. Please comment there using OpenID.

(Read Comments |Comment on this)

Как я переезжаю в dreamwidth
Сказал сделать импорт всего, importer отругался, что "Unable to load FOAF data", но вроде все из профиля втянул. Что ему не нравиться - неясно, в ЖЖ по ссылке /data/foaf все отлично отдается.

Взял ljdump.py отсюда, добавил два патчика отсюда и выкачал им все из ЖЖ и из dreamwidth.

С помощью bash и patdiff сравнил выкачанное, наколхозив вот такой скрипт:

#!/bin/bash
lj="$1"
dw="$2"
for l in ${lj}/L-* ; do
    l_url=$(xmlstarlet sel -t -v "event/url" -n $l | grep -o '[0-9]*')
    d=$(ag -l "/${l_url}</import_source" ${dw})
    d_url=$(xmlstarlet sel -t -v "event/url" -n $d | grep -o '[0-9]*')    
    echo "$l (${l_url}.html) vs ${d} (${d_url}.html)"
    [ -z "$d" ] && { echo "cant find dw post for $l"; exit 1; }
    patdiff -ascii <(xmlstarlet sel -t -v "event/event" -n $l | \
              sed -re 's#lj (user|comm)="?([^ &"]*)"?[^&]*&gt#user site="livejournal.com" \1="\2"\&gt#g') \
            <(xmlstarlet sel -t -v "event/event" -n $d)
done

Страшный sed из-за того, что в ссылки на пользователей ЖЖ dreamwidth добавляет site="livejournal.com" и обязательные кавычки вокруг имени пользователя.

Похоже, не переехало только embedded video, а все остальное - пучком. Настроил кросспост в ЖЖ. Что еще я пропустил?

Что DW делает с френдами, которые тоже переехали сюда? Как-то их вычисляет/добавляет, или нет?

This entry was originally posted at http://dastapov.dreamwidth.org/129182.html. Please comment there using OpenID.

(Read Comments |Comment on this)

So long, and thanks for all the fish
Журнал переехал на https://dastapov.dreamwidth.org/

(Read Comments |Comment on this)

Квестик
Сделал на день рождения жены квест. Кто хочет, может попробовать свои силы тут.

Комменты скринятся

UPD 1:
Я css и javascript/DOM не умею на уровне "читаю со словарем, сталкиваюсь раз в два года", поэтому все простенькое и страшненькое

UPD 2:
Судя по некоторым комментариям, кажется, что там один майнсвипер. Это не так :)

UPD 3:
Первыми на финише отметились:

• catap
  
• x
  
• swizard
  

(Read Comments |Comment on this)

ICFPC-2016: afterparty
Организаторы выложили результаты

Моя скромная команда сползла с 19-го места на 22-е (все равно, я считаю, офигенно для этого подхода к решению).

Первое место, как и в прошлом году, взяли Unagi и вот тут можно посмотреть, как работает их солвер.

Lightning round полностью вручную взял jabber.ru, как уже было, кажется, в 2007-м году.

(Read Comments |Comment on this)

Butt Naked
Ходил на днях в театр смотреть The Book of Mormon. Это такая религиозная сатира про мормонов, как очевидно из названия. Авторы - Трей Паркер и Мэтт Стоун, которые South Park. Сам спектакль более умеренный, чем любая серия South Park, но "талант не пропьешь", и весь спектакль там ездят паровым катком по религии вообще, мормонам в частности, по американцам, рассовым стереотипам и т.д. и т.п.

Все герои, и главные, и второстепенные, имеют вполне обычные имена - за исключением полевого командира в Уганде, который называет себя General Butt-F@#$ing-Naked. Объясняет он это тем, что сейчас он тут будет грабить и убивать, а кто осмелиться сказать слово поперек - с тем он разберется лично, немедля голову долой и все такое -- и делать это он все будет в чем мать родила, отсюда и имя. Удивительно, правда, то, что дальше по ходу пьесы ни имя, ни его поведение никак не обыгрывается и его с таким же успехом могли бы звать Джон Смит. Ну, вполне в духе South Park, ладно.

По пути домой я читаю википедию про спекталь, реакцию на него мормонов и т.п. и тут ВНЕЗАПНО.

(Read Comments |Comment on this)