In which I continue solving a series of puzzles first posed as part of the programming course for my Mathematics degree. This time it’s the last puzzle of all, the fifth. (The others: one, two, three, four, or click on the Puzzles category beneath this post.)
“Can we try on our new hats?” the dwarves begged Snow White one day.
“All right,” she said, “but first shut your eyes.” When they had done so, she popped a red or a green hat on each. When they opened their eyes each could see the other six hats but not his own.
“I see exactly three red hats,” said Dopey lethargically.
“I see exactly three green hats,” said Doc assertively.
“I see exactly one green hat,” said Sleepy drowsily.
“I see no red hats at all,” said Happy merrily.
“Well, I see exactly five green ones,” said Grumpy crossly.
“I can see five red ones,” said Sneezy, before a resounding “a-tishoo!”
“I can see just red ones,” said Bashful, blushing.
As it happens, those with hats of one colour have spoken the truth, and those of the other colour have lied.
Now, who was wearing the green hats?
OK, a cute one, but it’s one of those logic puzzles that makes me wonder how to program it. Yet another loop of loops? And then, it struck me. There are seven dwarves. Each dwarf has two configurations, as it were: wearing a red hat or wearing a green one. And then there’s the overall possibility of red hatters lie or green hatters do.
WAIT A MOMENT! That’s eight binary possibilities! 2 to the power 8! It can be represented as a byte, people! There’s just one loop going from 0 to 255! Bit-twiddling here we come!
What I did was to assume that a zero bit meant green and a one bit, red. I kept the same dwarf order as in the puzzle: so Dopey is bit 0, Doc, bit 1, etc, with the eighth bit defining whether red hatters lie or not (so a one bit means yes). Each cycle through the loop, I’d split the “byte” into bits that I’d use as booleans and return an object that has an array of dwarves’ headgear values (red: true, green: false) and a boolean stating whether red hat wearers lie or not.
var isOdd = function(i) {
return (i & 1) === 1;
};
var splitBits = function(byteValue) {
var p = {wearsRedHat : [], redHatsLie: byteValue > 127};
for (var i = 0; i < 7; i += 1) {
p.wearsRedHat.push(isOdd(byteValue));
byteValue = byteValue >> 1;
}
return p;
};
var cycleThroughPossibilities = function() {
for (var i = 0; i < 256; i += 1) {
var possibility = splitBits(i);
if (checkPossibility(possibility)) {
printAnswer(possibility);
}
}
};
cycleThroughPossibilities();The interesting thing here for me is that I think this is the first time I’ve done bit-twiddling in JavaScript. Check the isOdd() function where I test to see whether the zeroth bit of the value is one or not. And then there’s the bit-shift operator in splitBits. I’m a Real JavaScript™ developer now!
The `checkPossibilities` function defers its result to a series of tests, one for each of the dwarves’ statements, taking into consideration whether red hat wearers are lying or not. Each of those defers to a check of red hat counts or green hat counts (and of course, the green hat count check just calls the red hat check looking for 6 minus the expected green hat count).
Here’s the code for that:
var validateRedHatCount = function(p, dwarf, expectedCount) {
var redCount = 0;
p.wearsRedHat.forEach(function(redHat) {
if (redHat) { redCount += 1; }
});
if (p.wearsRedHat[dwarf]) { redCount -= 1; }
if (p.redHatsLie) {
if (p.wearsRedHat[dwarf]) {
return redCount !== expectedCount;
}
else {
return redCount === expectedCount;
}
}
else {
if (p.wearsRedHat[dwarf]) {
return redCount === expectedCount;
}
else {
return redCount !== expectedCount;
}
}
};
var validateGreenHatCount = function(p, dwarf, expectedCount) {
return validateRedHatCount(p, dwarf, 6 - expectedCount);
};
And an example call for Dopey, so you can see how it hangs together:
var validateDopey = function(p) {
return validateRedHatCount(p, dopey, 3);
};Although I did consider replacing those nested ifs with some clever code, in the end I decided to leave it as is: the clearer, the better.
Here’s the complete code:
/*jslint white this */
/*global console*/
(function () {
"use strict";
var dopey = 0;
var doc = 1;
var sleepy = 2;
var happy = 3;
var grumpy = 4;
var sneezy = 5;
var bashful = 6;
var validateRedHatCount = function(p, dwarf, expectedCount) {
var redCount = 0;
p.wearsRedHat.forEach(function(redHat) {
if (redHat) { redCount += 1; }
});
if (p.wearsRedHat[dwarf]) { redCount -= 1; }
if (p.redHatsLie) {
if (p.wearsRedHat[dwarf]) {
return redCount !== expectedCount;
}
else {
return redCount === expectedCount;
}
}
else {
if (p.wearsRedHat[dwarf]) {
return redCount === expectedCount;
}
else {
return redCount !== expectedCount;
}
}
};
var validateGreenHatCount = function(p, dwarf, expectedCount) {
return validateRedHatCount(p, dwarf, 6 - expectedCount);
};
var validateDopey = function(p) {
return validateRedHatCount(p, dopey, 3);
};
var validateDoc = function(p) {
return validateGreenHatCount(p, doc, 3);
};
var validateSleepy = function(p) {
return validateGreenHatCount(p, sleepy, 1);
};
var validateHappy = function(p) {
return validateRedHatCount(p, happy, 0);
};
var validateGrumpy = function(p) {
return validateGreenHatCount(p, grumpy, 5);
};
var validateSneezy = function(p) {
return validateRedHatCount(p, sneezy, 5);
};
var validateBashful = function(p) {
return validateRedHatCount(p, bashful, 6);
};
var checkPossibility = function(p) {
return validateDopey(p) &&
validateDoc(p) &&
validateSleepy(p) &&
validateHappy(p) &&
validateGrumpy(p) &&
validateSneezy(p) &&
validateBashful(p);
};
var printAnswer = function(p) {
var name = ["Dopey", "Doc", "Sleepy", "Happy", "Grumpy", "Sneezy", "Bashful"];
p.wearsRedHat.forEach(function(redHat, index) {
if (!redHat) {
console.log(name[index], "is wearing a green hat");
}
});
if (p.redHatsLie) {
console.log("The red hats are lying");
}
else {
console.log("The green hats are lying");
}
console.log("-----");
};
var isOdd = function(i) {
return (i & 1) === 1;
};
var splitBits = function(byteValue) {
var p = {wearsRedHat : [], redHatsLie: byteValue > 127};
for (var i = 0; i < 7; i += 1) {
p.wearsRedHat.push(isOdd(byteValue));
byteValue = byteValue >> 1;
}
return p;
};
var cycleThroughPossibilities = function() {
for (var i = 0; i < 256; i += 1) {
var possibility = splitBits(i);
if (checkPossibility(possibility)) {
printAnswer(possibility);
}
}
};
cycleThroughPossibilities();
}());The answer that is printed is this:
Sleepy is wearing a green hat Sneezy is wearing a green hat The red hats are lying -----
Which of course can now be verified manually.
And that unfortunately brings us to the end of this little series of programming puzzles from 1978/79. It’s been fun thinking of them in JavaScript terms instead of in FORTRAN, which to be honest I wouldn’t be able to write or read now, at least not without a lot of work/learning. I don’t remember solving them way back when (I certainly don’t have the code nicely printed out on green fanfold paper), except that I seem to remember coming across the fact that Puzzle IV gave four solutions of which the required answer was the same in each.
Of the five, Puzzle III was the most ‘meh’ for me, with the others being more interesting or fun to do. Puzzle IV was the longest running bit of code, mainly because I couldn’t come up with any deeper analysis that would reduce the number of cycles (over 9 million, if you recall).
And, yes, I used the rarer word dwarves for the plural of dwarf. Sue me!
Loading links to posts on similar topics...
No Responses
Feel free to add a comment...
Leave a response
Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.
_emphasis_**strong**[text](url)`IEnumerable`* an item1. an item> Now is the time...Preview of response