Le tour du cavalier

**elishac** · 28/04/2008, 20h47

Bonjour,

je suis débutant en CamL (et en informatique en général), et je cherche à m'entraîner avec quelques problèmes amusants. Celui que je considère ici est le tour du cavalier. Le but est d'accéder une et une seule fois (à savoir, au moins une fois, et pas deux fois) sur chaque case d'un échiquier de taille n*m (n est le nombre de lignes, et m celui de colonnes), avec un cavalier. Un cavalier est une pièce qui se déplace en L. Dans l'absolu, il a 8 déplacements possibles (cliquer ici pour plus d'informations).
J'impose de plus que la dernière case soit en communion avec la première, i.e. qu'on puisse accéder à la dernière case depuis la première, afin que ça forme une boucle (un "tour", d'où le nom du sujet).
J'ai déjà un peu (beaucoup)réfléchi à l'algorithme et à la programmation, mais je vais pas tout vous écrire d'un coup, sinon vous allez avoir peur et vous allez pas m'aider :-).
Je vous donne néanmoins mes idées générales :
- je numérote les case de l'échiquier de 1 à p=n*m (je commence en bas à gauche, et je numérote de gauche à droite, et en montant d'une ligne et en recommençant à gauche dès que je suis arrivé à la fin d'une ligne. Exemple pour n=2 et m=3 :
456
123
)
- j'utilise la méthode du programme intelligent, qui revient en arrière si la configuration envisagée n'aboutit pas, et essaye une autre voie.
- je crois qu'on peut montrer mathématiquement qu'il vaut mieux choisir en premier les cases qui ont le moins de cases accessibles, je vais donc inclure cela dans ma programmation (cela devrait alourdir les calculs mais réduire grandement le nombre de cas à étudier, et donc peut-être au final gagner du temps, bien que je n'aie fait aucun calcul de complexité temporelle à ce niveau-là).

Voilà pour l'idée générale de mon programme.
Je vais de suite écrire mes premières procédures, mais dans un autre post.
Je suis bien sûr ouvert à toutes remarques concernant l'algorithme, mais, à moins d'une grande opposition de votre part, c'est celui que j'adopterai, car j'y ai déjà pas mal réfléchi et ai écrit déjà pas mal de lignes de code, que j'aimerai partager avec vous, pour que vous les corrigiez si besoin.

Merci d'avance de vous intéresser à mon sujet.

**elishac** · 28/04/2008, 21h35

Tout ce que je dis ne sont que de simples conclusions personnelles, et je ne suis pas sûr du résultat. Je n'ai pas mis de "je crois", "peut-être", "que pensez-vous de",..., tout au long de mon exposé, pour ne pas trop alourdir, mais je ne suis pas sûr du tout de mes résultats, et c'est pour cela que je les poste : merci de les vérifier, et de me dire ce que vous en pensez (améliorations possibles, etc.).

La première chose que je souhaite créer, et qui vient naturellement à l'esprit, est un tableau cases_accessibles de taille p=n*m, pour lequel, pour tout entier naturel c appartenant à [0...p-1], cases_accessibles.(c) donne l'ensemble des cases théoriquement accessibles depuis la case c (théoriquement, car il faudra ensuite vérifier que la case n'a pas déjà été accédée une fois dans le tour considéré). Ce tableau me semble indispensable si on ne veut pas avoir à refaire sans cesse les mêmes calculs (en effet, il y a de fortes chances pour qu'on ait besoin de connaître plusieurs fois les cases accessibles à partir d'une même case, car l'algorithme revient en arrière ; le seul cas où ce n'est pas nécessaire, c'est si on trouve un "tour" du premier coup).
Pour ce faire, il nous faut déjà trouver les formules permettant d'avoir les 8 mouvements théoriquement disponibles (ce théoriquement signifie que pour l'instant on ne considère pas les problèmes de bord de l'échiquier), à partir de la case c :
c+2+m
c+2-m
c+1+2m
c+1-2m
c-1+2m
c-1-2m
c-2+m
c-2-m
Analysons maintenant les problèmes de bord :
dans un premier temps, les problèmes de haut et de bas. Il suffira de vérifier, quand on fait +am, avec a=1 ou a=2, que l'on ne dépasse pas le haut de l'échiquier, en vérifiant que le nombre reste inférieur ou égal à p=n*m.
De même, quand on descend, i.e. quand on fait -am, avec a=1 ou a=2, Il suffira de vérifier que l'on ne dépasse pas le bas de l'échiquier, en vérifiant que le nombre reste supérieur ou égal à 1.
enfin, les problèmes de bord : la réflexion n'est pas facile à exprimer en peu de lignes, donc je vous balance simplement le résultat, dîtes moi si vous êtes d'accord ou pas (si vous n'êtes pas d'accord, je développerai mon idée) :
quand il y a +1 dans la formule (bord à droite) : ((c-1) mod n) + 1 - n <0
quand il y a +2 dans la formule (bord à droite) : ((c-1) mod n) + 2 - n <0
quand il y a -1 dans la formule (bord à gauche) : (c-1) mod n >0
quand il y a -2 dans la formule (bord à gauche) : ((c-1) mod n) -1 >0

Voici donc la création du tableau cases_accessibles, suivant les remarques faites précédemment :
on suppose que p=n*m est une variable globale. Explication en deux mots : les tests de problème de bord à gauche ou à droite sont les mêmes pour 2 cases, je les regroupe donc (sous le nom boolean, qui change donc 8/2=4 fois), afin de ne pas faire 2 fois le même test. (comme pour tout le reste, mais tout particulièrement ici, je ne suis pas sûr du résultat, merci de corriger si besoin). De plus je nomme la case considérée, case_potentielle, pour plus de clarté, et parce qu'elle est utilisée 2 fois, afin de ne pas refaire le même calcul.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
let cases_accessibles = make_vect p [];;
for c=1 to p do
	let tmp=ref [] in
		let boolean=((c-1) mod n) + 2 - n <0 in
			let case_potentielle=c+2+m in
				if boolean && (case_potentielle <= p) then tmp:= case_potentielle :: (!tmp);
			let case_potentielle=c+2-m in
				if boolean && (case_potentielle >= 1) then tmp:= case_potentielle :: (!tmp);
		let boolean=((c-1) mod n) + 1 - n <0 in
			let case_potentielle=c+1+2m in
				if boolean && (case_potentielle <= p) then tmp:= case_potentielle :: (!tmp);
			let case_potentielle=c+1-2m in
				if boolean && (case_potentielle >= 1) then tmp:= case_potentielle :: (!tmp);
		let boolean=(c-1) mod n >0 in
			let case_potentielle=c-1+2m in
				if boolean && (case_potentielle <= p) then tmp:= case_potentielle :: (!tmp);
			let case_potentielle=c-1-2m in
				if boolean && (case_potentielle >= 1) then tmp:= case_potentielle :: (!tmp);
		let boolean=((c-1) mod n) -1 >0 in
			let case_potentielle=c-2+m in
				if boolean && (case_potentielle <= p) then tmp:= case_potentielle :: (!tmp);
			let case_potentielle=c-2-m in
				if boolean && (case_potentielle >= 1) then tmp:= case_potentielle :: (!tmp);
	cases_accessibles.(c)<-!tmp
done;;

Voilà, merci pour vos commentaires, suggestions, corrections, améliorations, ...

**Jedai** · 29/04/2008, 17h07

Envoyé par elishac

- je numérote les case de l'échiquier de 1 à p=n*m (je commence en bas à gauche, et je numérote de gauche à droite, et en montant d'une ligne et en recommençant à gauche dès que je suis arrivé à la fin d'une ligne.

Pourquoi ? Pourquoi s'imposer cette complication supplémentaire alors que tu pourrais te contenter de faire un tableau 2D (une matrice), à la fois plus lisible et plus intuitive...

Envoyé par elishac

- j'utilise la méthode du programme intelligent, qui revient en arrière si la configuration envisagée n'aboutit pas, et essaye une autre voie.

Ce n'est pas un algorithme "intelligent", c'est du simple backtracking sans aucune intelligence (mais c'est très suffisant pour le problème).

Envoyé par elishac

- je crois qu'on peut montrer mathématiquement qu'il vaut mieux choisir en premier les cases qui ont le moins de cases accessibles, je vais donc inclure cela dans ma programmation (cela devrait alourdir les calculs mais réduire grandement le nombre de cas à étudier, et donc peut-être au final gagner du temps, bien que je n'aie fait aucun calcul de complexité temporelle à ce niveau-là).

Il est relativement simple de rajouter ce tri après avoir fait la version naïve.

Envoyé par elishac

La première chose que je souhaite créer, et qui vient naturellement à l'esprit, est un tableau cases_accessibles de taille p=n*m, pour lequel, pour tout entier naturel c appartenant à [0...p-1], cases_accessibles.(c) donne l'ensemble des cases théoriquement accessibles depuis la case c (théoriquement, car il faudra ensuite vérifier que la case n'a pas déjà été accédée une fois dans le tour considéré). Ce tableau me semble indispensable si on ne veut pas avoir à refaire sans cesse les mêmes calculs (en effet, il y a de fortes chances pour qu'on ait besoin de connaître plusieurs fois les cases accessibles à partir d'une même case, car l'algorithme revient en arrière ; le seul cas où ce n'est pas nécessaire, c'est si on trouve un "tour" du premier coup).

Optimisation prématurée, commence par calculer à chaque coup les cases accessibles, ensuite si ton algo est trop lent tu pourras essayer cette optimisation.

Envoyé par elishac

Pour ce faire, il nous faut déjà trouver les formules permettant d'avoir les 8 mouvements théoriquement disponibles (ce théoriquement signifie que pour l'instant on ne considère pas les problèmes de bord de l'échiquier), à partir de la case c :

Et là apparaît l'une des raisons pour lesquelles je te conseillais de prendre une simple matrice et représenter tes mouvements et coordonnées par des paires d'entiers : le code que tu vas produire avec ta représentation va être difficile à lire et à écrire, et donc bien plus susceptible de contenir des fautes.

Envoyé par elishac

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
let cases_accessibles = make_vect p [];;
for c=1 to p do
	let tmp=ref [] in
		let boolean=((c-1) mod n) + 2 - n <0 in
			let case_potentielle=c+2+m in
				if boolean && (case_potentielle <= p) then tmp:= case_potentielle :: (!tmp);
			let case_potentielle=c+2-m in
				if boolean && (case_potentielle >= 1) then tmp:= case_potentielle :: (!tmp);
		let boolean=((c-1) mod n) + 1 - n <0 in
			let case_potentielle=c+1+2m in
				if boolean && (case_potentielle <= p) then tmp:= case_potentielle :: (!tmp);
			let case_potentielle=c+1-2m in
				if boolean && (case_potentielle >= 1) then tmp:= case_potentielle :: (!tmp);
		let boolean=(c-1) mod n >0 in
			let case_potentielle=c-1+2m in
				if boolean && (case_potentielle <= p) then tmp:= case_potentielle :: (!tmp);
			let case_potentielle=c-1-2m in
				if boolean && (case_potentielle >= 1) then tmp:= case_potentielle :: (!tmp);
		let boolean=((c-1) mod n) -1 >0 in
			let case_potentielle=c-2+m in
				if boolean && (case_potentielle <= p) then tmp:= case_potentielle :: (!tmp);
			let case_potentielle=c-2-m in
				if boolean && (case_potentielle >= 1) then tmp:= case_potentielle :: (!tmp);
	cases_accessibles.(c)<-!tmp
done;;

Quelle horreur... Penses-tu pouvoir relire ce code dans une semaine sans parler de dans quelques mois ?

Sépare les concepts, n'optimise pas prématurément, choisit une structure de donnée qui correspond bien au problème... KISS !!

Exemple en Haskell :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type BoardSpec = (Int,Int)
type Point = (Int,Int)
 
-- add a move to a position
(<+>) :: Point -> Point -> Point
(x,y) <+> (mx,my) = (x+mx,y+my)
 
knightMoves :: [Point]
knightMoves = [(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)]
 
validPos :: BoardSpec -> Point -> Bool
validPos (m,n) (x,y) = 0 < x && x <= m && 0 < y && y <= n
 
canGoFrom :: BoardSpec -> Point -> [Point]
canGoFrom b pos = filter (validPos b) . map (pos <+>) $ knightMoves

Ce code est propre et je suis sûr que je le comprendrais instantanément si j'y revient plus tard. (Il est également immédiatement traduisible en OCaml modulo de toutes petites différences de syntaxe)

La fonction finale ne sera pas plus compliquée.

--
Jedaï

**elishac** · 29/04/2008, 19h08

Avant tout, merci d'avoir répondu.

Envoyé par Jedai

Pourquoi ? Pourquoi s'imposer cette complication supplémentaire alors que tu pourrais te contenter de faire un tableau 2D (une matrice), à la fois plus lisible et plus intuitive...

Ok, je vais le refaire en (i,j), si tu veux. Je me suis simplement dit que c'était peut-être plus pratique de nommer les cases ainsi, afin d'avoir un simple entier au lieu de couples d'entiers (plus compliqué, surtout quand on veut accéder à un élément du couple : il faut au moins 20 caractères, alors que c'est immédiat si c'est un entier), d'autant que le cavalier ne se déplace pas en ligne ou colonne, donc les (i,j) ne servent à rien. Bref, ma motivation pour faire comme ça, c'était que ce serait plus simple pour l'ordi, et que ça ne serait pas plus compliqué à programmer (voire même plus simple), une fois qu'on a bien compris le système. Mais il est vrai que je n'ai pas pensé au fait que d'autres aient besoin de lire les lignes de programmation.

Envoyé par Jedai

Ce n'est pas un algorithme "intelligent", c'est du simple backtracking sans aucune intelligence (mais c'est très suffisant pour le problème).

Je ne connaissais simplement pas le nom "backtracking" et c'est le terme qui m'est venu à l'esprit pour définir cette méthode.

Envoyé par Jedai

Il est relativement simple de rajouter ce tri après avoir fait la version naïve.

Je n'ai pas l'impression que ce le soit : ça veut dire que pour chaque case, doit en fait déjà connaitre les cases qui sont accessibles depuis cette case (autant garder ce calcul en mémoire, afin de ne pas refaire des millions de fois la même chose).

Envoyé par Jedai

(à propos d'un tableau qui donne les cases accessibles directement)
Optimisation prématurée, commence par calculer à chaque coup les cases accessibles, ensuite si ton algo est trop lent tu pourras essayer cette optimisation.

Je trouve qu'il est presque plus dur de le faire à chaque fois. Au moins on le fait une fois pour toutes, comme ça on est débarrassés, et puis ça améliore grandement la vitesse générale. Je préfère qu'on fasse comme ça, si ça te dérange pas (de toute façon, cet algorithme devra être créé, donc autant l'appliquer au début plutôt qu'à chaque tour de boucle).

Envoyé par Jedai

Et là apparaît l'une des raisons pour lesquelles je te conseillais de prendre une simple matrice et représenter tes mouvements et coordonnées par des paires d'entiers : le code que tu vas produire avec ta représentation va être difficile à lire et à écrire, et donc bien plus susceptible de contenir des fautes.
Quelle horreur... Penses-tu pouvoir relire ce code dans une semaine sans parler de dans quelques mois ?

Sépare les concepts, n'optimise pas prématurément, choisit une structure de donnée qui correspond bien au problème... KISS !!

C'est vrai que je trouvais mon idée compliquée, mais je ne voyais pas comment faire plus simple. En fait, mon idée n'est pas si compliquée que ça, c'est juste que c'est long de faire des tests pour 8 cases différentes, mais quand on regarde bien, c'est quasiment toujours la même chose.

Envoyé par Jedai

Exemple en Haskell :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type BoardSpec = (Int,Int)
type Point = (Int,Int)
 
-- add a move to a position
(<+>) :: Point -> Point -> Point
(x,y) <+> (mx,my) = (x+mx,y+my)
 
knightMoves :: [Point]
knightMoves = [(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)]
 
validPos :: BoardSpec -> Point -> Bool
validPos (m,n) (x,y) = 0 < x && x <= m && 0 < y && y <= n
 
canGoFrom :: BoardSpec -> Point -> [Point]
canGoFrom b pos = filter (validPos b) . map (pos <+>) $ knightMoves

Je ne peux pas commenter cela car je ne comprends rien. Ecris le en CamL, éventuellement. (est-ce que dans ce code tu testes les problèmes de bord ?).

Bon, en conclusion, qu'est-ce que je dois faire maintenant ?
Quelle fonction dois-je créer, fonction qui fait quoi, etc. ?

**Sve@r** · 29/04/2008, 19h55

Envoyé par elishac

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
let cases_accessibles = make_vect p [];;
for c=1 to p do
	let tmp=ref [] in
		let boolean=((c-1) mod n) + 2 - n <0 in
			let case_potentielle=c+2+m in
				if boolean && (case_potentielle <= p) then tmp:= case_potentielle :: (!tmp);
			let case_potentielle=c+2-m in
				if boolean && (case_potentielle >= 1) then tmp:= case_potentielle :: (!tmp);
		let boolean=((c-1) mod n) + 1 - n <0 in
			let case_potentielle=c+1+2m in
				if boolean && (case_potentielle <= p) then tmp:= case_potentielle :: (!tmp);
			let case_potentielle=c+1-2m in
				if boolean && (case_potentielle >= 1) then tmp:= case_potentielle :: (!tmp);
		let boolean=(c-1) mod n >0 in
			let case_potentielle=c-1+2m in
				if boolean && (case_potentielle <= p) then tmp:= case_potentielle :: (!tmp);
			let case_potentielle=c-1-2m in
				if boolean && (case_potentielle >= 1) then tmp:= case_potentielle :: (!tmp);
		let boolean=((c-1) mod n) -1 >0 in
			let case_potentielle=c-2+m in
				if boolean && (case_potentielle <= p) then tmp:= case_potentielle :: (!tmp);
			let case_potentielle=c-2-m in
				if boolean && (case_potentielle >= 1) then tmp:= case_potentielle :: (!tmp);
	cases_accessibles.(c)<-!tmp
done;;

Je ne suis programmeur Caml mais si je devais le faire dans les langages que je connais (Python, C) je créerais un tableau de déplacement. Exemple en C

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct {
    int depX;
    int depY;
} t_depl;
...
t_depl tabDepl[]={
    {1, 2},
    {2, 1},
    {2, -1},
    {1, -2},
    {-1, -2},
    {-2, -1},
    {-2, 1},
    {-1, 2}
};

Ensuite pour tester une case ben je balaye mon tableau et je teste à chaque tour la case résultante du déplacement courant. Un seul corps de test au lieu d'en faire 8...

**Jedai** · 29/04/2008, 20h00

Envoyé par elishac

Je ne peux pas commenter cela car je ne comprends rien. Ecris le en CamL, éventuellement. (est-ce que dans ce code tu testes les problèmes de bord ?).

Tu ne comprends RIEN ? Inquiétant vu que la traduction en OCaml est pratiquement identique...
Et comme ça, ça va mieux :

Code OCaml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
let addMove (x,y) (mx,my) = (x+mx,y+my)
 
let knightMoves = [(1,2);(1,-2);(-1,2);(-1,-2);(2,1);(2,-1);(-2,1);(-2,-1)]
 
let validPos (m,n) (x,y) = 0 < x && x <= m && 0 < y && y <= n
 
let canGoFrom board pos = List.filter (validPos board) (List.map (addMove pos) knightMoves)

--
Jedaï

**elishac** · 29/04/2008, 20h18

Sve@r, merci beaucoup pour ta participation, mais je suis désolé, j'ai rien capté (je connais pas un mot sur deux, parmi les termes que tu utilises, et je ne sais pas encore programmer avec autre chose que Caml, donc j'ai pas compris ton code), c'est tro cho pour moi ce que tu racontes, je crois (peut-être quelqu'un peut-il me traduire ce qu'il a dit ?).

Jedai, merci d'avoir traduit, mais peux-tu traduire encore un peu plus ? (ce que j'utilises en fait c'est Caml light, donc je connais pas list.filter ni list.map (et d'ailleurs j'ai un peu de mal à comprendre ce que fait la fonction map, si c'est de ça que tu veux parler)).

**Sve@r** · 29/04/2008, 22h20

Envoyé par elishac

Sve@r, merci beaucoup pour ta participation, mais je suis désolé, j'ai rien capté (je connais pas un mot sur deux, parmi les termes que tu utilises, et je ne sais pas encore programmer avec autre chose que Caml, donc j'ai pas compris ton code)

Ben en fait, au lieu de coder les 8 déplacements "en dur" de cette façon
- déplacement n° 1 (2 vers le haut et 1 à droite + test si la case est libre)
- déplacement n° 2 (1 vers le haut et 2 à droite + test identique)
- déplacement n° 3 (1 vers bas et 2 à droite + test identique)
etc...

Je définis un tableau de couples de déplacements contenant l'ensemble de ces valeurs (2, 1), (1, 2), (-1, 2), ... et ensuite, je boucle sur chaque couple et je calcule le déplacement en utilisant les valeurs du couple en cours. Un seul bloc de code avec un seul test à programmer mais ce bloc sera exécuté 8 fois avec à chaque fois un déplacement différent...

Et dans son code

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

let knightMoves = [(1,2);(1,-2);(-1,2);(-1,-2);(2,1);(2,-1);(-2,1);(-2,-1)]

Jedai fait pareil....

Envoyé par elishac

(et d'ailleurs j'ai un peu de mal à comprendre ce que fait la fonction map, si c'est de ça que tu veux parler)).

En Python (et je suppute que c'est pareil en Caml), la fonction "map" permet d'appliquer une fonction quelconque (c'est toi qui indique la fonction) à chaque élément d'un tableau.

Plutôt que de faire
- boucle sur chaque élément[i] du tableau
- exécution de la fonction "xxx" en lui passant en paramètre l'élément [i]
Tu peux faire un truc qui ressemble à ça

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

map(tableau, xxx)

Et là, la fonction "xxx" (qui peut être une fonction standard ou bien une fonction créée par toi) sera appliquée sur chaque élément [i] du tableau. Un gadget en quelque sortes...

**Jedai** · 29/04/2008, 22h29

Envoyé par Sve@r

Un gadget en quelque sortes...

Oh non, pas un gadget, map est bien plus concis et expressif que les simples boucles pour tout une catégorie de tâches.
Et tu as oublié une différence fondamentale entre map et une boucle : map renvoie une liste des résultats de la fonction appliquée à chaque élément de la boucle d'entrée.

Exemple :

Code OCaml :

Sélectionner tout - Visualiser dans une fenêtre à part

let doubleListe = map (fun x -> x * 2)

Est une fonction qui prend une liste d'entiers et renvoie une liste où tous les éléments ont été multiplié par 2 :

Code OCaml :

Sélectionner tout - Visualiser dans une fenêtre à part

doubleListe [1;10;5]

renvoie [2;20;10].

map est une fonction fondamentale en programmation fonctionnelle... Où exactement as-tu appris Caml, elishac ? (Et le fait que ce soit Caml Light n'y change rien) Tu as un style affreusement impératif...

--
Jedaï

alex_pi · 30/04/2008, 01h51

Envoyé par Jedai

Où exactement as-tu appris Caml, elishac ? (Et le fait que ce soit Caml Light n'y change rien) Tu as un style affreusement impératif...

C'est triste à dire, mais j'ai collé (fais passer des TDs) toute l'année en spé, et ils codaient tous comme ça

J'ai tenté de nombreuses fois de leur faire comprendre que programmer en Caml, ce n'est pas programmer en C avec une syntaxe ideuse, mais je crois que beaucoup de profs d'infos en prépas se sont recyclé depuis Pascal et n'ont pas bien compris que la différence entre les deux langages n'était pas simplement une question de syntaxe, mais bien un gros changement de paradigme, et qu'il fallait revoir sa façon d'enseigner la programmation. Mais bon, je ne désespère pas qu'un jour, la programmation fonctionnelle prendra le dessus dans la plupart des applications! (avant qu'on ne me jette des pierres, je ne dis pas qu'elle doit remplacer l'impératif partout, juste presque partout :-p)

**elishac** · 30/04/2008, 06h47

Oui, je suis en prépa.
J'ai compris l'utilisation de map, je crois, bien qu'on ne l'utilise jamais, nous.
Sinon, que veulent dire list.filter et list.map en caml light ?
Et qu'est-ce que je dois faire à présent pour continuer mon programme ?

alex_pi · 30/04/2008, 09h28

Je suppose que tu es en sup :-) Sinon il serait assez déraisonnable de "perdre" ton temps à faire ce genre de programmes en ce moment !

Sinon, malheureusement, il semble que la fonction filter n'existe pas de base en camllight, à en croire la doc

Elle peut s'écrire assez facilement

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
let rec filter p = function
  | [] -> []
  | t::q when p t -> t::(filter p q)
  | t::q -> filter p q;;
 
val filter : ('a -> bool) -> 'a list -> 'a list

C'est donc simplement la fonction qui dans une liste ne garde que les élément satisfaisant un prédicat ou une propriété

La syntaxe Foo.bar est la syntaxe OCaml pour acceder à la fonction bar du module Foo. C'est un peu l'équivalent de foo__bar en camllight.

Je n'ai en revanche toujours pas compris pourquoi l'éducation nationale ne s'est pas décidée à enfin passer à OCaml dans son enseignement en prépa, histoire que l'on puisse tenter de convaincre les élèves que, si si, c'est un vrai langage et que l'on peut faire des vrais choses avec...

**elishac** · 30/04/2008, 22h52

Et qu'est-ce que je dois faire à présent pour continuer mon programme ?

**Saint_Louis** · 01/05/2008, 12h58

Le problème du cavalier est un problème de parcours de graphe. Il se traite facilement en Caml.
Comme le nombre de coups est déterminé à l'avance, le mieux est d'explorer le graphe en hauteur pour trouver la première solution.
Pour cela, définir une exception semble la méthode la plus simple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

exception echec;;

Je te propose un shéma:
Au depart, l'échiquier représenté par une matrice n,n est rempli de zéros.
Toute case déjà occupée par le cavalier prendra la valeur du nombre de coups qu'il a fallu
pour l'atteindre (en commençant par 1).
Pour simplifier, on peut supposer t.(0).(0)=1 et aussi par raison de symétrie t.(2).(1)=2.
On fait alors comme si on était au milieu du parcours et qu'on était en position (p,q) et qu'on avait
déjà avancé de k coups.
On définit deux fonctions:
La première a comme paramètre la position (p,q) et l'échiquier,
#bonvoisin : int * int -> int vect vect -> (int * int) list = <fun>
Elle renvoie la liste des successeurs possibles (c'est à dire les (x,y) atteignables en partant de (p,q);
il y a deux contraintes: rester dans l'échiquier et t.(x).(y)=0)
puis une fonction récursive avance qui a comme paramétre
k , (p,q) , la matrice échiquier, et enfin la liste L des suivants de (p,q).
#avance :
int -> int * int -> int vect vect -> (int * int) list -> int vect vect <fun>
Cette fonction renvoie la matrice modifiée mais on aurait pu lui faire renvoyer le type unit.
La fonction avance doit filtrer:
si L est vide avec k=n*n, on renvoie la matrice gagnante qu'il faut ensuite traiter pour obtenir le parcours.
sinon si L est vide, on a échoué: raise echec
sinon avec L=((x,y)::q), on exécute

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
try avance (k+1) (x,y) t (bonvoisin (x,y) t) 
with  echec ->begin  t.(x).(y) <- 0; avance k (p,q) t (tl L); end ;;

On lancera le programme avec:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

avance 2 (2,1) t (bonvoisin (2,1) t);;

On peut compliquer (un peu) le problème en imposant que le dernier coup puisse lui permettre de revenir à la case départ (cavalier rentrant).

Le tour du cavalier

Caml

Discussions similaires

Partager

Partager