Algo de tableau d'horaires

Dev
41

Oui bon ca va

Et pourtant, ce que j’ai énoncé comme un blague au début est, je pense, une bonne méthode.
D’ailleurs, une solution simple :
(bon, evidemment, je ne déclare pas 1440 booleens)

Journée est une chaîne = Répète(“0”,1440)
i est un entier
j est un entier
TableAjoute(montableau,1200)
TableAjoute(montableau,1300)
Debplage est un entier
finplage est un entier
POUR i=1 A TableOccurrence(montableau) PAS 2
 POUR j=(PartieEntière(Val(montableau[i])/100)60)+modulo(Val(montableau[i]),100) A (PartieEntière(Val(montableau[i+1])/100)60)+modulo(Val(montableau[i+1]),100)
Journée[[j]]=1
 FIN
FIN
POUR i=1 A Taille(Journée)
 TANTQUE PAS Journée[[i]]=“1” ET PAS i>=Taille(Journée)
 i++
 FIN
 Debplage=i
 TANTQUE PAS Journée[[i]]=“0” ET PAS i>=Taille(Journée)
i++
 FIN
 SI PAS (i=1440 ET Journée[[1440]]=“0”) ALORS
 finplage=i-1
 Debplage=EntierVersHeure(Debplage6000)
 Debplage=Debplage/10000
 finplage=EntierVersHeure(finplage6000)
 finplage=finplage/10000
 TRACE("debut : "+Debplage+ " fin : "+finplage)
 FIN
FIN

42

[quote]QUAND EXCEPTION DANS
 TANTQUE Val(montableau[i]) TableOccurrence(montableau)
dersuppr=montableau[i]
TableSupprime(montableau,i)
 FIN
FAIRE

…[/quote]Je suis pas sur de comprendre, donc si je me gourre je m’excuse mais j’ai peur de voir un truc ignoble la. Si tu fais du branchement logique base sur le lancement d’une exception c’est ULTRA, TOP, MEGA, GIGA mal. Genre en C# si tu faisait:

public int longeur(string s) {
 try {
return s.Length;
 } catch (NullException e) {
return 0;
 }
}

Ou qqch d’equivalent tu te prend un coup de pied au cul et 500 lignes a copier “Je ne ferais pas de branchement logique avec des exceptions.” Arf

PS: C’est illisible ce truc avec des mots clefs en majuscule de partout, pire que du VB…
Ce message a été édité par GloP le 20/10/2004

43

Non, il ne s’agit pas d’un embranchement logique mais d’un simple “s’il y a une erreur là dedans alors c’est pas grave, continue quand même”.
Je l’ai placé par fainéantise pour éviter je ne sais plus quel cas particulier (probablement si i ne correspond plus une ligne de la table).
Pas taper, c’est normal (mais pas propre, j’en conviens).

Par contre tu tombes bien, tu as dû voir le petit bug qui m’a fait disparaitre les “ET PAS” de mon message ?

44

Bon, personne n’a réussi à trouver de solution qui fonctionne (désolé ko, ta solution ne fonctionne pas dans tous les cas de figure).

Bon, je continue de chercher mais ça commence à me prendre la tête…

GloP : en dehors des critiques d’ordre esthétique sur le W-langage, tu n’as pas une petite idée pour mon problème ?

Edit : je suis de plus en plus persuadé qu’il faut faire appel à une fonction récursive pour ce problème, je planche là dessus !
Ce message a été édité par use-writer le 21/10/2004

45

Ah ? ma dernière solution fonctionne dans tous les cas énoncés, chez moi

46

Ah ? Pas de bol … ça c’est à cause du Java, ça ramollit le cerveau je trouve 
Tu pourrais me donner les cas où ça ne fonctionne pas ?
Sinon, j’avais eu une autre idée d’algo, je vais voir si j’arrive à l’implémenter.

47

Je l’utiliserais si je n’arrive pas à me dépétrer de mon idée de fonction récursive.

ko : d’après ce que j’ai compris en regardant ton programme, il n’y aura pas de « recouvrement ».

Exemple, si mon tableau contient 1000, 1100, 1300, 1400
si j’ajoute 800, 1600, mon tableau ne contiendra pas 800, 1600 (qui aura écrasé les autres temps d’occupation puisqu’il englobe ceux existants).

Ou alors je n’ai pas réussi à simuler ton algo correctement…

48

Bidouille certes, mais je ne vois pas le problème…

Enifin bon, je vous laisse entre pros des simplex et multiplex (gnagna)

49

Bon, je suis en passe… de RESOUDRE le problème !!!

J’arrive à des résultats pas trop mal là (plantage dans un cas) avec une fonction récursive qui a l’air de bien marcher.

Je vous poste mon code dès que j’en suis sûr à 100% (et après avoir becqueté).

50

En effet, tu n’as pas dû réussir à bien le simuler … C’est vrai que le code en Java c’est pas l’idéal pour ça, pour la peine, je vais essayer d’expliquer un peu ma méthode (avec des vrais mots, c’est pas gagné d’avance) :

  • Le principe que j’utilise, c’est de trouver la place éventuelle des deux heures à insérer.

  • Pour le premier, je recherche l’indice du premier entier qui lui est supérieur, puis je copie dans le tableau résultat tous les entiers précedent cet indice.

