ProgHelp

Une communauté intelligente et active

[Défi] Chorégraphie

Message par Patak » 05 Février 2018, 00:19


Bonjour à tous :-D

Voilà un petit défi algo-maths bien sympathique :

Un chorégraphe aimerait constituer la plus haute tour humaine possible.

Image

Pour des raisons esthétiques et pratiques, il faut que chaque personne soit plus petite et légère que la personne qui la porte (en dessous).

Écrire un algo qui reçoit les tailles et poids de chaque membre, et retourne la séquence des membres qui participent à la plus haute tour humaine !

Exemple :

Input (taille, poids) = (190, 95) (170,71) (180, 79) (160, 63) (185, 85) (175, 76)

Output = (160, 63) (170,71) (175, 76) (180, 79) (185, 85) (190, 95)


Encore plus d'exemples :

SPOILER : AFFICHER
in = (1, 1) (2, 5) (3, 3) (4, 4)
out = (1, 1) (3, 3) (4, 4)

in = (1, 1) (2, 2) (3, 1) (4, 4)
out = (1, 1) (2, 2) (4, 4)

in = (1, 1) (2, 5) (3, 3) (4, 4) (5, 3)
out = (1, 1) (3, 3) (4, 4)

in = (2, 5) (1, 1) (4, 4) (3, 3) (5, 3)
out = (1, 1) (3, 3) (4, 4)

in = (1, 100) (2, 101) (3, 102) (4, 4) (5, 5) (6, 6) (7, 7)
out = (4, 4) (5, 5) (6, 6) (7, 7)

in = (4, 4) (5, 5) (6, 6) (7, 7) (100, 1) (101, 2) (102, 3)
out = (4, 4) (5, 5) (6, 6) (7, 7)

Conseil

Dessinez les points sur un plan et vous verrez que c'est un problème géométrique !
Il faut un maximum de rectangles qui s'emboitent =)


La séquence retournée est strictement croissante (selon la taille et le poids)

Il se peut que Ouput contienne moins d'éléments que Input.

Si il y a plusieurs séquences optimales, vous pouvez n'en retourner qu'une seule d'entres elles.

_____

Il y aura un bonus de PH pour les meilleures réponses.

Utilisez le langage que vous voulez :cowboy:

Accompagnez votre solution d'explications, et précisez (si possible) le temps algorithmique selon la taille de l'input.

Bonne chance !
Image
Avatar de l’utilisateur
Patak
Administrateur
 
Messages : 1165
Points d'honneur : -666 PH
Inscription : 30 Oct 2012

Message par Sehnsucht » 05 Février 2018, 13:33

['Tin j'en ai marre, je tape un message je vais pour le poster, je suis plus logué du coup je perds le message ; et comme je fais des tartines je dois tout recommencer... Du coup ça va être plus court. (bien pour vous ça)]

Je veux pas être méchant mais

Y'a pas assez d'exemples pour que ce soit bien, les jeux d'essais (tests unitaires si vous préférez) c'est important, là un seul exemple, sans difficulté, pas de cas d'égalité ou de taille inférieure avec poids supérieur = pas bien.

On fait comment dans les cas où il y a plusieurs "bonnes réponses" possibles, ex (160, 63) (170, 71) (160, 64) (170, 72) -> (160, 63) (170, 71) ou bien (160, 63) (170, 72) ou bien (160, 64) (170, 71) ou bien (160, 64) (170, 72)

Ensuite je trouve le truc un peu bidon (pardon) ; des algos de tri ça se trouve à la pelle avec leur détails, complexités et tout, la seule chose qui change c'est le critère de tri au lieu d'un simple "inférieur" ou "supérieur" c'est une paire, mais c'est une part totalement négligeable de l'algo et donc ça rentre pas dans la complexité de toute façon ; du coup reste plus qu'à choisir l'algo de tri qu'on veut (qui peut dépendre du langage et/ou structure de données "préférée" du langage) et finalement ça va probablement se réduire à merge sort / heap sort / quicksort
(Note au passage, complexité, tu devrais préciser si c'est temporelle ou autre, genre mémorielle ; mais bon comme c'est quasi-toujours temporelle)

