Algo de tableau d'horaires

use_writer · Octobre 20, 2004, 9:56

Bonjour à tous.

Je vous explique mon problème, je cherche à obtenir un algo “intelligent” de modification de tableau contenant des bornes d’horaires (genre tâches dans le planning d’une journée).

Les règles :

j’ai un tableau d’entiers représentant les horaires des tâches (la taille du tableau sera forcément paire, donc)
je cherche à y ajouter une tâche représentée par deux entiers (exemple, 900 et 1250 pour une tâche s’étalant de 9h00 à 12h50)
le but est que l’horaire ajouté dans le tableau remanipule les horaires de manière “intelligente”.
une tâche ne peut pas être vide (au moins une minute de durée)
les deux entiers sont bien évidemment déjà dans le bon ordre
un seul tableau par jour, on ne gère pas les tâches à cheval sur deux jours.

Exemples concrets parce que je ne suis pas sûr d’être clair :
tableau d’origine : 100, 150, 2200, 2330
ajout : 1200, 1300
donne 100, 150, 1200, 1300, 2200, 2330

tableau d’origine : 1100, 1200
ajout : 1000, 1130
donne 1000, 1200 (la tâche rejoint l’autre, on fusionne les deux)

tableau d’origine : 1100, 1130, 1200, 1210, 1300, 1350
ajout : 1000, 1400
donne : 1000, 1400

etc

Bref, comment pourrais-je programmer un algo qui me donnerait un tableau où la tâche ajoutée le serait de façon intelligente ?

J’imagine qu’il faut que je fasse une fonction récursive pour le parcours du tableau, j’ai cherché mais je dois dire que je sèche un peu là… Toute aide est la bienvenue, même si c’est juste pour me donner le nom d’un algo connu résolvant ce problème.

PS : le langage est WINDEV mais vu que c’est un langage que peu de personnes connaissent, je demande un algo générique et je me débrouillerais pour écrire en W-langage.

Kzi · Octobre 20, 2004, 10:33

je reflechi sur ton probleme (j editerai un poil plus tard) mais deja je voie un truc uber relou.

tes heures je trouve que c est un super mauvaise idee de les stocker comme ca il y a une enorme possibilité d erreur. prend plutot le nombre de minute depuis 00h00 c est nettement plus simple exemple: 916 = 15H16 car 916/60 = 15 (stocké dans un int pour la troncature) et 916%60 = 16. pour le creer dans l autre sens c est tout aussi simple du coup : 60*H + min

par contre un autre probleme se pose: avec ton systeme il est impossible de prevoir un rdv qui s etale sur deux jours, en tout cas d apres les elements fournis

EDIT1: ni deux rdv qui se superposent du coup (+fautes )

Ce message a été édité par Kzi le 20/10/2004

BodySplash · Octobre 20, 2004, 11:12

Déjà, je suis entièrement d’accord sur le fait qu’il vaut mieux stocker les minutes écoulés depuis 00h00. (on va rentrer dans les détails, mais j’ai codé un truc du genre, et coryez-moi, c’est mieux )

Ensuite je ne vois pas le problème pour l’insert. Déjà; si tu utilises une file, et pas un tableau, et vu que celle-ci est forcément trié, il te suffit de la parcourir, et d"insérer le nouveau rdv dès que tu rencontres une horaire supérieure (bien sûr, à la fin si tu n’en trouves pas, et au début si la file est vide).

EDIT: ah et il faut penser au cas d’erreur ou le nouveau rdv empiete sur le suivant. Mais là non plus pas de panique. Une fois que tu as trouvé le point d’inser du début du rdv, vérifie le début du suivant pour voire s’il ne gène pas la fin de l’autre.

Désolé au fait mais vu que je suis au boulot, je ne peux pas écire l’algo.
Ce message a été édité par BodySplash le 20/10/2004

kaneloon · Octobre 20, 2004, 11:19

[quote]Bref, comment pourrais-je programmer un algo qui me donnerait un tableau où la tâche ajoutée le serait de façon intelligente ?[/quote]Que veux tu dire ?
Parce que sinon, un bête algo avec ta tâche en entrée, un parcours du tableau jusqu’au premier élément postérieur à la tâche, ensuite parcours jusqu’au premier élément antérieur à la fin de la tâche. puis série de if else entre les deux…

use_writer · Octobre 20, 2004, 11:23

[quote]EDIT1: ni deux rdv qui se superposent du coup (+fautes )[/quote]Oui, je sais et c’est voulu.