Exemple : 1000 1100 1300 1400
Si je veux insérer 800, mon tableau résultat est vide.
Si je veux insérer 1030, mon tableau résultat est 1000.
Si je veux insérer 1200, mon tableau résultat est 1000 1100.
Si je veux insérer 1500, mon tableau résultat est 1000 1100 1300 1400.

Ensuite, je regarde cet indice : s’il n’existe pas d’entier supérieur (dans mon algo -1), j’insère mes deux horaires et j’obtiens quelque chose comme 1000 1100 1300 1400 1500 1600. L’algo se termine ensuite.
Ensuite s’il existe, je regarde sa parité : s’il est pair je l’insère, sinon non.

Pour reprendre mes exemples :

Si je veux insérer 800, mon tableau résultat est 800 (indice 0).
Si je veux insérer 1030, mon tableau résultat est 1000 1100 (indice 1).
Si je veux insérer 1200, mon tableau résultat est 1000 1100 1200 (indice 2).
Si je veux insérer 1500, mon tableau résultat est 1000 1100 1300 1400 1500 XXXX (indice -1).

  • Et pour le deuxième c’est le même principe : je recherche l’indice du premier entier supérieur. Je regarde s’il est nécessaire de placer l’heure (si l’indice est pair, oui, sinon non) puis éventuellement j’insère le reste de la liste à partir de l’indice. (Si l’indice vaut -1, je ne place pas le reste de la liste).

(Je speede j’ai un entretien chez Alten ce midi, si besoin je détaillerai plus cet aprèm.)

Voilà je ne sais pas si je suis clair, mais bon j’espère que ça pourra t’aider …

51

J’Y SUIS ARRIVÉ !!!

Premier appel :

SI TableauInfo(iet_jour,tiDimension) = 0 ALORS
 //aucun élément, c’est facile
 TableauAjoute(iet_jour, le_HeureDeb)
 TableauAjoute(iet_jour, le_HeureFin)
SINON
 TableauSupprimeTout(iet_TabTampon)
POUR le_I2 = 1 A TableauInfo(iet_jour,tiDimension) / 2
Test_Recouvrement(iet_jour, le_HeureDeb, le_HeureFin, le_I2)
 FIN
 TableauCopie(iet_TabTampon, {ict_Jours[le_I]})
FIN
Et la fonction récursive :

FONCTION Test_Recouvrement(pc_NomTableau est une chaîne, pe_ValAjoutDeb est un entier, pe_ValAjoutFin est un entier, pe_Indice est un entier)
le_BorneDeb, le_BorneFin sont des entiers
SI TableauInfo({pc_NomTableau}, tiDimension) >= pe_Indice * 2 ALORS
 //Récupération des bornes
 le_BorneDeb = {pc_NomTableau}[pe_Indice * 2 -1]
 le_BorneFin = {pc_NomTableau}[pe_Indice * 2]
SINON
 //Insertion directe. On a dépassé le niveau max
 TableauAjoute(iet_TabTampon, pe_ValAjoutDeb)
 TableauAjoute(iet_TabTampon, pe_ValAjoutFin)
 RENVOYER 2
FIN
SI pe_ValAjoutDeb < le_BorneDeb ALORS
 SI pe_ValAjoutFin < le_BorneDeb ALORS
//Complètement avant la borne suivante, insère et renvoie 1
TableauAjoute(iet_TabTampon, pe_ValAjoutDeb)
TableauAjoute(iet_TabTampon, pe_ValAjoutFin)
TableauAjoute(iet_TabTampon, le_BorneDeb)
TableauAjoute(iet_TabTampon, le_BorneFin)
RENVOYER 1
 SINON
SI pe_ValAjoutFin <= le_BorneFin ALORS
 //Rejoint la borne suivante sans dépasser le recouvrement, insère et renvoie 3
 TableauAjoute(iet_TabTampon, pe_ValAjoutDeb)
 TableauAjoute(iet_TabTampon, le_BorneFin)
 RENVOYER 3
SINON
 //les valeurs à insérer incluent la borne actuelle
 pe_Indice++
 SI Test_Recouvrement(pc_NomTableau, le_BorneDeb, pe_ValAjoutFin, pe_Indice) = 5 ALORS
RENVOYER 5
 FIN
FIN
 FIN
SINON
 SI pe_ValAjoutDeb <= le_BorneFin ALORS
//Débute dans la borne actuelle
SI pe_ValAjoutFin <= le_BorneFin ALORS
 //Les valeurs à ajouter sont inclues dans les bornes, l’ajout est inutile, on insère néanmoins les valeurs
 TableauAjoute(iet_TabTampon, le_BorneDeb)
 TableauAjoute(iet_TabTampon, le_BorneFin)
 RENVOYER 6
