culmea separării lucrurilor…

M-am ocupat mult timp (dar acum vreo 20 de ani) de orarul şcolii, folosind un program propriu. Acest program avea două părţi: mai întâi se obţinea o "schemă" de repartizare a orelor pe zilele săptămânii; apoi - după definitivarea manuală a acestei scheme - se obţineau orarele zilnice.

Şcoala funcţionează cu două schimburi şi sunt fixate de la bun început, lista claselor care pe parcursul anului şcolar vor avea ore în intervalul orar 8-14 şi respectiv, lista claselor cu orele în intervalul orar 14-20; de regulă, fiecare clasă are câte 5-6 ore pe zi, dar unele clase trebuie să aibă în unele zile câte 7 ore (8-15, respectiv 13-20).

Exceptând eventual intervalul (de două ore) 13-15, orele dintr-un schimb nu se pot suprapune cu ore din celălalt schimb - încât mi s-a părut firesc - dar aşa consider şi astăzi - să vizez separat cele două schimburi: practic, programul trebuie rulat de două ori, corespunzător fiecărui schimb.

Furnizam datele iniţiale prin lista claselor (codificate direct, prin câte o literă):

ABCDEFGVWabcdefg  # clasele a XI-a: ABCDEFG; a V-a: V; a VI-a: W; a XII-a: abcdefg

şi printr-un fişier text conţinând încadrările pe săptămână (şi restricţiile de zile) ale profesorilor:

Alexa: B3 g4  # 3 ore la clasa XI-B şi 4 ore la clasa XII-G
Alexandrescu: d1 e1 g7 -2  # fără ziua 2 (marţi="liber")
Anitei: V1 W1 -135  # orele trebuie puse în zilele 2 (marţi) şi/sau 4 (vineri)
Anusca: A2 C2 D1 F1 G1 c1 e2 
...

În ultima versiune (prin anul 2002), obţineam schema de repartizare folosind Perl (beneficiind astfel de "expresii regulate" şi de "tablouri asociative"), sub Linux; dar pentru orarele zilnice foloseam Borland C++3.1 şi o subrutină scrisă în Turbo Assembler - sub DOS/Windows, cu I-486. Astăzi îmi dau seama că această manieră neortodoxă de lucru este "culmea" principiului separării lucrurilor.

Repartizarea omogenă a orelor pe zilele săptămânii

Considerăm ca indiscutabil, principiul repartizării omogene a orelor; de exemplu, dacă profesorul are 3 ore pe săptămână la cutare clasă - atunci acestea trebuie repartizate câte una pe zi, pe cât posibil cu distanţă de o zi între ele; iar dacă profesorul are în schimbul respectiv 20 de ore - atunci acestea trebuie repartizate în mod echilibrat (câte 4 ore în fiecare zi şi nicidecum ca 6/6/6/2/0).

Programul nostru este bazat pe acest principiu, repartizarea orelor pe zilele săptămânii fiind realizată pe baza unui "tablou asociativ" calculat în prealabil: ("zile de lucru", "număr de ore la clasă") => listă de şabloane posibile de repartizare.

Încadrările de tip (A, n) cu n ≥ 5 (însemnând că profesorul are la clasa 'A' cel puţin 5 ore/săptămână) se reduc automat la încadrări de tip (A, n-5): programul repartizează câte 1 oră la clasa 'A' în fiecare zi şi rămân de repartizat doar n-5 ore (dacă n-5 < 5; altfel, se mai iterează o dată).

Prin urmare, avem de vizat doar încadrări de tip (A, n) cu 1 ≤ n ≤ 4; putem avea şi acum, simplificări - de exemplu în cazul unui profesor pentru care avem restricţia "-2" (adică "liber în ziua 2"), încadrarea de tip (A, 4) este imediat omisă (cele 4 ore fiind repartizate în cele 4 zile de lucru, câte una pe zi).

Am definit nişte măşti binare pentru cele 5 zile de lucru, prin lista ("array Perl") @Z = (1, 2, 4, 8, 16): bitul de rang 0 corespunde cu "Luni", cel de rang 1 cu "Marţi", etc. Şablonul binar 0x1F (în care primii 5 biţi sunt '1') reprezintă situaţia când profesorul nu are nici o restricţie de zile; conform simplificărilor arătate mai sus, el poate avea cel mult 4 ore la clasa respectivă - iar în cazul a 4 ore, repartizarea acestora se poate face după unul dintre următoarele cinci şabloane:

0x1F =>  # zile de lucru: toate cele 5; număr de ore la clasă: 4
    [ 0x0F,  # 00001111 - în primele 4 zile (câte o oră la clasa respectivă)
      0x17,  # 00010111 - Luni, Marţi, Miercuri şi Vineri (fără Joi)
      0x1B,  # 00011011 - Luni, Marţi, Joi, Vineri (fără ziua 3)
      0x1D,  # 00011101 - Luni, Miercuri, Joi, Vineri (fără ziua 2)
      0x1E   # 00011110 - Marţi, Miercuri, Joi, Vineri (fără ziua 1)
    ],

