momente şi schiţe de informatică şi matematică
To attain knowledge, write. To attain wisdom, rewrite.

De la încadrarea profesorilor la orarul şcolii, folosind R

limbajul R | orar şcolar
2021 mar

O încadrare cu clase partajate

Următorul tabel reprezintă încadrarea profesorilor dintr-o anumită şcoală (reală sau nu), în ordinea descrescătoare a numărului de ore pe săptămână:

      10_________ 11_________ 12_________         9__________
prof  A B C D E F A B C D E F A B C D E F 5 6 7 8 A B C D E F
  P01 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  P02 5 3 . . . . 7 . . . . 1 3 1 . . . . 1 . . . 7 . . . . .
  P03 3 6 . 1 . . 3 . . 2 . . 7 . 2 . . . . 1 . . 3 . . . . .
  P04 . . 1 3 . . . . . 2 2 1 . 1 . 5 5 3 . . . . . . . 2 . 2
  P05 . . 3 . 2 3 . 2 . . . . 2 2 . . 5 . . 2 . . 2 2 . 2 . .
  P06 . . 2 . 1 1 . 2 2 . 2 . . . . 1 1 1 . . 1 1 . 3 3 2 2 2
  P07 . 4 . . . . . . . . . . 4 . . . 2 . . . 6 . . 4 4 . . 2
  P08 . . 4 . . . 5 4 . . . . . 5 . . . . . . . 4 4 . . . . .
  P09 . 2 . . . . . . . 2 9 . . . . . . 4 2 . . 2 . . . . . 4
  P10 1 1 1 1 1 1 . . . 1 1 1 . . . 1 1 2 1 1 1 1 1 1 1 1 1 2
  P11 . . . 2 2 . . 3 . . . . . . 3 . . . . . . 2 . 3 4 2 . 2
  P12 . 2 . 2 . . . 2 2 2 . . 2 . . 5 . . . . . . 2 . . 4 . .
  P13 2 . 2 . . 3 . . . . 2 3 . . . . . . 2 . 2 . . 2 2 . 2 .
  P14 2 . 3 . . . 1 4 3 . . . 1 . . . . . . . 2 2 2 . . 1 . 1
  P15 . . . . 6 . 2 . . . 1 . . 2 2 . 2 3 . 2 . 2 . . . . . .
  P16 . . . 2 3 2 . . . 2 2 . . . 4 2 . . . . . . . . . 2 2 .
  P17 2 2 . . 1 . . 3 3 . . 1 1 . . . . 1 . . . . . 4 3 . . .
  P18 . . 3 . . . . . . . . . 4 . . . 4 . . . . 5 . . . . 5 .
  P19 2 . . . . . . . 1 2 1 2 2 . . . . 1 . . 2 2 1 1 1 . 1 1
  P20 3 . . . . . . 4 . 5 . . . . . 4 . . . . . . . 4 . . . .
  P21 . 3 . . . . . . 4 . 4 . . . 4 . . . . . . . . . . 5 . .
  P22 . . . 4 . . . . . 4 . . 1 . . . 5 3 . . . . . . . . 2 .
  P23 . 2 2 1 1 1 1 1 . . . . . 1 1 1 1 . 3 2 . . . . . 1 . .
  P24 . . . . . . . . . . 4 . . . . 4 . . 2 2 . . 1 1 1 2 . 2
  P25 . . . 4 . . . . . . . 6 . 4 . . . 5 . . . . . . . . . .
  P26 . . 2 1 . 1 1 . . . . . . 4 3 . . . . 2 . 1 2 . . 1 1 .
  P27 1 1 1 . 3 4 1 1 1 . . 3 . 1 1 . . . . . . . . . . . . .
  P28 1 1 1 2 . . 1 . . . . . 1 1 . 2 . . 1 . . 3 1 . . 2 . .
  P29 . 2 . 1 1 1 . . . . . . . 3 4 . . . . . . . . 2 2 . 1 .
  P30 . 3 3 . . 2 . . 4 . . . . 3 . . . . . . . . . . . . 2 .
  P31 1 1 1 1 1 1 . . . . . . . . . . . . 1 1 1 1 1 1 1 1 1 1
  P32 2 . . . . . . . . . . . . . . . 6 . . . . . . . . . 6 .
  P33 . . . 3 . . . . 2 . . 3 . . 2 2 . . . . . . . . 2 . . .
  P34 . . . . . . . . . . . . . . . . . . . 5 . . . . 4 . . 4
  P35 . . . . 4 4 4 . . . . . . . . . . . . . . . . . . . . .
  P36 3 . . . . . 3 . . . . . 3 . . . . . . . . . 3 . . . . .
  P37 . . . . . 2 . . . . 2 2 . . . . . . . . . . . . . . 2 2
  P38 . . . 1 1 1 . . . . . 2 . . . . . 1 . . 1 . . . . 1 1 1
  P39 . . . . . . 2 . . . . . . . . . . . . . 2 . . . . . 5 .
  P40 . . . . 2 . . . 1 . . . . . 1 . 2 . . . . . . 1 . . . 2
  P41 . . . . . . . . 4 . . . . . . . . . 5 . . . . . . . . .
  P42 1 1 1 1 1 1 1 1 . . . . . . . . . . . . . . . . . . . .
  P43 . . . . . . . . . . . . . . . . . . . . 4 . 4 . . . . .
  P44 4 . . . . . . . . . . . . . . . . . . 4 . . . . . . . .
  P45 1 1 . . . . . . . . . . . . . . . . . . . . 1 1 1 . 2 .
  P46 . . . . . . . . 1 2 2 1 . . . . . . . . . 1 . . . . . .
  P47 . . . . . . . 1 . 3 . . . . . . . 2 . . . . . . 1 . . .
  P48 . . . . 6 . . . . . . . . . . . . . . . . . . . . . . .
  P49 . . . . . . . . . . 5 . . . . . . . . . . . . . . . . .
  P50 . . . . . . . . . . . . . . . . . . 1 . 2 . . . . . . 1
  P51 . . . . . . . . . . . . . . . . . . . 2 2 . . . . . . .
  P52 . . . . 2 2 . . . . . . . . . . . . . . . . . . . . . .
  P53 . . . . . . . . . . . . . . . . . . 4 . . . . . . . . .
  P54 . . . . . . . . . 1 . 1 . . . 1 . 1 . . . . . . . . . .
  P55 . . . . . . . . . . . . . . . . . . . . 1 2 . . . . . .
  P56 . . . . . . . . . . . . . . . . . . 1 1 1 . . . . . . .
  P57 . . . . . . . . . . . . . . . . . . 1 . 1 1 . . . . . .
  P58 . . . . . . . . . . . . . . . . . . . 1 1 . . . . . . .
  P59 . . . . . . . . . . . 1 . . . . . 1 . . . . . . . . . .
  P60 . . . . . . . . . . . . 1 . 1 . . . . . . . . . . . . .
  P61 . . . . . . . . . . . . . . . . . . . 1 . . . . . . . .
      A B C D E F A B C D E F A B C D E F 5 6 7 8 A B C D E F
      10          11          12                  9          

Întrebare: este vorba de o şcoală reală? Păi într-o încadrare inventată de noi, n-am fi considerat profesori cu o singură oră pe săptămână (ba chiar, nici cu numai două sau trei ore); în realitate, "P61" are 36 ore/an (şi numai orarul vede "1 ore/săpt.").
Este vorba de o şcoală reală, cu câte 6 clase pe nivelele 9..12 şi cu 4 clase gimnaziale 5..8; nu-i cazul să punem întrebări fără sens: care şcoală anume, de unde? sau, care este numele (şi CNP-ul) lui "P07"?

Întrebare: Ce disciplină predă P01? Păi "P01" are câte o oră la fiecare clasă (şi una în plus la 10A) – deci predă "Religie" (singurul obiect impus politic la toate clasele). Disciplinele nu sunt precizate, dar ele sunt totuşi importante pentru a reda complet orarul şcolar.

Întrebare: cum de "P09" are 9 ore, la clasa 11E? Întrebarea are sens: există numai trei profesori cu mai mult de 6 ore la o aceeaşi clasă (şi numai 7 cazuri cu 6 ore). "P02" şi "P03" au 7 sau 3 ore la aceleaşi clase (şi 5/3 sau 3/6 la 10A şi 10B); de obicei (într-o şcoală reală) clasele "A" sunt „de informatică”, iar parte dintre orele de "Info" se desfăşoară partajând clasa între doi profesori; la fel stau lucrurile pentru alte câteva discipline (de obicei, limbi străine, sau "Des/Muz") şi probabil, cele 9 ore la 11E sunt partajate cumva între "P09" şi alţi profesori.

Pe tabelul de încadrare de mai sus (extras din orarul public al unei anumite şcoli) sunt înregistrate toate orele profesorilor, indiferent de faptul că unele dintre acestea sunt ore comune mai multor profesori (de obicei, doi profesori care partajează o clasă într-o aceeaşi oră a zilei); „orarul claselor” (publicat separat de „orarul profesorilor”) ne-a furnizat informaţiile privitoare la partajarea claselor.

