Exercise[29]

Give not that which is holy unto the dogs, neither cast ye your pearls before swine, lest they trample them under their feet, and turn again and rend you.

Matthew 7:6
King James Bible

The study of algorithms offers much to the practicing programmer. A course on the subject equips students with algorithms for important tasks and design techniques for attacking new problems. We'll see in later columns how advanced algorithmic tools sometimes have a substantial impact on software systems, both in reduced development time and faster execution speed.

As crucial as those sophisticated ideas are, algorithms have a more important impact at a more common level of programming. In his book Aha! Insight (from which I shamelessly stole my title), Martin Gardner describes the contribution I have in mind: "A problem that seems difficult may have a simple, unexpected solution." Unlike the advanced methods, the aha! insights of algorithms don't come only after extensive study; they're available to any programmer willing to think seriously before, during and after coding.

Jon Bently
“Column 2: Aha! Algorithms”, p. 11
Programming Pearls, 1986

Professor Strunk was a positive man. His book contained rules of grammar phrased as direct orders. In the main I have not attempted to soften his commands, or modify his pronouncements, or delete the special objects of his scorn.

E. B. White
“A Note on This Book”, p. v
The Elements of Style, 1959

It turns out that style matters in programming for the same reason that it matters in writing. It makes for better reading.

Douglas Crockford
“Chapter 9 - Style”, p. 94
JavaScript: The Good Parts, 2008

Functional composition is better.

Email message from Douglas Crockford
Sent to John Spurgeon on Sun, Oct 23, 2016 at 7:53 PM

Tom Finnegan's Big Problem

Tom Finnegan has a homework assignment that is due soon. He's been procrastinating and hasn't been paying attention in class, so he copied some clever code that Tamsin Finnegan wrote. Tom thought he was being clever until Tamsin informed him, at the eleventh hour, that the code he copied wasn't code for Tom's assignment at all. It was just something she did for fun! (Tamsin was wise to Tom all along and is hanging him out to dry.) Tom's actual assignment is to implement a Utility method called josephusNumber, which must be defined in terms of two parameters: rebelCount and skipCount. The method must return the Josephus number corresponding to the argument values passed to the method as demonstrated here. (Note that skipCount may be zero or negative!) Tom's teacher gave him some "Flippant Functions" to work with. All he has to do is find the right function and modify it.

On page 8 of Concrete Mathematics: A Foundation for Computer Science, the authors (Graham, Knuth and Patashnik) present the Josephus problem as follows: Our final introductory example is a variant of an ancient problem named for Flavius Josephus, a famous historian of the first century. Legend has it that Josephus wouldn't have lived to become famous without his mathematical talents. During the Jewish-Roman war, he was among a band of 41 Jewish rebels trapped in a cave by the Romans. Preferring suicide to capture, the rebels decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. But Josephus, along with an unindicted co-conspirator, wanted none of this suicide nonsense; so he quickly calculated where he and his friend should stand in the vicious circle. In our variation, we start with n people numbered 1 to n around a circle, and we eliminate every second remaining person until only one survives.

The Josephus Problem Tamsin's Loopy Lines Tamsin's Clever Code Tamsin's Flippant Functions Tom's Flippant Functions

Your Assignment

Using Tom's Flippant Functions, help Tom get out of his jam.

The function Tom needs to find is named cycleShiftLeft and is defined in terms of three parameters: n, i and j. After you've found the function, make sure you understand its purpose and how it works. Then figure out what needs to change. Make the necessary changes and test them. After you have tested your function using the Test Fixture below:

1. Copy your modified code directly from the Test Fixture below and paste it into the body of an email message.
2. If you want to receive the bonus points, include your answer to the bonus question in the body of the email message.
3. Make sure the message is addressed to: jspurgeon@vcstudent.org
4. Make sure the subject of the message is: Exercise[29]
5. Send the email.

Grading Rubric

• Not counting bonus points, this assignment is worth 100 points.
• If your submission is late or if you submit a corrected assignment after the due date, you will lose 10 points.
• If your code does not produce the correct results, you will lose up to 50 points.
• If the style of the code that you submit is not consistent with the style of the code provided, you may lose up to 10 points.
• If your code is not submitted in the body of an email message as instructed above, you will lose 10 points.
• If your code is not sent to the correct email address, you will lose 10 points.
• If the subject of your email message is not "Exercise[29]", you will lose 10 points.
• If you answer the bonus question (below) correctly, you will receive up to 10 bonus points.

