Superhero Movies

Ponder This in June

IBM has a Ponder This blog once a month. This month, there is a Superhero Team Movie challenge. Below, is the problem verbatim from https://research.ibm.com/blog/ponder-this-june-2026

A certain comic book publisher holds the copyright for a certain superhero team, and wishes to create a movie franchise based on them. To minimize superhero fatigue with the audience, the movie franchise is planned ahead with the goal of having the minimum number of action sequences which cover all the possible superhero combinations.

Each superhero movie is built in the same manner: First, one hero appears and participates in an action sequence. Next, another hero joins them and the next action sequence contains both heroes, and so on. A movie need not contain all the heroes on the team.

As an example, assume the superhero team contains the heroes Dinolady (D), Vacuum Cleaner (V), and MathMan (M). A possible list of movies is:

The first movie provides action sequences starring D solo, and D and V together. Mathematically speaking, {D} and {D,V}.

The second movie includes the scenes {V} and {M,V}.

The third movie has the scenes {M}, {D, M} and the grand finale of {D, M, V}.

In this example, we managed to cover all the possible superhero combinations without using any such combination twice, using a total of 7 combinations. In general this is not possible. With 4 superheroes there are 15 combinations total, but we will need at least 17 combinations spread across 6 films to cover them all (since we have 6 films and 4 superheroes, we’ll have two solo action sequences starring a hero that already had a solo action sequence).

In order to write solutions compactly, we can avoid spaces and linebreaks and use “0” to signify a new movie begins. With these conventions, the above solution becomes “0DV0VM0MDV”.

Your goal: Find an optimal solution for the case of \(n=6\) heroes. Give your solution in the compacted format.

A bonus “*” will be given for finding an optimal solution for the case of \(n=10\) heroes.

Possible 6 Hero Solution

If I understand this correctly, then we’re going to need at least \({}_6C_3 = 20\) movies to cover what is needed. Although there are \(2^6 - 1 = 63\) possible combinations, we’ll need to have at least 5 repeats of just two members (since \({}_6C_2 = 15\) is five less than 20 and we need two members to build up to three members), and at least 14 repeats of the solo member intro by the same logic. So, we’ll need to use 63+19=82 combinations spread over 20 films.

To do this, I’ll use a function to build a list from the middle outward.

build_middle_out <- function(N, items = NULL) {
  # up first, some error checking on the input N
    if (!is.numeric(N) || length(N) != 1L || is.na(N) || N < 1L || N != floor(N)) {
      stop("N must be one positive integer.")
    }
    
  # let's force N to be an integer
    N <- as.integer(N)
    
  # doubtful that we'll use this for N > 24, but who knows?   
    if (is.null(items)) {
      items <- if (N <= length(LETTERS)) LETTERS[seq_len(N)] else paste0("V", seq_len(N))
    }
    
  # We can supply our own items (say c("D", "V", "M") in the N=3 case)
    if (length(items) != N || anyNA(items) || anyDuplicated(items)) {
      stop("items must contain N distinct, non-missing labels.")
    }
  
  # The middle number that we begin with in forming combinations
    m <- ceiling(N / 2)
    
  # handy function from R that creates all combinations of n things taken k at a time
    cmb <- function(k) {
      combn(items, k, simplify = FALSE)
    }
    
  # Start with the middle level.
    chains <- lapply(cmb(m), function(x) {
      z <- vector("list", N)
      z[[m]] <- x
      z
    })
    
    # Add smaller vectors: m - 1, m - 2, ..., 1.
    # These are placed top-down.
    if (m > 1L) {
      for (s in seq.int(m - 1L, 1L, by = -1L)) {
        got <- rep(FALSE, length(chains))
        
        for (x in cmb(s)) {
          for (i in seq_along(chains)) {
            if (!got[i] && all(x %in% chains[[i]][[s + 1L]])) {
              chains[[i]][[s]] <- x
              got[i] <- TRUE
              break
            }
          }
        }
        
        # Fill remaining chains using the first s entries of the next larger vector.
        for (i in seq_along(chains)) {
          if (!got[i]) {
            chains[[i]][[s]] <- chains[[i]][[s + 1L]][seq_len(s)]
          }
        }
      }
    }
    
    # Add larger vectors: m + 1, m + 2, ..., N.
    # These are placed bottom-up
    if (m < N) {
      for (s in seq.int(m + 1L, N)) {
        for (x in rev(cmb(s))) {
          placed <- FALSE
          
          for (i in rev(seq_along(chains))) {
            previous <- chains[[i]][[s - 1L]]
            
            if (
              !is.null(previous) &&
              is.null(chains[[i]][[s]]) &&
              all(previous %in% x)
            ) {
              chains[[i]][[s]] <- x
              placed <- TRUE
              break
            }
          }
          
          if (!placed) {
            stop("Could not place combination: ", paste(x, collapse = ""))
          }
        }
      }
    }
    
    # Drop the unused NULL slots.
    lapply(chains, function(z) z[!vapply(z, is.null, logical(1))])
  }

Let’s have a look at a few examples.

chains3 <- build_middle_out(3, items = c("D", "V", "M"))
chains3

## [[1]]
## [[1]][[1]]
## [1] "D"
## 
## [[1]][[2]]
## [1] "D" "V"
## 
## 
## [[2]]
## [[2]][[1]]
## [1] "M"
## 
## [[2]][[2]]
## [1] "D" "M"
## 
## 
## [[3]]
## [[3]][[1]]
## [1] "V"
## 
## [[3]][[2]]
## [1] "V" "M"
## 
## [[3]][[3]]
## [1] "D" "V" "M"

This didn’t provide the exact 7 combination order the problem stated, but it still is one optimal solution.

Now, to build the compact version of the solution, another function is defined.

# Input the list created from function above
middle_out_string <- function(chains){
  one_chain <- function(chain) {
    previous <- character(0)
    pieces <- character(length(chain) + 1L)
    pieces[1L] <- "0"
    
    for (j in seq_along(chain)) {
      new_item <- setdiff(chain[[j]], previous)
      
      if (length(new_item) != 1L) {
        stop("A vector did not add exactly one new item.")
      }
      
      pieces[j + 1L] <- new_item
      previous <- chain[[j]]
    }
    
    paste0(pieces, collapse = "")
  }
  
  paste0(vapply(chains, one_chain, character(1)), collapse = "")
}

middle_out_string(chains3)

## [1] "0DV0MD0VMD"

Now, let’s build some for \(n=6\) and \(n=10\) and check to see if they are optimal.

chains6 <- build_middle_out(6)
chains10 <- build_middle_out(10)

## These two numbers should be the same
sum(lengths(chains6))

## [1] 82

3 * choose(6,3) + sum(choose(6,4:6))

## [1] 82

## As well as these:
sum(lengths(chains10))

## [1] 1646

5 * choose(10,5) + sum(choose(10, 6:10))

## [1] 1646

Let’s have a look at the the first few and last few elements of each of these lists.

head(chains6,3)

## [[1]]
## [[1]][[1]]
## [1] "A"
## 
## [[1]][[2]]
## [1] "A" "B"
## 
## [[1]][[3]]
## [1] "A" "B" "C"
## 
## 
## [[2]]
## [[2]][[1]]
## [1] "D"
## 
## [[2]][[2]]
## [1] "A" "D"
## 
## [[2]][[3]]
## [1] "A" "B" "D"
## 
## 
## [[3]]
## [[3]][[1]]
## [1] "E"
## 
## [[3]][[2]]
## [1] "A" "E"
## 
## [[3]][[3]]
## [1] "A" "B" "E"

tail(chains6,3)

## [[1]]
## [[1]][[1]]
## [1] "C"
## 
## [[1]][[2]]
## [1] "C" "D"
## 
## [[1]][[3]]
## [1] "C" "D" "F"
## 
## [[1]][[4]]
## [1] "B" "C" "D" "F"
## 
## [[1]][[5]]
## [1] "A" "B" "C" "D" "F"
## 
## 
## [[2]]
## [[2]][[1]]
## [1] "C"
## 
## [[2]][[2]]
## [1] "C" "E"
## 
## [[2]][[3]]
## [1] "C" "E" "F"
## 
## [[2]][[4]]
## [1] "B" "C" "E" "F"
## 
## [[2]][[5]]
## [1] "A" "B" "C" "E" "F"
## 
## 
## [[3]]
## [[3]][[1]]
## [1] "D"
## 
## [[3]][[2]]
## [1] "D" "E"
## 
## [[3]][[3]]
## [1] "D" "E" "F"
## 
## [[3]][[4]]
## [1] "C" "D" "E" "F"
## 
## [[3]][[5]]
## [1] "B" "C" "D" "E" "F"
## 
## [[3]][[6]]
## [1] "A" "B" "C" "D" "E" "F"

