Err Less (少出错): Program FCG2

Program AT1 (Analyze this: Program FCG2).

Program FCG2 (solveFoxChickenGrainPuzzle).

// this IS PUZZLING
//
// Sometimes, to avoid getting into a bind, JavaScript
// developers will use the keyword 'this' and the identifier
// 'that' like this:
//
//     const that = this;
//
// Riddle me this: Why do they do that?

/** :....1....:....2....:....3....:....4....:....5....:....6....:.
 *
 *  Program AT1 (Analyze this: Program FCG2).
 *  by John P. Spurgeon
 *  https://errless.blogspot.com/2018/09/program-fcg2.html#at1
 * 
 *  INTRODUCTION
 *
 *  The Fox, Chicken, Grain puzzle is a classic river-crossing
 *  puzzle where a man needs to get a fox, a chicken, and a
 *  sack of grain from one side of a river to the other. The
 *  man must use a boat to cross the river. And the boat can only
 *  hold the man and one other item. The man must always be in
 *  the boat when it crosses the river, but he doesn't have to
 *  take anyone with him: he can cross alone. If the man leaves
 *  the fox and the chicken together unsupervised, then the fox
 *  will eat the chicken. If he leaves the chicken and the grain
 *  together, then the chicken will eat the grain. The challenge
 *  is to get the fox, the chicken, and the grain to the desired
 *  side of the river without either the chicken or the grain
 *  being eaten.
 *
 *  Program AT1 is a JavaScript program composed of several
 *  subroutines, some of which can be viewed as first-class
 *  programs in their own right. For example, the subroutine
 *  solveFoxChickenGrainPuzzle is itself a JavaScript program
 *  that solves a well-defined problem using what is almost but
 *  not quite an algorithm. The subroutine is technically an
 *  implementation of a computational method, which is like an
 *  algorithm except that it might not terminate. In theory,
 *  solveFoxChickenGrainPuzzle could run forever as it simulates
 *  a man going back-and-forth across a river, trying to get
 *  a fox, a chicken, and a sack of grain to the other side but
 *  never achieving the goal. Per the method's instructions,
 *  the man might: take the chicken across the river; return by
 *  himself; take the grain across the river; and then take the
 *  chicken back-and-forth across the river an infinite number of
 *  times. That scenario is EXTREMELY unlikely to the point of
 *  being practically impossible, however, so we can invoke the
 *  program/subroutine with a high degree of confidence that
 *  it will actually terminate.
 *
 *  Another example of a subprogram of Program AT1 is the
 *  subroutine analyzeFCG2, which is designed to execute
 *  solveFoxChickenGrainPuzzle two or more times (why not 1?) and
 *  analyze the performance of the computational method in terms
 *  of the number of times the man has to cross the river to
 *  achieve the goal. Program AT1 is, therefore, a fairly easy
 *  to follow, fun, yet non-trivial introduction to the subfield
 *  of computer science that Donald Knuth christened Analysis of
 *  Algorithms in _The Art of Computer Programming_. (It's also
 *  a less-than-perfect attempt by the author to demonstrate a
 *  style of coding Knuth calls Literate Programming.)
 *
 *  CONTENTS
 *  
 *    0. Commentary.
 *    1. Begin immediately-invoked function expression (IIFE).
 *    2. Evaluate "use strict".
 *    3. Global constant variable(s).
 *    4. Program FCG2 (solveFoxChickenGrainPuzzle).
 *    5. Initialization subroutines.
 *    6. State transition subroutines.
 *    7. Subroutines that return true or false.
 *    8. Utilities (tools).
 *    9. Object constructor functions.
 *   10. Analyze this.
 *   11. Analysis of Program FCG2.
 *   12. End outer IIFE.
 */

// SEE:
//
// 1. https://www-cs-faculty.stanford.edu/~knuth/taocp.html
// 2. https://en.wikipedia.org/wiki/
//   a. The_Art_of_Computer_Programming
//   b. Analysis_of_algorithms
//   c. Literate_programming

/******************/
/* 0. Commentary. */
/******************/

// Read The Fine Manual. Otherwise, your programs will be
// Fouled Up Beyond All Recognition.

// SEE:
//
// 1. https://developer.mozilla.org/en-US/docs/Learn
//   a. /Getting_started_with_the_web
//   b. /Getting_started_with_the_web#See_also
//   c. /Getting_started_with_the_web/JavaScript_basics
//   d. /JavaScript
// 2. https://developer.mozilla.org/en-US/docs/
//   a. /Web/JavaScript/Reference/Lexical_grammar#Comments
//   b. /Glossary/JavaScript

// "R.T.F.M" -- Anonymous
//
// The initialism appeared in print in 1979 on the table of
// contents page of the LINPACK User's Guide [...] suggesting
// that it was already well established. Cleve Moler has since
// revealed that a visit to Argonne National Laboratory by
// Tektronix software manager Ned Thanhouser (grandson of Edwin
// Thanhouser) during the development of MATLAB led to the
// anonymous quote.
//
// -- https://en.wikipedia.org/wiki/RTFM (accessed 9 SEP 2018)