Enfin, et ça justifie le paragraphe précédent, un tri ne supprime pas d'élément du coup ce que tu demandes ce sont 2 choses d'abord un tri et ensuite un filtrage, et comme certains langages trient naturellement les paires (ou les tuples d'une manière générale) ce qui se fait en temps linéaire
Donc on aurait tri + filtrage = O(n log n) + O(n) = O(2n log n) donc O(n log n) donc le tri donc paragraphe précédent donc merge/heap/quick sort

[Là je fais un ctrl+c de mon post juste au cas où je serais dé-logué pour pouvoir le ctrl+v au cas où]
Censément, quelqu'un de sensé est censé s'exprimer sensément.

Image
Avatar de l’utilisateur
Sehnsucht
Membre VIP
 
Messages : 289
Points d'honneur : 270 PH
Inscription : 10 Fév 2013

Message par Patak » 05 Février 2018, 16:17


Je veux pas être méchant mais y'a pas assez d'exemples pour que ce soit bien, les jeux d'essais (tests unitaires si vous préférez) c'est important, là un seul exemple, sans difficulté, pas de cas d'égalité ou de taille inférieure avec poids supérieur = pas bien.


L'énoncé est très clair.
_

La difficulté du défi, c'est aussi de trouver les tests unitaires plus compliqués.

Contrairement à un (bon) topic de demande d'aide, il y a ici un effort de compréhension qui est exigé de la part du lecteur.

On fait comment dans les cas où il y a plusieurs "bonnes réponses" possibles


Juste en renvoyer une.
Le chorégraphe n'a besoin que d'une séquence possible.

Ensuite je trouve le truc un peu bidon (pardon)

[...]

ce que tu demandes ce sont 2 choses d'abord un tri et ensuite un filtrage


Tu te trompes complètement.
C'est plus compliqué que ça en a l'air.
Un simple algo de tri + filtrage ne suffira pas.

Je vais te donner un exemple :

(2, 10) (1, 2) (4, 4) (3, 3) (5, 5)

Ici, si tu fais un trie sur le premier nombre du Tuple, tu obtiens ça :

(1, 2) (2, 10) (3, 3) (4, 4) (5, 5)

Puis un filtrage pour ne garder que les bons, tu obtiens ça :

(1, 2) (2, 10)

Qui n'est pas la solution optimale.
Puisqu'il s'agit de :

(1, 2) (3, 3) (4, 4) (5, 5)

________________________

Message général

Ce problème prend du temps à résoudre, et est de niveau difficile.

Pour s'y attaquer sérieusement, il faut une bonne dose de motivation, et de patience.

Il n'y a aucune obligation de participation, c'est un défi ouvert.

Si vous décidez de participer, alors prenez votre temps, rien ne presse.
Image
Avatar de l’utilisateur
Patak
Administrateur
 
Messages : 1165
Points d'honneur : -666 PH
Inscription : 30 Oct 2012

Message par Sehnsucht » 05 Février 2018, 17:24

Trouver un algorithme sans spécifications c'est quand même drôle, ça va finir en
A: "j'ai ce code qui marche"
B: "Non pas dans ce cas : *exemple de cas*"
A: "ah ok, ... maintenant c'est bon"
B: "Toujours pas, sur cet *exemple* ça coince"
...

Autant dans une optique pro avec dialogue client je comprends ; autant là dans une optique "défi" celui qui donnera sa solution en premier sera désavantagé par rapport à celui qui viendra après et pourra lire l'échange, donc autant mettre tout le monde à égalité d'emblée (mais bon ça à la limite c'est accessoire)

Sinon on doit pas faire le même filtrage parce que j'obtiens le bon résultat.
Censément, quelqu'un de sensé est censé s'exprimer sensément.

Image
Avatar de l’utilisateur
Sehnsucht
Membre VIP
 
Messages : 289
Points d'honneur : 270 PH
Inscription : 10 Fév 2013

Message par Patak » 05 Février 2018, 18:06


Ce défi, je ne le conçois pas vraiment comme un échange, ni comme une compétition.
C'est avant tout un casse tête individuel !

Voilà les étapes :

1) Je prends 15 minutes pour analyser le problème et trouver un maximum d'exemples (crayon + papier)
2) Je fais une première tentative de résolution de façon naïve et sans me soucier de la performance
3) J'essaie d'optimiser ma solution un maximum tout en validant avec mes exemples trouvés
4) Je publie tout ce que j'ai fait en un seul message, dans un BBCode Spoiler

