[Question]
  [
# Perfect License Plates
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!
License plate: G34Z7T
Digits -> (3 + 4) * 7 
        = 49
Chars  -> G + Z + T 
        = 7 + 26 + 20 
        = 53
49 != 53 -> not perfect!
License plate: 10G61
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!
  
[Answer]
# 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.
[Answer]
# 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
[Answer]
# 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
[Answer]
# [Python 2](https://docs.python.org/2/), ~~291~~ ~~287~~ ~~276~~ 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!](https://tio.run/nexus/python2#TY7BasMwEETv/gqRQ6MlqiGQ5mBQf6QpRo0ks8WWFu0aYv@8a9HS9rYzzLydaG/b6KYP71TqeJ70OeaiHgqT4pZK9vNd9HJaTQkUnNgEGPVPgQxbDtKVsKeCxiRt30/z2PfmraImR9U0CFChWKEltBGTd@Ooy@HmTwdD8G7OYG1t5OI1wvP18psnhVF926/XC7jkFWuCJ9bLf7EC6OOx/cyY9AMAGpwoF9nfGZRQJOeRlWPFhqVgGuotzWKlnYlCuTsOzborjwMKb39zXRqCfoGuUbT3RKGJ@5TtCw "Python 2 – TIO Nexus")
---
Results:
```
0 0
1 0
2 18
3 355
4 8012
```
[Answer]
# [Perl 5](https://www.perl.org/), 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!](https://tio.run/nexus/perl5#U1YsSC3KUdAt@K@iZKuko2Tt4Gar4ainF6VjoKdnqWmdm1hQrVJka2itUqRlm1qWmKNQrK@nr62ipp9epJCWX6Qfk6Ktnw6U1bY1M9HNL0qBCBbkgARjtG0VgfrAXCCZol@bnpOfpFTt4FarVKESX1v9/78xAA "Perl 5 – TIO Nexus")
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.
[Answer]
# [APL (Dyalog)](https://www.dyalog.com/), 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!](https://tio.run/nexus/apl-dyalog#e9TRnvZfW19DQ1v/UdeiR72bH3Ws1HzUMeNR31RHW43D0/XVY1K01YG84Gqgit6@Qyse9W7V800sSc6o1dQ8tCIHKLjiUcfyRz37H3Ws0D@0IhmoWe9RR1fOo7YJOhpARjKQAdTvAjIRZLKezqPexUDOo66mR71r/j/qaP@fxmXIlcZlBMTGAA "APL (Dyalog Unicode) – TIO Nexus")
[Answer]
## [GAP](http://www.gap-system.org), 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)`.
[Answer]
# 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.
[Answer]
# 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); }
```
[Answer]
# Pyth, 55 bytes
```
FNQI<xrG1N0=+ZsN).?=+YZ=Z0;qu*G?HH1Y1sm?<xrG1d00hxrG1dQ
```
]