SINON
 pe_Indice++
 SI Test_Recouvrement(pc_NomTableau, le_BorneDeb, pe_ValAjoutFin, pe_Indice) = 5 ALORS
RENVOYER 5
 SINON
RENVOYER 4
 FIN
FIN
 SINON
//Insertion “propre” à la suite de la borne
TableauAjoute(iet_TabTampon, le_BorneDeb)
TableauAjoute(iet_TabTampon, le_BorneFin)
pe_Indice++
SI Test_Recouvrement(pc_NomTableau, pe_ValAjoutDeb, pe_ValAjoutFin, pe_Indice) = 5 ALORS
 RENVOYER 5
SINON
 RENVOYER 2 
FIN
 FIN
FIN
RENVOYER 0
A noter que les retours ne sont (presque pas) utilisés mais me permettent de me repérer dans le code.

Le tableau iet_TabTampon est un tableau d’instance (portée dans tout l’objet), nécessaire pour que le lien entre les différents appels à la fonction travaillent sur un tableau viable.

Pour ceux qui ne connaissent pas windev, les opérateurs {} permettent de faire une référence dynamique à un contrôle/une variable à l’éxecution et les fonction TableauInfo(), TableauAjoute() etc sont des fonctions intégrées au langage.

Quand on vous dit que c’est puissant…

Ah oui, et le premier qui critique ma façon de nommer les variables se prends un double combo de programmeur furax (“mouahah, on code plus ça depuis longtemps, c’est dépassé”, rien à foutre au moins je connais le type et la portée de mes variables !).

52

[quote]Pour ceux qui ne connaissent pas windev, les opérateurs {} permettent de faire une référence dynamique à un contrôle/une variable à l’éxecution et les fonction TableauInfo(), TableauAjoute() etc sont des fonctions intégrées au langage.[/quote]J’aurais du commencer à reflechir en 8.0, ca m’aurait permis d’utiliser ces fonctions au lieu de me peter les couilles avec la fonction Dimension

Bon bah en recursif, c’est propre…

J’avais encore un probleme avec ton derniere cas, maintenant que tu y es arrivé, je laisse tomber

Bien Joué Use

53

Ah oui…

MERCI A TOUS pour vos recherches, vous le méritez bien !

edit : oups, je viens de voir un bug… Bon, je corrige.
Ce message a été édité par use-writer le 21/10/2004

54

Maintenant, ça m’intéresserait de savoir pourquoi cette soluce est meilleure que la mienne (sérieusement, histoire de comprende, quoi).

55

Et puis aussi parce que ça tape, les fonctions récursives…

Et je pense que l’utilisation mémoire est moindre mais là je m’avance.

Non en fait c’est complètement subjectif.
C’est juste qu’on est toujours plus fier d’utiliser son propre code (la preuve, tu préfères le tien ! ).

En tout cas je te remercie pour ta soluce.

(en passant, il reste des bugs à corriger dans certains cas mais à mon avis c’est plus trop loin de l’utilisation que j’en attends).

56

N’empeche, je suis toujours persuader qu’un probleme de planification d’horaire avec contraintes (reservation de voies pour un train, une salle de reunion, ou encore des jalons de tache) se resoud de manieres optimales avec un simplex

Bon, c’est pas la question, en fait, j’avais pas compris ce que tu voulais faire, c’est tout

57

[quote]C’est juste qu’on est toujours plus fier d’utiliser son propre code (la preuve, tu préfères le tien ! ).[/quote]Hin hin (c’était sincérement une vraie question, je suis toujours curieux de savoir pourquoi tel chemin est meilleur qu’un autre)

En tout cas c’est marrant comme ce problème avait l’air simple et est en fait une belle saloperie. J’aurais juré le finir en une heure si on me l’avait présenté comme ça, tout innocent, prêt à être torché en surfant sur cafzone.

58

Je me permet juste de signaler que dans 99% des cas, l’itératif est plus puissant que le récursif, contrairement aux idées reçues. J’ai testé, sur un de mes algos il y a pas mal de temps, et même si le code du coup paraissait moins clean, le résultat était là: version itérative plus puissante. Le seul bémol c’est qu’il est souvent difficile de concevoir correctement la version itérative par rapport à la version récursive.

59

J’ai suivi de loin la conversation.

Cela a un rapport avec cela ?
Segmentation Fault > [SQL] La meilleure méthode pour stocker une arborescence 
qui pointait là dessus : SQLPro: Gestion d’arbres par représentation intervallaire ?

A part que cet URL parle en SQL on dirait que c’est le même problème que ce tableau d’horaire.

60

[quote]J’ai suivi de loin la conversation.

Cela a un rapport avec cela ?
Segmentation Fault > [SQL] La meilleure méthode pour stocker une arborescence 
qui pointait là dessus : SQLPro: Gestion d’arbres par représentation intervallaire ?

A part que cet URL parle en SQL on dirait que c’est le même problème que ce tableau d’horaire.[/quote]Non, rien à voir.

Mais je ne connaissais pas cette méthode de représentation d’arborescence intervallaire et je la trouve très très intéressante… Merci pour le lien.