Dans le cas où y'a des exemples non considérés, ça vient d'un problème dans la phase 1)
____________

Sinon on doit pas faire le même filtrage parce que j'obtiens le bon résultat.


Ça doit être car tu parcours la liste dans l'autre sens.

Un tri te donne l'ordre de parution, mais il te reste à trouver la plus longue séquence,
et ça, je ne vois pas comment tu peux le faire avec un filtrage.
____________

Petite précision :

Ce défi a déjà été proposé à des candidats lors d'entretiens d'embauche,
et c'était à eux de trouver les exemples.
____________

Edit :

Finalement, j'ai rajouté des tests à passer
Mais ils seront secondaires. Dans le sens, où c'est l'énoncé qui est le plus porteur de sens !
Image
Avatar de l’utilisateur
Patak
Administrateur
 
Messages : 1165
Points d'honneur : -666 PH
Inscription : 30 Oct 2012

Message par Sehnsucht » 06 Février 2018, 03:36

Bon j'avais pas spécialement fait gaffe à l'histoire de la plus longue chaîne.

Enfin bref ; j'ai pour le moment 2 implémentations qui passent les tests (dont une où j'ai même pas besoin de trier)

(Je mets en spoiler au cas où, même si pour le moment le code est pas là)
SPOILER : AFFICHER
J'ai pas encore regarder en détail niveau complexité, mais si je dis pas d'ânerie les 2 sont en O(n log n)
  • Une c'est du O(n log n) pour le tri + O(n log n) pour la création des chaines + O(n) pour la recherche de la plus longue
  • L'autre c'est du O(n) pour la "création" + O(log n) pour la création de la chaîne (mais celui là faut que je le vérifie)
Après faut que je vois avec différentes structures de données, entre les coûts d'insertion et d'accès où on pourrait gagner, même si globalement, je vois pas comment ça réduirait la complexité globale.

Finalement j'ai passé plus de temps à me faire une jolie solution multi-projet avec système de plugin via MEF2 pour chaque version :lol:
Censément, quelqu'un de sensé est censé s'exprimer sensément.

Image
Avatar de l’utilisateur
Sehnsucht
Membre VIP
 
Messages : 289
Points d'honneur : 270 PH
Inscription : 10 Fév 2013

Message par Sehnsucht » 20 Février 2018, 19:56




Pour tes cours d'auxiliaire d'enseignement en programmation fonctionnelle tu pourras leur expliquer qu'on peut modéliser n'importe quelle structure de données rien qu'avec des fonctions.

Pourquoi je raconte ça ici parce que je l'ai fait pardi (bon pas pour résoudre le truc je suis pas fou à ce point.

à la base voilà ma structure de données en VB.Net "classique" :
Dim source = {
({(1, 1), (2, 5), (3, 3), (4, 4)}, {(1, 1), (3, 3), (4, 4)}),
({(1, 1), (2, 2), (3, 1), (4, 4)}, {(1, 1), (2, 2), (4, 4)})
}

