Fall Challenge 2024 - Feedback and Strategies

[lD1]

Thanks for sharing this, it’s really interesting to see how you organize yourself to improve your dev process. I might try your tool when the game falls in the puzzles category
I just learned through your repo that the arena input files where in the original game repo … helpful for next contests

[1000i100]

Sinon, coté défi, je me suis vraiment régalé !
J’ai un peu galéré avec des héritages de types en TypeScript, mais je me suis régalé à approfondir les algos de proximité de graph (Delauney, Gabriel, RNG…) avec plus de temps, je serais aussi allé sur du A-star, je pense.

Les téléporteurs

J’ai commencé par faire du tout téléporteur, et j’ai atteint plus de 3M comme ça (je crois 3.5M).
Pour ce faire, je regardais quel TP pouvais déplacer le plus de personne d’un type vers une cible de ce type.
Puis après avoir ajouté des tubes (j’y reviendrais) j’ai perfectionné le ciblage des téléporteurs :

• destination éloignée si possible
• cardinalité de la destination (et du départ) aussi haute que possible (plus il y a de tubes, voir de connexion directe possible, mieux c’est)
• diversité des voisins maximale (et si les voisins correspondent à d’autres types que l’émetteur a, c’est encore mieux)
• réseau différent mais pas noeud isolé autant que possible, puis si toutes les couleurs sont reliées, même réseau pour optimiser la répartition plutôt que noeud isolé.

D’abord je choisi parmis les site d’atterrissage celui qui me semble optimal, puis pour un émetteur, je cherche la cible optimale, puis je boucle.

En priorité par rapports aux tubes, si s’il y au moins 120% du prix d’un TP et qu’il y a un site d’atterissage à type unique et une destination compatible, alors je fait le TP en priorité, sinon je fais les tubes en priorité, et les TP s’il reste du rab.

Également, j’exclus des départs comme des arrivées les nœuds ayant en voisinage effectif ou potentiel des nœuds avec déjà un téléporteur.

Les pods

presque jusqu’à la fin pour chaque tube construit j’y associai un pod et basta (pas d’upgrade, de vente ou de comportement plus poussés).

Sur la fin, notamment pour les scénarios très contraints du côté finance, j’ai tenté de décorréler les deux, mais résultats mitigés.
Le principe : entre bâtiments déjà présents, je construis un tissage que je détaillerai dans la partie Les tubes, puis parmi ces tubes :

1. je mets un pod dédié pour chaque site d’atterrissage relié à un type inclut sur ce site.
2. ensuite pour chaque nœud non desservi, j’ajoute un pod qui va sur tous les tubes adjacents les uns après les autres. (j’appelle ça des starPod, qui ont le même ID que leur noeud de référence) avec pour priorité les nœud ayant un nœud voisin déjà desservi.
3. s’il reste des tubes non desservis, j’ajoute un starpod sur le sommet voisin qui à le plus de tubes non desservi et en second lieu le moins de tubes total. (s’il y a déjà un starPod pour ce sommet je le vends, c’est le seul cas ou je vends pour l’instant)
4. tant qu’il y a des tubes sans pod dédiés, j’en ajoute
5. une fois que tous les tubes ont au moins un pod dédié, j’upgrade les tubes traversés par plus de pods que leur capacité, avec une priorité en fonction de la fréquence d’encombrement (un starPod à 2 branche + un pod dédié est plus encombré que si le starPod est à 5 branches)
6. j’ajoute un 2nd pod dédié aux voisins de destination de téléporteur
7. (en projet) j’ajoute un 2nd pod dédié aux voisins de voisins de destination de téléporteur

Vers l’étape 4 (avant ou après je ne me rappelle plus) je peux ajouter des téléporteurs pour mieux répartir la desserte.

Malgré tout, sauf sur le scénario des villages, je ne crois pas avoir amélioré mon score par rapport à 1 tube = 1 pod dédié (en fait, si, sur les 4 premiers tableaux, mes optimisations de pods ont payé, mais en score global, c’est 3 fois rien)

Les tubes

