给定一个元组列表，检查是否可以构造一个元组中第二个值没有连续重复的单词

Question

假设我有一个元组列表，如下所示：

list_of_tuples = [('A', 'R'), ('B', 'R'), ('C', 'G'), ('D', 'G'), ('E', 'B'), ('D', 'B'), ('R', 'B'), ('F', 'R'), ('V', 'R'), ('A', 'G')]

每个元组中的第二个值总是R、B或G。我想创建一个函数validate，它检查是否可以使用每个元组第一个位置的字母构造某个单词，但前提是该元组的节位置的字母没有重复

例如，可以构造单词：

由于每个元组中的第二个值对应于不连续重复任何字母的RGB，因此ACE具有(A, R)、(C, G)和(E, B)

ACED与(A, R), (C, G), (E, B), and ('D', 'B')不可能，因为这将对应于RGBB，其中有一个连续的B

请注意，有时同一个字母的第二个位置可能有不同的字母，例如：

('A', 'R') and ('A', 'G')。如果选择第一个元组而不是第二个元组，则只能拼写ACE，否则G会重复

还要注意，像GBRBG这样的组合是可能的，即使第二个位置字母“重复”它们不会连续重复

因此，我想要一个函数，可以通过以下方式验证单词：

def validate(submitted_word, list_of_tuples)

一种可能性是构造此集合可能的序列的每个可能组合，以及第二个序列中的字母将产生的相应序列，过滤掉有效单词，然后过滤掉具有连续字母重复的单词，但我担心，考虑到元组列表可能会变得如此之大，这将变得效率低下

Answer 1

这是一个图遍历问题。可用节点是（字母、颜色）的元组；您的边是给定单词中的字母过渡

对于每个输入，“simply”构造该单词的图形。有了A，你就有了

Layer 1 -- transition START to any A
START -> AR
START -> AG

Layer 2 -- transition A to C
AR -> CG
not allowed: AG -> CG

Layer 3 -- transition C to E
CG -> EB

Layer 4 -- transition any E to GOAL
EB -> GOAL

现在，您只需应用图形遍历函数（任何自尊心图形包都有一个）来解决拼写问题

Answer 2

有关独立的解决方案和测试，请参见下文：

list_of_tuples = [
    ('A', 'R'),
    ('B', 'R'),
    ('C', 'G'),
    ('D', 'G'),
    ('E', 'B'),
    ('D', 'B'),
    ('R', 'B'),
    ('F', 'R'),
    ('V', 'R'),
    ('A', 'G')
]

def validate(submitted_word, list_of_tuples):
    # Check length of word
    if len(submitted_word) == 0:
        raise ValueError("len(submitted_word) must be > 0")

    # Initialise options for first character
    options = [[tup for tup in list_of_tuples if tup[0] == submitted_word[0]]]
    # Iterate through the rest of the characters
    for char in submitted_word[1:]:
        # Initialise set of characters in second position of previous tuple
        forbidden_chars = set(tup[1] for tup in options[-1])
        # Add valid options for the next character
        options.append([
            tup
            for tup in list_of_tuples
            if (tup[0] == char) and len(forbidden_chars - set(tup[1])) > 0
        ])
        # If there are no options, then submitted_word does not validate
        if len(options[-1]) == 0:
            print(options)
            return False
    
    print(options)
    return True

print(validate("ACE", list_of_tuples))
print()
print(validate("ACED", list_of_tuples))
print()
print(validate("ACFFFED", list_of_tuples))

控制台输出：

[[('A', 'R'), ('A', 'G')], [('C', 'G')], [('E', 'B')]]
True

[[('A', 'R'), ('A', 'G')], [('C', 'G')], [('E', 'B')], [('D', 'G')]]        
True

[[('A', 'R'), ('A', 'G')], [('C', 'G')], [('F', 'R')], []]
False

Answer 3

我们可以使用回溯，其中状态是每个字母使用的R、G、B的计数，以及在构造单词时选择的先前“RGB”

Python代码（未记忆）：

def f(i, word, prev, state):
  if i == len(word):
    return True

  letter = word[i]

  for second in ["R", "G", "B"]:
    if state[letter][second] and prev != second:
      state[letter][second] -= 1
      is_valid = f(i + 1, word, second, state)
      state[letter][second] += 1
      if is_valid:
        return True

  return False

def get_counts(tuples):
  result = {}
  for letter, rgb in tuples:
    if letter in result:
      result[letter][rgb] += 1
    else:
      result[letter] = {"R": 0, "G": 0, "B": 0}
      result[letter][rgb] = 1
  return result

tuples = [('A', 'R'), ('B', 'R'), ('C', 'G'), ('D', 'G'), ('E', 'B'), ('D', 'B'), ('R', 'B'), ('F', 'R'), ('V', 'R'), ('A', 'G')]

counts = get_counts(tuples)

print f(0, "ACE", "", counts) # True
print f(0, "ACED", "", counts) # True
print f(0, "BF", "", counts) # False