Starting a few years ago, I made myself a little game while driving around: checking if nearby license plates are "perfect". It's relatively rare, but exciting when you find one.

To check if a license plate is perfect:

1. Sum up the characters, with A = 1, B = 2, ... Z = 26.
2. Take each consecutive chunk of numerals, and sum them; multiply each of these sums together.

If the values in part 1 and part 2 are equal, congratulations! You've found a perfect license plate!

### Examples

License plate: AB3C4F

Digits -> 3 * 4
= 12
Chars  -> A + B + C + F
= 1 + 2 + 3 + 6
= 12
12 == 12 -> perfect!

Digits -> (3 + 4) * 7
= 49
Chars  -> G + Z + T
= 7 + 26 + 20
= 53
49 != 53 -> not perfect!

Digits -> (1 + 0) * (6 + 1)
= 7
Chars  -> G
= 7
7 == 7 -> perfect!


## The Challenge

I used license plates of length 5 and 6 as examples, but this procedure is valid for any plate length. Your challenge is, for a given length N, return the number of perfect license plates of that length. For the purposes of the challenge, a valid license plate is any combination of digits 0-9 and characters A-Z. The plate must contain both a character and a numeral to be considered potentially perfect. For checking purposes, here are the values I got (though I can't be 100% about their correctness, hahaha)

N < 2: 0
N = 2: 18
N = 3: 355
N = 4: 8012


### Notes

If somehow it makes the problem simpler in your language, you may output the proportion of perfect license plates for a given N, to at least 2 significant digits.

N < 2: 0
N = 2: 0.0138888...
N = 3: 0.0076088...
N = 4: 0.0047701...


OR, you may output the equivalent value mod 256

N < 2: 0
N = 2: 18
N = 3: 99
N = 4: 76


Shortest wins!

• Welcome to the site! I think this is a good challenge, but the additional permitted outputs make it hard to actually score answers. PPCG looks for objective winning criteria, and it's hard to do that when there are so many freedoms; this doesn't only change the output format, this actually changes what you're allowed to output. I would recommend editing out the other options and just making it required to output the number of perfect license plates for N. – hyper-neutrino Apr 3 '17 at 4:57
• I would personally enjoy this challenge a lot more if it was simply validating whether a given licence plate is perfect or not (especially because you don't have definitive numbers for the test cases. It's probably ok though, as long as the potential calculated results are reduced. Not sure about how other people feel though. Nice idea though! – MercyBeaucou Apr 3 '17 at 5:12
• I agree with Mistah Figgins; I feel like this way it's more about finding a pattern, which is still an interesting challenge, but I think it might attract more answers if it were just a validation check. Nice challenge though! – hyper-neutrino Apr 3 '17 at 5:14
• I have posted a closely related challenge, hoping that it will draw attention on this wonderful question, as well as simplifying this a bit, only checking for (nearly) perfect licence plate. – Mr. Xcoder Apr 8 '17 at 15:30
• @carusocomputing I tried my best but came up empty. I sent it to my math teacher and he is empty so far – Christopher Apr 13 '17 at 20:31

# Python 3.6, 150 bytes

f=lambda n,t=-1,p=-1,a=0:sum(f(n-1,*((t,c+p*(p>=0),a),((t<0 or t)*(p<0 or p),-1,a-c))[c<0])for c in range(-26,10))if n else 0<(t<0 or t)*(p<0 or p)==a


results:

f(2) = 18
f(3) = 355
f(4) = 8012
f(5) = 218153


Ungolfed version with explanation:

digits=[*range(10)]
letters=[*range(1,27)]

def f(n, dt=-1, dp=-1, lt=0):
if n:
for d in digits:
yield from f(n - 1,
dt,
d if dp < 0 else dp + d,
lt
)

for l in letters:
yield from f(n - 1,
dp if dt < 0 else dt if dp < 0 else dt*dp,
-1,
lt + l
)
else:
yield 0 < lt == (dt<0 or dt)*(dp<0 or dp)


The problem boils down to searching a tree in which each level of the tree corresponds to a position in a license plate number and each node has 36 children (10 digits and 26 letters). The function does a recursive search of the tree, accumulating the values for the digits and letters as it goes.

n is the number of levels to search.
dp accumulates the sum of a group of digits.
dt accumulates the product of the digit sums.
lt accumulates the sum of the letter values.

For dp and dt, a value < 0 indicates it is not initialized.


Golf included, converting the for loops to sums of generators:

sum(f(n-1,
dt,
d if dp < 0 else dp + d,
lt) for d in digits)
+
sum(f(n-1,
dp if dt<0 else dt if dp<0 else dt*dp,
-1,
lt+l) for l in letters)


Then combining the generators. Encode letters, A to Z, as -1 to -26 and digits as 0 to 9. So the sum becomes:

sum(f(n-1, *args) for c in range(-26, 10)),


where args is:

((dp if dt<0 else dt if dp<0 else dt*dp, -1, lt-l) if c <0 else
(dt, d if dp<0 else dp+d, lt))


The rest of the golfing is converting the function to a lambda, shortening variable names, and simplifying expressions.

• This is an eloquent solution, what would the runtime be? n*n*log(n) or something similar? – Magic Octopus Urn Apr 12 '17 at 20:15
• @carusocomputing Thanks. The solution still generates all possible permutations of the given length, so it has the same complexity as the other solutions. Something like k**n, where k is the number of symbols in the alphabet (e.g., 10 digits + 26 letters = 36) and n is the number of symbols on a license plate. Running it for n = 5 requires checking 36^5 = 60,466,176 permutations and took a minute or two (memoization might speed it up, but would cost a lot of bytes ;-) ). – RootTwo Apr 14 '17 at 0:35

# Dyalog APL, 57 56 bytes

+/(+/0⌈a-9)=×/c*⍨-2-/0,⌈\(+\a×b)×c←2>/0,⍨b←9≥a←↑1↓,⍳⎕⍴36


(assumes ⎕io←0)

a matrix of all valid licence plates (except 00...0) encoded with: 0-9 for digits, 10-35 for letters

b bitmask for where digits occur

c bitmask for the last digit in every group of consecutive digits

# Python 2, 359 295 bytes

Rather long; this is the trivial solution. I'm confident this is correct, though it does not match the test cases in the challenge. The solutions I'm getting match Dada's answers.

import itertools as i,re as r,string as s
print len([''.join(x)for x in i.product(s.lowercase+s.digits,repeat=input())if(lambda t:r.search('\\D',t)and r.search('\\d',t)and reduce(int.__mul__,[sum(map(int,k))for k in r.split('\\D+',t)if k])==sum([k-96 for k in map(ord,t) if k>96]))(''.join(x))])


-64 bytes thanks to suggestions from @numbermaniac

• You can save about three bytes in c(x) and the last line; remove a space between 96 and for; between map(ord,x) and if; and in the last line, between .join(x) and for. I think you can also save even more if you redefine the functions to lambdas. – numbermaniac Apr 4 '17 at 3:46
• @numbermaniac Thanks! (64 bytes total) – hyper-neutrino Apr 4 '17 at 12:30

# Python 2, 291287276 273 bytes

lambda n:sum(1for x in s.product(y+z,repeat=n)if(lambda p,s=set:reduce(int.__mul__,[sum(map(int,i))for i in re.findall(r"\d+",p)],1)==sum(ord(i)-64for i in p if ord(i)>64)and s(p)&s(y)and s(p)&s(z))(''.join(x)))
import re,itertools as s,string as t
y=t.uppercase
z=t.digits


Try it online!

Results:

0 0
1 0
2 18
3 355
4 8012


# Perl 5, 117 bytes

116 bytes of code + -p flag.

$"=",";@F=(A..Z,0..9);map{$r=1;$r*=eval s/./+$&/gr for/\d+/g;$r+=64-ord for/\pl/g;$\+=!$r*/\pl/*/\d/}glob"{@F}"x$_}{


Try it online!

It feels quite suboptimal, but I 'm out of ideas right now.
The code itself is very inefficient as it computes every permutation of a..z,0..9 of length n (it takes roughly 1 second for n=3, ~15 seconds for n=4 and ~7 minutes for n=5).
The algorithm is quite straight forward: for every possible plate of size n (generated with glob"{@F}"x$_ - the glob operator is quite magic), $r*=eval s/./+$&/gr for/\d+/g; computes the product of every chunk of digits, and $r+=64-ord for/\pl/g subtract to it the weight of the letters. Then, we increment the counter $\ if the $r is 0 (!$r) and if the plate contains numbers and letters (/\pl/*/\d/). $\ is implicitly printed at the end thanks to -p flag.

Note that the numbers I obtain are n=2 -> 18, n=3 -> 355, n=4 -> 8012, n=5 -> 218153. I'm pretty sure these are the right ones, but I might be mistaken, in which case let me know and I'll deleted this answer.

# APL (Dyalog), 71 bytes

Full program body. Prompts for N. N≥4 requires huge amounts of memory and computation.

+/((+/⊢⍳∩)∘⎕A=(×/'\d+'⎕S{+/⍎¨⍵.Match}))¨l/⍨∧⌿∨/¨c∘.∊l←,(∊c←⎕D⎕A)∘.,⍣⎕⊂⍬


Try it online!

# Scala, 265 bytes

(n:Int)=>{val i=('A'to'Z')++('0'to'9');Seq.fill(n)(i).flatten.combinations(n).flatMap(_.permutations).map(_.mkString).count(l=>"(?=.*[A-Z])(?=.*\\d)".r.findAllIn(l).size>0&&l.map(_-64).filter(_>0).sum==l.split("[A-Z]").filter(""<).map(_.map(_-48).sum).reduce(_*_))}


Explanations :

(n:Int) => {
val i = ('A' to 'Z') ++ ('0' to '9');                       // All license plates available characters.
Seq.fill(n)(i).flatten                                      // Simulate combination with repetition (each character is present n times)
.combinations(n)                                        // and generate all combinations of size n (all license plates).
.flatMap(_.permutations)                                // For each combination, generate all permutations (ex. : Seq('A', '1') => Seq('A', '1') and Seq('1', 'A')), and
.map(_.mkString)                                        // convert each permutation to String (Seq('A', '1') => "A1").
.count ( l =>                                           // Then count all strings having :
"(?=.*[A-Z])(?=.*\\d)".r.findAllIn(l).size > 0 &&   // at least 1 character and 1 digit and
l.map(_ - 64).filter(_ > 0).sum ==                  // a sum of characters (> 'A' or > 64) equals to
l.split("[A-Z]").filter(""<)
.map(_.map(_ - 48).sum)
.reduce(_*_)                                    // the product of sum of digits groups (split String by letters to get digits groups)
)
}


Notes :

• -64 and -48 are used to transform a Char (respectively letter and digit) to its Int value ('A' - 64 = 1, 'B' - 64 = 2, ..., '9' - 48 = 9)
• The filter in l.split("[A-Z]").filter(""<) is used to eliminate "" values if l starts with a letter (example : "A1".split("[A-Z]") => Array("", 1)). There might be a better and shorter solution

Test cases :

val f = (n:Int) => ...  // assign function
(1 to 5).foreach ( i =>
println(s"N = $i:${f(i)}")
)


Results :

N = 1: 0
N = 2: 18
N = 3: 355
N = 4: 8012
N = 5: 218153


The function is pretty slow for n > 4 since all combinations must be generated.

# Java, 382 365 bytes

• Saved 17 bytes, thanks to Kevin Cruijssen

Golfed

int h(String s){int m=0;for(int c:s.toCharArray())m+=c-48;return m;}
int g(String t){int d=1,c=0;for(String s:t.split("[^0-9]"))d*=h(s);for(String s:t.split("[^A-Z]"))c+=s.charAt(0)-65;return d==c?1:0;}
int f(String t,int n){int m=0;if(t.length()==n)return g(t);for(int d=48;d<58;)m+=f(t+d++,n);for(int c=65;c<91;)m+=f(t+c++,n);return m;}
int s(int n){return f("",n);}


Detailed

// return sum of adjecent digits
int h(String s)
{
int sum = 0;
for(char c : s.toCharArray()) sum += c-'0';
return sum;
}

// check if perfect
int g(String t)
{
int d = 1;
int c = 0;

for(String s : t.split("[^0-9]")) d *= h(s);
for(String s : t.split("[^A-Z]")) c += s.charAt(0)-'A';

return d == c ? 1 : 0;
}

// tree of enumerations
int f(String t, int n)
{
// base case
if(t.length() == n)
{
return g(t);
}

// enumeration
int sum = 0;
for(char d='0'; d<='9'; d++) sum += f(t+d, n);
for(char c='A'; c<='Z'; c++) sum += f(t+c, n);

return sum;
}

int s(int n){ return f("",n); }

• I think you need a function that only takes n as input. – Christian Sievers Apr 20 '17 at 0:52
• @ChristianSievers fixed – Khaled.K Apr 20 '17 at 9:13
• Some things to golf for your current code: int h(String s){int m=0;for(int c:s.toCharArray())m+=c-48;return m;}int g(String t){int d=1,c=0;for(String s:t.split("[^0-9]"))d*=h(s);for(String s:t.split("[^A-Z]"))c+=s.charAt(0)-65;return d==c?1:0;}int f(String t,int n){int m=0;if(t.length()==n)return g(t);for(int d=48;d<58;)m+=f(t+d++,n);for(int c=65;c<91;)m+=f(t+c++,n);return m;}int s(int n){return f("",n);} (365 bytes) You can compare your current version with this one to see the changes I did (too much to fit in the remainder of this comment). :) – Kevin Cruijssen Apr 20 '17 at 9:35
• @KevinCruijssen thx, 17 bytes off now – Khaled.K Apr 20 '17 at 9:42

## GAP, 416 bytes

Won't win on code size, and far from constant time, but uses math to speed up a lot!

x:=X(Integers);
z:=CoefficientsOfUnivariatePolynomial;
s:=Size;

f:=function(n)
local r,c,p,d,l,u,t;
t:=0;
for r in [1..Int((n+1)/2)] do
for c in [r..n-r+1] do
l:=z(Sum([1..26],i->x^i)^(n-c));
for p in Partitions(c,r) do
d:=x;
for u in List(p,k->z(Sum([0..9],i->x^i)^k)) do
d:=Sum([2..s(u)],i->u[i]*Value(d,x^(i-1))mod x^s(l));
od;
d:=z(d);
t:=t+Binomial(n-c+1,r)*NrArrangements(p,r)*
Sum([2..s(d)],i->d[i]*l[i]);
od;
od;
od;
return t;
end;


To squeeze out the unnecessary whitespace and get one line with 416 bytes, pipe through this:

sed -e 's/^ *//' -e 's/in \[/in[/' -e 's/ do/do /' | tr -d \\n


My old "designed for Windows XP" laptop can calculate f(10) in less than one minute and go much further in under an hour:

gap> for i in [2..15] do Print(i,": ",f(i),"\n");od;
2: 18
3: 355
4: 8012
5: 218153
6: 6580075
7: 203255386
8: 6264526999
9: 194290723825
10: 6116413503390
11: 194934846864269
12: 6243848646446924
13: 199935073535438637
14: 6388304296115023687
15: 203727592114009839797


## How it works

Suppose that we first only want to know the number of perfect license plates fitting the pattern LDDLLDL, where L denotes a letter and D denotes a digit. Assume we have a list l of numbers such that l[i] gives the number of ways the letters can give the value i, and a similar list d for the values we get from the digits. Then the number of perfect licence plates with common value i is just l[i]*d[i], and we get the number of all perfect licence plates with our pattern by summing this over all i. Let's denote the operation of getting this sum by l@d.

Now even if the best way to get these lists was to try all combinations and count, we can do this independently for the letters and the digits, looking at 26^4+10^3 cases instead of 26^4*10^3 cases when we just run through all plates fitting the pattern. But we can do much better: l is just the list of coefficients of (x+x^2+...+x^26)^k where k is the number of letters, here 4.

Similarly, we get the numbers of ways to get a sum of digits in a run of k digits as the coefficients of (1+x+...+x^9)^k. If there is more than one run of digits, we need to combine the corresponding lists with an operation d1#d2 that at position i has as value the sum of all d1[i1]*d2[i2] where i1*i2=i. This is the Dirichlet convolution, which is just the product if we interpret the lists as coefficients of Dirchlet series. But we have already used them as polynomials (finite power series), and there is no good way to interpret the operation for them. I think this mismatch is part of what makes it hard to find a simple formula. Let's use it on polynomials anyway and use the same notation #. It is easy to compute when one operand is a monomial: we have p(x) # x^k = p(x^k). Together with the fact that it is bilinear, this gives a nice (but not very efficient) way to compute it.

Note that k letters give a value of at at most 26k, while k single digits can give a value of 9^k. So we will often get unneeded high powers in the d polynomial. To get rid of them, we can compute modulo x^(maxlettervalue+1). This gives a big speed up and, though I didn't immediately notice, even helps golfing, because we now know that the degree of d is not bigger then that of l, which simplifies the upper limit in the final Sum. We get an even better speed up by doing a mod calculation in the first argument of Value (see comments), and doing the whole # computation at a lower level gives an incredible speed up. But we're still trying to be a legitimate answer to a golfing problem.

So we have got our l and d and can use them to compute the number of perfect licence plates with pattern LDDLLDL. That is the same number as for the pattern LDLLDDL. In general, we can change the order of the runs of digits of different length as we like, NrArrangements gives the number of possibilities. And while there must be one letter between the runs of digits, the other letters are not fixed. The Binomial counts these possibilities.

Now it remains to run through all possible ways of having lengths of runs digits. r runs through all numbers of runs, c through all total numbers of digits, and p through all partitions of c with r summands.

The total number of partitions we look at is two less than the number of partitions of n+1, and the partition functions grows like exp(sqrt(n)). So while there are still easy ways to improve the running time by reusing results (running through the partitions in a different order), for a fundamental improvement we need to avoid looking at each partition seperately.

## Computing it fast

Note that (p+q)@r = p@r + q@r. On its own, this just helps avoid some multiplications. But together with (p+q)#r = p#r + q#r it means that we can combine by simple addition polynomials corresponding to different partitions. We can't just add them all, because we still need to know with which l we have to @-combine, which factor we have to use, and which #-extensions are still possible.

Let's combine all polynomials corresponding to partitions with the same sum and length, and already account for the multiple ways of distributing the lengths of runs of digits. Different from what I speculated in the comments, I don't need to care about the smallest used value or how often it is used, if I make sure that I won't extend with that value.

Here is my C++ code:

#include<vector>
#include<algorithm>
#include<iostream>
#include<gmpxx.h>

using bignum = mpz_class;
using poly = std::vector<bignum>;

poly mult(const poly &a, const poly &b){
poly res ( a.size()+b.size()-1 );
for(int i=0; i<a.size(); ++i)
for(int j=0; j<b.size(); ++j)
res[i+j]+=a[i]*b[j];
return res;
}

poly extend(const poly &d, const poly &e, int ml, poly &a, int l, int m){
poly res ( 26*ml+1 );
for(int i=1; i<std::min<int>(1+26*ml,e.size()); ++i)
for(int j=1; j<std::min<int>(1+26*ml/i,d.size()); ++j)
res[i*j] += e[i]*d[j];
for(int i=1; i<res.size(); ++i)
res[i]=res[i]*l/m;
if(a.empty())
a = poly { res };
else
for(int i=1; i<a.size(); ++i)
a[i]+=res[i];
return res;
}

bignum f(int n){
std::vector<poly> dp;
poly digits (10,1);
poly dd { 1 };
dp.push_back( dd );
for(int i=1; i<n; ++i){
dd=mult(dd,digits);
int l=1+26*(n-i);
if(dd.size()>l)
dd.resize(l);
dp.push_back(dd);
}

std::vector<std::vector<poly>> a;
a.reserve(n);

a.push_back( std::vector<poly> { poly { 0, 1 } } );
for(int i=1; i<n; ++i)
a.push_back( std::vector<poly> (1+std::min(i,n+i-i)));
for(int m=n-1; m>0; --m){
//    std::cout << "m=" << m << "\n";
for(int sum=n-m; sum>=0; --sum)
for(int len=0; len<=std::min(sum,n+1-sum); ++len){
poly d {a[sum][len]} ;
if(!d.empty())
for(int sumn=sum+m, lenn=len+1, e=1;
sumn+lenn-1<=n;
sumn+=m, ++lenn, ++e)
d=extend(d,dp[m],n-sumn,a[sumn][lenn],lenn,e);
}
}
poly let (27,1);
let[0]=0;
poly lp { 1 };
bignum t { 0 };
for(int sum=n-1; sum>0; --sum){
lp=mult(lp,let);
for(int len=1; len<=std::min(sum,n+1-sum); ++len){
poly &a0 = a[sum][len];
bignum s {0};
for(int i=1; i<std::min(a0.size(),lp.size()); ++i)
s+=a0[i]*lp[i];
bignum bin;
mpz_bin_uiui( bin.get_mpz_t(), n-sum+1, len );
t+=bin*s;
}
}
return t;
}

int main(){
int n;
std::cin >> n;
std::cout << f(n) << "\n" ;
}


This uses the GNU MP library. On debian, install libgmp-dev. Compile with g++ -std=c++11 -O3 -o pl pl.cpp -lgmp -lgmpxx. The program takes its argument from stdin. For timing, use echo 100 | time ./pl.

At the end a[sum][length][i] gives the number of ways in which sum digits in length runs can give the number i. During computation, at the beginning of the m loop, it gives the number of ways that can be done with numbers greater than m. It all starts with a[0][0][1]=1. Note that this is a superset of the numbers we need to compute the function for smaller values. So at almost the same time, we could compute all values up to n.

There is no recursion, so we have a fixed number of nested loops. (The deepest nesting level is 6.) Each loop goes through a number of values that is linear in n in the worst case. So we need only polynomial time. If we look closer at the nested i and j loops in extend, we find an upper limit for j of the form N/i. That should only give a logarithmic factor for the j loop. The innermost loop in f (with sumn etc) is similar. Also keep in mind that we compute with numbers that grow fast.

Note also that we store O(n^3) of these numbers.

Experimentally, I get these results on reasonable hardware (i5-4590S): f(50) needs one second and 23 MB, f(100) needs 21 seconds and 166 MB, f(200) needs 10 minutes and 1.5 GB, and f(300) needs one hour and 5.6 GB. This suggests a time complexity better than O(n^5).

• As this is a code golf challenge, this answer needs to be golfed. Sorry. – Rɪᴋᴇʀ Apr 8 '17 at 15:31
• @Riker While I don't think my code was overly verbose to start with, I golfed some more and took the burden of determining its size when whitespace is squeezed out. – Christian Sievers Apr 8 '17 at 16:53
• @carusocomputing I'm afraid it's much worse. I'm handling separately each case of distributing digits among runs of digits, like there is one run of three digits, or there is one run of two digits and one single digit, or there are three single digits, but for n=5, there is no case with a run of two digits and two single digits, because then we don't have enough letters to separate the numbers. This is what the three outer for loops do: run through all useful partitions of numbers <n. (And I just realized I also allow n digits. By sheer luck another optimization counts this as 0). – Christian Sievers Apr 11 '17 at 0:19
• @carusocomputing Note that for numbers <n/2, all partitions are useful. And the remaining computations still take their non-constant time. To see what is going on, you could add Print(p,"\n"); at the beginning of the body of the for p... loop. - I got an idea for using one loop less, but it will only help code size. – Christian Sievers Apr 11 '17 at 0:37
• I get an amazing speed up by moving the mod (which already helped a lot) into Value, changing it to Value(d mod x^(1+QuoInt(s(l)-1,i-1)),x^(i-1)). That alone allows to compute f(15) in 80 seconds. – Christian Sievers Apr 14 '17 at 13:21

# Pyth, 55 bytes

FNQI<xrG1N0=+ZsN).?=+YZ=Z0;qu*G?HH1Y1sm?<xrG1d00hxrG1dQ