J’ai tout de suite cherché un algo de maillage, j’ai commencé par une triangulation de Delauney, puis j’y ai rajouté le sous-ensemble Gabriel Graph et le sous-ensemble RNG, j’étais aussi tenté d’en ajouter d’autres (Urquhart graph, ACM/EMST/RMST, MBST, Principal Curves…) mais par manque de temps je n’ai pas creusé davantage.

J’ai ensuite travaillé avec les arrêtes retenues par la triangulation, bonifiées d’une pondération si elles font partie de sous graphe plus optimisés (GG et/ou RNG).
J’ai commencé par les élaguer des tubes existants ou en collision avec l’existant.
Avec ce sous-ensemble d’arêtes, j’ai fait un scoring par arête pour les trier et prioriser leur construction (et supprimé celle à score nul).

Lorsque des bâtiments sont reliés par des tubes, je crée un objet commun pour le sous graphe avec tous les types atteignables et les astronautes en errance (à destination d’un type absent du sous graphe). Les sous graphes reliés par des téléporteurs ne sont pas fusionnés, mais les astronautes suivent dans le sens du TP et les destinations cible sont considérés comme atteignable depuis les sous graphes en amont des TP.

0. bonus si pondération GG et/ou RNG en plus de Delauney
1. quantité d’astronautes du site de départ qui peuvent aller directe à leur destination grâce à ce lien
2. quantité et surtout diversité d’astronautes acheminable d’un sous graphe à l’autre grâce à ce lien
3. taille et diversité des sous graphes reliables (>1 pour ne pas agréger les nœuds isolés)
4. si aucun nouveau lien ne semble utile au regard des critères précédents, on peut :
   • ajouter des téléporteurs
   • densifier les arêtes du sous graph sans ajouter de nouveaux noeud, à commencer par les voisines de téléporteurs pour l’instant, mais avec un calcul de distance, plus une arrête réduit la distance entre deux noeud du même sous graphe, mieux c’est.
   • upgrader/ajouter des pods.

Les ressources

Le fait que les ressources inutilisées génère 10% d’intérêt (et que les astronautes amenés à bon port n’en rapportent pas), m’a amené à essayer différentes stratégies : attendre les 4 ou 5 premiers tours avant de commencer à bâtir quoi que ce soit, pour :

• avoir plus de ressources (10% par tour)
• voir si des ressources supplémentaires arrivent par ailleurs, régulièrement ou corrélé aux bâtiments
• voir si de nouveaux bâtiments arrivent (et planifier les constructions avec une meilleure connaissance plutôt que d’avoir des tubes indestructibles relativement obsolètes au regard des nouveaux bâtiments)

Priorisation stratégique des optimisations de code

Je me suis fait un tableur avec les meilleurs scores théoriques atteignable pour chaque scénario (si chaque astronaute est téléporté chaque mois sur son nœud idéal dès qu’il arrive).
En partant de là j’ai noté mes scores actuels par scénario, et regardé plusieurs choses :

• quel est l’étendu du manque à gagner pour ce scénario (donc un gros scénario est prioritaire à ceux ayant un seul site d’atterrissage par exemple)
• quel pourcentage du max théorique j’atteins ?
• ai-je des régressions sur certains scénarios ?

En partant de là, je me mets sur le scénario dans lequel je m’en sors le moins bien et je regarde ce qui se passe pour réfléchir à ce que je pourrais faire différemment pour que ce soit mieux.

En dernier recours, j’ajoute une détection de scénario pour ajuster des réglages au cas par cas :

• peu ou beaucoup de bâtiments initiaux
• nombre de bâtiments qui augmente ou non (et idem pour les ressources, mais ça implique d’attendre pour identifier)
• ressources faibles ou abondantes en quantitatif, ou en relatif au nombre de bâtiments
• distance homogène ou hétérogène dans les liens potentiels entre nœud voisins.
• type de nœud diversifié ou non…

Mais je l’ai davantage utilisé pour faire des optimisations temporaires pour voir ce que j’arrive à atteindre et ce que j’en apprends, pour ensuite essayer d’intégrer ça dans mes stratégies générales, afin de rester le plus générique et adaptable possible au final.

Conclusion et remerciements

Je me suis vraiment régalé avec ce défi en temps limité. Un max de stimulation intellectuelle avec le côté heuristique pour chercher des moyens d’optimiser avec les aléas des tours suivants d’un côté et des algos plus académiques de l’autre, un mélange vraiment savoureux ! Merci !

