18
\$\begingroup\$

Every Brazilian citizen has a national identification number associated with them, named CPF.

This number has 11 digits (formatted as XXX.XXX.XXX-XX) and it's validated by the following (real) algorithm1:

  1. Take the 9 most significant digits of the number. Call it c.
  2. Multiply the n-th least significant digit of c by n+1, where 1 ≤ n ≤ 9.
  3. Add all the products and evaluate the remainder of the division between that and 11.
  4. If the remainder r is less than 2, consider 0. Otherwise, consider 11 - r. Update c to contain that as an appended least significant digit.
  5. First time on step 4? Go back to step 1, but now 1 ≤ n ≤ 10. Otherwise, go to step 5.
  6. Is c the same as your initial number? If yes, then your CPF is valid.

Let's take 111.444.777-35.

  1. Take the 9 most significant digits of the number. Call it c:

c = 111444777

  1. Multiply the n-th least significant digit of c by n+1, where 1 ≤ n ≤ 9:
c 1 1 1 4 4 4 7 7 7
10 9 8 7 6 5 4 3 2
result 10 9 8 28 24 20 28 21 14
  1. Add all the products and evaluate the remainder of the division between that and 11:

10+9+8+28+24+20+28+21+14 = 162 mod 11 = 8

  1. If the remainder r is less than 2, consider 0. Otherwise, consider 11 - r. Update c to contain that as an appended least significant digit:

Considering 11 - 8 = 3, c = 1114447773.

  1. Go back to step 1, but now 1 ≤ n ≤ 10.
c 1 1 1 4 4 4 7 7 7 3
11 10 9 8 7 6 5 4 3 2
result 11 10 9 32 28 24 35 28 21 6

11+10+9+32+28+24+35+28+21+6 = 204 mod 11 = 6

Considering 11 - 6 = 5, c = 11144477735.

  1. Is c the same as your initial number?

Yes. Therefore, the CPF is valid.

Input

You can accept one of the following (or all of them):

  • a string containing exactly 11 digits
  • a string containing exactly 14 characters formatted as XXX.XXX.XXX-XX, where X is a digit
  • a number 0 ≤ n ≤ 99999999999
    • you must read it from the most to the least significant digit: n = 12345678901 corresponds to 123.456.789-01
    • you must pad it to 11 digits: n = 3 corresponds to 000.000.000-03
  • a list/array of numbers 0 ≤ n ≤ 9 containing exactly 11 elements
    • you must read it from the left-most to the right-most element: [1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1] corresponds to 123.456.789-01

Always assume the input meets these constraints.

Output

Whether the input is a valid CPF. You may either

  • output truthy/falsy using your language's convention
  • use two distinct, fixed values to represent true and false

Truthies

11144477735
52398680002
05830033542
06865086376
39385258001
39290600780
01871863759
03337363466
66377805292
71462831435
54669275895
24029901557
83190130205
97727810509
70159591945
68730451957
55829849330
30162341903
56684732365
60505376660
29535063731

Falsies

10433218196
00133890838
63794026542
35116155940
78161849593
10341316475
25534192832
76483503056
41395376724
23884969653
28710122691
66978480184
51462704828
14893252880
95701543039
11718227824
89638346578
71331509839
30103105183
47382997376

Try to create your code with fewest bytes as possible.

The standard I/O is applied.


1 Source (in Portuguese).

