Skip to content

Instantly share code, notes, and snippets.

@jonsadka

jonsadka/.block

Last active September 18, 2016 17:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jonsadka/3d6b770b33ed18f622efcd9906d2c9a2 to your computer and use it in GitHub Desktop.
Save jonsadka/3d6b770b33ed18f622efcd9906d2c9a2 to your computer and use it in GitHub Desktop.
Download ZIP
Kadane's Algorithm
Raw
.block
license: mit
Raw
README.md
Raw
index.html
<!DOCTYPE html>
<head>
<meta charset="utf-8">
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/4.2.2/d3.min.js"></script>
<style>
* {
font-family: Sans-Serif;
font-weight: 300;
}
body {
margin:0;position:fixed;top:0;right:0;bottom:0;left:0;
background-color: #564b71;
}
.btn {
float: right;
box-sizing: border-box;
-webkit-appearance: none;
-moz-appearance: none;
appearance: none;
background-color: transparent;
border: 2px solid white;
border-radius: 0.6em;
color: white;
cursor: pointer;
display: inline-block;
-webkit-align-self: center;
-ms-flex-item-align: center;
align-self: center;
font-size: 1rem;
font-weight: 400;
line-height: 1;
margin: 20px 10px;
padding: 0.6em 1.4em;
text-decoration: none;
text-align: center;
text-transform: uppercase;
-webkit-transition: box-shadow 300ms ease-in-out, color 300ms ease-in-out;
transition: box-shadow 300ms ease-in-out, color 300ms ease-in-out;
}
.btn:hover, .btn:focus {
color: #564b71;
outline: 0;
box-shadow: 0 0 40px 40px white inset;
}
#status-text {
display: inline-block;
color: white;
font: 300 42px Helvetica Neue;
margin: 20px;
text-transform: uppercase;
opacity: 0.90;
}
</style>
</head>
<body>
<h1 id="status-text">Kadane's Algorithm</h1>
<button class="btn" onclick="removeLastValue()">Remove last</button>
<button class="btn" onclick="addValue()">Add value</button>
<script>
var Kadanes = function(array) {
var contigiousMax = Number.NEGATIVE_INFINITY;
var trailingSum = 0;
var contigiousIndexes = [];
var contigiousTrailingIndexes = [];
for(var index = 0; index < array.length; index++) {
// Add the new number to the current sum
trailingSum += array[index];
contigiousTrailingIndexes.push(index);
// Record as the largest sum if necessary
if (Math.max(contigiousMax, trailingSum) === trailingSum) {
contigiousIndexes = contigiousTrailingIndexes.slice();
}
contigiousMax = Math.max(contigiousMax, trailingSum);
// If negative, throw out earlier progress
// and consider intervals starting at this point
if(trailingSum < 0) {
trailingSum = 0;
contigiousTrailingIndexes = [];
}
}
return {
max: contigiousMax,
indexes: contigiousIndexes
}
};
</script>
<script>
var randomData = d3.range(8).map(function(){
return Math.round((Math.round(Math.random()) * 2 - 1) * Math.random()*222);
});
var WIDTH = window.innerWidth || 960;
var HEIGHT = (window.innerHeight || 500) - 91;
var MARGIN = 24;
var PADDING = 12;
var TIME = 400;
var svg = d3.select('body').append('svg')
.style('background-color', '#665A88')
.attr('width', WIDTH)
.attr('height', HEIGHT)
.append('g')
.attr('transform', 'translate(' + MARGIN + ',' + MARGIN + ')' )
var defs = svg.append('defs');
var filter = defs.append('filter')
.attr('id', 'inset-shadow')
.attr('x0', '-50%')
.attr('y0', '-50%')
.attr('width', '200%')
.attr('height', '200%')
filter.append('feGaussianBlur')
.attr('in', 'SourceAlpha')
.attr('stdDeviation', '4')
.attr('result', 'blur')
filter.append('feOffset')
.attr('dy', '2')
.attr('dx', '3')
filter.append('feComposite')
.attr('in2', 'SourceAlpha')
.attr('operator', 'arithmetic')
.attr('k2', '-1')
.attr('k3', '1')
.attr('result', 'shadowDiff')
filter.append('feFlood')
.attr('flood-color', '#444444')
.attr('flood-opacity', '0.75')
filter.append('feComposite')
.attr('in2', 'shadowDiff')
.attr('operator', 'in')
filter.append('feComposite')
.attr('in2', 'SourceGraphic')
.attr('operator', 'over')
.attr('result', 'firstfilter')
filter.append('feGaussianBlur')
.attr('in', 'firstfilter')
.attr('stdDeviation', '4')
.attr('result', 'blur2')
filter.append('feOffset')
.attr('dy', '-2')
.attr('dx', '-3')
filter.append('feComposite')
.attr('in2', 'firstfilter')
.attr('operator', 'arithmetic')
.attr('k2', '-1')
.attr('k3', '1')
.attr('result', 'shadowDiff')
filter.append('feFlood')
.attr('flood-color', '#444444')
.attr('flood-opacity', '0.75')
filter.append('feComposite')
.attr('in2', 'shadowDiff')
.attr('operator', 'in')
filter.append('feComposite')
.attr('in2', 'firstfilter')
.attr('operator', 'over')
var mappedResults = {};
randomData.forEach(function(d, i){
var time = i * TIME;
mappedResults[time] = Kadanes(randomData.slice(0, i + 1));
})
var indexCount = 0;
var intervalId = setInterval(function(){
var dataToPassIn = randomData.slice(0, indexCount + 1).map(function(value, index){
return {
index: index,
value: value
}
})
updateChart(svg, dataToPassIn, mappedResults);
indexCount++;
if (indexCount >= randomData.length) clearInterval(intervalId);
}, TIME)
function updateChart(svg, data, mappedResults){
var groups = svg.selectAll('.group-content')
.data(data, function(d, i){return d.index;});
var currentMappings = mappedResults[(data.length - 1 ) * TIME];
groupEnter = groups.enter().append('g')
.attr('class', 'group-content')
var tileCount = data.length;
var horizontalLimit = (WIDTH - 2 * MARGIN - tileCount * PADDING) / tileCount;
var verticalLimit = (HEIGHT - 2 * MARGIN - 3 * PADDING) / 3
var tileSize = Math.min(horizontalLimit, verticalLimit);
var maxCircleRadius = tileSize / 2;
var maxValue = d3.max(data, function(d){return Math.abs(d.value)});
groups.selectAll('.tile')
.transition()
.attr('x', function(d){return d.index * (tileSize + PADDING);})
.attr('y', MARGIN)
.attr('width', tileSize)
.attr('height', tileSize)
.attr('rx', tileSize / 10)
.attr('ry', tileSize / 10)
.attr('opacity', function(d){
var indexes = currentMappings.indexes;
if (indexes.indexOf(d.index) > -1) return 0.9;
return 0.08;
})
groupEnter.append('rect')
.attr('class', 'tile')
.attr('x', function(d){return d.index * (tileSize + PADDING);})
.attr('y', MARGIN)
.attr('width', tileSize)
.attr('height', tileSize)
.attr('rx', tileSize / 10)
.attr('ry', tileSize / 10)
.attr('stroke', '#665A88')
.attr('fill', 'white')
.attr('opacity', 0)
.transition()
.attr('opacity', function(d){
var indexes = currentMappings.indexes;
if (indexes.indexOf(d.index) > -1) return 0.9;
return 0.08;
})
groups.selectAll('.tile-text')
.transition()
.text(function(d){return d.value;})
.attr('x', function(d){return d.index * (tileSize + PADDING) + tileSize /2;})
.attr('y', MARGIN + 0.5 * tileSize)
.attr('font-size', tileSize / 3)
.attr('opacity', function(d){
var indexes = currentMappings.indexes;
if (indexes.indexOf(d.index) > -1) return 1;
return 0.50;
})
.attr('fill', function(d){
var indexes = currentMappings.indexes;
if (indexes.indexOf(d.index) > -1) return '#564B71';
return 'white';
})
groupEnter.append('text')
.text(function(d){return d.value;})
.attr('class', 'tile-text')
.attr('x', function(d){return d.index * (tileSize + PADDING) + tileSize /2;})
.attr('y', MARGIN + 0.5 * tileSize)
.attr('text-anchor', 'middle')
.attr('alignment-baseline', 'central')
.attr('font-size', tileSize / 3)
.attr('fill', function(d){
var indexes = currentMappings.indexes;
if (indexes.indexOf(d.index) > -1) return '#564B71';
return 'white';
})
.attr('opacity', 0)
.transition()
.attr('opacity', function(d){
var indexes = currentMappings.indexes;
if (indexes.indexOf(d.index) > -1) return 1;
return 0.50;
})
groups.selectAll('.circle-scale')
.transition()
.attr('cx', function(d){return d.index * (tileSize + PADDING) + maxCircleRadius;})
.attr('cy', HEIGHT - MARGIN)
.attr('r', function(d, i){
return Math.abs(d.value / maxValue) * 3 * maxCircleRadius;
})
groupEnter.append('circle')
.attr('class', 'circle-scale')
.attr('r', 0)
.attr('cx', function(d){return d.index * (tileSize + PADDING) + maxCircleRadius;})
.attr('cy', HEIGHT - MARGIN)
.attr('fill-opacity', 0.5)
.attr('fill', '#564B71')
.style('filter', function(d, i){
return 'url(#inset-shadow)';
})
.transition()
.attr('r', function(d, i){
return Math.abs(d.value / maxValue) * 3 * maxCircleRadius;
})
groups.selectAll('.circle-outline')
.transition()
.attr('cx', function(d){return d.index * (tileSize + PADDING) + maxCircleRadius;})
.attr('cy', HEIGHT - MARGIN)
.attr('r', function(d, i){
return Math.abs(d.value / maxValue) * 3 * maxCircleRadius;
})
groupEnter.append('circle')
.attr('class', 'circle-outline')
.attr('r', 0)
.attr('cx', function(d){return d.index * (tileSize + PADDING) + maxCircleRadius;})
.attr('cy', HEIGHT - MARGIN)
.attr('stroke-width', 3)
.attr('stroke', function(d, i){
if (d.value < 0) return '#EE3D63';
return '#81BC00'
})
.attr('fill', 'none')
.transition()
.attr('r', function(d, i){
return Math.abs(d.value / maxValue) * 3 * maxCircleRadius;
})
groups.exit().remove()
document.getElementById('status-text').classList.add('sum');
document.getElementById('status-text').innerHTML = 'Max contiguous sum ' + currentMappings.max;
}
function addValue(){
var newValue = Math.round((Math.round(Math.random()) * 2 - 1) * Math.random()*222);
randomData.push(newValue);
var dataToPassIn = randomData.map(function(value, index){
return {
index: index,
value: value
}
})
var mappedResults = {};
randomData.forEach(function(d, i){
var time = i * TIME;
mappedResults[time] = Kadanes(randomData.slice(0, i + 1));
})
updateChart(svg, dataToPassIn, mappedResults);
}
function removeLastValue(){
randomData.pop();
var dataToPassIn = randomData.map(function(value, index){
return {
index: index,
value: value
}
})
var mappedResults = {};
randomData.forEach(function(d, i){
var time = i * TIME;
mappedResults[time] = Kadanes(randomData.slice(0, i + 1));
})
updateChart(svg, dataToPassIn, mappedResults);
}
</script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment