Pouvez-vous jouer au golf?

53

Vous devez générer un parcours de golf de 18 trous au hasard.

Exemple de sortie:

[3 4 3 5 5 4 4 4 5 3 3 4 4 3 4 5 5 4]

Règles:

  • Votre programme doit générer une liste de longueurs de trous pour exactement 18 trous
  • Chaque trou doit avoir une longueur de 3, 4 ou 5
  • La longueur des trous doit atteindre 72 pour tout le parcours
  • Votre programme doit être capable de produire toutes les configurations de trous possibles avec une probabilité non nulle (les probabilités de chaque configuration ne doivent pas nécessairement être égales, mais n'hésitez pas à réclamer des félicitations supplémentaires si tel est le cas).
Mikera
la source
3
S'il vous plaît confirmer, 44152809 solutions?
bébé-lapin
1
Moi aussi je suis curieux du nombre exact de solutions, mais je pense que cela devrait être plus de 44 millions ... (je ne suis pas mathématicien cependant: | 1 (5) / 1 (3) = 306 possibilités (17 * 18) | 2 (5) / 2 (3) = 69360 poss (17 * 17 * 16 * 15) | 3 (5) / 3 (3) = 11182080 poss (16 * 16 * 16 * 15 * 14 * 13) | fait ça a l'air correct?
NRGdallas
11
@ bébé-lapin: je peux confirmer 44 152 809 solutions par énumération par force brute. En outre, il peut être calculé directement la façon suivante : puisque la moyenne est exactement 4, et les seules possibilités sont 3, 4ou 5, les classes solution sont { no 3's or 5's, one 3 and one 5, two 3's and two 5's, ..., nine 3's and nine 5's}. Ceci peut être calculé par nCr(18,0)*nCr(18,0) + nCr(18,1)*nCr(17,1) + nCr(18,2)*nCr(16,2) + ... + nCr(18,9)*nCr(9,9) = 44,152,809. Cela signifie qu'environ 11.4%toutes les combinaisons possibles sont des solutions valides (44,152,809 / 3^18).
mellamokb
2
sum(factorial(18)/factorial(x)/factorial(y)/factorial(z) for x in range(25) for y in range(25) for z in range(25) if 3*x+4*y+5*z == 72 and x+y+z == 18)donne44152809L
Sanjeev Murty

Réponses:

29

k ( 18 17 16 caractères)

Retour à l'approche originale, créditons CS pour l'amélioration.

(+/4-){3+18?3}/0

Autre approche (17 caractères), même méthode que la solution J, H / T à CS

4+a,-a:9?2 -18?18

Ancienne version:

(72-+/){18?3+!3}/0

Non susceptible de déborder de la pile et s'exécute dans un espace d'espace fixe.

Skeevey
la source
Qu'est-ce que H / T à CS?
Gareth
Ce programme m'a aidé à découvrir un bug dans mon interprète K - merci! Je n'avais pas réalisé précédemment que les nilads pouvaient être appliqués à un seul argument (qu'ils ignorent).
JohnE
17

K, 28

{$[72=+/s:18?3 4 5;s;.z.s`]}
tmartin
la source
15

J, 20 18 17 caractères

(?~18){4+(,-)?9#2

Cela fonctionne de la même manière que la réponse précédente, à ceci près que les 9 chiffres aléatoires sont 0 ou 1 et sont annulés avant d’être ajoutés. Cela signifie qu'il y a autant de -1s que de 1s. Ajouter 4 me donne une liste de 3s, 4s et 5s qui totalisent 72 à chaque fois.

Réponse précédente:

({~?~@#)3+(,2-])?9#3

Génère les 9 premiers trous de manière aléatoire ?9#3, puis les copie et les inverse (,2-])(transforme un 3 en un 5 et un 5 en un 3) pour générer le 9 final. Cela garantit que le total sera de 72 (puisque tous les 3 auront un Le total moyen par trou sera de 4 et 4x18 = 72). Il ({~?~@#)mélange ensuite le résultat au hasard pour s'assurer que chaque combinaison est possible.

Gareth
la source
en fait, vous ne générerez pas {3,5,4,4,4 ...} il est préférable de mélanger tout le résultat
fratchet freak
@rachetfreak Bon point. Je vais éditer maintenant.
Gareth
13

Code machine x86 16 bits sous MS-DOS - 45 octets

Hexdump:

0E5F576A12595188ECE44088C3E44130D8240374F400C4AAE2EF595E80FC2475DFAC0432CD29B020CD29E2F5C3

Binaire codé en Base64:

Dl9XahJZUYjs5ECIw+RBMNgkA3T0AMSq4u9ZXoD8JHXfrAQyzSmwIM0p4vXD

Le code source actuel avec quelques commentaires:

 bits 16
 org 0x100

again:
 push cs               ; Save whatever CS we get.
 pop di                ; Use CS:DI as our course buffer..
 push di               ; Save for later use in the print loop
 push 18               ; We need 18 holes for our golf course.
 pop cx                ; ch = 0, cl = 18.
 push cx               ; Save for later use.
 mov ah, ch            ; Zero out ah.
generate_course:
 in al, 0x40           ; Port 0x40 is the 8253 PIT Counter 0.
 mov bl, al            ; Save the first "random" value in bl.
 in al, 0x41           ; Port 0x41 is the 8253 PIT Counter 1.
 xor al, bl            ; Add some more pseudo randomness.
 and al, 3             ; We only need the two lower bits.
 jz generate_course    ; If zero, re-generate a value, since we need only 3, 4, 5 holes.
 add ah, al            ; Sum in ah register.
 stosb                 ; Store in the course buffer.
 loop generate_course  ; Loop for 18 holes.
 pop cx                ; cx = 18.
 pop si                ; si = course buffer.
 cmp ah, 36            ; 72 holes?
 jne again             ; No, re-generate the whole course.

print:                 ; Yup, we have a nice course.
 lodsb                 ; Load the next hole.
 add al, '2'           ; Add ASCII '2' to get '3', '4' or '5'
 int 0x29              ; Undocumented MS-DOS print function.
 mov al, ' '           ; Print a space too for better readability.
 int 0x29              ; Print the character.
 loop print            ; Print the whole course.
 ret                   ; Return to the beginning of the PSP where a INT 0x20 happen to be.

Compilez avec nasm 18h.asm -o 18h.comet exécutez-vous sous MS-DOS (ou Dosbox) ou NTVDM à partir d'une version Windows 32 bits.

Exemple de sortie:

4 5 4 5 4 5 3 4 3 4 3 4 4 5 4 3 5 3
Jonas Gulle
la source
3
amour assembleur ...
woliveirajr
13

Mathematica 71 68 66 60

Avec 6 caractères sauvés par la suggestion de Tally.

RandomSample@RandomChoice@IntegerPartitions[72, {18}, {3, 4, 5}]

{5, 4, 3, 3, 5, 3, 5, 5, 3, 3, 4, 5, 3, 5, 4, 4, 5, 3}

Tous les résultats possibles sont possibles, mais ils ne sont pas également probables.


Une analyse

IntegerPartitions[72, {18}, {3, 4, 5}]

produit toutes les 10 partitions possibles (combinaisons, pas permutations) de 72 en 18 éléments composés de 3, 4 et 5.

des cloisons


RandomChoice sélectionne l'un d'entre eux.

RandomSample renvoie une permutation de ce choix.

DavidC
la source
Hé hé, je suis sur le point de publier presque exactement la même réponse, en utilisant seulement RandomChoice au lieu de RandomInteger. Je pense que vous pouvez raser 4 autres personnages en le faisant.
Tally
Tally, merci. Votre suggestion était utile.
DavidC
8

R - 41

x=0;while(sum(x)!=72)x=sample(3:5,18,T);x

# [1] 5 3 5 3 3 3 3 3 5 4 5 4 5 4 4 5 5 3

L'algorithme est similaire à celui de @ sgrieve.

flodel
la source
Même problème que @sgrieve ci-dessus - rien ne l’empêche de passer par 18 trous.
gt6989b
3
Ce n'est pas un problème, l'exemple de commande génère toujours 18 valeurs.
samedi
8

GolfScript (26 caractères)

{;0{3rand.3+@@+(}18*])}do`

Il y a des similitudes évidentes avec la solution d'Ilmari, mais aussi des différences évidentes. En particulier, j'exploite le fait que le pair moyen est de 4.

Peter Taylor
la source
Bon sang, mais c’est un truc astucieux avec la condition de boucle. Je me suis inventé {;0{3.rand+.@+}18*])72-}domoi-même, mais je ne savais pas comment le raccourcir à partir de là. +1
Ilmari Karonen
7

Python 77

Code

from numpy.random import*;l=[]
while sum(l)!=72:l=randint(3,6,18)
print l

Sortie

[3 4 4 5 3 3 3 5 4 4 5 4 5 3 4 4 5 4]

L'import tue vraiment cette solution. Il utilise numpy pour générer 18 nombres compris entre 3 et 5 et continue de générer des listes jusqu'à ce que la somme de la liste soit égale à 72.

sgrieve
la source
Qu'est-ce qui empêche le programme d'atteindre 72 avant de générer 18 trous? Qu'est-ce qui l'empêche de sauter 72?
DavidC
3
Le code générera toujours 18 trous, puis vérifiez si la somme est égale à 72. Par exemple, si la somme après 16 trous était de 72, il générerait encore 2 autres trous, poussant ainsi la somme au-dessus de 72 et échouant au test.
samedi
7

GolfScript, 27 caractères

{;18{3.rand+}*].{+}*72-}do`

Utilise la même méthode d'échantillonnage de rejet que la solution Python de sgrieve. Ainsi, chaque sortie valide est également probable.

Ilmari Karonen
la source
7

Q (25 caractères)

Original (27)

while[72<>sum a:18?3 4 5];a

Échantillon de sortie

4 4 3 3 4 5 4 3 4 5 5 3 5 5 5 4 3 3

Un peu plus court (25)

{72<>sum x}{x:18?3 4 5}/0
sinedcm
la source
7

JavaScript, 66 64 61 caractères

Fortement inspiré par TwoScoopsofPig (PHP) et Joe Tuskan (JS).

for(a=[s=0];s!=72;)for(s=i=0;i<18;s+=a[i++]=Math.random()*3+3|0);a

for(a=[s=0];s-72;)for(s=i=0;i<18;s+=a[i++]=Math.random()*3+3|0)a

for(a=s=[];s;)for(i=18,s=72;i;s-=a[--i]=Math.random()*3+3|0)a
Grawity
la source
2
s!=72peut être s-72pour sauver un caractère. Et le dernier point-virgule ;an'est pas nécessaire non plus pour un autre personnage.
Joe Tuskan
Je n'ai jamais vu for(i=x;i;i--)auparavant, il enregistre 2 caractères for(i=0;i<x;i++), merci mec!
Math Chiller
7

Python 2, 70 octets

from random import*
print sample(([3,5]*randint(0,9)+[4]*99)[:18],18)
modifier:

En voici un autre, similaire à la solution de sgrieve:

Python 2, 73 octets + probabilité égale

from random import*
a=[]
while sum(a)-72:a=sample([3,4,5]*18,18)
print a
Daniero
la source
5

JavaScript, 116 99 65 octets

for(i=0,h=[];i<18;)h[i++]=5;while(h.reduce(function(a,b){return a+b})!=72){i=Math.random()*18|0;h[i]=[3,4,4][i%3]}h;

h=[0];while(h.reduce(function(a,b){return a+b})-72)for(i=0;i<18;h[i++]=[3,4,5][Math.random()*3|0])h

while(i%18||(a=[i=s=0]),s+=a[i++]=Math.random()*3+3|0,s-72|i-18)a
Joe Tuskan
la source
1
Quand je lance ceci dans Chrome 21, je reçois i is not defined.
mellamokb
5

Python, 128 120 116 caractères

import random,itertools
random.choice([g for g in itertools.product(*(range(3,6)for l in range(18))) if sum(g)==72])

import les instructions sont toujours des tueurs de longueur (23 caractères pour importer 2 fonctions dans l'espace de noms)

J'espère que vous n'aurez pas besoin du résultat dans un proche avenir, car ce code évalue d'abord toutes les solutions possibles avant d'en choisir une au hasard. peut-être la solution la plus lente à ce problème.

Je réclame des félicitations supplémentaires pour une probabilité égale de chaque configuration ...

Adrien Plisson
la source
4
import random,itertools
Grawity
vous avez raison, cela raccourcit un peu les choses.
Adrien Plisson le
Autres conseils: import random as r,itertools as iutilisez ensuite ret à la iplace de randomet itertools. Utilisez 18*[0]au lieu de range(18), et [3,4,5,6]au lieu de range(3,6):)
Alex L
J'utilise python 3: une liste de compréhension est un générateur et n'a pas de longueur, ce qui interdit son utilisation avec la choice()fonction. c'est aussi ce qui rend ce code si lent ...
Adrien Plisson le
1
ooops, désolé, j'ai gâché la compréhension de la liste et l'expression du générateur (j'évite généralement la compréhension de la liste au profit de l'expression du générateur en raison de la meilleure performance de l'itérateur). Donc, en effet, même en python3, je peux toujours supprimer certains caractères ... @Alex l'a bien fait.
Adrien Plisson le
4

PHP - 77 caractères

<?while(array_sum($a)!=72){for($i=0;18>$i;){$a[++$i]=rand(3,5);}}print_r($a);

Un peu comme la solution de sgrieve, cela construit une liste de 18 trous, vérifie le total pair, et l’imprime ou le rejette et essaie à nouveau. Curieusement, nos deux solutions ont la même longueur.

Plutôt ennuyeux, PHP n'offre pas de fonctions de tableau avec un nom aussi bref. Array_sum et print_r me tuent. Suggestions bienvenues.

TwoScoopsofPig
la source
1
Les accolades ne sont pas nécessaires ici, et la somme peut être +=. <?while($s!=72)for($s=$i=0;18>$i;$s+=$a[++$i]=rand(3,5));print_r($a);
Grawity
C'est utile - je n'ai jamais pensé mettre la logique dans l'appel de la boucle for (et je me sens un peu idiot de ne pas incrémenter un compteur pour la somme).
TwoScoopsofPig
Merci - mais ce n'est pas ce que je voulais dire par "accolades inutiles"; vous auriez aussi pu les supprimer dans le code d'origine:while(array_sum($a)!=72)for($i=0;18>$i;)$a[++$i]=rand(3,5);
grawity le
Bien sauf que je cours contre un php.ini plus strict que ça parce que je joue au golf au travail; il se plaint sans fin des accolades manquantes / incompatibles. Normalement j'aurais.
TwoScoopsofPig
C'est étrange; 5.4.7 avec E_ALL | E_STRICT ne se plaint jamais des manquants {}(puisque la syntaxe de PHP le permet explicitement).
Grawity
4

Ruby 1.9 (62 caractères)

a=Array.new(18){[3,4,5].sample}until(a||[]).inject(:+)==72
p a

Rails (55 caractères)

Dans le $ rails cREPL (dans n'importe quel dossier Rails):

a=Array.new(18){[3,4,5].sample}until(a||[]).sum==72
p a

Remarque: cela fonctionne avec Ruby 1.8 si vous utilisez à la shuffle[0]place de sample.

js-coder
la source
2
Avez-vous besoin d'espaces autour de jusqu'à?
Kaz
@ Kaz Vous avez raison, ce n'est pas nécessaire. :) 62 caractères maintenant.
js-coder
1
Vous pouvez utiliser (1..18).map{rand(3)+3}pour obtenir le tableau aléatoire;)
epidemian
4

Lisp ( 78 69 caractères)

(do ((c ()) (mapcar (lambda (x) (+ 3 (aléatoire 3))) (liste de sélection 18)))) ((= (appliquer '+ c) 72) c))

(do((c()(loop repeat 18 collect(+ 3(random 3)))))((=(apply'+ c)72)c))

C'est assez similaire à la solution Python de sgrieve.

Commencez avec c comme NIL, vérifiez pour un montant de 72, le do "fonction d’incrément" de c génère une liste de 18 nombres compris entre 3 et 5, recherchez 72 de plus, faites mousser, rincez, répétez.

C'est rafraîchissant de voir doet de loopjouer au golf ensemble.

Wintermute
la source
3

C (123 caractères) - effort d'efficacité

Passez par wc et il générera toutes les solutions 44152809 en 10 secondes ...

char s[19];g(d,t){int i;if(d--){for(i=51,t-=3;i<54;i++,t--)if(t>=3*d&&t<=5*d)s[d]=i,g(d,t);}else puts(s);}main(){g(18,72);}

Oh, bien - je n'ai pas bien lu la question - mais étant donné que nous générons toutes les solutions, en choisir une au hasard avec une probabilité égale est un exercice de script: P

bébé-lapin
la source
3

Clojure - 55

(shuffle(mapcat #([[4 4][3 5]%](rand-int 2))(range 9)))

Une astuce assez amusante .... exploite la structure mathématique du problème selon laquelle il doit y avoir exactement autant de trous 3 en par que de 5 en trous.

Mikera
la source
3

Python 83

import random as r;x=[]
while sum(x)!=72:x=[r.randint(3,5) for i in 18*[0]]
print x

Comme la solution de sgrieve, mais sans numpy

La solution de golf d'Adrien Plisson: 120 -> 108 personnages

import random as r,itertools as i
r.choice([g for g in i.product(*([3,4,5,6]for l in 18*[0]))if sum(g)==72])

MATLAB 53

x=[];
while sum(x)~=72
x=3+floor(rand(1,18)*3);
end
x

Sortie :

x = 4 3 4 4 4 4 5 5 4 4 3 4 4 3 5 3 5 4 5

Alex L
la source
Belle approche, mais vous pouvez économiser 4 octets en tapant à la randi([3,5],1,18)place de3+floor(rand(1,18)*3)
brainkz
3

Java (61 caractères)

while(s!=72)for(i=0,s=0;i<18;i++)s+=3+(int)(Math.random()*3);

Exemple de sortie:

5 4 3 4 5 3 4 4 3 5 4 4 4 4 3 4 4 5
Quasar
la source
Je ne suis pas un expert de Java, mais ne devrait-il pas y avoir une déclaration de s et i, et une sorte d’appel à System # println (..)?
hiergiltdiestfu
Ceci est juste un extrait de code, pas un programme. Et cela ressemble beaucoup à la version C de @JoeIbanez.
Franz D.
2

C (94 caractères)

int h[18],s=0,i;
while(s!=72)for(i=s=0;i<18;s+=h[i++]=rand()%3+3);
while(i)printf("%d ",h[--i]);

La s=0ligne 1 peut ne pas être nécessaire, car quelles sont les chances qu'un int non initialisé soit égal à 72? Je n'aime tout simplement pas lire les valeurs non initialisées en C droit. De plus, cela nécessite probablement de semer la rand()fonction.

sortie

3 3 3 4 5 5 3 3 4 5 5 4 3 4 5 5 5 3 
Joe Ibanez
la source
Donc, fondamentalement, vous allez parcourir des chaînes aléatoires de 18 nombres compris entre 3 et 5 jusqu'à ce que l'un soit égal à 72? Bonne chose l'efficacité n'est pas une condition requise.
KeithS
5
@KeithS Pour être juste, c'est ce que la majorité des réponses à cette question font.
Gareth
2

Script shell Bash (65 caractères)

shuf -e `for x in {0..8}
do echo $((r=RANDOM%3+3)) $((8-r))
done`

( shuf vient du paquet GNU coreutils. Merci également à Gareth.)

Veuillez vous lever
la source
2

C # (143 espaces non blancs):

()=>{
  var n=new Math.Random().Next(10);
  Enumerable.Range(1,18)
    .Select((x,i)=>i<n?3:i>=18-n?5:4)
    .OrderBy(x=>Guid.NewGuid())
    .ForEach(Console.Write);
}
KeithS
la source
new Guid()crée un GUID vide. Pour générer réellement un GUID unique, vous devez appeler une méthode statique Guid.NewGuid.
Rotsor
Et vous avez deux erreurs différentes (pour ainsi dire): les comparaisons doivent être i <n et i> = 18-n, et non l'inverse. Et vous pouvez réduire la taille en utilisant une constante 3 au lieu de x-1 et 5 au lieu de x + 1. Et puis vous pourriez remplacer Enumerable.Repeat par Enumerable.Range.
Mormegil
Édité; encore 143 caractères
KeithS
Il n'y a pas Math.Random, c'est System.Random.
CodesInChaos
Une autre approche C # (143 caractères):var r=new Random();for(;;){var e=Enumerable.Range(1,18).Select(i=>r.Next(3,6)).ToList();if(e.Sum()==72){e.ForEach(i=>Console.Write(i));break;}}
thepirat000
2

Haskell, 104 102 98 caractères.

import System.Random
q l|sum l==72=print l|1>0=main
main=mapM(\_->randomRIO(3::Int,5))[1..18]>>=q
Rotsor
la source
[1..n]>>[r]est légèrement plus court que replicate n$r.
cessé de tourner dans le sens anti-horaire le
Aussi changé sequencepour mapM.
Rotsor
2

Perl, 74

{@c=map{3+int rand 3}(0)x18;$s=0;$s+=$_ for@c;redo unless$s==72}print"@c"

Solution alternative:

@q=((3,5)x($a=int rand 9),(4,4)x(9-$a));%t=map{(rand,$_)}(0..17);print"@q[@t{sort keys%t}]"
o_o
la source
2

TXR (99 caractères)

@(bind g@(for((x(gen t(+ 3(rand 3))))y)(t)((pop x))(set y[x 0..18])(if(= [apply + y]72)(return y))))

Cette expression génère une liste paresseuse infinie de nombres aléatoires de 3 à 5:

(gen t (+ 3(rand 3)))  ;; t means true: while t is true, generate.

Le reste de la logique est une simple boucle qui vérifie si les 18 premiers éléments de cette liste totalisent 72. Sinon, un élément est retiré et réessayé. La forboucle contient un bloc implicite appelé nilet (return ...)peut donc être utilisé pour terminer la boucle et renvoyer la valeur.

Notez que la longueur de 99 caractères inclut une nouvelle ligne de terminaison, obligatoire.

Kaz
la source
Je mets dans un commit qui permet de remplacer le (t) par (). :)
Kaz
2

APL 12

4+{⍵,-⍵}?9⍴2

Notez que l'origine de l'index est définie sur 0, ce qui signifie que les tableaux commencent à 0. Vous pouvez définir ceci avec ⎕IO←0.

Zaq
la source
La question demande à un programme capable de produire toutes les configurations possibles. Le vôtre peut produire des simmetric. Vous ne pouvez pas produire, par exemple, 55545555555333333343, du moins me semble-t-il.
Moris Zucca
2

R, 42 octets

a=0;while(sum(a)-72)a=sample(3:5,18,r=T);a

sample, par défaut, tire uniformément parmi les valeurs possibles (ici 3 4 5). r=Treprésente replace=TRUEet permet l'échantillon avec remplacement.

planificateur
la source
2

CJam, 17 14 octets

CJam est plus récent que ce défi, mais ce n'est pas la réponse la plus courte de toute façon, donc cela n'a pas vraiment d'importance.

Z5]Amr*I4e]mrp

Testez-le ici.

Pour maintenir le total de 72, chacun 3doit être associé 5. Alors, voici comment cela fonctionne:

Z5]            e# Push [3 5].
   Amr         e# Get a random number between 0 and 9.
      *        e# Repeat the [3 5] array that many times.
       I4e]    e# Pad the array to size 18 with 4s.
           mr  e# Shuffle the array.
             p e# Print it.
Martin Ender
la source