Theorem∎ X Cris September 7 2019 Test

README.md

How to run this program?

Download the 3 files: index.html, flatten.js, and tests.js into 1 directory and open index.html with a web browser.

Open the JavaScript console to see test output.

flatten.js

export default function flatten(arr) {
  // type checking and edge cases
    /**
      Iterable input types

      We could include a check for iterables here
      (things that can be iterated like (for const item of list))
      to extend this function to handle more input types,
      and one way is to check it conforms to iteratable protocol
      and has the Symbol.iterator function slot,
      and for simplicity I omit that.
    **/
    if ( ! Array.isArray(arr) ) {
      /**
        Type checking

        We could choose to simply return [] here
        and swallow any error, but if we are explicit
        then we can see when our function is not getting
        the argument types we expect it to.
      **/
      throw new TypeError(`function flatten expects 1 argument of type Array`);
    }

    if ( arr.length == 0 ) {
      // return a new array instead of mutate old one
      return [];
    }

  /*
    Approach like a tree

    Nested arrays are equal to trees, with the array
    members being branch nodes and the non-array members
    being leaf nodes.

    We want all the leaf nodes, in some order.

    The easiest traversal is where we push any branch
    nodes onto a queue, and loop until the queue is empty,
    which is why I chose it.

    A LIFO queue, or stack, gives depth first, while
    a FIFO queue gives breadth first.

    Depth first gives the correct left-to-right order, so I chose it.

    After investigating I believe the complexity is O(k+n), where
    k is the number of arrays and n is the number of numbers,
    in other words one step for each node in the "tree".
  */

  // variable declaration

  const leaves = [];
  const stack = [];

  // setup

  stack.push(arr);

  // main flatten loop

  while( stack.length ) {
    // How does it work?
      // uncomment the following line to inspect the algorithm progress:
      // console.log(JSON.stringify(stack));

    const next = stack.pop();

    if ( Array.isArray(next) ) {
      stack.push(...next);
    } else if ( Number.isInteger(next) ) {
      // we process input end-first so unshift to get correct order:
      leaves.unshift(next);
    } else {
      // if it's not an array or an integer, we ignore it
    }
  }

  return leaves;
}

index.html

<meta charset=utf-8>
<meta name=viewport content="width=device-width, initial-scale=1.0">
<title>Theorem&#x220e;</title>
<h1>Theorem&#x220e; Test</h1>
<style>
  main {
    margin: 0 auto;
    max-width: 777px;
  }

  blockquote {
    font-family: monospace;
  }
</style>
<main>
  <dl>
    <dt>Candidate
    <dd>Cris Stringfellow
    <dt>Date
    <dd><time datetime=2019-09-07>September 7, 2019</time>
    <dt>Task
    <dd>
      <blockquote
          cite=https://theorem.applytojob.com/questionnaire/55e9bb9657b1d/prospect_20190905092917_RDOMQCKKXTWE8OZU/projob_20190905092917_31GJ2NT9WR4SCYJP
      >
        <p>
          Write some code, that will flatten an array of arbitrarily nested arrays of integers into a flat array of integers. e.g. [[1,2,[3]],4] -> [1,2,3,4].
        <p>
          Your solution should be a link to a gist on gist.github.com with your implementation.
        <p>
          When writing this code, you can use any language you're comfortable with. The code must be well tested and documented. Please include unit tests and any documentation you feel is necessary. In general, treat the quality of the code as if it was ready to ship to production.
        <p>
          Try to avoid using language defined methods like Ruby's Array#flatten.
      </blockquote>
    </dd>
    <dt>Self-test result
    <dd>Passes all 5 tests
    <dt>Time to complete
    <dd>~ approximately 1 hour
    <dt>Link to GitHub gist:
    <dd><a target=_blank href=https://gist.github.com/crislin2046/1bde3adc5655f4072c0ec2e92acfb30d>gist</a>
    <dt>Embedded gist:
    <dd>
      <hr>
      <script src="https://gist.github.com/crislin2046/1bde3adc5655f4072c0ec2e92acfb30d.js"></script>
      <hr>
    </dd>
  </dl>
</main>
<script type=module>
  import {tests, run} from './tests.js';
  import flatten from './flatten.js';

  run(flatten, tests);
</script>

tests.js

export const tests = [
  {
    question: [[1,2,[3]],4],
    answer: [1,2,3,4]
  },
  {
    question: [[1,2], [[[3],[[4]]]], 5, 6, [[[7]]], 8, [9,[[10]],11], 12],
    answer: [1,2,3,4,5,6,7,8,9,10,11,12],
  },
  {
    question: [],
    answer: []
  },
  {
    question: [10, 9, 8, 7, [6,[5],[],[[]],4], [[],3], [], 2, 1],
    answer: [10,9,8,7,6,5,4,3,2,1]
  },
  {
    question: [[],['cris'],[[[[[[[[[[[[[[[[]]]]]], 'awesome' ]]]]], /because/]]]],[undefined]], [],[],[null, [[]],[], Symbol('ok?') ]],
    answer: []
  },
];

export function run(func, tests) {
  for( const {question, answer} of tests ) {
    const result = func(question);
    const score = equal(result, answer);
    console.log(`Test score: ${score ? 'pass' : 'fail'}`);
    console.log("Question", question);
    console.log("Correct answer", answer);
    console.log("Result obtained", result);
    console.log("\n");
  }
}

function equal(arr1, arr2) {
  if ( arr1.length !== arr2.length ) return false;

  for( let i = 0; i < arr1.length; i++) {
    if ( arr1[i] != arr2[i] ) return false;
  }

  return true;
}