head(chains10,3)

## [[1]]
## [[1]][[1]]
## [1] "A"
## 
## [[1]][[2]]
## [1] "A" "B"
## 
## [[1]][[3]]
## [1] "A" "B" "C"
## 
## [[1]][[4]]
## [1] "A" "B" "C" "D"
## 
## [[1]][[5]]
## [1] "A" "B" "C" "D" "E"
## 
## 
## [[2]]
## [[2]][[1]]
## [1] "F"
## 
## [[2]][[2]]
## [1] "A" "F"
## 
## [[2]][[3]]
## [1] "A" "B" "F"
## 
## [[2]][[4]]
## [1] "A" "B" "C" "F"
## 
## [[2]][[5]]
## [1] "A" "B" "C" "D" "F"
## 
## 
## [[3]]
## [[3]][[1]]
## [1] "G"
## 
## [[3]][[2]]
## [1] "A" "G"
## 
## [[3]][[3]]
## [1] "A" "B" "G"
## 
## [[3]][[4]]
## [1] "A" "B" "C" "G"
## 
## [[3]][[5]]
## [1] "A" "B" "C" "D" "G"

tail(chains10,3)

## [[1]]
## [[1]][[1]]
## [1] "E"
## 
## [[1]][[2]]
## [1] "E" "F"
## 
## [[1]][[3]]
## [1] "E" "F" "H"
## 
## [[1]][[4]]
## [1] "E" "F" "H" "I"
## 
## [[1]][[5]]
## [1] "E" "F" "H" "I" "J"
## 
## [[1]][[6]]
## [1] "D" "E" "F" "H" "I" "J"
## 
## [[1]][[7]]
## [1] "C" "D" "E" "F" "H" "I" "J"
## 
## [[1]][[8]]
## [1] "B" "C" "D" "E" "F" "H" "I" "J"
## 
## [[1]][[9]]
## [1] "A" "B" "C" "D" "E" "F" "H" "I" "J"
## 
## 
## [[2]]
## [[2]][[1]]
## [1] "E"
## 
## [[2]][[2]]
## [1] "E" "G"
## 
## [[2]][[3]]
## [1] "E" "G" "H"
## 
## [[2]][[4]]
## [1] "E" "G" "H" "I"
## 
## [[2]][[5]]
## [1] "E" "G" "H" "I" "J"
## 
## [[2]][[6]]
## [1] "D" "E" "G" "H" "I" "J"
## 
## [[2]][[7]]
## [1] "C" "D" "E" "G" "H" "I" "J"
## 
## [[2]][[8]]
## [1] "B" "C" "D" "E" "G" "H" "I" "J"
## 
## [[2]][[9]]
## [1] "A" "B" "C" "D" "E" "G" "H" "I" "J"
## 
## 
## [[3]]
## [[3]][[1]]
## [1] "F"
## 
## [[3]][[2]]
## [1] "F" "G"
## 
## [[3]][[3]]
## [1] "F" "G" "H"
## 
## [[3]][[4]]
## [1] "F" "G" "H" "I"
## 
## [[3]][[5]]
## [1] "F" "G" "H" "I" "J"
## 
## [[3]][[6]]
## [1] "E" "F" "G" "H" "I" "J"
## 
## [[3]][[7]]
## [1] "D" "E" "F" "G" "H" "I" "J"
## 
## [[3]][[8]]
## [1] "C" "D" "E" "F" "G" "H" "I" "J"
## 
## [[3]][[9]]
## [1] "B" "C" "D" "E" "F" "G" "H" "I" "J"
## 
## [[3]][[10]]
##  [1] "A" "B" "C" "D" "E" "F" "G" "H" "I" "J"

What is a compact solution to the problem?

middle_out_string(chains6)

## [1] "0ABC0DAB0EAB0FABE0CAD0CEA0CFAE0DEAC0DFAC0EFADC0BCDA0BECA0BFCA0BDEA0BDFA0BEFDA0CDEBA0CDFBA0CEFBA0DEFCBA"

middle_out_string(chains10)

