fork download
copy 
  1. #! /usr/bin/python
  2. #
  3. """
  4. Problem: Please write a function in Python that takes an 8x8 grid of letters and a list of words and returns the longest word from the list (ignoring case) that can be produced from the grid using the following procedure:
  5.  
  6. 1.	Start at any position in the grid, and use the letter at that position as the first letter in the candidate word.
  7. 2.	Move to a position in the grid that would be a valid move for a knight in a game of chess, and add the letter at that position to the candidate word.
  8. 3.	Repeat step 2 any number of times.
  9.  
  10. For example, if the list of words is ["algol", "fortran", "simula"] and the grid is:
  11.  
  12.   1 2 3 4 5 6 7 8
  13. 1 Q W E R T N U I
  14. 2 O P A A D F G H
  15. 3 T K L Z X C V B
  16. 4 N M R W F R T Y
  17. 5 U I O P A S D F
  18. 6 G H J O L Z X C
  19. 7 V B N M Q W E R
  20. 8 T Y U I O P A S
  21.  
  22. ...then the longest word from the list that can be produced using the rules is “fortran”, by starting at the ‘F’ at position (5, 4), and moving to (4, 6), then (3, 4), (1, 3), back to (3, 4) and then (4, 2) and finally (6,1). Again, note that the match is case-insensitive, and that grid positions can be reused.
  23.  
  24. Create a list of words found in Shakespeare’s early comedy, Love’s Labour’s Lost (text available at http://s...content-available-to-author-only...t.edu/lll/full.html). Make sure to remove punctuation and ignore case when generating the word list. What is the output of your function using this word list on the grid below?
  25.  
  26.         H A R R Y H A T
  27.         P A T T E R N S
  28.         Q I H A C I Q T
  29.         L F U N U R X B
  30.         B W D I L A T V
  31.         O S S Y N A C K
  32.         Q W O P M T C P
  33.         K I P A C K E T
  34.  
  35.  
  36. """
  37. class Game:
  38.   def __init__(self):
  39.     self.width = 8
  40.     self.height = 8
  41.     self.Matrix = [['A' for x in range(self.width)] for y in range(self.height)]
  42.     """
  43.     creates
  44.       1 2 3 4 5 6 7 8
  45.     1 Q W E R T N U I
  46.     2 O P A A D F G H
  47.     3 T K L Z X C V B
  48.     4 N M R W F R T Y
  49.     5 U I O P A S D F
  50.     6 G H J O L Z X C
  51.     7 V B N M Q W E R
  52.     8 T Y U I O P A S
  53.     """
  54.     self.Matrix[0][0]= 'Q'
  55.     self.Matrix[0][1]= 'W'
  56.     self.Matrix[0][2]= 'E'
  57.     self.Matrix[0][3]= 'R'
  58.     self.Matrix[0][4]= 'T'
  59.     self.Matrix[0][5]= 'N'
  60.     self.Matrix[0][6]= 'U'
  61.     self.Matrix[0][7]= 'I'
  62.  
  63.     self.Matrix[1][0]= 'O'
  64.     self.Matrix[1][1]= 'P'
  65.     self.Matrix[1][2]= 'A'
  66.     self.Matrix[1][3]= 'A'
  67.     self.Matrix[1][4]= 'D'
  68.     self.Matrix[1][5]= 'F'
  69.     self.Matrix[1][6]= 'G'
  70.     self.Matrix[1][7]= 'H'
  71.  
  72.     self.Matrix[2][0]= 'T'
  73.     self.Matrix[2][1]= 'K'
  74.     self.Matrix[2][2]= 'L'
  75.     self.Matrix[2][3]= 'Z'
  76.     self.Matrix[2][4]= 'X'
  77.     self.Matrix[2][5]= 'C'
  78.     self.Matrix[2][6]= 'V'
  79.     self.Matrix[2][7]= 'B'
  80.  
  81.     self.Matrix[3][0]= 'N'
  82.     self.Matrix[3][1]= 'M'
  83.     self.Matrix[3][2]= 'R'
  84.     self.Matrix[3][3]= 'W'
  85.     self.Matrix[3][4]= 'F'
  86.     self.Matrix[3][5]= 'R'
  87.     self.Matrix[3][6]= 'T'
  88.     self.Matrix[3][7]= 'Y'
  89.  
  90.     self.Matrix[4][0]= 'U'
  91.     self.Matrix[4][1]= 'I'
  92.     self.Matrix[4][2]= 'O'
  93.     self.Matrix[4][3]= 'P'
  94.     self.Matrix[4][4]= 'A'
  95.     self.Matrix[4][5]= 'S'
  96.     self.Matrix[4][6]= 'D'
  97.     self.Matrix[4][7]= 'F'
  98.  
  99.     self.Matrix[5][0]= 'G'
  100.     self.Matrix[5][1]= 'H'
  101.     self.Matrix[5][2]= 'J'
  102.     self.Matrix[5][3]= 'O'
  103.     self.Matrix[5][4]= 'L'
  104.     self.Matrix[5][5]= 'Z'
  105.     self.Matrix[5][6]= 'X'
  106.     self.Matrix[5][7]= 'C'
  107.  
  108.     self.Matrix[6][0]= 'V'
  109.     self.Matrix[6][1]= 'B'
  110.     self.Matrix[6][2]= 'N'
  111.     self.Matrix[6][3]= 'M'
  112.     self.Matrix[6][4]= 'Q'
  113.     self.Matrix[6][5]= 'W'
  114.     self.Matrix[6][6]= 'E'
  115.     self.Matrix[6][7]= 'R'
  116.  
  117.     self.Matrix[7][0]= 'T'
  118.     self.Matrix[7][1]= 'Y'
  119.     self.Matrix[7][2]= 'U'
  120.     self.Matrix[7][3]= 'I'
  121.     self.Matrix[7][4]= 'O'
  122.     self.Matrix[7][5]= 'P'
  123.     self.Matrix[7][6]= 'A'
  124.     self.Matrix[7][7]= 'S'
  125.  
  126.   def isInMatrix(self, i,j):
  127.       return ((0<=i) and (i<self.height) and (0<=j) and (j<self.width))
  128.  
  129.   def FindX(self, X):
  130.       locations = []
  131.       for i in range(self.height):
  132.           for j in range(self.width):
  133.               if self.Matrix[i][j] == X:
  134.                  locations.append((i,j))
  135.       return locations
  136.  
  137.  
  138.   def IsWordInMatrix(self, word, i,j, pos, path):
  139.       id = [ -2, -1,  1,  2, 2, 1, -1, -2 ]
  140.       jd = [ -1, -2, -2, -1, 1, 2,  2,  1 ]
  141.       if pos + 1 == len(word):
  142.          return True
  143.       path.append((i,j))
  144.       #print('path='+repr(path)+'&X='+repr(word[pos]))
  145.       X = word[pos + 1]
  146.       for k in range(len(id)):
  147.          ni = i + id[k]
  148.          nj = j + jd[k]
  149.          location = (ni,nj)
  150.          #path.append(location)
  151.          #print('path='+repr(path)+'&X='+repr(word[pos]))
  152.          if (self.isInMatrix(ni, nj) and self.Matrix[ni][nj] == X ): #and ((ni, nj) not in path)):
  153.              if (self.IsWordInMatrix(word, ni, nj, pos + 1 , path)):
  154.                 return True
  155.          #path.remove(location)
  156.       return False
  157.  
  158.   def HasWord(self, word):
  159.       locations = self.FindX(word[0])
  160.       for tup in locations:
  161.           path = []
  162.           pos = 0
  163.           if self.IsWordInMatrix(word, tup[0], tup[1], pos, path):
  164.              return True
  165.       return False
  166.  
  167.   def test1(self):
  168.       g = Game()
  169.       #print(repr(g.Matrix))
  170.       locations = g.FindX('F')
  171.       print(repr(locations))
  172.       for tup in locations:
  173.           path = []
  174.           pos  = 0
  175.           #path.append(tup)
  176.           if g.IsWordInMatrix("FORTRAN", tup[0], tup[1], pos, path):
  177.              print(repr(path))
  178.           else:
  179.            print("NOT FOUND")
  180.           #path.remove(tup)
  181.  
  182.  
  183.   def test2(self):
  184.       g = Game()
  185.       """
  186.       0 1 2 3 4 5 6 7
  187.     0 H E N R Y H A T
  188.     1 P A T T E R N S
  189.     2 Q I H A C I Q T
  190.     3 L F U N U R X B
  191.     4 B W D I L A T V
  192.     5 O S S Y N A C K
  193.     6 Q W O P M T C P
  194.     7 K I P A C K E T
  195.       """
  196.       g.Matrix[0][0]= 'H'
  197.       g.Matrix[0][1]= 'E'
  198.       g.Matrix[0][2]= 'N'
  199.       g.Matrix[0][3]= 'R'
  200.       g.Matrix[0][4]= 'Y'
  201.       g.Matrix[0][5]= 'H'
  202.       g.Matrix[0][6]= 'A'
  203.       g.Matrix[0][7]= 'T'
  204.  
  205.       g.Matrix[1][0]= 'P'
  206.       g.Matrix[1][1]= 'A'
  207.       g.Matrix[1][2]= 'T'
  208.       g.Matrix[1][3]= 'T'
  209.       g.Matrix[1][4]= 'E'
  210.       g.Matrix[1][5]= 'R'
  211.       g.Matrix[1][6]= 'N'
  212.       g.Matrix[1][7]= 'S'
  213.  
  214.       g.Matrix[2][0]= 'Q'
  215.       g.Matrix[2][1]= 'I'
  216.       g.Matrix[2][2]= 'H'
  217.       g.Matrix[2][3]= 'A'
  218.       g.Matrix[2][4]= 'C'
  219.       g.Matrix[2][5]= 'I'
  220.       g.Matrix[2][6]= 'Q'
  221.       g.Matrix[2][7]= 'T'
  222.  
  223.       g.Matrix[3][0]= 'L'
  224.       g.Matrix[3][1]= 'F'
  225.       g.Matrix[3][2]= 'U'
  226.       g.Matrix[3][3]= 'N'
  227.       g.Matrix[3][4]= 'U'
  228.       g.Matrix[3][5]= 'R'
  229.       g.Matrix[3][6]= 'X'
  230.       g.Matrix[3][7]= 'B'
  231.  
  232.       g.Matrix[4][0]= 'B'
  233.       g.Matrix[4][1]= 'W'
  234.       g.Matrix[4][2]= 'D'
  235.       g.Matrix[4][3]= 'I'
  236.       g.Matrix[4][4]= 'L'
  237.       g.Matrix[4][5]= 'A'
  238.       g.Matrix[4][6]= 'T'
  239.       g.Matrix[4][7]= 'V'
  240.  
  241.       g.Matrix[5][0]= 'O'
  242.       g.Matrix[5][1]= 'S'
  243.       g.Matrix[5][2]= 'S'
  244.       g.Matrix[5][3]= 'Y'
  245.       g.Matrix[5][4]= 'N'
  246.       g.Matrix[5][5]= 'A'
  247.       g.Matrix[5][6]= 'C'
  248.       g.Matrix[5][7]= 'K'
  249.  
  250.       g.Matrix[6][0]= 'Q'
  251.       g.Matrix[6][1]= 'W'
  252.       g.Matrix[6][2]= 'O'
  253.       g.Matrix[6][3]= 'P'
  254.       g.Matrix[6][4]= 'M'
  255.       g.Matrix[6][5]= 'T'
  256.       g.Matrix[6][6]= 'C'
  257.       g.Matrix[6][7]= 'P'
  258.  
  259.       g.Matrix[7][0]= 'K'
  260.       g.Matrix[7][1]= 'I'
  261.       g.Matrix[7][2]= 'P'
  262.       g.Matrix[7][3]= 'A'
  263.       g.Matrix[7][4]= 'C'
  264.       g.Matrix[7][5]= 'K'
  265.       g.Matrix[7][6]= 'E'
  266.       g.Matrix[7][7]= 'T'
  267.       words = self.wordlist() #["TOO", "TIN", "POT"]
  268.       output = []
  269.       for word in words:
  270.           if g.HasWord(word):
  271.              output += [word]
  272.       return output
  273.       pass
  274.  
  275.   def extract(self, url):
  276.       import urllib
  277.       from bs4 import BeautifulSoup
  278.  
  279.       html = urllib.urlopen(url).read()
  280.       soup = BeautifulSoup(html, "html.parser")
  281.  
  282.       # kill all script and style elements
  283.       for script in soup(["script", "style"]):
  284.           script.extract()    # rip it out
  285.  
  286.       # get text
  287.       text = soup.get_text()
  288.  
  289.       # break into lines and remove leading and trailing space on each
  290.       lines = (line.strip() for line in text.splitlines())
  291.       # break multi-headlines into a line each
  292.       chunks = (phrase.strip() for line in lines for phrase in line.split("  "))
  293.       # drop blank lines
  294.       text = '\n'.join(chunk for chunk in chunks if chunk)
  295.  
  296.       return text
  297.  
  298.  
  299.   def wordlist(self):
  300.       url = 'http://s...content-available-to-author-only...t.edu/lll/full.html'
  301.       text = self.extract(url)
  302.       text = text.replace(",","")
  303.       text = text.replace("?","")
  304.       text = text.replace("!","")
  305.       text = text.replace("'","")
  306.       text = text.replace("`","")
  307.       text = text.replace(".","")
  308.       text = text.replace("-","")
  309.       text = text.replace("-","")
  310.       text = text.replace(":","")
  311.       text = text.replace("|","")
  312.       text = text.replace("[","")
  313.       text = text.replace("]","")
  314.       text = text.upper()
  315.       words = [str(x) for x in text.split()]
  316.       words = list(set(words))
  317.       return words
  318. g = Game()
  319. print(repr(g.test2()))
  320. """
  321. g = Game()
  322. locations = g.FindX('F')
  323. print(repr(locations))
  324. for tup in locations:
  325. path = []
  326. pos = 0
  327. if g.IsWordInMatrix("FORTRAN", tup[0], tup[1], pos, path):
  328. print(repr(path))
  329. else:
  330. print("NOT FOUND")
  331.  
  332. [(1, 5), (3, 4), (4, 7)]
  333. path=[(1, 5)]&X='F'
  334. NOT FOUND
  335. path=[(3, 4)]&X='F'
  336. path=[(3, 4), (4, 2)]&X='O'
  337. path=[(3, 4), (4, 2), (5, 3)]&X='O'
  338. path=[(3, 4), (4, 2), (5, 3), (3, 2)]&X='R'
  339. path=[(3, 4), (4, 2), (5, 3), (3, 2), (2, 0)]&X='T'
  340. path=[(3, 4), (4, 2), (5, 3), (3, 2), (2, 0), (3, 2)]&X='R'
  341. path=[(3, 4), (4, 2), (5, 3), (3, 2), (2, 0), (3, 2), (4, 4)]&X='A'
  342. path=[(3, 4), (4, 2), (5, 3), (3, 2), (2, 0), (3, 2), (4, 4), (1, 3)]&X='A'
  343. [(3, 4), (4, 2), (5, 3), (3, 2), (2, 0), (3, 2), (4, 4), (1, 3)]
  344. path=[(4, 7)]&X='F'
  345. NOT FOUND
  346. """
  347. """
  348. ['MAY', 'NINTH', 'MAN', 'SIN', 'NON', 'NOW', 'V', 'FARE', 'LA', 'ONT', 'A', 'HEAT', 'CLUB', 'NINE', 'SAW', 'APT', 'TRIM', 'B', 'CAME', 'WONT', 'WHERE', 'SUCH', 'BUY', 'BUT', 'NAME', 'D', 'ON', 'WHICH', 'LAUS', 'OF', 'HE', 'SUB', 'RENT', 'FAR', 'EAT', 'PAP', 'LUTE', 'ME', 'INT', 'MI', 'INS', 'ANON', 'ERE', 'WOOD', 'RARE', 'DINE', 'ANNE', 'NIT', 'IMP', 'DO', 'MIRE', 'WAS', 'DID', 'AIR', 'I', 'IS', 'IT', 'IN', 'IF', 'NAY', 'E', 'SNAKE', 'NO', 'NE', 'WHEN', 'ISBUT', 'FIRE', 'SIR', 'SIT', 'RICH', 'KNOWN', 'CAP', 'CAN', 'MAKE', 'L', 'WOO', 'ET', 'ARE', 'BA', 'OFT', 'THIN', 'SAT', 'AND', 'ANT', 'HER', 'OWN', 'FAN', 'T', 'DART', 'DARE', 'FA', 'O', 'ACT', 'EQUAL', 'TH', 'TI', 'TE', 'AD', 'AM', 'AN', 'AS', 'AT', 'AY', 'MANS', 'LAY', 'KNOW', 'LINEN', 'HIS', 'HID', 'HIM', 'HIT', 'TRUTH', 'WON', 'HERE', 'BID', 'FIFTY', 'CONTINENT', 'FIFTH', 'THINE', 'WANT', 'RE', 'ART', 'ACUTE', 'TIS', 'UT', 'US', 'U', 'CUT', 'DAN', 'DAY', 'PLAY']
  349. """
  350.  
Runtime error #stdin #stdout #stderr 0.08s 119680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Traceback (most recent call last):
  File "./prog.py", line 319, in <module>
  File "./prog.py", line 267, in test2
  File "./prog.py", line 301, in wordlist
  File "./prog.py", line 279, in extract
AttributeError: module 'urllib' has no attribute 'urlopen'
https://ideone.com/SjlLWd
language:
Python 3 (python  3.9.5)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!