function mini(a,b) { return (a<b)?a:b;}
function minimum(a,b,c) { return mini(a, mini(b, c));}

function distance(a, b) {
        var n = a.length, m = b.length, matrice = [];
	var cout,u,v,w;
        for(var i=-1; i < n; i++) {
                matrice[i]=[];
                matrice[i][-1]=i+1;
        }
        for(var j=-1; j < m; j++) {
                matrice[-1][j]=j+1;
        }
        for(var i=0; i < n; i++) {
                for(var j=0; j < m; j++) {
			cout = (a.charAt(i) == b.charAt(j))? 0 : 1;
			u=1+matrice[i][j-1]; v=1+matrice[i-1][j]; w=cout+matrice[i-1][j-1];
			matrice[i][j]=(u<v)?(u<w)?u:w:(v<w)?v:w;
                }
        }
        return matrice[n-1][m-1];
}

function cherche() {
	var s=""
	var tb=document.frm.ar.value.split(/\n+/g);
	for(var i=0; i<tb.length; i++) {
		var sep=" ";
		tb[i]=tb[i].replace(/\s+/g," ");
		tb[i]=tb[i].replace(/^\s+/g,"");
		var u;
		if(tb[i].search(/;/g)!=-1){
			sep = " ; "
			tb[i]=tb[i].replace(/\s*;\s*/g,";");
			tb[i]=tb[i].replace(/\s*,\s*/g,", ");
			u = tb[i].split(/;+/g);
		} else if(tb[i].search(/,/g)==-1){
			u = tb[i].split(/\s+/g);
		}else {
			sep = ", ";
			tb[i]=tb[i].replace(/\s*,\s*/g,",");
			u = tb[i].split(/,+/g);
		}
		if(u.length>=2) {
			s += u[0]+sep+u[1]+sep+"\t "+distance(u[0], u[1])+"\n";
		} 
	}
	document.frm.ar.value=s;
}

function efface() {
	document.frm.ar.value="";
}
function eff2() {
	document.frm2.t.value=""
	document.getElementById("res").innerHTML="";
	document.getElementById("commt").innerHTML="";
}

var mcur=null;

function matr() {
	document.getElementById("res").innerHTML="";
	var s=document.frm2.t.value;
	s=s.replace(/^\s+/,"")
	s=s.replace(/\s+$/,"")
	s=s.replace(/,+/g," ")
	s=s.replace(/;+/g," ")
	s=s.replace(/\s+/g," ")
	
	document.frm2.t.value=s.toLowerCase();
	s=s.toUpperCase();
	var tb=s.split(/\s+/g);
	if(tb.length<2) {

	} else {
		if(mcur!=null) delete mcur
		mcur=new trace(tb[0], tb[1]);
		var aff = mcur.affmatrice();
		document.getElementById("res").innerHTML=aff;
	}

}

