Le blog d'un Geekus biologicus juvénile

Jeu des tentes en Answer Set Programming

Le jeu des tentes est un casse-tête logique qui se joue sur une grille rectangulaire ou carrée. Chaque case de la grille peut être occupée par un arbre, une tente ou rester vide. <Nourry (2024)>

Les règles sont les suivantes:

• Il y a des arbres sur certaines cellules de la grille.
• Les tentes sont placées sur des emplacement vides.
• Chaque tente est attaché à un arbre placé sur une case adjacente (pas en diagonale).
• Un arbre ne peut être associé qu’à une seule tente.
• Deux tentes ne peuvent se toucher, même en diagonale.
• Le nombre de tentes de chaque colonne et de chaque ligne est indiqué.
• Certaines cases sont inaccessibles, il est impossible d’y placer une tente. <“Fiche: Jeux de Réflexion - Tentes” (n.d.);Nourry (2024)>

Dans son rapport, Célian Nourry a proposé un programme de résolution de ce problème avec du backtracking implémenté en C. Dans le présent article, on va s’intéresser à un encodage de ce problème avec l’Answer Set Programming.

Carrés latins en Answer Set Programming

Un carré latin est un tableau dans lequel chaque ligne et chaque colonne contient le même ensemble de symboles. L’objectif de ce billet est de proposer un ensemble de règles Answer Set Programming pour générer les carrés latins en utilisant la programmation par contrainte.

Les règles du carré latin

alphabet(a;b;c;d;e;f;g;h;i;j;k;l;m;n;o;p;q;r;s;t;u;v;w;x;y;z).

% Chaque cellule a un symbole issu de l'alphabet.
1 { cell(R, C, S): alphabet(S) } 1 :- R = 1..side , C = 1..side.

% Une cellule ne peut contenir qu'une seule valeur
S1 = S2 :- cell(R, C, S1) , cell(R, C, S2).

% Une ligne ne peut contenir plusieurs fois la même valeur
S1 != S2 :- cell(R, C1, S1) , cell(R, C2, S2) , C1 != C2.
% Idem pour les colonnes.
S1 != S2 :- cell(R1, C, S1) , cell(R2, C, S2) , R1 != R2.

% On vérifie que chaque ensemble de symboles
% pour chaque ligne et chaque colonne est le même que la référence
symbol(S) :- cell(1, C, S) , C = 1..side.

:- - symbol(S) , cell(_, _, S).
:- symbol(S) , - cell(R, _, S) , R = 1..side.
:- symbol(S) , - cell(_, C, S) , C = 1..side.

Application avec trois exemples

Les exemples qui suivent sont issus des « Selected Papers on Fun and Games » de Donald E. Knuth, chapitre 36 Quadrata Obscura. Je me suis permis d’ajouter les cellules de la ligne du bas dans l’entrée des problèmes, correspondants aux mots anglais choisis par Knuth; ce qui a pour effet de limiter à un seul le nombre de carrés latins générés par Clingo pour chaque entrées, grâce aux choix judicieux des cellules indiquées dans l’entrée du problème. Une autre approche aurait pu être d’ajouter une contrainte sur les cellules de la ligne du bas pour qu’elle corresponde à un mot d’une liste donnée…

Les échelles de mots de Lewis Carroll, une application de GraphSearch et du problème de l'arbre de Steiner

Source: chapitre 33 de « Selected Papers on Fun and Games » de Donald E. Knuth.

Une échelle de mots est un jeu qui consiste à trouver, connaissant un mot de départ et un mot d’arrivée une succession de mots tel que le mot \(i+1\) est semblable au mot \(i\) (au sens où une transformation simple suffit à passer du mot \(i\) au mot \(i+1\)).

Nous allons considerer une version simplifiée du jeu qui n’autorise que l’opération de changement d’une lettre sur les mots (on ignore les opérations « ajout / retrait de lettre » et « changement de l’ordre des lettre »).

Quelques problèmes en Answer Set Programming

Cette page rassemble quelques solutions en Answer Set Programming (avec Clingo) à une sélection de problèmes de logique originaires de sources diverses et variées.

Brilliant Order logic

Source: https://brilliant.org

Qu°1

• 4 is before 1 and 2.
• 3 is after 1 and 2.
• 2 is before 1.

#const n=4.

values(1..n).
before(4, (1;2)).
after(3, (1;2)).
before(2, 1).


values(1..n).

after(After, Before) :- before(Before, After).
before(Before, After) :- after(After, Before).

n { position(Value, Position): values(Value), values(Position) } n.

:- position(Value, Position1), position(Value, Position2) , Position1 != Position2.
:- position(Value1, Position), position(Value2, Position) , Value1 != Value2.


Position1 < Position2 :- before(Value1, Value2) , position(Value1, Position1), position(Value2, Position2).

#show position/2.

4,2,1,3

Le problème de couverture par sommets en Answer Set Programming avec Clingo

Dans le précédent poste, nous avions résolu le problème de la couverture minimale avec l’Integer Programming. Dans ce billet, nous poursuivons notre exploration de ce problème en implémentant un programme logique Answer Set Programming avec clingo.

Reprenons le meme exemple:

