Your task is, given a square grid of digits (
0-9), output one of the ways that the digits can be grouped such that:
- Each digit is part of exactly one group
- All groups have the same number of digits
- All groups are bounded by one polygon-like shape (this means that every digit in the group is next to [left, right, up, down] at least one other digit of the same group, unless each group has 1 element).
- All groups have the same sum
The input grid will always be a square: You may choose any input method you would like (including supplying arguments to a function or method). In addition, the input will supply the number of groups that your program should group the digits into.
Suppose your input format is
An example input would be:
which would translate to (a grid of
sqrt(9) * sqrt(9))
1 5 6 7 9 0 8 0 9
which you would have to divide into 3 groups, each of which should have
9 / 3 = 3 elements with the same sum.
Output should be the string of digits, with optional spaces and newlines for formatting, with each digit followed by a letter
a-z indicating its group. There should be exactly
numberOfTotalDigits / numberOfGroups elements in each group. You will never have to divide something into more than 26 groups.
1a 5a 6b 7c 9a 0b 8c 0c 9b
Note that replacing all
as is equally valid. As long as each group is denoted by a distinct letter, the output is valid.
In addition, I expect most programs to output something along the lines of this, because newlines/spaces are optional:
In this case, adding all digits of group
c makes 15. In addition, all groups are bound by some polygon.
1a 5a 6b 7c 9a 0c 8c 0b 9b
because the groups do not form polygons (specifically, the
6b is isolated and
0c is also lonely).
1a 5a 6b 7c 9a 0b 8c 0b 9b
because the group
b has 4 elements while
c only has 2.
If there is no valid solution, your program may do anything (i.e. stop, crash, run forever) but if your program prints
None when there is no valid solution,
-15 to your score.
If there is more than one solution, you only have to print one, but
-20 if your program prints all of them separated by some delimiter.
This is code golf, so shortest code (with bonuses) wins!