function trace(a, b) {
	this.a=a;
	this.b=b;
        this.n = a.length, this.m = b.length, this.matrice = [];
	this.modif=[];
	this.mcols=[]
	var n=this.n, m=this.m
	this.s=null

        for(var i=-1; i < n; i++) {
                this.matrice[i]=[];
		this.modif[i]=[];
		this.mcols[i]=[];
		this.mcols[i][-1]=0
                this.matrice[i][-1]=i+1;
		this.modif[i][-1]="h";     // on vient du haut : suppression lettre du premier
        }
        for(var j=-1; j < m; j++) {
		this.mcols[-1][j]=0;
                this.matrice[-1][j]=j+1;
		this.modif[-1][j]="g"     // on vient de gauche : insertion lettre du second
        }
	
	var mode;
        for(var i=0; i < n; i++) {
                for(var j=0; j < m; j++) {
			this.mcols[i][j]=0;
                        var cout = (a.charAt(i) == b.charAt(j))? 0 : 1;
			var u = 1+this.matrice[i][j-1], v=1+this.matrice[i-1][j], w=cout+this.matrice[i-1][j-1];
		this.matrice[i][j] =(u<v)? (u<w)? u : w :(v<w)? v : w;
		
		if(w<u && w<v) {
			mode="w"
		} else if(w == u && w<v) {
			mode = (Math.random()<0.5)? "w":"u";
		} else if(w == v && w<u) {
			mode = (Math.random()<0.5)? "w":"v";
		} else if(u == v && u<w) {
			mode = (Math.random()<0.5)? "u":"v";
		} else if(u==v && v==w) {
			var mr=Math.random()
			mode = (mr<1/3) ? "u" : (mr<2/3)? "v" : "w";
		} else {
			mode = (u<v)? ((u<w)? "u" : "w") : ((v<w)? "v" : "w");
		}
		this.modif[i][j]= (mode=="u") ? "g" : ((mode=="v")? "h" : ((cout==0)? "0" : "1"));
                }
        }
	var ch="", chm="",x=n-1, y=m-1
	while(x>-1||y>-1) {
		this.mcols[x][y]=1;
		var md = this.modif[x][y], mm=this.matrice[x][y]
		ch = md+ch
		chm=mm+chm
		if(md=="g") {
			y--
			
		} else if(md=="h") {
			x--
		} else {
			x--;
			y--;
		}
		if(x>=-1 && y>=-1)
			this.mcols[x][y]=1;
	}
	
	x--
	y--
	//if(x>=-1 && y>=-1) this.mcols[x][y]=1;
	for( ; x>=-1; x--) this.mcols[x][y]=1;
	for( ;y>=-1; y--) this.mcols[x][y]=1;
	
        var x=0, y=0, ptch=0, mo=0
	var z, ccur=a;
	var tabmots=[]
	tabmots[0]=a;
	
	var stats=[0,0,0,0]
	for(i=0; i<ch.length;i++) {
		car=ch.charAt(i)
		if(car=="0") { // pas de changement
			x++; y++;mo++
			stats[0]++
		} else if(car == "1") { // change
			z=ccur.slice(0,mo)+b.charAt(y)+ccur.slice(mo+1)
			ccur=z
			tabmots.push(ccur)
			x++; y++;mo++
			stats[1]++
		}else if(car=="g") { // ajout
			z = ccur.slice(0,mo)+b.charAt(y)+ccur.slice(mo)
			y++;mo++
			ccur=z
			tabmots.push(ccur)
			stats[2]++
		}else if(car=="h") { // suppression
			z = ccur.slice(0,mo)+ccur.slice(mo+1)
			ccur=z
			tabmots.push(ccur)
			x++
			stats[3]++
		}
	}
	var rapport=""
	if(stats[0]==0) rapport +="Aucune lettre n'est restée incnangée.<br />"
	else if(stats[0]==1) rapport +="Une seule lettre est restée inchangée.<br />"
	else if(stats[0]>1) rapport += stats[0]+" lettres sont restées inchangées.<br />"
	if(stats[1]==1) rapport +="Une seule lettre a été changée en place.<br />"
	else if(stats[1]>1) rapport += stats[1]+" lettres ont été remplacées.<br />"
	if(stats[2]==1) rapport +="Une seule lettre a été ajoutée.<br />"
	else if(stats[2]>1) rapport += stats[2]+" lettres ont été ajoutées.<br />"
	if(stats[3]==1) rapport +="Une seule lettre a été retirée.<br />"
	else if(stats[3]>1) rapport += stats[3]+" lettres ont été retirées.<br />"
        var s  ='<br /><div  style="font-size:14px;font-weigth:bolder;font-family:courier,sans;color:#888;text-align:left;">'
	s += '<table border="0" ><tr><td>'
	for(i=0; i<tabmots.length;i++) {
		s += tabmots[i]+'<br />'
	}
	s += '</td><td style="padding:0 5 0 30;vertical-align:top;font-size:13px;color:#000">'+rapport+'</td></tr></table>'
	s+='</div>'
	s += '<center><table class="mat">'
                +'<tr class="mat"><td class="mat">&nbsp;</td><td class="mat">&nbsp;</td>'
        for(var j=0; j<m;j++) {
                s += '<td class="mat m0 b">' + b.charAt(j) + '</td>'
        }
        s += '</tr><tr class="mat"><td class="mat">&nbsp;</td>'
        for(var j=-1; j<m;j++) {
		var col= ((this.mcols[-1][j]==0)?' c ':' j ')
                s += '<td class="mat m1'+col +'">' + (j+1) + '</td>'
	}
	s += '</tr>'
	for(var i=0; i<n; i++) {
		var col=((this.mcols[i][-1]==0)?' c ':' j')
		s += '<tr><td class="mat m0 b">' + a.charAt(i) + '</td><td class="mat m1'+col+'">' + (i+1) + '</td>'
		for(var j=0; j<m; j++) {
			var classe='mat p '
			
			if(i==n-1 && j==m-1) {
				classe += "m2 j "
				//s += '<td class="mat m2 p" onmouseover="cmt('+i+','+j+')">'+this.matrice[i][j]+'</td>'
			} else {
				
				classe += ( (this.mcols[i][j]==1)? 'j ':'w ')
				//s += '<td class="mat p" onmouseover="cmt('+i+','+j+')">'+this.matrice[i][j]+'</td>'
			}
			s += '<td class="'+classe+'" onmouseover="cmt('+i+','+j+')">'+this.matrice[i][j]+'</td>'
		}
		s += '</tr>'
	}
	s += '</table>' + '</center>'

	this.s=s
	this.affmatrice = function() {
		return s;
	}
	this.comment = function(x, y) {
               if(x<0 || y<0 || x>=this.n || y>=this.m) return
                var u = this.a.charAt(x), v = this.b.charAt(y)
                var s = "Cette case est à l'intersection d'une ligne "+u+" et d'une colonne "+v+"<br />"
                var ndiag, ngauche, nhaut;
                if(u==v) {
                        ndiag=this.matrice[x-1][y-1]
                        s += "Comme "+u+"="+v+" le côut est 0. En lui ajoutant l'élément diagonal "+ndiag+" (plus haut et à gauche), le premier nombre calculé est "+ndiag+".<br />"
                } else {
                        ndiag=this.matrice[x-1][y-1]+1
                        s += "Comme "+u+" est différent de "+v+", le côut est 1. En lui ajoutant l'élément diagonal "+this.matrice[x-1][y-1]+", le premier nombre calculé est "+ndiag+".<br />"
                }
                ngauche=this.matrice[x][y-1]+1
                nhaut=this.matrice[x-1][y]+1
                s+="On ajoute 1 à l'élément "+this.matrice[x][y-1]+" de gauche, le second nombre est "+ngauche+"<br />"
                s+="On ajoute 1 à l'élément "+this.matrice[x-1][y]+" qui se trouve au-dessus, le troisième nombre est "+nhaut+"<br />"
                var nmin=minimum(ndiag,ngauche,nhaut)
                s +="La plus petite valeur des trois nombres "+ndiag+", "+ngauche+", "+nhaut+" est "+nmin+"<br />"
                s += "On inscrit donc "+nmin+" dans cette case.<br />"

                return s;
        }

}