Reluăm din [1], repartizarea pe zile şi pe orele zilei a orelor din încadrare – îmbunătăţind într-o anumită măsură programele respective şi ţinând seama acum şi de situaţiile în care doi profesori trebuie să intre simultan la o aceeaşi clasă.

Introducerea cuplurilor prin „profesori fictivi”

Extindem tabelul de încadrare de mai sus cu o listă de profesori fictivi, reprezentând fiecare câte un cuplu de profesori care partajează anumite clase:

prF <- list(F1 = c("P02", "P03"), F2 = c("P31", "P10"), F3 = c("P32", "P39"),
            F4 = c("P32", "P05"), F5 = c("P09", "P13"), F6 = c("P09", "P15"))

"P02" şi "P03" partajează pe câte 3 ore, fiecare dintre clasele 10A, 10B, 11A, 12A şi 9A; scădem câte 3 ore fiecăruia, la clasele respective, punându-le în schimb la "F1":

      10_________ 11_________ 12_________         9__________
prof  A B C D E F A B C D E F A B C D E F 5 6 7 8 A B C D E F
  P02 2 0 . . . . 4 . . . . 1 0 1 . . . . 1 . . . 4 . . . . .
  P03 0 3 . 1 . . 0 . . 2 . . 4 . 2 . . . . 1 . . 0 . . . . .
  F1  3 3 . . . . 3 . . . . . 3 . . . . . . . . . 3 . . . . .

La alocarea pe zile, va trebui să avem grijă ca în fiecare zi, suma dintre numărul de ore „fictive” (alocate lui "F1") şi numărul de ore alocate lui "P02", respectiv lui "P03", să fie în ambele cazuri cel mult 7. La alocarea pe orele zilei, va trebui să avem grijă ca orele din zi alocate lui "F1" să nu se suprapună nici cu orele lui "P02", nici cu orele lui "P03" (încât aceştia să poată intra împreună în acea zi, la clasele respective).

La fel avem de revizuit tabelul de încadrare, pentru integrarea celorlalţi profesori fictivi din lista prF. Pentru unele partaje existente în contextul real din care am extras datele de mai sus, n-a fost necesar să înfiinţăm vreun profesor fictiv; de exemplu, "P15" şi "P48" sunt cuplaţi pe clasa 10E, cu câte 6 ore – dar "P48" apare în tabelul de încadrare de mai sus numai cu această clasă, încât devine suficient să eliminăm pur şi simplu "P48" (şi numai la afişarea orarului final, să ţinem seama cumva de faptul că orele lui "P15" la 10E trebuie notate fiecare şi cu "P48").

După ce am modificat astfel tabelul de încadrare, am înlocuit pe toate rândurile " " cu "," (şi '0' cu '.') – obţinând încadrarea în format CSV, "incadrare.csv".

Normalizarea datelor de încadrare

Pentru a folosi algoritmii de etichetare (cu zile, respectiv cu ore-ale-zilei) din [1], trebuie să aducem încadrarea la „forma normală” (specificând orele din încadrare prin linii 'prof' | 'clasă', repetate consecutiv de câte ore are 'prof' la 'clasă'):

fram <- read_csv("incadrare.csv", na = '.') %>%   # sum(!is.na(fram[, 2:29]))  ## 409
        gather("cls", "nore", 2:29) %>%
        filter(! is.na(nore)) %>%  # 409 linii 'prof' | 'cls' | 'nore'
        mutate(nore = as.integer(nore)) %>%  # sum(fram$nore)  ## 839
        uncount(nore)  # 'prof' | 'cls' (cu linii identice de câte 'nore' ori)
> str(fram)  # inspectează structura datelor, din consolă
tibble [839 × 2] (S3: tbl_df/tbl/data.frame)
 $ prof: chr [1:839] "P01" "P01" "P02" "P02" ...
 $ cls : chr [1:839] "10A" "10A" "10A" "10A" ...

Transformăm coloana $prof în factor, ordonat descrescător după numărul de ore pe săptămână corespunzător profesorului:

srt <- sort(table(fram$prof), decreasing=TRUE)
fram$prof <- factor(fram$prof, levels = names(srt), ordered=TRUE)
> str(fram)
tibble [839 × 2] (S3: tbl_df/tbl/data.frame)
 $ prof: Ord.factor w/ 65 levels "P01"<"P04"<"P06"<..: 1 1 31 31 28 28 28 10 10 13 ...
 $ cls : chr [1:839] "10A" "10A" "10A" "10A" ...

Cu table() putem vedea 'fram' din nou ca „tabel de încadrare” (în forma iniţială, având coloane pentru fiecare clasă) şi prin apply() putem aplica sum() pe liniile tabelului, obţinând numărul total de ore pentru fiecare profesor:

> apply(table(fram[c('prof','cls')]), 1, sum)
P01 P04 P06 P07 P08 P11 P12 P05 P09 P14 P15 P16 P17 P18 P13 P19 P20 P21 P22 P23 
 29  27  27  26  26  23  23  22  22  22  21  21  21  21  20  20  20  20  19  19 
P24 P25 P26 P27 P28 P29 P30  F1 P10 P33 P02 P03 P34 P35 P36 P37 P38  F2 P40 P41 
 19  19  19  18  17  17  17  15  15  14  13  13  13  12  12  10  10   9   9   9 
P42 P43 P44 P31 P45 P46 P47  F4  F3 P32 P39 P50 P51 P52 P53 P54 P55 P56 P57  F5 
  8   8   8   7   7   7   7   6   5   4   4   4   4   4   4   4   3   3   3   2 
P58 P59 P60  F6 P61 
  2   2   2   1   1 

Din rezultatul redat deducem că primii 37 profesori (dinaintea lui "F2") au fiecare cel puţin 10 ore pe săptămână; când vom repartiza pe zilele de lucru cele 839 de ore din încadrare, vom cere ca orele acestora să fie distribuite cât mai uniform (v. [2]).

Am zice că această încadrare este mai densă decât cea vizată în [1], media orară fiind 839/65≈13 ore de profesor, pe 28 de clase – faţă de [1], unde aveam 1202/76≈16 ore de profesor pe 41 de clase (iar 13/28 > 16/41); vom vedea mai încolo că densitatea încadrării este importantă (programul de repartizare pe orele zilei din [1] trebuie corectat, pentru a nu eşua dacă încadrarea este prea densă).

Deocamdată, folosind saveRDS(), salvăm datele respective în fişierul frame.RDS.

Repartizarea pe zile a încadrării

Reluăm cu anumite îmbunătăţiri şi corecturi, programul "distribute.R" din [2].

Anterior, în funcţia CND() se opera pe toate coloanele matricelor de alocare (curentă şi respectiv, cumulată) – acum operăm numai pe acele coloane care corespund profesorilor clasei curente (prevăzând în prealabil lista prOf – care indică profesorii fiecărei clase în parte – şi desemnând coloanele lui Zore prin levels(FRM$prof)).

În [2] adăugam coloana $zl (în cadrul funcţiei alloc_by_class()) ca factor ordonat, folosind gl(); dar este suficient să folosim rep_len(1:5, nrow(.)) (etichetând zilele prin 1..5 şi repetând secvenţa pe toate orele clasei curente) şi abia în final, să convertim $zl în factor cu nivelele Zile ("Lu", "Ma", etc.).

Bineînţeles că prin aceasta, viteza de execuţie sporeşte sensibil. Dar am evitat să mai complic în CND(), condiţiile impuse distribuţiilor individuale; este mult mai simplu de rezolvat interactiv (ulterior obţinerii rezultatului programului) diversele situaţii particulare (de exemplu, cazul când lui "F1" i s-au alocat 4 ore, în timp ce "P02" are deja 4 ore – însemnând că în ziua respectivă "P02" ar avea 8 ore, în loc de maximum 7).

# distribute_by_days.R  (distribuie pe zile, orele din încadrarea profesorilor)
library(tidyverse)

FRM <- readRDS("frame.RDS")  # 839 linii <prof> <cls> (fiecare oră din săptămână)
nrPr <- nlevels(FRM$prof)  # 65 profesori; primii 37 au măcar 10 ore pe săptămână
FRM <- FRM %>%
       split(.$cls)  # listă de „tabele”, câte unul de clasă

prOf <- map(FRM, function(K) {  # lista profesorilor fiecărei clase
    lpr <- unique(K$prof)
    lpr[lpr < "F2"]  # restrânge lista la cei cu măcar 10 ore/săpt.
})

