Built with blockbuilder.org
forked from jonsadka's block: Linked List
license: mit |
Built with blockbuilder.org
forked from jonsadka's block: Linked List
<!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> | |