Solving Logic Puzzles Using R

Question

I came across the following logic problem:

In this problem, you are required to match the real names of basketball players to their nicknames, and sort the basketball players by their heights. Normally, this problem would require you to manually enumerate different combinations of names-nicknames and names-heights, until there are no contradictions according to the conditions below.

I was wondering if these kinds of problems can be solved by brute force using programming languages such as R.

For example, the code below lists every possible combination of basketball players by height:

my_list = c("Bill", "Ernie", "Oscar", "Sammy", "Tony")

d = permn(my_list)

all_combinations  = as.data.frame(matrix(unlist(d), ncol = 120)) |>
  setNames(paste0("col", 1:120))


data_frame_version = data.frame(matrix(unlist(d), ncol = length(d))

matrix_version = matrix(unlist(d), ncol = length(d)) 

#first 20 rows of matrix version:

     [,1]    [,2]    [,3]    [,4]    [,5]    [,6]    [,7]    [,8]    [,9]    [,10]   [,11]   [,12]   [,13]   [,14]   [,15]   [,16]   [,17]   [,18]   [,19]  
[1,] "Bill"  "Bill"  "Bill"  "Bill"  "Tony"  "Tony"  "Bill"  "Bill"  "Bill"  "Bill"  "Bill"  "Bill"  "Bill"  "Bill"  "Tony"  "Tony"  "Sammy" "Sammy" "Sammy"
[2,] "Ernie" "Ernie" "Ernie" "Tony"  "Bill"  "Bill"  "Tony"  "Ernie" "Ernie" "Ernie" "Sammy" "Sammy" "Sammy" "Tony"  "Bill"  "Sammy" "Tony"  "Bill"  "Bill" 
[3,] "Oscar" "Oscar" "Tony"  "Ernie" "Ernie" "Ernie" "Ernie" "Tony"  "Sammy" "Sammy" "Ernie" "Ernie" "Tony"  "Sammy" "Sammy" "Bill"  "Bill"  "Tony"  "Ernie"
[4,] "Sammy" "Tony"  "Oscar" "Oscar" "Oscar" "Sammy" "Sammy" "Sammy" "Tony"  "Oscar" "Oscar" "Tony"  "Ernie" "Ernie" "Ernie" "Ernie" "Ernie" "Ernie" "Tony" 
[5,] "Tony"  "Sammy" "Sammy" "Sammy" "Sammy" "Oscar" "Oscar" "Oscar" "Oscar" "Tony"  "Tony"  "Oscar" "Oscar" "Oscar" "Oscar" "Oscar" "Oscar" "Oscar" "Oscar"

And this code below records every possible combination of name-nickname:

list.a <- as.list(c("Bill", "Ernie", "Oscar", "Sammy", "Tony"))

list.b <- as.list(c("Slats", "Stretch", "Tiny", "Tower", "Tree"))

result.df <- expand.grid(list.a, list.b)
result.list <- lapply(apply(result.df, 1, identity), unlist)
result.list <- result.list[order(sapply(result.list, head, 1))]

 head(result.list)
[[1]]
   Var1    Var2 
 "Bill" "Slats" 

[[2]]
     Var1      Var2 
   "Bill" "Stretch" 

[[3]]
  Var1   Var2 
"Bill" "Tiny" 

[[4]]
   Var1    Var2 
 "Bill" "Tower" 

[[5]]
  Var1   Var2 
"Bill" "Tree" 

[[6]]
   Var1    Var2 
"Ernie" "Slats" 

The way I see it, the two objects ("matrix_version" and "result.list") should contain the right answer to this logic puzzle - I just don't know how to extract the correct combination from these two objects such that the logical conditions are respected.

Can someone please show me how to do this?

Thanks!

Answer 1

If efficiency is not your primary concern, then here is a pretty straightforward way to brute force the results: just generate all possible combinations and then filter out the ones that do not satisfy the conditions.

library(dplyr)

dt <- purrr::cross_df(list(
  name = list(c("Bill", "Ernie", "Oscar", "Sammy", "Tony")),
  nickname = combinat::permn(c("Slats", "Stretch", "Tiny", "Tower", "Tree")), 
  height = combinat::permn(c(6.6, 6.5, 6.3, 6.1, 6))
))

dt %>%  
  group_by(id = (seq_len(n()) - 1L) %/% 5L) %>% 
  filter(
    height[name == "Oscar"] > height[nickname == "Tree"], 
    height[nickname == "Tree"] > height[name == "Tony"], 
    height[name == "Bill"] > height[name == "Sammy"], 
    height[name == "Bill"] < height[nickname == "Slats"], 
    nickname[name == "Tony"] != "Tiny",
    height[nickname == "Stretch"] > height[name == "Oscar"], 
    height[nickname == "Stretch"] < 6.6
  )

dt looks like this

# A tibble: 72,000 x 3
   name  nickname height
   <chr> <chr>     <dbl>
 1 Bill  Slats       6.6
 2 Ernie Stretch     6.5
 3 Oscar Tiny        6.3
 4 Sammy Tower       6.1
 5 Tony  Tree        6  
 6 Bill  Slats       6.6
 7 Ernie Stretch     6.5
 8 Oscar Tiny        6.3
 9 Sammy Tree        6.1
10 Tony  Tower       6  
# ... with 71,990 more rows

Output is

# A tibble: 5 x 4
# Groups:   id [1]
  name  nickname height    id
  <chr> <chr>     <dbl> <int>
1 Bill  Stretch     6.5 14398
2 Ernie Slats       6.6 14398
3 Oscar Tiny        6.3 14398
4 Sammy Tree        6.1 14398
5 Tony  Tower       6   14398

Answer 2

Here is a tidyverse solution which does the heavy lifting and leaves the very last bit to us.

Lets start with the setup.

library(tidyverse)

players = c("Bill", "Ernie", "Oscar", "Sammy", "Tony")
nick_nms = c("Slats", "Stretch", "Tiny", "Tower", "Tree")
heights = c(6.6, 6.5, 6.3, 6.1, 6.0)

In the first step we combine conditions 1 and 4:

# Result 1: Based on condition 1 & 4
res1 <- cross_df(list(Oscar = heights,
              Tree = heights,
              Tony = heights,
              Stretch = heights)
         ) %>% 
  filter(Oscar > Tree,
         Tree > Tony,
         Stretch > Oscar,
         Stretch < 6.6)
res1 
#> # A tibble: 1 x 4
#>   Oscar  Tree  Tony Stretch
#>   <dbl> <dbl> <dbl>   <dbl>
#> 1   6.3   6.1     6     6.5

In the second step we look at the result of condition 2 and also take result 1 into account:

# Result 2: Based on conditon 2
res2 <- cross_df(list(Slats = heights,
                      Bill = heights,
                      Sammy = heights)) %>% 
  filter(Slats > Bill,
         Bill > Sammy,
         # after result 1 add:
         !Bill %in% c(6.3, 6),
         !Sammy %in% c(6.3, 6)) 
res2
#> # A tibble: 1 x 3
#>   Slats  Bill Sammy
#>   <dbl> <dbl> <dbl>
#> 1   6.6   6.5   6.1

Now all we need to do is to reshape our results 1 and 2:

# reshape data:
res1_long <- res1 %>%
  pivot_longer(cols = everything(),
               values_to = "height")

res2_long <- res2 %>%
  pivot_longer(cols = everything(),
               values_to = "height")

dat2 <- res1_long %>% 
  bind_rows(res2_long) %>% 
  mutate(type = ifelse(name %in% players, "player", "nick")) %>% 
  pivot_wider(names_from = type,
              values_from = name)
dat2
#> # A tibble: 5 x 3
#>   height player nick   
#>    <dbl> <chr>  <chr>  
#> 1    6.3 Oscar  <NA>   
#> 2    6.1 Sammy  Tree   
#> 3    6   Tony   <NA>   
#> 4    6.5 Bill   Stretch
#> 5    6.6 <NA>   Slats

At this point we can infer the final result by keeping condition 3 in mind: Tony is not Tiny. Then the rest falls into place. Of course it would be nice to have an approach which calculates the final result. But anything I've come up with was so much more complicated compared to just taking condition 3 into account and fill the tibble manually:

dat2 %>% 
  # Fill in the last 
  mutate(player = ifelse(is.na(player),
                         "Ernie",
                         player),
         
         nick = case_when(is.na(nick) & player == "Oscar" ~ "Tiny",
                          is.na(nick) ~ "Tower",
                          TRUE ~ nick)
         )
#> # A tibble: 5 x 3
#>   height player nick   
#>    <dbl> <chr>  <chr>  
#> 1    6.3 Oscar  Tiny  
#> 2    6.1 Sammy  Tree   
#> 3    6   Tony   Tower  
#> 4    6.5 Bill   Stretch
#> 5    6.6 Ernie  Slats

^{Created on 2022-01-01 by the reprex package (v0.3.0)}