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

Problema orarului școlar echilibrat și limbajul R (II)

limbajul R | orar şcolar
2023 may

În [1] ajunsesem la un orar cu respectiv 7 / 11 / 10 / 7 / 6 ferestre pe zi; între timp, repetând programul reduce_gaps.R (după ce am dublat numărul de iterări în funcția search_better() și în compensație, am forțat cover_gaps() să returneze doar o parte aleatorie a reparațiilor curente de ferestre), am ajuns la un orar cu numai 35 de ferestre:

Mai <- readRDS("orar_mai.RDS")  # orarul curent
    sapply(Zile, function(zi) {
        set_globals(zi)  # v. [1]
        count_gaps(Mai[[zi]])
    }) |> print()
 Lu Ma Mi Jo Vi 
  5 10  9  6  5   # numărul curent de ferestre, pe fiecare zi (în total, 35)

Numărul de ferestre pe Ma și Mi rămâne (practic, oricât am repeta search_better()) sensibil mai mare decât pe celelalte zile; ar fi de investigat cauzele acestui fapt, reluând în ultimă instanță, repartizarea pe zile a lecțiilor…
Este de subliniat că spre deosebire de orarul original de pe care am dedus datele de încadrare (v. [1]), lecțiile au fost repartizate echilibrat – dar în pofida acestei diferențe majore, avem acum un număr sensibil mai mic de ferestre, decât cel (=55) din orarul original.
De obicei, pentru a remedia ferestrele se renunță la echilibre – acceptând ca un obiect sau altul să aibă două ore la clasă într-o aceeași zi, un profesor sau altul să aibă 2 ore într-o zi și 7 într-o alta, o clasă să aibă 4 ore într-o zi (începând poate nu de la prima, ci de la a doua sau a treia oră a zilei) și 7 într-o alta – dar aceasta nu este calea noastră, deschisă în [1] (am urmărit consecvent o repartizare cât mai uniformă a lecțiilor, pe zile, clase, profesori și obiecte).

În loc de a regândi repartizarea (echilibrată) pe zile, pare totuși „mai simplu” (și ar fi mai folositor) să vedem dacă nu cumva am putea reduce numărul de ferestre pe Ma și Mi, doar schimbând în prealabil unele ore (lecții prof|cls|ora) între aceste două zile (cu grija de a nu dezechilibra sensibil, orarul).

În principiu, pentru a decide ce schimbări de ore între cele două zile ar trebui încercate (în scopul de a reduce numărul de ferestre), ar trebui să plecăm de la profesorii care au ferestre; deci întâi, s-ar cuveni să evidențiem ferestrele existente în orarele zilelor.

Orarele zilelor sunt (în final) matrici care au drept nume de linii numele profesorilor (codificate după disciplină și număr de ore – v. [1]) și drept valori, clasele repartizate profesorilor respectivi în fiecare oră a zilei (sau "-" pentru fereastră, sau oră liberă):

> str(Mai[["Ma"]])
 chr [1:67, 1:7] "7A" "9D" "-" "11B" "10C" "8A" "6A" "-" "11E" "-" "11C" ...
 - attr(*, "dimnames")=List of 2
  ..$ : chr [1:67] "ES2" "Fi5" "Ge3" "TI2" ...  # numele profesorilor
  ..$ : chr [1:7] "1" "2" "3" "4" ...  # orele 1..7 ale zilei

Următoarea funcție preia matricea-orar a unei zile, o transformă în data.frame (integrând drept coloană numele de linii ale matricei), apoi adaugă o coloană $SB pe care, pentru profesorii care au ferestre (și pentru cei angajați în cuplaje), se vor vizualiza șabloanele-orare, folosind vectorul h2bin (care conține măștile binare ale orelor 1..7) și funcția byte_as_line() (care transformă un octet într-un șir de caractere '*' sau '-') (v. [1]):

emph_gaps <- function(ORR) {
    Oz <- ORR %>% as.data.frame() %>% 
          mutate(prof = rownames(.), .before=1) %>%
          mutate(SB = "")
    rownames(Oz) <- NULL  # numele de linii nu mai sunt necesare
    for(P in Oz$prof) {
        if(nchar(P) > 3) next  # ignoră cuplajele (profesorii "fictivi")
        MP <- Oz %>% filter(grepl(P, prof))
        if(nrow(MP) == 1) {  # profesor neangajat în cuplaje
            patt <- sum(h2bin[which(! MP[1, 2:8] %in% "-")]) %>%
                    byte_as_line()  # v. [1]
            if(grepl(".*\\*-{1,2}\\*.*", patt))
                Oz[Oz$prof == P, "SB"] <- patt
        } else {  # profesor angajat în cel puțin un cuplaj
            patt <- 0L
            for(i in 1:nrow(MP))
                patt <- patt + sum(h2bin[which(! MP[i, 2:8] %in% "-")])
            Oz[Oz$prof == P, "SB"] <- byte_as_line(patt)
        }
    }
    Oz %>% arrange(prof)
}

