Wytnij złoty łańcuch

32

Podróżny musi zostać na n dni w hotelu poza miastem. Brakuje mu gotówki, a jego karta kredytowa wygasła. Ale ma złoty łańcuch z n ogniwami.

W tym hotelu obowiązuje zasada, że ​​mieszkańcy powinni płacić czynsz każdego ranka. Podróżny dochodzi do porozumienia z menedżerem, aby płacić jedno ogniwo złotego łańcucha za każdy dzień. Ale menedżer wymaga również, aby podróżny wyrządzał jak najmniejsze szkody w łańcuchu, płacąc codziennie. Innymi słowy, musi znaleźć rozwiązanie, aby wyciąć jak najmniej linków.

Wycięcie linku tworzy trzy podłańcuchy: jeden zawierający tylko wycięty link i jeden z każdej strony. Na przykład przecięcie trzeciego ogniwa łańcucha o długości 8 tworzy podłańcuchy o długości [2, 1, 5]. Menedżer chętnie dokonuje zmian, aby podróżny mógł zapłacić pierwszego dnia łańcuchem długości 1, a następnie drugiego dnia łańcuchem długości 2, odzyskując pierwszy łańcuch.

Twój kod powinien wprowadzić długość n i wypisać listę linków do wycięcia o minimalnej długości.

Zasady :

  • n jest liczbą całkowitą> 0.
  • Możesz użyć indeksowania opartego na 0 lub 1 dla linków.
  • W przypadku niektórych liczb rozwiązanie nie jest unikalne. Na przykład, jeśli n = 15obie [3, 8]i [4, 8]są ważne wyjścia.
  • Możesz albo zwrócić listę, albo wydrukować ją z dowolnym rozsądnym separatorem.
  • To jest , więc wygrywa najkrótszy kod w bajtach.

Przypadki testowe :

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

Szczegółowy przykład

Dla n = 15 przecięcie ogniw 3 i 8 powoduje utworzenie podłańcuchów długości [2, 1, 4, 1, 7]. To prawidłowe rozwiązanie, ponieważ:

 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

Nie ma rozwiązania z tylko jednym cięciem, więc jest to optymalne rozwiązanie.

Uzupełnienie

Zauważ, że ten problem dotyczy partycjonowania liczb całkowitych. Szukamy partycji P od n takie, że wszystkie liczby całkowite od 1 do n mają co najmniej jeden patition który jest podzbiorem P .

Oto film na YouTube o jednym możliwym algorytmie dla tego problemu.

polfosol ఠ_ఠ
źródło
Nie rozumiem twojego odniesienia do „dokonywania zmian”. W opublikowanym przykładzie drugiego dnia płacisz łańcuchem 2-ogniwowym (i otrzymujesz łańcuch 1-ogniwowy (który zapłaciłeś dzień wcześniej) z powrotem jako zmianę, zgodnie z wyjaśnieniem). Ale trzeciego dnia płacisz 1+2. Skąd wziął się drugi 2-ogniwowy łańcuch?
Flater
4
@ Flater Ten menedżer już go ma. Po prostu płacimy dodatkowy. W rzeczywistości RHS to linki, które menedżer posiada każdego dnia
polfosol ఠ_ఠ

Odpowiedzi:

15

05AB1E , 23 11 8 bajtów

ΔÍN-;иg=

Wypróbuj online!

Wykorzystuje indeksowanie 0.

Wyjaśnienie:

             # 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

иgwygląda jak noop, ale w rzeczywistości robi dwie użyteczne rzeczy: obcina się do liczby całkowitej ( ;zwraca liczbę zmiennoprzecinkową) i powoduje awarię interpretera, jeśli x jest ujemny (jest to jedyny warunek wyjścia).


W rozwiązaniu 23-bajtowym zastosowano zupełnie inne podejście, więc tutaj jest to dla potomności: ÅœʒR2äθP}ʒæOê¥P}θ2äθη€O( TIO , wyjaśnienie ).