Suggestions d’évolution du défi

Si des variantes devaient voir le jour, je verrais d’un bon œil un découpage en ligues, même pour du défi d’optimisation :

1. bois :

• ressources illimitées
• pas de nouveau bâtiments en cours de scénario
• pas de téléporteur
• pas d’upgrade
• pod lié à chaque tube géré automatiquement

2. bronze :

• ressources contraintes, sans pouvoir influer dessus (pas de 10% d’intérêt)
• nouveaux bâtiments possibles en cours de scénario
• pas de téléporteur
• pas d’upgrade
• pod lié à chaque tube géré automatiquement

3. argent :

• ressources contraintes, avec N% d’intérêt sur l’épargne, mais aussi M% du score atteint en intérêt, M et N dépendant des scénarios.
• nouveaux bâtiments possibles en cours de scénario
• pas de téléporteur
• upgrade possible, incluant un pod supplémentaire (cout selon scénario)
• pod lié à chaque tube géré automatiquement

4. or :

• ressources contraintes, avec N% d’intérêt sur l’épargne, mais aussi M% du score atteint en intérêt, M et N dépendant des scénarios
• nouveaux bâtiments possibles en cours de scénario
• téléporteurs possibles, prix variable d’un scénario à l’autre
• upgrade possible, incluant un pod supplémentaire (cout selon scénario)
• pod lié à chaque tube géré automatiquement

5. platine :

• ressources contraintes, avec N% d’intérêt sur l’épargne, mais aussi M% du score atteint en intérêt, M et N dépendant des scénarios
• nouveaux bâtiments possibles en cours de scénario
• téléporteurs possibles, prix variable d’un scénario à l’autre
• upgrade possible (cout selon scénario)
• pod gérable indépendamment (cout selon scénario)
• pod échangeable (frais selon scénario)
• réaffectation de téléporteur entre destination déjà construites (frais selon scénario)
• les astronautes des sites d’atterrissage peuvent changer de type chaque mois
• les degrés de variation maximum par mois sont indiqués en début de scénario :
  • max ressources supplémentaires par tour (hors M et N)
  • min ressources supplémentaires par tour (hors M et N)
  • augmentation max des prix par mois (TP, tubes, pod… peuvent évoluer différemment)
  • baisse max des prix par mois
  • max astronautes remplacés par mois par site
  • min astronautes remplacés par mois par site
  • max bâtiments ajouté par mois
  • min bâtiments ajouté par mois

Qu’en pensez-vous ?

[1000i100]

@leojean890

tu as peut être trop overfit sur les jeux d ide et de submit ?

Je ne comprends pas cette dernière phrase, pourrais-tu la reformuler ?

[Fouk]

Je ne me souviens pas de ce que j’ai push en dernier, mais effectivement, je multipliais les tests “exotiques” en me disant que c’était le meilleur score qui était conservé…

[alexcercos]

#200 (4.7M)

First of all, I wasted the first 4 days fighting ghosts (I’m looking at you, constrained delaunay triangulations) and trying not very good heuristics (that got me to 2.9M), partially because I didn’t think I could even fit the complexity (or what I thought it was) in a genetic algorithm. On day 5 I couldn’t even put my hands on a PC, but that night I finally decided to go for GA and got some ideas for them. So to sum up, on day 6 I wrote a simulator, local runner (basically parsing the level files) and the genetic algorithm itself; and on the last day I debugged everything (up to some point) and made some basic test-case detection and another genetic optimizer of hyperparameters (this time in python, partially inspired by this script, except for the request parts). I left that optimizer running the last night, made some last-hour fixes with 2h left and sent the best result I was able to get from there (it improved from 4.5M to 4.8M at the time).