Je code une fenêtre permettant d’activer un traitement journalier selon le jour et l’heure.
Ainsi, deux “rendez-vous” qui se chevauchent fusionnent !

Le chevauchement sur deux jours n’est pas voulu.

En fait j’ai déjà posé les bases et les règles, elles sont utilisées ailleurs et ne sont pas à remettre en cause.

Il faut juste que j’arrive à modifier le tableau selon la nouvelle tâche qui y est ajoutée, c’est tout.

Enfin merci de vos conseils et du temps consacré, je reste à l’écoute.

Parce que sinon, un bête algo avec ta tâche en entrée, un parcours du tableau jusqu’au premier élément postérieur à la tâche, ensuite parcours jusqu’au premier élément antérieur à la fin de la tâche. puis série de if else entre les deux…
Oui, c’est ce que je m’étais dit au début et en commençant à coder je me suis aperçu que ce n’était pas si simple puisqu’une tâche peut “effacer” toutes les autres tâches.

Exemple
le tableau de tâches suivantes : 1000, 1100, 1200, 1230, 1400, 1600
donnera pour la tache 900, 1800 le tableau 900, 1800.

On ne sait pas combien d’éléments seront remplacés (ou même s’il y aura des remplacements vu qu’il peut s’agir d’un insert ou encore d’une fusion avec une ou plusieurs tâches existantes).

Ah non c’est pas simple !
Ce message a été édité par use-writer le 20/10/2004

Kzi · Octobre 20, 2004, 11:33

je m y suis penche et en effet c est loin d etre simple, notament pour les cas ou un nouveau rdv fait fusionner deux zones de rdv deja existant … GNIARK

debut d algo bourrin:

creer un table (“all”) genre int[X][2] avec a chaque ligne un couple d heures de rdv + le nouveau.

tant qu il reste des entree dans all :
{
variables: min et max;

creer un autre table (“rdv”);
prendre l entree avec le plus petit debut l ajouter a la table rdv, le supprimer de all, min = debut, max = fin.

parcourir toute la table all, si debut compris entre min et max : elever de la table all, ajouter a rdv, mettre a jour max si necessaire (et recommencer le parcours depuis le debut dans ce cas).

on se retrouve avec un table rdv dont le plus petit debut est le debut recherche, et le plus grand fin la fin cherche.
}

en bouclant on trouve un a un les differentes plages

j affinerai si necessaire ce soir

Ce message a été édité par Kzi le 20/10/2004
Ce message a été édité par Kzi le 20/10/2004

Arkhatope · Octobre 20, 2004, 11:39

Mais si. (Laisse moi 20 minutes, je te l’écris en windev)

(l’optimisme c’est beau )
Ce message a été édité par Arkhatope le 20/10/2004

Luk · Octobre 20, 2004, 11:44

mmm, j’ai une idée bête :
tu entre le début et la fin à la barbare dans ton tableau en insérant au moment où ca commence (et, si t’a 900 1000 à mettre dans 800 830 910 940 1100 1200, ca fait 800 830 900 1000 910 940 1100 1200), puis tu parcours ton tableau pour voir si y’a imcompatibilité d’horaires (le 900 1000 910 940 est pas bon, et là tu fais un traitement suivant les cas)

t’en pense quoi ?

use_writer · Octobre 20, 2004, 11:44

[quote]Mais si. (Laisse moi 20 minutes, je te l’écris en windev)

(l’optimisme c’est beau )
Ce message a été édité par Arkhatope le 20/10/2004[/quote]Si vraiment tu arrives à me trouver un algo (et déjà écrit en Windev en plus, le bonheur !), je te déclare officiellement masta del tableau de horares, grand titre honorifique devant l’éternel

Bon, je continue à creuser de mon côté pendant ce temps…

lucasbfr : hmmm, ton idée est pas bête. Je vais me pencher dessus tiens.
Ce message a été édité par use-writer le 20/10/2004

Arkhatope · Octobre 20, 2004, 12:06

terminé, je teste

Arkhatope · Octobre 20, 2004, 12:23

Aïe je dois m’absenter 3/4 d’heure, je te laisse ce que je fais, et je finirai après si besoin est :

Il me reste une erreur; la ligne « SI dersuppr>AjoutFin OU AjoutDeb… »
est fausse, c’est ce qui me restait à corriger
J’ai écrit l’exemple avec une table comme tu pourras le constater; je te laisse faire le changement, désolé

