# Generate a valid string

I have been observing her for just over a week now. She had seen me but didn't know she was being watched. As people pass she hands them a piece of paper. Some even stop and put money in a cigar box at her feet. When that happens, I write down the word found in the discarded piece of paper—but I am not perfect, no one is.

The following strings seem to be valid...

GB1XUH
XMATFU
91A6JY
CXSOZQ
KA40A5
WMYMDC
43RM26
7330GE
MOE21I


But the following strings do not seem to be valid...

EPWC4X
YK7JSA
NOS0QZ
GSIG0C
S5QH80
9W2JVM
JN8J2H
STVFSS
PXGSG7


How do I generate a valid string? I am getting desperate, I need that money so much...

Hint:

1 out of 36 random strings is a valid string

• You might want to add some negative cases: without the hint, all strings are valid is a perfectly fine answer Commented Sep 22, 2017 at 8:34
• @boboquack Thank you for your feedback! Edited. Commented Sep 22, 2017 at 8:55
• @JonMarkPerry Thank you for your feedback! Edited. Commented Sep 22, 2017 at 9:50

I am pretty sure this is not an intended solution, I just want to point out that the way the questions is posed is not completely satisfying.

There are a lot of solutions which separate the sets. Let us consider just a simple mapping $f:C \rightarrow \mathbb{Z}_{36}$, where each word is an element in $C^6$ and $(c_1,...c_6) \in C^6$ is evaluated as $\sum f(c_i) \bmod 36$. Here is such a mapping

{'1': 10, '0': 32, '3': 5, '2': 35, '5': 25, '4': 13, '7': 26, '6': 23, '9': 2, '8': 18, 'A': 4, 'C': 3, 'B': 1, 'E': 34, 'D': 20, 'G': 6, 'F': 0, 'I': 15, 'H': 8, 'K': 30, 'J': 2, 'M': 21, 'L': 9, 'O': 29, 'N': 16, 'Q': 17, 'P': 7, 'S': 14, 'R': 11, 'U': 19, 'T': 0, 'W': 12, 'V': 33, 'Y': 31, 'X': 28, 'Z': 17}

which produces an element-wise sum congruent $0 \bmod 36$.

 43RM26 0 7330GE 0 MOE21I 0 GB1XUH 0 XMATFU 0 91A6JY 0 KA40A5 0 WMYMDC 0 CXSOZQ 0 ......... EPWC4X 25 YK7JSA 35 NOS0QZ 17 GSIG0C 4 S5QH80 6 9W2JVM 33 JN8J2H 9 STVFSS 3 PXGSG7 15 

Another is

{'1': 24, '0': 3, '3': 17, '2': 4, '5': 8, '4': 29, '7': 2, '6': 25, '9': 18, '8': 9, 'A': 30, 'C': 13, 'B': 0, 'E': 19, 'D': 33, 'G': 14, 'F': 1, 'I': 16, 'H': 15, 'K': 8, 'J': 6, 'M': 23, 'L': 31, 'O': 22, 'N': 26, 'Q': 20, 'P': 28, 'S': 7, 'R': 10, 'U': 21, 'T': 35, 'W': 11, 'V': 32, 'Y': 5, 'X': 34, 'Z': 12}

This fits with the hint that a randomly chosen string is valid with probability $1/36$.

It is easy to find since most of the strings in the valid set have one or more free variables which can be used to zero out the sum. Just pick a random map for the variables that occur at least twice. Then, pick the remaining ones such that it does not occur in the set (I am assuming here that the map is invertible -- if it is not, the problem is even easier). This requires little bit of iteration. Then check if the invalid strings are all non-zero. Otherwise, repeat.

• ^vote for the analysis. I nonetheless trust there's something particularly interesting about the specifically intended solution.
– humn
Commented Sep 22, 2017 at 22:07