## Scenes from my programming past: Puzzles II

Continuing through this set of five puzzles from 40 years ago, presumably designed to be solved with FORTRAN, the language I used back then.

Here’s the second puzzle, one that seems like a logical one:

Five anglers were propping up the bar of The Compleat Idiot the other night, arguing about the day’s catch. As all were lying themselves blue, no information whatever emerged until the landlord finally intervened.

“Look,” he said, “each of you has caught just one fish. The five fish together weigh 25 pounds and each weighs a different whole number of pounds greater than one. Each of you at present knows only the weight of his own fish.”

The anglers sobered down enough to digest this and to speak truthfully thereafter.

“Mine is the heaviest,” said Albert.

“Then mine is next,” said Bert, thoughtfully.

“And mine is next,” piped up little Charlie.

“I know the weight of Albert’s fish, then,” said Derek.

“And so do I,” remarked Ernest.

Well, what was the weight of each man’s fish?

At first glance, I’m glad that Albert is not known as Bert (oh, puzzle setter from the past: why not ‘Brian’ or ‘Bob’ or something?). Moving on…

From my viewpoint, solving this involves working out the universe of possible answers that satisfy the total weight of fish being 25 lbs, each weight being a whole number greater than 1, no duplicates, and then knocking out the possible answers that no longer apply as we take into account each angler’s statement. The first part is pretty simple, then:

``````  var calculateAllPossibleSolutions = function() {
var s = [];
for (var v = 2; v < 11; v += 1) {
for (var w = v + 1; w < 11; w += 1) {
for (var x = w + 1; x < 11; x += 1) {
for (var y = x + 1; y < 11; y += 1) {
var z = 25 - v - w - x - y;
if (z > y) {
s.push({weights: [v, w, x, y, z], isOK: true});
}
}
}
}
}
return s;
}``````

For a slight bit of efficiency, the loops here all end at 11, since that is the absolute possible maximum weight for Albert’s fish (the other weights then being 2, 3, 4, and 5). The code creates an array of possible answers (as an array of five numbers) and a boolean to state whether it is still in the running or not. The way the loops work is that each possible answer has the values in ascending order. Here are the seven possible answers:

``````[ { weights: [ 2, 3, 4, 5, 11 ], isOK: true },
{ weights: [ 2, 3, 4, 6, 10 ], isOK: true },
{ weights: [ 2, 3, 4, 7, 9 ], isOK: true },
{ weights: [ 2, 3, 5, 6, 9 ], isOK: true },
{ weights: [ 2, 3, 5, 7, 8 ], isOK: true },
{ weights: [ 2, 4, 5, 6, 8 ], isOK: true },
{ weights: [ 3, 4, 5, 6, 7 ], isOK: true } ]``````

Given that Albert can then say that his fish is the heaviest means that we shall check whether each possible Albert fish weight is strictly greater than any of the second heaviest fish (assumed to be Bert’s). From the above you can see that the seventh possible answer should be rejected: it’s possible for Bert to have a 7lb fish, and so Albert couldn’t justifiably state that his was the heaviest in that case.

``````  var satisfyAlbert = function(s) {
s.forEach(function(a) {
if (a.isOK) {
a.isOK = isHeavier(s, a.weights[forAlbert], forBert)
}
});
};``````

The code cycles through all possible answers. For each answer, it checks that it’s still valid – in the running – and then checks to see if it is greater than any of Bert’s weights. If the called function `isHeavier()` returns false, then this particular answer should be marked as not OK.

``````  var isHeavier = function(s, maxWeight, index) {
return s.find(function(a) {
return a.isOK && (a.weights[index] >= maxWeight);
}) === undefined;
};``````

This function makes use of the Array `find` method: if no element returns true then `find` returns undefined. The `find` method here is being used to search for some weight that is greater than the maximum weight. Again we only check possible answers if they are still being considered (the `isOK` property is true).

Onto Bert who states, given that he knows Albert has the heaviest fish, that he has the second heaviest. In essence, the same process is initiated: for each possible answer remaining, check that the second heaviest value is greater than all of the other third greatest values. Ditto, for Charlie.

``````  var satisfyBert = function(s) {
s.forEach(function(a) {
if (a.isOK) {
a.isOK = isHeavier(s, a.weights[forBert], forCharlie)
}
});
};

var satisfyCharlie = function(s) {
s.forEach(function(a) {
if (a.isOK) {
a.isOK = isHeavier(s, a.weights[forCharlie], forDerek)
}
});
};``````

At this point, if you ran the code so far, you’d see that there were three remaining possible answers. Here Derek states that he knows the weight of Albert’s fish and Ernest concurs. For Derek to know this (knowing his own fish’s weight) means that there is a unique solution: if Derek’s fish’s weight is X then Albert’s is unequivocally Y. We therefore have to search for this unique answer.

We go through the array of possible answers, and for each pair of Derek and Albert’s weights, we search through the array again looking for a duplicate answer that has the same Derek weight, but a different Albert weight.