Mascăm cheia 0x1F cu 0x20, 0x40, sau cu 0x80 pentru a stabili cheile corespunzătoare cazurilor în care profesorul are 3 ore, 2 ore, respectiv 1 oră la clasa respectivă - rezultând şabloanele posibile de repartizare, pentru cazul când zilele de lucru nu sunt restricţionate:

0x3F => [0x15, 0x0B, 0x19, 0x16, 0x1A, 0x0D, 0x13, 0x0E, 0x1C, 0x07],
0x5F => [0x05, 0x0A, 0x09, 0x11, 0x06, 0x03, 0x12, 0x0C, 0x14, 0x18],
0x9F => [0x01, 0x02, 0x04, 0x08, 0x10],

De exemplu, pentru încadrarea (A, 3) avem cheia 0x1F | 0x20 = 0x3F cu repartizările 00010101 = 0x15 (cea mai de dorit: Luni, Miercuri, Vineri), 00001101 = 0x0B, etc.; pentru cazul (A, 2) avem cheia 0x1F | 0x40 = 0x5F cu repartizările 0x05 (Luni şi Miercuri), 0x0A (Marţi şi Joi), ş.a.m.d.

În cazul restricţiilor asupra zilelor de lucru, mascăm cheile considerate mai sus cu ~$Z[$zi - 1], unde variabila Perl $zi are ca valoare rangul 1..5 al zilei "libere". De exemplu, pentru restricţia "-2" (Marţi = liber) obţinem cheia 0x1F & ~0x02 = 0x3D pentru cazul a 3 ore la clasă - repartizarea asociată fiind [0x0D, 0x15, 0x19, 0x1C]. Pentru cazul a 2 ore la clasă, putem avea 0x5D => [0x05, 0x09, 0x11, 0x0C, 0x14, 0x18]; ş.a.m.d.

Pe baza sistemului de şabloane de repartizare constituit cum am exemplificat mai sus, programul transformă fişierul de încadrare care i-a fost indicat într-un tablou conţinând câte un hash pentru fiecare profesor; de exemplu, pentru încadrarea:

Talpalaru: C2 D2 W4 d2 g2 -2  # Marţi: liber

avem acest "dicţionar" (hash, în Perl):

          {
            'PROF' => 'Talpalaru',
            'ORAR' => { # Zi => orele repartizate pe acea zi
                        '0' => 'W      ',  # Luni
                        '1' => '       ',
                        '2' => 'W      ',
                        '3' => 'W      ',
                        '4' => 'W      ',
                      },
            'NOP' => [1, 0, 1, 1, 1, 4],  # ore plasate; 4 = (2+2+4+2+2)/4 + 1 (3-4 ore/zi)
            'SAB' => { # şabloane de repartizare a orelor rămase, pentru fiecare clasă
                       'g' => [5, 9, 17, 12, 20, 24], # 2 ore în 2 zile diferite de Marţi
                       'C' => [5, 9, 17, 12, 20, 24],
                       'd' => [5, 9, 17, 12, 20, 24],
                       'D' => [5, 9, 17, 12, 20, 24],
                     }
          },

Având numai 4 zile de lucru - încadrarea (W, 4) a fost rezolvată direct (înscriind 'W' în hash-ul indicat de 'ORAR'); orele rămase (câte două, la clasele C, D, d, g) urmează să fie repartizate (completând 'ORAR') astfel încât să nu se depăşească decât cel mult cu o oră, raportul - înregistrat pe ultimul loc în 'NOP' - dintre numărul total de ore şi numărul de zile de lucru.

Cât timp numărul de ore nerepartizate depăşeşte o anumită valoare prestabilită (10, sau să zicem 4% din totalul orelor de repartizat), tabloul acestor hash-uri este "randomizat" (invocând funcţia shuffle din modulul Perl List::Util) şi apoi este parcurs în noua ordine, completând secţiunile 'ORAR' pe baza şabloanelor din 'SAB' care se potrivesc contextului curent al lucrului. În final - când numărul de ore nerepartizate este sub limita prestabilită - repartizarea constituită se înscrie într-un fişier precum:

    # ... #
Bulete     aCCa...  aCW....  aCW....  aCW....  aCW....  
    # ... #
Cosovanu   Ccb....  ca.....  Ccb....  ca.....  Cab....  
    # ... #
Talpalaru  Wg.....  .......  Wg.....  WdD....  WdD....  C2  # 2 ore lipsă, la clasa 'C'
    # ... #
--------------------
A: 6 6 6 6 6
B: 6 6 6 6 6
C: 6 4 6 6 6  # clasei 'C' îi lipsesc 2 ore, în ziua 2 (Marţi)
    # ... #
