32
\$\begingroup\$

A traveler needs to stay for n days in a hotel outside town. He is out of cash and his credit card is expired. But he has a gold chain with n links.

The rule in this hotel is that residents should pay their rent every morning. The traveler comes to an agreement with the manager to pay one link of the golden chain for each day. But the manager also demands that the traveler should make the least possible damage to the chain while paying every day. In other words, he has to come up with a solution to cut as few links as possible.

Cutting a link creates three subchains: one containing only the cut link, and one on each side. For example, cutting the third link of a chain of length 8 creates subchains of length [2, 1, 5]. The manager is happy to make change, so the traveller can pay the first day with the chain of length 1, then the second day with the chain of length 2, getting the first chain back.

Your code should input the length n, and output a list of links to cut of minimum length.

Rules:

  • n is an integer > 0.
  • You can use either 0-based or 1-based indexing for the links.
  • For some numbers, the solution is not unique. For example, if n = 15 both [3, 8] and [4, 8] are valid outputs.
  • You can either return the list, or print it with any reasonable separator.
  • This is , so the shortest code in bytes wins.

Test cases:

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

Detailed example

For n = 15, cutting the links 3 and 8 results in subchains of length [2, 1, 4, 1, 7]. This is a valid solution because:

 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

No solution with only one cut exists, so this is an optimal solution.

Addendum

Note that this problem is related to integer partitioning. We're looking for a partition P of n such that all integers from 1 to n have at least one patition that is a subset of P.

Here's a YouTube video about one possible algorithm for this problem.

\$\endgroup\$
  • \$\begingroup\$ I don't understand your "making change" reference. In your posted example, on the second day you pay with the 2-link chain (and get the 1-link-chain (which you paid with the day before) back as change, as per your explanation). But on the third day, you pay with 1+2. Where did the second 2-link-chain come from? \$\endgroup\$ – Flater Jun 18 at 11:04
  • 4
    \$\begingroup\$ @Flater The manager already has it. We just pay the additional one. In fact, the RHS are the links that manager owns each day \$\endgroup\$ – polfosol ఠ_ఠ Jun 18 at 11:17
15
\$\begingroup\$

05AB1E, 23 11 8 bytes

ΔÍN-;иg=

Try it online!

Uses 0-based indexing.

Explanation:

             # 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

иg looks like a noop, but it actually does two useful things: it truncates to an integer (; returns a float), and it crashes the interpreter if x is negative (this is the only exit condition).


The 23 byte solution used a very different approach, so here it is for posterity: ÅœʒR2äθP}ʒæOê¥P}θ2äθη€O (TIO, explanation).

\$\endgroup\$
  • 2
    \$\begingroup\$ I've deleted my answer. Mine being 42 and yours being 11 is too big of a difference for me to not feel embarrassed, haha. ;) Nice answer though, and lol at the Ø.Ø. Did you just try some random things in order to both floor and map all negatives to -1? Regardless, very nice answer and much shorter than I anticipated. I was thinking around 20 bytes after i posted my bad 42-byter. \$\endgroup\$ – Kevin Cruijssen Jun 17 at 16:37
  • 2
    \$\begingroup\$ @KevinCruijssen Nnope, Ø.Ø was actually my first idea. Your comment inspired me to try random things: I found ®Ÿà, ï®M, and more importantly, иg, which yields this nice 8-byter. I always found it annoying that osabie prefers doing nothing over crashing in many cases (div by 0, wrong type, etc), so this crash will come in handy. \$\endgroup\$ – Grimmy Jun 17 at 17:19
  • 2
    \$\begingroup\$ Hehe, 05AB1E is supposed to never crash, but you're right that it sometimes is a bit annoying it never does.. In the legacy I wouldn't even know how to crash, and in the past we even had an explicit division by zero error we could call manually. xD In the new version it still crashes with an error pretty often when giving incorrect arguments to certain builtins. And nice -3 again. \$\endgroup\$ – Kevin Cruijssen Jun 18 at 7:48
  • 2
    \$\begingroup\$ "crashes the interpreter if x is negative (this is the only exit condition)." - I love that \$\endgroup\$ – John Dvorak Jun 18 at 10:41
9
\$\begingroup\$

Python 2, 75 bytes

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

Try it online!


Explanation:

Builds a sequence of 'binary' chunks, with a base number matching the number of cuts.

Eg:

63 can be done in 3 cuts, which means a partition in base-4 (as we have 3 single rings):

Cuts: 5, 14, 31, which gives chains of 4 1 8 1 16 1 32 (sorted: 1 1 1 4 8 16 32).

All numbers can be made:

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

Other examples:

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Shouldn't you add f= to the start? Since you use a call to f in the lambda function, and I can only assume that you refer to the same lambda you're defining. \$\endgroup\$ – randomdude999 Jun 17 at 12:03
  • \$\begingroup\$ @randomdude999, Yeah, I forgot... \$\endgroup\$ – TFeld Jun 17 at 12:06
  • \$\begingroup\$ @randomdude999 does that rule apply to all languages, or just python? Cause I see a javascript answer that is a pure lambda in this challenge... \$\endgroup\$ – Shadow Jun 18 at 1:54
  • 3
    \$\begingroup\$ @Shadow It applies to all languages, but only for recursive lambdas. \$\endgroup\$ – TFeld Jun 18 at 5:10
  • 1
    \$\begingroup\$ @Shadow A more generic rule is that you can't reference something that is neither defined in your code nor globally defined in your language, unless it is explicitly allowed by the challenge. The most common case is a recursive function, but this applies to other situations. This answer is another example: f is not recursive, but it's however referenced in the code and therefore has to be named. \$\endgroup\$ – Arnauld Jun 18 at 6:41
