Solving A Stack Problem

2019-07-20

A data structure of type array stores data in a linear order. The bridge between elements is thus abstracted as inherent through sequentiality, the prefixed order of memory locations. JavaScript has lots of Array methods and the four most basic ones are push and pop, as well as the counterparts shift and unshift.

This post focuses on a problem borrowed from a text by Donald Knuth and tries to conceptualize the 'stack'.

Six railroad cars are positioned on the input trail. Each is numbered 1..6, left to right. Suppose we could move them to a “stack” (the blue track) one at a time, and from the stack (top first) to an output trail (the red one).

There are two possible operations. Let’s call the operation to move a car from the input to the stack ‘S’ and the operation to move a car from the stack to the output ‘X’.

How would you do it and what combinations would be possible?

Would the sequence 324641 be possible? How about 154623?

123456 into 325641:

S. input(123456) -> stack(,->1)
S. input(23456) -> stack(1, -> 2)
S. input(3456) -> stack (12, -> 3)
X. stack (123) -> output (,-> 3)
X. stack (12) -> output (3, -> 2)
S. input(456) -> stack(1, -> 4)
S. input(56) -> stack(14, -> 5)
X. stack(145) -> output (32, -> 5)
S. input(6) -> stack(14, -> 6)
X. stack(146) -> output (325, -> 6)
X. stack (14) -> output (3256, -> 4)
X. stack (1) -> output (32564, -> 1)
=========================
SSSXXSSXSXXX/success: 325641

123456 into 154623:

S. input(123456) -> stack(,->1)
X. stack (1) -> output (, ->1)
S. input(23456) -> stack(, ->2)
S. input(3456)  -> stack(2, ->3)
S. input(456)  -> stack(23, ->4)
S. input(56)  -> stack(234, ->5)
X. stack (2345) -> output (1, -> 5)
X. stack (234) -> output (15, -> 4)
S. input(6) -> stack(23, -> 6)
X. stack(236) -> output (154, -> 6)
X. stack(23) -> FAIL (car 2 can't jump over car 3)
=========================
SXSSSSXXSXX/fail: 1546

How should we understand this?

The sequence can be understood as a list of instructions, left to right. The first character of the sequence stream is the first element, the second character the second and so on.

A valid instruction of type 'X' must be preceded by the same quantity (or more) of instruction type 'S'. This also means that any list of instructions must begin with an 'S' instruction since the 'stack' is always empty at first.

The solution is therefore quite simple:

function isSolutionValid(charStream, input) {
  // Firstly, we check if the stream is
  // an valid instructions.
  const instructions = charStream.split('');
  const isStreamValid =
instructions.length % 2 === 0 &&
instructions.filter(
action => action === 'S'
  ).length === instructions.filter(
  action => action === 'X'
).length;
  if (!isStreamValid) {
const errorMsg = `
A valid instructions must contain an even
number of both 'S' and 'X'.
`;
throw new TypeError(errorMsg);
  }

  // We declare a stack, an output
  // but also deep copies (just so we can return
  // things for pretty printing.
  let stack = [];
  let output = [];
  const _insts = [...instructions];
  const _input = [...input];

  // While we have more instructions to perform, 
  // continue. If 'S', push to stack and remove 
  // from bottom of the input. If 'X', remove 
  // from the top of the stack and push to 
  // the output.
  while (_insts.length > 0) {
if (_insts[0] === 'S') {
  stack.push(_input[0]);
  _input.shift();
} else if (_insts[0] === 'X' && stack.length > 0) {
  const topOfTheStack = stack[stack.length - 1];
  output.push(topOfTheStack);
  stack.pop();
} else {
  throw new Error('ILLEGAL. Stack is empty!');
}
_insts.shift();
  }
  return {
output,
input,
instructions: charStream,
  };
}

const {
  output,
  input,
  instructions
} = isSolutionValid('SSSXXSSXSXXX', [1, 2, 3, 4, 5, 6]); 

And with pretty printing of the output…

console.log('INSTRUCTIONS:');
console.log(instructions);
console.log('=============');
console.log('INPUT:');
console.log(input);
console.log('=============');
console.log('OUTPUT:');
console.log(output);

/*
INSTRUCTIONS:
SSSXXSSXSXXX
=============
INPUT:
[ 1, 2, 3, 4, 5, 6 ]
=============
OUTPUT:
[ 3, 2, 5, 6, 4, 1 ]
*/

This algorithm handles any sequence of instructions, if the set of instructions follows the rules.