# alocă orele pe zile, pentru fiecare clasă
alloc_by_class <- function() {
    # matricea de control a numărului de ore pe zi cumulat, la profesori 
    Zore <- matrix(data=rep(0L, 5*nrPr), nrow = 5, ncol = nrPr, byrow=TRUE,
                   dimnames = list(1:5, levels(FRM$prof)))
                        
    # Condiţiile impuse unei distribuţii pe zile a orelor
    CND <- function(More, lpr) {  # 'lpr' = lista profesorilor clasei
        mex <- Zore[, lpr] + More[, lpr]  # cumulează alocările, curentă şi anterioară
        for(j in 1:ncol(mex)) {
            Pr <- mex[, j]  # câte ore ar avea, în fiecare zi, profesorul
            for(oz in Pr) 
                if(any(abs(Pr - oz) > 2)) 
                    return(FALSE)  # refuză alocarea, dacă nu este "pseudo-omogenă"
        }
        return(TRUE)  # acceptă alocarea: nr. ore/zi variază cu max. 2 
    }  

    # montează coloana zilelor alocate orelor unei clase 
    labelsToClass <- function(Q) {  # 'Q' conţine liniile din FRM cu o aceeaşi 'cls'
        lpr <- prOf[[Q$cls[1]]]  # profesorii clasei (cu măcar 10 ore/săpt.)
        S <- Q %>% 
             mutate(zl = rep_len(1:5, nrow(.))) 
        # verifică dacă orele pe zi alocate curent respectă CND()
        more <- t(as.matrix(table(S[c('prof', 'zl')])))
        if(CND(more, lpr)) {
            Zore <<- Zore + more  # actualizează numărul de ore pe zi
            return(S)  # o distribuţie care îndeplineşte condiţiile
        }
        # dacă nu-s îndeplinite CND(), permută profesorii clasei şi reia
        Q <- Q %>% arrange(match(prof, sample(unique(prof))), prof)
        return(labelsToClass(Q))  # Reia dacă nu-s îndeplinite condiţiile
    }       # (programul va fi stopat dacă reapelarea nu mai este posibilă)

    tryCatch(  # previne stoparea programului (v. [1])
        { FRM %>%  # etichetează liniile fiecăreia dintre clase
              map_df(., function(K) labelsToClass(K))
        }, 
        error = function(err) {  # s-a depăşit capacitatea stivei de apeluri
                    FRM <- FRM %>% 
                           sample(.)  # permută grupurile de linii ale claselor
                    tryCatch({
                               cat("1")  ## vizualizează cumva, reluările 
                               alloc_by_class()  # reia, în noua ordine de clase
                             }, 
                             error = function(e) NULL
                    )
                }
    )  # Returnează distribuţia pe zile a orelor claselor indicate (sau NULL)
}  # încheie 'alloc_by_class()'

Dis <- alloc_by_class()
Zile <- c("Lu", "Ma", "Mi", "Jo", "Vi")
Dis <- Dis %>% mutate(zl = factor(zl, labels=Zile))
saveRDS(Dis, file = "byDays1.rds")  # 'byDays2.rds', 'byDays91.rds', etc.
# afişează distribuţiile individuale pentru orele profesorilor
print(addmargins(as.matrix(table(Dis[c('prof', 'zl')]))))  # dacă 'Dis' ≠ NULL

Numai în două din vreo zece execuţii, am obţinut ca rezultat NULL: funcţia alloc_by_class() n-a reuşit – autoapelându-se (în limitele stivei de apeluri) cu o ordine schimbată aleatoriu a claselor şi a profesorilor clasei – să ajungă la o distribuire a orelor care să respecte CND(); altfel, distribuţia este produsă într-un timp mediu de 2 minute (pentru cazul de aici, cu 65 de profesori şi 28 de clase, totalizând 839 de ore).

Toate rezultatele Dis (din diversele execuţii ale programului de mai sus) au aceeaşi distribuţie (neuniformă) a numărului total de ore pe zi (descrescând în ordinea zilelor, după cum am justificat în [2]):

> unlist(lapply(Zile, function(z) nrow(Dis[Dis$zl == z, ])))
[1] 175 172 168 166 158  # Total: 839 ore

Urmează să revizuim interactiv una dintre distribuţiile pe zile rezultate, pentru a uniformiza numărul total de ore pe zi (ideal ar fi să avem o zi cu 167 de ore şi 4 zile cu câte 168 ore), pentru a remedia eventualele cazuri în care profesorii care partajează clase cumulează mai mult de 6-7 ore pe zi şi pentru a mai îndrepta alocarea orelor la profesorii cu puţine ore (evitând situaţia „o oră pe zi”).

Demersuri necesare finalizării distribuţiei pe zile

Prin următorul program modelăm una dintre distribuţiile pe zile obţinute mai sus, în formatul CSV cerut de aplicaţia /recast; deasemenea, extragem într-un fişier separat liniile corespunzătoare orelor cuplate prin „profesorii fictivi”, precum şi matricea care indică pentru fiecare clasă numărul de ore pe fiecare zi:

# disToRecast.R
rm(list=ls())
library(tidyverse)
D <- readRDS("byDays91.rds")  # distribuţia pe zile (prof|cls|zl) a celor 839 de ore

# listă de 5 obiecte 'tibble' (prof|cls), câte unul pentru fiecare zi
lDz <- D %>% split(.$zl) %>%
             map(., function(z) z[, 1:2] %>% 
             arrange(prof))

# modelează tabelul necesar aplicaţiei /Recast (scriindu-l apoi în format CSV)
Drc <- data.frame(prof="", Lu="", Ma="", Mi="", Jo="", Vi="")
row = 1
for(P in levels(D$prof)) {  # prof  Lu  Ma Mi Jo     Vi
    Drc[row, 1] <- P         # P31 |6 7|9E|  |5 8 9D|9F
    for(q in 2:6) {
        ql <- lDz[[q-1]] %>% 
              filter(prof == P)
        Drc[row, q] <- paste(c(ql$cls), collapse=" ") 
    }
    row <- row + 1
}
write_csv(Drc, file="Dis91.csv")  # Copy&Paste în aplicaţia interactivă /Recast

# alocarea pe zile a orelor cuplate prin profesorii "fictivi"
prF <- list(F1 = c("P02", "P03"), F2 = c("P31", "P10"), F3 = c("P32", "P39"),
            F4 = c("P32", "P05"), F5 = c("P09", "P13"), F6 = c("P09", "P15"))
tgt <- paste0("F", 1:6)  # cheile din lista 'prF'     
together <- map_df(tgt, function(key) 
                            Drc %>% 
                            filter(prof %in% c(key, prF[[key]])) %>% 
                            arrange(prof))
sink("together.txt")
    print(together, row.names=FALSE, width=150)
    print(addmargins(table(D[c('cls', 'zl')])))  # ore/zi pentru fiecare clasă
sink()

Conţinutul fişierului "Dis91.csv" poate fi pastat ca atare în caseta iniţială a aplicaţiei /recast (sau, mai bine, direct în elementul <textarea> al fişierului-sursă "recast.html"); datele din fişierul "together.txt" ne servesc pentru a decide ce clase să mutăm (prin operaţia SWAP a aplicaţiei) dintr-o zi în alta, încât să echilibrăm zilele în privinţa numărului total de ore pe zi şi să corectăm eventualele neajunsuri privind alocarea pe zile a orelor cuplate.

De exemplu, pentru orele cuplate prin "F1" avem această situaţie:

 prof        Lu                 Ma             Mi             Jo              Vi
   F1   10A 10B     10A 10B 12A 9A     11A 12A 9A     11A 12A 9A     10A 10B 11A
  P02    11A 9A           11A 5 9A     10A 11A 9A    10A 11F 12B          11A 9A
  P03   12A 12C    10B 11D 12A 12C        10B 11D        10B 12A       10D 12A 6

În ziua Lu, profesorii "P02" şi "P03" au câte 4 ore, dintre care două împreună (la clasele 10A şi 10B, alocate fictiv lui "F1"); însă Ma, "P02" are 7 ore, iar "P03" are chiar 8 ore – ceea ce trebuie corectat: de exemplu, ar fi suficient să mutăm la "F1" clasa 12A din ziua Ma în ziua Lu şi la "P03", clasa 12C din ziua Ma în ziua Mi (astfel, "P02" şi "P03" nu vor avea zile cu mai mult de 6 ore, comune sau nu).

Finalizarea interactivă a distribuţiei pe zile

Mai întâi uniformizăm numărul total de ore pe zi, urmărind totodată ca profesorii cuplaţi să aibă cel mult 6 ore pe zi; operaţia Mark din /recast evidenţiază liniile profesorilor care au ore la clasa indicată şi este uşor să vedem la cine ar fi cel mai bine să mutăm (prin SWAP) clasa respectivă dintr-o zi în alta (şi eventual invers, din ziua-destinaţie înapoi în ziua-sursă). Mutând unele clase din zilele Lu şi Ma (în care aveau câte 7 ore) în ziua Vi, am ajuns uşor la o distribuţie uniformă (168 168 168 167 168), pentru numărul total de ore pe zi (iar profesorii cuplaţi au fiecare, cel mult 6 ore pe zi).

Încheind repede această primă etapă, am salvat rezultatul – folosind operaţia "Export" – amânând pentru mai târziu, diverse alte modificări; dar am constatat că în fişierul CSV furnizat, clasele nu sunt indicate corect – de exemplu avem:

P34,69F,69C,69C 9F,69C 9F,69C 9F  # corect: P34,6 9F,6 9C,6 9C 9F,6 9C 9F,6 9C 9F

