E15: Sorceror’s Scale

The myth

In ancient times, a sorceror tested an apprentice’s logical skills by giving her eight balls. They all looked exactly the same, and seven of them weighed exactly the same amount, but one of them was slightly heavier. The sorceror also gave the apprentice a magic scale. The scale had a left pan and a right pan, and the apprentice could put any number of balls on either pan and the scale would indicate which pan was heavier. The magic? This scale would turn into dust if it was used more than four times!

For the apprentice to succeed at this challenge, she had to determine which one of the eight balls was heavier by using the scale no more than four times.

The WOD: Background

You are the apprentice, and your task is to write a Javascript function called findBall that will be passed a “magic” Scale object and which will find the heavier ball by invoking its weighing function no more than four times.

The Scale object has an internal array of ball weights. The first ball’s weight is at index 0, the second ball’s weight’ is at index 1, and so forth through index 7. All but one of the weights are the same.

Unfortunately, there’s no way to get at this array with your findBall function. Instead, the Scale object has a function called getWeight(). Your findBall function can call getWeight() up to four times. Each time you call getWeight(), you pass it two arrays. The first array contains a list of integers from 0 to 7 indicating the balls you want to put on the left pan, and the second array contains a list of integers from 0 to 7 indicating the balls you want to put on the right pan. The getWeight() function accesses the hidden array of ball weights, sums up the total weight on the left pan and the total weight on the right pan, and returns:

• -1 if the left pan of the scale is heavier.
• 1 if the right pan of the scale is heavier.
• 0 if both pans weigh the same.

An example might make this more clear. Let’s say there’s a Scale object bound to a variable named scale and it hides an array of ball weights that looks like this:

[10, 9, 9, 9, 9, 9, 9, 9]

Then, in this case,

1. scale.getWeight([0], [1]) returns -1 because the left pan (containing the first ball which weighs 10) weighs more than the right pan (containing the second ball which weighs 9).

2. scale.getWeight([1, 3, 5, 7], [0, 2, 4, 6]) returns 1 because the right pan (containing the “even” balls with a total weight of 37) weighs more than the left pan (containing the “odd” balls with a total weight of 36).

3. scale.getWeight([2, 4], [3, 5]) returns 0 because the weight of both pans is 18 and thus equal.

4. scale.getWeight([0], [0]) returns 0 (and of course this is not very helpful).

5. scale.getWeight([1, 2], [3, 4]) will throw an exception because scale has now been called more than 4 times!

To help you solve this problem, I’ve implemented both the Scale object as well as created eight sample Scale instances that put the heaviest ball in all eight positions. Here’s how it looks in JSFiddle (click on it to see full size):

As you can see, to load the Scale instance, put the following into the HTML pane:

<script src="//philipmjohnson.github.io/ics314f15/morea/javascript-2/scales.js"></script>

In addition to defining the Scale object, this script defines an object called sampleBalls with eight internal Scale instances, each one locating the heaviest ball in a different position. So, sampleBalls.firstHeavier is a Scale instance with the heaviest ball in the first position, sampleBalls.secondHeavier is a Scale instance with the heaviest ball in the second position, and so forth up to sampleBalls.eighthHeavier.

The only thing you can do with a Scale instance is call getWeight(). The first two lines in the Javascript window show invocations of getWeight for the firstHeavier instance (where the console prints out -1), and getWeight on the secondHeavier instance (where the console prints out 0). The last five lines show what happens when you invoke getWeight on a Scale instance more than four times: on the fifth invocation, getWeight throws an exception. Don’t let this happen to you!

The WOD: For real

Please implement a findBall function that will be passed a Scale instance and which will return the index of the heaviest ball. So, for example:

console.log(findBall(sampleBalls.firstHeavier));

should print out “0” to the console, and

console.log(findBall(sampleBalls.eighthHeavier));

should print out “7” to the console.

Use JSFiddle as your development environment.

Ready? Let’s begin:

1. Start your timer.

2. Create the findBall function. The findBall function should return the index of the heavy ball when it discovers it.

3. Informally test your program by running it with all eight sample scales and inspecting the output.

4. Press the “save” button to create a URL to refer to your code.

5. Stop your timer and record your time. Be sure to record it, because you will need your WOD time data when you write your technical essay.

Rx: < 9 min Av: 9 - 14 min Sd: 14-18 min DNF: 18+ min

Demonstration

Once you’ve finished trying the WOD for the first time, watch me do it:

Standard WOD Caveats

You’ll learn significantly less from watching me solve the WOD if you haven’t attempted the WOD yourself first.

While it’s an achievement to finish the WOD no matter how long it takes, you might experience “diminishing returns” if you work longer than the DNF time. Thus, it is usually strategic to stop working at the DNF time and watch my solution.

After watching my solution, I recommend that you repeat the WOD if you have not achieved at least Av performance. If so, be sure to:

• Create a new fiddle and don’t refer to your old one while resolving the problem.
• Don’t look at my screencast while you WOD; and
• Reset your timer.

Feel free to keep trying until you make Rx if that’s of interest to you.

Submission Instructions

To be completed by the time and date indicated on the Schedule page.