My process for the genetic algorithm was: picking a random number as amount of pods, substracting their cost, then making a boolean list of pods to delete (adding their gain), a list of possible tubes (that could repeat, which meant “upgrade”, and another boolean list that would override that tube with a random teleport, with some %), and lastly 2 list (with the size of that pod amount) with random origins and ids for the pods. P̶o̶d̶s̶ ̶a̶l̶w̶a̶y̶s̶ ̶s̶t̶a̶r̶t̶e̶d̶ ̶i̶n̶ ̶l̶a̶n̶d̶i̶n̶g̶ ̶p̶a̶d̶s̶ ̶(̶e̶v̶e̶n̶ ̶i̶f̶ ̶t̶h̶a̶t̶ ̶m̶e̶a̶n̶t̶ ̶t̶h̶a̶t̶ ̶s̶o̶m̶e̶ ̶w̶e̶r̶e̶ ̶b̶l̶o̶c̶k̶e̶d̶)̶.̶

Then, the “individual” state for the genome would be to build tubes/teleports in the list order until one of them was more expensive than the resources left, and then building the pods only if they could move. It would have been better to do it as Nagrarok said in his answer, because my approach caused too much “waste” of empty and redundant tubes (which I didn’t have the time to make them be detected and cleaned).
I generated the path of the pods on the simulation with some move rules (and a few random overrides) which basically were: if there are astronauts in current position, move close to their target, else go to a landing pad. If I had moves left in a pod’s path I made them random (just in case I deleted a blocking pod later). My simulation wasn’t even exact too (sometimes it would overestimate the score by ~10-20%) but I couldn’t find the reason.
Lastly, after the test-detection I made some specific re-triangulations and hyperparameters which I tried to optimize (GA probabilities and population sizes, and a parameter to “force” the simulations to save a % of resources for later).
I think I had some good pieces to do better, but the time to do much worse, so I guess that was a good contest after all for me (and I really liked it, I had been dreaming of getting an optimization contest since I started trying those types games this year, so that was really lucky in that sense).

Edit: now while debugging I noticed that forcing pods to start in a landing pad was an error: especially in the distribution network case, if I added a teleport from a landing pad to a destination point, no other type of astronaut that took the teleport (and wasn’t the same as the target building) could get to their destination since no pod could be made in that unconnected zone.

[leojean890]

Ah oui, l’overfitting c’est quand tu fais en sorte de maximiser ton score sur un certain de nombre de testCases mais que l’algorithme n’est pas assez général pour s’adapter à de nouveaux. En général il y a un compromis à faire entre overfitting et underfitting qui n’est pas évident à trouver. En l’occurrence je ne sais pas si c’est ton cas ou pas mais peut être. Parfois la raison d’un moins bon score sur des tests de validation par rapport aux tests provisionals ça peut être ça. Perso ici j’avais 5.14M aux jeux provisionnels et j’ai baissé à 4.85M aux finaux ce qui montre soit un overfit soit une variance élevée (si le même code peut avoir un rank entre ces 2 valeurs par ex). J’avais pas implémenté la vraie fonction de scoring pour l’évaluation, mais ça aurait pu aider, si il y avait une semaine de plus je l’aurais fait ! mais dans ce contest les règles de déplacement des astronautes étaient galères donc il me fallait réserver un certain nombre d’heures pour le coder précisément ;0

[leojean890]

Ah oui t’as pas vu sur le discord qu’ils scorent à la fois le meilleur et le dernier et prennent le best des 2 pour le classement final. C’est logique de favoriser le dernier plutôt que le “meilleur” sinon, car c’est à toi de décider quel est le code qui a le plus de chances de scorer en fonction de la variance que tu estimes sur chaque code (si tu le submit plusieurs fois). Genre si tu utilises un algo full random alors qu’on a ici si peu de valideurs et avec très peu de rollouts car tu manquerais de perfs tu peux avoir 3M2 et 4M2 en le submittant 2 fois. Mais du coup t’aurais un code qui score 4M1 de manière consistante et tu préférerais l’utiliser lui plutôt que l’autre et tu l’utilises donc comme dernier submit cf mon msg du 10/09 à 23h sur ce thread

[_CG_dhubleur]

Hello, for the end-of-challenge rerun:

• the validator set was very similar to the 2 sets already available (each testcase was generated with the same code, just using a different seed). If you have big score differences, it’s because you’ve overfit too much against the available testcases
• 2 of your submissions were run against this set of validators: your best submission and your last, and we keep the one with the highest score in this rerun

[N0sf3]

The challenge was good, I really enjoyed it, thank you!

