scribbledecobble: Tweedle Sum and Tweedle D

README

Code

<pre>
/** Tweedle Sum and Tweedle D
 *    agreed to divide and conquer.
 *  For Tweedle Sum, said Tweedle D,
 *    had digits galore to tronquer.
 *
 *  Just then flew down a monstrous row
 *    that went to who knows where.
 *  Since it threatened the stack to overflow,
 *    they quit their quarrel with roundoff error.
 */
</pre>

<p>
<button id="rand-num">Random Number</button>
<button id="one-third">1/3</button>
</p>
<p>
<button id="m-sort">Merge Sort</button>
<button id="i-sort">Insertion Sort</button>
<button id="get-max">Get Max</button>
</p>
<p>
<button id="sum1-nums">Sum1</button>
<button id="sum2-nums">Sum2</button>
<button id="sum3-nums">Sum3</button>
</p>
<p>
<button id="clear-seq">Clear Sequence</button>
<button id="clear-set">Clear Set</button>
<button id="clear-sum">Clear Values</button>
</p>

<h1>Computed Values</h1>
<ul id="v-list">
</ul>

<h1>Sorted Sequence</h1>
<ol id="o-list">
</ol>

<h1>Unsorted Set</h1>
<ul id="u-list">
</ul>

<script>

/** DIVIDE AND CONQUER STRATEGY A
 *
 *  Divide the problem into two smaller problems of
 *  unequal size: a base case and another possibly much
 *  larger case. Solve the two problems independently
 *  and then combine the solutions to obtain a solution
 *  to the original problem.
 */

// TACTIC: Divide lopsidedly and loop.

function divLopLoop(a, i, j, f) {
  let ans, x, y;
  ans = a(j);
  while (j > i) {
    j = j - 1;
    let x = a(j);
    let y = ans;
    ans = f(x, y);
  }
  return ans;
}

// TACTIC: Divide lopsidedly and recurse.

function divLopRecurse(a, i, j, f) {
  let ans, x, y;
  ans = a(j);
  if (j > i) {
    x = divLopRecurse(a, i, j - 1, f);
    y = ans;
    ans = f(x, y);
  }
  return ans;
}

/** DIVIDE AND CONQUER STRATEGY B
 *
 *  Divide the problem into two smaller problems of
 *  roughly equal size: one of the two problems will
 *  be at most one unit larger than the other. Solve
 *  the two problems independently and then combine
 *  the solutions to obtain a solution to the original
 *  problem.
 */

// TACTIC: Divide evenly and recurse.

function divRecurse(a, i, j, f) {
  let ans, x, y, n, m;
  if (j > i) {
    n = i + Math.floor((j - i)/2),
    m = n + 1,
    x = divRecurse(a, i, n, f),
    y = divRecurse(a, m, j, f);
    ans = f(x, y);
  }
  else {
    ans = a(i);
  }
  return ans;
}

/* Basic functions. */

function basicCompare(x, y) {
  if (x < y ) {
    return -1;
  }
  else if (x > y) {
    return 1;
  }
  else {
    return 0;
  }
}

function add(x, y) {
  return x + y;
}

function multiply(x, y) {
  return x * y;
}

function getMax(x, y, compare) {
  return compare(x, y) > 0 ? x : y;
}

function getMin(x, y, compare) {
  return compare(x, y) < 0 ? x : y;
}

function merge(x, y, compare) {
  let z = [];
  while (x.length > 0 && y.length > 0) {
    z.push(compare(x[0], y[0]) < 0 ?
        x.shift() : y.shift());
  }
  while (x.length > 0) {
    z.push(x.shift());
  }
  while (y.length > 0) {
    z.push(y.shift());
  }
  return z;
}

function insert(x, y, compare) {
  while (x.length > 0) {
    let val = x.shift(),
        i = undefined;
    for (i = 0; i < y.length; i++) {
      if (compare(val, y[i]) < 0) {
        break;
      }
    }
    y.splice(i, 0, val);
  }
  return y;
}

/* Templates for solving classes of problems. */

function computeValue(values, operation, conquer) {
  const i = 0,
        j = values.length - 1,
        f = operation,
        a = function(index) {
          return values[index];
        };
  return conquer(a, i, j, f);
}