% On commence par définir le graphe non orienté
% L'ensemble des sommets
noeud(a;b;c;d;e).
% L'ensemble des aretes
arete(a,c).
arete(a,d).
arete(a,e).
arete(c,b).
arete(d,e).

% Comme le graphe est non orienté, dès lors qu'une arete u,v existe, l'arete v,u est prise en compte.
arete(U,V) :- arete(V,U).

% Ici commence les choses intéressantes:

% Définition d'une couverture valide
:- couverture(V), - noeud(V).
% la couverture est un sous-ensemble des sommets

1 { couverture(U); couverture(V) } 2 :-
  arete(U, V).

cardinal(N) :- #count { V: couverture(V) } = N.
#minimize { N: cardinal(N) }.
#show couverture/1.

clingo version 5.8.0
Reading from /tmp/babel-lLz0Yh/clingo-zvg3tr
Solving...
Answer: 1 (Time: 0.001s)
couverture(c) couverture(d) couverture(e)
Optimization: 3
OPTIMUM FOUND

Models       : 1
  Optimum    : yes
Optimization : 3
Calls        : 1
Time         : 0.001s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.001s

Ce qui donne, en jaune sur le graphe ci-dessous, la couverture minimale:

Le problème de couverture par sommets en Integer Linear Programming avec LP-solve

Le problème de couverture par sommets (ou Vertex Cover en anglais) consiste, étant donné un graphe, à trouver un ensemble minimum de sommets de sorte que toutes les arêtes soient couvertes.

Formellement: soit \(G(V, E)\) un graphe, une couverture est un ensemble \(S\) tel que: \[ S \subseteq V \text{ tel que } \forall e = (u, v) \in E, u \in S, \text{ ou } v \in S \]

L’objectif est de miniser la taille de \(S\).

Analyser des sons pour le programme Vigie-Chiro sur votre machine GNU/Linux avec Wine

Après avoir enregistré des sons de chauve-souris, orthoptères ou d’oiseaux, il est souvent utile de jeter un oeil aux spectrogrammes des enregistrements, par exemple lors de l’analyse d’enregistrements réalisés dans le cadre du programme Vigie-Chiro.

Les logiciels recommandés dans les tutoriels Vigie-Chiro sont, pour certains, développés uniquement pour Windows. Dans cet article, nous apprendrons comment installer ces logiciels (Kaleidoscope, Syrinx, Batsound 4, 7-zip et Lupas-Rename) sur une machine Linux à l’aide de Wine.

How to render pseudocode in Hugo with pseudocode.js

To render pseudocode in Hugo, you can use the pseudocode.js library.

Here is what I did to make this working on my blog.

Theme configuration

In your theme files, you will first need to add link to the library CDN.

<!-- in themes/<theme>/layouts/partials/pseucodode.html -->
<script src="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.16.7/katex.min.js"
        integrity="sha512-EKW5YvKU3hpyyOcN6jQnAxO/L8gts+YdYV6Yymtl8pk9YlYFtqJgihORuRoBXK8/cOIlappdU6Ms8KdK6yBCgA=="
        crossorigin="anonymous" referrerpolicy="no-referrer">
</script>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/pseudocode@latest/build/pseudocode.min.css">
<script src="https://cdn.jsdelivr.net/npm/pseudocode@latest/build/pseudocode.min.js"></script>

And render all element with pseudocode HTMl class.

<!-- in themes/<theme>layouts/partials/pseudocode-render.html -->
<script>
    let pseudocodeElements = document.getElementsByClassName("pseudocode");
    for (let element of pseudocodeElements) {
        pseudocode.renderElement(element);
    }
</script>

<!-- in themes/<theme>/layouts/_default/baseof.html -->
<head>

    ...

    {{ if .Param "pseudocode" }}
      {{ partialCached "pseudocode" . }}
    {{ end }}
</head>

<body>
    
    ...

    <main>
        {{ block "main" . }}{{ end }}
        {{ if .Param "pseudocode" }}
            {{ partialCached "pseudocode-render" . }}
        {{ end }}
    <main>
</body>

Writing

Then, in your Markdown article, add the following in your frontmatter:

Unixfu

A bean for some useful UNIX command snippets.

hour() {
    start=$1
    duration=$2
    IFS=":" read -r duration_hour duration_minute <<< $duration
    date -d "$start $(($duration_hour * 60 + $duration_minute)) minutes" +"%H:%M"
}
hour 17:00 5:43

22:43

sudo dnf install xclip # sur fedora par exemple

echo "Coucou !" | xclip -selection c

cat ~/.ssh/id_ecdsa.pub | xclip -selection c

sudo mkdir -p /mnt/shared
sudo chmod -R a+rwX /mnt/shared
sudo semanage fcontext -a -t svirt_home_t "/mnt/shared(/.*)?"
sudo restorecon -R /mnt/shared
tee fs.xml << EOF > /dev/null
<filesystem type='mount' accessmode='mapped'>
<source dir='/mnt/shared'/>
<target dir='shared'/>
</filesystem>
EOF
virsh shutdown vm
virsh attach-device vm fs.xml --config
virsh start vm
ssh vm
sudo mkdir -p /mnt/shared
sudo tee -a /etc/fstab << EOF > /dev/null
shared /mnt/shared 9p trans=virtio 0 0
EOF
sudo mount -a

sudo apt install python3-venv

python3 -m venv .venv/myproject