Test Fixture

Array.prototype.cycleShiftLeft = // CYCLE-SHIFT PART OF AN ARRAY function(n, i, j) { // var array = this.clone(); // ARRAY TO CYCLE/SHIFT (C-S) var max = array.length - 1; // LAST INDEX OF ARRAY n = Number.toInt(n, 1); // NUM CELLS TO C-S (DEFAULT: 1) i = Number.toIntRange(i, 0, max, 0); // WHERE C-S STARTS (DEFAULT: 0) j = Number.toIntRange(j, 0, max, max); // WHERE C-S ENDS (DEFAULT: MAX) /* See Wikipedia: Modular_arithmetic */ // <= READ! // var modulus = /* to do */ // USED TO MAP n TO CONGRUENT VAL // n = n % /* to do */ // MAP n TO CONGRUENT VALUE // if (n < 0) { // IF n IS NEGATIVE // n = /* to do */ // CHANGE n TO MAKE C-S WORK // } // array = array.flip(i, i); /* fix */ // FLIP HEAD OF PART TO C-S array = array.flip(i+1, j); /* fix */ // FLIP TAIL OF PART TO C-S array = array.flip(i, j); // FLIP WHOLE PART (AHA!) return array; // RETURN ARRAY } //================================

Always looking for a shortcut, Tom somehow obtained the following strange-looking program from his teacher, who noticed that Tom took it but doesn't mind. You may use it to gauge how well you and Tom are doing on the assignment. (Although he claims he doesn't know how it got there, Tom has Teacher.grade() written in ink on his left palm.)

/* Out of Service */

The Whys and Wherefores

• This assignment provides more practice in the art of following instructions carefully. If you follow the rules of the assignment, then you will receive the specified points; if not, you won't—just like when you're programming a computer, where you have to follow the rules of the programming language; otherwise, the program won't run as desired.
• This assignment provides more practice reading, comprehending, and making small but important changes to a very modest amount of nontrivial code.
• This assignment provides review of and practice with key concepts covered in class, including:
  • Arrays
  • Loops
  • Recursion
  • Program design
  • Algorithms
  • Cycle Shift Left
• This assignment emphasizes the fact that Java and JavaScript programs can look very similar syntactically, even though the two languages are quite different. The code in this assignment shows that it is sometimes not difficult to understand and work with JavaScript code if you know how to program in Java but have not done much programming in JavaScript.

Grading Rubric

• You must submit JavaScript code for the Student object shown above in the body of an email message sent to jspurgeon@vcstudent.org with only the string Exercise[29] in the subject of your email. The code you submit may not produce any errors when copied and pasted into the JavaScript command prompt of a web browser. You will receive 15 points if and only if the email message you send and the code it contains meets these requirements.
  • If the work you submit is late, you will lose 5 points.
  • If code submitted prior to the due date produces any errors (when pasted into the command prompt), you will lose 5 points, even if you submit code that does not produce errors after the due date.
  • If your email message is sent to the wrong address OR does not contain only the string Exercise[29] in the subject of the message OR does not contain code in the body of the email message, you will lose 5 points.
• Your code must maintain the style of indentation (which uses spaces, not tab characters) and usage of curly braces shown in the code above. You will receive 15 points for meeting this requirement. Each instance of a tab character, improperly indented code, or an improperly formatted curly brace will be penalized 5 points up to a maximum penalty of 15 points.
• You will receive 30 points if the code you submit produces the correct Josephus number for all tests where the value of skipCount is one. You will lose points (up to a maximum of 30 points) for each test that your code does not pass where the value of skipCount is one.
• You will receive 40 points if the code you submit produces the correct Josephus number for all tests where the value of skipCount is greater than one. You will lose points (up to a maximum of 40 points) for each test that your code does not pass where the value of skipCount is greater than one.
• At any time prior to the end of the quarter, the weighting of this assignment or any other graded assignment might be adjusted to reflect the significance of the assignment relative to other graded assignments.

Bonus Question (worth 10 points)

What's the connection between this exercise and the parable of the laborers? (Matthew 20:1-16)

Due Date

EXTENDED: This assignment is due by end of day Tuesday, 29 Nov 2016.