Plaques d'immatriculation parfaites

Depuis quelques années, je me suis fait un petit jeu en conduisant: vérifier si les plaques d'immatriculation à proximité sont "parfaites". C'est relativement rare, mais excitant quand vous en trouvez un.

Pour vérifier si une plaque d'immatriculation est parfaite:

1. Résumer les caractères, avec A = 1, B = 2, ... Z = 26.
2. Prenez chaque morceau consécutif de chiffres et additionnez-les; multipliez chacune de ces sommes ensemble.

Si les valeurs des parties 1 et 2 sont égales, félicitations! Vous avez trouvé une plaque d'immatriculation parfaite!

Exemples

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!

Le défi

J'ai utilisé des plaques d'immatriculation de longueur 5 et 6 à titre d'exemple, mais cette procédure est valable pour toute longueur de plaque. Votre défi est, pour une longueur donnée N, de retourner le nombre de plaques d'immatriculation parfaites de cette longueur. Pour les besoins du défi, une plaque d'immatriculation valide est une combinaison des chiffres 0 à 9 et des caractères AZ. La plaque doit contenir à la fois un caractère et un chiffre pour être considérée comme potentiellement parfaite. À des fins de vérification, voici les valeurs que j'ai obtenues (bien que je ne puisse pas être à 100% sur leur exactitude, hahaha)

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

Remarques

Si, dans votre langue, le problème est simplifié, vous pouvez générer la proportion de plaques d'immatriculation parfaites pour un N donné, avec au moins deux chiffres significatifs.

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

OU vous pouvez sortir la valeur équivalente mod 256

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

Le plus court gagne!

Python 3.6, 150 octets

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

résultats:

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

Version non-golfée avec explication:

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)

Le problème revient à rechercher un arbre dans lequel chaque niveau de l’arbre correspond à une position dans un numéro de plaque d’immatriculation et chaque nœud a 36 enfants (10 chiffres et 26 lettres). La fonction effectue une recherche récursive de l’arbre, en accumulant les valeurs des chiffres et des lettres au fur et à mesure.

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 inclus, convertissant les boucles for en sommes de générateurs:

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)

Puis en combinant les générateurs. Encodez les lettres, de A à Z, de -1 à -26 et les chiffres de 0 à 9. La somme devient:

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

où args est:

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

Le reste du jeu consiste à convertir la fonction en lambda, à raccourcir les noms de variables et à simplifier les expressions.

Dyalog APL, 57 56 octets

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

(suppose ⎕io←0)

amatrice de toutes les plaques d'immatriculation valides (sauf 00...0) codée avec: 0-9 pour les chiffres, 10-35 pour les lettres

b masque de bits pour indiquer où se trouvent les chiffres

c masque de bits pour le dernier chiffre de chaque groupe de chiffres consécutifs

Python 2, 359 295 octets

Assez long; c'est la solution triviale. Je suis convaincu que c'est correct, bien que cela ne corresponde pas aux cas de test du challenge. Les solutions que je trouve correspondent aux réponses de Dada.

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 octets grâce aux suggestions de @numbermaniac

Python 2 , 291 287 276 273 octets

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

Essayez-le en ligne!

Résultats:

0 0
1 0
2 18
3 355
4 8012

Perl 5 , 117 octets

116 octets de code + -pdrapeau.

$"=",";@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$_}{

Essayez-le en ligne!

