6
\$\begingroup\$

Background

I was working on a system where for convenience (not security) people could use four digit codes to identify themselves. I figured this is something that may actually be useful in many real cases, yet is well enough defined that it could make a nice challenge!

Explanation of pin codes and typo resistant sets

EDIT: Based on the comments, this is probably a more formal definition:

I think a mathematical way of specifying what you are looking for is a maximal set of strings with length 4 over the alphabet {0,1,2,3,4,5,6,7,8,9} with minimum pairwise hamming distance 2, if it helps others.

There are 10000 possible pin codes (0000-9999).

Example pin code

1234

However, since a typo is easily made you are to generate a set of pincodes that is resistant to a single typo.

Example of set that is NOT resistant to single typo:

0000
0005 (if you mistype the last digit as 0 instead of 5, you get another code in the set)

Example of set that IS resistant to single typo

0000
0011
0101
0202

Allowed outputs

The allowed output can be a bit flexible, specifically:

  • A pincode may be a string or a number
  • You may always have separators (e.g. comma, newline), however if your codes are always represented as 4 digits separators are optional
  • The codes should be represented by 0-9, not other characters

Example sets:

0011,0022: OK
00220011: OK
11,22,33: OK
112233: NOT OK
abcd,abef: NOT OK
{'1111',/n'2222'}: OK

Scoring system

The primary score is the number of unique pin codes generated (note that 0001,1000 would count as 2).

Edit: If your code does not always generate the same amount of unique pin codes you must estimate the amount it will at least generate in 95% of the cases and you may use that as your score. So for example if you uniformly randomly generate between 300 and 400 unique pincodes, your score would be 395.

In case there is a tie, the shortest code wins!

Please post your score as: Language, #Unique codes generated with bytes (e.g. Python, 30 codes generated with 123 bytes)

(I guess formally this could be rewritten to 'generate X typo resistant pin codes' but as I have no idea what X is I will keep it like this, this also allows simpler solutions to compete against each other on lenght for 'third place' and beyond.)

In principle no inputs are needed and for simplicity sake I will not make it part of the challenge and scoring, but it would be interesting to see how the code would need to be changed to allow for various length pin codes.