function findValue(values, compare, select, conquer) {
  if (compare === undefined) {
    compare = basicCompare;
  }
  const i = 0,
        j = values.length - 1,
        a = function(index) {
          return values[index];
        },
        f = function(x, y) {
          return select(x, y, compare);
        };
  return conquer(a, i, j, f);
}

function sort(values, compare, combine, conquer) {
  if (compare === undefined) {
    compare = basicCompare;
  }
  const i = 0,
        j = values.length - 1,
        a = function(index) {
          return [values[index]];
        },
        f = function(x, y) {
          return combine(x, y, compare);
        };
  return conquer(a, i, j, f);
}

/* Functions that operate on a sequence of values. */

function sum(values) {
  return sum1(values);
}

function sum1(values) {
  return computeValue(values, add, divRecurse);
}

function sum2(values) {
  return computeValue(values, add, divLopRecurse);
}

function sum3(values) {
  return computeValue(values, add, divLopLoop);
}

function prod(values) {
  return computeValue(values, multiply, divRecurse);
}

function max(values, compare) {
  return findValue(values, compare, getMax, divLopLoop);
}

function min(values, compare) {
  return findValue(values, compare, getMin, divLopLoop);
}

function mergeSort(values, compare) {
  return sort(values, compare, merge, divRecurse);
}

function insertionSort(values, compare) {
  return sort(values, compare, insert, divLopRecurse);
}

// DEMONSTRATION

const uList = document.getElementById("u-list");
const oList = document.getElementById("o-list");
const vList = document.getElementById("v-list");

const randNumB = document.getElementById("rand-num");
const oneThirdB = document.getElementById("one-third");

const mSortB = document.getElementById("m-sort");
const iSortB = document.getElementById("i-sort");
const getMaxB = document.getElementById("get-max");

const clearValB = document.getElementById("clear-sum");
const clearSeqB = document.getElementById("clear-seq");
const clearSetB = document.getElementById("clear-set");

const sum1NumsB = document.getElementById("sum1-nums");
const sum2NumsB = document.getElementById("sum2-nums");
const sum3NumsB = document.getElementById("sum3-nums");

function compareTextAsFloat(node1, node2) {
  let x, y;
  x = parseFloat(node1.textContent),
  y = parseFloat(node2.textContent);
  return basicCompare(x, y);
}

function appendTo(list, nodes) {
  while (items.length > 0) {
    list.appendChild(nodes.shift());
  }
}

function clear(list) {
  while (list.children.length > 0) {
    list.removeChild(list.children[0]);
  }
}

randNumB.addEventListener("click", function() {
  const element = document.createElement("li");
  element.textContent = Math.random();
  appendTo(uList, [element]);
});

oneThirdB.addEventListener("click", function() {
  const element = document.createElement("li");
  element.textContent = 1/3;
  appendTo(uList, [element]);
});

mSortB.addEventListener("click", function() {
  const items = mergeSort(uList.children, compareTextAsFloat) 
  appendTo(oList, items);
});

iSortB.addEventListener("click", function() {
  const items = insertionSort(uList.children, compareTextAsFloat) 
  appendTo(oList, items);
});

getMaxB.addEventListener("click", function() {
  const items = [ max(uList.children, compareTextAsFloat) ]; 
  appendTo(oList, items);
});

function sumNums(sumFunc) {
  const values = [];
  for (let i = 0; i < uList.children.length; i++) {
    values.push(parseFloat(uList.children[i].textContent));
  }
  const element = document.createElement("li");
  element.textContent = sumFunc(values);
  appendTo(vList, [element]);
}

sum1NumsB.addEventListener("click", function() {
  sumNums(sum1);
});
sum2NumsB.addEventListener("click", function() {
  sumNums(sum2);
});
sum3NumsB.addEventListener("click", function() {
  sumNums(sum3);
});

clearSeqB.addEventListener("click", function() {
  clear(oList);
});

clearSetB.addEventListener("click", function() {
  clear(uList);
});

clearValB.addEventListener("click", function() {
  clear(vList);
});
</script>

/** Tweedle Sum and Tweedle D
 *    agreed to divide and conquer.
 *  For Tweedle Sum, said Tweedle D,
 *    had digits galore to tronquer.
 *
 *  Just then flew down a monstrous row
 *    that went to who knows where.
 *  Since it threatened the stack to overflow,
 *    they quit their quarrel with roundoff error.
 */

function getArrayOfValues(seq) {
  return Object.values(seq);
}

