Nerd-Sniped Myself!
A small aspect of the game “nonograms” captures my attention. Darn it, I was trying to contaminate others, not myself! Also Anti-nerd-sniped.
- TL;DR
-
Possibly interesting recursive solution to N objects in M containers. The usual blather. A late discovery renders the whole idea moot. Proceed or move on, as you prefer.
It was GeePaw Hill who casually mentioned the nonogram game. I checked it out and found it to be an engaging little number game, not so challenging as Sudoku, but just pleasant enough that it triggers your “just one more game” reflex at the end of each game. I’ll leave it to you to look up the game if you’re really interested but the essential notion is that you have a rectangular grid, and each row or column has a one or more numbers as a “hint” for which squares to fill in and which to leave blank. If you were on a row of ten, say, and the hint was 1, 3, 4, you could fill in the row in only one possible way, X_XXX_XXXX. Easy. But of course they aren’t all that easy.
As one plays the game, one comes up with more and more heuristics and rules that help with solutions. Suppose that you have a row of 10 cells and the hint is just 6. At first you might think there was nothing to do with that row until later, when maybe a column would get solved, eliminating some possibilities. But after a while playing, you might notice that if a row of ten has the hint 6, then cells 5 and 6 (starting from 1) must be filled in, no matter where the six is laid down.
So an interesting skill to have is to be able to go from a clue to a set of “forced cells”, I call them, that must be set no matter what, given that rule. And that sounds like something that would be fairly easy to program. So I tossed it out at Hill and he asked if I was daring him, and I said “Of course not”, so he reported that he had a little something, and I realized the problem is very similar if not identical to distributing spaces between words to justify lines, and ne thing you know I was thinking it would be fun to try to code it.
Unfortunately by then I had searched just a bit too much and actually found an algorithm, so my mind is contaminated by a bit too much knowledge of how to do it. But not much too much, because the solutions I found were all recursive, so they did not leap into one’s mind the way they might have.
So today, we’ll try to build a little something that finds the forced cells in a row or column. Let’s see if I can remember how to set up PyCharm.
- Start new project with a name “nono”.
- Add two packages, “src” and “tst”.
- Put a test under tst:
import pytest
class TestNono:
def test_hookup(self):
assert False
Run the file, see it fail. Change False to True, see it pass.
OK, maybe we’re set up. Now we need a test for something relating to the problem. This suggests that we need to think about how we’re going to solve it.
My basic picture of the problem using the 6 on 10 example, is that we will generate all possible arrangements, like this:
XXXXXX____
_XXXXXX___
__XXXXXX__
___XXXXXX_
____XXXXXX
Then we want to sort of “and” those together, keeping an X in any column that contains an X in every case. And that led me to the notion of creating an actual bitmap and literally anding them together:
1111110000
0111111000
0011111100
0001111110
0000111111
---------- and
0000110000 voila!
Then we might work from the 0/1 picture, or convert it back to X’s or whatever. So I’m kind of in love with the idea of bitmaps and anding them together.
When there is a pattern involving more than one number, such as “2 3”, there is a requirement for at least one space between the XX and the XXX, since otherwise it would be a five, XXXXX, not a two and a three.
I’m thinking that if there are N numbers in the clue, there are N+1 places where we can insert spaces, the N-1 spaces between the items, and the two end slots. Also, a little thinking (the only kind I have) tells us that if the sum of the numbers in the clue, plus the number of items, minus one, equals the length of the line, there is only one way for it to go. We might want to check for that, although a decent algorithm would just work. We will perhaps need to detect cases where the sum of the numbers won’t fit. I’ve never found a game with an error in it, but I could certainly incorrectly transcribe the clue. We’ll see. We’re here to be nerd-sniped, not to build a product.
At the ends, we can insert zero or more spaces. In between words, there must be at least one space. While musing yesterday, I was thinking about line justification, trying to remember how I did that, because I’m sure I’ve coded it at least once, I sort of decided that I’ll treat the segments as if all but the last one actually includes a space, so that clue 2, 3, 2 has us processing something like this:
[XX_, XXX_, XX]
Of course it is clear that much of our algorithm doesn’t care about the lengths of the words, only about the number of slots into which we want to insert spaces. We’ve identified that number as the number of hints plus one.
The number of spaces we have to allocate, N, will be the difference between the length of the puzzle line and the minimum number of cells required by the pattern, that is, the sum of its hints plus the number of hints, minus one. And the number of slots into which we can insert spaces is M, equal to the number of hints plus 1.
So the problem comes down to enumerating all the ways that N spaces can be allocated among M slots. And, of course, to devising tests for our algorithm, ideally tests that drive out the code. But the problem here is that for this code, I need to build up at least a theory about how it’s going to work. I suppose we can just create some examples. I’ll try a couple of easy ones:
I started by laying out a 3 on 3 test but then did a 3 on 2 and then finally a 1 on 2. My tests, so far, look like this:
def test_allocate_1_2(self):
spaces = 1
slots = 2
result = [ [0, 1], [1, 0]]
def test_allocate_3_2(self):
spaces = 3
slots = 2
result = [[0, 3], [1, 2], [2, 1], [3, 0]]
def test_allocate_3_3(self):
spaces = 3
slots = 3
result = [
[3, 0, 0],
[2, 1, 0], [2, 0, 1],
[1, 2, 0], [1, 0, 2], [1, 1, 1],
[0, 3, 0], [0, 2, 1], [0, 1, 2], [0, 0, 3]
]
I’m not sure of the last one but it looks right. I haven’t come up with a scheme for producing them by hand, much less by code. But the pattern reminds me of counting. It’s not base ten or base 2, except in the first case which does look a lot like base 2.
Let’s try one or two more easy ones, try to get the pattern.
def test_allocate_1_1(self):
spaces = 1
slots = 1
result = [ [1] ]
def test_allocate_1_2(self):
spaces = 1
slots = 2
result = [ [0, 1], [1, 0]]
def test_allocate_2_2(self):
spaces = 2
slots = 2
result = [[0, 2], [1, 1], [2, 0]]
def test_allocate_3_2(self):
spaces = 3
slots = 2
result = [[0, 3], [1, 2], [2, 1], [3, 0]]
def test_allocate_3_3(self):
spaces = 3
slots = 3
result = [
[3, 0, 0],
[2, 1, 0], [2, 0, 1],
[1, 2, 0], [1, 0, 2], [1, 1, 1],
[0, 3, 0], [0, 2, 1], [0, 1, 2], [0, 0, 3]
]
I’d swear that’s some kind of counting, base N = the number of spaces. I’ll rearrange the last one to be like the others.
Belay that. Let’s look at it another way. We want a function that we can call with the numbers in those tests and get back the same result. (Net of order, we’ll have to deal with that.)
Function is allocate(n_spaces, m_containers). Let’s do some cases. If there is only one container, all the spaces go into that one. I change the result names to expected and do this much:
class TestNono:
def allocate(self, spaces, slots):
return []
def test_allocate_1_1(self):
spaces = 1
slots = 1
actual = self.allocate(spaces, slots)
expected = [ [1] ]
assert expected == actual
Test fails, of course. Let’s do some special cases for a while. If there is only one slot, the entire n goes in there:
def allocate(self, spaces, slots):
if slots == 1:
return [ [spaces] ]
return []
First test passes. Let’s test what happens if we have no spaces to allocate across however many slots. That’s the case where the hint exactly fills the line, if I’m not mistaken. We’ll return one case, showing three slots, each with a zero entry.
def test_allocate_0_3(self):
spaces = 0
slots = 3
actual = self.allocate(spaces, slots)
expected = [ [0, 0, 0] ]
assert expected == actual
And the special case:
def allocate(self, spaces, slots):
if slots == 1:
return [ [spaces] ]
if spaces == 0:
return [ [0] * slots ]
return []
Two tests passing out of two that have assertions. Life is good. Well, sort of good, because now we have to actually solve something.
OK, let’s try the 1_2 case:
def test_allocate_1_2(self):
spaces = 1
slots = 2
expected = [ [0, 1], [1, 0]]
actual = self.allocate(spaces, slots)
assert expected == actual
This will fail now on an empty list, the default answer.
Expected :[]
Actual :[[0, 1], [1, 0]]
So far so good. I think we’d like to solve this recursively. I suppose that in allocate(n, m), we should do something and then call allocate with smaller values. That will sooner or later get down to where one of the special cases will return a constant value. I confirm what’s going on with this new test, which passes:
def test_allocate_0_1(self):
spaces = 0
slots = 1
actual = self.allocate(spaces, slots)
expected = [ [0] ]
assert actual == expected
So suppose we’re inside allocate with slots = 2, so we have to come up with two results. Let’s suppose that we have an accumulating collection to add things to, and that we return it at the end. It’ll look like this:
def allocate(self, n_spaces, m_slots):
if m_slots == 1:
return [[n_spaces]]
if n_spaces == 0:
return [([0] * m_slots)]
accumulating_allocations = []
# a miracle occurs here
return accumulating_allocations
I renamed the parameters because saying there were spaces spaces and slots slots to deal with wasn’t going to help my prose any. We’ll refer to them as N and M below, with—I hope—the obvious choices.
Somewhere inside the miracle, we’ll call allocate with smaller figures, so that we can add our level’s info to the situation. Ah. There are N spaces to allocate so we’ll produce a new allocation for each possibility for the current slot, 0 through N, and prepend those to the existing allocations from the previous level, which will have all the allocations for all the preceding slots. Like this:
def allocate(self, n_spaces, m_slots):
if m_slots == 1:
return [[n_spaces]]
if n_spaces == 0:
return [([0] * m_slots)]
accumulating_allocations = []
for number_allocated in range(n_spaces+1):
prior_allocations = self.allocate(n_spaces-number_allocated, m_slots-1)
for allocation in prior_allocations:
accumulating_allocations.append([number_allocated] + allocation)
return accumulating_allocations
OK, that came out of the blue a bit, but my reasoning got me there:
- We’ll have n+1 possible allocations for every slot, 0 through n_spaces.
- We have some number of allocations for prior (smaller) situations,
- We produce a new allocation for each value zero through n_spaces,
- We prepend our allocation to the proper set of allocations for the number of spaces we have, minus the number we use up at this level. If we have N to get rid of and we allocate 0 to our position, then we have to allocate N to the remaining slots, M-1. If we allocate 1 to our position, we have to allocate N-1 to the remaining M-1 positions.
- In general, if we choose to allocate k at this level, we must allocate N-k to the M-1 remaining slots.
- And that is our recursive call.
Weird. Let me try to explain from another angle:
We assume by the recursion step that we have an allocation for the preceding smaller number of slots. That allocation will have as its n_spaces, the total number of spaces (n_spaces) minus the ones we plan to allocate here. So, for each of those prior allocations, we prepend our chosen number and add it to our output list. When we have done all the n_spaces, we return our new larger list.
My test passes. This may be it. Let’s turn on the others. They all pass. Here they are, together with the allocate function:
class TestNono:
def allocate(self, n_spaces, m_slots):
if m_slots == 1:
return [[n_spaces]]
if n_spaces == 0:
return [([0] * m_slots)]
accumulating_allocations = []
# a miracle occurs here
for number_allocated in range(n_spaces+1):
prior_allocations = self.allocate(n_spaces-number_allocated, m_slots-1)
for allocation in prior_allocations:
accumulating_allocations.append([number_allocated] + allocation)
return accumulating_allocations
def test_allocate_0_1(self):
spaces = 0
slots = 1
actual = self.allocate(spaces, slots)
expected = [ [0] ]
assert expected == actual
def test_allocate_1_1(self):
spaces = 1
slots = 1
actual = self.allocate(spaces, slots)
expected = [ [1] ]
assert expected == actual
def test_allocate_0_3(self):
spaces = 0
slots = 3
actual = self.allocate(spaces, slots)
expected = [ [0, 0, 0] ]
assert expected == actual
def test_allocate_1_2(self):
spaces = 1
slots = 2
expected = [ [0, 1], [1, 0]]
actual = self.allocate(spaces, slots)
assert expected == actual
def test_allocate_2_2(self):
spaces = 2
slots = 2
actual = self.allocate(spaces, slots)
expected = [[0, 2], [1, 1], [2, 0]]
assert expected == actual
def test_allocate_3_2(self):
spaces = 3
slots = 2
actual = self.allocate(spaces, slots)
expected = [[0, 3], [1, 2], [2, 1], [3, 0]]
assert expected == actual
def test_allocate_3_3(self):
spaces = 3
slots = 3
actual = self.allocate(spaces, slots)
expected = [
[0, 0, 3],
[0, 1, 2], [0, 2, 1],
[0, 3, 0], [1, 0, 2], [1, 1, 1],
[1, 2, 0], [2, 0, 1], [2, 1, 0], [3, 0, 0]
]
assert expected == actual
Time for a well-deserved break and a nice iced chai latte. We’ll do some grunt work to get the actual answers later today. Or not.
Later That Day …
Let’s see about using our new space allocator, since it seems to work. I still think there is some kind of enumeration going on there, but let’s get to wrapping it in what we need. What do we need, anyway?
We’ll begin with a nonogram hint, a series of small integers representing X’d parts. We’ll need to derive n_spaces and m_slots. The number of slots needed is the number of items in the hint, plus one. The number of extra spaces is the sum of the individual hint values, plus the number of values, minus one. Unless I’ve counted incorrectly on my fingers.
Given those we can derive the various allocations, and from those we’ll create a binary string. Each number in the allocation will be converted to a string of that many zero bits, and the hint numbers will be converted to the hint number plus one one bits, representing the extra spaces, except that the last one we don’t give an extra space to.
We need some tests.
def test_get_n_spaces_and_m_slots(self):
hint = [2, 3, 4]
line = 13
n_spaces, m_slots = self.get_spaces_and_slots(hint, line)
assert n_spaces == 2
assert m_slots == 4
And this makes it pass:
def get_spaces_and_slots(self, hints, line_size):
n_spaces = line_size - (sum(hints) + len(hints) - 1)
m_slots = len(hints) + 1
return n_spaces, m_slots
I’ll try another one but I am just transcribing my theory to the code so it’s not much of a test yet. Oh let me generate one that should produce the same as the big example above.
def test_hint_gets_proper_list(self):
hints = [5, 7]
line_size = 16
n_spaces, m_slots = self.get_spaces_and_slots(hints, line_size)
actual = self.allocate(n_spaces, m_slots)
expected = [
[0, 0, 3],
[0, 1, 2], [0, 2, 1],
[0, 3, 0], [1, 0, 2], [1, 1, 1],
[1, 2, 0], [2, 0, 1], [2, 1, 0], [3, 0, 0]
]
assert expected == actual
That passes. So that’s nice.
Let’s see about making some binary strings. Suppose we have a hints collection and one allocation and we want the bits. I’ll write a test for that.
def test_bits(self):
hints = [5, 6, 7]
allocation = [1, 2, 3, 4]
expected = 0b011111100111111100011111110000
actual = self.make_bits(hints, allocation)
err_msg = f'\nexpected {expected:032b}\nactual {actual:032b}'
assert expected == actual, err_msg
I had to add the err_msg because pytest’s error display was showing me the numbers in decimal, which was not as helpful as it might have been. After a bit of bit-fiddling, I have this, which passes the test:
def make_bits(self, hints, allocation):
bits = 0
for i, a in enumerate(allocation):
bits = bits << a
if i < len(hints):
hint = hints[i]
if i < len(hints) - 1:
hint += 1
for _ in range(hint):
bits <<= 1
bits |= 1
return bits
I have worn out my eyeballs and we have FGNO Zoom tonight, so I’ll take a break now. Good progress, though, the problem is essentially solved.
Anti-Nerd-Sniped?
Last night, GeePaw Hill asserted in a private communication that if we have an empty line and a hint pattern, and we place the compact pattern all the way to the left, and all the way to the right, the cells then shown in common are all the forced cells there can be.
My experience suggested that this was true, but I couldn’t quite see why. Now I do, and it goes like this:
- Because the pattern is placed all the way to the left, there can be no further forced cells to the left. (There are no cells to the left.)
- Similarly, when it is placed to the right, there are no possible additional forced cells to the right.
- Because no additional pattern can ever force a cell not covered by these two, whatever cells they both cover are the only forced cells. (Covered cells are
anded together, notored.)
So that’s fine, after I’ve generated all possible configurations of the pattern that can possibly exist. My purpose was to find forced cells, which can be done far more easily than I’ve done here.
Perhaps all is not lost. If we were to ever want to write a brute force solver, what we’ve done here might be a part of that. We don’t want to do that, but if we did …
And you never know when you might want to know all the ways FedEx might deliver your N packages given that they have M trucks that come to your neighborhood. Our code would work for that. Swell. Super. Outstanding.
Perhaps in a day or week or month or so I’ll revisit the game of Nonogram, or the problem of allocating N candy bars among M housemates. Until then, well, it was an interesting diversion.
Such is the life of a nerd.