[PYTHON] A story about finding the longest shiritori of a given word group by ignoring computational complexity

Overview

When I wrote a program to solve the longest shiritori problem in Ruby without thinking too much, the amount of calculation became too large and it became useless, so I will give a memorial service. For useful programs, for example, the following article will be helpful.

-I tried to make a program that seeks the longest shiritori-Qiita

Details

Save the word group in words.txt. At this time, the character code is ** Shift JIS ** [^ 2].

words.txt

Gorilla
Apple
Panda
Rappa

[^ 2]: To avoid garbled characters.

Implementation

Step.1: Save the superfamily in an array

shiritori.rb

#Save words in an array
words = readlines(chomp: true)
p words

Execution result at the command prompt

>type words.txt | ruby shiritori.rb
["Gorilla", "Apple", "Panda", "Rappa"]

Step.2: Save the word group and the beginning / end of each word in a hash

shiritori.rb

#Save words in an array
words = readlines(chomp: true)

#Save the word group and the beginning / end of each word in a hash
words_ht = {}
words.each {|word|
    words_ht[word] = [word[0],word[word.length-1]]
}

p words_ht

Execution result at the command prompt

>type words.txt | ruby shiritori.rb
{"Gorilla"=>["Go", "Et al."], "RiんGo"=>["Ri", "Go"], "Panda"=>["Pa", "Is"], "Et al.っPa"=>["Et al.", "Pa"]}

Step.3: Find the full permutation of the superfamily and save the shiritori in a hash along with the number of words.

shiritori.rb

#Save words in an array
words = readlines(chomp: true)

#Save the word group and the beginning / end of each word in a hash
words_ht = {}
words.each {|word|
    words_ht[word] = [word[0],word[word.length-1]]
}

#Find the full permutation of the superfamily and save the shiritori in a hash along with the number of words
shiritoris = {}
words.permutation(words.length) {|perm|
    shiritori = []
    n = 0
    while (n < perm.length-1 && words_ht[perm[n]][1] == words_ht[perm[n+1]][0]) do
        n += 1
    end
    for i in 0..n do
        shiritori += [perm[i]]
    end

    shiritoris[shiritori] = shiritori.length
}

p shiritoris

Execution result at the command prompt

>type words.txt | ruby shiritori.rb
{["Gorilla"]=>1, ["Gorilla", "Rappa"]=>2, ["Gorilla", "Rappa", "Panda"]=>3, ["Apple", "Gorilla"]=>2, ["Apple", "Gorilla", "Et al.
Pappa", "Panda"]=>4, ["Apple"]=>1, ["Panda"]=>1, ["らPappa"]=>1, ["らPappa", "Panda"]=>2}

Step.4: Output the one with the largest number of words in Shiritori

shiritori.rb

#Save words in an array
words = readlines(chomp: true)

#Save the word group and the beginning / end of each word in a hash
words_ht = {}
words.each {|word|
    words_ht[word] = [word[0],word[word.length-1]]
}

#Find the full permutation of the superfamily and save the shiritori in a hash along with the number of words
shiritoris = {}
words.permutation(words.length) {|perm|
    shiritori = []
    n = 0
    while (n < perm.length-1 && words_ht[perm[n]][1] == words_ht[perm[n+1]][0]) do
        n += 1
    end
    for i in 0..n do
        shiritori += [perm[i]]
    end

    shiritoris[shiritori] = shiritori.length
}

#Outputs the largest number of words in Shiritori
p shiritoris.max { |a, b| a[1] <=> b[1] }

Execution result at the command prompt

>type words.txt | ruby shiritori.rb
[["Apple", "Gorilla", "Rappa", "Panda"], 4]

Computational complexity

Since the above program finds the full permutation of the superfamily, it calculates at least $ n! $ For every $ n $ of words. Therefore, if $ n $ is large, it is completely useless. In fact, if you calculate with 151 Pokemon in the Can Tho picture book

\log_{10}151!\fallingdotseq264.94

Therefore, the amount of calculation is $ 10 ^ {264.94} \ fallingdotseq8.7 \ times10 ^ {264} $ or more [^ 1]. [^ 1]: It's too big to come to mind, but it's a ridiculous number considering that 1 immeasurable number is 10 to the 68th power.

Bonus: Implemented in Python

If you write a program similar to the above in Python, for example: Note that Python does not use arrays as hash keys.

shiritori.py

# -*- coding: utf-8 -*-
import codecs
import itertools

#Save words in an array
wordsfile = codecs.open('words.txt', 'r', 'utf-8')
words = wordsfile.read().split()

#Save the word group and the beginning / end of each word in a hash
words_ht = {}
for word in words:
    words_ht[word] = [word[0],word[len(word)-1]]

#Find the full permutation of the superfamily and save the shiritori in an array along with the number of words
wperms = list(itertools.permutations(words, len(words)))
shiritoris = []
for wperm in wperms:
    shiritori = []
    n = 0
    while (n < len(wperm)-1 and words_ht[wperm[n]][1] == words_ht[wperm[n+1]][0]):
        n += 1
    for i in range(0, n+1):
        shiritori += [wperm[i]]

    shiritoris += [shiritori]

#Outputs the largest number of words in Shiritori
print(max(shiritoris))

words.txt

Raccoon
Cat
Fox
Little pig

Execution result at the command prompt

>python shiritori.py
['Cat', 'Little pig', 'Raccoon', 'Fox']