The defective digital clock downside

2024-01-09 16:47:11

You enter the escape room alone, understanding it’s not a good suggestion. Because the door locks, you discover solely two issues within the room: a word and a digital clock.

To unravel the crime
Return in time
It occurred at Midnight
Or so says the wee mite

Why do all escape rooms must be really easy? However as you attain for the clock, a woeful sight strikes your eyes:

“Oh, trouble”, you sigh. Some LED segments are defective, and it is a easy clock, with solely “ahead” buttons to regulate the time. Now you must orient your self round every of the digits, ideally with out looping over too many occasions. As you begin pondering essentially the most environment friendly technique for doing that, you notice it’s too late: you’ve been nerd-sniped. The escape room doesn’t matter, this particular occasion of the issue doesn’t matter – you’re going to jot down a common program to unravel it! Thankfully you at all times carry a pencil, which you promptly apply to the word paper to hack on the downside.

The issue

Given a defective show for a single digit (that’s, a show the place a few of the LED segments are at all times off no matter which digit is displayed), and the power to increment the digit (looping round 9 to 0), we need to “orient across the show”, i.e. iterate by way of the digits till we unambiguously know which digit is presently displayed. For sufficiently defective shows, there may not be a single digit the place the LEDs uniquely establish a single digit. Nonetheless, for the reason that digits are iterated in a set sequence, the issue is sufficiently constrained to be at all times solvable, even with just one practical LED (although this isn’t instantly apparent). On this put up we’ll strategy the issue as a constraint satisfaction downside, particularly utilizing a easy model of constraint propagation.

Let’s observe the next sequence of digits on some defective show:

And let’s uncover the unique digits.

The answer

With out even wanting on the show, we all know it should be displaying one of many digits 0-9. That is our area. Wanting on the preliminary state, we are able to additional constrain the doable values of the digit – for instance, it may possibly’t be 1 because the top-left phase is on. We are able to thus constrain all of the states, however this isn’t sufficient to get to an answer. Nonetheless, there are additionally pairwise constraints between the states, since consecutive states characterize consecutive digits. Because the second state (“Preliminary state + 1”) can’t characterize 1 (equally to the primary state), the primary state can’t be 0, regardless that the LED patterns within the first state are suitable with 0. Due to this fact our technique goes to incorporate discovering the preliminary constraints, after which propagating them alongside the sequence. Word that they work each methods – simply by wanting on the preliminary state we are able to know that the subsequent state isn’t going to be 2.

We’ll begin by assigning an index to every phase:

And proceed by defining for every digit which segments needs to be on:

digits_segments = [
    [1, 1, 1, 0, 1, 1, 1],  # 0
    [0, 0, 1, 0, 0, 1, 0],  # 1
    [1, 0, 1, 1, 1, 0, 1],  # 2
    [1, 0, 1, 1, 0, 1, 1],  # 3
    [0, 1, 1, 1, 0, 1, 0],  # 4
    [1, 1, 0, 1, 0, 1, 1],  # 5
    [1, 1, 0, 1, 1, 1, 1],  # 6
    [1, 0, 1, 0, 0, 1, 0],  # 7
    [1, 1, 1, 1, 1, 1, 1],  # 8
    [1, 1, 1, 1, 0, 1, 0]   # 9
]

We are able to additionally characterize the defective shows of the 4 consecutive states depicted above:

faulty_displays = [
    [0, 1, 0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0, 1, 0]
]

Now we’ll generate the candidates for every state simply through the use of the unary constraints, i.e. for every state ruling out digits which ought to have a phase off that’s turned on in that state.

def get_candidates(display_mask):
    return {
        digit for digit, digit_segments in enumerate(digits_segments)
        if all([digit_segment >= display_segment
                for digit_segment, display_segment
                in zip(digit_segments, display_mask)])
    }

candidates = [get_candidates(display) for display in faulty_displays]
print(candidates)

[{0, 4, 5, 6, 8, 9},
 {0, 4, 5, 6, 8, 9},
 {0, 1, 3, 4, 5, 6, 7, 8, 9},
 {0, 4, 5, 6, 8, 9}]

Appears proper, but in addition removed from an answer.

We’ll now apply the pairwise constraints, in two passes – one ahead and one backward. In every go, we additional constrain every state in response to the possible candidates of the earlier / subsequent state. For enjoyable, we’ll print the candidates after the ahead go, earlier than the backward go.

for i in vary(1, len(candidates)):
    candidates[i] = candidates[i].intersection({(d + 1) % 10
                                                for d in candidates[i - 1]})

print(candidates)

for i in vary(len(candidates) - 2, -1, -1):
    candidates[i] = candidates[i].intersection({(d - 1) % 10
                                                for d in candidates[i + 1]})

print(candidates)

[{0, 4, 5, 6, 8, 9}, {0, 9, 5, 6}, {0, 1, 6, 7}, {8}]
[{5}, {6}, {7}, {8}]

And there we now have our resolution.

Some notes

There’s a small modification we are able to do to make the unary constraints stronger: we are able to hold observe of which LED segments are functioning, and use that info to rule out digits which ought to have a type of segments on (however is off within the show). This for instance will rule out 0, 4, 5, 6, 8, 9 from the third state in our instance.
I believe the formal equal of what most individuals would do is to use the unary constraints, then begin a backtracking search, i.e. guess at some digit based mostly on the unary constraints and see if it suits, and going again as soon as they see a mistake. Backtracking is extensively utilized in constraint satisfaction issues, though on this case constraint propagation was enough. Normally, constraint propagation is utilized earlier than backtracking to make the search house smaller.
That is an very simple constraint propagation downside – it’s extremely constrained, all of the constraints are both unary or binary, and the binary constraints kind a linear graph. For this reason constraint propagation alone is enough to seek out all possible options, and why a easy ahead and backward go are sufficient.
The final downside of constraint satisfaction is NP-complete.
Actual-world use instances of constraint satisfaction issues embrace static language type inference, circuit verification, varied issues in operations research, and extra. There are even layout engines based mostly on constraint solvers.