g: 5 5 6 6 6
--------------------
10 ore nerepartizate

Este uşor să completăm manual repartizarea obţinută astfel, folosindu-ne de informaţiile furnizate în fişier; de exemplu pentru cazul considerat mai sus, cele 2 ore la clasa 'C' care lipsesc la 'Talpalaru' ar trebui puse (cel mai bine, după principiul omogenităţii) în zilele 1 şi 3 - şi în acest scop observăm deasupra că - fără a "strica" nimic - putem muta o oră 'C' la 'Bulete' din ziua 1 în ziua 2 şi una la 'Cosovanu' din ziua 3 în ziua 2:

Bulete     aCa....  aCCW...  aCW....  aCW....  aCW....  
Cosovanu   Ccb....  caC....  cb.....  ca.....  Cab....  
Talpalaru  WCg....  .......  WCg....  WdD....  WdD....

Acum 'C' are 6 ore şi în ziua 2, iar 'Talpalaru' are înscrise toate orele. Rezolvăm similar celelalte 8 ore care au rămas nerepartizate şi desigur, putem face după caz diverse alte ajustări.

Orarul propriu-zis, asociat unei scheme de repartizare a orelor

Pentru fiecare zi, trebuie extrasă sub-schema corespunzătoare acesteia - urmând să realizăm orarul propriu-zis pentru ziua respectivă; de exemplu, pentru repartiţia redată mai sus 'WCg....', pentru ('Talpalaru', ziua 1) - avem de stabilit a câta oră 1..7 din zi intră la clasa 'W', respectiv la 'C' şi la 'g', având în vedere că doi profesori nu pot intra simultan la o aceeaşi clasă.

Dar ne-am propus din start, scopul maximal posibil: să obţinem un orar cu zero ferestre. Utilizăm caracterul '.' pentru a desemna "oră liberă" sau "fereastră" - de exemplu, reprezentarea '..W.Cg.' ar însemna că profesorul respectiv are "liber" primele două ore din zi, are a III-a oră la clasa 'W', apoi are o fereastră şi ora a V-a la 'C', etc.; ce dorim este ca '.' să nu apară niciodată între două litere.

În condiţiile din anul 2000 (cu Intel-486 şi Turbo Assembler, sub DOS), am conceput o structură de memorie _ORZ cât se poate de compactă, pentru date şi pentru anumiţi indicatori de lucru, împreună cu o subrutină _engine în limbaj de asamblare, care parcurge şi întreţine în manieră "backtracking" zona de memorie respectivă, conducând într-un timp rezonabil la orarul fără ferestre dorit.

Zona _ORZ este constituită şi furnizată subrutinei _engine printr-un program C intermediar, plecând de la fişierul care conţine schema de repartizare a orelor pentru ziua respectivă; mai precis - pentru fiecare zi se constituie _ORZ, se apelează subrutina externă _engine, se reţine orarul setat în _ORZ de această subrutină, iar în final se înscrie într-un fişier text orarul complet (pe toate zilele).

după 15 ani…

Reluând după aproape 15 ani preocupările mele pentru orarul şcolar, am constatat întâi că programul Perl pentru obţinerea unei scheme de repartizare pe zile a orelor (descris mai sus) încă funcţionează, fără nicio modificare prealabilă; bineînţeles că acum viteza de execuţie este mult sporită, încât am putut obţine uşor scheme care lasă nerepartizate cel mult 2-3% din numărul total de ore - ceea ce face ca definitivarea manuală a repartizării respective să fie aproape banală.

Pot recunoaşte astăzi (spre deosebire desigur, de nivelul din 2002) că mecanismul care conduce la o schemă de repartizare în programul Perl menţionat este unul de tip "Monte Carlo" (vezi Aplicaţii elementare ale metodei Monte Carlo); se ajunge la o schemă cu cel mult 3% ore nerepartizate prin "eşuarea" câtorva zeci de mii de reordonări aleatoare, ale tabloului de hash-uri asociate profesorilor. Ar fi de precizat că iniţial (ceva mai înainte de 2002) chinuiam un program C++ "echivalent" celui în Perl descris mai sus, bazat însă pe mecanismul backtracking obişnuit; cum-necum - el se comporta mult mai prost decât formularea Perl ulterioară, bazată pe "Monte Carlo" (în loc de "backtracking").

În ceea ce priveşte partea a doua a programului - obţinerea orarelor zilnice propriu-zise, pe baza schemei de repartizare a orelor pe zilele săptămânii - lucrurile stau cu totul altfel: astăzi lucrez pe x86_64 şi nu pot exploata direct subrutina în Turbo Assembler _engine. Urmează desigur, să ne ocupăm (în articolele următoare) de "modernizarea" acestei subrutine…