AjoutDeb est un entier=1000
AjoutFin est un entier=1130
ACheval est un entier
i est un entier
dersuppr est un entier
POUR i=1 A TableOccurrence(montableau)
SI Val(montableau[i])>=AjoutDeb ET Val(montableau[i])<=AjoutFin ALORS
ACheval=1
FIN
FIN

SELON ACheval
CAS 0
i=1
TANTQUE Val(montableau[i]) TableOccurrence(montableau)
i++
FIN
TableInsère(montableau,AjoutDeb,i)
TableInsère(montableau,AjoutFin,i+1)
CAS 1
i=1
TANTQUE montableau[i] TableOccurrence(montableau)
i++
FIN
TableInsère(montableau,AjoutDeb,i)
i++
QUAND EXCEPTION DANS
TANTQUE Val(montableau[i]) TableOccurrence(montableau)
dersuppr=montableau[i]
TableSupprime(montableau,i)
FIN
FAIRE
FIN
SI i

use_writer · Octobre 20, 2004, 12:37

TANTQUE Val(montableau[i]) TableOccurrence(montableau)

Hmmm, je ne comprends pas bien cette ligne…
Il manque l’opérateur non ?
Bug de glopnuke ?

ko1 · Octobre 20, 2004, 12:42

Bon, je disais que j’avais programmé ça en Java … si çe peut t’aider, je pense que ça marche (mise en page puis j’ai corrigé un bug au passage)

public static int[] usewriter(int d, int f) {
int taille = 6;
int[] t = new int[taille];
int[] nt = new int[taille + 2];

t[0] = 1100;
t[1] = 1130;
t[2] = 1200;
t[3] = 1210;
t[4] = 1300;
t[5] = 1350;

int current = 0;

int a1 = searchindice(d, t, 0);
if (a1 == -1) {
current = copyvalues(t, nt, 0, t.length, current);
nt[current] = d;
current ++;
nt[current] = f;
current ++;
} else {
if (a1 % 2 == 0) {
current = copyvalues(t, nt, 0, a1, current);
nt[current] = d;
current++;
} else {
current = copyvalues(t, nt, 0, a1, current);
}
}

if (a1 != -1) {
int a2 = searchindice(f, t, a1);
if (a2 == -1) {
nt[current] = f;
current ++;
} else {
if (a2 % 2 == 0) {
nt[current] = f;
current++;
current = copyvalues(t, nt, a2, t.length, current);
} else {
current = copyvalues(t, nt, a2, t.length, current);
}
}
}

return nt;
}

public static int searchindice(int v, int[] t, int dep) {
for (int i = dep ; i < t.length ; i++) {
if (v < t[i]) return i;
}
return -1;
}

