Kadane's Algorithm

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('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;
    }

https://cdnjs.cloudflare.com/ajax/libs/d3/4.2.2/d3.min.js