It's Halloween again!

Question

Problem Description

We all love a Twix (because it is the best candy), but this is the kids' first Halloween --- we gotta grab at least one of each type of candy for them. Each Halloween all the residents of Numberline avenue send out an email saying what types of candy they'll be giving away this year.

Oh! And we live in a 1D world.

Being exceptionally lazy in some ways and not in others, we've made a map of the houses giving their positions along the street. We also noted the types of candy they have. Here's the map we made for this year:

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

For the sake of the kids' little legs, we need to find the shortest walk starting at any house in the neighborhood to gather at least one of each type of candy.

Examples

At the request of a couple users (including Shaggy), I'll toss in some worked examples. Hopefully this clears things up. :) Input:

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

Output:

[1, 2, 3]

Another map and solution...

Input:

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

Output:

[0, 1, 2]

We could begin at the coordinate 9 house collecting candies to at houses 6 and 1. That fills the candy quota by walking 8 units, but is it the shortest solution?

Rules

Entries must take in a similarly structured single argument to the example and output the indices of the houses to visit in the shortest solution.

Typical code golf rules apply: shortest correct solution in bytes wins!

P.S. This was an interview question given to me by one of the world's largest tech companies. If you don't like golf, try finding an O(k*n) time solution where k is the number of candy types and n is the number of houses.

Edit

As Jonathon Allan pointed out, some confusion exists around what "indices" means in this case. We want to output the houses positions in the argument list and not their coordinates on the lane.

Answer 1

Jelly, 16 bytes

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

A monadic Link accepting the input as described in a list sorted from lowest to highest Numberline Avenue houses (if we need to accept any ordering we can prepend an Ṣ) which yields the shortest path starting at the lowest numbered house and travelling up the Avenue.

Try it online!

If we want to find all such shortest paths replace the trailing bytes, ÞḢ, with ÐṂ; this is also 16 bytes.

How?

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

Answer 2

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

Try it online!

Answer 3

05AB1E, 22 bytes

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

Assumes the numbers in the input-list are sorted lowest to highest.
If more than one solution is found, it will output all of them.

Try it online.

Explanation:

æ            # 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)

Answer 4

Perl 6, 70 bytes

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

Try it online!

Answer 5

Haskell, 343 372 bytes

Thanks to @ASCII-only for improvements, there's also a 271 bytes variant he proposed in the comments :)

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

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

---

First attempt

Answer 6

O(k*n) time solution, with O(k*n) space

Let \$x_i\$ be the position of the \$i\$th house (where \$0 \le i < n\$, and \$x_i\$ are sorted) and \$c_i\$ be the list of candies offered by the \$i\$th house.

Observe that if we have a path from house \$i_1\$ to \$j_1\$ that gets all candy types, then for all \$i_0 < i_1\$, there is such a path from \$i_0\$ to \$j_0\$ where \$i_0 \le j_0\$.

Thus, our algorithm is:

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

The construction of \$A\$ takes \$O(k)\$ time for each element, or \$O(nk)\$ time (and space) total. The outer loop for computing the best distance executes \$n\$ times. The inner loop can execute up to \$n\$ times in one iteration, but the body is executed at most \$n\$ times, so the condition is checked \$O(n)\$ times; thus, the inner loop accounts for a total of \$O(nk)\$ time. The rest of the outer loop body takes \$O(k)\$ time as well. Hence, our algorithm takes \$O(nk)\$ time and space.