8
\$\begingroup\$

R, 77 69 bytes

-8 bytes thanks to Aaron Hayman

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

Try it online!

Let \$k\$ be the number of cuts needed; \$k\$ is the smallest integer such that \$(k+1)\cdot2^k\geq n\$. Indeed, a possible solution is then to have subchains of lengths \$1,1,\ldots,1\$ (\$k\$ times) and \$(k+1), 2(k+1), 4(k+1), 8(k+1), \ldots, (k+1)\cdot 2^{k-1}\$. It is easy to check that this is sufficient and optimal.

(The last subchain might need to be made shorter if we exceed the total length of the chain.)

Ungolfed (based on previous, similar version):

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
}

(Proof that the value of \$k\$ is as I state: suppose we have \$k\$ cuts. We then have \$k\$ unit subchains, so we need the first subchain to be of length \$k+1\$. We can now handle all lengths up to \$2k+1\$, so we need the next one to be of length \$2k+2\$, then \$4k+4\$... Thus the maximum we can get out of \$k\$ cuts is obtained by summing all those lengths, which gives \$(k+1)\cdot 2^k-1\$.)

If \$a(k)\$ is the smallest integer \$n\$ requiring \$k\$ cuts, then \$a(k)\$ is OEIS A134401.

\$\endgroup\$
  • \$\begingroup\$ I doubt it would help with the special case for n=1, but an alternative way to generate the cutoffs is the recurrence 1, 4, 4a(n-1)-4a(n-2). \$\endgroup\$ – Peter Taylor Jun 17 at 22:28
  • \$\begingroup\$ @PeterTaylor I had a similar recurrence for computing k; this corresponds to OEIS A134401: oeis.org/A134401 But my implementation of the recurrence relation takes up more bytes than the current code. \$\endgroup\$ – Robin Ryder Jun 18 at 5:33
  • \$\begingroup\$ A bit of rearrangement I got it down to 73. Try it online! \$\endgroup\$ – Aaron Hayman Jun 18 at 9:06
  • \$\begingroup\$ @AaronHayman Thanks! Smart move using sum instead of match. \$\endgroup\$ – Robin Ryder Jun 18 at 9:41
  • \$\begingroup\$ 69 bytes and got rid of that if statement that was upsetting you: Try it online! \$\endgroup\$ – Aaron Hayman Jun 18 at 9:56
3
\$\begingroup\$

Jelly, 12 bytes

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

Try it online!

Translation of Grimy's 05AB1E answer so be sure to upvote that one too! Slightly disappointed this comes in a byte longer, but does at least have something a bit like an emoticon as the first three bytes!

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 66 bytes

This is a port of TFeld's answer.

n=>(g=a=>n<++i<<i?a.map(j=>(j+=(i<<j)-i)>n?n:j):g([...a,i]))(i=[])

Try it online!

\$\endgroup\$
2
\$\begingroup\$

C++, 109,107 bytes

-2 bytes thanks to 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<<',';}

The algorithm is similar to the Robin Ryder's answer. The code is written in a compilable, whole form. Try it!

Details:

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

This has a C variation with the same byte length (doesn't seem to need a separate answer):

#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);}
\$\endgroup\$
  • \$\begingroup\$ Two minor things to golf: =0 after k can be removed, since its 0 by default. std::cin>>n;while(++k<<k<n); can be for(std::cin>>n;++k<<k<n;);. I also have the feeling for(n-=k;n>0;k*=2,n-=k+1) can be simplified somehow by combining stuff, but not sure how. PS: Changing the comma-delimiter to a space looks slightly better since you don't see the trailing one imo, but this is purely cosmetic :) \$\endgroup\$ – Kevin Cruijssen Jun 19 at 10:58
  • 1
    \$\begingroup\$ @KevinCruijssen Thanks, but some compilers don't assign a default value to non-static variables. So I thought =0 was necessary for portability ;) I also realized that the space after #include is not necessary. \$\endgroup\$ – polfosol ఠ_ఠ Jun 19 at 11:02
  • \$\begingroup\$ Ah ok. I don't know C++ too well, so I've used that online compiler you linked in your answer to test some things. :) You forgot the second change I proposed in my comment: the while-loop to a for-loop and putting the std::cin>>n inside it. \$\endgroup\$ – Kevin Cruijssen Jun 19 at 11:08
  • \$\begingroup\$ 103 bytes \$\endgroup\$ – ceilingcat Jul 9 at 19:50
1
\$\begingroup\$

Retina 0.8.2, 61 bytes

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

Try it online! 1-indexed port of @Grimy's answer. Explanation:

.+
11,$&$*

Start with N=2 and the input converted to unary.

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

Repeatedly try to subtract N from the input and then divide by 2.

1$2¶1$1,$3

If successful, remember 1 more than the input on the previous line, increment N on the current line, and update the input to the new value.

1+,
1

Remove N and increment the last value so that it's also 1-indexed.

1A`

Remove the incremented original input.

1+
$.&

Convert the results to decimal.

\$\endgroup\$
1
\$\begingroup\$

Ruby, 62 bytes

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

Try it online!

Mostly stolen from TFeld's Python answer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.