Discrete Logic Discussion Board: Only needs to be around 200-300 words Start wit
ID: 3774345 • Letter: D
Question
Discrete Logic Discussion Board: Only needs to be around 200-300 words
Start with a thought experiment. Have you encountered any situation in normal day-to-day life where you needed to list the number of possible permutations of anything?
Have you ever tried to see how many words you can make out of a given word or phrase?
Do you ever do the crossword puzzle? Have you ever gotten stuck on a crossword puzzle, trying to figure out, maybe, one or two letters in an 8 or 9 letter word? If so, an effective approach (at least sometimes) is to cycle through all the permutations for the missing letters. Sometimes your mind gets stuck in a rut, and that little trick gets you going again.
Write an algorithm for how you could do something like that in software, which would include checking the English dictionary to see if 1) the resulting “word” is even a real word and 2) if the definition mentions any of the words or phrases in the clue. Do you think it would be possible to write software to complete the entire crossword puzzle from beginning to end?
Do a kind of freewheel supposition to see what kinds of obstacles you might encounter.
Have you seen the IBM computer Big Blue play Jeopardy? Do you suppose there were any issues of permutations and combinations in developing that sort of artificial intelligence software?
Do a little research to see if you find any interesting topics regarding Big Blue and Ken Jennings.
Explanation / Answer
In a normal day-to-day life, one can be in a situation as follows: If you wash your sports shoes and afterwards, you need to lace your shoes, then how many ways are there to put on the shoelace while traversing all the holes. Eg. If the number of holes is 6 (3 on each side) and we have a sufficiently large shoelace, then in how many ways can be put on the lace, assuming that the lace traverses each hole exactly once. There can be multiple answers based on the condition that we use :
Case 1: Simplest: start from any of the 6 holes and traverse by choosing any of the remaining holes, till you traverse the last one. Answer: 6*5*4*3*2*1 ways.
Case 2: There are 3 holes on each side and for a better fit, you need to choose the opposite side hole each time. Thus, 6*3*2*3*1*1 ways.
Case 3: You need to start from one of the two bottom holes and end at the other bottom hole. Thus, 2*2*2*1*1*1 ways.
Algorithm:
check_word (target_word , len): //target_word is a String with already known chars and spaces elsewhere
Check number of blank spaces in target_word, store it in count_spaces.
//If the target_word has no blank spaces
If count_spaces == len:
return target_word
word_found = False
while not word_found:
potential_target_word = generate_next_permutation(target_word, count_spaces, generation_sequence_number)
word_found = check_dictionary(potential_target_word)
return potential_target_word
check_dictionary(target_word):
dict_index = search target_word word in dictionary
if word_found:
similarity_score = match_clue_with_meaning(target_word, dict_index)
if similarity_score > threshold:
return True
else:
return False
generate_next_permutation(target_word, count_spaces, generation_sequence_number):
//function to generate the next permuation of the word using the alphabets in the language.
//Eg. using English and 3 blank spaces, there will be 26*26*26 permutations from 'aaa' to 'zzz'
It would be very tough to write a software for solving the entire crossword puzzle as of now. There would be a number of challenges pertaining to Semantics of the language. We, as humans, are able to understand the hidden meaning, analogy, metaphor given in a clue, while a computer does not. If it does not know the context in which a clue is presented, then it would miss the correct solution to the problem. Also, Prof. Seigel of Columbia Univ has pointed out that Crossword Puzzles are Constraint Satisfaction Problems with are computationally hard to solve.
IBM Big Blue / Watson definitely uses permutations and combinations but does so in an efficient way, not a brute force way which would require a lot of time and computation.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.