Вдохновение для этого кода гольф головоломки является проблема моста и факел , в котором г люди в начале моста все должны пересечь его в наименьшее количество времени.

Загвоздка в том, что максимум два человека могут пересекать одновременно, иначе мост сломается под их весом, и у группы будет доступ только к одному факелу, который нужно нести, чтобы пересечь мост.

У каждого человека во всей загадке есть определенное время, которое ему требуется, чтобы пройти через мост. Если два человека пересекаются вместе, пара идет так же медленно, как самый медленный человек.

Нет определенного количества людей, которые должны пересечь мост; Ваше решение ДОЛЖНО работать для любого значения d .

Вам не нужно использовать стандартный ввод для этой проблемы, но для объяснения проблемы я буду использовать следующий формат ввода и вывода для объяснения. Первое число, d , это количество людей в начале моста. Затем код отсканирует d чисел, каждое из которых представляет скорость человека.

Выводом кода будет наименьшее количество времени, необходимое для прохождения всех от начала моста до конца моста при соблюдении критериев, описанных ранее.

Вот некоторые входные случаи и выходные случаи и объяснение для первого входного случая. Это зависит от вас, чтобы извлечь алгоритм из этой информации, чтобы решить проблему с наименьшим количеством байтов кода.

вход

4
1 2 5 8

выход

15

Чтобы достичь этого результата, люди должны перейти следующим образом.

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)

Вот еще один тестовый пример, который поможет вам на вашем пути.

вход

5
3 1 6 8 12

выход

29

Правила:

1. Предположим, что входные данные не будут отсортированы, и вы должны сделать это самостоятельно (если вам нужно)
2. Количество людей в головоломке не установлено на 4 (N> = 1)
3. Каждая группа и индивидуальный переход должны иметь факел. Есть только один факел.
4. Каждая группа должна состоять максимум из 2 человек!
5. Нет, вы не можете спрыгнуть с моста и переплыть на другую сторону. Никаких других трюков, как это;).

Python 3, 100 99 байт

рекурсивное решение

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

Спасибо @xnor за эту статью

Благодаря @lirtosiast экономит 2 байта, @movatica сохраняет 1 байт и @gladed указывает на то, что мое предыдущее решение не работает

используйте следующий трюк для оценки чего-либо в лямбда-функции s.sort() or s здесь мы вычисляем sort и возвращаем результат тестаs.sort()or len(s)>3

Ungolfed

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

Результаты

>>> 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 байтов

Мне посоветовали разделить мои ответы.

Решение с использованием Theorem 1, A2:09 этой статьи XNOR связано . Чтобы процитировать статью (изменив ее на нулевую индексацию):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

Рубин, 94 133 97 96 101 96 99 байт

Мне посоветовали разделить мои ответы.

Это решение на основе алгоритма , описанного в A6:06-10из этой бумаги на мосту и факелом проблемы .

Редактировать: Исправление ошибки, когда a=s[0]еще не определено, когда aвызывается в конце, если s.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

Скала, 113 135 (дарнит)

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

В некотором роде

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
}

Tester:

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(", "))

Не очень хорошо, но, возможно, неплохо для строго типизированного языка. И благодарю xnor за то, что я обнаружил случай, который я не понял.

Руби, 104 95 93 байта

Мне посоветовали разделить мои ответы.

Это решение , основанное на моем решение Python 2 и Theorem 1, A2:09из этой бумаги на мосте и факел проблеме .

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