Solving Logic Puzzles Using R-CodePudding

The

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!

CodePudding user response：

Write a function that translates nickname to name for a given allocation, e.g. realname <- function(nickname, i) ... where i is the allocation you're testing.

Write a function that translates name to height for a given allocation in that list, e.g. height <- function(name, j) ... where j is the entry in that list.

Write the 4 conditions in terms of these functions. E.g. condition 1 is

height("Oscar", j) > height(realname("Tree", i), j) && height(realname("Tree", i), j) > height("Tony", j)

Do for loops over all possible allocations i and j and run all 4 tests. If you ever find all tests coming out TRUE, you've got the solution.

Edited to add: A slightly simpler approach: just randomly permute the nicknames and the heights, and run the tests on each random selection. You'll probably run more tests than the loops (because you'll test some configurations more than once), but it shouldn't take long to cover all 14400 possibilities.

CodePudding user response：

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 Tower #> 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)}

CodePudding user response：

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