Sys.command "ocaml -version";;

type place = int;;
type rues = place list;;

type ville = rues list;;

let graphe1 : ville = [
    [2];           (* place 0 *)
    [2; 3; 6];     (* place 1 *)
    [0; 1];        (* place 2 *)
    [1; 4];        (* place 3 *)
    [3; 5];        (* place 4 *)
    [1; 4; 6; 8];  (* place 5 *)
    [1; 5; 7];     (* place 6 *)
    [6; 8];        (* place 7 *)
    [5; 7];        (* place 8 *)
];;

type eclairage = place list;;

let eclairage1_sat : eclairage = [
    0; 1; 2; 3; 4; 5; 6; 7; 8
];;

let eclairage2_sat : eclairage = [
    1; 2; 3; 5; 6; 8
];;

let eclairage1_nonsat : eclairage = [
    2; 4; 8
];;

let eclairage2_nonsat : eclairage = [
    1; 2; 3; 5; 6
];;

let somme =
    List.fold_left (+) 0
;;

let compte_simple_ou_double_0 (ici : place) (voisines : rues) (proposition : eclairage) =
    somme
    (List.map (fun voisine -> 
        if List.mem voisine proposition
        then 1
        else 2
    ) voisines)
;;

let verifie_eclairage_0 (graphe : ville) (proposition : eclairage) : bool =
    (* 1. compter le nombre de rues *)
    let nombre_rues =
        List.fold_left (fun a b -> a + (List.length b)) 0 (graphe)
        (* (List.length (List.flatten graphe)) *)
    in
    (* 2. pour chaque place *éclairée*, compter le nombre de rues qui en partent *)
    let nombre_rues_eclairees =
        somme
        (List.map (fun place_eclairee ->
            compte_simple_ou_double_0
            place_eclairee
            (List.nth graphe place_eclairee)
            proposition
        ) proposition)
    in
    (* 3. s'il y a (au moins) une rue non éclairée, renvoyer [false], sinon renvoyer [true] *)
    nombre_rues <= nombre_rues_eclairees
;;

let compte_simple_ou_double (_ : place) (voisines : rues) (est_eclairee : bool array) =
    somme
    (List.map (fun voisine -> 
        if est_eclairee.(voisine)
        then 1
        else 2
    ) voisines)
;;

let precalcule_places_eclairees (n : int) (proposition : eclairage) : bool array =
    let resultat = Array.make n false in
    List.iter (fun i -> 
        resultat.(i) <- true
    ) proposition;
    resultat
;;

let verifie_eclairage (graphe : ville) (proposition : eclairage) : bool =
    (* 0. précalcul *)
    let n = List.length graphe in
    let est_eclairee = precalcule_places_eclairees n proposition in
    (* 1. compter le nombre de rues *)
    let nombre_rues =
        List.fold_left (fun a b -> a + (List.length b)) 0 (graphe)
        (* (List.length (List.flatten graphe)) *)
    in
    (* 2. pour chaque place *éclairée*, compter le nombre de rues qui en partent *)
    let nombre_rues_eclairees =
        somme
        (List.map (fun place_eclairee ->
            compte_simple_ou_double
            place_eclairee
            (List.nth graphe place_eclairee)
            est_eclairee
        ) proposition)
    in
    (* 3. s'il y a (au moins) une rue non éclairée, renvoyer [false], sinon renvoyer [true] *)
    nombre_rues <= nombre_rues_eclairees
;;

graphe1;;

eclairage1_sat;;
List.map (fun place_eclairee -> List.nth graphe1 place_eclairee) eclairage1_sat;;

verifie_eclairage graphe1 eclairage1_sat;;    (* true *)

eclairage2_sat;;
List.map (fun place_eclairee -> List.nth graphe1 place_eclairee) eclairage2_sat;;

verifie_eclairage graphe1 eclairage2_sat;;    (* true *)

let eclairage3_sat : eclairage = [
    2; 3; 5; 6; 7;
];;

List.map (fun place_eclairee -> List.nth graphe1 place_eclairee) eclairage3_sat;;

verifie_eclairage graphe1 eclairage3_sat;;    (* true *)

eclairage1_nonsat;;
List.map (fun place_eclairee -> List.nth graphe1 place_eclairee) eclairage1_nonsat;;

verifie_eclairage graphe1 eclairage1_nonsat;;   (* false *)

eclairage2_nonsat;;
List.map (fun place_eclairee -> List.nth graphe1 place_eclairee) eclairage2_nonsat;;

verifie_eclairage graphe1 eclairage2_nonsat;;   (* false *)

let max_liste (liste : int list) : int =
    List.fold_left max (-max_int) liste
;;

max_liste [123; 12; 1];;

let max_liste_liste (listeliste : int list list) : int =
    max_liste (List.map max_liste listeliste) 
;;

max_liste_liste [[123; 12; 1]; [1234; 13]];;

List.for_all (fun x -> (0 <= x) && (x <= 1234)) (List.flatten [[123; 12; 1]; [1234; 13]])

let compte_occurences (liste : int list) (x : int) =
    let rec aux xs x acc =
        match xs with
        | [] -> acc
        | y :: ys when y = x -> aux ys x (acc + 1)
        | _ :: ys -> aux ys x acc
    in
    aux liste x 0
;;

compte_occurences [1; 2; 3; 4; 5] 1;;
compte_occurences [1; 2; 3; 4; 5] 10;;
compte_occurences [1; 2; 3; 4; 5; 1; 6; 7] 1;;

let graphe_valide (graphe : ville) : bool =
    let n = max_liste_liste graphe in
    (* D'abord, on vérifie qu'il y a exactement n + 1 listes de places voisines *)
    let test1 =
        (List.length graphe) = (n + 1)
    in
    (* Ensuite, on vérifie que toutes les places voisines sont bien dans des places valides *)
    let test2 =
        List.for_all (
            fun x -> (0 <= x) && (x <= n)
        ) (List.flatten graphe)
    in
    (* Enfin, on vérifie qu'une place voisine v n'est présente qu'une fois dans V[u] *)
    let test3 =
        List.for_all (
            fun voisines -> List.for_all (
                fun place ->
                    (compte_occurences voisines place) = 1
            ) voisines
        ) graphe
    in
    (* test1, test2, test3 *)
    test1 && test2 && test3
;;

graphe1;;

graphe_valide graphe1;;

let graphe2 : ville = [
    [2];           (* place 0 *)
    [2; 3; 6];     (* place 1 *)
    [0; 1];        (* place 2 *)
    [1; 3];        (* place 3 *)
    [3; 5];        (* place 4 *)
    [1; 4; 6; 8];  (* place 5 *)
    [1; 5; 7];     (* place 6 *)
    [6; 8];        (* place 7 *)
                   (* place 8 absente ! *)
];;

graphe_valide graphe2;;

let graphe3 : ville = [
    [2];           (* place 0 *)
    [2; 3; 6];     (* place 1 *)
    [0; 1];        (* place 2 *)
    [1; 3];        (* place 3 *)
    [3; 5];        (* place 4 *)
    [1; 4; 6; 8];  (* place 5 *)
    [1; 5; 7];     (* place 6 *)
    [6; 8];        (* place 7 *)
    [5; 7];        (* place 8 absente ! *)
    [5; 7]         (* place 9 ?! *)
];;

graphe_valide graphe3;;

let graphe4 : ville = [
    [2];           (* place 0 *)
    [2; 3; 6];     (* place 1 *)
    [0; 1];        (* place 2 *)
    [1; 3];        (* place 3 *)
    [3; 5];        (* place 4 *)
    [1; 4; 6; 8];  (* place 5 *)
    [1; 5; 7];     (* place 6 *)
    [6; 8];        (* place 7 *)
    [50]           (* place 8 -> 50 ?! *)
];;

graphe_valide graphe4;;

let graphe5 : ville = [
    [2];           (* place 0 *)
    [2; 3; 6];     (* place 1 *)
    [0; 1];        (* place 2 *)
    [1; 3];        (* place 3 *)
    [3; 5];        (* place 4 *)
    [1; 4; 6; 8];  (* place 5 *)
    [1; 5; 7];     (* place 6 *)
    [6; 8];        (* place 7 *)
    [5; 7; 5]      (* place 8 -> 5 deux fois ! *)
];;

graphe_valide graphe5;;

let ajoute_ou_pas (x : 'a) (acc : 'a list list) =
    (List.map (fun liste ->
        if (List.mem x liste)
        then liste
        else x :: liste
    ) acc
    )
    @
    (List.filter (fun liste ->
        not (List.mem x liste)
    ) acc
    )
;;

ajoute_ou_pas 1 [[]];;
ajoute_ou_pas 2 [[1]; []];;

let tous_sous_ensembles (liste : 'a list) : 'a list list =
    let rec aux xs acc =
        match xs with
        | [] -> acc
        | y :: ys ->
            aux ys (ajoute_ou_pas y acc)
    in
    aux liste [ [] ]
;;

tous_sous_ensembles [];;
tous_sous_ensembles [1];;
tous_sous_ensembles [1; 2];;
tous_sous_ensembles [1; 2; 3];; (* taille 2^3 = 8 *)

tous_sous_ensembles [0; 1; 2; 3];; (* taille 2^4 = 16 *)
tous_sous_ensembles [0; 1; 2; 3; 4];; (* taille 2^5 = 32 *)
tous_sous_ensembles [0; 1; 2; 3; 4; 5];; (* taille 2^6 = 64 *)
tous_sous_ensembles [0; 1; 2; 3; 4; 5; 6];; (* taille 2^7 = 128 *)
tous_sous_ensembles [0; 1; 2; 3; 4; 5; 6; 7];; (* taille 2^8 = 256 *)
tous_sous_ensembles [0; 1; 2; 3; 4; 5; 6; 7; 8];; (* taille 2^9 = 512 *)

assert ((List.length (tous_sous_ensembles [0; 1; 2; 3; 4; 5; 6; 7; 8])) = 512);;

let range (n : int) : (int list) =
    let rec range_x (n : int) : (int list) =
    match n with
    | n when n < 0 -> []
    | 0 -> [0]
    | n -> n :: (range_x (n - 1))
    in
    List.rev (range_x n)
;;

range 0;;
range 1;;
range 5;;
range 10;;

let tous_les_eclairages_possibles (graphe : ville) : (eclairage list) =
    assert (graphe_valide graphe);
    let n = (List.length graphe) - 1 in
    let sommets = range n in
    tous_sous_ensembles sommets    
;;

tous_les_eclairages_possibles graphe1;;

let min_liste (liste : int list) : int =
    List.fold_left min (max_int) liste
;;

min_liste [123; 12; 1];;

let taille_min (listes : int list list) : int =
    min_liste (List.map List.length listes)
;;

let eclairages_optimaux (graphe : ville) : (eclairage list) =
    let propositions =
        tous_les_eclairages_possibles graphe
    in
    let propositions_valides =
        List.filter (verifie_eclairage graphe) propositions
    in
    let taille_minimale = 
        taille_min propositions_valides
    in
    let propositions_minimales =
        List.filter (fun li ->
            (List.length li) = taille_minimale
        ) propositions_valides
    in
    propositions_minimales
;;

let graphe2 : ville = [
    [1; 2];  (* place 0 -> 1 2 *)
    [0; 2];  (* place 1 -> 0 2 *)
    [0; 1]   (* place 2 -> 0 1 *)
] ;;

tous_les_eclairages_possibles graphe2;;

List.length (tous_les_eclairages_possibles graphe2);;

eclairages_optimaux graphe2;;

graphe1;;

tous_les_eclairages_possibles graphe1;;

List.length (tous_les_eclairages_possibles graphe1);;

eclairages_optimaux graphe1;;