J'ai pris que les 2 première vous allez vite comprendre pourquoi, on a donc une liste de paires de listes de paires d'entiers
Voilà la même chose représentée avec une seule fonction (méga monstrueuse tout ce que j'ai fait avant, c'est une balade en forêt avec les oiseaux qui gazouillent) ; j'aurais pu j'aurais imbriqué 10 spoilers
SPOILER : AFFICHER
Dim rows As Object = Function(_051) _051.Invoke(
Function(_031) _031.Invoke(
Function(_017) _017.Invoke(
Function(_013) _013.Invoke(
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004))).Invoke(
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))).Invoke(
Function(_018) _018.Invoke(
Function(_014) _014.Invoke(
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006))).Invoke(
Function(_011) Function(_012) _011.Invoke((
Function(_009) Function(_010) _009.Invoke((
Function(_007) Function(_008) _007.Invoke((
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))(_007)(_008)))(_009)(_010)))(_011)(_012)))).Invoke(
Function(_019) _019.Invoke(
Function(_015) _015.Invoke(
Function(_007) Function(_008) _007.Invoke((
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))(_007)(_008))).Invoke(
Function(_007) Function(_008) _007.Invoke((
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))(_007)(_008)))).Invoke(
Function(_020) _020.Invoke(
Function(_016) _016.Invoke(
Function(_009) Function(_010) _009.Invoke((
Function(_007) Function(_008) _007.Invoke((
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))(_007)(_008)))(_009)(_010))).Invoke(
Function(_009) Function(_010) _009.Invoke((
Function(_007) Function(_008) _007.Invoke((
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))(_007)(_008)))(_009)(_010)))).Invoke(
Function(_021) Function(_022) _022))))).Invoke(
Function(_026) _026.Invoke(
Function(_023) _023.Invoke(
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004))).Invoke(
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))).Invoke(
Function(_027) _027.Invoke(
Function(_024) _024.Invoke(
Function(_007) Function(_008) _007.Invoke((
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))(_007)(_008))).Invoke(
Function(_007) Function(_008) _007.Invoke((
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))(_007)(_008)))).Invoke(
Function(_028) _028.Invoke(
Function(_025) _025.Invoke(
Function(_009) Function(_010) _009.Invoke((
Function(_007) Function(_008) _007.Invoke((
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))(_007)(_008)))(_009)(_010))).Invoke(
Function(_009) Function(_010) _009.Invoke((
Function(_007) Function(_008) _007.Invoke((
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))(_007)(_008)))(_009)(_010)))).Invoke(
Function(_029) Function(_030) _030))))).Invoke(
Function(_052) _052.Invoke(
Function(_050) _050.Invoke(
Function(_036) _036.Invoke(
Function(_032) _032.Invoke(
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004))).Invoke(
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))).Invoke(
Function(_037) _037.Invoke(
Function(_033) _033.Invoke(
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006))).Invoke(
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))).Invoke(
Function(_038) _038.Invoke(
Function(_034) _034.Invoke(
Function(_007) Function(_008) _007.Invoke((
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))(_007)(_008))).Invoke(
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))).Invoke(
Function(_039) _039.Invoke(
Function(_035) _035.Invoke(
Function(_009) Function(_010) _009.Invoke((
Function(_007) Function(_008) _007.Invoke((
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))(_007)(_008)))(_009)(_010))).Invoke(
Function(_009) Function(_010) _009.Invoke((
Function(_007) Function(_008) _007.Invoke((
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))(_007)(_008)))(_009)(_010)))).Invoke(
Function(_040) Function(_041) _041))))).Invoke(
Function(_045) _045.Invoke(
Function(_042) _042.Invoke(
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004))).Invoke(
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))).Invoke(
Function(_046) _046.Invoke(
Function(_043) _043.Invoke(
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006))).Invoke(
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))).Invoke(
Function(_047) _047.Invoke(
Function(_044) _044.Invoke(
Function(_009) Function(_010) _009.Invoke((
Function(_007) Function(_008) _007.Invoke((
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))(_007)(_008)))(_009)(_010))).Invoke(
Function(_009) Function(_010) _009.Invoke((
Function(_007) Function(_008) _007.Invoke((
Function(_005) Function(_006) _005.Invoke((
Function(_003) Function(_004) _003.Invoke((
Function(_001) Function(_002) _002)(_003)(_004)))(_005)(_006)))(_007)(_008)))(_009)(_010)))).Invoke(
Function(_048) Function(_049) _049))))).Invoke(
Function(_053) Function(_054) _054))