public static int copyvalues(int[] t, int[] nt, int dep, int fin, int ind) {
for (int i = dep ; i < fin ; i++) {
nt[ind] = t[i];
ind++;
}
return ind;
}
public static void main(String[] args) {
try {
usewriter(1500, 1600);
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}

En fait je l’aivas pas vraiment corrigé le bug, maintenant ça y est … enfin je crois

Ce message a été édité par ko le 20/10/2004

Arkhatope · Octobre 20, 2004, 12:49

[quote]TANTQUE Val(montableau[i]) TableOccurrence(montableau)

Hmmm, je ne comprends pas bien cette ligne…
Il manque l’opérateur non ?
Bug de glopnuke ?[/quote]Ca alors… en effet, il me bouffe tous les “ET PAS”. Je retente :

AjoutDeb est un entier=1000
AjoutFin est un entier=1400
ACheval est un entier
i est un entier
dersuppr est un entier
blabla est un booléen
POUR i=1 A TableOccurrence(montableau)
SI Val(montableau[i])>=AjoutDeb ET Val(montableau[i])<=AjoutFin ALORS
ACheval=1
FIN
FIN

SELON ACheval
CAS 0
i=1
TANTQUE Val(montableau[i]) TableOccurrence(montableau)
i++
FIN
TableInsère(montableau,AjoutDeb,i)
TableInsère(montableau,AjoutFin,i+1)
CAS 1
i=1
TANTQUE montableau[i] TableOccurrence(montableau)
i++
FIN
TableInsère(montableau,AjoutDeb,i)
i++
QUAND EXCEPTION DANS
TANTQUE Val(montableau[i]) TableOccurrence(montableau)
dersuppr=montableau[i]
TableSupprime(montableau,i)
FIN
FAIRE
FIN
SI i

Arkhatope · Octobre 20, 2004, 12:52

argh en fait, ils disparaissent quand j’édite mon message !

(désolé, je recolle

AjoutDeb est un entier=1000
AjoutFin est un entier=1400
ACheval est un entier
i est un entier
dersuppr est un entier
blabla est un booléen
POUR i=1 A TableOccurrence(montableau)
SI Val(montableau[i])>=AjoutDeb ET Val(montableau[i])<=AjoutFin ALORS
ACheval=1
FIN
FIN

SELON ACheval
CAS 0
i=1
TANTQUE Val(montableau[i])<AjoutDeb ET PAS i> TableOccurrence(montableau)
i++
FIN
TableInsère(montableau,AjoutDeb,i)
TableInsère(montableau,AjoutFin,i+1)
CAS 1
i=1
TANTQUE montableau[i] TableOccurrence(montableau)
i++
FIN
TableInsère(montableau,AjoutDeb,i)
i++
QUAND EXCEPTION DANS
TANTQUE Val(montableau[i]) TableOccurrence(montableau)
dersuppr=montableau[i]
TableSupprime(montableau,i)
FIN
FAIRE
FIN
SI i<TableOccurrence(montableau) ALORS
TableInsère(montableau,AjoutFin,i)
// blabla=1
SINON
SI dersuppr>AjoutFin OU AjoutDeb>dersuppr ALORS
TableAjoute(montableau,AjoutFin)
FIN
FIN
FIN

ko1 · Octobre 20, 2004, 12:58

[quote]C’est en windev 5.5b. J’avais pas le 7.5 ou le 8 d’ouvert quand j’ai commencé à reflechir.

i est un entier
j est un entier
k est un entier …[/quote]Euh, je ne connais pas du tout Windev, le code il est vraiment comme ça ?

Donjohn · Octobre 20, 2004, 1:02

[quote][quote] C’est en windev 5.5b. J’avais pas le 7.5 ou le 8 d’ouvert quand j’ai commencé à reflechir.

i est un entier
j est un entier
k est un entier …[/quote]Euh, je ne connais pas du tout Windev, le code il est vraiment comme ça ?
[/quote]oui, mais si ca te gene je le tappe en anglais ca fera plus 1337 et plus proche des autres langages (entre printf() et info(), je ne vois aucune difference…)

Arkhatope · Octobre 20, 2004, 1:04

Donjohn, j’ai testé ton exemple dans le 1er cas, il me semble que ça ne fonctionne pas (renvoie 3 lignes, les 3 égales à 1300)

Donjohn · Octobre 20, 2004, 1:07

ouais ? je vais voir ca

Arkhatope · Octobre 20, 2004, 1:15

ppffioou j’en ai mal à la tête

Une solution qui semble fonctionner dans tous les cas :

AjoutDeb est un entier=1000
AjoutFin est un entier=1400
ACheval est un entier
i est un entier
dersuppr est un entier
blabla est un booléen
POUR i=1 A TableOccurrence(montableau)
SI Val(montableau[i])>=AjoutDeb ET Val(montableau[i])<=AjoutFin ALORS
ACheval=1
FIN
FIN

SELON ACheval
CAS 0
i=1
TANTQUE Val(montableau[i])<AjoutDeb ET PAS i> TableOccurrence(montableau)
i++
FIN
TableInsère(montableau,AjoutDeb,i)
TableInsère(montableau,AjoutFin,i+1)
CAS 1
i=1
TANTQUE montableau[i] TableOccurrence(montableau)
i++
FIN
TableInsère(montableau,AjoutDeb,i)
i++
QUAND EXCEPTION DANS
TANTQUE Val(montableau[i]) TableOccurrence(montableau)
dersuppr=montableau[i]
TableSupprime(montableau,i)
FIN
FAIRE
FIN
SI i<TableOccurrence(montableau) ALORS
TableInsère(montableau,AjoutFin,i)
// blabla=1
SINON
SI dersupprdersuppr ALORS//ou (dersuppr<Ajoutfin et AjoutDeb<dersuppr) alors
SI montableau[TableOccurrence(montableau)]<AjoutFin ALORS
TableAjoute(montableau,AjoutFin)
FIN
FIN
FIN
FIN

Dommage, j’étais vraiment tout proche à mon premier jet. Manquait un petit test, quoi