I did not yet see a thread on the contest, so created one.
See this replay: Coding Games and Programming Challenges to Code Better. I have a TUBE 2 0: between building 2 (landing pad with type 1 astronauts) and building 0 (lunar module type 1). I create a POD 2 0 2, expecting it to go endlessly between buildings 2 and 0.
Why do none of the type 1 astronauts get on this pod to their typeâs lunar module?
EDIT: I found the problem (and leave it here for others that are as stupid as me): the command POD 2 0 2 does not create a pod going from 2 â 0 â 2 â ⊠It creates a pod with id 2, going only from 0 â 2 (and then stops). Hence, instead, I should do POD id 2 0 2.
Hello all,
There is a point in the rules that I may not have understood well.
It is written: âIt is guaranteed that no building will be constructed on the path of an existing tubeâ.
But in test 7 when I draw a route between 24 and 25 it is not accepted because it intersects building 27. Can you explain to me why this is possible?
Thanks you for you help
Congratulation for one of the most complexe game from Codingame.
In one year we will still have new best solutions for sure.
Itâs rare when I donât know how to start even for the simpliest level where I still find new best solution hoping we cannot reach better than 55030
Of course. As all the previous challenges and all future one I guess
There is Contests category and after the game switches in bot programming and sometimes optimization category like for this one.
However optimization is ultimately rare because strong computer (player) try to solve it with powerful computer and algorithm and it less fun because we cannot watch the link VIEW LAST BATTLES to study among the best player.
The game should be in this link https://www.codingame.com/multiplayer/optimization in 7 days max.
Have fun to find +++new best solution in all futures weeks
Very interesting challenge. But I couldnât submit my code for the last 55 minutes of the challenge. Always got the red popup asking for retry in a few minutes. For 55 minutes⊠What happened ?
Yes, this was really fun⊠after I overcame my laziness looking at the complexity and opted in to start off just doing âanyâ solution at all.
Added some fine-tuning later and the final result didnât turn out bad at all.
Already planning to play around with this, when itâs up as optimization challenge without time limit. Want to try out more ways on how to approach this.
I used some pretty standard simulated annealing to select actions for the current month.
Scoring is a combination of points earned and resources left (resource score having a decreasing factor as months go by).
The only notable trick is to not select TUBE actions explicitly, since needed tubes can be computed from POD actions.
I could not get any score improvement from UPGRADE actions so ended up disabling them. Probably something wrong on my end, Iâm sure they can be useful at least on some test cases.
I had to simplify the game rules before I was able to write some algorithms:
Build Tube only together with Pod, moving along only this tube.
Allow building only short tubes (with some tricks), to reduce the time-complexity of the algorithm.
Score is calculated in the simplified way: ignore pods and tube capacities (i.e. astronauts are pedestrians, walking inside the tubes via the shortest path to the closest module). So I did not implement correct simulation â only this simplified version.
Upgrade only if no other tubes can improve the score.
Do not use teleports at all.
With these restrictions and simplifications, it was not so difficult to implement greedy algorithm.
My impressions:
It was not enough time as for me. It would be greater to have the second weekend available.
It was interesting dilemma: to implement full correct simulation, or some simplified, not so accurate, but faster version, or even ignore the whole idea of estimation function and use some heuristics, based on the classical graph algorithms (DSU + BFS/Dijkstra).
A slightly similar situation, python + Scipy for a relatively low-effort solution, I only had 4-5 hours to invest in the challenge.
Create an adjacency matrix for the existing tubes and resize according to the number of points.
Calculate the distance matrix between all the points (scipy.cdist)
Creation of a matrix G corresponding to the minimum spanning tree. ( scipy minimum_spanning_tree(dst) ). If a node is a leaf, it is connected to the nearest leaf. We add the matrix of existing tubes. Iâve tried using Delaunay triangulation, but itâs much less stable than MST when nodes are added. This is probably the part where I messed up because I often had sub-optimal spanning graph. I found myself with a lot of collisions. Especially on rectangles and grids, scipyâs algo doesnât guarantee that the diagonals will always be positioned in more or less the same way.
Choose 10 unconnected gates not served by a pipe network. Calculate the shortest paths between these gates and their destination modules. Choosing only 10 gates is there to avoids time out on certain test case with a lot of paths as the Grid.
Sort and rationalise the number of segments required for a path. Paths that are subsets of other paths are deleted, and paths that are too long are split into smaller ones.
Creation of tubes only when a complete path and its pod can be created.
Lazy ass collision detection: if a tube is supposed to be created and does not appear in the next turn, it was invalid. It is stored in a matrix which is subtracted from G so that the same errors do not occur twice.
Final score ~4K points.
Things I didnât have time to implement:
Generate a better spanning graph G. Main drawbacks of my solution
Upgrading overloaded tubes according to the number of established paths that pass through the tube.
Implementing teleporters based on the presence of clusters of gates and modules.
I didnât like this contest. With the unknown changes to the network in subsequent months, this becomes a âhidden information gameâ. The theoretically optimal play for such cases depends on the probability distribution over possible chance events, i.e. future changes to the buildings and resources. Contrary to the more typical head to head games, there is no Nash-equilibrium distribution, nor is any distribution to be found in the source code - itâs the distribution over possible test-cases as arbitrarily chosen by the challenge designer. Now the example test-cases makes it very obvious that the test-cases are not drawn from a âuniform distributionâ (whatever that means), but an extremely sparse distribution. Therefore, winning this challenge amounts to correctly âguessingâ what the test-cases will look like. At this point, you are going to make dedicated semi-hardcoded solutions for each of the test-cases. This is exacerbated by the extreme size of the game tree, making it hopeless to search for the optimal solution for any reasonably wide dsitribution. So, basically, itâs just throwing dice.
For me, it appears to be #214 or so after the re-run (when I last checked before the re-run, I was around ~50, but thatâs a couple days ago). I started with a generic low-effort python solution using scipyâs Delaunay triangulation and graph shortest-path as-well, but never even attempted to solve for optimal ressource allocation, once I realised the example distribution is so sparse. Instead, I hard-coded very simple low-effort solutions for grid, villages (which was good on the high-resource test-case before the update but failed the low-resource verifications case), spiral and distribution network. There are definitely some of the test-cases which have more randomness and thus benefit from an actual simulating strong solver, for which I would have switched to C++. But given the dependence on unknown test-case distribution combined with the notoriously outdated C++ compiler and standard support here on CodingGame, I didnât want to spend the effort and lost interest.
I tried to get some colleagues to join, but some of them have been fraightened by the length of the rules. With the classicals challenges with he leagues system, the rules come gradually, so itâs a bit easier to dive in.
However, for those who try to submit the given sample, it makes the things really clearer, and it is so addictive when you dive in. I had a lot of fun hardcoding the first solutions with my little son!
In terms of strategy, I didnât use the classic path-finding and prediction algorithms, because I found the rounds complicated to simulate (risk of tubes not being created, with their associated pods, and therefore unused resources ⊠and the risk of finally code during the whole week and donât have anything at the endâŠ).
My code is therefore mainly based on
(many) tubes with a single pod that goes back and forth
and rarely, teleporters to complete the network (but only as a secondary option, if there are resources left)
I reached a real milestone when I implemented collision detection (the algorithm for which was in the statement, thanks for that too )
So pleeeeease do more optimisation contests. I understand it might be less accessible to classical bots contests, but it is soooo fun! Ended around #150, so I think it is much more accessible than it seemed.
I was #48 for 5.7 M. The rerun donât change nothing for me.
My strategy was pretty simple #48 :
Make fitness function to evaluate solution. The fitness use distance from landing to the right base.
When iâm building a TUBE, i build also associated POD. So all my POD are associated at only one TUBE.
Enumerate all pair TUBE / POD that are interesting to build.
I evaluate the result of each construction individually. I sort this result. Then, I will try different associations to find an optimal combination of construction
I had to adjust the fitness function to make it favorable to use teleport on case 12. The main idea, that the teleport can be benefit if we build it in for four first turn. And I evaluate the gains on future astraunauts
I use Referee function for collision. My code is in Java :-). I do only one optimization. I make a cache for the squareRoot function.
Ended up 141 with score 5 000 745 (a bit less than the given sets of tests)
I wrote a post-mortem here
also here is my tool to benchmark my solution locally.
Thanks Codingame, always great challenges, see you in winter