However seeing the score dropping of 1M in the recalculation and the position dropping from 50 to 150 was not really amusing; perhaps my solution was doing too much overfitting on the disclosed test cases and validators. Something to take into consideration on the next challenge.

I must give a feedback on something that, in my point of view, was not … fair sportsmanship .
Sharing on Discord that you were computing a max(last_submission, best_submission) was unfair to people that are not part of that community. May I suggest, for the next time, to send a wide spread communication around how the final scores are computed.
I could understand if this was coming from a player guessing, but this came from someone working inside CodinGame.
You created a situation of advantage in which only a subset of player could benefit; the active Discord Community.
Would have I scored higher on my solution if I knew? Most likely since I had in place two solutions and consistently one was perform better than another one under certain tests (and I had no time to understand why and generalize the conditions).

In any case, thank you for the challenge, I have learned a lot during it; from some needed refresh on Graph Theory, to optimizing code in Java (was my first submission using it), to the fact that I need to regularly keep an eye on Discord for possible score breaking hints from the CodinGame employees

[CodeVanguard]

#525 with 2 887 025 pts (3rd at the beginning)

Help for future Codingamer:

Number of astronauts by level:
Lvl:1->30 Lvl:2->100 Lvl:3->200 Lvl:4->300 Lvl:5->780 Lvl:6->760 Lvl:7->960 Lvl:8->800 Lvl:9->960 Lvl:10->620 Lvl:11->1000 Lvl:12->950

[CodeVanguard]

Maximal possibles ressources by levels:
//Level 1 //Start Ressources 2000 //Max Ressources 31599
//Level 2 //Start Ressources 3000 //Max Ressources 42314
//Level 3 //Start Ressources 5000 //Max Ressources 124059
//Level 4 //Start Ressources 5000 //Max Ressources 134546
//Level 5 //Start Ressources 2100 //Max Ressources 110846
//Level 6 //Start Ressources 5000 //Max Ressources 115900
//Level 7 //Start Ressources 1500 //Max Ressources 156231
//Level 8 //Start Ressources 100000 //Max Ressources 611578
//Level 9 //Start Ressources 3000 //Max Ressources 171807
//Level 10 //Start Ressources 11500 //Max Ressources 236827
//Level 11 //Start Ressources 5500 //Max Ressources 320118
//Level 12 //Start Ressources 6000 //Max Ressources 252573

[jddingemanse]

I would not want to live in a city with my own transport system. Finished 184 (4767243 points), with rather stupid heuristics and a lot of room for improvement for which I did not have enough time.

For every pad, my algorithm checks per astronaut type the closest matching lunar module; and for each of these a TUBE command (pad to mod) is given. One turn later, based on the tubes that are actually built, for every pad with tubes a POD is created that travels back and forth between the mods and the pad.
In case a pad already exists, but has no tubes, apparently my algorithm does not manage to build a tube to some relevant module. So, that one gets a TELEPORT command for the astronaut type that is the most present, with exit at the farthest module of that type. Within the same type of actions, actions were roughly prioritized based on the number of astronauts involved.
My algorithm did nothing with collision checks, whether or not a tube was already built, whether I had enough resources, etcetera. In some of the test cases I received 200+ warnings for failed commands.

My fingers are itching, given time, to first make these basic heuristics smarter (predict collision rather than simply give it a try; do something with distributing astronauts over similar type modules, prioritize actions based on the amount of resources, …), and then to start trying to make smarter routes, and then some more. Frankly, I was surprised that this algorithm rewarded me with this amount of points. I think that, in the more complex cases, most astronauts did not arrive at their end destination at all, and had to somehow make a living at their landing pad. If I were amongst them, I would block any incoming flight until the transportation system would be improved.

[Blazde]

#22, ~6.2mil, Rust

I used a local search to find a cost-efficient set of non-conflicting new constructions each turn.