Ponury
źródło
2
Usunąłem swoją odpowiedź. Mój wiek 42 i twój wiek 11 to zbyt duża różnica, abym nie czuł się zawstydzony, haha. ;) Ładna odpowiedź, i lol na Ø.Ø. Czy próbowałeś tylko losowych rzeczy, aby zmapować i zmapować wszystkie negatywy -1? Niezależnie od tego bardzo miła odpowiedź i znacznie krótsza niż się spodziewałem. Myślałem o około 20 bajtach po tym, jak opublikowałem mój zły 42-bajt.
Kevin Cruijssen
2
@KevinCruijssen Nnope, Ø.Øbył właściwie moim pierwszym pomysłem. Twój komentarz zainspirowało mnie do próby losowe rzeczy: znalazłem ®Ÿà, ï®Mi co ważniejsze иg, co daje ten miły 8-byter. Zawsze denerwowało mnie to, że w wielu przypadkach osabie woli nic nie robić niż awarie (div przez 0, zły typ itp.), Więc ta awaria się przyda.
Grimmy,
2
Hehe, 05AB1E ma nigdy nie upaść, ale masz rację, że czasami jest to trochę denerwujące, że nigdy tak się nie dzieje. W spuściźnie nie wiedziałbym nawet, jak się upaść, aw przeszłości mieliśmy nawet wyraźny podział według błąd zerowy możemy wywołać ręcznie. xD W nowej wersji nadal dość często zawiesza się z błędem przy podawaniu błędnych argumentów niektórym wbudowanym funkcjom. I znowu miłe -3.
Kevin Cruijssen
2
„powoduje awarię interpretera, jeśli x jest ujemne (jest to jedyny warunek wyjścia).” - Kocham to
John Dvorak
9

Python 2 , 75 bajtów

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

Wypróbuj online!


Wyjaśnienie:

Tworzy sekwencję „binarnych” fragmentów, których liczba bazowa odpowiada liczbie cięć.

Na przykład:

63 można wykonać w 3 cięciach, co oznacza partycję w podstawie 4 (ponieważ mamy 3 pojedyncze pierścienie):

Cięcia:, 5, 14, 31który daje łańcuchy 4 1 8 1 16 1 32(posortowane:) 1 1 1 4 8 16 32.

Wszystkie numery mogą być wykonane:

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

Inne przykłady:

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
źródło
1
Nie powinieneś dodawać f=na początek? Ponieważ używasz wywołania do fw funkcji lambda, a ja mogę jedynie założyć, że odwołujesz się do tej samej lambda, którą definiujesz.
randomdude999
@ randomdude999, Tak, zapomniałem ...
TFeld
@ randomdude999 czy ta reguła dotyczy wszystkich języków, czy tylko python? Bo widzę odpowiedź javascript, która jest czystą lambda w tym wyzwaniu ...
Shadow
3
@Shadow Dotyczy wszystkich języków, ale tylko rekurencyjnych lambd.
TFeld
1
@Shadow Bardziej ogólną zasadą jest to, że nie możesz odwoływać się do czegoś, co nie jest zdefiniowane w twoim kodzie ani globalnie zdefiniowane w twoim języku, chyba że jest to wyraźnie dozwolone przez wyzwanie. Najczęstszym przypadkiem jest funkcja rekurencyjna, ale dotyczy to innych sytuacji. Ta odpowiedź jest kolejnym przykładem: fnie jest rekurencyjna, ale jest jednak wymieniona w kodzie i dlatego musi zostać nazwana.
Arnauld
8

R , 77 69 bajtów

-8 bajtów dzięki Aaronowi Haymanowi

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

Wypróbuj online!

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

(Ostatni łańcuch może wymagać skrócenia, jeśli przekroczymy całkowitą długość łańcucha).

Ungolfed (na podstawie poprzedniej, podobnej wersji):

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+12)k+12)k+2)4k+4k(k+1)2)k-1.)

za(k)nkza(k)