function countItems(a) {
  return a.length;
}

function getItemAtIndex(a, i) {
  return a[i];
}

function getItemAtIndexAsArray(a, i) {
  return [ a[i] ];
}

function getSelf(x) {
  return x;
}

function getArrayOfSelf(x) {
  return [x];
}

function conquer(a, i, j, technique, baseCase) {
  const n = j - i;
  if (n < 0) {
    return conquer(a, j, i, technique);
  }
  else if (i < 0 || j >= a.length) {
    throw Error("Index out of range.");
  }
  else if (n > 0) {
    return technique(n);
  }
  else {
    return baseCase(a[i]);
  }
}

function divideAndConquer(a, i, j, f, baseCase) {
  function technique(n) {
    const m1 = Math.floor(i + n/2),
          m2 = m1 + 1,
          x = divideAndConquer(a, i, m1, f, baseCase),
          y = divideAndConquer(a, m2, j, f, baseCase);
    return f(x, y);
  }
  return conquer(a, i, j, technique, baseCase);
}

function gt3DivAndConquerElseLoop(a, i, j, f, baseCase) {
  function technique(n) {
    if (n > 3) {
      const m1 = Math.floor(i + n/2),
            m2 = m1 + 1,
            x = divideAndConquer(a, i, m1, f, baseCase),
            y = divideAndConquer(a, m2, j, f, baseCase);
      return f(x, y);
    }
    else {
      return loopAndConquer(a, i, j, f, baseCase);
    }
  }
  return conquer(a, i, j, technique, baseCase);
}

function lopAndConquer(a, i, j, f, baseCase) {
  function technique(n) {
    const x = a[i],
          y = lopAndConquer(a, i + 1, j, f, baseCase);
    return f(x, y);
  }
  return conquer(a, i, j, technique, baseCase);
}

function loopAndConquer(a, i, j, f, baseCase) {
  function technique(n) {
    let y = baseCase(a[j]);
    for (let k = j - 1; i <= k; k--) {
      let x = baseCase(a[k]);
      y = f(x, y);
    }
    return y;
  }
  return conquer(a, i, j, technique, baseCase);
}

function comparePair(x, y) {
  if (x < y) {
    return -1;
  }
  else if (x > y) {
    return 1;
  }
  else {
    return 0;
  }
};

function mergeSortedArrays(a1, a2, compare) {
  let a3 = [];
  while(a1.length > 0 && a2.length > 0) {
    if (compare(a1[0], a2[0]) < 0) {
      a3.push(a1.shift());
    }
    else {
      a3.push(a2.shift());
    }
  }
  while(a1.length > 0) {
    a3.push(a1.shift());
  }
  while(a2.length > 0) {
    a3.push(a2.shift());
  }
  return a3;
}

function sum(seq, i, j, strategy, add) {

  const a = getArrayOfValues(seq);
  const f = function(x, y) {
    return add(x, y);
  };

  if (i == undefined) {
    i = 0;
  }
  if (j === undefined) {
    j = a.length - 1;
  }
  if (strategy === undefined) {
    strategy = loopAndConquer;
  }
  if (add === undefined) {
    add = function(a, b) { return a + b; };
  }
  return strategy(a, i, j, f, getSelf);
}

function max(seq, i, j, strategy, compare) {

  const a = getArrayOfValues(seq);
  const f = function(x, y) {
    return compare(x, y) > 0 ? x : y;
  };

  if (i == undefined) {
    i = 0;
  }
  if (j === undefined) {
    j = a.length - 1;
  }
  if (strategy === undefined) {
    strategy = loopAndConquer;
  }
  if (compare === undefined) {
    compare = comparePair;
  }

  return strategy(a, i, j, f, getSelf);
}

function mergeSort(seq, i, j, strategy, compare) {

  const a = getArrayOfValues(seq);
  const f = function(x, y) {
    return mergeSortedArrays(x, y, compare);
  };

  if (i == undefined) {
    i = 0;
  }
  if (j === undefined) {
    j = a.length - 1;
  }
  if (strategy === undefined) {
    strategy = divideAndConquer;
  }
  if (compare === undefined) {
    compare = comparePair;
  }

  return strategy(a, i, j, f, getArrayOfSelf);
}

function avg(seq) {
  return sum(seq)/countItems(seq);
}

scribbledecobble

Pages

Tweedle Sum and Tweedle D

README

See also

Code