Couper la chaîne en or

32

Un voyageur doit rester n jours dans un hôtel situé en dehors de la ville. Il n'a plus d'argent et sa carte de crédit est expirée. Mais il a une chaîne en or avec n liens.

La règle dans cet hôtel est que les résidents doivent payer leur loyer tous les matins. Le voyageur conclut un accord avec le responsable pour payer un maillon de la chaîne en or chaque jour. Mais le responsable exige également que le voyageur fasse le moins de dégâts possible à la chaîne en payant tous les jours. En d'autres termes, il doit trouver une solution pour couper le moins de liens possible.

Couper un lien crée trois sous-chaînes: une contenant uniquement le lien coupé et une de chaque côté. Par exemple, couper le troisième maillon d'une chaîne de longueur 8 crée des sous-chaînes de longueur [2, 1, 5]. Le responsable est heureux de rendre la monnaie, de sorte que le voyageur puisse payer le premier jour avec la chaîne de longueur 1, puis le deuxième jour avec la chaîne de longueur 2, en récupérant la première chaîne.

Votre code doit entrer la longueur n et générer une liste de liens à couper de longueur minimale.

Règles :

  • n est un entier> 0.
  • Vous pouvez utiliser l'indexation 0 ou 1 pour les liens.
  • Pour certains numéros, la solution n'est pas unique. Par exemple, si les n = 15deux [3, 8]et [4, 8]sont des sorties valides.
  • Vous pouvez soit renvoyer la liste, soit l’imprimer avec un séparateur raisonnable.
  • C'est le , donc le code le plus court en octets gagne.

Cas de test :

Input          Output (1-indexed)
1              []
3              [1]
7              [3]
15             [3, 8]
149            [6, 17, 38, 79]

Exemple détaillé

Pour n = 15, couper les liens 3 et 8 donne des sous-chaînes de longueur [2, 1, 4, 1, 7]. C'est une solution valable pour les raisons suivantes:

 1 = 1
 2 = 2
 3 = 1+2
 4 = 4
 5 = 1+4
 6 = 2+4
 7 = 7
 8 = 1+7
 9 = 2+7
10 = 1+2+7
11 = 4+7
12 = 1+4+7
13 = 2+4+7
14 = 1+2+4+7
15 = 1+1+2+4+7

Il n’existe pas de solution avec une seule découpe, c’est donc une solution optimale.

Addenda

Notez que ce problème est lié au partitionnement entier. Nous sommes à la recherche d'une partition P de n tel que tous les entiers de 1 à n ont au moins un patition qui est un sous - ensemble de P .

Voici une vidéo YouTube sur un algorithme possible pour ce problème.

polfosol ఠ_ఠ
la source
Je ne comprends pas votre référence "faire le changement". Dans votre exemple posté, le deuxième jour, vous payez avec la chaîne à 2 maillons (et vous récupérez la chaîne à 1 maillon (que vous avez payée la veille) comme monnaie, conformément à votre explication). Mais le troisième jour, vous payez avec 1+2. D'où vient la deuxième chaîne à 2 maillons?
Flater
4
@Flater Le gestionnaire l'a déjà. Nous ne payons que le supplément. En fait, les RHS sont les liens que le gestionnaire possède chaque jour
polfosol ఠ_ఠ

Réponses:

15

05AB1E , 23 11 8 octets

ΔÍN-;иg=

Essayez-le en ligne!

Utilise l'indexation basée sur 0.

Explication:

             # start from the implicit input
Δ            # loop forever
 Í           # subtract 2
  N-         # subtract the current iteration number
    ;        # divide by 2
     и       # create a list of length x
      g      # get the length of the list
       =     # print

иgCela ressemble à un noop, mais il fait deux choses utiles: il tronque un entier ( ;renvoie un float) et bloque l'interpréteur si x est négatif (c'est la seule condition de sortie).


La solution à 23 octets utilisait une approche très différente, donc la voici pour la postérité: ÅœʒR2äθP}ʒæOê¥P}θ2äθη€O( TIO , explication ).

