Idealne tablice rejestracyjne

Zaczynam kilka lat temu, prowadząc małą grę podczas jazdy: sprawdzając, czy pobliskie tablice rejestracyjne są „idealne”. Jest to stosunkowo rzadkie, ale ekscytujące, gdy go znajdziesz.

Aby sprawdzić, czy tablica rejestracyjna jest idealna:

1. Sumuj znaki, z A = 1, B = 2, ... Z = 26.
2. Weź każdą kolejną część cyfr i zsumuj je; pomnóż każdą z tych sum razem.

Jeśli wartości w części 1 i 2 są równe, gratulacje! Znalazłeś idealną tablicę rejestracyjną!

Przykłady

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!

Wyzwanie

Jako przykłady użyłem tablic rejestracyjnych o długości 5 i 6, ale ta procedura obowiązuje dla dowolnej długości tablicy rejestracyjnej. Twoim wyzwaniem jest, dla danej długości N, zwrócenie liczby idealnych tablic rejestracyjnych o tej długości. Dla celów wyzwania ważną tablicą rejestracyjną jest dowolna kombinacja cyfr 0–9 i znaków AZ. Tabliczka musi zawierać zarówno znak, jak i cyfrę, aby uznać ją za potencjalnie idealną. Dla celów kontrolnych oto wartości, które otrzymałem (chociaż nie mogę w 100% mówić o ich poprawności, hahaha)

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

Notatki

Jeśli w jakiś sposób uprości to problem w twoim języku, możesz przekazać proporcję idealnych tablic rejestracyjnych dla danego N, do co najmniej 2 cyfr znaczących.

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

LUB możesz podać wartość równoważną mod 256

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

Najkrótsze wygrane!

Python 3.6, 150 bajtów

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

wyniki:

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

Wersja bez golfa z wyjaśnieniem:

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)

Problem sprowadza się do przeszukania drzewa, w którym każdy poziom drzewa odpowiada pozycji w numerze rejestracyjnym, a każdy węzeł ma 36 dzieci (10 cyfr i 26 liter). Ta funkcja dokonuje rekurencyjnego przeszukiwania drzewa, gromadząc wartości cyfr i liter.

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.

Zawiera golf, konwertując pętle for na sumy generatorów:

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)

Następnie łączenie generatorów. Zakoduj litery od A do Z, od -1 do -26, a cyfry od 0 do 9. Tak więc suma staje się:

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

gdzie args to:

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

Reszta gry w golfa polega na zamianie funkcji na lambda, skracaniu nazw zmiennych i upraszczaniu wyrażeń.

Dyalog APL, 57 56 bajtów

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

(zakłada ⎕io←0)

amacierz wszystkich ważnych tablic rejestracyjnych (oprócz 00...0) kodowanych: 0-9 dla cyfr, 10-35 dla liter

b maska ​​bitowa dla miejsca występowania cyfr

c maska ​​bitowa dla ostatniej cyfry w każdej grupie kolejnych cyfr

Python 2, 359 295 bajtów

Raczej długi; to jest trywialne rozwiązanie. Jestem pewien, że jest to poprawne, choć nie pasuje do przypadków testowych w wyzwaniu. Rozwiązania, które otrzymuję, pasują do odpowiedzi Dady.

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 bajty dzięki sugestiom @numbermaniac

Python 2 , 291 287 276 273 bajtów

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

Wypróbuj online!

Wyniki:

0 0
1 0
2 18
3 355
4 8012

Perl 5 , 117 bajtów

116 bajtów kodu + -pflaga.

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

Wypróbuj online!