\$\endgroup\$
2
  • \$\begingroup\$ "Every Brazilian citizen has a national identification number associated with it" ouch, that pronoun makes us look insignificant (I am brazilian myself) :( \$\endgroup\$
    – Joao-3
    Jan 16 at 18:35
  • \$\begingroup\$ @Joao-3 Sorry, I was referring to the Bosos there. Will update! \$\endgroup\$
    – enzo
    Jan 17 at 1:19

15 Answers 15

6
\$\begingroup\$

JavaScript (Node.js), 43 bytes

a=>a.some((v,i)=>i>8&(y+=x+=v)%11>!v,x=y=0)

Try it online!

-1 bug from Nick Kennedy

Inversed output, 1 byte to invert

\$\endgroup\$
0
4
\$\begingroup\$

Jelly, 10 bytes

ÄÄ%11>¬ṫ-Ẹ

Try it online!

A Jelly translation of l4m2’s clever JavaScript answer; be sure to upvote that one!

A monadic link that takes a list of digits and returns 0 for true and 1 for false.

Explanation

ÄÄ         | Cumulative sum twice
  %11      | Mod 11
     >¬    | Greater than not the original argument
       ṫ-  | Last two
         Ẹ | Any true

Why does this work?

The (sum of the cumulative sum of the first 10 digits) mod 11 is equivalent to (the answer to step 2 in the question plus the tenth digit) mod 11.

For a valid CPF number, this should be zero unless the result from step 2 was one, in which case it will be one (and the tenth digit will be zero). As such, this can be checked to see if it is greater than the result of not (tenth digit); for valid CPF numbers, this comparison will return false.

The same applies for checking the final digit, so in practice it’s possible to do the cumulative sum twice and then just take the final two values, as implemented above.

To extend the table given in the question:

c 1 1 1 4 4 4 7 7 7 3 5
10 9 8 7 6 5 4 3 2
result 10 9 8 28 24 20 28 21 14
cumsum c 1 2 3 7 11 15 22 29 36 39 44
cs cs c 1 3 6 13 24 39 61 90 126 165 209

\$ 165 \bmod 11 = 0 \$

\$ 209 \bmod 11 = 0 \$

Therefore this number was valid.

Alternative Jelly, 21 17 bytes

J‘Uḋị⁵ḶUŻ¤ṭ
ḣ9ÇÇ⁼

Try it online!

A pair of links which is called as a monad with a list of 11 decimal digits as its argument and returns one true and zero for false.

Thanks to @JonathanAllan for saving 4 bytes!

Explanation

J‘Uḋị⁵ḶUŻ¤ṭ     | Helper link, takes a list of integers and appends the next check digit
J               | Indices
 ‘              | Add 1
  U             | Reverse order
   ḋ            | Dot product with original link argument
    ị           | Modular index into:
     ⁵ḶUŻ¤      | [0,9,…,2,1,0]
             ṭ  | Concatenate to end of link argument

ḣ9ÇÇ⁼ | Main link, takes a list of integers and returns 1 if valid and 0 if not
ḣ9    | Head 9 (first 9 integers)
  ÇÇ  | Call helper link twice
    ⁼ | Is this equal to original argument?
\$\endgroup\$
2
  • 1
    \$\begingroup\$ @JonathanAllan thanks, I’d forgotten that was equivalent when the left argument was not a list \$\endgroup\$ Jan 12 at 18:06
  • \$\begingroup\$ Output without inverting with ṫ-Ẹ -> Ḅ4ḍ. (Also typo for ⁵ḶUŻ¤, should be [0,9,8,…,2,1,0].) \$\endgroup\$ Jan 12 at 19:45
3
\$\begingroup\$

JavaScript (ES6), 64 bytes

Expects an array of digits. Returns \$0\$ or \$1\$.

a=>(g=k=>a[k]==(a.map(v=>x-=k&&v*~k--,x=0)|10*x%11%10))(9)&g(10)

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ How both are 1? \$\endgroup\$
    – l4m2
    Jan 12 at 0:36
  • \$\begingroup\$ @l4m2 Seems like the 49-byte version is wrong indeed. I'm signing off for now, so I've just rolled back to a safe version. \$\endgroup\$
    – Arnauld
    Jan 12 at 0:52
  • \$\begingroup\$ I now compare with !a[k](initial k, if it's 0 then more possibility) you should try if that fit \$\endgroup\$
    – l4m2
    Jan 12 at 0:53
2
\$\begingroup\$

05AB1E, 23 bytes

¨¨2FDā>R*O11%11αDT‹*ª}Q

Input as a list of digits.

Try it online or verify all test cases.

Explanation:

¨¨                    # Remove the last two digits of the (implicit) input-list
  2F                  # Loop 2 times:
    D                 #  Duplicate the current list
     ā                #  Push a list in the range [1,length] (without popping)
      >               #  Increase each by 1 to range [2,length+1]
       R              #  Reverse it to range [length+1,2]
        *             #  Multiply the values of the two lists at the same positions together
         O            #  Sum
          11%         #  Modulo-11
             11α      #  Absolute difference with 11
                D     #  Duplicate this value
                 T‹   #  Pop the copy, and check that it's smaller than 10
                      #  (1 if its [1,9]; 0 if it's 10 or 11)
                   *  #  Multiply that to the value
                    ª #  Append it to the list
   }                  # After the loop:
    Q                 # Check whether this list equals the (implicit) input-list
                      # (after which the result is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