Initially it seemed there was so much instance variety we’d benefit from per-case parameter specialisation (ie. which kind of junctions to try using, whether pods should run up and down a single link, multiple, loops, how many resources to save each month, etc). So I identify the case type by comparing 1st turn parameters (just: resources, #buildings, #astronauts) against test & known validator instances, encouraged by admin comments that the hidden validators were very similar.

To allow this specialisation in a general way I perform the search over many ‘projects’ where a project is any arbitrary set of teleporters & tubes & pods that will either be collectively in or out of the final orders that month, and then the set of trialled projects can be decided per-case type. The trialled projects may involve lots of conflicting/overlapping ones and we seek a mutually-compatible optimal subset. The idea is I could have complicated constructions like ‘StarPods’ (that 1000i100 mentions) or a StarPod connected to a teleporter, and those complicated pieces would jive well with single tube & pod constructions, or even a single pod meant to use spare capacity on another project, and I’d have a platform to easily tinker with these ideas for each case.

In practice I use single tubes with one dedicated pod running up and down 95% of the time The only important exception is allowing teleporters on a few cases (Distribution Network especially) and disallowing them on a few others where buying them looks good initially but turns out inefficient in later months. In the final hour of the contest I experimented with V-shape projects, where a first tube is always connected between a LandingPad & Module that are closest to each other with the restriction that they share matching Astronaut/Module types, and a second tube runs to an arbitrary building, with only one pod running up and down both tubes. Those constructions help a little on some cases by saving pod costs but more often a net-neutral benefit even when they do get used. On the other hand searching over sets of 3 arbitrary buildings to create V-shapes or Triangular routes for pods caused too much combinatorial explosion to be useful, which probably highlights the weakness of this idea. Nagrarok’s point that tubes can be calculated based on pod movements sounds like a better method of cutting down a lot of the complexity I was trying to with this approach.

I use Extremal optimisation (EO) for the search, a not-well-known scheme which works well if you can identify which parts of a prototype solution are good or bad. I simulate astronauts (in batches not individually) using the currently proposed set of included projects. Astronauts keep a list of which projects they travelled on and, if they score, award their score to those projects. I then calculate an efficiency metric for each project (just score/cost). Projects involved in incompatibilities (>5 tubes to a building, intersecting tubes, more than one teleporter at a building) have a penalty applied totalling the score of all projects they’re clashing with, and all projects with any clashes are ordered before projects with no clashes in the fitness function. EO then selects bad projects to remove (in particular enough to keep the spend under the resources available).

Ideally I’d planned to also rank un-included projects using the simulation with some kind of non-deterministic/sliding doors astronaut movement but it was too costly so I just add some random projects each simulation. That worked reasonably but rightfully shouldn’t because on the biggest cases like Grid I was only doing 300-500 simulations while selecting from a pool of thousands projects, potentially missing very efficient links.

Like others, I think 2 weeks would have done this problem more justice. I finally suppressed ‘warnings’ in the last few hours, still have a minor scoring bug, and for a long while didn’t think I’d pull my main ideas together in time. My code is littered with comments to refactor this or that calculation more efficiently. Another week to get a 20-fold improvement in #simulations and try out some secondary ideas would have been nice!

I never got to explore saving resources, though I think it should be important in some cases. The 10% interest was a really nice puzzle feature to encourage this. I never destroy pods. Or change their priorities on later turns (pods created in later months always have higher IDs but I do randomise within a month to give the search more options and not create pathological priorities). I was doing tube upgrades successfully but stopped seeing them at some point. Not sure whether my tube collision detection started foiling those or they just became redundant when I added teleporters.

Many thanks to CG for hosting this (especially Mathis Hammel for creating it)! I’m new enough around here that I’d not done previous Optimisation contests so it was a very welcome change when I was expecting to have to hack some SQL again This one especially I think I’ll continue to enjoy long after the contest.

[vcoubray]

#81 (5.3mil) in Kotlin

First, thanks for this challenge, I really enjoyed it.

I couldn’t spend as much time as I wanted on this challenge, so I do a very simple strategy and I am very surprised (and proud) of my rank.

For each month, I start by creating a list of pair ‘Landing pad/Module’ for each Landing Pad and all modules with a corresponding type.
Then, I sort this list of potential tubes by cost and I try to create all tubes until I have not enough resources.
Before creating the tube, I check :

• if a module with the same type is not already connected to the landing pad.
• The landing pad or the module haven’t reach the maximum of tube.
• if there is no intersection with another tube or a module (already existing or already planned in the turn).
  If the tube can be created, it is created with its own pod.

Later, I added the teleports in the “potential tubes” list. So if it’s cheaper to create a teleport or there is no possibility to build a tube, I create a teleport
And that’s it, I only have paths with a length of 1 from all landing pads, and sometime, a few teleports.

The last day, I tried to improve this strategy to have longer paths but that wasn’t very successful. So I stay with this strategy.
I probably could gain a few more points by trying to have a better repartition of the astronauts

[TBali]

#3121 / 3970
I used a “lazy algorithm”. What I mean: I opened the IDE to read the statement and I ran the IDE tests with the default php stub without any modification. Business travels and lack of free time during the contest prevented me to participate, so I never pressed submit. I was very surprised to see that I was still ranked and overtaking 850 other people… Okay, most likely they also did not participate, but the percentages and points varied…

[MyNameShallBeHere]

We can get 55065 if we build a teleport and upgrade the other route at the same turn. Don’t know if we can get more, it’s probably the best option. We can view scoring as a type of possible upgrades we can make. For example, with 15 astronauts we can have several setups.

• 1395 points/round using teleport, which cost us 5000.
• 1380 with 1-distance route and 2 pods, that cost extra 2000 resources at 500 distance.
• 1370 is our base production with 1-distance route and 1 pod.

Then we just trade between accumulating interest and possible upgrades. For example, at month 4 we have 2100 points with two 1-distance and 1 pod routes. If we immediately upgrade, we get 17x10=170 extra points. If we wait 7 months, we have ~4092 resources and are able to make 2 upgrades, 10x20=200 extra points. If we wait one month more, then ~4501 resources is enough to destroy one pod and build teleport, 9x25=225 extra points. In this particular case, we receive extra 1000 credits and are able to get ~6450 resources after 8 months, so we can build teleport and make one upgrade, 9x35=315 extra points. If we wait even longer to build 2 teleports, it takes 11 months and 6x50=300 extra points, that is already lower.

[lD1]

In the same spirit, if you just delete 2 chars from the initial solution, you can multiply your points by 2!
(Edit : from what I remembered. Retesting it in the now published optimisation game, you go from 304150 to 446540)
(Edit 2: you also validate one less test case, so you are lower rated … I don’t think it was the case during the contest)

Anyway, as you pointed out, “just submitting” was a not so bad solution ^^

[Vintarel]

I finished 25th with 6.1M points.

First of all, thanks CG for this very nice contest and for the fact that many efforts have been made to ensure that the statements are very clear !

That being said, I am still not 100% sure on how the game works, about the order in which the astronauts board the pods… I decided to not care too much and I have coded a game engine that would be close but not identical, which frustrated me a little bit at the end because the actions I took were not optimal.

My algorithm is a genetic one, with no mutation (I was too lazy to add mutations) but merges instead:

• I only considered teleports and chains of tubes: a chain is a path (A ← B ─ C ─ … ─ X ─ Y → Z) of cities in which a pod goes back and forth in it. No upgrade, no destroy.
• Initial population: 100 series of random teleports or chains of length 2 (A⟷B)
• Crossover: given 2 individuals, I make a new one by shuffling and mixing all their teleports and chains. When two consecutive chains can be merged, I merge them. For instance, the two chains (A ← B → C) and (C ← D → E) give a new chain (A ← B ─ C ─ D → E).
• Scoring: I keep individuals with the higher value of (round score + 15% of round final money). I evaluate the score with my game engine. I have noticed that keeping a little bit of money at the end increased overall score by 500k points. I guess it’s because it avoids creating useless little routes and it saves money for big teleports after.

My algorithm is far from being very good but I’m happy with it !

[Anastaszor]

#267 / 3970

Contrary to some here, i actually gained about 30 places even if the scores from the final scoring and the tests and validation test suites are actually similar (~4.4M pts).

As everyone here i’d like to use a unique algorithm with high end maths that would solve it all (but without the knowledge of delaunay triangulation and more) and it failed miserably.

I ending with a somewhat generic algorithm for all the base cases with minimal spanning tree or nearest neighbor depending on the scenario ; and as others pointed out, assigning a pod to every tube got us quite far. Tubes were built first which is probably sub optimal as many tubes are without a pod in the end.

For all difficult scenarios i used specific strategies that are tailored to that scenario – which is the opposite of what we should do but hey, i dunno how i gained places in the end ! And i burnt a lot of hours into this challenge.

Some notable strategy I used are :

• for the spiral, i used custom clustering (one new cluster every turn) with 2 pods, one for the desserving the new local buildings, and one which link the landing are of the current pod with the landing area of the last cluster. every 6 cluster a pod would link the inner arm of the spiral. (why 6 ? because manual testing showed it was the best score)

• for the grid, i make a circuit (circular link between all the landing areas), then incorporated all mandatory buildings (which crossed paths already made for the circuit) and then one of every missing building type. I ended up with a 41 section circuit, each section with its own pod. I used up the remaining money on teleporters as much as i can to shuffle everyone along the circuit. I’m very proud of this one which made 1M points on testing even i resorted to a suboptimal for testing because it scored more points on validation.

• for the neural network i ended up using a strategy that teleports then dispatch, avoiding all the navigation amongst the inner layers, as every teleporter sent only people to villages that were near each other. Half of the landing areas in the front row of the input layer will be given teleports, other areas would carry their people to the teleports, and on the output layer would dispatch the people to their neighbors. There is not enough money to make this strategy with 1 tube = 1 pod so pods had to be shared amongst 2 tubes, and some delivery optimisations had to be made.

• for the villages, i didn’t find a viable strategy as i find myself too starved to build something structured with tubes, so i resorted to do only teleports, teleporting the max number of people to their destinations. It did the minimal job at least…

I’d be curious to know what is the max (real, not theorical) score that anyone have made on his or her best scenario, or which scenario anyone has preferred ?

Overall it was a very good challenges, but 2 things very bothered me : imprevisibility of the budget changes and layout changes. It’s a missed opportunity i do think that the number of people carried over did not matter for the money made on the next month.

[VirtualAtom]

Rank #40

I had a lot of fun with this challenge. I was busy at work and lacked time to do as much as I wanted, but I’m happy with my results and glad CodinGame proposed an optimization challenge. I’ll provide short feedback here; a more extended version is available on my website.

After reading the game description, I decided on a plan and stuck to it during the challenge. I ignored astronaut pathing and most pod mechanisms. I did not simulate the full rules and used instead fully deterministic greedy algorithms:

• generate ideas of actions that will bring astronauts to destination buildings,
• score ideas,
• pick the best idea and either regenerate new ideas or trim outdated ideas.

I ended up with a multi-tube pod bot for the generic case; I’m not sure how it works, as I was almost sleeping on my keyboard when I wrote it ^^. I crafted manual solutions to some levels and then tried to code algorithms that reproduce such solutions. I failed (not enough brain power left) to do it for all levels I had handmade solutions that outperformed the dumb greedy generic algorithm. My final submission was just a bit short of the 6 million points, with special algorithms for Example1, Balancing, Grid, and Distribution Network. Final score was 5.77M.

Suggestions:

• We are getting up to 150 buildings, and the viewer cannot display their identifiers; we have to mouse over all the buildings until we find the one we are looking for. Please display the identifiers in debug mode.
• Please separate the state at the beginning of a turn in the viewer. I had to scrub very slowly between the last day of the previous month and the first day of the current month to see what was going on. To describe precisely what I’d like: a day 0 on which I could see all buildings, tubes, and teleports without my actions being taken into account, with all astronauts at their initial place.
• It’s a good idea not to fail on timeout when the bot has scored at least one point. However, I’m using debug tools to catch and report assertion failures; they stop the bot, which used to be considered a failure, and I would immediately see that a level has issues. Please add a setting, maybe a game variable, that I can pass to the referee to stop silently ignoring such errors. I’m using a custom fork of the referee to work around this, but it may be helpful for others, too.
• There were a lot of rules, and it was said in Discord that the API does not allow leagues to be made for optimization games. Players had a lot to learn all that once, which could be overwhelming. We can work around that by activating game features per level. The first levels would allow users only to create pods: no bonus resource, no new buildings, no tube creation, no teleport. Then, you could enable tube creation on other levels, and so on. This would emulate leagues on optimization puzzles/contests.