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.
Bonjour,
Je suis un peu écœuré : j’ai perdu 1 M de points entre mes dernier runs et le Rerun officiel (donc je passe de 96è à 277è…), alors que mon score était comparable entre le jeu de test et le jeu de soumission… Mon programme n’était probablement pas assez fort pour faire face à toutes les situations, mais peut-être que le jeu de test caché était aussi très différent… #blazé
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.
Même déboire ici, je suis passé d’une position entre 70è et 80è à la fin à 226è au rerun final.
Dans mon cas, ma dernière version était en chantier et obtenait un score similaire à celui du rerun final, soit 1M de moins que le meilleur que j’ai fait avant.
Je me pose donc également la question suivante : Le rerun final s’appuie-t-il sur le code de la dernière soumission ou sur le code de la meilleure ? (idéalement j’aurais tendance à faire un double rerun et à retenir le meilleur score entre la dernière et la meilleure).
J’ai aussi constaté que pendant le challenge, le nombre de participants était entre 1500 et 1800 (sauf au début ou c’était moins de 1000) hors au final, il y a plus de 3000 personnes indiquées au rerun. Bref, je serais intéressé par quelques explications du fonctionnement à cet endroit (notamment quelle version du code est utilisée au final, pour ne pas faire des essais audacieux vers la fin du timing si ça risque d’être pénalisant).
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
Ils ont dit sur le discord qu’ils utilisaient ton meilleur submit et également le dernier. Ils scorent les 2 et utilisent le meilleur score. Mais du coup le fait surprenant c’est que ton meilleur score a fait 1M de moins qu’avant. Si tu le push plusieurs fois, quelle est sa variance ? Une variance de 100-300k est assez standard mais 1M me surprend pour un code qui faisait top 100 sur les scores provisionals. Un code qui fait parfois 3.2M et parfois 4.2M ne me surprend moins pour du MC full random:) tu as peut être trop overfit sur les jeux d ide et de submit ?
