Descrição do Problema

Todos nós amamos um Twix (porque é o melhor doce), mas este é o primeiro Halloween das crianças - precisamos pegar pelo menos um de cada tipo de doce para eles. Todo Dia das Bruxas, todos os moradores da avenida Numberline enviam um e-mail dizendo que tipos de doces eles distribuirão este ano.

Oh! E nós vivemos em um mundo 1D.

Sendo excepcionalmente preguiçosos em alguns aspectos e não em outros, fizemos um mapa das casas dando suas posições ao longo da rua. Também observamos os tipos de doces que eles têm. Aqui está o mapa que fizemos para este ano:

 [(-2, {"Kisses", "KitKats"}),
 (1, {"KitKats", "Peanut Butter Cups"}),
 (6, {"Kisses", "Twix"}),
 (9, {"Skittles"}),
 (10, {"Twix"})]

Para o bem das perninhas das crianças, precisamos encontrar a caminhada mais curta, começando em qualquer casa do bairro, para reunir pelo menos um de cada tipo de doce.

Exemplos

A pedido de alguns usuários (incluindo Shaggy), apresentarei alguns exemplos trabalhados. Espero que isso esclareça as coisas. :) Entrada:

 [(-2, {"Kisses", "KitKats"}),
 (1, {"KitKats", "Peanut Butter Cups"}),
 (6, {"Kisses", "Twix"}),
 (9, {"Skittles"}),
 (10, {"Twix"})]

Resultado:

[1, 2, 3]

Outro mapa e solução ...

Entrada:

[(-3, {"KitKats", "Twix"}),
(-1, {"Hundred Grands"}),
(3, {"Kisses"}),
(12, {"Hundred Grands", "Twix", "KitKats"})]

Saída :

[0, 1, 2]

Poderíamos começar na casa coordenada 9, coletando doces, nas casas 6 e 1. Isso preenche a cota de doces caminhando 8 unidades, mas é a solução mais curta?

Regras

As entradas devem receber um argumento único estruturado da mesma forma que o exemplo e gerar os índices das casas a serem visitadas na solução mais curta.

Aplicam-se regras típicas de golfe com código: a solução correta mais curta em bytes vence!

PS Esta foi uma pergunta de entrevista que me foi dada por uma das maiores empresas de tecnologia do mundo. Se você não gosta de golfe, tente encontrar uma solução de tempo O (k * n) em que k é o número de tipos de doces e n é o número de casas.

Editar

Como Jonathon Allan apontou, existe alguma confusão em torno do que "índices" significa neste caso. Queremos exibir as posições das casas na lista de argumentos e não suas coordenadas na pista.

Gelatina , 16 bytes

ŒPṪ€ẎQLƲÐṀẎISƊÞḢ

Um link monádico que aceita a entrada conforme descrito em uma lista classificada das casas mais baixas para as mais altas da Numberline Avenue (se precisarmos aceitar qualquer pedido, podemos acrescentar um Ṣ) que produz o caminho mais curto começando na casa com o menor número e subindo a Avenue.

Experimente online!

Se quisermos encontrar todos os caminhos mais curtos, substitua os bytes à direita,, ÞḢcom ÐṂ; isso também é 16 bytes.

Como?

ŒPṪ€ẎQLƲÐṀẎISƊÞḢ - Link: list of [index, candies]
ŒP               - power-set
        ÐṀ       - keep those for which this is maximal:
       Ʋ         -   last four links as a monad:
  Ṫ€             -     tail €ach -- this removes the candies lists from the current list
                 -                  and yields them for use now
    Ẏ            -     tighten (to a flat list of candies offered by these hoses)
     Q           -     de-duplicate (get the distinct candies offered)
      L          -     length (how many distinct candies are on offer)
              Þ  - sort (now just the indexes of remaining sets due to Ṫ) by:
             Ɗ   -   last three links as a monad:
          Ẏ      -     tighten (to a flat list of indexes since Ṫ leaves a list behind)
           I     -     incremental differences (distances between houses)
            S    -     sum
               Ḣ - head (get the first)

Python 2 , 133 130 127 bytes

def f(l):r=range(len(l));v,c=zip(*l);print min((v[j]-v[i],r[i:j+1])for i in r for j in r if s(*c)==s(*c[i:j+1]))[1]
s={0}.union

Experimente online!

05AB1E , 22 bytes

æʒ€θ˜I€θ˜åP}€€нD€¥OWQÏ

Supõe que os números na lista de entrada sejam classificados do menor para o maior.
Se mais de uma solução for encontrada, ela produzirá todas elas.

Experimente online.

Explicação:

æ            # Get the powerset (all possible combinations) of the (implicit) input-list
 ʒ           # Filter this list of combinations by:
  €θ         #  Get the last items of each (the list of strings)
    ˜        #  Flatten the list
  I          #  Get the input-list again
   €θ˜       #  Get the last items of each (the list of strings) flattened as well
      å      #  Check for each if it is in the list of strings of this combination
       P     #  Check if all are present
 }           # Close the filter (we now have all combinations, containing all unique strings)
  €€н        # Only leave the first items of each item in the combination (the integers)
     D       # Duplicate this list
      €¥     # Get the deltas (forward differences) of each
        O    # Sum these deltas
         W   # Get the lowest sum (without popping the list)
          Q  # Check for each if it's equal to this minimum
           Ï # And only leave the list of integers at the truthy indices
             # (which are output implicitly as result)

Perl 6 , 70 bytes

{grep({.[@^i;1]⊇.[*;1]},combinations ^$_).min:{[-] .[@^i[*-1,0];0]}}

Experimente online!

Haskell , 343 372 bytes

Graças a @ ASCII-only para melhorias, há também uma variante de 271 bytes que ele propôs nos comentários :)

import Data.List
import Data.Function
f s=subsequences(map(\a@(x,y)->(x,y,[(a`elemIndices`s)!!0]))s)
g f s=if f*s<=0 then f+abs f+abs s else f+abs(f-s)
h=foldl(\(a,b,c)(d,e,f)->(g a d,nub(b++e),c++f))(0,[],[])
i s=map h(filter(not.null)s)
l m=filter(\(_,x,_)->length x==(maximum$map(\(_,x,_)->length x)m))m
m=minimumBy(compare`on`(\(p,_,_)->p))
n s=(\(_,_,l)->l)$m$l$i$f s

Experimente online!

Ungolfed

import Data.List
import Data.Function

allPaths :: [(Integer, [String])] -> [[(Integer, [String], [Int])]]
allPaths xs = subsequences(map (\a@(x,y) -> (x,y,[(a`elemIndices`s) !! 0])) s)

pathLength :: Integer -> Integer -> Integer
pathLength f s = if f*s <= 0 then f + abs f + abs s else f + abs(f - s)

traversePath :: [(Integer, [String], [Int])] -> (Integer, [String], [Int])
traversePath = foldl (\(n1, a1, c1) (n2, a2, c2) -> (pathLength n1 n2, nub (a1 ++ a2), c1 ++ c2)) (0, [], [])

allTraversedPaths :: [[(Integer, [String], [Int])]] -> [(Integer, [String], [Int])]
allTraversedPaths xs = map traversePath (filter (not . null) xs)

getCompletePaths :: [(Integer, [String], [Int])] -> [(Integer, [String], [Int])]
getCompletePaths m = filter (\(_,x,_) -> length x == ( maximum $ map (\(_,x,_) -> length x) m)) m

getFastestPath :: [(Integer, [String], [Int])] -> (Integer, [String], [Int])
getFastestPath = minimumBy (compare `on` (\(p, _, _) -> p))

getPath :: [(Integer, [String])] -> (Integer, [String], [Int])
getPath xs = (\(_,_,l) -> l) getFastestPath $ getCompletePaths $ allTraversedPaths $ allPaths xs

Primeira tentativa

Solução de tempo O (k * n), com espaço O (k * n)

Seja a posição da ésima casa (onde e são classificados) e seja a lista de doces oferecidos pela ésima casa.$x_i$$i$$0 \le i < n$$x_i$$c_i$$i$

Observe que, se temos um caminho de casa para que recebe todos os tipos de doces, em seguida, para todos , há um tal caminho de para onde .$i_1$$j_1$$i_0 < i_1$$i_0$$j_0$$i_0 \le j_0$

Assim, nosso algoritmo é:

// A[k] is the number of each candy we get from the first k houses
A := array of n bags
A[0] := {}
for k := 0 to n - 1
  A[k] := A[k - 1] + c[k - 1]
end
best_distance := ∞
best_i := -1
best_j := -1
// Find the range [i, j] such that we get all candy types
j := n
for i := n - 1 to 0
  while j > i and (A[j - 1] - A[i]) has all candy types
    j := j - 1
  end
  if (A[j] - A[i]) does not have all candy types then continue end
  distance = x[j - 1] - x[i]
  if distance < best_distance then
    best_distance = distance
    best_i = i
    best_j = j
  end
end
return best_i ..^ best_j

A construção de leva tempo para cada elemento, ou tempo (e espaço) total. O loop externo para calcular a melhor distância é executado vezes. O loop interno pode executar até vezes em uma iteração, mas o corpo é executado no máximo vezes; portanto, a condição é verificada vezes; assim, o loop interno é responsável por um tempo total de . O restante do corpo do loop externo também leva tempo . Portanto, nosso algoritmo ocupa tempo e espaço.$A$$O(k)$$O(nk)$$n$$n$$n$$O(n)$$O(nk)$$O(k)$$O(nk)$