Improve this question
\$\endgroup\$
15
  • 1
    \$\begingroup\$ Please define precisely what a "typo" is. Why is 0005 -> 0000 not allowed, but 0011 -> 0000 is? \$\endgroup\$
    – pxeger
    Jul 10 at 6:11
  • 3
    \$\begingroup\$ I think a mathematical way of specifying what you are looking for is a maximal set of strings with length 4 over the alphabet {0,1,2,3,4,5,6,7,8,9} with minimum pairwise hamming distance 2, if it helps others. \$\endgroup\$
    – Sisyphus
    Jul 10 at 6:15
  • 4
    \$\begingroup\$ @DennisJaheruddin Ah I understand now. It wasn't at all clear to me that the aim was to find pin codes where making a typo couldn't accidentally produce another valid code. I thought the aim was to allow the code whether or not a typo was made. \$\endgroup\$
    – pxeger
    Jul 10 at 7:55
  • 3
    \$\begingroup\$ If your code does not always generate the same amount of unique pin codes you must estimate the amount it will at least generate in 95% of the cases -> This can't be easily verified. I think the output should be deterministic. It would not prevent from using a random search with a well chosen seed. \$\endgroup\$
    – Arnauld
    Jul 10 at 12:53
  • 3
    \$\begingroup\$ A proof 1000 is optimal: drop the last digit from all PINs. All the resultant PINs must be unique (otherwise there's a pair with distance 1). There are 1000 unique PINs with length 3. \$\endgroup\$
    – Command Master
    Jul 10 at 13:34

7 Answers 7

Reset to default
11
\$\begingroup\$

Python 2, 1000 unique pin codes, 44 bytes

i=0;exec'print i+int(`i`,11)%10;i+=10;'*1000

Try it online!

I suspect 1000 pin codes is optimal. You can check the verification program.

How was this discovered?

The process for discovering this rather simple formula was quite messy for me. The first insight I had was that you can transform this into a graph problem - let the PIN numbers be nodes and connect edges if and only if the hamming distance between the PIN numbers is greater than 1. Then the problem boils down to finding a maximum clique of the graph. From reading some papers apparently there was a simple C program available in the web archive that solves the maximal clique problem for small instances, so I downloaded it (and patched it a little bit since it doesn't compile on a modern compiler). I wrote a simple driver program to generate input in the format it expected and ran it. It was too slow for the full problem but I noticed something odd about its output for smaller instances:


...
level = 9997(10000) best = 100 time =     0.65
level = 9998(10000) best = 100 time =     0.65
level = 9999(10000) best = 100 time =     0.65
level = 10000(10000) best = 100 time =     0.65
Record: 9 10 21 32 43 54 65 76 87 98 100 111 122 133 144 155 166 177 188 199 201 212 220 234 245 253 267 278 289 296 302 313 324 330 341 356 368 379 385 397 403 414 425 431 447 458 469 470 486 492 504 515 526 537 548 559 560 571 582 593 605 616 623 638 649 657 661 672 680 694 706 717 728 739 740 751 762 773 784 795 807 818 829 835 846 852 863 874 881 890 908 919 927 936 942 950 964 975 983 991

For the first 1000 PINs, the optimal clique had 100 nodes, which suspiciously looks like just the number of PINs divided by 10. And also, every prefix from 000..099 appeared once. This led me to hypothesize that there was some closed form solution of the form:

10 * i + f(i) % 10

It looks like f is almost just f(i) = i but occasionally it jumps some extra.

After toying around a little bit, I came across the formula (i + i / 10 + i / 100) % 10, which passes. But (i + i / 10 + i / 100) % 10 is just int(str(i), 11) % 10, that is, reinterpreting the digits of i in base 11! This gives the final answer.

Improve this answer
\$\endgroup\$
1
  • 4
    \$\begingroup\$ Nice solution! You probably noticed this already, but your numbers are those where the last digit equals the sum of the remaining digits mod 10. Another set are the numbers whose digits add to a multiple of 10 though those seem longer to generate. It makes sense for both these sets why changing any digit must ruin the property. For base 2, both the corresponding sets are the Evil Numbers. \$\endgroup\$
    – xnor
    Jul 10 at 8:51
8
\$\begingroup\$

05AB1E, 1000 codes generated with 7 bytes

9Ý4ãʒOθ

Try it online!

Works using the observation that you can append any function \$ f(a, b, c) \$ to all 3-digit PINs \$ abc \$ iff after fixing two of the variables you get a permutation - no value appears more than once. This code uses \$ f(a, b, c) = (1 - a - b - c) \mod 10 \$, which is equivalent to the statement that the last digit of the PIN's digit sum is 1.

9Ý     push [0, 1, 2, ..., 9]
4ã     push the fourth cartesian power, all choices of four values from the above list
ʒ      keep only elements for which the following returns 1
 O     sum all values
 θ     take the last digit of the sum
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

K (ngn/k), 1000 codes, 16 bytes

(~10!+/')#+!4#10

Try it online!

-5 bytes thanks to @CommandMaster and @ovs!

Uses @xnor's clever observation that each pin can satisfy (digit sum) mod 10 == 0.

Explanation

  • +!4#10 generate all 4-digit pins
  • (...)# filter...
    • ~10!+/' equivalent to (digit sum) mod 10 == 0
Improve this answer
\$\endgroup\$
5
  • 1
    \$\begingroup\$ You can replace 1= with ~ for -1 \$\endgroup\$
    – Command Master
    Jul 10 at 18:17
  • \$\begingroup\$ @CommandMaster unfortunately I think that would also allow sums ending in 2-9 to filter through. \$\endgroup\$
    – Mama Fun Roll
    Jul 10 at 18:24
  • 1
    \$\begingroup\$ Your digit list can be +10\. And ~ is basically 0=, so that should work as well. You might want to look into producing output as a 4-column matrix, this can be slightly shorter \$\endgroup\$
    – ovs
    Jul 10 at 18:26
  • \$\begingroup\$ @ovs ooh ok, now I see what CommandMaster meant. Thanks for the help! \$\endgroup\$
    – Mama Fun Roll
    Jul 10 at 19:18
  • \$\begingroup\$ there's "filter out" - the negation of filter: (~..)# -> (..)_ \$\endgroup\$
    – ngn
    Jul 11 at 19:14
3
\$\begingroup\$

Charcoal, 1000 codes, 17 bytes

ＵＢ0←ＥΦＸχ⁴¬﹪Σιχ⮌Ｉι

Try it online! Link is to verbose version of code. Explanation: Uses @xnor's observation.

ＵＢ0                 Zero-fill the output.
   ←Ｅ         ⮌Ｉι   Output right-aligned an in reverse order.
       χ            Predefined variable `10`
      Ｘ             Raised to power
        ⁴           Literal integer `4`
     Φ              Filter over implicit range
            ι       Current value
           Σ        Digital sum
          ﹪         Modulo
             χ      Predefined variable `10`
         ¬          Is zero

By replacing the ⁴ with an Ｎ the program will accept the number of digits in the PIN as an input.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ ＥΦＸχ⁴¬﹪ΣιχＩι seems to work just fine for 12 bytes - it's allowed to output numbers. Is there a reason you didn't do that? \$\endgroup\$
    – Command Master
    Jul 10 at 16:33
  • \$\begingroup\$ @CommandMaster Sure, ＩΦＸχ⁴¬﹪Σιχ outputs numbers, but I wanted to output PIN codes. \$\endgroup\$
    – Neil
    Jul 10 at 20:53
3
\$\begingroup\$

JavaScript (ES6), 1000 codes, 46 bytes

Returns a comma-separated string. Based on xnor's observation.

f=(n=1e3)=>--n&&n+[~(~(n/100)-n-n/10)%10,f(n)]

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Vyxal M, 6 bytes, 1000 codes

k2'∑₀Ḋ

Try it Online!

Uses that the digit sum must be divisible by 10.

k2'∑₀Ḋ
k2'    # Filter for elements in [0, 10000]:
   ∑₀Ḋ #  Is the digit sum divisible by 10?
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I think you meant [0, 10000] in your explanation, instead of [0, 1000]. \$\endgroup\$
    – Aiden Chow
    Jul 10 at 21:07
2
\$\begingroup\$

Desmos, 61 bytes

l=[0...9999]
l[[mod(floor(i/10^{[0...3]}).total,10)fori=l]=0]

Outputs a list of numbers. Uses xnor's observation that the digit sum has to be a multiple of 10.

Try It On Desmos!

Try It On Desmos! - Prettified

Improve this answer
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.