Citind handler-ul de click pentru link-ul Export (redat şi în [2](III)), se poate deduce uşor de ce clasele 5..8 (notate cu câte o cifră) nu sunt redate corect: prin qls = $(el).text() extrăgeam textul conţinut de elementul <td> curent, obţinând de exemplu qls = "10A10B12B69A", sau pentru linia exemplificată mai sus qls = "69F"; apoi separam clasele din şirul qls folosind qls = qls.match(/\d*[A-Z]/g) – ceea ce ar fi corect dacă fiecare clasă este notată (ca de obicei) prin "cifre + literă".

De corectat, n-ar fi o problemă: de exemplu, putem folosi (cam grosolan) .match(/9[A-Z]|10[A-Z]|11[A-Z]|12[A-Z]|5|6|7|8/g), identificând separat fiecare clasă, fie că este notată obişnuit, fie că este notată 5..8 (fără literă). Numai că, modificând acum codul javaScript şi reîncărcând apoi în browser fişierul "recast.html" – am reveni la distribuţia iniţială, pierzând modificările făcute deja asupra acesteia…

A fost un bun prilej de a observa că în Firefox nu mai avem (ca acum câţiva ani) un meniu "View Generated source", dar şi o ocazie de a înţelege că acesta nici nu este necesar: utilizăm instrumentul "Inspector" (accesibil de exemplu prin combinaţia de taste Ctrl+Shift+C), selectăm <div>-ul care conţine tabelul HTML redat la momentul respectiv în fereastra browser-ului şi din meniul deschis prin click-dreapta alegem "Copy / InnerHTML" – obţinând fragmentul HTML corespunzător tabelului respectiv. L-am pastat apoi într-o copie „curată” a fişierului "recast.html" (fără elementul <textarea> şi fără activarea widget-ului .recast()) şi am imitat operaţia "Export", adăugând un element <a> împreună cu un <script> conţinând handler-ul de click corespunzător (modificând acum, expresia din .match(), cum am arătat mai sus).

Am reuşit astfel să obţin fişierul CSV corect, reflectând modificările întreprinse asupra distribuţiei iniţiale; bineînţeles că l-am pastat în elementul <textarea> din fişierul recast.html, încât la următoarea lansare a aplicaţiei vom putea continua modificările, în loc să o luăm de la capăt.

De notat şi „lecţia” primită: este bine să notăm clasele în modul obişnuit, sau în orice caz într-un acelaşi stil (deci "5A" şi nu "5")…

Ilustrăm genul de modificări care ar mai fi de făcut, pentru a îmbunătăţi unele distribuţii individuale. La clasa 10F avem câteva cazuri de „o oră pe zi”:

"P52" are numai 4 ore pe săptămână şi le-ar face în 4 zile (câte una pe zi); de dorit ar fi să le facă în 2 zile, iar o posibilitate de redistribuire constă în următoarea secvenţă de operaţii SWAP:

P52:  10F (Vi)  -->  Ma    Ma: 10E 10F
P37:  10F (Ma)  -->  Vi    Ma: 11E 9F    Vi: 9E 10F
P52:  10F (Lu)  -->  Mi    Mi: 10E 10F
P30:  10F (Mi)  -->  Lu    Lu: 10B 10C 11C 10F    Mi: 11C 12B 9E

Astfel, distribuţia iniţială pentru "P52" (1 1 1 0 1) a devenit (0 2 2 0 0); cea iniţială pentru "P37" (2 3 2 2 1) a devenit omogenă, (2 2 2 2 2); iar cea pentru "P30" nu şi-a pierdut caracterul de omogenitate (2 zile cu câte 4 ore şi 3 zile cu câte 3 ore).

Desigur, am ţinut seama de faptul că 10F intră într-un cuplaj (fiindcă apare la "F2"), dar acest cuplaj nu angajează niciunul dintre cei 3 profesori implicaţi în operaţiile SWAP redate mai sus.

După ce am făcut o serie de asemenea modificări (dar numai dintre cele mai evidente), am salvat distribuţia obţinută în fişierul divRecast.csv; urmează să generăm orarele fiecărei zile. Subliniem că nu ne-am ocupat mai mult de vreo 20-30 de minute, să redistribuim orele pe zile prin /recast; probabil că ocupându-ne mai mult, am putea obţine o distribuţie pe zile chiar „perfectă” – numai că experienţa cumulată anterior în [1] şi [2] sugerează că tocmai în acest caz, reducerea numărului de ferestre pe orarele zilnice devine dificilă.

Probabil că planul de lucru cel mai bun este acesta: facem prin aplicaţia /recast numai modificările „evidente”, precum cele ilustrate mai sus; apoi producem orarele zilnice şi deducem eventual ce modificări în repartiţia pe zile divRecast.csv ar mai fi de făcut, încât să putem reduce cât mai mult numărul ferestrelor apărute pe orare; dacă este cazul, putem relua /recast, modificând divRecast.csv (acum, în cunoştinţă de cauză) şi apoi, generând din nou orarele, pentru noua distribuţie pe zile a orelor.

Renormalizarea datelor (din distribuţia CSV pe zile)

Redăm fişierul divRecast.csv (separând însă unele linii prea lungi):

prof,Lu,Ma,Mi,Jo,Vi
P01,10A 10B 11D 12B 6 9A,10A 10E 11C 12E 9E 9F,11B 11F 12F 8 9B 9C,
    10C 11A 12A 12C 7,10D 10F 11E 12D 5 9D
P04,10D 12D 12E 12F 9D 9F,10D 12B 12D 12E 12F 9D,10D 12D 12E 12F,
    11D 11E 11F 12D 12E,10C 11D 11E 12D 12E 9F
P06,11B 7 9B 9C 9D 9F,10C 10F 12D 9C 9D,10C 11C 12F 9C,11C 11E 12E 8 9B 9E,
    10E 11B 11E 9B 9E 9F
P07,10B 12A 12E 7,12A 7 9B 9C 9F,10B 7 7 9B 9C 9F,10B 12A 7 9B 9C,
    10B 12A 12E 7 9B 9C
P08,11A 11B 12B 8 9A,10C 11A 11B 12B 8 9A,10C 11A 11B 12B 9A,
    10C 11A 11B 12B 8,10C 11A 12B 8 9A
P11,11B 12C 9C 9F,11B 12C 8 9B 9C,11B 12C 9B 9C 9D,10D 10E 9B 9D,10D 10E 9C 9F 8
P12,10D 11B 12D 9D,10B 10D 11D 12D,10B 11C 12A 12D 9D,11C 12A 12D 9A 9D,
    11B 12D 9A 9D 11D
P05,10C 12A 12B 9B,10C 12A 6 9A,10C 10E 10F 6 9A,10E 10F 11B 9D,10F 11B 12B 9B 9D
P09,10B 11E 12F 5 9F,10B 11E 11E 12F 9F,11D 11E 12F 9F,11D 11E 8 9F,11E 12F 5 8
P14,10C 11B 11C 7 8,10C 11B 7 8,10A 10C 11B 12A 9D,10A 11A 11C 9A 9F,11B 11C 9A
P15,10E 10E 11A 12E 8,10E 12E 12F 12C,10E 12B 12F,10E 12B 12C 12F 6,10E 11A 6 8
P16,10E 12C 12D 9E 10F,10E 11E 12C 12D,11D 11E 12C 9D,10D 10F 11D 9D,10D 10E 12C 9E
P17,10A 11C 12F 9B,11B 11C 11F 9B 9C,11B 12A 9C,10B 10E 11B 9B 9C,10A 10B 11C 9B
P18,12E 8 9E,10C 12A 12E 8 9E,10C 12A 8 9E,10C 12A 8 9E 12E,12A 12E 8 9E
P13,11F 7 9B 9C,10A 11F 9B 9E,10F 11F 5 9E,10C 10F 5,10C 10F 7 9C 10A
P19,11D 11E 9A 9E,10A 11C 12F 8 12A,10A 7 8 9F,11F 7 9B 9C,11D 11F 12A
P20,10A 11B 11D 12D 9B,11B 11D 9B,11B 11D 12D 9B,10A 11B 11D 12D,10A 11D 12D 9B
P21,10B 11C 11E 12C 9D,10B 11E 12C 9D,10B 11E 12C 9D,11C 11E 9D,11C 12C 9D 11C
P22,12A 12E 12F,10D 11D 12E 9E,10D 11D 12E 9E,10D 11D 12E 12F,10D 11D 12E 12F
P23,10E 10F 12D 6,11A 11B 12B 5,10D 12E 5,10B 10C 12C 5,10B 10C 6 9D
P24,11E 5 9C 9D,12D 5 9D,11E 12D 6 9A,11E 12D 6 9F,11E 12D 9B 9F
P25,10D 11F 11F 12B 12F,10D 11F 12F,10D 11F 12B 12F,10D 11F 12B 12F,11F 12B 12F
P26,10C 12B 6 8,10C 12B 12C 6,12B 12C 9D,10D 12C 9A,10F 11A 12B 9A 9E
P27,10B 10C 11A 11F,10A 10E 10F 11F,10E 10F 11C 12B,10E 10F 11B,10F 11F 12C
P28,10D 11A 8 9D,10D 9A 9D,10A 10C 12D,12B 12D 5 8,12A 8 10B
P29,10D 10F 12B 9C,12B 12C 9C,10B 10E 12C 9B,10B 12C 9B 9E,12B 12C
P30,10B 10C 11C 10F,10B 10F 12B,11C 12B 9E,10C 11C 12B,10B 10C 11C 9E
F1,10A 10B 12A,10A 10B 9A,11A 12A 9A,11A 12A 9A,10A 10B 11A
P10,5 9E,11D 11F 9D,12E 6 8,12D 12F 7 9F,11E 12F 9F
P33,10D 11C 11F,10D 11C 12D,10D 12D,11F 12C 9C,11F 12C 9C
P02,11A 9A,11A 5 9A,10A 11A 9A,10A 11F 12B,11A 9A
P03,12A 12C,10B 11D 12A,10B 11D 12C,10B 12A,10D 12A 6
P34,6 9F,6 9C,6 9C 9F,6 9C 9F,6 9C 9F
P35,10F,10E 10F 11A,10E 10F 11A,10E 10F 11A,10E 11A
P36,10A 11A 12A 9A,11A 12A,11A 12A,10A 9A,10A 9A
P37,10F 9F,11E 9F,11E 11F,11F 9E,9E 10F
P38,10E 12F,11F 9F,11F 9E,10D 10F,7 9D
F2,10C 10E 9B,10F 9A,10A,9C,10B 10D
P40,10E 12C,10E 9B,11C 9F,12E 9F,12E
P41,11C 5,11C 5,5,11C 5,11C 5
P42,,,10B 10D 10F,11A 10A,10C 10E 11B
P43,,7 9A,7 9A,7 9A,7 9A
P44,10A,6,10A 6,10A 6,10A 6
P31,6,7 9E,5 9F,8 9D,
P45,9A 9C,10A,9B 9E,10B 9E,
P46,11D 11E,11D 11E,11C 11F 8,,
P47,,,11D,11B 11D 12F,11D 12F 9C
F4,12E 9E,12E,12E,12E,12E
F3,9E,9E,9E,9E,9E
P32,,10A,12E,9E,10A
P39,,11A,11A 7,,7
P50,5 7,7 9F,,,
P51,7 6,,,,7 6
P52,,10E 10F,10E 10F,,
P53,5,5,,5,5
P54,11D 11F 12D,12F,,,
P55,,7 8,8,,
P56,,,5 7 6,,
P57,,,,,5 7 8
F5,,,11E,11E,
P58,,,,7 6,
P59,,,,12F,11F
P60,,,,,12A 12C
F6,11E,,,,
P61,,6,,,

