Perfect License Plates

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 1

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 2

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 3

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 4

Python 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!

---

Results:

0 0
1 0
2 18
3 355
4 8012

Answer 5

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.

Answer 6

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!

Answer 7

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 8

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).

Answer 9

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 10

Pyth, 55 bytes

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