Grimmy
la source
2
J'ai supprimé ma réponse. Le mien étant 42 ans et le vôtre 11 ans est trop grand pour que je ne me sente pas gêné, haha. ;) Bonne réponse cependant, et lol à la Ø.Ø. Avez-vous simplement essayé des choses aléatoires afin d’établir un plan et de cartographier tous les négatifs -1? Quoi qu'il en soit, très bonne réponse et beaucoup plus courte que prévue. Je pensais environ 20 octets après avoir posté mon mauvais 42 octets.
Kevin Cruijssen
2
@KevinCruijssen Nnope, Ø.Øétait en fait ma première idée. Votre commentaire m'a inspiré pour essayer des choses au hasard: J'ai trouvé ®Ÿà, ï®Met plus important encore , иg, ce qui donne cette belle 8 byter. J'ai toujours trouvé ennuyeux qu'Osabie préfère ne rien faire en cas de plantage (div par 0, type incorrect, etc.), alors ce plantage sera utile.
Grimmy
2
Hé hé, 05AB1E est supposé ne jamais planter, mais vous avez raison de dire que c’est parfois un peu gênant que cela ne se produise jamais. zéro erreur, nous pourrions appeler manuellement. xD Dans la nouvelle version, il y avait encore assez souvent une erreur en donnant des arguments incorrects à certaines commandes intégrées. Et bien encore -3.
Kevin Cruijssen le
2
"bloque l’interprète si x est négatif (c’est la seule condition de sortie)." - J'aime ça
John Dvorak
9

Python 2 , 75 octets

f=lambda n,i=0:n>=i<<i and f(n,i+1)or[min(n,2**j*i-i+j)for j in range(1,i)]

Essayez-le en ligne!


Explication:

Construit une séquence de morceaux «binaires», avec un numéro de base correspondant au nombre de coupes.

Par exemple:

63 peut être fait en 3 coupes, ce qui signifie une partition en base 4 (comme nous avons 3 anneaux simples):

Cuts:, 5, 14, 31qui donne des chaînes de 4 1 8 1 16 1 32(trié:) 1 1 1 4 8 16 32.

Tous les nombres peuvent être faits:

1       1
2       1 1
3       1 1 1
4       4
...
42      1 1 8 32
...
62      1 1 4 8 16 32
63      1 1 1 4 8 16 32

Autres exemples:

18: 4,11        ->  3 1 6 1 7
27: 5,14,27     ->  4 1 8 1 13 1
36: 5,14,31     ->  4 1 8 1 16 1 5
86: 6,17,38,79  ->  5 1 10 1 20 1 40 1 7
TFeld
la source
1
Ne devriez-vous pas ajouter f=au début? Puisque vous utilisez un appel à fdans la fonction lambda, et je ne peux que supposer que vous vous référez au même lambda que vous définissez.
randomdude999
@ randomdude999, oui, j'ai oublié ...
TFeld
@ randomdude999 Cette règle s'applique-t-elle à toutes les langues, ou simplement à Python? Parce que je vois une réponse en javascript qui est un lambda pur dans ce défi ...
Shadow
3
@Shadow Cela s'applique à toutes les langues, mais uniquement aux lambdas récursifs.
TFeld le
1
@Shadow Une règle plus générique est que vous ne pouvez pas faire référence à quelque chose qui n'est ni défini dans votre code ni défini globalement dans votre langage, à moins que cela ne soit explicitement autorisé par le défi. Le cas le plus courant est une fonction récursive, mais cela s'applique à d'autres situations. Cette réponse est un autre exemple: fn'est pas récursif, mais il est cependant référencé dans le code et doit donc être nommé.
Arnauld
8

R , 77 69 octets

-8 octets grâce à Aaron Hayman

pmin(n<-scan(),0:(k=sum((a=2:n)*2^a<=n))+cumsum((k+2)*2^(0:k))+1)[-n]

Essayez-le en ligne!

kk(k+1)2kn1,1,,1k(k+1),2(k+1),4(k+1),8(k+1),,(k+1)2k1

(La dernière sous-chaîne devra peut-être être raccourcie si nous dépassons la longueur totale de la chaîne.)

Ungolfed (basé sur la version précédente similaire):

n = scan()                            # read input
if(n - 1){                            # If n==1, return NULL
  k = match(F, (a = 2:n) * 2 ^ a > n) # compute k
  b = (k + 1) * 2 ^ (1:k - 1)         # lengths of subchains
  c = 1:k + cumsum(b)                 # positions of cuts
  pmin(c, n )                         # if last value is >n, coerce it to n
}

kkkk+12k+12k+24k+4k(k+1)2k-1.)

une(k)nkune(k)