Wydaje się to dość nieoptymalne, ale obecnie brakuje mi pomysłów.
Sam kod jest bardzo nieefektywny, ponieważ oblicza każdą permutację a..z,0..9długości n(zajmuje to około 1 sekundy dla n=3, ~ 15 sekund dla n=4i ~ 7 minut dla n=5).
Algorytm jest dość prosty: dla każdej możliwej płytki wielkości n(wygenerowanej za pomocą glob"{@F}"x$_- globoperator jest dość magiczny) $r*=eval s/./+$&/gr for/\d+/g;oblicza iloczyn każdego kawałka cyfr i $r+=64-ord for/\pl/godejmuje od niego wagę liter. Następnie zwiększamy licznik, $\jeśli $ris 0( !$r) i jeśli tablica zawiera cyfry i litery ( /\pl/*/\d/). $\jest niejawnie wydrukowany na końcu dzięki -pflagi.

Należy pamiętać, że numery mogę uzyskać to n=2 -> 18, n=3 -> 355, n=4 -> 8012, n=5 -> 218153. Jestem pewien, że to są właściwe, ale mogę się mylić, w takim przypadku daj mi znać, a ja usunę tę odpowiedź.

APL (Dyalog) , 71 bajtów

Pełna treść programu. Monity o N. N≥4 wymagają ogromnej ilości pamięci i obliczeń.

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

Wypróbuj online!

Scala, 265 bajtów

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

Objaśnienia:

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

Uwagi:

• -64i -48są stosowane do przekształcenia Char(odpowiednio litery i cyfry) do jego Intwartości ( 'A' - 64 = 1, 'B' - 64 = 2, ..., '9' - 48 = 9)
• Filtr w l.split("[A-Z]").filter(""<)służy do eliminacji ""wartości, jeśli lzaczyna się na literę (przykład "A1".split("[A-Z]") => Array("", 1):). Może być lepsze i krótsze rozwiązanie

Przypadki testowe :

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

Wyniki:

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

Ta funkcja działa dość wolno, n > 4ponieważ wszystkie kombinacje muszą zostać wygenerowane.

Java, 382 365 bajtów

• Zaoszczędzono 17 bajtów dzięki Kevinowi Cruijssenowi

Grał w golfa

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

Szczegółowy

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

LUKA , 416 bajtów

Nie wygra rozmiaru kodu, i to daleko od stałego czasu, ale używa matematyki, aby znacznie przyspieszyć!

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;

Aby wycisnąć niepotrzebne białe znaki i uzyskać jedną linię z 416 bajtami, przeciągnij przez to:

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

Mój stary laptop „zaprojektowany dla systemu Windows XP” może obliczyć f(10)w mniej niż minutę i pójść znacznie dalej w ciągu godziny:

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

Jak to działa

Załóżmy, że najpierw chcemy znać tylko liczbę idealnych tablic rejestracyjnych pasujących do wzoru LDDLLDL, gdzie Loznacza literę, a Dcyfrę. Załóżmy, że mamy taką listę lliczb, która l[i]podaje liczbę sposobów, w jakie litery mogą podawać wartość i, oraz podobną listę dwartości, które otrzymujemy z cyfr. Zatem liczba idealnych tablic rejestracyjnych o wspólnej wartości ijest po prostu l[i]*d[i]i otrzymujemy liczbę wszystkich idealnych tablic rejestracyjnych według naszego wzoru, sumując to wszystko i. Oznaczmy operację uzyskania tej sumy l@d.

Teraz nawet jeśli najlepszym sposobem na uzyskanie tych list było wypróbowanie wszystkich kombinacji i policzenie, możemy to zrobić niezależnie dla liter i cyfr, patrząc na 26^4+10^3przypadki zamiast 26^4*10^3 przypadków, gdy po prostu przeglądamy wszystkie tablice pasujące do wzoru. Ale możemy zrobić znacznie lepiej: tutaj ljest tylko lista współczynników, (x+x^2+...+x^26)^kgdzie kjest liczba liter4 .

Podobnie otrzymujemy liczbę sposobów uzyskania sumy cyfr w szeregu kcyfr jako współczynników (1+x+...+x^9)^k. Jeśli jest więcej niż jeden ciąg cyfr, musimy połączyć odpowiednie listy z operacją, d1#d2która na pozycji ima jako wartość sumę wszystkich d1[i1]*d2[i2]gdzie . Wraz z faktem, że jest dwuliniowy, daje to miły (ale niezbyt wydajny) sposób na jego obliczenie.i1*i2=i . Jest to splot Dirichleta, który jest produktem, jeśli interpretujemy listy jako współczynniki serii Dirchleta. Ale używaliśmy ich już jako wielomianów (skończone szeregi mocy) i nie ma dobrego sposobu na interpretację ich działania. Myślę, że to niedopasowanie jest częścią tego, co utrudnia znalezienie prostej formuły. W każdym razie użyjmy go na wielomianach i zastosujmy tę samą notację #. Łatwo jest obliczyć, gdy jeden operand jest monomialny: mamyp(x) # x^k = p(x^k)

Zauważ, że klitery dają co najwyżej wartość 26k, podczas gdy k pojedyncze cyfry mogą dawać wartość 9^k. Tak więc często otrzymamy niepotrzebne wysokie moce w dwielomianu. Aby się ich pozbyć, możemy obliczyć modulo x^(maxlettervalue+1). Daje to duże przyspieszenie i chociaż nie zauważyłem od razu, nawet pomaga w grze w golfa, ponieważ teraz wiemy, że stopieńd nie jest większy niż ten l, co upraszcza górną granicę w finale Sum. Jeszcze lepsze przyspieszenie uzyskujemy, wykonując modobliczenia w pierwszym argumencie Value (patrz komentarze), a wykonanie całego #obliczenia na niższym poziomie daje niesamowite przyspieszenie. Ale wciąż staramy się być uzasadnioną odpowiedzią na problem golfowy.

Więc mamy nasze lid i można z nich korzystać, aby obliczyć liczbę doskonałych tablic rejestracyjnych z wzorem LDDLLDL. To ta sama liczba, co dla wzoru LDLLDDL. Ogólnie rzecz biorąc, możemy zmienić kolejność ciągów cyfr o różnej długości, jak nam się podoba, NrArrangementsdaje to szereg możliwości. I chociaż między ciągami cyfr musi znajdować się jedna litera, pozostałe litery nie są ustalone. BinomialLiczy te możliwości.

Teraz pozostaje przejść przez wszystkie możliwe sposoby uzyskania długości cyfr przebiegów. rprzebiega przez wszystkie liczby przebiegów,c przez całkowitą liczbę cyfr i pprzez wszystkie partycje cz rsumami.

Całkowita liczba partycji, które przeglądamy, jest o dwa razy mniejsza niż liczba partycji n+1, a funkcje partycji rosną podobnie exp(sqrt(n)). Tak więc, chociaż wciąż istnieją proste sposoby na poprawę czasu działania poprzez ponowne wykorzystanie wyników (przeglądanie partycji w innej kolejności), dla fundamentalnej poprawy musimy unikać oddzielnego patrzenia na każdą partycję.

Obliczam to szybko

Zauważ, że (p+q)@r = p@r + q@r. Samo to pomaga po prostu uniknąć mnożenia. Ale razem z (p+q)#r = p#r + q#rtym oznacza, że ​​możemy łączyć poprzez proste dodawanie wielomianów odpowiadających różnym partycjom. Nie możemy po prostu dodać ich wszystkich, ponieważ wciąż musimy wiedzieć, z czym lmusimy @połączyć, jaki czynnik musimy zastosować i które #rozszerzenia są nadal możliwe.

Połączmy wszystkie wielomiany odpowiadające partycjom z tą samą sumą i długością, i już uwzględniliśmy wiele sposobów dystrybucji długości ciągów cyfr. W odróżnieniu od tego, co spekulowałem w komentarzach, nie muszę się martwić o najmniejszą używaną wartość lub częstotliwość jej używania, jeśli upewnię się, że nie będę rozszerzać o tę wartość.

Oto mój kod 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" ;
}

Wykorzystuje bibliotekę GNU MP. W Debianie zainstaluj libgmp-dev. Kompiluj z g++ -std=c++11 -O3 -o pl pl.cpp -lgmp -lgmpxx. Program bierze swój argument ze standardowego wejścia. Do pomiaru czasu użyj echo 100 | time ./pl.

Na końcu a[sum][length][i]podaje liczbę sposobów, w jakie sum cyfry w lengthseriach mogą podawać liczbę i. Podczas obliczeń, na początku mpętli, podaje liczbę sposobów, które można zrobić z liczbami większymi niż m. Wszystko zaczyna się od a[0][0][1]=1 . Zauważ, że jest to nadzbiór liczb potrzebnych do obliczenia funkcji dla mniejszych wartości. Więc prawie w tym samym czasie moglibyśmy obliczyć wszystkie wartości do n.

Nie ma rekurencji, więc mamy stałą liczbę zagnieżdżonych pętli. (Najgłębszy poziom zagnieżdżenia to 6.) Każda pętla przechodzi przez szereg wartości, które nw najgorszym przypadku są liniowe . Potrzebujemy tylko czasu wielomianowego. Jeśli przyjrzymy się bliżej zagnieżdżeniu ii jpętli extend, znajdziemy górną granicę jformy N/i. To powinno dać jedynie współczynnik logarytmiczny dla jpętli. Najbardziej wewnętrzna pętla w f (zsumn etc) jest podobna. Należy również pamiętać, że obliczamy z szybko rosnącymi liczbami.

Pamiętaj również, że przechowujemy O(n^3) te liczby.

Eksperymentalnie otrzymuję te wyniki na rozsądnym sprzęcie (i5-4590S): f(50)potrzebuje jednej sekundy i 23 MB, f(100)potrzebuje 21 sekund i 166 MB, f(200)potrzebuje 10 minut i 1,5 GB oraz f(300)potrzebuje godziny i 5,6 GB. To sugeruje złożoność czasu lepszą niż O(n^5).

Pyth, 55 bajtów

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