# 224 Puzzle from the New Scientist

Jul 10, 2023 7 min read puzzle

created by DALL·E

Puzzle #224 from the New Scientist is:

I collect Russian dolls, the type where each doll can be opened to reveal a smaller one inside. I am particularly fond of my simple, single-coloured ones, which come in sets of five (and, unusually, have a hollow smallest doll). I have five lovely sets of them, each a different colour.

Alas, while I was out, my daughter Kira rearranged them so that each large doll now contains one each of the four other colours. She proudly tells me that no blue doll contains a doll that has a yellow doll anywhere within it. There is no doll that contains a pink doll with a red doll anywhere within it. And no yellow doll contains a green doll with a pink doll anywhere within it.

“By the way, have you seen my wedding ring?” I ask her.

“Ah, I put that inside the smallest blue doll” replies Kira.

Which coloured doll should l open first if I want to find the ring as quickly as possible?

Solution

The figure shows all the possible arrangements of the five dolls. The letter indicates the colour: R for red, Y for yellow and so on. The index indicates the doll size: 5 for the smallest and 1 for the largest.

As an example, the top path - P1 R2 G3 Y4 B5- corresponds to the combination pink, red, green, yellow and blue (from the largest to the smallest doll).

Further, B5 occupies the left hand size since we know the smallest doll is blue.

With the a few lines of code I recreate the figure. Each row of the output corresponds to a set of five dolls. For example, the last row corresponds to the combination yellow, red, pink, green and blue. In total, we have 24 possible arrangements - same as in the figure.

# pkgs used in this post
library(gtools)
library(stringi)
library(stringr)
library(rebus) 
library(purrr)

colour <- c("blue", "yellow", "pink", "red", "green") # all the different colours

numb <- 1:5 # the size index (1 is the largest)

opt <- paste0(rep(colour, each = 5), "_", numb) # combine colour and index

perms <- permutations(n = 25, r = 5, v = opt, repeats.allowed = F) # all the combinations of 5 dolls

# define function to use 
my_fun <- function(x, data, pattern = NULL){
   # x: the row index of `data`
   # data: the input dataset
   # pattern: the pattern to search for in each row of `data`
   
   if(is.null(pattern)){
      perms3 <- stri_split_fixed(data[x,], "_", simplify = T) # split the vectors into two
      dupl <- sum(stri_duplicated(perms3[,1])) # check for uniqueness
      sorted <- is.unsorted(perms3[,2], strictly = T) # check for correct order
   
      if(dupl == 0 & sorted == 0){ # if no duplicated and correct order data is returned
         out <- data[x,]
         } else {
            out <- c()
            }
      } else {
         splitted <- stri_split_fixed(data[x,], "_", simplify = T) # split the vectors into two
         ind <- str_detect(paste(splitted[,1], collapse = ""), pattern = pattern, negate = T) # find patterns
      
         if(ind == 1){ # if pattern is found it's returned
            out <- data[x,]
            }else{
               out <- c()
            }
      }
   
   return(out)
}

##### add restrictions
# 1: select only the ones where blue is the smallest doll
blue_smallest_doll <- which(perms[,5] == "blue_5") # blue is the smallest doll

perms2 <- perms[blue_smallest_doll,]

# 2: select only the combinations where each colour appears once and indexes are sorted correctly 
combinations <- matrix( # simplify final result into a matrix 
   unlist( # simplify output of map()
      map(1:nrow(perms2), my_fun, data = perms2)), # apply my_fun to all rows of perms2
   ncol = 5, byrow = TRUE) 

combinations

##       [,1]       [,2]       [,3]       [,4]       [,5]    
##  [1,] "green_1"  "pink_2"   "red_3"    "yellow_4" "blue_5"
##  [2,] "green_1"  "pink_2"   "yellow_3" "red_4"    "blue_5"
##  [3,] "green_1"  "red_2"    "pink_3"   "yellow_4" "blue_5"
##  [4,] "green_1"  "red_2"    "yellow_3" "pink_4"   "blue_5"
##  [5,] "green_1"  "yellow_2" "pink_3"   "red_4"    "blue_5"
##  [6,] "green_1"  "yellow_2" "red_3"    "pink_4"   "blue_5"
##  [7,] "pink_1"   "green_2"  "red_3"    "yellow_4" "blue_5"
##  [8,] "pink_1"   "green_2"  "yellow_3" "red_4"    "blue_5"
##  [9,] "pink_1"   "red_2"    "green_3"  "yellow_4" "blue_5"
## [10,] "pink_1"   "red_2"    "yellow_3" "green_4"  "blue_5"
## [11,] "pink_1"   "yellow_2" "green_3"  "red_4"    "blue_5"
## [12,] "pink_1"   "yellow_2" "red_3"    "green_4"  "blue_5"
## [13,] "red_1"    "green_2"  "pink_3"   "yellow_4" "blue_5"
## [14,] "red_1"    "green_2"  "yellow_3" "pink_4"   "blue_5"
## [15,] "red_1"    "pink_2"   "green_3"  "yellow_4" "blue_5"
## [16,] "red_1"    "pink_2"   "yellow_3" "green_4"  "blue_5"
## [17,] "red_1"    "yellow_2" "green_3"  "pink_4"   "blue_5"
## [18,] "red_1"    "yellow_2" "pink_3"   "green_4"  "blue_5"
## [19,] "yellow_1" "green_2"  "pink_3"   "red_4"    "blue_5"
## [20,] "yellow_1" "green_2"  "red_3"    "pink_4"   "blue_5"
## [21,] "yellow_1" "pink_2"   "green_3"  "red_4"    "blue_5"
## [22,] "yellow_1" "pink_2"   "red_3"    "green_4"  "blue_5"
## [23,] "yellow_1" "red_2"    "green_3"  "pink_4"   "blue_5"
## [24,] "yellow_1" "red_2"    "pink_3"   "green_4"  "blue_5"

Then, we need to take into account the two additional restrictions:

“no doll that contains a pink doll with a red doll anywhere within it”, and
“no yellow doll contains a green doll with a pink doll anywhere within it”.

The first one is easy. We need to discard all solutions where pink is followed by red. This gives us 12 remaining solutions.

# 224 Puzzle from the New Scientist

Solution

1st interpretation

2nd interpretation

3rd interpretation

Solon Karapanagiotis

Research Associate
MRC Biostatistics Unit

Related

# 224 Puzzle from the New Scientist

Solution

1st interpretation

2nd interpretation

3rd interpretation

Solon Karapanagiotis

Research AssociateMRC Biostatistics Unit

Related

Research Associate
MRC Biostatistics Unit