Robin Ryder
la source
Je doute que cela aiderait avec le cas particulier n=1, mais une autre façon de générer les seuils est la récurrence 1, 4, 4a(n-1)-4a(n-2).
Peter Taylor
@PeterTaylor I a eu une récurrence similaire pour l'informatique k; cela correspond à OEIS A134401: oeis.org/A134401 Mais mon implémentation de la relation de récurrence utilise plus d'octets que le code actuel.
Robin Ryder le
Un peu de réarrangement je l'ai eu à 73. Essayez-le en ligne!
Aaron Hayman le
@ AaronHayman Merci! Mouvement intelligent en utilisant sumau lieu de match.
Robin Ryder le
69 octets et vous en êtes débarrassé si une affirmation vous contrarie: essayez-la en ligne!
Aaron Hayman le
3

Gelée , 12 octets

’_‘ɼ:2»-µƬṖḊ

Essayez-le en ligne!

Traduction de la réponse 05AB1E de Grimy, assurez-vous donc de l'emporter également! Légèrement déçu, cela vient dans un octet plus long, mais a au moins quelque chose qui ressemble un peu à une émoticône que les trois premiers octets!

Nick Kennedy
la source
2

C ++, 109 , 107 octets

-2 octets grâce à Kevin

#include<iostream>
main(){int n,k=0;for(std::cin>>n;++k<<k<n;);for(n-=k;n>0;k*=2,n-=k+1)std::cout<<n<<',';}

L'algorithme est similaire à la réponse de Robin Ryder. Le code est écrit sous une forme complète compilable. Essayez le!

Détails:

std::cin>>n;               // get the value of n as input
while(++k<<k<n);           // determine k
for(n-=k;n>0;k*=2,n-=k+1)  // we don't need n, so the lengths...
    std::cout<<n<<' ';     // of links are subtracted repeatedly

Cela a une variation C avec la même longueur d'octet (ne semble pas avoir besoin d'une réponse séparée):

#include<stdio.h>
main(){int n,k=0;for(scanf("%d",&n);++k<<k<n;);for(n-=k;n>0;k*=2,n-=k+1)printf("%d,",n);}
polfosol ఠ_ఠ
la source
Deux choses mineures au golf: =0après kpeuvent être supprimés, puisque c'est 0par défaut. std::cin>>n;while(++k<<k<n);peut être for(std::cin>>n;++k<<k<n;);. J'ai aussi le sentiment que l' for(n-=k;n>0;k*=2,n-=k+1)on peut simplifier en combinant des choses, mais je ne sais pas comment. PS: Changer le séparateur de virgule en un espace est légèrement meilleur car vous ne voyez pas le dernier imo, mais c'est purement cosmétique :)
Kevin Cruijssen
1
@KevinCruijssen Merci, mais certains compilateurs n'attribuent pas de valeur par défaut aux variables non statiques. J'ai donc pensé que =0c'était nécessaire pour la portabilité;) J'ai aussi réalisé que l'espace après #includen'est pas nécessaire.
polfosol 19_ఠ
Ah ok. Je ne connais pas très bien le C ++, j'ai donc utilisé le compilateur en ligne que vous avez associé dans votre réponse pour tester certaines choses. :) Vous avez oublié le deuxième changement que j'ai proposé dans mon commentaire: la boucle while en une boucle for et y mettre l' std::cin>>nintérieur.
Kevin Cruijssen le
103 octets
ceilingcat le
1

Retina 0.8.2 , 61 octets

.+
11,$&$*
+`\b(1+),(\1(1*)1?\3)$
1$2¶1$1,$3
1+,
1
1A`
1+
$.&

Essayez-le en ligne! Port indexé 1 de la réponse de @ Grimy. Explication:

.+
11,$&$*

Commencez avec N=2et l'entrée convertie en unaire.

+`\b(1+),(\1(1*)1?\3)$

Essayez à plusieurs reprises de soustraire Nde l’entrée puis de diviser par 2.

1$2¶1$1,$3

En cas de succès, rappelez-vous de plus que l'entrée de la ligne précédente, incrémentez Nla ligne actuelle et mettez à jour l'entrée avec la nouvelle valeur.

1+,
1

Supprimez Net incrémentez la dernière valeur pour qu'elle soit également indexée sur 1.

1A`

Supprimez l'entrée d'origine incrémentée.

1+
$.&

Convertir les résultats en décimal.

Neil
la source
1

Ruby , 62 octets

->n{(1...c=(0..n).find{|r|n<r<<r}).map{|b|[n,b-c+(c<<b)].min}}

Essayez-le en ligne!

Surtout volé dans la réponse Python de TFeld.

GB
la source