Detecting vicinal words

Question

Basically i need to create a python file which takes an input of a few random words and prints back the vinical words and the non-vinical words. Vinical words are words in which each letter has an adjacent letter in the word. E.G blacksmith is vicinal as every letter has at least one neighbouring letter so here is what the program needs to function like:

Line: The blacksmith fights in the tower
Vicinals: blacksmith fights
Non-vicinals: The in the tower
Line: The baker fights in the street
Vicinals: fights
Non-vicinals: The in the
Line: The butcher flees from the scene
Non-vicinals: The from the scene
Line: 

So far i have this, basically i have not put it into a loop yet but it seems that my ord comparison is not working and for some reason i get a terrible output.

line = input('Line: ').lower().split()
for item in line:
  listy = []
  nonvicinals = []
  yesvicinals = []
  vicinal = True
  for letter in item:
    listy.append(ord(letter))
  for num in listy:
    if int(num) != 97 or int(num) != 122:
      # because if it is a or z (97, 122) the number can wrap around
      if (num + 1) in listy or (num - 1) in listy:
        vicinal = True
      else:
        vicinal = False
    else:
      if int(num) == 97:
        if (num + 1) in listy or 122 in listy:
          vicinal = True
        else:
          vicinal = False
      else:
        if (num - 1) in listy or 97 in listy:
          vicinal = True
        else:
          vicinal = False
    if vicinal == False:
      nonvicinals.append(item) 
      break
  if vicinal == True:
    yesvicinals.append(item)

if yesvicinals:
  print('vicinals: {}'.format(' '.join(yesvicinals)))
if nonvicinals:
  print('Non-vicinals: {}'.format(' '.join(nonvicinals)))

Now the output i get when i put in the first example:

Line: The blacksmith fights in the tower
Non-vicinals: tower

What am i doing wrong and why am i not getting the desired output? Also my code is frankly really long and terribly ugly. is there a faster way using some lambdas/comprehensions etc?

Any help is appreciated, this has been plaguing me for hours! Thanks, Itechmatrix

Answer 1

This is a question from the current NCSS Challenge (Advanced), a programming competition. Please do not do user24492's work for him/her.

user24492/Itechmatrix, there are forums and tutors available to you for a reason. Please use those instead.

Answer 2

Disregarding character repetitions, per-word O(N) can be realized, with N being the length of the word:

LINES = ["The blacksmith fights the Gazh in the tower",
     "The almanac has a dictionary"]
ABC = [False for _ in range(0, ord('z')-ord('a')+1)]
LEN = len(ABC)


def is_vicinal(arr, abc):
    vicinal = True
    index = 0
    while vicinal and index < len(arr):
        c = arr[index]
        vicinal = vicinal and (abc[(c-1) % LEN] or abc[(c+1) % LEN])
        index += 1
    return vicinal


def is_non_vicinal(arr, abc):
    non_vicinal = True
    index = 0
    while non_vicinal and index < len(arr):
        c = arr[index]
        isolated = (not(abc[(c-1) % LEN])) and (not(abc[(c+1) % LEN]))
        non_vicinal = non_vicinal and isolated
        index += 1
    return non_vicinal


for line in LINES:
    vicinals = []
    non_vicinals = []
    neithers = []

    for word in line.split():
        arr = [ord(c.lower()) - ord('a') for c in word]
        abc = ABC[:]
        for c in arr:
            abc[c] = True

        if is_vicinal(arr, abc):
            vicinals.append(word)
        elif is_non_vicinal(arr, abc):
            non_vicinals.append(word)
        else:
            neithers.append(word)

    print(line)
    print("\tvicinal: " + str(vicinals))
    print("\tnon_vicinal: " + str(non_vicinals))
    print("\tneither: " + str(neithers))
    print('\n')

Please note, that nonvicinal is not just not(vicinal); attend http://en.wikipedia.org/wiki/Vicinal_(logology).

Output:

The blacksmith fights the Gazh in the tower
    vicinal: ['blacksmith', 'fights', 'Gazh']
    non_vicinal: ['The', 'the', 'in', 'the', 'tower']
    neither: []


The almanac has a dictionary
    vicinal: []
    non_vicinal: ['The', 'has', 'a']
    neither: ['almanac', 'dictionary']

Answer 3

This would be much easier in (at least) two functions:

def process(line):
    vicinals = []
    non_vicinals = []
    for word in line.split():
        if is_vicinal(word):
            vicinals.append(word)
        else:
            non_vicinals.append(word)
    if vicinals:
        print('vicinals: {}'.format(' '.join(vicinals)))
    if non_vicinals:
        print('Non-vicinals: {}'.format(' '.join(non_vicinals)))

def is_vicinal(word):
    raise NotImplementedError()

line = input('Line: ').lower()
process(line)

Now we can develop and test is_vicinal without worrying about any of the display or input stuff.

---

Next, note that you want to process only unique characters and don't care about the order within word (suggesting a set), and that you want to look at adjacent characters (suggesting sorting):

>>> sorted(set("blacksmith"))
['a', 'b', 'c', 'h', 'i', 'k', 'l', 'm', 's', 't']

Now we want to group those characters (I will leave this implementation to you), such that:

>>> group(['a', 'b', 'c', 'h', 'i', 'k', 'l', 'm', 's', 't'])
[['a', 'b', 'c'], ['h', 'i'], ['k', 'l', 'm'], ['s', 't']]

Now our is_vicinal function becomes easy:

>>> def is_vicinal(word)
    letters = sorted(set(word))
    return all(len(l) > 1 for l in group(letters))

>>> is_vicinal("blacksmith")
True
>>> is_vicinal("tower")
False

Now all you need to do is add in the extra logic for 'a' and 'z'! You could put this either in group or in is_vicinal - experiment and see where it fits best.

---

Note that, according to the definition in Wikipedia at least, non-vicinal isn't quite as simple as not is_vicinal, so you may need to write another functiondef is_non_vicinal(word): to deal with that. This will be very similar to the is_vicinal function, and can still use group (which is why it's good to break out separate functions).

>>> is_non_vicinal("tower")
True
>>> is_vicinal("almanac")
False
>>> is_non_vicinal("almanac")
False

This will also entail a slight modification to process.

Answer 4

Some tips:

create a function:

def is_vicinal(word):
    letters = [ord(l) for l in word]
    for letter in letters:
        if letter - 1 not in letters and letter + 1 not in letters:
            if letter == 97 and 122 in letters:
                continue
            elif letter == 122 and 97 in letters:
                continue
            else:
                return False
    return True

now you've split your vicinal logic out from the main loop. You can then test that function independently and make sure it's doing what you want.

You can then simply call it on every word.

vicinals = [w for w in line.split() if is_vicinal(w)]
non_vicinials = [w for w in line.split() if not is_vicinal(w)]

for instance.

You can combine the two, so that you only run the is_vicinal function once per word:

words_tested = [w, is_vicinal(w) for w in line.split()]

which would then give a list:

[('word',False)] ... 

Note:

My is_vicinal function above may not be totally right. But it's the right direction, I believe. :-)