Cela semble assez sous-optimal, mais je suis à court d'idées pour le moment.
Le code lui-même est très inefficace car il calcule chaque permutation de a..z,0..9longueur n(cela prend environ 1 seconde pour n=3, environ 15 secondes pour n=4et environ 7 minutes pour n=5).
L'algorithme est assez simple: pour chaque plaque de taille possible n(générée avec glob"{@F}"x$_- l' globopérateur est assez magique), $r*=eval s/./+$&/gr for/\d+/g;calcule le produit de chaque bloc de chiffres et lui $r+=64-ord for/\pl/gsoustrait du poids des lettres. Ensuite, nous incrémentons le compteur $\si $ris 0( !$r) et si la plaque contient des chiffres et des lettres ( /\pl/*/\d/). $\est implicitement imprimé à la fin grâce à -pflag.

Notez que les chiffres que j'obtiens sont n=2 -> 18, n=3 -> 355, n=4 -> 8012, n=5 -> 218153. Je suis à peu près sûr que ce sont les bons, mais je peux me tromper, dans ce cas, faites-le moi savoir et je supprimerai cette réponse.

APL (Dyalog) , 71 octets

Corps du programme complet. Les invites pour N. N≥4 nécessitent d'énormes quantités de mémoire et de calculs.

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

Essayez-le en ligne!

Scala, 265 octets

(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(_*_))}

Explications:

(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)
        )
}

Remarques :

• -64et -48sont utilisés pour transformer un Charson (respectivement lettre et chiffres) Intvaleur ( 'A' - 64 = 1, 'B' - 64 = 2, ..., '9' - 48 = 9)
• Le filtre dans l.split("[A-Z]").filter(""<)est utilisé pour éliminer les ""valeurs si lcommence par une lettre (exemple:) "A1".split("[A-Z]") => Array("", 1). Il pourrait y avoir une solution meilleure et plus courte

Cas de test:

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

Résultats :

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

La fonction est assez lente n > 4car toutes les combinaisons doivent être générées.

Java, 382 365 octets

• 17 octets sauvés, merci à Kevin Cruijssen

Golfé

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);}

Détaillé

// 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); }

GAP , 416 octets

Ne gagnera pas sur la taille du code, et loin du temps constant, mais utilise les mathématiques pour accélérer beaucoup!

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;

Pour réduire les espaces inutiles et obtenir une ligne de 416 octets, dirigez-le:

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

Mon ancien ordinateur portable "conçu pour Windows XP" peut calculer f(10)en moins d'une minute et aller beaucoup plus loin en moins d'une heure:

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

Comment ça marche

Supposons que nous ne voulions d'abord connaître que le nombre de plaques d'immatriculation parfaites correspondant au motif LDDLLDL, où correspond à Lune lettre et à Dun chiffre. Supposons que nous ayons une liste lde nombres l[i]donnant le nombre de façons dont les lettres peuvent donner la valeur iet une liste similaire dpour les valeurs que nous obtenons des chiffres. Ensuite, le nombre de plaques d'immatriculation parfaites ayant une valeur commune iest juste l[i]*d[i], et nous obtenons le nombre de toutes les plaques d'immatriculation parfaites avec notre modèle en additionnant l'ensemble i. Notons l'opération consistant à obtenir cette somme par l@d.

Maintenant, même si le meilleur moyen d’obtenir ces listes était d’essayer toutes les combinaisons et de compter, nous pouvons le faire indépendamment pour les lettres et les chiffres, en regardant les 26^4+10^3cas au lieu des 26^4*10^3 cas où nous passons simplement en revue toutes les plaques correspondant au modèle. Mais nous pouvons faire beaucoup mieux: lest juste la liste des coefficients de (x+x^2+...+x^26)^koù kest le nombre de lettres, ici 4.

De même, nous obtenons le nombre de façons d'obtenir une somme de chiffres dans une suite de kchiffres en tant que coefficients de (1+x+...+x^9)^k. S'il y a plus d'une suite de chiffres, nous devons combiner les listes correspondantes avec une opération d1#d2dont position ia la valeur la somme de tous d1[i1]*d2[i2]où i1*i2=i. Il s'agit de la convolution de Dirichlet, qui est simplement le produit si nous interprétons les listes comme des coefficients de la série de Dirchlet. Mais nous les avons déjà utilisés en tant que polynômes (séries de puissance finie) et il n’existe aucun moyen d’interpréter l’opération pour eux. Je pense que cette inadéquation fait partie de ce qui rend difficile de trouver une formule simple. Utilisons-le quand même sur les polynômes et utilisons la même notation #. Il est facile de calculer quand un opérande est un monôme: on ap(x) # x^k = p(x^k). Avec le fait qu'il soit bilinéaire, cela donne un moyen agréable (mais pas très efficace) de le calculer.

Notez que les klettres donnent une valeur d'au plus 26k, alors que k les chiffres simples peuvent donner une valeur de 9^k. Nous aurons donc souvent des pouvoirs élevés inutiles dans le dpolynôme. Pour nous en débarrasser, nous pouvons calculer modulo x^(maxlettervalue+1). Cela donne une grande vitesse et, bien que je ne l'aie pas remarqué tout de suite, aide même au golf, car nous savons maintenant que le degré de dn'est pas plus grand que celui de l, ce qui simplifie la limite supérieure en finale Sum. Nous obtenons une vitesse encore meilleure en faisant un modcalcul dans le premier argument de Value (voir les commentaires), et en effectuant tout le #calcul à un niveau inférieur, cela donne une vitesse incroyable. Mais nous essayons toujours d'être une réponse légitime à un problème de golf.

Nous avons donc nos let nous dpouvons les utiliser pour calculer le nombre de plaques d'immatriculation parfaites avec un motif LDDLLDL. C'est le même nombre que pour le motif LDLLDDL. En général, nous pouvons modifier l'ordre des séquences de chiffres de longueur différente selon NrArrangementsle nombre de possibilités. Et s'il doit y avoir une lettre entre les séries de chiffres, les autres lettres ne sont pas fixes. Le Binomialcompte ces possibilités.

Il reste maintenant à parcourir tous les moyens possibles pour avoir des longueurs de chiffres de courses. rpasse à travers tous les numéros de pistes, à ctravers tous le nombre total de chiffres, et à ptravers toutes les partitions de cavec rsummands.

Le nombre total de partitions que nous examinons est deux de moins que le nombre de partitions n+1, et les fonctions de partition se développent comme suit exp(sqrt(n)). Il est donc toujours facile d'améliorer le temps d'exécution en réutilisant les résultats (en parcourant les partitions dans un ordre différent), mais pour une amélioration fondamentale, nous devons éviter de regarder chaque partition séparément.

Le calcul rapide

Notez que (p+q)@r = p@r + q@r. En soi, cela permet d'éviter certaines multiplications. Mais (p+q)#r = p#r + q#rcela signifie que nous pouvons combiner par simple addition des polynômes correspondant à différentes partitions. Nous ne pouvons pas simplement les ajouter tous, car nous avons encore besoin de savoir avec lequel lnous devons @combiner, quel facteur nous devons utiliser et quelles #extensions sont encore possibles.

Associons tous les polynômes correspondant aux partitions ayant la même somme et la même longueur, et prenons déjà en compte les multiples façons de répartir les longueurs des séries de chiffres. Contrairement à ce que j'ai spéculé dans les commentaires, je n'ai pas besoin de me soucier de la plus petite valeur utilisée ou de la fréquence d'utilisation, si je m'assure que je ne vais pas prolonger cette valeur.

Voici mon code C ++:

#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" ;
}

Ceci utilise la bibliothèque GNU MP. Sur Debian, installez libgmp-dev. Compiler avec g++ -std=c++11 -O3 -o pl pl.cpp -lgmp -lgmpxx. Le programme tire son argument de stdin. Pour le timing, utilisez echo 100 | time ./pl.

À la fin, a[sum][length][i]donne le nombre de façons dont les sum chiffres dans les lengthexécutions peuvent donner le nombre i. Lors du calcul, au début de la mboucle, il indique le nombre de façons de procéder avec des nombres supérieurs à m. Tout commence par a[0][0][1]=1. Notez que ceci est un sur-ensemble des nombres dont nous avons besoin pour calculer la fonction pour des valeurs plus petites. Donc, presque au même moment, nous pourrions calculer toutes les valeurs jusqu’à n.

Il n'y a pas de récursivité, nous avons donc un nombre fixe de boucles imbriquées. (Le niveau d'imbrication le plus profond est 6.) Chaque boucle passe par un nombre de valeurs qui est linéaire ndans le pire des cas. Nous avons donc besoin que de temps polynomial. Si nous regardons de plus près l'imbrication iet la jboucle extend, nous trouvons une limite supérieure pour jla forme N/i. Cela ne devrait donner qu'un facteur logarithmique pour la jboucle. La boucle la plus interne f (avec sumnetc.) est similaire. Gardez également à l'esprit que nous calculons avec des nombres qui croissent rapidement.

Notez également que nous stockons O(n^3)ces nombres.

Expérimentalement, j'obtiens ces résultats sur un matériel raisonnable (i5-4590S): f(50)nécessite une seconde et 23 Mo, f(100)21 secondes et 166 Mo, f(200)10 minutes et 1,5 Go, et f(300)une heure et 5,6 Go. Cela suggère une complexité temporelle meilleure que O(n^5).

Pyth, 55 octets

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