Robin Ryder
źródło
Wątpię, czy pomogłoby to w specjalnym przypadku n=1, ale alternatywnym sposobem generowania wartości odcięcia jest powtórzenie 1, 4, 4a(n-1)-4a(n-2).
Peter Taylor
@PeterTaylor Miałem podobną powtarzalność dla komputerów k; odpowiada to OEIS A134401: oeis.org/A134401 Ale moja implementacja relacji powtarzalności zajmuje więcej bajtów niż bieżący kod.
Robin Ryder
Trochę przegrupowań Mam go do 73. Wypróbuj online!
Aaron Hayman
@AaronHayman Thanks! Inteligentny ruch za pomocą sumzamiast match.
Robin Ryder
69 bajtów i pozbyłem się tego, co cię denerwowało: Wypróbuj online!
Aaron Hayman
3

Galaretka , 12 bajtów

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

Wypróbuj online!

Tłumaczenie odpowiedzi 05AB1E firmy Grimy, więc pamiętajcie o tym! Nieco rozczarowany pojawia się to w bajcie dłużej, ale ma przynajmniej coś w rodzaju emotikonu jako pierwsze trzy bajty!

Nick Kennedy
źródło
2

JavaScript (ES6), 66 bajtów

To jest port odpowiedzi TFeld .

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

Wypróbuj online!

Arnauld
źródło
2

C ++, 109 , 107 bajtów

-2 bajty dzięki Kevinowi

#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<<',';}

Algorytm jest podobny do odpowiedzi Robina Rydera. Kod jest napisany w kompilowalnej, całej formie. Spróbuj!

Detale:

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

Ma to odmianę C o tej samej długości bajtów (wydaje się, że nie wymaga osobnej odpowiedzi):

#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 ఠ_ఠ
źródło
Dwie drobne rzeczy do golfa: =0po kmożna usunąć, ponieważ 0jest to domyślnie. std::cin>>n;while(++k<<k<n);może być for(std::cin>>n;++k<<k<n;);. Mam też wrażenie, że for(n-=k;n>0;k*=2,n-=k+1)można to jakoś uprościć, łącząc różne rzeczy, ale nie jestem pewien, jak to zrobić. PS: Zmiana separatora przecinków na spację wygląda nieco lepiej, ponieważ nie widać końcowego imo, ale jest to czysto kosmetyczne :)
Kevin Cruijssen
1
@KevinCruijssen Dzięki, ale niektóre kompilatory nie przypisują wartości domyślnej do zmiennych niestatycznych. Pomyślałem więc, że jest =0to konieczne do przenoszenia;) Zdałem sobie również sprawę, że miejsce po #includenie jest konieczne.
polfosol ఠ_ఠ
Ach ok. Nie znam zbyt dobrze C ++, więc użyłem kompilatora online, który podałeś w odpowiedzi, aby przetestować niektóre rzeczy. :) Zapomniałeś drugiej zmiany, którą zaproponowałem w moim komentarzu: pętla while do pętli for i umieszczenie jej w std::cin>>nśrodku.
Kevin Cruijssen
103 bajty
ceilingcat
1

Retina 0.8.2 , 61 bajtów

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

Wypróbuj online! 1-indeksowany port odpowiedzi @ Grimy. Wyjaśnienie:

.+
11,$&$*

Zacznij od, N=2a dane wejściowe zostaną przekonwertowane na jednoargumentowe.

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

Wielokrotnie spróbuj odjąć Nod danych wejściowych, a następnie podzielić przez 2.

1$2¶1$1,$3

Jeśli się powiedzie, pamiętaj o 1 więcej niż dane wejściowe w poprzednim wierszu, zwiększ Nwartość w bieżącym wierszu i zaktualizuj dane wejściowe do nowej wartości.

1+,
1

Usuń Ni zwiększ ostatnią wartość, aby była ona również indeksowana 1.

1A`

Usuń pierwotnie zwiększoną wartość wejściową.

1+
$.&

Konwertuj wyniki na dziesiętne.

Neil
źródło
1

Rubin , 62 bajty

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

Wypróbuj online!

Najczęściej skradziony z odpowiedzi TFeld na Python.

GB
źródło