Layout Engine (coding challenge)

layout-engine.js

/*
* Complete the function below.
*
* Sample input 1: ['10 0 0 I love monkeys.']
* Sample output 1 (dashes denote trailing spaces): 
* ---I love ---
* ---monkeys. -
*
* Sample input 2: ['10 0 0 I love monkeys.', '20 0 0 Good times and bad times.']
* Sample output 2 (dashes denote trailing spaces):
* It was the best of -
* ----I love ---times-
* it  monkeys. -was --
* the worst of times.-
*/
function layout(lines) {
  // grid is simulated with 2D array
  let grid = [[]];

  for (let i = 0; i < lines.length; i++) {
    const [meta, text] = separateMetaFromText(lines[i]);

    if (i === 0) grid = initEmptyGrid(meta);
    else grid = updateGridWidth(meta, grid);

    grid = layoutTextOnGrid(text, meta, grid);
  }
  // output to stdout on Hackerrank interface
  console.log(outputLayoutFromGrid(grid));
}

/**
 * ======================================
 * HELPER FUNCTIONS
 * ======================================
 */
// take a single input line (from "lines" arg)
// return an array with 2 args: [metaString, textString]
// sample singleLine value: '10 0 0 I love monkeys.'
function separateMetaFromText(singleLine) {
  // get index of third occurrence of ' ' that delimits meta from text
  let index = singleLine.indexOf(' ');
  let count = 1;
  while (count !== 3) {
    index = singleLine.indexOf(' ', index + 1);
    count++;
  }

  const meta = singleLine.substring(0, index);
  const text = singleLine.substring(index + 1);

  return [meta, text];
}

// return 2D array representing the layout, with `null` as default value
// sample metaString input: '20 1 2'
// format: width, x, y
function initEmptyGrid(metaString) {
  const [width, x, y] = extractMeta(metaString);

  // each row should have (width + x) cells to account for x offset
  const row = new Array(width + x).fill(null);

  const arbitraryBufferRows = 5;
  const emptyGrid = new Array(parseInt(y + arbitraryBufferRows, 10)).fill(row.map((slot) => slot));

  return emptyGrid;
}

// update grid with new meta (ie. width)
// only used for `lines` inputs with >1 length
function updateGridWidth(metaString, grid) {
  const [width, x, y] = extractMeta(metaString);
  const columnsToAdd = width + x - grid[0].length;

  if (columnsToAdd <= 0) return;

  return grid.map((row) => {
    return row.concat(new Array(columnsToAdd).fill(null));
  });
}

// return grid with full textString laid out onto grid
// sample textString: 'I love monkeys.'
// functional approach, does not modify grid directly
function layoutTextOnGrid(textString, metaString, grid) {
  const gridClone = grid.map((arr) => arr.slice());
  const words = textString.split(' ');
  const [, x, y] = extractMeta(metaString);

  let currentRowIndex = y;  // respect y offset
  let currentCellIndex = 0;
  let row = gridClone[currentRowIndex];

  let carryOverSpace = false;
  let lastInsertedCellIndex = 0;
  let isNewRow = true;

  words.forEach((word, index) => {
    const isLastWord = index === words.length - 1;
    isNewRow = false;

    let nextInsertCellIndex = indexOfNextInsertableCell(word, row, lastInsertedCellIndex);

    while (nextInsertCellIndex === -1) {
      currentRowIndex++;
      row = gridClone[currentRowIndex];
      nextInsertCellIndex = indexOfNextInsertableCell(word, row, 0);
      isNewRow = true;
    }

    currentCellIndex = nextInsertCellIndex;
    if (isNewRow || index === 0) currentCellIndex += x;  // respect x offset

    for (let i = 0; i < word.length; i++) {
      // can safely assume word length <= width (excluding x offset)
      const chr = word.charAt(i);

      if (carryOverSpace) {
        // add carried over space and reset flag to false
        row[currentCellIndex] = ' ';
        carryOverSpace = false;
        currentCellIndex++;
        continue;
      }
      // add character to current cell
      while (row[currentCellIndex] !== null) {
        currentCellIndex++;
      }
      row[currentCellIndex] = chr;
      currentCellIndex++;
    }
    lastInsertedCellIndex = currentCellIndex;

    // add space to end of line if a cell exists, else carry over to next row
    if (row[currentCellIndex] === undefined || isLastWord) carryOverSpace = true;
    else {
      row[currentCellIndex] = ' ';
      currentCellIndex++;
    }
  });

  return padWithTrailingSpaces(gridClone, metaString);
}

// check if cell with adjacent empty cells that can hold `word` exists
// if yes, return index of first occurrence
// else, return -1
function indexOfNextInsertableCell(word, row, startIndex) {
  let foundNull = false;
  let count = 0;
  let index = 0;

  for (let i = startIndex; i < row.length; i++) {
    const cell = row[i];

    if (foundNull && cell === null) {
      count++;
    } else if (!foundNull && cell === null) {
      foundNull = true;
      index = i;
      count++;
    }

    if (word.length === count) return index;

    if (foundNull && cell !== null) {
      foundNull = false;
      count = 0;
    }
  }

  return -1;
}

// replace trailing `null` with spaces to take up text box width
function padWithTrailingSpaces(grid, metaString) {
  const [width, x, y] = extractMeta(metaString);
  const gridClone = grid.map((arr) => arr.slice());
  let rowIndex = 0;

  while (rowIndex !== gridClone.length - 1) {
    let row = gridClone[rowIndex];
    let foundChar = false;
    for (let i = 0; i < (width + x); i++) {
      if (!foundChar) {
        if (row[i]) foundChar = true;
      } else {
        if (row[i] === null) row[i] = ' ';
      }
    }
    gridClone[rowIndex] = row;
    rowIndex++;
  }
  return gridClone;
}

// convert meta string to array of integers
// format [width, x, y]
function extractMeta(metaString) {
  let [width, x, y] = metaString.split(' ');
  width = parseInt(width, 10);
  x = parseInt(x, 10);
  y = parseInt(y, 10);
  return [width, x, y];
}

// convert left-trailing `null` to spaces to preserve spacing
// remove all right-trailing `null` and add '\n' to indicate newline
// return single string
function outputLayoutFromGrid(grid) {
  let outputString = '';
  let rowIndex = 0;

  while (rowIndex !== grid.length - 1) {
    let row = grid[rowIndex];
    let foundChar = false;
    for (let i = 0; i < row.length; i++) {
      if (!foundChar) {
        if (row[i] === null) row[i] = ' ';
        else foundChar = true;
      } else {
        if (row[i] === null) row[i] = '';
      }
    }

    if (rowIndex !== 0 && foundChar) outputString += '\n';
    rowIndex++;

    // ignore if row only has `null` cells
    if (!foundChar) continue;
    outputString += row.join('');
  }
  return outputString;
}

/**
 * Test cases
 */
layout([
  '10 3 0 I love monkeys.'
]);
layout([
  '10 4 1 I love monkeys.',
  '20 0 0 It was the best of times it was the worst of times.'
]);