This is the solution of ICFPC contest of command Wintermute.
This year we were using 2 programming languages for our solution:
From the very beginning we tried to solve 2 separate tasks:
Create our own model realization of model and strategies
Try to reuse organizers
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.
Java8 builtin Nashorn engine to execute
JS code withing Java Virtual Machine and communications between
Java code bases. See detailed information on how we did this in the last section.
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
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.
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
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
DFS algorithms in obfuscated code.
Callbacks on success and failure results were used for automated testing from
Nashorn Engine for inter-communications between
Data was loaded from
Java process as byte array and injected to JS code using
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
It was super fun to see watch how our own solutions were executed. Organizers team did great job collecting all the figures!
- Alexander Savin
- Alexey Zakharov
- Anton Volokhov
- Dmitry Schitinin
- Oleg Shpynov
- Vadim Tsesko