## [1] "0ABCDE0FABCD0GABCD0HABCD0IABCD0JABCDI0EABCF0EGABC0EHABC0EIABC0EJABCI0FGABC0FHABC0FIABC0FJABCI0GHABC0GIABC0GJABCI0HIABCG0HJABCG0IJABCHG0DABEF0DGABE0DHABE0DIABE0DJABEI0DFABG0DFHAB0DFIAB0DFJABI0DGHAB0DGIAB0DGJABI0DHIABG0DHJABG0DIJABHG0EFABG0EFHAB0EFIAB0EFJABI0EGHAB0EGIAB0EGJABI0EHIABG0EHJABG0EIJABHG0FGHABE0FGIABE0FGJABE0FHIABE0FHJABE0FIJABHE0GHIABFE0GHJABFE0GIJABFE0HIJABGFE0CADEF0CGADE0CHADE0CIADE0CJADEI0CFADG0CFHAD0CFIAD0CFJADI0CGHAD0CGIAD0CGJADI0CHIADG0CHJADG0CIJADHG0CEAFG0CEHAF0CEIAF0CEJAFI0CEGAH0CEGIA0CEGJAI0CEHIAG0CEHJAG0CEIJAHG0CFGAHE0CFGIAE0CFGJAE0CFHIAE0CFHJAE0CFIJAHE0CGHIAFE0CGHJAFE0CGIJAFE0CHIJAGFE0DEAFGC0DEHAFC0DEIAFC0DEJAFC0DEGAHC0DEGIAC0DEGJAC0DEHIAC0DEHJAC0DEIJAHC0DFGAHC0DFGIAC0DFGJAC0DFHIAC0DFHJAC0DFIJAHC0DGHIAFC0DGHJAFC0DGIJAFC0DHIJAGFC0EFGAHDC0EFGIADC0EFGJADC0EFHIADC0EFHJADC0EFIJADC0EGHIADC0EGHJADC0EGIJADC0EHIJAGDC0FGHIAEDC0FGHJAEDC0FGIJAEDC0FHIJAEDC0GHIJAFEDC0BCDEFA0BGCDEA0BHCDEA0BICDEA0BJCDEA0BFCDGA0BFHCDA0BFICDA0BFJCDA0BGHCDA0BGICDA0BGJCDA0BHICDA0BHJCDA0BIJCDHA0BECFGA0BEHCFA0BEICFA0BEJCFA0BEGCHA0BEGICA0BEGJCA0BEHICA0BEHJCA0BEIJCHA0BFGCHA0BFGICA0BFGJCA0BFHICA0BFHJCA0BFIJCHA0BGHICFA0BGHJCFA0BGIJCFA0BHIJCGFA0BDEFGA0BDHEFA0BDIEFA0BDJEFA0BDGEHA0BDGIEA0BDGJEA0BDHIEA0BDHJEA0BDIJEHA0BDFGHA0BDFIGA0BDFJGA0BDFHIA0BDFHJA0BDFIJHA0BDGHIFA0BDGHJFA0BDGIJFA0BDHIJGFA0BEFGHDA0BEFIGDA0BEFJGDA0BEFHIDA0BEFHJDA0BEFIJDA0BEGHIDA0BEGHJDA0BEGIJDA0BEHIJGDA0BFGHIEDA0BFGHJEDA0BFGIJEDA0BFHIJEDA0BGHIJFEDA0CDEFGBA0CDHEFBA0CDIEFBA0CDJEFBA0CDGEHBA0CDGIEBA0CDGJEBA0CDHIEBA0CDHJEBA0CDIJEBA0CDFGHBA0CDFIGBA0CDFJGBA0CDFHIBA0CDFHJBA0CDFIJBA0CDGHIBA0CDGHJBA0CDGIJBA0CDHIJGBA0CEFGHBA0CEFIGBA0CEFJGBA0CEFHIBA0CEFHJBA0CEFIJBA0CEGHIBA0CEGHJBA0CEGIJBA0CEHIJGBA0CFGHIEBA0CFGHJEBA0CFGIJEBA0CFHIJEBA0CGHIJFEBA0DEFGHCBA0DEFIGCBA0DEFJGCBA0DEFHICBA0DEFHJCBA0DEFIJCBA0DEGHICBA0DEGHJCBA0DEGIJCBA0DEHIJCBA0DFGHICBA0DFGHJCBA0DFGIJCBA0DFHIJCBA0DGHIJFCBA0EFGHIDCBA0EFGHJDCBA0EFGIJDCBA0EFHIJDCBA0EGHIJDCBA0FGHIJEDCBA"