[1] V.Bazon - De la seturi de date și limbajul R, la orare școlare (Google Books)
[2] V. Bazon - Orare școlare echilibrate și limbajul R (Google Books)
[3] v. partea a II-a
Reluăm într-un program "analyze.R", cu unele mici îndreptări, funcțiile referitoare la șabloanele binare de orare individuale:
# analyze.R library(tidyverse) hourly_matrix <- function(Dorar) { # pleacă de la forma normală prof|cls|ora orz <- Dorar %>% droplevels() %>% split(.$prof) %>% map_df(., function(K) pivot_wider(K, names_from="ora", values_from="cls")) M <- orz[, c('prof', sort(colnames(orz)[-1]))] %>% replace(is.na(.), '-') %>% as.matrix() row.names(M) <- M[, 1] M[, 2:ncol(M)] } # rezultă matricea-orară a zilei, prof |1|2|3|4|5|6|7 h2bin <- as.integer(c(1, 2, 4, 8, 16, 32, 64)) # măștile orelor zilei cnt_holes <- function(sb) { # sb: șablonul binar al orelor profesorului bits <- which(bitwAnd(sb, h2bin) > 0) # rangurile biților '1' n <- length(bits) bits[n] - bits[1] + 1 - n } # Numărul de biți '0' aflați între biți '1' ("ferestre") byte_line <- function(sb) bitwAnd(sb, h2bin) %>% sapply(., function(b) if(b) "*" else "-") %>% paste0(., collapse = "") # forma literală a șablonului binar new_SB <- function(sb, h1, h2) bitwShiftL(1, h1-1) |> bitwNot() |> bitwAnd(sb) |> bitwOr(bitwShiftL(1, h2-1)) # șablonul rezultat după mutarea (h1, h2) bin_patt <- function(matPr) apply(matPr, 1, function(Row) sum(h2bin[which(! Row %in% "-")])) # dicționar (Prof, Șablon)
bin_patt() returnează un vector cu nume (spre deosebire de varianta "îmbunătățită", din [3]-IV, unde returnam numai valorile acestui vector); păstrând numele, putem selecta imediat liniile cu ferestre, din matricea-orar curentă (v. primele trei linii din funcția următoare, cu care încheiem programul "analize.R"):
list_gaps <- function(OZ) { Vsb <- bin_patt(OZ) # transformă liniile orare în șabloane binare B1 <- which(Vsb %in% names(SBC)) # indecșii celor cu ferestre B2 <- Vsb[B1] # prof_cu_ferestre --> șablonul_binar_al_orarului_său sapply(B2, cnt_holes) %>% as.data.frame() %>% rename(gaps=1) %>% rownames_to_column(var="prof") %>% mutate(row = B1, byte = B2 %>% as.vector()) %>% mutate(template = sapply(byte, byte_line)) %>% arrange(desc(gaps)) }
De exemplu, pentru unul dintre orarele de care ne-am ocupat anterior pe aici:
source("analyze.R") load("SBC.Rda") # 1092 mutări corectoare (h1 h2) ORR <- readRDS("~/24oct/Orar1.RDS") mORR <- map(ORR, hourly_matrix) OZ <- mORR[["Lu"]] # matricea-orară inițială, a zilei Lu VS <- list_gaps(OZ) prof gaps row byte template prof gaps row byte template 1 En3 2 23 21 *-*-*-- 14 Gr3 1 22 5 *-*---- 2 Sp3 2 26 38 -**--*- 15 Ds1 1 24 13 *-**--- 3 Fz5 2 30 36 --*--*- 16 Ro4 1 27 46 -***-*- 4 Ro5 2 36 50 -*--**- 17 Ro3 1 29 22 -**-*-- 5 TI1 2 38 57 *--***- 18 In3 1 33 40 ---*-*- 6 Fr1 2 40 53 *-*-**- 19 Fz1 1 35 46 -***-*- 7 Bl1 2 43 57 *--***- 20 En2 1 39 52 --*-**- 8 Gg1 2 44 53 *-*-**- 21 Ch2 1 45 122 -*-**** 9 Ch1 2 53 121 *--**** 22 Is1 1 47 54 -**-**- 10 En5En1 1 6 10 -*-*--- 23 Ec1 1 49 58 -*-***- 11 Bl3 1 11 11 **-*--- 24 Sp1 1 50 58 -*-***- 12 En5 1 20 5 *-*---- 25 En1 1 51 52 --*-**- 13 In1 1 21 29 *-***--
Vedem astfel că orarul inițial (înainte de a demara procedura de reducere a ferestrelor) conține 34 de ferestre — dacă neglijăm eventualele ferestre "ascunse", ale celor implicați în cuplaje! — repartizate câte două la 9 profesori și câte una la alți 16 profesori (subliniem că în funcția concisă list_gaps() nu se au în vedere ferestrele "ascunse" și nici cele "false", existente eventual în orarul curent!).
Restrângând cheile din SBC la cele din coloana byte, găsim numărul de mutări corectoare care pot fi aplicate orarului respectiv:
print(SBC[as.character(VS$byte)] %>% unlist() %>% length()/2) [1] 286 # mutări corectoare pentru orarul curent
Iar acum, să considerăm de exemplu șablonul orar al lui En1 (v. linia 25) și să vedem ce "mutări corectoare" ne propune SBC:
> SBC[["52"]] # --*-**- $h1 [1] 3 3 3 3 5 5 5 5 6 6 6 6 $h2 [1] 1 2 4 7 1 2 4 7 1 2 4 7
În setul SBC curent am avut în vedere (v. [2]) toate posibilitățile de mutare a unei lecții "*" pe un loc liber "-"; dar mutările (3 1) și (5 1) sunt chiar "absurde": șabloanele rezultate, "*---**-" și respectiv "*-*--*-" au câte trei ferestre, în loc de singura fereastră din șablonul inițial. Și mai absurdă, ar fi mutarea (3 7) prevăzută în SBC[["5"]] (v. liniile 12, 14): în loc de fereastra inițială, ar rezulta 5 ferestre!
Considerăm ca "absurdă", o mutare (h1 h2) prin care numărul de ferestre devine mai mare decât 2; cel mai probabil, efectuarea unor asemenea mutări consumă în mod inutil, un anumit număr de iterații ale procesului de reducere a ferestrelor — încât se cuvine să le eliminăm din SBC:
for(sb in names(SBC)) { h1 <- SBC[[sb]]$h1 h2 <- SBC[[sb]]$h2 ex <- vector("integer", 0) for(j in 1:length(h1)) { ns <- new_SB(as.integer(sb), h1[j], h2[j]) if(cnt_holes(ns) > 2) # vom exlude mutările care ex <- c(ex, j) # produc mai mult de două ferestre } if(length(ex) > 1) { ## h1[-0] este integer(0) SBC[[sb]]$h1 <- h1[-ex] SBC[[sb]]$h2 <- h2[-ex] } } save(SBC, file="SBC.Rda")
De-acum, "SBC.Rda" conține cam cu 300 de mutări corectoare mai puțin, decât considerasem anterior:
> SBC |> unlist() |> length()/2 [1] 794 # mutări corectoare (h1 h2)
Restrângând cheile din noul SBC la cele din VS$byte găsim acum, numai 229 de mutări corectoare (cam cu 50 mai puține decât pentru SBC inițial); procesul iterativ de reducere a ferestrelor (declanșat de search_better()) va decurge mai rapid acum, dat fiind că se evită încercările de mutări care nu prea au șanse de a conduce la un orar cu număr total de ferestre mai mic decât cel inițial.
O execuție pentru ziua curentă, în care se nimeresc "cel mai bune" mutări corectoare, poate duce la un orar cu numărul minim posibil de ferestre în mai puțin de un minut (uneori, chiar și numai în 15 secunde):
19:23:55 Lu (35 ferestre)
34 33 32 30 28 27 26 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 * 5 * 5 * 5 * 5 19:24:49
20:21:49 Ma (41 ferestre)
40 39 38 37 36 35 33 32 30 28 27 25 24 22 20 19 18 17 16 15 14 13 12 11 10 9 * 9 * 9 8 * 8 6 5 4 * 4 20:22:46
21:08:05 Jo (40 ferestre)
39 38 37 36 35 34 31 30 29 28 27 26 25 24 23 22 19 17 16 15 14 13 12 11 10 9 8 7 6 5 4 * 4 21:08:19 # 15 secunde
(am evidențiat aici și reduceri intermediare cu câte două sau trei ferestre deodată; de remarcat că lanțul reducerilor succesive este mai scurt, decât când foloseam SBC-ul inițial)
Dar de obicei, o execuție pentru ziua curentă ia până în două minute și în general, se oprește deasupra numărului minim de ferestre:
21:02:37 Jo (40 ferestre) # execuție precedentă ultimeia de mai sus
39 37 36 35 34 33 32 31 29 27 26 25 24 23 22 21 19 18 17 16 15 14 13 12 11 10 9 * 9 8 7 * 7 * 7 * 7 21:03:31
încât execuția trebuie repetată de mai multe ori (pe ziua curentă), pentru a ajunge la un orar cu numărul de ferestre cât mai aproape de minimul posibil.
vezi Cărţile mele (de programare)