Pour afficher ça (parce que je veux bien croire qu'on me croit pas sur parole), j'utilise ceci :
SPOILER : AFFICHER
Dim rowsEmptyQuery = rows.Invoke(Function(_055) Function(_056) Function(_057) Function(_058) Function(_059) _059).Invoke(Function(_060) Function(_061) _060)

Do Until rowsEmptyQuery.Invoke(True).Invoke(False)
Dim currentRow = rows.Invoke(Function(_062) Function(_063) _062)

WriteLine(New String("-"c, WindowWidth - 1))
Write("Input : ")

Dim input = currentRow.Invoke(Function(_064) Function(_065) _064)
Dim inputEmptyQuery = input.Invoke(Function(_066) Function(_067) Function(_068) Function(_069) Function(_070) _070).Invoke(Function(_071) Function(_072) _071)

Do Until inputEmptyQuery.Invoke(True).Invoke(False)
Dim currentInput = input.Invoke(Function(_073) Function(_074) _073)

Dim fst = currentInput.Invoke(Function(_075) Function(_076) _075)
Dim snd = currentInput.Invoke(Function(_077) Function(_078) _078)

Dim n1 = fst.Invoke(Function(_079) _079 + 1UI).Invoke(0UI)
Dim n2 = snd.Invoke(Function(_080) _080 + 1UI).Invoke(0UI)

Write($"({n1}, {n2}) ")

input = input.Invoke(Function(_081) Function(_082) _082)
inputEmptyQuery = input.Invoke(Function(_083) Function(_084) Function(_085) Function(_086) Function(_087) _087).Invoke(Function(_088) Function(_089) _088)
Loop
WriteLine()

Write("Expected : ")

Dim expected = currentRow.Invoke(Function(_090) Function(_091) _090)
Dim expectedEmptyQuery = expected.Invoke(Function(_092) Function(_093) Function(_094) Function(_095) Function(_096) _096).Invoke(Function(_097) Function(_098) _097)

Do Until expectedEmptyQuery.Invoke(True).Invoke(False)
Dim currentExpected = expected.Invoke(Function(_099) Function(_100) _099)

Dim fst = currentExpected.Invoke(Function(_101) Function(_102) _101)
Dim snd = currentExpected.Invoke(Function(_103) Function(_104) _104)

Dim n1 = fst.Invoke(Function(_105) _105 + 1UI).Invoke(0UI)
Dim n2 = snd.Invoke(Function(_106) _106 + 1UI).Invoke(0UI)

Write($"({n1}, {n2}) ")

expected = expected.Invoke(Function(_107) Function(_108) _108)
expectedEmptyQuery = expected.Invoke(Function(_109) Function(_110) Function(_111) Function(_112) Function(_113) _113).Invoke(Function(_114) Function(_115) _114)
Loop
WriteLine()
WriteLine(New String("-"c, WindowWidth - 1))

rows = rows.Invoke(Function(_116) Function(_117) _117)
rowsEmptyQuery = rows.Invoke(Function(_118) Function(_119) Function(_120) Function(_121) Function(_122) _122).Invoke(Function(_123) Function(_124) _123)
Loop

On peut y voir que les seuls moment où c'est pas de la fonction sont les moments où j'écris dans la console, les tests de boucle (je "sors" un bool de la fonction) et la récupération du nombre (planqué en fonction) en entier pour son affichage

Bon appétit !
Censément, quelqu'un de sensé est censé s'exprimer sensément.

Image
Avatar de l’utilisateur
Sehnsucht
Membre VIP
 
Messages : 289
Points d'honneur : 270 PH
Inscription : 10 Fév 2013

Suivant

Retour vers Discussion

cron
  • Qui est en ligne ?
  • Consulter les nouveaux messages
  • Consulter les messages sans réponse
  • Au total, il y a 2 utilisateurs en ligne :: 1 inscrit, 0 invisible et 1 invité (basé sur le nombre d’utilisateurs actifs des 5 dernières minutes)
  • Le nombre maximum d’utilisateurs en ligne simultanément a été de 272 le 12 Mars 2015, 03:11
  • Utilisateur(s) parcourant ce forum : Google [Bot] et 1 invité