``````  var hasDifferentDuplicate = function(s, currWeight, maxWeight) {
return s.find(function(a) {
return ((a.isOK) &&
(a.weights[forDerek] === currWeight) &&
(a.weights[forAlbert] !== maxWeight));
}) !== undefined;
};``````

If we find at least one for a given Derek fish weight, we then have to mark all duplicates with the same weight as invalid.

``````  var clearDuplicates = function(s, currWeight) {
s.forEach(function(a) {
if (a.isOK && (a.weights[forDerek] === currWeight)) {
a.isOK = false;
}
});
};``````

And this makes Derek’s function look like this:

``````  var satisfyDerek = function(s) {
s.forEach(function(a) {
if (a.isOK) {
if (hasDifferentDuplicate(s, a.weights[forDerek], a.weights[forAlbert])) {
clearDuplicates(s, a.weights[forDerek]);
};
}
});
};``````

Finally, we can wrap all this code up and print out the answer (hopefully only one) on the console.

``````/*jslint white this */
/*global console*/
(function () {
"use strict";

var forAlbert = 4;
var forBert = 3;
var forCharlie = 2;
var forDerek = 1;
var forErnest = 0;

var calculateAllPossibleSolutions = function() {
var s = [];
for (var v = 2; v < 11; v += 1) {
for (var w = v + 1; w < 11; w += 1) {
for (var x = w + 1; x < 11; x += 1) {
for (var y = x + 1; y < 11; y += 1) {
var z = 25 - v - w - x - y;
if (z > y) {
s.push({weights: [v, w, x, y, z], isOK: true});
}
}
}
}
}
return s;
}

var isHeavier = function(s, maxWeight, index) {
return s.find(function(a) {
return a.isOK && (a.weights[index] >= maxWeight);
}) === undefined;
};

var hasDifferentDuplicate = function(s, currWeight, maxWeight) {
return s.find(function(a) {
return ((a.isOK) &&
(a.weights[forDerek] === currWeight) &&
(a.weights[forAlbert] !== maxWeight));
}) !== undefined;
};

var clearDuplicates = function(s, currWeight) {
s.forEach(function(a) {
if (a.isOK && (a.weights[forDerek] === currWeight)) {
a.isOK = false;
}
});
};

var satisfyAlbert = function(s) {
s.forEach(function(a) {
if (a.isOK) {
a.isOK = isHeavier(s, a.weights[forAlbert], forBert)
}
});
};

var satisfyBert = function(s) {
s.forEach(function(a) {
if (a.isOK) {
a.isOK = isHeavier(s, a.weights[forBert], forCharlie)
}
});
};

var satisfyCharlie = function(s) {
s.forEach(function(a) {
if (a.isOK) {
a.isOK = isHeavier(s, a.weights[forCharlie], forDerek)
}
});
};

var satisfyDerek = function(s) {
s.forEach(function(a) {
if (a.isOK) {
if (hasDifferentDuplicate(s, a.weights[forDerek], a.weights[forAlbert])) {
clearDuplicates(s, a.weights[forDerek]);
};
}
});
};

var printFishWeight = function(a, angler, index) {
console.log(angler + "'s fish weighed", a.weights[index], "lbs");
};

if (a.isOK) {
printFishWeight(a, "Albert", forAlbert);
printFishWeight(a, "Bert", forBert);
printFishWeight(a, "Charlie", forCharlie);
printFishWeight(a, "Derek", forDerek);
printFishWeight(a, "Ernest", forErnest);
return true;
}
});

}());``````

```Albert's fish weighed 8 lbs
Bert's fish weighed 6 lbs
Charlie's fish weighed 5 lbs
Derek's fish weighed 4 lbs
Ernest's fish weighed 2 lbs```

Again, if you have Node.js installed, save this script as, say `puzzletwo.js`, and you can just run it from the command line with `node puzzletwo.js`.

This time, I’d have to say that I’m using a more functional style of programming, something that would not have been available back then with FORTRAN. To which I say, thanks heavens for that. Writing this out in FORTRAN would certainly be an exercise to sort the pros from the novices…  Loading links to posts on similar topics...

#### 1 Response ##### #1julian m bucknall said...
25-Jul-17 2:11 PM

One thing that I hadn't discussed in writing this blog post was why I bothered with this `isOK` property. Why not just delete the rejected possibilities from the array as and when the code finds them?

The reason is simple: you should never delete items (or indeed add one) from an array as you are walking through it. This goes especially for the built-in methods like `forEach` and `find` and what have you. You have no idea how they're implemented and whether you'd miss an item or try to access beyond the end of the array or something equally dire when you delete an item.

Cheers, Julian

##### Leave a response

Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.

•  Emphasize with italics: surround word with underscores `_emphasis_`
•  Emphasize strongly: surround word with double-asterisks `**strong**`
•  Link: surround text with square brackets, url with parentheses `[text](url)`
•  Inline code: surround text with backticks ``IEnumerable``
•  Unordered list: start each line with an asterisk, space `* an item`
•  Ordered list: start each line with a digit, period, space `1. an item`
•  Insert code block: start each line with four spaces
•  Insert blockquote: start each line with right-angle-bracket, space `> Now is the time...`