yipo
5/11/2017 - 3:08 PM

flcs

flcs

index.html
content_copyfile_download
<!doctype html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title>flcs-js</title>
	<link rel="stylesheet" href="//netdna.bootstrapcdn.com/bootstrap/3.0.0/css/bootstrap.min.css">
	<link rel="stylesheet" href="flcs.css">
</head>
<body>
	<div class="container">
		<div>
			<form id="main" class="input-group">
				<span class="input-group-btn">
					<button id="rand" class="btn" type="button">Rand</button>
				</span>
				<input id="input" class="form-control" type="text">
				<span class="input-group-btn">
					<button id="go" class="btn btn-primary" type="submit">Go</button>
				</span>
			</form>
		</div>
		<div id="output">
			<table class="table table-bordered">
				<tbody id="display"></tbody>
			</table>
		</div>
	</div>
	<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>
	<script src="//netdna.bootstrapcdn.com/bootstrap/3.0.0/js/bootstrap.min.js"></script>
	<script src="//cdnjs.cloudflare.com/ajax/libs/d3/3.3.3/d3.min.js"></script>
	<script src="flcs.js"></script>
</body>
</html>
flcs.js
content_copyfile_download

function sfunc(sol) {
	return sol.s + 2*sol.u*sol.v/(1+sol.g) + sol.v*sol.v;
}

function intersect_wrap(a,b,match) {
	return match?intersect_match(a,b):intersect_gap(a,b);
}

function intersect_match(a,b) {
	var p=function(sol) {return 2*sol.u/(1+sol.g) + 2*sol.v;}
	var q=function(sol) {return sol.s + 2*sol.u*sol.v/(1+sol.g) + sol.v*sol.v;}
	var x=(q(b)-q(a)) / (p(a)-p(b));
	return Math.floor(x);
}

function intersect_gap(a,b) {
	var p=a.s-b.s;
	var q=p*(2+a.g+b.g)+2*a.u-2*b.u;
	var r=p*(1+a.g)*(1+b.g)+2*a.u*(1+b.g)-2*b.u*(1+a.g);
	var x=(-q+Math.sqrt(q*q-4*p*r)) / 2*p;
	return Math.floor(x);
}

function solution(gap) {
	this.s=0;
	this.t=Infinity;
	
	this.u=0;
	this.g=gap || 0;
	this.v=0;
	
	this.extend=function(match) {
		var sol=$.extend({},this);
		if (match) {
			sol.t--;
			sol.v++;
		} else if (this.v==0) {
			sol.t--;
			sol.g++;
		} else {
			sol.s=sfunc(sol);
			sol.u=sol.v;
			sol.g=1;
			sol.v=0;
		}
		return sol;
	}
}

function range(x,a,b) { // assume a<b
	if (x<=a) return -1;
	if (b<=x) return +1;
	return 0;
}

function insert(list,sol,match) {
	if (list.length<=0) {
		sol.t=Infinity;
		return [sol];
	}
	
	var p,q;
	var touch=false;
	var pfunc=function(sol) {
		return sfunc(match?sol:sol.extend(true));
	}
	var begin=function(i) {
		return (--i>=0)?list[i].t:(-1);
	}
	
	for (var i=0;i<list.length;i++) {
		var sfs=pfunc(sol);
		var sfi=pfunc(list[i]);
		if (sfs>=sfi) {
			p=i-1;
			q=i;
			if (sfs==sfi) {
				var sfse=pfunc(sol.extend(match));
				var sfie=pfunc(list[i].extend(match));
				if (sfse<=sfie) return list; // discard sol
				touch=true;
				q=i+1;
			}
			break;
		}
	}
	
	for (;p>=0;p--) {
		var t=intersect_wrap(sol,list[p],match);
		var r=isNaN(t)?(+1):range(t,begin(p),list[p].t);
		if (r<=0) touch=true;
		if (r==0) list[p].t=t;
		if (r>=0) break;
	}
	
	for (;q<list.length;q++) {
		var t=intersect_wrap(sol,list[q],match);
		var r=isNaN(t)?(+1):range(t,begin(q),list[q].t);
		if (r>=0) touch=true;
		if (r==0) sol.t=t; // otherwise, infinity by default.
		if (r<=0) {
			if (t>0) break;
			touch=true;
		}
	}
	
	return [].concat(
		list.slice(0,p+1),
		touch?sol:[],
		list.slice(q)
	);
}

function lattice(gap) {
	this.match=false;
	this.list=(gap!=undefined)?[new solution(gap)]:[];
	this.flcs=0;
}

function go_flcs(x,y) {
	var m=x.length;
	var n=y.length;
	
	var mat=[];
	for (var i=0;i<=m;i++) mat[i]=[new lattice(i)];
	for (var j=1;j<=n;j++) mat[0][j]=new lattice(j);
	
	for (var i=1;i<=m;i++) {
		for (var j=1;j<=n;j++) {
			go_lattice(mat,i,j,x[i-1]==y[j-1]);
		}
	}
	return mat;
}

function go_lattice(mat,i,j,match) {
	mat[i][j]=new lattice;
	mat[i][j].match=match;
	
	var yipo=function(match) {
		return function(k,sol) {
			mat[i][j].list=insert(mat[i][j].list,sol.extend(match),match);
		};
	};
	if (match) $.each(mat[i-1][j-1].list,yipo(true));
	$.each(mat[i-1][j].list,yipo(false));
	$.each(mat[i][j-1].list,yipo(false));
	
	if (match) {
		mat[i][j].flcs=sfunc(mat[i][j].list[0]);
	} else {
		mat[i][j].flcs=Math.max(mat[i-1][j].flcs,mat[i][j-1].flcs);
	}
}

function display(mat) {
	var tb=d3.select('#display').html(null);
	
	var tr=tb.selectAll('tr').data(mat)
		.enter().append('tr');
	
	var td=tr.selectAll('td').data(function(d) {return d})
		.enter().append('td').classed('match',function(d) {return d.match});
	td.append('div').classed('flcs',true).text(function(d) {return d.flcs.toFixed(2)});
	td.append('div').classed('list',true);
	
	var vec=function(x) {return '('+x.join(',')+')'};
	var inf=function(x) {return (x==Infinity)?'&infin;':x};
	
	var sol=td.select('div.list').selectAll('div').data(function(d) {return d.list})
		.enter().append('div').classed('sol',true)
			.html(function(d) {return vec([sfunc(d).toFixed(2),inf(d.t)])+' '+[d.u,d.g,d.v].join('-')});
}

function go() {
	var input=$('#input').val().split(' ');
	if (input.length!=2) return;
	var mat=go_flcs(input[0],input[1]);
	display(mat);
}

$('#main').submit(function() {
	go();
	return false;
});

function rand_range(a,b) {
	return a+Math.floor(Math.random()*(b-a));
}

function rand_str(set,len) {
	var str='';
	while (len--) str=str.concat(set.charAt(rand_range(0,set.length)));
	return str;
}

$('#rand').click(function() {
	var set='abc',a=12,b=16;
	$('#input').val([
		rand_str(set,rand_range(a,b)),
		rand_str(set,rand_range(a,b))
	].join(' '));
	go();
});
flcs.css
content_copyfile_download

.container {
	max-width: 100%;
}
.container>div {
	margin-top: 20px;
}

#display td {
	padding: 6px;
}
.match {
	background-color: hsl(90,60%,90%);
}
.sol {
	font-size: 10px;
	white-space: nowrap;
}