In which I take a look at the fourth puzzle in the set of five that I had to solve in FORTRAN in my early programming days. The others are here: one, two, three.
Without further ado:
My friend Gogol is a whale for cryptarithmetic. He has two children called, of course, Fleur and Angio.
Why ‘of course’ you may ask?
Well, Fleur was born on FL/E/UR and Angio on AN/G/IO. Gogol himself was born on GO/G/OL, seeing that FLEUR + ANGIO = GOGOL.
Each different letter stands for a different digit. Thus Angio might have been born on 09/4/58, so A=0, N=9, etc… (and then again he might not have been!).
When was Gogol born?
(Aside: you try typing ‘Gogol’ without error in these days of ubiquitous Google. It certainly didn’t exist in 1978…)
The puzzle has one big assumption: dates are understood to be in the form dd/m/yy – hey, this puzzle was posed in the UK after all. Along with that, the example given also implies that the first digit of the day part can be 0. We could also make the assumption that the year values are in the range 00 to 79 since these puzzles came from 1978-1979, but this is something we won’t do. After all, our laptops are way faster than that old timeshare system I used to have to use, so a few more cycles testing possibilities won’t make any real difference.
OK, given all that, what conclusions can we draw before putting fingers to keyboards in our favorite editor? For me, there are two main vectors for analysis. The first is looking at the day parts of the dates. In essence: F, A, and G could either be 0, 1, 2, or 3. In fact, neither F or A could be 3, since then G would be greater than 3 (or equivalently, from the addition restriction GO would be greater than 31). We can limit it even further: since F, A, and G are all different, it would imply that G must be 2 or 3.
The next one for me was the middle of the addition: we have E + G + (a possible carry) = G. If the carry were 0, then E is 0, except that this is not a valid month number. Hence the carry must be 1, so E is 9.
So already we know that F is 0..2, A is 0..2, G is 2..3, E is 9. The other six values will be found through looping through the possibilities in the range 0..8. Total cycles? 9,565,938. Er, OK then.
/*jslint white this */
/*global console*/
(function () {
"use strict";
var verifyUniqueValues = function(p) {
return p.find(function(possibleDupe) {
var count = 0;
p.forEach(function(value) {
if(value === possibleDupe) {
count += 1;
}
});
return count !== 1;
}) === undefined;
};
var verifyAddition = function(p) {
var fleur = (p[0] * 10000) +
(p[1] * 1000) +
(p[2] * 100) +
(p[3] * 10) + p[4];
var angio = (p[5] * 10000) +
(p[6] * 1000) +
(p[7] * 100) +
(p[8] * 10) + p[9];
var gogol = (p[7] * 10000) +
(p[9] * 1000) +
(p[7] * 100) +
(p[9] * 10) + p[1];
return fleur + angio === gogol;
};
var verifyDate = function(p) {
var go = (p[7] * 10) + p[9];
return go <= 31;
};
var checkPossibility = function(p) {
if (!verifyDate(p)) {
return false;
}
if (!verifyAddition(p)) {
return false;
}
if (!verifyUniqueValues(p)) {
return false;
}
return true;
};
var formatAsDate = function(p, d) {
return p[d[0]].toString() +
p[d[1]].toString() + "/" +
p[d[2]].toString() + "/" +
p[d[3]].toString() +
p[d[4]].toString();
};
var printAnswer = function(p) {
console.log("Gogol's birthdate is:", formatAsDate(p, [7, 9, 7, 9, 1]));
console.log("Fleur's birthdate is:", formatAsDate(p, [0, 1, 2, 3, 4]));
console.log("Angio's birthdate is:", formatAsDate(p, [5, 6, 7, 8, 9]));
console.log("-----");
};
var cycleThroughPossibilities = function() {
var e = 9;
for (var f = 0; f <= 2; f += 1) {
for (var l = 0; l <= 8; l += 1) {
for (var u = 0; u <= 8; u += 1) {
for (var r = 0; r <= 8; r += 1) {
for (var a = 0; a <= 2; a += 1) {
for (var n = 0; n <= 8; n += 1) {
for (var g = 2; g <= 3; g += 1) {
for (var i = 0; i <= 8; i += 1) {
for (var o = 0; o <= 8; o += 1) {
var possibility = [f, l, e, u, r, a, n, g, i, o];
if (checkPossibility(possibility)) {
printAnswer(possibility);
}
}
}
}
}
}
}
}
}
}
};
cycleThroughPossibilities();
}());
OK, a lovely triangle of `for` loops in the code, but otherwise it’s not too bad. One fascinating bit was that it took a couple of seconds to run on my laptop, so I started to think about optimizations. Should I try to discard possibilities early on in the loops if one of the loop values is a duplicate of another one? I played around with some if statements for a bit with no great success. And then I thought about the checkPossibility function. I’d originally written it to do the uniqueness check first (are all the values unique?), but in retrospect that is the most intense of the checks. The date check function is simplicity itself (is GO less than or equal to 31? Yep, I was ignoring the fact that some months have 30 or even 28 days) and the addition check is pretty simple too. Putting those first made the code much faster.
The most interesting part for me with the code (and the original puzzle) is that it produces four answers:
Gogol's birthdate is: 23/2/38 Fleur's birthdate is: 08/9/65 Angio's birthdate is: 14/2/73 ----- Gogol's birthdate is: 23/2/38 Fleur's birthdate is: 08/9/75 Angio's birthdate is: 14/2/63 ----- Gogol's birthdate is: 23/2/38 Fleur's birthdate is: 18/9/65 Angio's birthdate is: 04/2/73 ----- Gogol's birthdate is: 23/2/38 Fleur's birthdate is: 18/9/75 Angio's birthdate is: 04/2/63 -----
But notice that Gogol’s birthdate is always the same with these solutions, it’s just Fleur’s and Angio’s that vary. And then you notice it’s just because individual digits are being swapped in those dates: there are not enough constraints in the original puzzle to be able to narrow it down to just the one solution for all three birthdates, hence the need to just produce Gogol’s birthdate.
Verdict: despite the loop of loops, I found this a more interesting puzzle than the previous one because I could apply some analysis to it to improve the code and hence the run time.
Now playing:
Moby - Sunday (The Day Before My Birthday)
(from 18)
Loading links to posts on similar topics...
1 Response
#1 Kris said...
27-Jul-17 12:44 PMKeep 'm coming Julian!
I bought the book 'the lady or the tiger' from Raymond Smullyan the other month. Love logical puzzles, love mathematical puzzles, love every puzzle for that matter ! Tickle the brain.
And Fortran- Oh man- i remember that one,.. 6 or 7 floppies to put it on a pc..We had to program something with the chessboard full of queens without being able to take eachother..
kind regards
K
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