Pe orarele individuale rezultate prin programele din [1] putem avea o fereastră, după șablonul parțial "*-*", sau două ferestre consecutive, după șablonul parțial "*--*"; deci expresia regulată care depistează orarele individuale cu ferestre este în cazul nostru, ".*\\*-{1,2}\\*.*" (folosită deja mai sus, pentru cei neangajați în cuplaje).
Următoarea funcție selectează din tabelul returnat de emph_gaps(), liniile corespunzătoare celor care au ferestre în ziua respectivă:

per_gaps <- function(Oz) 
    Oz %>% filter(grepl(".*\\*-{1,2}\\*.*", SB))

Cele 35 de ferestre existente pe orarul curent reprezintă 3.44% din totalul 1018 al tuturor lecțiilor dintr-o săptămână; or fi ele (zicem noi…) puține – dar este important să vedem și cum sunt repartizate ferestrele, pe profesori și zile:

gaps <- map_dfr(Zile, function(zi)
    Mai[[zi]] |> emph_gaps() |> per_gaps() %>%
    mutate(zi = zi, .before=2)) %>%
    arrange(prof)
           prof zi   1   2   3   4   5   6 7      SB
        1   Bi1 Vi 12A   -   -  9E 10E 10C - **-***-
        2   En1 Ma 12A 10C  9B   - 10B 12D - ***-**-
        3   En1 Mi  9B 10B   - 12D 10C  9E - **-***-
        4   En1 Vi 10C 11A   -  9B 10B  9E - **-***-
        5   En2 Lu  6D 10D 11B   -  8C  9D - ***-**-
        6   En2 Jo  8C  9D   - 10D 11B  6D - **-***-
        7   En3 Ma 10E 12B   -  5C 11E  7B - **-***-
        8   En4 Ma   -  6C   -  8B  7A 12E - -*-***-
        9   En4 Mi  6B  8A   -   - 12E  8B - **--**-
        10  En5 Lu  5B  5D 11D   - 12C   - - ***-*--
        11  Fi1 Ma   -  6A 12B   -  9C 11A - -**-**-
        12  Fr1 Ma   -  6B  7A   -   -   - - ***-*--
        13  Fr1 Jo   -   -   -   -  5B  8B - -**-**-
        14  IP1 Ma 10A 12A 11A   - 12A   - - ***-*--
        15  Is1 Mi  8B  6C 10E   -  8A 10D - ***-**-
        16  Is1 Jo  8A 11D  8C   - 11C 10E - ***-**-
        17  Is2 Jo 11E  7A  5D   -  5C   - - ***-*--
        18  Ma1 Lu  7A  5B  9A   - 11A 10A - ***-**-
        19  Ma2 Mi 10B  6A   -   -  9C  7B - **--**-
        20  Ma4 Vi   - 11B 12B   -  5C  8A - -**-**-
        21  Mu1 Vi  5B   -   -   -  8A  6B - ***-**-
        22  Re1 Ma  5B  6D   - 12C  6B   - - **-**--
        23  Ro2 Lu 10B  7A   - 10A 12D 11B - **-***-
        24  Ro2 Mi 12A  7A 12D   - 11B 10B - ***-**-
        25  Ro3 Lu 12E 12E  9C   - 12B  6A - ***-**-
        26  Ro3 Jo 12E  6A   -  9C 11A 12E - **-***-
        27  Ro3 Vi 12B  6A 12E   -  9C 11A - ***-**-
        28  Ro6 Ma 11C  5B   -  5A  5A   - - **-**--
        29  Sp1 Ma   -  9E   -  6B 10D  6A - -*-***-
        30  Sp1 Jo   - 10A   - 10C 10B  9D - -*-***-
        31  Sp2 Ma   -  5C   - 11A  5D  9A - -*-***-
        32  Sp3 Mi 11B  8B   -   -  7A  6D - **--**-

Constatăm că au apărut și situații pe care nu ni le-am fi dorit: doi profesori (En1 și Ro3) au câte trei zile cu câte o fereastră; trei profesori (En4, Ma2 și Sp3) au câte o zi – și se întâmplă că aceasta este la toți, ziua Mi – cu câte două ferestre consecutive (și se întâmplă că în aceleași ore ale zilei, a treia și a patra – după șablonul "**--**-").
Să observăm însă că dacă vom relua search_better() plecând de la orarele obținute mai sus, vom obține noi orare, cam cu același număr de ferestre zilnice, dar cu alte repartizări pe profesori a ferestrelor, poate mai convenabile…

