Comptage des fontaines

17

Une fontaine est un arrangement de pièces en rangées de sorte que chaque pièce touche deux pièces dans la rangée en dessous, ou se trouve dans la rangée du bas, et la rangée du bas est connectée. Voici une fontaine de 21 pièces:

Depuis http://mathworld.wolfram.com/Fountain.html

Votre défi est de compter combien de fontaines différentes peuvent être fabriquées avec un nombre donné de pièces.

Vous recevrez en entrée un entier positif n. Vous devez afficher le nombre de différentes nfontaines en coin qui existent.

Règles d'E / S standard, échappatoires standard interdites. Les solutions devraient pouvoir calculer n = 10en moins d'une minute.

Sortie souhaitée pour n = 1 ... 10:

1, 1, 2, 3, 5, 9, 15, 26, 45, 78

Cette séquence est OEIS A005169 .

C'est le golf de code. Le moins d'octets gagne.

code-golf sequence combinatorics isaacg
la source
Existe-t-il un programme npour lequel le programme doit être garanti? (c'est-à-dire après quoi il peut se briser)
quintopie
@quintopia Cela devrait fonctionner pour tous n, jusqu'aux limitations du type de données, du matériel, etc.
isaacg

Réponses:

3

Python, 57 octets

f=lambda n,i=0:sum(f(n-j,j)for j in range(1,i+2)[:n])or 1

Comme observé sur OEIS , si vous décalez chaque ligne d'un demi-pas par rapport à la ligne en dessous, les tailles de colonne forment une séquence d'entiers positifs avec un pas vers le haut maximum de 1.

La fonction f(n,i)compte les séquences avec la somme net le dernier nombre i. Ceux-ci peuvent être sommés récursivement pour chaque choix de la taille de colonne suivante de 1à i+1, qui est range(1,i+2). Tronquer pour range(1,i+2)[:n]éviter que les colonnes n'utilisent plus de pièces qu'il n'en reste, évitant d'avoir à dire que le négatif ndonne 0. De plus, cela évite un cas de base explicite, car la somme vide est 0et ne récurrente pas, mais f(0)doit être définie à la 1place, ce qui or 1suffit (comme le ferait +0**n).

xnor
la source
17 octets en Pyth:M|sgL-Gd<ShHG1gQ0
isaacg
5

Mathematica, 59 octets

SeriesCoefficient[1-Fold[1-x^#2/#&,Range[#,0,-1]],{x,0,#}]&

Basé sur le programme Mathematica sur OEIS par Jean-François Alcover.

alephalpha
la source
Pouvez-vous réécrire cela sous forme de formule (je veux juste comparer avec la formule que j'ai trouvée)? Je ne peux tout simplement pas lire Mathematica =)
flawr
@flawr La fonction génératrice de la séquence est 1/(1-x/(1-x^2/(1-x^3/(1-x^4/(1-x^5/(...)))))).
alephalpha
Merci pour l'explication, c'est en effet une bonne approche si vous avez un CAS aussi puissant =)
flawr
3

Haskell, 60 48 octets

Merci à @nimi d'avoir fourni une solution beaucoup plus courte!

n#p|p>n=0|p<n=sum$map((n-p)#)[1..p+1]|1<2=1
(#1)

Ancienne version.

t n p|p>n=0|p==n=1|p<n=sum[t (n-q) q|q<-[1..p+1]]
s n=t n 1

La fonction calculant la valeur est s, l'implémentation de la formule récursive trouvée ici: https://oeis.org/A005169

flawr
la source
Un bug: l'appel récursif l'est t (n-p) q. Golf Conseils: utiliser un opérateur infixe pour t, échanger les gardes et utiliser au maplieu de la compréhension de la liste: n#p|p>n=0|p<n=sum$map((n-p)#)[1..p+1]|1<2=1. sdevient s=(#1), mais vous n'avez pas du tout à donner un nom à la fonction principale, cela (#1)suffit donc. 48 octets.
nimi
Merci beaucoup pour les conseils! Je viens de commencer à apprendre les bases de Haskell. Je vais devoir en apprendre davantage sur la façon dont l'utilisation de #et $ici d'abord =)
flawr
Un peu d'explication: #est une fonction infix définie par l'utilisateur comme +, *, etc. sont des fonctions infixes prédéfinies. $est une autre façon d'ajuster la priorité (en plus des parenthèses) f (g (h x))-> f$g$h xou dans notre cas sum(map(...)[...])-> sum$map(...)[...].
nimi
Merci, c'est assez utile à savoir, j'apprécie votre explication!
flawr
3

Haskell, 43 octets

n%i=sum[(n-j)%j|j<-take n[1..i+1]]+0^n
(%0)

Voir réponse Python pour l'explication.

Même longueur avec minplutôt que take:

n%i=sum[(n-j)%j|j<-[1..min(i+1)n]]+0^n
(%0)
xnor
la source
1

Matlab, 115 105 octets

function F=t(n,varargin);p=1;if nargin>1;p=varargin{1};end;F=p==n;if p<n;for q=1:p+1;F=F+t(n-p,q);end;end

Mise en œuvre de la formule récursive trouvée ici: https://oeis.org/A005169

function F=t(n,varargin);
p=1;
if nargin>1
    p=varargin{1};
end;
F=p==n;
if p<n;
    for q=1:p+1;
        F=F+t(n-p,q);
    end;
end;
flawr
la source
1

Julia, 44 43 octets

f(a,b=1)=a>b?sum(i->f(a-b,i),1:b+1):1(a==b)

Cela utilise une formule récursive sur OEIS.

Explication

function f(a, b=1)
    if a > b
        # Sum of recursing
        sum(i -> f(a-b, i), 1:b+1)
    else
        # Convert bool to integer
        1 * (a == b)
    end
end

Quelqu'un d'autre a-t-il remarqué que la grève à travers 44 est régulière à 44 ??

Télécopieur
la source
0

Python 3, 88 octets

f=lambda n,p:sum([f(n-p,q)for q in range(1,p+2)])if p<n else int(p==n)
t=lambda n:f(n,1)
monopole
la source
0

JavaScript (ES6), 63

Implémentation de la formule récursive sur la page OEIS

F=(n,p=1,t=0,q=0)=>p<n?eval("for(;q++<=p;)t+=F(n-p,q)"):p>n?0:1
edc65
la source