nav[aria-label="Primary Navigation"] { padding: 0; & ul { list-style: none; width: 100%; display: flex; flex-direction: row; justify-content: start; align-items: start; gap: 30px; padding: 0; & li { margin: 0; } & ul li { list-style: none; } } }

Child Item

Combinatorial problem?

oq4v3ht0u76kf2

Apologies for the cross post in both Maths and Programming, but it really is a cross-disciplinary problem.

A friend of mine has given me this problem and it really is wrecking my head. I have a list of 22 distinct 16 digit numbers. They hold within them the clues to one true solution to the code, i.e. the single correct thirteen digit number. My clues are as follows. The number of correct digits for a given code indicates how many digits within that example are correct.

x0: 0 correct digits
x1 - x6: 1 correct digit
x7 - x13: 2 correct digits
x15 - x21: 3 correct digits

For example, a line may be:
3248975391044454 with 2 correct digits

So, let's just assume it's the first two which are correct, the correct code will be:
32ABCDEFGHIJKLMN where A - N are other digits.

I'm absolutely lost trying to find a decent algorithm which will let me solve this question. He assures me that the correcgt algorithm will find a solution in less than twenty minutes on any modern computer. I've been using Python to try and solve the problem.

I cannot devise an algorithm which will allow me to eliminate numbers from each position. I had something I thought would work which basically ran like this:

Guess first X digits from row 1 where X is the number we have been told are correct in row 1
Guess first Y digits from row 2 where Y is the number we have been told are correct in row 2

And so on, until EITHER:

1. Guess is complete and we have our solution
2. Guess cannot go any further (for example, gets to row [i]M[/i] and there are no possible correct values left, where 0 < [i]M[/i] < 20)

My problem lies in the fact that more often than not, we'll get to scenario two as the guess will break unless we are very lucky during our first run... however, when the guess does break, what exactly does this tell me? Was the first number I placed in the guess incorrect? Is the very last number I've guessed? Can I say anything EXCEPT that the EXACT sequence of numbers I have guessed is incorrect? - This seems very brute forcish for something supposedly elegant.

Does anyone have any tips or references I could take a look at? If there's not much interest but anyone really does want to try and tackle this with me, I'm always availabile at rob@robburke.ie but let's try and get a good thread going first!

Find more posts tagged with

Quick Links

Comments

Fremen

Any chance you could post up the numbers and clues? I want a crack at this

I'm not sure I understand your pseudo-code. Are you taking the first X digits from number 1, then then next Y digits from row 2, and joining them up?

Do the correct digits need to be in sequence?

Edit:

They hold within them the clues to one true solution to the code, i.e. the single correct thirteen digit number.

Did you meen sixteen digit number?

Edit #2:
Here's my first stab at an algorithm.

Put the digits of the numbers into a 22X16 matrix
Let row 1 contain the number with no correct digits
Let rows 2 - 7 contain the numbers with 1 correct digit
Let rows 8 - 14 contain the numbers with 2 correct digits
Let rows 15 - 22 contain the numbers with 3 correct digits

Now eliminate all digits known to be incorrect. If a digit in row R, position P matches row zero position P, then set it to NULL

Now, for each non-null entry in row 1:
[Assume this digit is correct. Then all other digits in this row are incorrect. Set all digits in the other rows which agree with incorrect digits in this row to NULL.
Repeat recursively for the next rows. If you reach a stage where all numbers in a given row are set to NULL, then break out of the loop]

Not sure how comprehensible that is, or if it would work.

oq4v3ht0u76kf2

I won't going to post the numbers for now, purely because the construction of the correct algorithm will be irrelevant to the actual numbers. If you really think the numbers are essential I'll post them up asap.

Yes, the correct Code is a sequential sixteen digit number.

Okay, the psuedo-code I wanted to use was this:

1. Get first X digits from row 1 where X is the number of correct digits we have been told row 1 has

2. Set the first X digits of our guess accordingly

3. Mark all other digits in row 1 as incorrect, and similarly eliminate them from other rows where they appear in the same column as they do in row 1

3. Repeat steps 1 and 2 for other rows until either:

3a. We have the sixteen digit code

3b. We can no longer continue as when we get to row [i]M[/i] we no longer have any valid digits left due to our elimination in step 1 [b][i]-> Repeat[/i][/b]

My problem is, when we get to 3b. and need to repeat, how do we eliminate the correcgt numbers? Can we then assume that the very first digit of our Guess is incorrect, is it the very last digit? Or can we 'only' know for definite that the exact combination of numbers in our Guess is incorrect?

Fremen

It looks to me like when we reach step 3b, we have shown that our choice of X digits in row one was wrong, so we assume the next digit of row 1 is correct, etc

Are you an experienced programmer? Are you comfortable working with recursion? It looks like that would be the natural way of programming something like this.