Inspiracją dla tego kodu golfowego układanki jest problemem Bridge i latarki , w którym d ludzie na początku mostu wszystko musi przejechać ją w jak najkrótszym czasie.

Chodzi o to, że najwyżej dwie osoby mogą przejść jednocześnie, w przeciwnym razie most zmiażdży się pod ich ciężarem, a grupa ma dostęp tylko do jednej pochodni, którą należy zabrać, aby przejść przez most.

Każda osoba w całej układance ma określony czas na przejście przez most. Jeśli dwie osoby krzyżują się razem, para idzie tak wolno, jak najwolniejsza osoba.

Nie ma określonej liczby osób, które muszą przejść przez most; twoje rozwiązanie MUSI działać dla dowolnej wartości d .

Nie musisz używać standardowych danych wejściowych dla tego problemu, ale dla wyjaśnienia problemu użyję następującego formatu danych wejściowych i wyjściowych dla wyjaśnienia. Pierwsza liczba, d , to liczba osób na początku mostu. Następnie kod będzie skanował w poszukiwaniu cyfr d , z których każda reprezentuje prędkość osoby.

Wyjściowym kodem będzie NAJMNIEJ czas wymagany do przejścia wszystkich od początku mostu do końca mostu, przy jednoczesnym spełnieniu kryteriów wyjaśnionych wcześniej.

Oto niektóre przypadki wejściowe i wyjściowe oraz wyjaśnienie pierwszego przypadku wejściowego. Wyodrębnienie algorytmu na podstawie tych informacji zależy od rozwiązania problemu w jak najmniejszej liczbie bajtów kodu.

Wejście

4
1 2 5 8

wynik

15

Aby osiągnąć ten wynik, ludzie muszą przejść w następujący sposób.

A and B cross forward (2 minutes)
A returns (1 minute)
C and D cross forward (8 minutes)
B returns (2 minutes)
A and B cross forward (2 minutes)

Oto kolejny przypadek testowy, który poprowadzi Cię po drodze.

Wejście

5
3 1 6 8 12

wynik

29

Zasady:

1. Załóż, że dane wejściowe nie zostaną posortowane i musisz to zrobić samodzielnie (w razie potrzeby)
2. Liczba osób w układance nie jest ustalona na 4 (N> = 1)
3. Każda grupa i indywidualne przejście musi mieć pochodnię. Jest tylko jedna pochodnia.
4. Każda grupa musi składać się maksymalnie z 2 osób!
5. Nie, nie możesz zeskoczyć z mostu i przepłynąć na drugą stronę. Żadnych innych takich sztuczek;).

Python 3, 100 99 bajtów

rozwiązanie rekurencyjne

f=lambda s:s[0]+s[-1]+min(2*s[1],s[0]+s[-2])+f(s[:-2])if s.sort()or 3<len(s)else sum(s[len(s)==2:])

Dzięki @xnor za ten artykuł

Dzięki @lirtosiast zapisz 2 bajty, @movatica zapisz 1 bajt i @ gladed wskazując, że moje poprzednie rozwiązanie nie działa

użyj poniższej sztuczki, aby ocenić coś w funkcji lambda, s.sort() or s tutaj obliczamy sortowanie i zwracamy wynik testus.sort()or len(s)>3

Bez golfa

def f(s):
    s.sort()                                   # sort input in place
    if len(s)>3:                               # loop until len(s) < 3
        a = s[0]+s[-1]+min(2*s[1],s[0]+s[-2])  # minimum time according to xnor paper
        return  a + f(s[:-2])                  # recursion on remaining people
    else:
        return sum(s[len(s)==2:])              # add last times when len(s) < 3

Wyniki

>>> f([3, 1, 6, 8, 12])
29
>>> f([1, 2, 5, 8])
15
>>> f([5])
5
>>> f([1])
1
>>> f([1, 3, 4, 5])
14

Python 2, 119 114 112 119 110 100 95 bajtów

Poradzono mi, aby oddzielić moje odpowiedzi.

