CODEWITHSUNDEEP
pythonalgorithmtuples
Parseltongue
Parseltongue

Reputation: 11697

Given a list of tuples, check to see if it's possible to construct a word in which the second value in the tuple is not consecutively repeated

Let's say I have a list of tuples like so:

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

The second value in each tuple will always either be R, B, or G. I'd like to create a function validate that checks to see if a certain word can be constructed using the letters in the first position of each tuple, but only if the letters in the section position of that tuple are not repeated.

For example, it's possible to construct the word:

ACE with (A, R), (C, G) and (E, B) since the second value in each tuple corresponds to RGB which doesn't repeat any letter consecutively.

ACED with (A, R), (C, G), (E, B), and ('D', 'B') is not possible since that would correspond to RGBB in which there is a consecutive B.

Note that sometimes the same letter can have different letter in its second position, for example:

('A', 'R') and ('A', 'G'). You'd only be able to spell ACE if you selected the first tuple, not the second, otherwise the G's would repeat.

Also note that combinations like GBRBG are possible even though the second position letters "repeat" they don't repeat consecutively.

So I'd like a function that can validate words in the following way:

def validate(submitted_word, list_of_tuples)

One possibility is to construct every possible combination of sequences that are possible with this set and the corresponding sequences that would be produced with the letters in the second sequence, filter out the ones that are valid words, and then filter out the ones that have consecutive repeats of letters, but I worry that will be to inefficient given how big the list of tuples can become.

Upvotes: 1

Views: 301

Answers (4)

גלעד ברקן
גלעד ברקן

Reputation: 23945

We can use backtracking, where the state is the count of each of R, G, B used per letter, as well as the previous "RGB" chosen, as we construct the word.

Python code (not memoized):

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

Upvotes: 1

IoaTzimas
IoaTzimas

Reputation: 10624

I built the following. Firstly we create a function that compares 2 lists and checks if they have at least one different element. Secondly we run this function for the assosiated lists of all consecutive pairs of letters in the word. I considered that all letters of the word are represented in the list_of_tuples. Otherwise it will need a couple of lines more to check for existance (let me know in that case, so that i will add them).

def validate(word, list_of_tuples):
    def rgb(l1,l2):
        return len(set(l1).difference(set(l2)))>0

l=[[i, [k[1] for k in list_of_tuples if k[0]==i]] for i in word]

for i in range(len(l)-1):
    if not rgb(l[i][1], l[i+1][1]):
        return False
return True

Upvotes: 0

Jake Levi
Jake Levi

Reputation: 1742

See below for a self-contained solution and tests:

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))

Console output:

[[('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

Upvotes: 1

Prune
Prune

Reputation: 77850

This is a graph traversal problem. Your available nodes are the tuples of (letter, color); your edges are the letter transitions in the given word.

For each input, "simply" construct the graph for that word. Given ACE, you have

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

Now you simply apply the graph traversal function (any self-respecting graph package has one) to solve your spelling problem.

Upvotes: 1

Related Questions