Următorul program (provenit din [2]-IV, unde l-am conturat „pas cu pas” – încât acum ne scutim de „explicaţii”) transformă disRecast.csv într-un obiect tibble (salvat în disPeZile.RDS) cu structura prof|cls|zl, $prof şi $zl fiind de tip "factor" (profesorii fiind ordonaţi descrescător după numărul de ore pe săptămână):

# csv2df.R  ## v. [2]-IV ("renormal.R")
library(tidyverse)
Dcsv <- read_csv("disRecast.csv")  # distribuţia pe zile iniţială, format CSV

splt <- function(Txt)  unlist(strsplit(Txt, " "))

renormalize <- function(D) {
    D %>% gather("zl", "cls", 2:6, na.rm=TRUE) %>%
          mutate(ncl = unlist(lapply(.$cls, 
                                     function(q) length(splt(q))))) %>%
          uncount(.$ncl) %>% 
          split(., .$cls) %>%
          map_df(., function(G) {
                    q <- splt(G$cls[1])
                    G$cls <- rep(q, nrow(G) %/% length(q))
                    as.data.frame(G)
          })
}

Din <- renormalize(Dcsv) %>% select(-4)  # elimină coloana $ncl
Zile <- c("Lu", "Ma", "Mi", "Jo", "Vi")
srt <- sort(table(Din$prof), decreasing=TRUE)
Dzl <- as_tibble(Din) %>% 
       mutate(prof = factor(prof, levels=names(srt), ordered=TRUE), 
              zl = factor(zl, levels=Zile, ordered=TRUE)) %>%
       relocate(cls, .after=prof) %>%
       arrange(prof)
saveRDS(Dzl, "disPeZile.RDS")  # tibble, 839 x 3, $prof (ord.) | $cls | $zl (ord.)

Urmează să alocăm pe orele 1..7 ale zilei de lucru, orele profesorilor repartizate prin disPeZile.RDS într-o aceeaşi zi.

Noua filozofie a distribuţiei orare a lecţiilor unei zile

Preferăm să schimbăm notaţia claselor 5..8, pentru a nu confunda cumva cu orele zilei; le renotăm adăugând sufixul "G" (vine de la „Gimnaziu”):

Dis <- readRDS("disPeZile.RDS")
for(k in 5:8) 
    Dis[Dis$cls == as.character(k), ]$cls <- paste0(as.character(k),"G")
saveRDS(Dis, file="disPeZile.RDS")

Reamintim ideea introdusă în [1] pentru repartizarea pe orele 1..7 ale zilei, a orelor profesorilor dintr-o aceeaşi zi, corectând totodată o anumită hibă.
Orele profesorilor” sunt cupluri (profesor, clasă) şi vom mai zice lecţii, pentru a evita confuzia cu „orele 1..7 ale zilei”.

Mai întâi, separăm pe clase lecţiile repartizate în ziua respectivă; fiecărei clase îi corespund câte λ = 4..7 linii de lecţii, λ fiind numărul de ore din acea zi ale clasei. Tratăm pe rând clasele, într-o anumită ordine, eventual aleatorie.

Etichetăm liniile clasei curente cu una dintre permutările mulţimii {1, 2, ..., λ} (vom prelua din [1]-(I) fişierul "lstPerm47.RDS", care conţine lista celor 4 matrice de λ-permutări necesare); dacă ora alocată astfel unuia dintre profesorii de pe liniile respective coincide cu ora alocată lui la o clasă tratată anterior, atunci reetichetăm liniile clasei cu o altă λ-permutare (şi verificăm din nou, dacă există suprapuneri).

Avansând astfel, clasă după clasă – se poate întâmpla totuşi (undeva spre final) ca reetichetarea clasei curente să eşueze: pentru toate λ-permutările posibile încercate, există suprapuneri cu ore alocate anterior, profesorilor clasei respective. Această hibă nu s-a manifestat pentru încadrările din [1] şi [2], dar pentru încadrarea de faţă – care este mai densă – orarul final obţinut aplicând direct programul anterior, omite câte o clasă în unele zile (deci liniile acelei clase n-au putut fi etichetate fără suprapuneri).

Corectăm acum, această hibă (dar într-o manieră „nedeterministă”, cam cum am procedat şi la repartizarea pe zile a orelor): dacă pentru clasa curentă se epuizează toate λ-permutările (negăsind niciuna care să evite suprapuneri cu alocări făcute anterior), atunci abandonăm complet tratarea în curs a claselor, ordonăm aleatoriu grupurile de linii aferente claselor şi o luăm de la capăt, tratând clasele în noua ordine a acestora – repetând „abandonarea” şi „reluarea” până ce se reuşeşte tratarea tuturor claselor (practic, factorialul numărului de clase este foarte mare, încât cam trebuie să nimerim la un moment dat, o ordine a claselor care să permită „tratarea” tuturora).

Existenţa cuplajelor creşte binişor complexitatea acestei tratări, trebuind făcute verificări de suprapunere suplimentare (iar riscul epuizării λ-permutărilor creşte); în plus, formularea corectă a acestor verificări este complicată. Să zicem de exemplu, că la clasa curentă apare "F1"; va trebui verificat nu numai că ora alocată lui nu se suprapune cu una alocată lui anterior, dar şi că nu se suprapune cu o oră alocată anterior profesorilor cuplaţi de "F1" – iar pentru fiecare dintre aceştia va trebui verificat, oricând ar apărea între profesorii unei clase, că ora alocată nu se suprapune cu o oră alocată deja lui "F1" (şi la fel, pentru ceilalţi profesori fictivi).

Deocamdată preferăm să nu complicăm programul şi generăm orarul zilei ca şi când toţi profesorii ar fi independenţi între ei; în fond, pe o zi avem numai câteva cuplaje şi va fi uşor să rezolvăm interactiv eventualele suprapuneri apărute pe orarul generat pentru ziua respectivă.

Să ne amintim că undeva mai sus am constituit fişierul "together.txt", înregistrând cuplajele existente în încadrarea profesorilor; după ce am generat distribuţia pe zile a orelor din încadrare, ne-am ghidat după acest fişier pentru a muta interactiv anumite clase dintr-o zi în alta, astfel încât să eliminăm situaţiile în care vreunul dintre profesorii cuplaţi pe acele clase ar avea mai mult de 6 ore pe zi.
Dar ne-a scăpat din vedere, să şi actualizăm fişierul respectiv, în urma mutărilor de clase pe care le-am făcut; să reconstituim acum, cuplajele existente pe fiecare zi, folosind nu forma normalizată disPeZile.RDS a distribuţiei pe zile, ci mult mai simplu – folosind direct fişierul CSV din care a provenit aceasta:

# cuplaje.R  # alocarea pe zile a orelor cuplate prin profesorii "fictivi"
library(tidyverse)
Dcsv <- read_csv("disRecast.csv")  # din care produsesem "disPeZile.RDS"
Zile <- c("Lu", "Ma", "Mi", "Jo", "Vi")
prFi <- list(F1 = c("P02", "P03"), F2 = c("P31", "P10"), F3 = c("P32", "P39"),
             F4 = c("P32", "P05"), F5 = c("P09", "P13"), F6 = c("P09", "P15"))
tags <- paste0("F", 1:6)  # cheile din lista 'prFi' 
for(day in Zile)
    for(key in tags) {
        D <- Dcsv %>% filter(prof %in% c(key, prFi[[key]])) %>% 
             select(prof, day)
        # vizează numai profesorii fictivi din acea zi
        if(!is.na(D[D$prof == key, 2])) {
            D %>% rbind(., c(paste("---", day, "---"), "")) %>%
                  write_csv(., file = "together.csv", append = TRUE)
        }
    }

După ce obţinem orarul pentru ziua de "Lu" de exemplu, vom urmări conţinutul fişierului together.csv pentru a opera prin SWAP (în aplicaţia /dayRecast) mutările cuvenite de ore, cam cum ilustrăm aici:

F1,10A 10B 12A  # de plasat în „ferestre comune” ale profesorilor "P02" şi "P03"
P02,11A 9A
P03,12A 12C
--- Lu ---,
P10,5 9E
F2,10C 10E 9B  # de plasat în „ferestre comune” ale profesorilor "P10" şi "P31"
P31,6  # De exemplu: P10 - orele 1 şi 2; P31 - ora 2; P10+P31 - orele 3, 4, 5
--- Lu ---,
F3,9E  # aparent, se poate plasa oricând, fiindcă "P32" şi "P39" sunt liberi
P32,NA  # nu are ore proprii, în ziua respectivă
P39,NA
--- Lu ---,
P05,10C 12A 12B 9B
F4,12E 9E
P32,NA  # Atenţie: are deja o oră! (cu "P39", mai sus)
--- Lu ---,
P09,10B 11E 12F 5 9F
P15,10E 10E 11A 12E 8
F6,11E  # de plasat în unica fereastră comună a profesorilor "P15" şi "P09"
--- Lu ---,

Să recunoaştem totuşi că vom avea şi cazuri mai complicate – de exemplu, "P32" este cuplat şi prin "F3" şi prin "F4" – dar oricum, ni se pare clar că va fi mai uşor de pus la punct situaţiile de cuplaj operând interactiv cum am sugerat mai sus, decât imaginând vreo secvenţă de program care să aibă în vedere toate situaţiile.

Programul de distribuţie orară a lecţiilor unei zile

Nu ne mai gândim ca în [1], să obţineam „deodată” toate cele 5 orare zilnice; este preferabil să lucrăm pe fiecare zi în parte, repetând programul pentru ziua respectivă dacă orarul tocmai furnizat pentru ea nu este suficient de convenabil.

În directorul de lucru curent s-au adunat deja multe fişiere (".R", ".RDS", ".csv"); dar mai departe, avem (neapărat) nevoie numai de lista matricelor de λ-permutări (din fişierul lstPerm47.RDS) şi de cele 5 distribuţii ale orelor corespunzătoare fiecărei zile (extrase din "disPeZile.RDS"). Se cuvine să înfiinţăm un subdirector /byDays/, care să conţină aceste fişiere şi în care să generăm apoi, cele 5 orare zilnice.

Prin următorul program (lansat din directorul părinte al lui /byDays/) extragem din distribuţia pe zile a tuturor orelor încadrării, distribuţiile corespunzătoare fiecărei zile în parte, obţinând fişierele byDays/dis_{zi}.RDS (unde "{zi}" este "Lu", "Ma", etc.); în plus, constituim în Bits.RDS un „vector cu nume”, care ne va servi pentru a controla în privinţa suprapunerilor (v. [1]), alocarea pe orele zilei a lecţiilor clasei curent tratate:

library(tidyverse)
Dzl <- readRDS("disPeZile.RDS")  # distribuţia pe zile a orelor, prof|cls|zl
Zile <- c("Lu", "Ma", "Mi", "Jo", "Vi")
# orele repartizate zilei, ordonate după profesori şi separate după clasă
disOfDay <- function(zi) {
    Dzl %>% 
    filter(zl == zi) %>% 
    select(prof, cls) %>%
    arrange(prof) %>%  # arrange(desc(prof))
    split(.$cls) %>%
    saveRDS(., file = paste0("byDays/dis_", zi, ".RDS"))
} 
lapply(Zile, disOfDay)

Bits <- rep(0L, nlevels(Dzl$prof))  # urma alocărilor de ore (v. [1]), iniţial 0
names(Bits) <- levels(Dzl$prof)
saveRDS(Bits, file="Bits.RDS")

Deocamdată avem:

vb@Home:~/21mar/ORARE$ ls byDays
Bits.RDS dis_Jo.RDS  dis_Lu.RDS  dis_Ma.RDS  dis_Mi.RDS  dis_Vi.RDS  lstPerm47.RDS

Vom obţine orarul uneia sau alteia dintre zile, după această schemă:

lu <- readRDS("dis_Lu.RDS")  # lecţiile prof|cls repartizate în ziua 'Lu'
hLu <- mountHtoDay(lu)  # prof|cls|ora  (alocă fiecare lecţie pe orele 1..7)

mountHtoDay() fiind funcţia pe care am introdus-o în [1] şi pe care o reluăm acum, corectând hiba pe care am evidenţiat-o undeva mai sus; am preferat să introducem lista de λ-permutări precum şi tabloul octeţilor de alocare Bits în afara contextului funcţiei (era posibil şi în interior, dar atunci readRDS() ar fi fost invocată de mai multe ori şi în plus, dacă vrem să folosim ulterior şi valorile rămase în Bits atunci ele ar trebui salvate, cu saveRDS(), înainte de a încheia execuţia – altfel se pierd):

# set_hours_day.R (setează orele 1..7 lecţiilor repartizate într-o aceeaşi zi)
library(tidyverse)
Pore <- readRDS("lstPerm47.RDS")  # lista matricelor de permutări (de 4..7 ore)
Bits <- readRDS("Bits.RDS")  # alocările orelor prof., pe câte un octet (iniţial 0)

## alocă profesorii pe orele zilei, pentru fiecare clasă
mountHtoDay <- function(Z) {  # 'tibble' <ord>prof|cls, split()-at pe clase
    # iniţializează octeţii de alocare, copiind tabloul global 'Bits'
    bith <- Bits  # <- readRDS("Bits.RDS")

    # alocă pe orele 1..7, orele (lecţiile) unei clase                    
    mountHtoCls <- function(Q) {  # 'Q' conţine liniile din Z cu o aceeaşi 'cls'
        if(succ == FALSE) return(NULL)
        # cat(Q$cls[1], " ")  ## dacă vrem să vedem clasele tratate pe parcurs
        mpr <- Pore[[nrow(Q)-3]]  # matricea de permutări corespunzătoare clasei
        for(i in 1:ncol(mpr)) { 
            po <- mpr[, i]
            S <- Q  %>%  mutate(ora = po)  # etichetează cu permutarea curentă
            # vectorul octeţilor de ore asociaţi acestei permutări:
            bis <- bitwShiftL(1, S$ora - 1)  
            # vectorul octeţilor de ore alocate deja profesorilor clasei:
            bhp <- bith[S$prof]

            # Dacă există suprapuneri (de ore) între cei doi vectori, 
            # atunci angajează coloana următoare a matricei de permutări,
            # dacă mai există una (altfel, abandonează)
            if(i == ncol(mpr) & any(bitwAnd(bhp, bis) > 0)) {
                succ <<- FALSE
                break
            }
            if(any(bitwAnd(bhp, bis) > 0)) next
            
            # se presupune că la o aceeaşi clasă, avem cel mult 2 ore de profesor
            j <- anyDuplicated(names(bhp))
            if(j > 0) {  # dacă în Z, profesorul are 2 ore la acea clasă
                bis[j-1] <- bis[j] <- bis[j-1] + bis[j]
            }

            # actualizează global, octeţii de alocare:
            bith[S$prof] <<- bitwOr(bhp, bis)
            return(S)
        }
    } 
    succ <- TRUE    
    # aplică montHtoDay() pentru fiecare clasă, în ordinea iniţială a claselor
    orar <- Z  %>%  map_df(., function(K) mountHtoCls(K)) 
    while(succ == FALSE) { # print("insucc")  ## nu se poate trece de clasa curentă
        succ <- TRUE
        bith <- Bits  # <- readRDS("Bits.RDS"); reiniţializează octeţii de alocare
        orar <- Z  %>% 
                sample(.) %>%  # ordonează aleatoriu lista tabelelor claselor
                map_df(., function(K) mountHtoCls(K))  # reia alocarea orelor
    }
    Bits <<- bith  # salvează octeţii de alocare rezultaţi în final
    return(orar)  # orarul zilei, prof|cls|ora
}

Iată o mostră de tratare, activând afişarea pe parcurs a unor informaţii:

> rm(list=ls())  # elimină din memorie obiectele create în sesiunea curentă
> source("set_hours_day.R")
> lu <- readRDS("dis_Lu.RDS")  # lecţiile prof|cls din ziua 'Lu'
> orLu <- mountHtoDay(lu)  # orarul zilei 'Lu'
10A  10B  10C  10D  10E  10F  11A  11B  11C  11D  11E  11F  12A 
12B  12C  12D  12E  12F  5G  6G  7G  8G  9A  9B  9C  9D  [1] "insucc"

12A  9F  11A  9E  12C  10C  12E  12F  10B  11F  9B  5G  9C  7G  10A  12B  11E 
10E  11D  10F  9A  10D  9D  8G  11B  [1] "insucc"
#... ... ...
7G  12B  11F  10B  8G  12C  11B  12A  11D  12E  12F  9F  9B  10C  9D  11A  12D 
11C  5G  10D  9E  11E  10E  9C  6G  9A  10A  10F  > 

Mai întâi, clasele au fost tratate în ordinea iniţială (alfabetică) – dar nu s-a putut trece de clasa 9D (epuizând toate cele 720 de permutări posibile pentru cele 6 ore din acea zi ale clasei 9D). Apoi, seturile de linii corespunzătoare claselor au fost reordonate (aleatoriu), dar nici în noua ordine a claselor (12A, 9F, 11A, etc.) nu s-a reuşit tratarea tuturora (clasa 11B are 5 ore în acea zi şi pentru oricare 5-permutare încercată, există suprapuneri cu ore alocate unor clase tratate anterior).

După un număr de asemenea insuccese (poate în vreo două minute, poate mai mult), se nimereşte totuşi una dintre ordonările de clase (mai sus, 7G, 12B, 11F, etc.) care asigură tratarea tuturora, obţinând un orar pentru ziua respectivă; repetând programul, într-o altă sesiune de lucru, va rezulta câte un alt orar al zilei respective, diferit de cel anterior obţinut (în măsura în care este adevărat că există numeroase reordonări ale claselor care să asigure tratarea tuturora).

Putem vedea orarul unei clase (şi analog, al unui profesor) de exemplu astfel:

> orr <- orLu %>% arrange(ora) %>% split(.$cls)  # sau, %>% split(.$prof)
> orr$`9A`  # respectiv, orr$`P02`
# A tibble: 6 x 3
  prof  cls     ora
  <ord> <chr> <int>
  P19   9A        1
  P02   9A        2
  P36   9A        3
  P45   9A        4
  P08   9A        5
  P01   9A        6

Eventual, pentru prelucrări ulterioare, vom păstra orarul obţinut, într-un fişier:

> saveRDS(orLu, file="orar_Lu.RDS")

În final, putem investiga şi tabelul Bits:

> Bits  # octeţii cu alocarea pe ore 1..7 a profesorilor
P01 P04 P06 P07 P08 P11 P12 P05 P09 P14 P15 P16 P17 P18 P13 P19 P20 P21 P22 P23 
 63  63  63  15  47  15  23  15  31  31  31  31  15  14  27  15  47  61  26  39 
#  etc. 

şi nu doar pentru a număra ferestrele profesorilor (v. [1]), dar şi pentru a vedea în ce măsură sunt posibile cuplajele prin profesorii fictivi (care nu au fost avute în vedere de program – rămânând de rezolvat interactiv); de exemplu, avem:

> Bits[c("F1", "P02", "P03")]
 F1 P02 P03 
 70  18  40  # 70=1000110  18=0010010  40=0101000 biţii pentru ora7, ora6, ..., ora1

şi urmărind biţii octeţilor respectivi, constatăm o singură nepotrivire: "P02" şi "P03" nu pot intra împreună în ora a 2-a indicată de "F1" (prin bitul de rang 1, de valoare 1), fiindcă "P02" este ocupat deja în acea oră. Desigur, o singură nepotrivire va fi uşor de corectat interactiv…
Cuplajul este posibil dacă bitwAnd(Bits["F1"], Bits["P02"]) şi bitwAnd(Bits["F1"], Bits["P03"]) au valoarea zero; cu toate că este relativ simplă, o asemenea condiţionare este delicat de integrat în programul de mai sus – trebuind aplicată numai claselor la care apare măcar unul dintre cei trei profesori (şi am constatat că e greu totuşi, de formulat un test eficient „apare profesorul la clasa curentă?”, mai având în vedere şi toate cuplajele, prin toţi profesorii fictivi consideraţi).

Finalizarea interactivă a orarului zilei

Orarul orar_Lu.RDS obţinut mai sus (sau orarul vreunei alte zile, obţinut analog) conţine multe ferestre şi (cum am evidenţiat deja) unele suprapuneri de ore la profesori cuplaţi prin cei fictivi; aplicaţia /dayRecast (HTML + jQuery) permite corectarea interactivă a acestor neajunsuri, tabelând profesorii şi clasele alocate pe orele 1..7 ale zilei şi prevăzând operaţia SWAP, prin care se pot schimba alocările iniţiale.

Dar avem de transformat „formatul” prof|cls|ora specific pentru orar_Lu.RDS, într-un fişier CSV cu structura "prof, ora1, ora2, ..., ora7" (care să fie apoi „pastat” în elementul <textarea> al aplicaţiei). Dar… vrem ceva mai mult: să reordonăm liniile încât cele corespunzătoare profesorilor cuplaţi să fie grupate la începutul tabelului (pentru a ne uşura intervenţia interactivă prin operaţiile SWAP):

# rds2csv.R
library(tidyverse)
file <- "orar_"
# Zile <- c("Lu", "Ma", "Mi", "Jo", "Vi")
format_csv <- function(zi) {
    readRDS(paste0(file, zi, ".RDS")) %>%
    arrange(prof) %>%
    split(.$prof) %>%
    map_df(., function(Q) spread(Q, ora, cls))
} # orz <- format_csv("Lu")

# lista tuturor cuplajelor prin profesorii fictivi
prFi <- list(F1 = c("P02", "P03"), F2 = c("P31", "P10"), F3 = c("P32", "P39"),
            F4 = c("P32", "P05"), F5 = c("P09", "P13"), F6 = c("P09", "P15"))

rds2csv <- function(zi) {
    orz <- format_csv(zi)
  # vectorul profesorilor cuplaţi în această 'zi'
    cplv <- unlist(lapply(paste0("F", 1:6), 
                         function(k) {if(any(orz$prof == k))
                                          c(k, prFi[[k]])
                                     }))
  # vectorul tuturor profesorilor din acea 'zi', începând cu cei cuplaţi
    ord_pr <- c(cplv, setdiff(orz$prof, cplv))  # ?? cplv <- unique(cplv) [*]
  # indecşii liniilor din 'orz', în ordinea dată de 'ord_pr'
    row_ids <- unlist(lapply(ord_pr, function(pr, D) { 
                                         which(D$prof == pr) 
                                     }, D = orz))
    orz <- orz[row_ids, ]  # pe primele linii avem acum cuplurile din acea zi
    write_csv(orz, file=paste0(file, zi, ".csv"), na = "-", col_names=TRUE)
}

De exemplu, prin rds2csv("Lu") obţinem "orar_Lu.csv", având pe primele linii:

prof,1,2,3,4,5,6,7
F1,-,10A,12A,-,-,-,10B
P02,-,9A,-,-,11A,-,-
P03,-,-,-,12C,-,12A,-
F2,-,10E,-,10C,-,9B,-
P31,-,-,-,-,6G,-,-
P10,-,9E,5G,-,-,-,-
F3,-,-,-,-,-,9E,-
F4,-,-,-,-,9E,12E,-
P05,9B,10C,12B,-,12A,-,-
F6,-,-,-,-,-,11E,-
P09,11E,5G,10B,9F,12F,-,-
P15,8G,11A,12E,10E,10E,-,-
P01,10B,6G,10A,11D,12B,9A,-
P04,10D,12E,12D,12F,9D,9F,-
... ... ...

Reordonând astfel liniile, vedem uşor de exemplu, că "P02" şi "P03" nu pot intra împreună la clasa 10A (pe care sunt cuplaţi prin F1); sau, că în acest moment "P09" şi "P15" îşi pot face şi orele proprii şi ora la 11E (pe care sunt cuplaţi prin F6).
Mai observăm că F5 nu apare în ziua respectivă; linia lui F3 nu este succedată de cele două linii care ar corespunde profesorilor pe care îi cuplează, ceea ce înseamnă că aceştia nu au ore proprii în această zi – deci 9E se poate muta dacă este cazul (pentru a reduce ferestre la alţi profesori) în oricare oră 1..7 de pe linia lui F3.

Procedând cam cum am arătat în [1] (III), am reuşit după un anumit număr de operaţii SWAP să corelez între ei profesorii cuplaţi şi să reduc cele 42 de ferestre existente iniţial (cum arată "Gaps" în imaginea redată mai sus) la numai 8, toate de câte o singură oră (nu-i cazul să ne lăudăm: pe orarul original de pe care am extras încadrarea, pentru orele de "Lu" – altele însă, decât cele care ne-au rezultat aici – existau numai 7 ferestre):