Rozwiązanie wykorzystujące Theorem 1, A2:09 ten papier xnor połączone . Aby zacytować artykuł (zmieniając go na indeksowanie zerowe):The difference between C_{k-1} and C_k is 2*t_1 - t_0 - t_{N-2k}.

lambda n,t:t.sort()or(n-3)*t[0]*(n>1)+sum(t)+sum(min(0,2*t[1]-t[0]-t[~k*2])for k in range(n/2))

Ungolfing:

def b(n, t): # using length as an argument
    t.sort()
    z = sum(t) + (n-3) * t[0] * (n>1) # just sum(t) == t[0] if len(t) == 1
    for k in range(n/2):
        z += min(0, 2*t[1] - t[0] - t[-(k+1)*2]) # ~k == -(k+1)
    return z

Ruby, 94 133 97 96 101 96 99 bajtów

Poradzono mi, aby oddzielić moje odpowiedzi.

Jest to rozwiązanie oparte na algorytmie opisanym w A6:06-10 od tego papieru na moście i pochodnia problem .

Edycja: Naprawienie błędu, który a=s[0]nie jest jeszcze zdefiniowany, kiedy ajest wywoływany na końcu ifs.size <= 3 .

->s{r=0;(a,b,*c,d,e=s;r+=a+e+[b*2,a+d].min;*s,y,z=s)while s.sort![3];r+s.reduce(:+)-~s.size%2*s[0]}

Ungolfing:

def g(s)
  r = 0
  while s.sort![3]      # while s.size > 3
    a, b, *c, d, e = s  # lots of array unpacking here
    r += a + e + [b*2, a+d].min
    *s, y, z = s        # same as s=s[:-2] in Python, but using array unpacking
  end
  # returns the correct result if s.size is in [1,2,3]
  return r + s.reduce(:+) - (s.size+1)%2 * s[0]
end

Scala, 113 135 (darnit)

def f(a:Seq[Int]):Int={val(s,b)=a.size->a.sorted;if(s<4)a.sum-(s+1)%2*b(0)else b(0)+Math.min(2*b(1),b(0)+b(s-2))+b(s-1)+f(b.take(s-2))}

Ungolfed nieco:

def f(a:Seq[Int]):Int = {
    val(s,b)=a.size->a.sorted      // Sort and size
    if (s<4) a.sum-(s+1)%2*b(0)    // Send the rest for cases 1-3
    else Math.min(b(0)+2*b(1)+b(s-1),2*b(0)+b(s-2)+b(s-1)) + // Yeah.
        f(b.take(s-2))             // Repeat w/o 2 worst
}

Próbnik:

val tests = Seq(Seq(9)->9, Seq(1,2,5,8)->15, Seq(1,3,4,5)->14, Seq(3,1,6,8,12)->29, Seq(1,5,1,1)->9, Seq(1,2,3,4,5,6)->22, Seq(1,2,3)->6, Seq(1,2,3,4,5,6,7)->28)
println("Failures: " + tests.filterNot(t=>f(t._1)==t._2).map(t=>t._1.toString + " returns " + f(t._1) + " not " + t._2).mkString(", "))

Ogólnie nie jest to świetne, ale może nie jest złe dla mocno napisanego języka. I niechętnie dziękuję xnorowi za wykrycie sprawy, której nie złapałem.

Rubin, 104 95 93 bajtów

Poradzono mi, aby oddzielić moje odpowiedzi.

To rozwiązanie oparte na moim roztwór Python 2 i Theorem 1, A2:09od tego papieru na moście i pochodnia problem .

->n,t{z=t.sort!.reduce(:+)+t[0]*(n>1?n-3:0);(n/2).times{|k|z+=[0,2*t[1]-t[0]-t[~k*2]].min};z}

Ungolfing:

def b(n, t) # using length as an argument
  z = t.sort!.reduce(:+) + t[0] * (n>1 ? n-3 : 0)
  (n/2).times do each |k|
    a = t[1]*2 - t[0] - t[-(k+1)*2] # ~k == -(k+1)
    z += [0, a].min
  end
  return z
end