Pe de altă parte, dacă vedem lucrurile global, la nivelul întregii săptămâni:

table(gaps$prof) |> as.data.frame() |> arrange(desc(Freq)) |> print()

putem aprecia că situația este totuși apropiată de „normal”: 14 profesori au doar câte o singură fereastră pe săptămână, 6 au câte două ferestre și numai doi, ajung la 3 ferestre pe săptămână; ceilalți 45 de profesori își fac orele fără nicio fereastră.
Iar aceste proporții s-ar îmbunătăți, dacă am reuși să reducem numărul de ferestre pe Ma și Mi (care este prea mare, față de celelalte zile).

Pentru un prim experiment, să considerăm liniile 8 și 9 din tabelul redat mai sus:

           prof zi   1   2   3   4   5   6 7       SB
        8   En4 Ma   -  6C   -  8B  7A 12E -  -*-***-
        9   En4 Mi  6B  8A   -   - 12E  8B -  **--**-

Să ne imaginăm că "6C" ar figura la En4 nu Ma în ora a doua (cu fereastră în a treia oră), ci Mi în ora a treia (sau în a patra); atunci En4 ar scăpa de două ferestre (este aproape sigur, având în vedere cum funcționează search_better(), că acele 3 ore rămase pe Ma vor rămâne așezate compact). Este drept însă că astfel, En4 (și poate, încă vreun profesor) ar căpăta o distribuție orară ușor dezechilibrată (3/5 în loc de 4/4)

Am mutat manual 6C din coloana orară "2" a zilei Ma în coloana "3" a zilei Mi – imitând funcția move_cls() (ținând seama că acum mutarea clasei are loc între coloane orare din zile diferite și nu ale unei aceleiași zile, ca în [1]). Pe orarul rezultat astfel, am lansat search_better() și apoi am evidențiat prin emph_gaps() noua situație a ferestrelor:

Ma prof   1   2  3   4   5   6 7      SB    Mi prof   1   2   3   4   5   6 7      SB
1   En3 12B  5C 7B   - 11E 10E - ***-**-    1   Ch1 10C 12E 12A   -  7C   - - ***-*--
2   En5  5D 11C 5B   - 11D   - - ***-*--    2   En1 10B  9B   -  9E 12D 10C - **-***-
3   Fi1  6A 11A 9C   - 12B   - - ***-*--    3   En2  6D 11B  8C   -  9D 10D - ***-**-
4   GF4   -   -  -   -   - 11E - -**-**-    4   En4  6C  8A  6B   - 12E  8B - ***-**-
5   IP1   - 10A  - 12A 12A 11A - -*-***-    5   Is1  8B 10D   - 10E  8A  6C - **-***-
6   Is1 10E 11B  - 12E  6B 10C - **-***-    6   Is2  9E 10A  5B   -  7A   - - ***-*--
7   IT1   -  5B  -  5C  5A  6D - -*-***-    7   Re2  5C  9E   -   - 11E 12A - **--**-
8   Ma5  6B 10C  - 12D  9E   - - **-**--
9   Ro1  5C  5D  -  8C 10C 11D - **-***-
10  Ro4  7B  9E  -  8A  6D   - - **-**--

Pe Ma avem tot 10 ferestre (toate de câte o singură oră – fie a treia, fie a patra), dar cu altă repartizare pe profesori, față de cea existentă pe orarul inițial; pe Mi au rezultat totuși 8 ferestre, în loc de cele 9 existente inițial (iar numărul de profesori cu câte două ferestre consecutive s-a redus de la 3, la 1 – anume la profesorul de Religie Re2).

Experimentul modest evocat mai sus arată că în final, am putea echilibra orarul și în privința numărului de ferestre pe zi, folosind o funcție analogă cu move_cls() din [1], prin care să mutăm anumite lecții prof|cls|ora între anumite coloane orare (cel mai probabil, a doua și a treia sau a patra) din orarele a două zile pe care numărul curent de ferestre a rămas prea mare, față de celelalte zile. Rămâne să formulăm o versiune corespunzătoare de move_cls() și să decidem asupra unei liste de mutări pe care să le încercăm succesiv, prin search_better()… Deasemenea, va trebui să vedem în ce măsură mutările respective perturbă echilibrele existente pe orarul inițial.

vezi Cărţile mele (de programare)

docerpro | Prev | Next