Retina, 29 bytes

.$
¶$=
.
*$<%'
.{11}

^0?¶0?$

Try it online! Link includes test cases. Takes input as a string of 11 digits. Explanation: Same idea as @Arnauld's previous answer.

.$
¶$=

Duplicate the input, but without the last digit.

.
*$<%'

For each digit, repeats the substring starting at that digit by that many times.

.{11}

Reduce modulo 11.

^0?¶0?$

Only a single 0 is allowed to be left over each time.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 24 21 bytes

⊙θ∧›κ⁹›﹪Σ⭆⊕κ…θ⊕λ¹¹¬Iι

Try it online! Link is to verbose version of code. Outputs an inverted Charcoal boolean, i.e. - for invalid, nothing for invalid. Explanation: Now a port of @l4m2's JavaScript answer.

 θ                      Input string
⊙                       Any digit satisfies
    κ                   Current index
   ›                    Is greater than
     ⁹                  Literal integer `9`
  ∧                     Logical And
           κ            Current index
          ⊕             Incremented
         ⭆              Map over implicit range and join
             θ          Input string
            …           Truncated to length
               λ        Current value
              ⊕         Incremented
        Σ               Take the digital sum
       ﹪                Modulo
                ¹¹      Literal integer `11`
      ›                 Is greater than
                    ι   Current digit
                   I    Cast to integer
                  ¬     Logical Not
                        Implicitly print
