Skip to content

README.md

Latest commit

 

History

History
41 lines (24 loc) · 1.76 KB

README.md

File metadata and controls

41 lines (24 loc) · 1.76 KB

https://www.codingame.com/ide/puzzle/fantastic-bits

https://stackoverflow.com/questions/64025633/scipy-linear-sum-assignment-show-the-workings

2 options:

  • (Bronze 360/408) Munkres: Description sommaire du problème hongrois: https://www.developpez.net/forums/blogs/283256-f-leb/b17/python-problemes-daffectation-methode-hongroise/

    Implementation choice in this challenge:

    • First, we build a 2d matrix representing distances between each wizard and each snaffle

        distances---s1------s2-----s3------s4-------s5------s6------s7

  wiz_1-------50------70-----100-----120------80------150-----200

  wiz_2-------130-----20------5------179------20------30------40

    • Second, we create a dictionary to create an association from each wizard to a distinct snaffle describing the cost matrix in term of distance/duration of moves:

      costs[(0, i), (1, j)] = matrix[0][i] + matrix[1][j] (i, j going from 1 to snaffles_count and i != j)

    • Third, we choose the best combination to optimize global team effort (extracts the dictionary key (tuple) of minimum cost value)

      best_combination = min(costs)

      i, j = best_combination[0][1], best_combination[1][1]

    • Finally, we extract the snaffle target for each wizard:

      wiz_1.target, wiz_2.target = snaffles[i], snaffles[j]

  • (Bronze 243/418) Avec algorithme linéaire (module scipy.optimise.linear_sum_assignment): https://perso.ens-lyon.fr/ruben.staub/vrac/bash_tricks/trick_18.php

Replays: