Routine maintenance visit. Looks like a “Reggie” comes by this way with his dogs and signs the logbook, sometimes! :-) Not such a forgotten footbridge after all?
I’ve been working in Witney one day every week or two lately, but somehow I’ve never managed to sync up my work times with the hours that this building is accessible! Or, when I do, I’m in a hurry and don’t have time to stop and hunt!
This morning, though, the stars aligned and I was able to get to the GZ. The cache was pretty much where I expected based on the coordinates and the hint, but still took a minute out two to lay hands on. Soon, though, I was quietly sitting and reading past log entries.
SL TFTC! FP awarded for sheer awesome.
GPSr was all over the place, but the hint quickly sent me to the obvious hiding place. SL, TFTC.
A pair of walkers who’d stopped at the GZ for a snack made searching difficult, plus the geodog isn’t very good at stealth, so we had to give up on our search for this one. Maybe on the way back. (Although as I write this I see they’re coming the same direction as us; might need stealth again yet!)
This cache’s container is likely to go on to make an appearance as GC9Z37H Friar’s Farm – Woodland Walk.
That’s a really useful thing to have in this new age of the web, where
Refererer: headers are no-longer commonly passed cross-domain and Google Search no longer provides the
link: operator. If you want to know if I’ve ever
linked to your site, it’s a bit of a drag to find out.
So, obviously, I’ve written an implementation for WordPress. It’s really basic right now, but the source code can be
found here if you want it. Install it as a plugin and run
wp outbound-links to kick it off. It’s fast: it takes 3-5 seconds to parse the entirety of danq.me,
and I’ve got somewhere in the region of 5,000 posts to parse.
You can see the results at https://danq.me/.well-known/links – if you’ve ever wondered “has Dan ever linked to my site?”, now you can find the answer.
If this could be useful to you, let’s collaborate on making this into an actually-useful plugin! Otherwise it’ll just languish “as-is”, which is good enough for my purposes.
This blog post is also available as a video. Would you prefer to watch/listen to me tell you about how I’ve implemented a tool to help me beat the kids when we play Mastermind?
I swear that I used to be good at Mastermind when I was a kid. But now, when it’s my turn to break the code that one of our kids has chosen, I fail more often than I succeed. That’s no good!
Mastermind and me
Maybe it’s because I’m distracted; multitasking doesn’t help problem-solving. Or it’s because we’re “Super” Mastermind, which differs from the one I had as a child in that eight (not six) peg colours are available and secret codes are permitted to have duplicate peg colours. These changes increase the possible permutations from 360 to 4,096, but the number of guesses allowed only goes up from 8 to 10. That’s hard.
Or maybe it’s just that I’ve gotten lazy and I’m now more-likely to try to “solve” a puzzle using a computer to try to crack a code using my brain alone. See for example my efforts to determine the hardest hangman words and make an adverserial hangman game, to generate solvable puzzles for my lock puzzle game, to cheat at online jigsaws, or to balance my D&D-themed Wordle clone.
Hey, that’s an idea. Let’s crack the code… by writing some code!
Representing a search space
The search space for Super Mastermind isn’t enormous, and it lends itself to some highly-efficient computerised storage.
There are 8 different colours of peg. We can express these colours as a number between 0 and 7, in three bits of binary, like this:
There are four pegs in a row, so we can express any given combination of coloured pegs as a 12-bit binary number. E.g.
100 110 111 010 would represent the
permutation blue (
100), purple (
110), white (
111), yellow (
010). The total search space, therefore, is the range of numbers from
111111111111… that is: decimal 0 through 4,095:
||Red, red, red, red|
||Red, red, red, orange|
||Red, red, red, yellow|
||White, white, white, blue|
||White, white, white, pink|
||White, white, white, purple|
||White, white, white, white|
Whenever we make a guess, we get feedback in the form of two variables: each peg that is in the right place is a bull; each that represents a peg in the secret code but isn’t in the right place is a cow (the names come from Mastermind’s precursor, Bulls & Cows). Four bulls would be an immediate win (lucky!), any other combination of bulls and cows is still valuable information. Even a zero-score guess is valuable- potentially very valuable! – because it tells the player that none of the pegs they’ve guessed appear in the secret code.
representing the guess as shown below. Decoding uses an AND bitmask to filter to the requisite digits then divides by the order of magnitude. Encoding is just a
function that bitshift-concatenates the numbers together.
With this, we can simply:
- Produce a list of candidate solutions (an array containing numbers 0 through 4,095).
- Choose one candidate, use it as a guess, and ask the code-maker how it scores.
- Eliminate from the candidate solutions list all solutions that would not score the same number of bulls and cows for the guess that was made.
- Repeat from step #2 until you win.
Step 3’s the most important one there. Given a function
getScore( solution, guess ) which returns an array of
[ bulls, cows ] a given
score if faced with a specific
solution, that code would look like this (I’m convined there must be a more-performant way to eliminate candidates from the list with XOR
bitmasks, but I haven’t worked out what it is yet):
I continued in this fashion to write a full solution (source code). It uses ReefJS for component rendering and state management, and you can try it for yourself right in your web browser. If you play against the online version I mentioned you’ll need to transpose the colours in your head: the physical version I play with the kids has pink and purple pegs, but the online one replaces these with brown and black.
Testing the solution
Let’s try it out against the online version:
As expected, my code works well-enough to win the game every time I’ve tried, both against computerised and in-person opponents. So – unless you’ve been actively thinking about the specifics of the algorithm I’ve employed – it might surprise you to discover that… my solution is very-much a suboptimal one!
My solution is suboptimal
A couple of games in, the suboptimality of my solution became pretty visible. Sure, it still won every game, but it was a blunt instrument, and anybody who’s seriously thought about games like this can tell you why. You know how when you play e.g. Wordle (but not in “hard mode”) you sometimes want to type in a word that can’t possibly be the solution because it’s the best way to rule in (or out) certain key letters? This kind of strategic search space bisection reduces the mean number of guesses you need to solve the puzzle, and the same’s true in Mastermind. But because my solver will only propose guesses from the list of candidate solutions, it can’t make this kind of improvement.
Search space bisection is also used in my adverserial hangman game, but in this case the aim is to split the search space in such a way that no matter what guess a player makes, they always find themselves in the larger remaining portion of the search space, to maximise the number of guesses they have to make. Y’know, because it’s evil.
There are mathematically-derived heuristics to optimise Mastermind strategy. The first of these came from none other than Donald Knuth (legend of computer science, mathematics, and pipe organs) back in 1977. His solution, published at probably the height of the game’s popularity in the amazingly-named Journal of Recreational Mathematics, guarantees a solution to the six-colour version of the game within five guesses. Ville  solved an optimal solution for a seven-colour variant, but demonstrated how rapidly the tree of possible moves grows and the need for early pruning – even with powerful modern computers – to conserve memory. It’s a very enjoyable and readable paper.
But for my purposes, it’s unnecessary. My solver routinely wins within six, maybe seven guesses, and by nonchalantly glancing at my phone in-between my guesses I can now reliably guess our children’s codes quickly and easily. In the end, that’s what this was all about.
This blog post is also available as a video. Would you prefer to watch/listen to me tell you about not being a “dog person”, but still loving one dog in particular?
I am not a “dog person”. I’m probably more of a “cat person”.
My mum has made pets of one or both of dogs or cats for most of her life. She puts the difference between the two in a way that really resonates for me. To paraphrase her:
When you’re feeling down and you’ve had a shitty day and you just need to wallow in your despair for a little bit… a pet dog will try to cheer you up. It’ll jump up at you, bring you toys, suggest that you go for a walk, try to pull your focus away from your misery and bring a smile to your face. A cat, though, will just come and sit and be melancholy with you. Its demeanour just wordlessly says: “You’re feeling crap? Me too: I only slept 16 hours today. Let’s feel crap together.”
So it surprised many when, earlier this year, our family was expanded with the addition of a puppy called Demmy. I guess we collectively figured that now we’d solved all the hard problems and the complexities of our work, volunteering, parenting, relationships, money etc. and our lives were completely simple, plain sailing, and stress-free, all of the time… that we now had the capacity to handle adding another tiny creature into our midst. Do you see the mistake in that logic? Maybe we should have, too.
It turns out that getting a puppy is a lot like having a toddler all over again. Your life adjusts around when they need to sleep, eat, and poop. You need to put time, effort, and thought into how to make and keep your house safe both for and from them. And, of course, they bring with them a black hole that eats disposable income.
They need to be supervised and entertained and educated (the latter of which may require some education yourself). They need to be socialised so they can interact nicely with others, learn the boundaries of their little world, and behave appropriately (even when they’re not on camera).
Even as they grow, their impact is significant. You need to think more-deeply about how, when and where you travel, work out who’s responsible for ensuring they’re walked (or carried!) and fed (not eaten!) and watched. You’ve got to keep them safe and healthy and stimulated. Thankfully they’re not as tiring to play with as children, but as with kids, the level of effort required is hard to anticipate until you have one.
But do you know what else they have in common with kids? You can’t help learning to love them.
It doesn’t matter what stupid thing they’re illicitly putting in their mouth, how many times you have to clean up after them, how frustrating it is that they can’t understand what you need from them in order to help them, or how much they whine about something that really isn’t that big a deal (again: #PuppyOrToddler?). It doesn’t even matter how much you’re “not a dog person”, whatever that means. They become part of your family, and you fall in love with them.
I’m not a “dog person”. But: while I ocassionally resent the trouble she causes, I still love our dog.
Surprisingly easy find! I got up earlier than most of the festival campers this morning to do the canalside series and then, figuring I had time, decided to tackle this multi too. Little did I know I’d end up retracing my steps to find this one – I’d passed the final coordinates twice this morning already!
At the GZ I first thought I’d have no chance – that the cache would be too well-concealed among the foliage. But despite the container’s camo I caught sight of it almost instantly. Easy peasy! TFTC.
Think the bench must be inside the marquee pictured, based on the coordinates. I got my festival breakfast in the yesterday but didn’t think to look for the bench – whoops! All sealed up this morning as the festival campers have a post-party lie in and Cropredy life begins to pivot back towards normal. Never mind!
Finding the cache while avoiding strange looks from the boaters using the lock was relatively easy: I just sat down and did some stretches to give me an excuse to peep into the likely hiding places. Retrieving it while in stealth mode was harder, but luckily I’m wearing laced shoes. TFTC!