Asupra unui orar școlar
[*] V. Bazon - Logica producerii unui orar al școlii, Recreații Matematice XXVII Nr. 2 (2025)
Redăm parțial un orar descărcat mai demult de pe site-ul unei anumite școli:
Documentele respective, în format "PDF 1.7 Tagged", proveniseră din Microsoft Word (a răsfoi eventual, overleaf.com/ #Introducing_tagged_PDF):
pdfinfo ORAR-profesori-A3-an-scolar-2024_2025.pdf
Author: Biblio
Creator: Microsoft® Word LTSC
Producer: Microsoft® Word LTSC
CreationDate: Mon Oct 7 12:51:38 2024 EEST
ModDate: Tue Oct 8 11:20:19 2024 EEST
Custom Metadata: no
Metadata Stream: yes
Tagged: yes
UserProperties: no
Suspects: no
Form: none
JavaScript: no
Pages: 3
Encrypted: no
Page size: 1190.74 x 842.06 pts (A3)
Page rot: 0
File size: 728457 bytes
Optimized: yes
PDF version: 1.7
Ne-ar interesa datele, nu imaginile; am încercat vreo două convertoare "on-line", dar niciunul n-a reușit să extragă textul necesar (însă n-am accesat variante "Premium", cu plată). Așa că, fără a mai insista asupra formatului "tagged PDF", am adoptat procedeul clasic ("muncitoresc"): am constituit întâi un fișier prof.csv, în care am tastat numele profesorilor (citite din primul fișier PDF) și am pastat după fiecare secvența de 7 virgule:
# fișierul "prof.csv" prof,1,2,3,4,5,6,7 # antetul CSV (numele coloanelor) Andone Emanuel,,,,,,, Arghire Cristiana,,,,,,, Asandulesei-Budeanu Maria,,,,,,, # ș.a.m.d. (total: 72 profesori)
Apoi, folosind Bash, am copiat "prof.csv" pe fișiere-orar zilnice:
for zi in {Lu,Ma,Mi,Jo,Vi}; do
cp prof.csv "$zi.csv"; done
Apoi, am încărcat în editorul de text ("Gedit") fișierul "Lu.csv" și am tastat la fiecare profesor, pe locurile ținute de virgule, clasele citite (cu mare atenție) de pe coloana titrată cu "Luni" din fișierul PDF al profesorilor (fișier rămas deschis într-o fereastră alăturată celeia în care avem Gedit):
# fișierul "Lu.csv" prof,1,2,3,4,5,6,7 Andone Emanuel,10D,10D,9G,9G,10H,10H, Arghire Cristiana,,,,,,, Asandulesei-Budeanu Maria,10E,9C,10J,9E,10B,10C, # ș.a.m.d.
Lucrurile trebuie apoi repetate pentru celelalte zile…
Procedeul "băbesc" arătat este cel mai sigur, pentru extragerea datelor (și afară de faptul specific că este plictisitor, nu pare greu); extragerea automată a datelor (fără să plătești pentru asta) ar impune un studiu temeinic al formatului "tagged PDF" (format care introduce o "structură logică", bineînțeles complicată, pentru tabelul de date afișat) — studiu care este chiar plictisitor (și inutil)… Singurul scop al formatului PDF este afișarea (dar independent de "dispozitivul de afișare" folosit); firmele Microsoft și Adobe au făcut averi uriașe, inventând formatele de afișare specifice (".doc" și PDF) și speculând cu talent lipsa de pregătire caracteristică majorității utilizatorilor de calculatoare, conducând la adoptarea acestor formate de către toate instituțiile publice și de toți cei care nu-s interesați de date (și de prelucrări), ci doar de tabelarea vizuală, grafică, a acestora (folosind în acest scop numai mouse-ul, butoanele și meniurile de editare oferite; și tuturor acestora li s-a părut mai ușor să "învețe" butoanele și meniurile, decât să se deprindă cu folosirea unui editor de text decent).
Fișierele PDF arătate mai sus tabelează cu o grafică admirabilă un set relativ mic de date, pe dimensiuni de memorie de ordinul a 105 bytes; în schimb, fișierele-text în format CSV rezultate ca mai sus (măsurând fiecare sub 3000 bytes) permit obținerea ușoară a oricăror informații privitoare la orarul școlii; în plus, dacă ai o anumită pregătire (te pricepi la HTML, la LaTeX și să zicem la Python), este ușor de scris o procedură de afișare, în orice fel (sau format) imaginabil, a datelor conținute în fișierele CSV respective. Și Nu există aberație mai mare, decât să impui oficial studiul "procesorului" comercial Microsoft-Word, în loc să adopți un editor de text și formatul simplu CSV!
Deocamdată ne ocupăm aici (folosind limbajul R și "dialectul" tidyverse) de orarul existent în fișierul "Lu.csv" pentru ziua Luni:
# fișierul "review.R" library(tidyverse) Z <- read_csv("Lu.csv")
Prin comanda print(head(Z)) vizualizăm primele câteva linii de date:
prof `1` `2` `3` `4` `5` `6` `7`
1 Andone Emanuel 10D 10D 9G 9G 10H 10H NA
2 Arghire Cristiana NA NA NA NA NA NA NA
3 Asandulesei-Budeanu Maria 10E 9C 10J 9E 10B 10C NA
4 Baciu Livia NA NA NA NA NA NA NA
5 Balasanu Ana Irina NA NA NA NA NA NA NA
6 Baltatescu Gheorghe 9A 10F NA NA NA NA NA
Pe unele linii, toate valorile din coloanele orare 1:7 sunt NA, însemnând că profesorii respectivi nu au de făcut lecții la clase, în ziua "Lu" (dar probabil că au, în alte zile).
Nu ne interesează numele profesorilor, ci mai degrabă disciplina principală pe care este încadrat fiecare — am înscrie drept "nume" un cod constituit dintr-o abreviere a disciplinei și un număr de ordine în lista celor încadrați pe disciplina respectivă. Putem stabili disciplinele, confruntând cu fișierul PDF al claselor; de exemplu, vedem că "Mate" este colorat cu o anumită nuanță de verde, deci toți profesorii "colorați" în celălalt fișier PDF cu nuanța respectivă, au ca disciplină "Mate".
Însă aici simplificăm lucrurile, evitând deocamdată munca necesară pentru a deduce disciplina principală a fiecăruia: înscriem drept "nume" (în coloana prof) numărul de ordine al liniei, prefixat cu "p":
Z$prof <- paste0("p", rownames(Z))
Prin secvența următoare constituim o matrice W, conținând numai liniile din Z corespunzătoare profesorilor care nu sunt liberi în ziua respectivă (și pe aceste linii înlocuim orele libere "NA", prin caracterul "-"):
free <- apply(Z[, 2:8], 1, function(L) all(is.na(L))) W <- Z[!free, ] %>% as.matrix() W[is.na(W)] <- "-" saveRDS(W, "Lu.RDS")
În final, am salvat pe disc (în fișierul "Lu.RDS") structura de date constituită în W.
Prin comanda print(W, quote=FALSE) putem vizualiza orarul zilei respective:
prof 1 2 3 4 5 6 7
[1,] p1 10D 10D 9G 9G 10H 10H -
[2,] p3 10E 9C 10J 9E 10B 10C -
[3,] p6 9A 10F - - - - -
[4,] p7 11B 11A 11A 9A - - -
[5,] p8 - 12E 11B 10C 10G - -
[6,] p9 9H 11C - - - - -
[7,] p10 - - - - - 9B -
[8,] p11 12B 10I 11G 12F - - -
[9,] p12 - 11F 10B 10J 11J 11J -
[10,] p15 11C 9D 9D 11C - - -
[11,] p17 10I 11G 9F 12C 12C 12C -
[12,] p19 12I 12I 12I 12I 12I - -
[13,] p20 11D 11I 11I 9B 9B - -
[14,] p21 - 12B 12B 12B 9A 12A -
[15,] p22 12C 10E 10E 12H 11G 10G -
[16,] p23 12A - 9B 10G 9F 10J -
[17,] p24 10H 10J 10D 10A 10J 10E -
[18,] p25 9E 11D 11D 11D 9H 9E -
[19,] p26 10J 10C 11C 11F 11F - -
[20,] p28 - - 11H 11I 12A 12I 11A
[21,] p29 - - 11K 12G 12G 9H -
[22,] p30 12F 11B 10F - 9G 10I -
[23,] p33 9C 10H 10I 12D - - -
[24,] p34 9G 9E - - - - -
[25,] p36 12H 12F 12C 9D 9E 11D -
[26,] p37 9F 10A 12H 11G 11C - -
[27,] p38 - - 9A 10B 11K 12B 11G
[28,] p39 11G 10B 10A 10I 11B 11C -
[29,] p40 11A 9I - 11H 12B 11G 11F
[30,] p41 - - - 9I 9I 9C -
[31,] p42 - - 12A 10D 10C 10A -
[32,] p43 11I 11E - 11A 11I 9A -
[33,] p44 10F 9A 9E 9F 9C 9D -
[34,] p46 11H 11H - 10F 10F 11A -
[35,] p48 11E 9H 10C 12A 10D 11F -
[36,] p49 12G - 12F - 11D 12E -
[37,] p50 9D 12H 11F 11B 11A 11B -
[38,] p51 10G 10G 12G - - - -
[39,] p54 - - - - - 11I 11H
[40,] p55 9I 9G 10G - - - -
[41,] p56 - - - - - 9G -
[42,] p57 10B - - - - - -
[43,] p58 9B 9B 12E 12E 12E 10F -
[44,] p60 11J 11J 11J 10H 10I 10B -
[45,] p61 - - - - - 9I -
[46,] p63 12E 11K - - - - -
[47,] p64 10A 12A 10H 11J 12D 11H -
[48,] p65 11K 12G 9C 9H 9D - -
[49,] p66 12D 12D 12D 10E 10E 9F -
[50,] p67 - - 11E 11E 11E 11E -
[51,] p69 10C 9F 9I 9C 10A - -
[52,] p70 11F 12C 9H 11K 12H 12G -
[53,] p71 - - - - 12F 10D -
[54,] p72 - - - - 11H 11K -
Putem constata imediat care sunt profesorii liberi în ziua Lu:
> setdiff(Z$prof, W[, 1]) # liberi în ziua Lu (18 din cei 72) [1] "p2" "p4" "p5" "p13" "p14" "p16" "p18" "p27" "p31" "p32" "p35" "p45" [13] "p47" "p52" "p53" "p59" "p62" "p68"
Din matricea W putem constitui setul LSS care conține toate lecțiile prof|ora|cls, facilitând investigarea datelor respective:
LSS <- readRDS("Lu.RDS") %>% as.data.frame(.) %>% pivot_longer(cols = 2:ncol(.), names_to = "ora", values_to = "cls") %>% filter(cls != "-")
Constatăm că în total avem 235 de lecții (în ziua Lu):
> glimpse(LSS) Rows: 235 Columns: 3 $ prof <chr> "p1", "p1", "p1", "p1", "p1", "p1", "p3", "p3", "p3", "p3", "p3",… $ ora <chr> "1", "2", "3", "4", "5", "6", "1", "2", "3", "4", "5", "6", "1", … $ cls <chr> "10D", "10D", "9G", "9G", "10H", "10H", "10E", "9C", "10J", "9E",…
Care sunt clasele și câte ore are (în ziua Lu) fiecare clasă:
> table(LSS$cls) 10A 10B 10C 10D 10E 10F 10G 10H 10I 10J 11A 11B 11C 11D 11E 11F 11G 11H 11I 11J 6 6 6 6 6 6 6 6 6 6 7 6 6 6 6 7 7 7 6 6 11K 12A 12B 12C 12D 12E 12F 12G 12H 12I 9A 9B 9C 9D 9E 9F 9G 9H 9I 6 6 6 6 5 6 5 6 5 6 6 6 6 6 6 6 6 6 6
Pe ultima coloană din matricea W apar numai 4 clase, anume tocmai cele arătate în tabelul de mai sus cu câte 7 ore/zi; deci toate clasele cu câte 6 ore/zi își încep programul de la prima oră a zilei. Dacă vreuna dintre cele trei clase cu câte 5 ore/zi ajunge în a 6-a oră, atunci clasa respectivă își începe programul nu de la prima oră, ci de la a doua oră a zilei:
> LSS %>% filter(ora == 6 & cls %in% c("12D", "12F", "12H")) # A tibble: 0 × 3 (niciuna dintre cele 3 clase nu ajunge în ora a 6-a)
Rezultatul afișat ne încredințează că nu s-a făcut vreo derogare de la regula după care fiecare clasă își începe programul de la prima oră a zilei.
Din aceste constatări rezultă și că fiecare clasă apare câte o singură dată în fiecare dintre orele 1:n, unde n este numărul de ore/zi la clasa respectivă (și implicit, nu avem cuplaje, când o aceeași clasă ar apărea într-o aceeași oră la doi profesori — aceștia lucrând în ora respectivă cu câte o grupă de elevi din clasa respectivă); dar nu-i rău să ne convingem direct de acest lucru:
> any(table(LSS[c('ora','cls')]) > 1) [1] FALSE # (orice clasă apare cel mult o singură dată în fiecare oră)
Dacă vrem, putem obține orarul uneia sau alteia dintre clase, de exemplu așa:
> LSS %>% filter(cls == "9A") %>% arrange(ora) %>% pull(prof) [1] "p6" "p44" "p38" "p7" "p21" "p43"
Revenind la matricea W redată mai sus, observăm că există 5 profesori care au câte o fereastră și unul ("p49") care are două ferestre; totalul de 7 ferestre/zi este chiar rezonabil, însemnând numai 3% din totalul de 235 de ore. Totuși, bănuim că putem reformula orarul respectiv, încât să avem chiar mai puțin de 7 ferestre…
Pentru a încerca să reducem numărul de ferestre putem folosi pachetul nostru refitgaps (existent pe CRAN), după ce mai întâi, eliminăm coloana prof din matricea W și adoptăm numele respective drept nume de linie (rezultând o "matrice-orar"):
W <- readRDS("Lu.RDS") rownames(W) <- W[, 1] W <- W[, 2:8] # matricea-orar inițială library(refitgaps) R <- recast(W) # caută un orar cu mai puține ferestre
Funcția recast() produce o listă conținând o matrice-orar cu aceleași lecții ca în orarul inițial, dar realocate pe orele 1:7 astfel încât numărul total de ferestre este de regulă mai mic decât cel inițial; al doilea element al listei este numărul actual de ferestre:
> print(R[[2]]) [1] 4 # orarul rezultat are 4 ferestre (inițial erau 7) > print.table(R[[1]]) # noul orar 1 2 3 4 5 6 7 p1 10D 10D 9G 9G 10H 10H - p3 10E 9C 10B 10C 9E 10J - p6 10F 9A - - - - - p7 - - - 11B 11A 9A 11A p8 10C 11B 12E 10G - - - p9 9H 11C - - - - - p10 - - - - - 9B - p11 11G 10I 12B 12F - - - p12 - - 10J 10B 11J 11J 11F p15 - - 11C 11C 9D 9D - p17 9F 11G 10I 12C 12C 12C - p19 12I 12I - 12I 12I 12I - p20 11I 11I 9B 9B 11D - - p21 12A 12B 9A 12B 12B - - p22 12H 10E 12C 10E 10G 11G - p23 - 9B 12A 9F 10J 10G - p24 10A 10J 10H 10J 10D 10E - p25 11D 11D 11D 9E 9H 9E - p26 10J 10C - 11F 11F 11C - p28 11H 11A 12I - 11I 12A - p29 12G 12G 9H 11K - - - p30 12F 10F 11B 10I 9G - - p33 10I 10H 12D 9C - - - p34 9E 9G - - - - - p36 12C 12F 9E 9D 12H 11D - p37 11C 10A 9F 12H 11G - - p38 - - 11K 9A 10B 12B 11G p39 11B 10B 11G 10A 11C 10I - p40 12B 11F 11H 11G 9I 11A - p41 - - - 9I 9C 9I - p42 - - 10D 12A 10A 10C - p43 11A 11E 11I 11I 9A - - p44 9A 9E 9D 10F 9F 9C - p46 - 11H 11A 11H 10F 10F - p48 11E 9H 10C 10D 12A 11F - p49 - - 12F 11D 12E 12G - p50 9D 12H 11F 11A 11B 11B - p51 10G 10G 12G - - - - p54 - - - - - 11I 11H p55 9G 9I 10G - - - - p56 - - - - - 9G - p57 10B - - - - - - p58 9B 12E 10F 12E 9B 12E - p60 11J 11J 11J 10H 10I 10B - p61 9I - - - - - - p63 12E 11K - - - - - p64 10H 12A 10A 11J 12D 11H - p65 11K 9D 9C 9H 12G - - p66 12D 12D 10E 12D 10E 9F - p67 - - 11E 11E 11E 11E - p69 9C 9F 9I - 10C 10A - p70 11F 12C 12H 12G 11K 9H - p71 - - - - 12F 10D - p72 - - - - 11H 11K -
În noul orar — rezultat cam în două secunde — avem numai 4 ferestre, câte una la patru profesori, în ora a 3-a sau a 4-a. Iar repetând comanda R <- recast(W), obținem de fiecare dată un alt orar, tot cu 4 ferestre (sau poate și mai puține), dar cu altă distribuție pe profesori a acestora (și în general, cu orare individuale care diferă mai mult sau mai puțin, prin ordinea lecțiilor, de cele inițiale).
Este drept că aici am avut de-a face cu un caz foarte simplu, cu multe clase (39) într-adevăr, dar fără cuplaje (și fără tuplaje) — de aceea reducerea ferestrelor a durat așa de puțin. Rămâne de văzut eventual, cum stau lucrurile pe celelalte zile…
vezi Cărţile mele (de programare)