\$\endgroup\$
4
  • 1
    \$\begingroup\$ @NickKennedy My fault for copying @‌Arnauld's broken algorithm... \$\endgroup\$
    – Neil
    Jan 12 at 8:49
  • \$\begingroup\$ @NickKennedy Newer version has fewer false positives! \$\endgroup\$
    – Neil
    Jan 12 at 9:59
  • 1
    \$\begingroup\$ (It looks somewhat similar to @l4m2's approach now.) \$\endgroup\$
    – Neil
    Jan 12 at 10:00
  • 2
    \$\begingroup\$ (It looks even more similar now!) \$\endgroup\$
    – Neil
    Jan 12 at 12:20
2
+200
\$\begingroup\$

Vyxal 3, 23 bytes

9Θ2(DκṚꜝ×∑11%9z0JṚṙiJ}₌

Try it Online!

9Θ2(DκṚꜝ×∑11%9z0JṚṙiJ}₌­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁢⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁤​‎⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁢⁡⁤‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁢⁢⁡‏⁠‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁢⁢⁣‏‏​⁡⁠⁡‌­
9Θ                       # ‎⁡Slice list from 0 to index 9
  2(                 }   # ‎⁢Repeat twice
    Dκ                   # ‎⁣ Triplicate top element and push range [1, length]
      Ṛꜝ×                # ‎⁤ Reverse, increment and multiply range with list
         ∑11%            # ‎⁢⁡ Sum list and mod 11
             9z0JṚṙ      # ‎⁢⁢ Push range [0,9], append 0, reverse and rotate list right => [0, 0, 9, 8, ..., 1]
                   i     # ‎⁢⁣ Index result into list
                    J    # ‎⁢⁤ Append to initial list
                      ₌  # ‎⁣⁡Is equal to input?
💎

Created with the help of Luminespire.

\$\endgroup\$
2
\$\begingroup\$

R, 39 bytes

\(x,`+`=cumsum)any((++x%%11>!x)[10:11])

Attempt This Online!

An R translation of my Jelly answer, itself a translation of l4m2’s JavaScript answer. A function that takes a list of digits and returns a logical value, with FALSE for valid and TRUE for invalid.

\$\endgroup\$
2
\$\begingroup\$

Perl 5 -F, 82 bytes

say"@{[map{$m=$_+2;($c=(sum map$_*$m--,@F[0..$_])%11)>1?11-$c:0}8,9]}"eq"@F[9,10]"

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Haskell, 78 bytes

x#s|r<-mod(sum$zipWith(*)x[s+1,s..2])11=x!!s==last(0:[11-r|r>1])
f x=x#9&&x#10

Try it online!

\$\endgroup\$
1
\$\begingroup\$

APL+WIN, 61 60 bytes

Prompts for a vector of 11 digits and returns 1 if valid 0 if invalid.

e=+/c=v,e-e|+/(e,n)×v←v,(r>2)×e-r←(e←11)|+/(v←9↑c←⎕)×n←⌽1+⍳9

Try it online! Thanks to Dyalog Classic

\$\endgroup\$
2
  • \$\begingroup\$ -2 bytes \$\endgroup\$
    – Fmbalbuena
    Jan 12 at 14:52
  • \$\begingroup\$ @Fmbalbuena Thanks but my ancient APL does not supports dfns. I did manage to save 1 byte assigning 11 to a variable so my code looks a bit like yours. \$\endgroup\$
    – Graham
    Jan 12 at 15:08
1
\$\begingroup\$

TI-BASIC, 62 bytes

Prompt N
For(X,11,12
X-cumSum(1 or ʟN
11-11fPart(11⁻¹sum(ʟNAns*(Ans>1
If Ans≤9≠Ans⁻¹ʟN(X
13→X
End
Ans≤9

Takes input as a list of digits.

\$\endgroup\$
1
\$\begingroup\$

Python 3.8, 122 116 112 bytes

The function takes as input the list of the digits of the CPF number.

It returns 0 for true cases, None for false ones.

def f(n):
 for i in 10,9:
  s=sum(n[j]*(i-j+1)for j in range(i))%11
  if 0if s<2else 11-s!=n[i]:return
 return 0

Try it online!

  • -6 bytes thanks to enzo
  • -4 bytes thanks to l4m2

Brief explanation

The for loop is to check the 2 last digits.

s computes the sum of products, takes modulo 11 and finally the (corrected) value is compared to the corresponding last digit of the CPF number.

If the values are different, the function returns None, else continues on the next loop. If both checks are ok, the function returns 0.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Great answer! -6 bytes with some optimizations. \$\endgroup\$
    – enzo
    Jan 15 at 11:49
  • 1
    \$\begingroup\$ 112 (some cases removed to fit in comment) \$\endgroup\$
    – l4m2
    Jan 17 at 7:42
  • 1
    \$\begingroup\$ 87 bytes plus True/False regain their actual meaning :) \$\endgroup\$
    – movatica
    Mar 18 at 21:01
1
\$\begingroup\$

Swift 5.9, 124 bytes

let f={(n:[Int])in
for i in[10,9]{let s=(0..<i).reduce(0){$0+n[$1]*(i-$1+1)}%11
if(s<2 ?0:11-s) != n[i]{return 0}}
return 1}

Since TIO doesn't support Swift 5 at all, here's a JDoodle link instead.

This is pretty much a direct port of this Python answer by @SevC_10.

\$\endgroup\$
1
\$\begingroup\$

Python 3.8 (pre-release), 87 bytes

lambda n:all(((s:=sum(n[j]*(i-j+1)for j in range(i))%11)>1)*(11-s)==n[i]for i in(10,9))

Try it online!

This is a seriously golfed down version of the other Python 3.8 answer. Repost, because the original post seems dormant.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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