function cmt(x, y) {
	var s = mcur.comment(x,y);
	document.getElementById("commt").innerHTML=s;
}
var exos=[
"avion aviron", "aviation avirons", "camions rations", "paragraphe orthographe","militaire sanitaire",
"militant militaire","arriviste archiviste","métro rétro","capitale capable","élixir élites",
"fontaine frontière","bordure ordure","pelouse pelote","voiture toiture","fraise braise","camion cation",
"prudent prudente","charrette chariot","calais balais","rasade salade","classe brasse","perdu duper",
"détourer dérouter","cahier cacher","argenter régenter","lièvre livre","buvard bavure","réveil veiller",
"balade ballade","quinze seize","trente tente","pentagone hexagone","orthogonal original","un nu",
"purger groupe","corbeille abeille","analyse catalyse","solitaire diamant","cadavres cadastre",
"sublimer subsister","découvrir recouvrir","univers ouvrier","ciment piment","glucose glucide",
"ludique pudique","moustique caustique","critique caustique","subsister résister",
"remplace remplace","grave priver","cascade embuscade","maussade moustache","bouteille embouchure",
"document orpiment","optique sceptique","assembleur assemblée","légende légion","rue route",
"comme crime","disponible pénibilité","goémon gnomon","dommage carnage","affliction affiliation",
"effectivement effacement","commencement aménagement","commissionnaire démissionner",
"capitaine croquemitaine","personne sonnerie","toutefois tournois","comprirent compromis",
"abondamment boniment","espagnolette campagnols","horloge logement","faiblesse diablesse"
];

var motssimples=["assurément","suspense","médiatique","télévision","cinéma","mondiaux",
"spielberg","stupéfait","mcworld","cacahuètes","éliminer","interactif","gamin","consommateur",
"politique","moderne","magistrale","ethnologie","sociale","campagne","promotionnelle","différence",
"france","espagne","italie","grèce","village","bombarde","britannique","anglais","habitant",
"identité","international","secteur","tertiaire","hybride","étrange","milliards","bizarre",
"express","concernant","mesure","espace","impossibilité","gödel","système","récursive",
"transcendance","argument","contredire","vulnérable","phrase","anomalie","complexe","langue",
"iceberg","séquence","contexte","mécanisme","linguistique","exception","ribosome","musique",
"bijou","attrait","chanson","pythagore","achille","rapidement","calculatrice","algorithme",
"étape","aisance","nombre","manipuler","dompté","professeur","européen","rapport","taille",
"théorème","démonstration","recherche","semblable","ambiguïté","ingéniosité","stratégie",
"atteindre","subtile","soin","idée","sous","objectif","principal","part","lecteur","niveau",
"prédicat","produire","meilleur","toujours","jamais","train","incité","automatisé","aiguillé"
];


for(var i =0; i<exos.length; i++) {
	var a=exos[i].split(/\s/g)
	if(a.length==2) {
	motssimples.push(a[0])
	motssimples.push(a[1])
	}
}

function motauhasard() {
	var m = motssimples[Math.floor(motssimples.length*Math.random())]
	document.frm3.t.value=m
	trouve();
}

/*
// utilisé pour vérifier la liste de mots
var veriftb=[]
for(var i=0; i<motssimples.length;i++) {
        var u = motssimples[i]
        if (veriftb[u]==null) veriftb[u]=1*0
        veriftb[u]++
}
var sver=""
for(x in veriftb) {
        if(veriftb[x]>1) sver += x+" "+veriftb[x]+"\n"
}
alert(sver)
*/
//Math.srandom();

function alea() {
	//eff2();
	if(Math.random()<0.8) {
		document.frm2.t.value=exos[Math.floor(exos.length*Math.random())];
	} else {
		document.frm2.t.value=motssimples[Math.floor(motssimples.length*Math.random())]+
		" "+motssimples[Math.floor(motssimples.length*Math.random())];
	}
	matr();	
	document.getElementById("commt").innerHTML="";
}