HTTPS SSH

ICFPC 2018

This is the solution of ICFPC contest of command Wintermute.

This year we were using 2 programming languages for our solution: Java8 and Javascript. From the very beginning we tried to solve 2 separate tasks: Create our own model realization of model and strategies Try to reuse organizers Javascript to get some ideas and reuse it as a reference for automated checking and ranking of out own strategies.

Model and strategies

It turned out that Java8 with it's nice features like Generics and lambdas is lacking functionality crucial for elegant and powerful decision of the tasks like this one: data classes and basic pattern matching.

Our solution contains separate logical layers: 1. Low level. Effective binary representation for data field. It contains functions for bots actions by specification, simple checks. 2. Intermediate levels for long-distance bots navigation, and splitting/merging. Some geom primitives like checking for grounded state, some model statistics like percentage of filled voxels, etc. 3. High level contains strategies realization for assembly/disassemble of models.

Model statistics suggested to use different strategies in different cases, however this time we didn't have enough resources to implement all the ideas. Instead of accurate implementation of all the checks and energy computations we used heuristics to avoid volatile interferences / ability to find way back home etc. It turned out that these worked quite good.

At the very beginning of the Lightning test we started to thinking in 2dimensional space because we have single special coordinate (ground) and others, while all the methods and algorithms can be transformed to 3d space by extending corresponding metrics. 2d space however is much easier to think about for human beings.

Finally we managed to use reference interpreter callbacks for generated models sanity checking. We used Java8 builtin Nashorn engine to execute JS code withing Java Virtual Machine and communications between JS and Java code bases. See detailed information on how we did this in the last section.

In production

One dimensional point filling is used for solving assembly problems. The initial space is splitted by rows, all the cells within one row is processed by one and only one bot. Possible further optimisation is to assign two bots for a single row and use linear GFill for assembling.

Our disassemble strategy works like hot iron: it allocates four bots in square shape and fires all under them by GVoid. There are some optimisation may be applied. First of all we start from the most high non-empty level. Then we can move our "iron" gliding bounding box containing shape on a level. After cleaning a level we move lower until we reach ground.

What we would like to implement but didn't: Split the model into a set of 3d figures (including planes and dots), minimising sum of all coordinates of all the figures, or the smallest number of them covering fixed volume. Next natural step was to use kind of priority queue of construction using metrics of figure volume (the more volume the better) and connectivity to the ground level, which changes during the process. If it would be possible to use validation and energy functionality, we could use try-to-improve algorithms both deterministic and and random ones (genetic algorithms). Use provided trace for all the tasks as a starting point modify it to stay in valid state while decreasing target energy.

Reference interpretation

We used IntellIJ IDEA Ultimate as a powerful tool for ML to JS code de-obfuscation tool. First of all it was really cool to find out changes in the tasks description from the very beginning, including different allowed number of bots and new commands GFill and GVoid. Transformation from ML to JS creates really hacky minified code, because all the executions are transformed to SSA (single site assignment) as well as emulation Optional concepts via arrays of indicator and value. It would be almost impossible to eliminate all the dead code and useless code calls using simple VIM like code editors. We reduced code size from 24k lines to 10k lines, split all the code into logical parts and find out all the callbacks for visualization purposes (later we used it for tracing energy). "Unused code" and "rename refactorings" were the most useful for code analysis and transformations. If would like to get the idea of functional immutable data structures in imperative data language uncomment any of the JSON pretty printing. It would be nice to authors solution, yes, we saw BFS and DFS algorithms in obfuscated code.

Callbacks on success and failure results were used for automated testing from Java. We used Javascript Nashorn Engine for inter-communications between Java and JS. Data was loaded from Java process as byte array and injected to JS code using invokeFunction, because FileReader is not available in it by security reasons. Unfortunately this prevented us from using automated testing from the early stages of this project.

Most of our final solutions were successfully validated by reference JS implementation in terms of results and scores with JUnit testing.

It was super fun to see watch how our own solutions were executed. Organizers team did great job collecting all the figures!

Team

  • Alexander Savin
  • Alexey Zakharov
  • Anton Volokhov
  • Dmitry Schitinin
  • Oleg Shpynov
  • Vadim Tsesko