> rc8 <- read_csv("Recast8.csv")  # din aplicaţia /dayRecast/, prin "Export"
> print(rc8, n=Inf)
   prof  `1`   `2`   `3`   `4`   `5`   `6`   `7`  
 1 F1    10A   12A   10B   -     -     -     -     # P02 + P03
 2 P02   -     -     -     9A    11A   -     -    
 3 P03   -     -     -     12C   12A   -     -    
 4 F2    -     -     -     10C   9B    10E   -     # P31 + P10
 5 P31   -     -     6G    -     -     -     -    
 6 P10   -     5G    9E    -     -     -     -    
 7 F3    -     -     -     9E    -     -     -     # P32 + P39 (P32 este dublu cuplat)
 8 F4    -     -     -     -     9E    12E   -     # P32 + P05
 9 P05   12B   10C   9B    12A   -     -     -    
10 F6    -     -     -     -     -     11E   -     # P09 + P15
11 P09   10B   11E   9F    5G    12F   -     -    
12 P15   11A   8G    10E   10E   12E   -     -     # 10E: P15 + P48 (fără fereastră)
13 P01   11D   6G    10A   -     12B   9A    10B  
14 P04   9F    12E   9D    12F   12D   10D   -    
15 P06   11B   9D    9C    9B    9F    7G    -    
16 P07   -     -     7G    12E   10B   12A   -    
17 P08   9A    12B   11A   11B   8G    -     -    
18 P11   9C    12C   11B   9F    -     -     -    
19 P12   -     -     10D   12D   9D    11B   -    
20 P14   7G    11B   -     11C   10C   8G    -    
21 P16   10F   12D   12C   -     10E   9E    -    
22 P17   11C   9B    12F   10A   -     -     -    
23 P18   8G    9E    12E   -     -     -     -    
24 P13   9B    9C    11F   7G    -     -     -    
25 P19   9E    9A    11E   11D   -     -     -    
26 P20   12D   10A   11D   -     11B   9B    -    
27 P21   9D    11C   -     11E   12C   10B   -    
28 P22   12E   12F   12A   -     -     -     -    
29 P23   10E   10F   12D   6G    -     -     -    
30 P24   -     -     5G    9C    11E   9D    -    
31 P25   12F   11F   -     12B   10D   11F   -    
32 P26   -     -     12B   8G    6G    10C   -    
33 P27   -     -     10C   10B   11F   11A   -    
34 P28   10D   11A   8G    9D    -     -     -    
35 P29   -     -     10F   10D   9C    12B   -    
36 P30   10C   10B   -     10F   11C   -     -    
37 P33   11F   10D   11C   -     -     -     -    
38 P34   6G    9F    -     -     -     -     -    
39 P35   -     -     -     -     -     10F   -    
40 P36   12A   -     9A    11A   10A   -     -    
41 P37   -     -     -     -     10F   9F    -    
42 P38   -     -     -     -     -     12F   10E  
43 P40   12C   10E   -     -     -     -     -    
44 P41   -     -     -     -     5G    11C   -    
45 P44   -     -     -     -     -     10A   -    
46 P45   -     -     -     -     9A    9C    -    
47 P46   11E   11D   -     -     -     -     -    
48 P50   5G    7G    -     -     -     -     -    
49 P51   -     -     -     -     7G    6G    -    
50 P53   -     -     -     -     -     5G    -    
51 P54   -     -     -     11F   11D   12D   -    

Dar… asta ne interesează aici, „să finalizăm orarul” pe o zi sau alta?

Finalizarea programelor…

Adăugăm în programul "set_hours_day.R" o funcţie utilitară ("helper") care să ne furnizeze (apelând mountHtoDay()) fişierul "orar_{zi}.RDS" pentru ziua indicată:

# în set_hours_day.R
orarofday <- function(zi) {
    tb <- readRDS(paste0("dis_", zi, ".RDS"))
    orZ <- mountHtoDay(tb)
    saveRDS(orZ, file=paste0("orar_", zi, ".RDS"))
}

Se întâmplă că "orar_Ma.RDS" este produs aproape imediat (cu tratarea claselor în ordinea lor iniţială, fără să mai apară "insucc"):

> source("set_hours_day.R")
> orMa <- orarofday("Ma")
10A  10B  10C  10D  10E  10F  11A  11B  11C  11D  11E  11F  12A  12B  12C  12D 
12E  12F  5G  6G  7G  8G  9A  9B  9C  9D  9E  9F  > 

Prin rds2csv("Ma") am obţinut "orar_Ma.csv", pe care l-am pasat aplicaţiei /dayRecast – dar acţionând "Load", în loc de tabelul HTML cuvenit, am obţinut un mesaj de atenţionare: "Suprapuneri: P32 / P32: 10A, ora 7"…
Aceasta înseamnă că P32 apare de două ori, în tabelul HTML – ceea ce nu trebuia să se întâmple; şi într-adevăr, în "orar_Ma.csv" găsim:

F3,-,-,-,-,-,9E,-  # cuplează P32 şi P39
P32,-,-,-,-,-,-,10A
P39,-,-,-,-,11A,-,-
F4,-,-,12E,-,-,-,-   # cuplează P32 şi P05
P32,-,-,-,-,-,-,10A  # ?? se produce a doua oară, linia lui P32
P05,6G,12A,10C,9A,-,-,-

Fiindcă "P32" este cuplat şi prin F3 şi prin F4, linia sa a fost inclusă de două ori.
Prin urmare, avem de corectat funcţia rds2csv() (în locul marcat cu [*]), aplicând unique() vectorului profesorilor cuplaţi:

## corectură, în funcţia rds2csv() ##
  # vectorul profesorilor din acea 'zi', începând cu cei cuplaţi
    cplv <- unique(cplv)  # evită dublarea liniei, când profesorul este dublu cuplat
    ord_pr <- c(cplv, setdiff(orz$prof, cplv))

Vedem deci, încă o dată, că „munca interactivă” este totuşi importantă pentru punerea la punct a programelor…

După corectura menţionată, operând în /dayRecast obţinem eventual această rezolvare a situaţiilor de cuplaj:

P02 şi P03 fac individual primele 3 ore şi apoi intră împreună următoarele 3 ore, la clasele indicate de F1. O situaţie analogă avem pentru P31 şi P10.
Interesant (şi complicat de tratat) este cazul lui P32, care cuplează şi cu F3 şi cu F4: întâi, P32 intră împreună cu P05 la clasa 12E (pe care este cuplat prin F4), apoi continuă singur cu clasa 12E, apoi intră împreună cu P39 (cu care este cuplat prin F3) la clasa 9E.

De observat că P05 şi P13 au câte o fereastră aparentă – în care P05 intră împreună cu P32 la clasa 12E, iar P13 intră împreună cu P09 la clasa 11E (pe care sunt cuplaţi prin F5); altfel, în situaţia redată pe imaginea de mai sus – pe cele 14 linii corespunzătoare profesorilor cuplaţi nu avem nicio fereastră reală.
Deci numărul curent de ferestre, afişat la "Gaps", ar trebui cumva corectat (este 20, nu 22); dar bineînţeles că nu vom complica aplicaţia, pentru atâta lucru (vrem doar să evidenţiem că mereu vom găsi câte ceva de „finalizat”).

Am reuşit până la urmă să reducem numărul de ferestre (reale) la 6 – dar trebuie să recunoaştem că n-a fost deloc uşor, trebuind să verificăm mereu dacă prin SWAP-ul curent nu deteriorăm cuplajele (fără nicio fereastră) arătate mai sus (apropo: iarăşi nu-i cazul să ne lăudăm – pe orarul original în ziua "Ma" există numai 5 ferestre reale; dar subliniem că pe orarul original orele sunt altfel distribuite pe zile, faţă de cazul nostru).
Pentru a uşura această muncă ar fi de adăugat în aplicaţia /dayRecast o funcţie care să verifice dacă prin operaţia SWAP curentă se produce vreo modificare de structură pe primele linii ale tabelului HTML (cele corespunzătoare cuplajelor, în cazul de aici – primele 14 linii); desigur, apare un aspect delicat: funcţia respectivă trebuie „activată” după ce vom fi stabilit structura de bază a cuplajelor.

Am evidenţiat mai sus câteva aspecte de corectat sau de completat, mai mult sau mai puţin importante; dar adevărata „finalizare” este încă departe şi ar consta în strângerea programelor respective într-un pachet R unitar (plus aplicaţii interactive, HTML+jQuery), care să exteriorizeze un set de funcţii cu denumiri bine alese, acoperind etapele principale de lucru; pe lângă etapele vizate până acum (preluarea şi normalizarea încadrării; distribuirea orelor pe zilele de lucru; obţinerea orarului unei zile), mai trebuie abordată şi chestiunea prezentării finale a orarului – de exemplu, ca site HTML (care să poată fi uşor de actualizat, în cazul schimbării orarului).

vezi Cărţile mele (de programare)

docerpro | Prev | Next