使用 R 解决逻辑谜题

Question

使用 R 解决逻辑谜题

rlistsortingdata-manipulation

7

我遇到了以下逻辑问题：

在这个问题中，你需要将篮球运动员的真实姓名与他们的绰号匹配，并按身高对篮球运动员进行排序。通常情况下，此问题需要您手动枚举不同的姓名-绰号和姓名-身高组合，直到根据以下条件没有矛盾为止。

我想知道这些问题是否可以使用编程语言（如R）通过暴力破解来解决。

例如，下面的代码列出了每个篮球运动员按身高可能的所有组合：

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"

以下代码记录了每个名字和昵称的所有可能组合：

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"

我认为，这两个对象（“matrix_version”和“result.list”）应该包含这个逻辑谜题的正确答案 - 我只是不知道如何从这两个对象中提取正确的组合，以便符合逻辑条件。

请问有人可以向我展示如何做到这一点吗？

谢谢！

- stats_noob

我喜欢R语言，但你对这个问题是否固执于它？这个问题以及许多类似的难题都非常适合使用一阶逻辑求解器（也称谓词逻辑、谓词演算）。看看Z3求解器吧——如果你感兴趣就回复我。 - Jim

3个回答

4

这里有一个tidyverse解决方案，它可以承担重要的工作，并将最后一点留给我们。

让我们从设置开始。

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)

在第一步中，我们将条件1和条件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

在第二步中，我们查看条件2的结果，并考虑结果1：

# 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

现在我们所需要做的就是调整我们的结果1和结果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

在考虑第三个条件时，我们可以推断出最终结果：Tony不是Tiny。接下来其他的就很清晰了。当然，有一种方法能够计算出最终结果，但我所想出的方法相对于仅考虑第三个条件并手动填写tibble而言更复杂得多。

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

^{这段内容是由 reprex package（v0.3.0）于2022-01-01创建的。}

- TimTeaFan

谢谢你的回答！我现在会尝试这个！ - stats_noob

2

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.

编辑补充：一种稍微简单的方法是：只需随机排列昵称和身高，然后在每个随机选择上运行测试。你可能会运行比循环更多的测试（因为你会多次测试某些配置），但覆盖所有14400种可能性不应该花费太长时间。

- user2554330

@user2554330：谢谢你的回答！如果你有时间，能否稍后向我展示如何编写这些函数？我会非常感激！谢谢！ - stats_noob

使用 rownames(matrix_version) <- c("Slats", "Stretch", "Tiny", "Tower", "Tree")。然后 realname <- function(nickname, i) matrix_version[nickname, i] 可以得到真实姓名。 - user2554330

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ekoam · Accepted Answer

如果效率不是您的首要关注点，那么这里有一个相当简单的方法来暴力破解结果：只需生成所有可能的组合，然后过滤掉不符合条件的那些。

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
  )

< p > dt 看起来像这样

# 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

输出是

# 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