/************************************************************/
/* 1. Begin immediately-invoked function expression (IIFE). */
/************************************************************/

// Don't pollute the global namespace.
//
// Names introduced within the body of a JavaScript function
// are local to that function and any subroutines defined
// within the function. Since our entire program will be
// defined within an anonymous, immediately-invoked function,
// we won't pollute the global namespace (any more than it
// already is polluted) with the names we choose to refer to
// things like variables and functions. Problems can arise
// when the same name is used to refer to different things;
// we're using an anonymous IIFE to improve our chances of
// avoiding headaches.

(function() { // Anonymous IIFE begins on this line.

// SEE:
//
// 1. https://developer.mozilla.org/en-US/docs
//   a. /Glossary/IIFE
//   b. /Learn/JavaScript/Building_blocks/Functions
//      #Anonymous_functions
//   c. /Glossary/Function
// 2. https://stackoverflow.com/questions
//   a. /8862665/

// STYLE NOTE: To conserve scarce space, we won't indent
// the lines of code that comprise the body of the outer
// IIFE. We don't want lines to be too long, because it
// is harder for people to read them if the program
// displaying the code wraps lines that extend beyond a
// limit that may be imposed by the displaying program.

/*****************************/
/* 2. Evaluate "use strict". */
/*****************************/

// Opt out of sloppy mode.
//
// Evaluating the string expression "use strict" is
// like chanting an incantation that may or may not
// have an effect depending on the JavaScript
// interpreter that interprets our code. Most modern
// web browsers implement versions of JavaScript that
// respond to the incantation by enforcing language
// rules that otherwise would not be enforced.
//
// If you're a very strict stickler for details, you
// might prefer to use the name ECMAScript instead
// of JavaScript to refer to the programming language
// the program is written in. (FYI: Brendan Eich, the
// creator of JavaScript, thinks ECMAScript sounds like
// the name of a skin disease.)

"use strict";

// SEE:
//
// 1. https://developer.mozilla.org/en-US/docs
//   a. /Web/JavaScript/Reference/Strict_mode
//   b. /Glossary/Sloppy_mode
// 2. https://en.wikipedia.org/wiki/
//   a. JavaScript
//   b. Brendan_Eich
//   c. ECMAScript
// 3. http://www.ecma-international.org
//   a. /publications/standards/Ecma-262.htm

/***********************************/
/* 3. Global constant variable(s). */
/***********************************/

// Don't use global variables.
// But if you do, do so constantly. (This is punny.)

// The side of a river that a man wants to move
// a fox, a chicken, and a sack of grain to is
// labeled side B. The other side of the river
// is labeled side A.

const SideLabels = new InterchangableBinaryLabels("A", "B");

// SEE:
//
// 1. https://developer.mozilla.org/en-US/docs/Web
//   a. /JavaScript/Reference/Statements/const
//   b. /JavaScript/Reference/Operators/new

/*************************************************/
/* 4. Program FCG2 (solveFoxChickenGrainPuzzle). */
/*************************************************/

// Algorithms terminate by definition.
//
// A computational method is an algorithm that might
// not terminate.
//
// (You might win the lottery.)

// In the mathematical theory of probability, an absorbing
// Markov chain is a Markov chain in which every state can
// reach an absorbing state. An absorbing state is a state
// that, once entered, cannot be left.

// SEE:
//
// 1. https://en.wikipedia.org/wiki
//   a. /Fox,_goose_and_bag_of_beans_puzzle
//   b. /Absorbing_Markov_chain
// 2. https://ed.ted.com/lessons
//    /can-you-solve-the-river-crossing-riddle-lisa-winer
// 3. https://developer.mozilla.org/en-US/docs/Web
//   a. /JavaScript/Reference/Functions
// 4. https://developer.mozilla.org/en-US/docs/Learn
//   a. /JavaScript/Building_blocks/Functions

/**********************************/
/* 5. Initialization subroutines. */
/**********************************/

function putAllActorsOnSideA(actors) {
  const valueOfSideA = SideLabels.A.getValue();
  actors.man.setValue(valueOfSideA);
  actors.fox.setValue(valueOfSideA);
  actors.chicken.setValue(valueOfSideA);
  actors.grain.setValue(valueOfSideA);
  return actors;
}

function putEachActorOnARandomSide(actors) {
  actors.man.setValue(MathUtil.getRandomBooleanValue());
  actors.fox.setValue(MathUtil.getRandomBooleanValue());
  actors.chicken.setValue(MathUtil.getRandomBooleanValue());
  actors.grain.setValue(MathUtil.getRandomBooleanValue());
  return actors;
}

/************************************/
/* 6. State transition subroutines. */
/************************************/

// SEE:
//
// 1. https://errless.blogspot.com/2018/09/
//   a. procedure-fcg2-state-transition-diagram.html
// 2. https://en.wikipedia.org/wiki/
//   a. Absorbing_Markov_chain

/*********************************************/
/* 7. Subroutines that return true or false. */
/*********************************************/

/*************************/
/* 8. Utilities (tools). */
/*************************/

// Careful study and imitation of good programs leads to better writing.
//
// -- KERNIGHAN & PLAUGER, _Software Tools_ (1976)

// SEE:
//
// 1. https://en.wiktionary.org/wiki/util

/************************************/
/* 9. Object constructor functions. */
/************************************/

// Every powerful programming language is more than just a
// means for instructing a computer to perform tasks. The
// language also serves as a framework within which we
// organize our ideas about processes. Thus, when we
// describe a language, we should pay particular attention
// to the means that the language provides for combining
// simple ideas to form more complex ideas. Every powerful
// language has three mechanisms for accomplishing this:
//
//  * primitive expressions, which represent the simplest
//    entities the language is concerned with,
//  * means of combination, by which compound elements are
//    built from simpler ones,
//  * means of abstraction, by which compound elements can
//    be named and manipulated as units.
//
// In programming, we deal with two kinds of elements:
// procedures and data.
//
// -- HAROLD ABELSON & GERALD JAY SUSSMAN w/ JULIE SUSSMAN,
//    _Structure and Implementation of Computer Programs_ (1996)

// I find that many beginning graduate students with an
// undergraduate degree in computer science have been more
// narrowly educated than I would like. Computer scientists
// are working to correct this present deficiency, which I
// believe is probably due to an overemphasis on computer
// languages instead of algorithms.
//
// -- DONALD E. KNUTH, "Computer Science and its Relation to
//    Mathematics" in _Selected Papers on Computer Science_ (1996)

function FairCoin() {
  this.flip = function() {
    return (Math.random() < 0.5) ?
        FairCoin.HEADS : FairCoin.TAILS;
  }
  Object.freeze(this);
}
FairCoin.TAILS = true;
FairCoin.HEADS = false;
Object.freeze(FairCoin);

// SEE:
//
// 1. https://developer.mozilla.org/en-US/docs/Learn
//   a. /JavaScript/Objects
//   b. /JavaScript/Objects/Basics
//   c. /JavaScript/Objects/Object-oriented_JS

/*********************/
/* 10. Analyze this. */
/*********************/

// Algorithm M requires a fixed amount of storage, so we
// will analyze only the time required to perform it. To
// do this, we will [emphasis] count the number of times
// each step is executed (cf. Fig. 9): [...] Knowing the
// number of times each step is executed gives us the
// information necessary to determine the running time on
// a particular computer.
//     In the above table, we know everything except the
// quantity A, [...] To complete the analysis, we shall
// study this interesting quantity A. The analysis usually
// consists of finding the minimum value of A (for optimistic
// people), the maximum value of A (for pessimistic people),
// the average value of A (for probabilistic people), and
// the standard deviation of A (a quantitative indication of
// how close to the average we may expect the value to be).
//
// -- DONALD E. KNUTH, TAOCP, Vol. 1, p.95-96 (1973)

const computeStdDev = function(avg, values) {
  const n = values.length;
  let sumOfSquares = 0;
  while (values.length > 0) {
    let value = values.pop();
    sumOfSquares += Math.pow((value - avg), 2);
  }
  const variance = sumOfSquares / (n - 1);
  return Math.sqrt(variance);
};

// SEE:
//
// 1. https://en.wikipedia.org/wiki
//   a. /Analysis_of_algorithms

/*********************************/
/* 11. Analysis of Program FCG2. */
/*********************************/

// In the 1960s and 1970s, [_How to Lie with Statistics_]
// became a standard textbook introduction to the subject of
// statistics for many college students. It has become one of
// the best-selling statistics books in history, with over one
// and a half million copies sold in the English-language edition.
// Themes of the book include 'Correlation does not imply
// causation' and 'Using random sampling'.
//
// -- https://en.wikipedia.org/wiki/How_to_Lie_with_Statistics

(function performExperiment() {
  const answer = prompt("How many trials?")
  const numTrials = parseInt(answer); 
  if (answer === null) {
    // User pressed cancel, so do nothing.
  }
  else if (numTrials >= 2 && numTrials < Infinity) {
    const analysis = analyzeFCG2(numTrials);
    console.log(analysis);
    alert(StringUtil.stringifyObject(analysis));
  }
  else {
    alert("Enter a very finite integer greater than one.");
    performExperiment(); // Try again.
  }
})();

/***********************/
/* 12. End outer IIFE. */
/***********************/

})(); // Anonymous IIFE ends here.

// .:....1....:....2....:....3....:....4....:....5....:....6....:.
// Analyze This is a 1999 gangster comedy film directed by
// Harold Ramis, who co-wrote the screenplay with playwright
// Kenneth Lonergan and Peter Tolan. The film stars Robert
// De Niro as a mafioso and Billy Crystal as his psychiatrist.
// A sequel, Analyze That, was released in 2002.
//
// -- https://en.wikipedia.org/wiki/Analyze_This

Pages

Program FCG2