#Pyth, 122 - 20 - 15 = 87
=Z/lzQ=ks^lz.5Jm]dUzL[-bk+bk?tb%bkb?hb%hbkb)FNJIgNZB~Jm+NksmybN;|jbS{msm+@zk@S*Z<GQxsdkUzfqSsTUz^fqsmv@*ZzbY/smvdzQJQ"None
Changes:
130 -> 120: Switched to newline separated input.
120 -> 134: Fixed a bug involving groups not of size equal to the side length of the matrix.
134 -> 120: Prints all solutions, including ones equivalent under group renaming.
120 -> 122: Fixed a bug where only paths would be generated, instead of all legal groups.
Test run:
pyth programs/sum_group.pyth <<< '156790809
3'
1a5a6b7c9a0b8c0c9b
1a5a6c7b9a0c8b0b9c
1b5b6a7c9b0a8c0c9a
1b5b6c7a9b0c8a0a9c
1c5c6a7b9c0a8b0b9a
1c5c6b7a9c0b8a0a9b
pyth programs/sum_group.pyth <<< '156790808
3'
None
pyth programs/sum_group.pyth <<< '1111
2'
1a1a1b1b
1a1b1a1b
1b1a1b1a
1b1b1a1a
Explanation:
Pyth code (Pseudo)-Python code Comments
(implicit) z = input() z is the digit string
(implicit) Q = eval(input()) S is the number of groups
(implicit) G = 'abcdefghijklmnopqrstuvwxyz'
=Z/lzQ Z = len(z)/Q Z is the size of each group.
=ks^lz.5 k = int(len(z) ** .5) k is the side length of the matrix.
Jm]dUz J = map(lambda d:[d], range(len(z))) Locations are encoded as numbers.
L def y(b): return y will be the transition function.
[-bQ [b-k, Move up - the row above is k less.
+bQ b+k, Move down - the row below is k more.
?tb%bkb b-1 if b%k else b Move left, unless at the left edge.
?hb%hbkb) b+1 if (b+1)%k else b] Move right, unless at right edge.
FNJ for N in J: This constructs the list of all
IgNZB if N[Z-1]: break Z-length connected groups.
~Jm+Nk J+=map(lambda k: N+[k], Append to J the group of N +
smybN sum(map(lambda b: anything reachable from
y(b),N))) anywhere in N.
; (end for)
| or Print first truthy thing between
S{ sorted(set( Unique elements in sorted order of
ms map(lambda b:sum( Map+sum over allowable combinations
m+@zd map(lambda d:z[d]+ Character in original digit string
@S*Z<GQ sorted(G[:Q]*Z)[ Repeated and sorted early alphabet
xsbd sum(b).index(d)], At index of number in sum of groups
Uz range(len(z))) Over possible indexes.
f filter(lambda T: To generate allowable combinations,
we will filter all groups of Q paths.
qSsTUz sorted(sum(T)) == range(len(z)) Ensure all locations are visited.
^ Combinations of
f filter(lambda Y: Filter over connected Z-length groups
qsm equal(sum(map(lambda k: Sum of the values of the group
v@*ZzkY eval((z*Z)[k]),Y) In the original digit string
/smvbzQ sum(map(lambda b:eval(b),z))/Q must equal the sum of all values in z
divided by the number of groups.
J J Filter over connected Z-length groups
Q Q Combinations of length Q
"None "None" If the above was empty, print "None"