[Python] I searched for the longest Pokemon Shiritori

Introduction

The act of taking sumo wrestling completely with the loincloth of another person. Let's Pokemon Shiritori! --Qiita

The comment said, "I think it's tough if you don't put it into some optimization problem", so refer to the code that tried the shiritori with the station name before (or almost as it is), and the code to search for Pokemon Shiritori with the optimization problem. I wrote.

Verification environment

• Ubuntu 18.04
• Python 3.6.9
• PuLP 2.1

program

The logic is exactly the same as the articles I wrote in the past, so please have a look there. I searched for the longest station name Shiritori with Python --Qiita

There is no trick in that alone, so I moved from uselessly </ del> Python 2 to Python 3. Also, the regulation has been adjusted to match that of the first article (changed to distinguish between voiced and semi-voiced sound marks).

We will use the data introduced in the first article. (All 890 animals) https://github.com/towakey/pokedex/blob/master/pokedex.json

shiritori.py

#!/usr/bin/env python3

# modules
import sys
import itertools
import collections
import pulp
import json

#Normalized table
#Lowercase->uppercase letter
regtable = dict(zip("Ayeo", "Aiue Yayuyo"))

#Source (beginning) and sink (end)
SOURCE = "s"
SINK = "t"

##A function that finds one cycle through a specified point
##Cycles found are removed from the edges(If not found, leave it as it is)
def one_cycle(edges, start):
    path = [start]
    #Depth-first search (stack)
    #Enumerate the branches from start
    stack = [e[1] for e, cnt in edges.items() if e[0] == start and cnt > 0]
    while len(stack) > 0:
        #Choose one branch
        e_new = (path[-1], stack[-1])
        edges[e_new] -= 1
        path.append(stack[-1])
        #Finish when you return to the original point
        if stack.pop() == start:
            return path
        #List the branches starting from the current point
        dest_avail = [e[1] for e, cnt in edges.items() if e[0] == e_new[1] and cnt > 0]
        if len(dest_avail) == 0:
            #Dead end:Rewind 1 step
            edges[e_new] += 1
            path.pop()
        else:
            #List destinations
            stack += dest_avail
    #I couldn't find the cycle
    return None

##Take out the Euler cycle
def euler_cycle(edges, start):
    edges_tmp = edges.copy()
    #First look for one cycle:Depth-first search(edges_Cycles taken from tmp are removed)
    cycle = one_cycle(edges_tmp, start)
    assert cycle is not None
    cycle_add = cycle
    while len(edges_tmp) > 0:
        #Select the points on the cycle that have the remaining branches
        next_start = [v for v in set(cycle) if any(e[0] == v and cnt > 0 for e, cnt in edges_tmp.items())]
        if len(next_start) == 0:
            #Give up because there is another connecting component
            break
        else:
            #Find another cycle
            cycle_add = one_cycle(edges_tmp, next_start[0])
            assert cycle_add is not None
            #Connect to the original cycle at the selected starting point
            idx = cycle.index(next_start[0])
            cycle = cycle[:idx] + cycle_add + cycle[idx+1:]
    return cycle

#Initialize solver and set constraints
def make_solver(edges, vertexes, constraints):
    solver = pulp.LpProblem("Shiritori", pulp.LpMaximize)

    #The flow flowing to each branch corresponds to a variable
    #Integer variable
    variables = dict((e, pulp.LpVariable(e, lowBound=0, cat="Integer")) for e in edges.keys())

    #Objective function:Maximum total flow
    solver += sum(variables.values())

    #Constraints
    #1 flow from source and 1 from sink
    solver += sum([variables[e] for e in edges if e[0] == SOURCE]) == 1
    solver += sum([variables[e] for e in edges if e[1] == SINK]) == 1

    #The sum of the flow that goes out and the flow that goes in for each vertex matches(s,Other than t)
    for v in vertexes:
        solver += sum([variables[e] for e in edges if e[0] == v]) \
               == sum([variables[e] for e in edges if e[1] == v]) 

    #Flow amount limit
    for e, maxflow in edges.items():
        solver += 0 <= variables[e] <= maxflow

    #Addition of constraints on the branch-and-bound method
    #"There is one or more transitions from a point included in the cycle to another point."
    for cons in constraints:
        solver += sum(variables[e] for e in cons) >= 1

    return solver, variables

def main():
    with open("pokedex.json", "r") as f:
        pokedex = json.load(f)

    pokemons = []
    for p in pokedex:
        #Normalize reading
        yomi_norm = "".join([regtable.get(c, c) for c in p["name"]])
        if yomi_norm[-1] == "-": yomi_norm = yomi_norm[:-1]
        #At the time of Nidoran ♂, Nidoran ♀
        yomi_norm = yomi_norm.replace("♂", "male")
        yomi_norm = yomi_norm.replace("♀", "Scalpel")
        #When polygon 2
        yomi_norm = yomi_norm.replace("2", "Tsu")
        #At the time of polygon Z
        yomi_norm = yomi_norm.replace("Z", "Zet")

        pokemons.append((p["name"], yomi_norm, p["id"]))

    ##Creating a graph for shiritori
    #Branch list (and number):Directed graph
    #Also create a list for each branch (first and last character)
    edges = collections.defaultdict(int)
    edges_pokemon = collections.defaultdict(set)
    for name, yomi_norm, pokedex_id in pokemons:
        t = (yomi_norm[0], yomi_norm[-1])
        edges[t] += 1
        edges_pokemon[t].add((name, pokedex_id))

    #Add source and sink
    vertexes = set(itertools.chain(*edges.keys()))
    for v in vertexes:
        edges[(SOURCE, v)] = 1
        edges[(v, SINK)] = 1

    # *****
    #Solve with integer programming as the maximum flow problem

    length_tmp = 0
    solution_tmp = None
    constraints = []
    while True:
        solver, variables = make_solver(edges, vertexes, constraints)
        solver.solve()
        if solver.status != pulp.constants.LpStatusOptimal:
            #There is no such solution:The current solution is the final solution
            break

        #Excluding the branches that come out of s and the branches that enter t,
        #Shiritori length (number of words) (assuming no excursions)
        length_upper = int(pulp.value(solver.objective)+0.01) - 2

        # *****
        #Process the result

        #List the branches to use
        #For simplicity t->Add the path of s and keep it closed
        #edges_sub = dict(itertools.ifilter(lambda _, sol: sol > 0,
        #                                   ((e, variables[e].value()) for e in edges.keys())))
        edges_sub = dict((e, variables[e].value()) for e in edges.keys() if variables[e].value() > 0)
        edges_sub[(SINK, SOURCE)] = 1

        #Euler Find a cycle (fixed to s as you can start anywhere)
        cycle = euler_cycle(edges_sub, SOURCE)
        # cycle: s -> X1 -> ... -> Xn -> t ->With s, from X1 to Xn->The number is len(cycle)-4
        length_lower = len(cycle) - 4
        sys.stderr.write("{0}/{1} ".format(length_lower, length_upper))
        if length_lower == length_upper:
            #Connected graph
            print("Connected graph", file=sys.stderr)
            if length_tmp < length_lower:
                #Solution update
                length_tmp = length_lower
                solution_tmp = cycle
            #Confirmed by the current solution
            break
        else:
            #Not a connected graph
            #If you can't update the solution, you're done
            print("Unconnected graph", file=sys.stderr)
            if length_upper <= length_tmp:
                break
            if length_tmp < length_lower:
                #At least I found a better solution than the current one
                length_tmp = length_lower
                solution_tmp = cycle
            print("Try to find a new solution", file=sys.stderr)

            #From the next time onward, "There is one or more transitions from points included in the cycle to other points."
            #Added the condition
            vertexes_cycle = [v for v in vertexes if v in cycle]
            vertexes_outofcycle = [v for v in vertexes if v not in cycle]
            #Enumerate such transitions
            list_added_edges = [e for e in itertools.product(vertexes_cycle, vertexes_outofcycle) if e in edges]
            if len(list_added_edges) == 0:
                #If there is no such transition from the beginning, it ends
                break
            constraints.append(list_added_edges)

    # *****
    ##Convert to list

    print("Number of pokemon", length_tmp, file=sys.stderr)
    for e1, e2 in zip(solution_tmp[1:-3], solution_tmp[2:-2]):
        #Select and output one Pokemon that applies to the given first and last characters
        used = edges_pokemon[(e1, e2)].pop()
        print("{0} {1} {2:03d} {3}".format(e1, e2, used[1], used[0]))

if __name__ == "__main__":
    main()

Results (370 animals in total)

There is no one way to make the longest shiritori. The following is an example of the longest shiritori.

Swirlix 684 Swirlix
Fellow 795 Fellow
Eko 300 Skitty
Copo 875 Coo Lippo
Popo 016 Poppo
Poma 393 Piplup
Made 851 Maruyakude
Deci 719 Diancie
Shii 773 Silvadi
Eve 826 Iolb
Buki 197 Blacky
Kiwa 764 Kuwawa
Jumpluff 189 Jumpluff
Kodo 620 Kojondo
Doto 887 Drapart
Toga 365 Walrein
Guy 058 Guardy
Geodude 074 Geodude
Theo 223 Remoraid
Swellow 277 Swellow
Mema 469 Yanmega
Bellsprout 069 Bellsprout
Mitsu 150 Mewtwo
Shuckle 213 Shuckle
Bora 306 Aggron
Rata 020 Raticate
Exeggcute 102 Exeggcute
Maki 056 Mankey
Kipi 010 Caterpie
Pippi 035 Pippi
Pixie 036 Pixie
Cedar 090 shellder
Dugtrio 051 Dugtrio
Spearow 021 Spearow
Tentacool 072 Tentacool
Gega 094 Gengar
Rattle 105 Rattle
La U 026 Raichu
Victreebel 071 Victreebel
Tru 777 Togedemaru
Lula 124 Rougela
Rau 243 Raikou
Wui 059 Windy
Good 133 Eevee
Good 557 Dwebble
Onix 095 Onix
Gloom 044 Gloom
Oddish 043 Oddish
Corsola 222 Corsola
Goki 067 Gorky
Girafarig 203 Girafarig
Kiri 192 Kimawari
Lido 005 Lizard
Dodo 084 Dodo
Tentacruel 073 Tentacruel
Greninja 658 Greninja
Gala 115 Garula
Las 754 Larantes
SK 123 Strike
Pineco 204 Pineco
Mata 296 Makuhita
Seedot 273 Seedot
Boss 642 Thundurus
Skuntank 435 Skuntank
Kuto 169 Crobat
Togekiss 468 Togekiss
Sumi 121 Starmie
Mim 413 Wormadam
Mud 508 Stoutland
Dora 436 Bronzor
Las 381 Latios
Sumi 406 Budew
Michi 412 Burmy
Team 308 Medicham
Staravia 397 Staravia
Dora 532 Dokkoler
Ruth 645 Landorus
Spa 097 Sleeper
Paa 484 Palkia
Ada 617 Accelgor
Sawk 539 Sawk
Kia 318 Carvanha
Am 482 Azelf
Smoochum 238 Smoochum
Ruri 298 Ruri
Lima 217 Ringma
Mad 756 Machade
Barboach 339 Barboach
Team 421 Cherrim
Muru 396 Muckle
Ludicolo 272 Ludicolo
Seel 086 Seel
Wooper 194 Wooper
Pato 047 Parasect
Togetic 176 Togetic
Mawile 303 Mawile
Topi 175 Togepi
Pichu 172 Pichu
Snorunt 361 Snorunt
Sheila 117 Seadra
Las 380 Latias
Stunky 434 Stunky
Frillish 592 Frillish
Lugia 249 Lugia
Ad 348 Armaldo
Dochi 886 Dronchi
Chi Chi 170 Chinchou
Cheetah 152 Chikorita
Tatsu 870 Tyrate
Pikipek 731 Pikipek
Ralts 280 Ralts
Sp 096 sleep
Pla 142 Aerodactyl
Ruth 370 Luvdisc
Sua 015 Spear
Surskit 283 Surskit
Mad 802 Marshadow
Loudred 294 Loudred
Muma 200 Muma
Mad 268 Mayurd
Doo 085 Dodrio
Ota 139 Omastar
Horsea 116 Horsea
Tour 614 Beartic
Torchic 255 Torchic
Moco 877 Morpeco
Koku 054 Kodak
Kubu 098 Club
Buba 126 Buba
Bada 323 Bakuda
Daz 476 Dy Nose
Zubat 041 Zubat
Toto 118 Goldeen
Toll 011 Transel
Lula 792 Lunaara
Ruth 131 Laplace
Sua 769 Snubber
Ats 159 Alligators
Tsuya 495 Snivy
Yama 193 Yanma
Linoone 264 Linoone
Mago 219 Magcargo
Golem 076 Golem
Yama 661 Fletchling
Mashi 156 Quilava
Sheila 561 Sigilyph
Raki 113 Lucky
Kia 281 Kirlia
Seaking 119 Seaking
Uki 185 Usokki
Texture 278 Wingull
Sandile 551 Sandile
Kota 019 Rattata
Tama 862 Tachifu Saguma
Mashi 655 Delphox
Sheila 609 Chandelure
Rafflesia 045 Rafflesia
Abo 023 Abo
Boda 373 Salamence
Doug 275 Shiftry
Gligar 207 Gligar
Gauge 537 Gamageroge
Gera 657 Frogadier
Lala 608 Lampent
Rad 409 Rampardos
Doya 885 Drameshiya
Ya Ya 854 Ya Bacha
Yakude 850 Yakude
Dedenne 702 Dedenne
Necrozma 800 Necrozma
Mani 739 Mackencani
Nibi 725 Litten
Victini 494 Victini
Near 700 Sylveon
Ayu 841 Apprew
Yumi 872 Yuki Hami
Miyu 778 Mimikyu
Yuko 478 Froslass
Mienfoo 619 Mienfoo
Flabebe 669 Flabebe
Beba 859 Belover
Bani 871 Bachin Uni
Nima 431 Glameow
Inkay 686 Inkay
Turtle 833 Cam Turtle
Meta 648 Meloetta
Octopus 852 Tatakko
Coffee 580 ducklett
Hika 829 Himenka
Turtle 834 Kajirigame
Larvesta 636 Larvesta
Baya 710 Pumpkaboo
Yam 674 Pancham
Muna 890 Mugen Dyna
Nai 598 Ferrothorn
Iko 744 Ivanko
Kori 527 Woobat
Lille 605 Wrigley
Reza 384 Rayquaza
Zata 889 The Magenta
Bamboo 590 Foongus
Wurmple 265 Wurmple
Soo 791 Solgaleo
Oge 861 Oronge
Get 649 Genesect
Tra 364 Sealeo
Rat 310 Leibold
Toss 641 Tornadus
Suda 849 Stringer
Daka 554 Darumaka
Cuff 786 Kapu Tetefu
Venipede 543 Venipede
Ded 225 Deliverd
Doco 749 Dorobanco
Swoobat 528 Swoobat
Rear 470 Leafeon
Aa 823 Armor Gaa
Ag 799 Akji King
Guya 768 Gusokumusha
Yaki 512 Simisage
Kima 760 Kiteruguma
Mayo 618 Stunfisk
Yoshi 746 Yoshi
Sina 770 Shirodesuna
Throh 538 Throh
Axew 610 Axew
Goda 812 Gorilander
Daro 524 Dangoro
ROHM 479 ROTOM
Musharna 518 Musharna
Trapinch 328 Trapinch
Rat 814 Rabbi Foot
Toss 357 Tropius
Subi 843 Snake Snake
Viva 329 Vibrava
Basculin 550 Basculin
Araquanid 752 Araquanid
Mou 873 Mosnow
Udo 793 Utsuroid
Dode 748 Dohideide
Dew 181 Ampharos
Uu 845 Uu
Clauncher 692 Clauncher
Bonsly 438 Bonsly
Chiki 616 Shelmet
Kisa 286 Breloom
Saya 844 Sadaija
Sableye 302 Sableye
Patrat 504 Patrat
Mini 415 Mitsu Honey
Poliwhirl 061 Poliwhirl
Zorua 570 Zorua
Ayo 763 Amarjo
Yori 506 Lillipup
Riolu 447 Riolu
Lulu 701 Ruchable
Luo 404 Luxio
Odo 611 Onondo
Dragalge 691 Dragalge
Rod 407 Roserade
Doa 549 Lilligant
Ako 762 Amamaiko
Koshi 401 Kricketot
Shimo 751 Shizukumo
Moyu 529 Drilbur
Yuo 460 Abomasnow
Stantler 234 Stantler
Ship 682 Spritzee
Puga 564 Tirtouga
Gas 689 Barbaracle
Swanna 581 Swanna
Naro 287 Slakoth
Lower 315 Roselia
Aji 761 Amakaji
Jigo 783 Jarango
Gobe 446 Gobe
Bef 153 Bay Leaf
Drifloon 425 Drifloon
Teya 797 Tekkaguya
Yag 199 Slowking
Gua 471 Glaceon
Grubbin 736 Grubbin
Litleo 667 Litleo
Scatterbug 664 Scatterbug
Escavalier 589 Escavalier
Whismur 293 Whismur
Yoku 164 Noctowl
Kune 827 Kusune
Nera 775 Komala
Rye 309 Electrike
Ize 314 Illumise
Zebstrika 523 Zebstrika
Binacle 688 Binacle
Ted 597 Ferroseed
Gurdurr 533 Gurdurr
Tsude 805 Tunde Tunde
Deda 050 Digda
Daki 503 Samurott
Shroomish 285 Shroomish
Koshi 767 Kosokumushi
Deerling 585 Deerling
Key 083 Farfetch'd
Gimo 860 Gimo
Tangrowth 465 Tangrowth
Bole 708 Phantump
Leva 165 Ledyba
Bab 325 Spoink
Buta 136 Booster
Seed 531 Audino
Neyu 755 Nemash
Yuri 459 Snover
Lileep 345 Lileep
Radi 260 Swampert
Jiko 782 Jaraco
Photoshop 304 Cocodora
Las 579 Reuniclus
Skorupi 451 Skorupi
Piku 440 Happiny
Qui 707 Klefki
Im 221 Piloswine
Munna 517 Munna
Pear 771 Pear
Blitzle 522 Blitzle
Mau 594 Alomomola
Swinub 220 Swinub
Muji 429 Mismagius
Jibi 496 Janoby
Bima 100 Voltorb
Machi 556 Maractus
Cinccino 573 Cinccino
Dunsparce 206 Dunsparce
Petilil 548 Petilil
Neo 178 Xatu
Sentret 161 Sentret
Chico 509 Purrloin
Koku 402 Kricketune
Skrelp 690 Skrelp
Moko 180 Mokoko
Koku 403 Shinx
Swadloon 541 Swadloon
Uxie 480 Uxie
Simi 492 Shaymin
Mim 856 Mim Brim
Staraptor 398 Staraptor
Kur 488 Cresselia
Anu 730 Achilleine
Numa 759 Nuikoguma
Mime 439 Mime
Natu 177 Natu
Il 717 Yveltal
Luo 448 Lucario
Furret 162 Furret
Chibu 499 Pignite
Buta 693 Clawitzer
Tata 458 Tamanta
Tashi 363 Spheal
Crawdaunt 342 Crawdaunt
Gato 444 Gabite
Toss 411 Bastiodon
Taillow 276 Taillow
Sawsbuck 586 Sawsbuck
Key 798 Kamitsurugi
Guido 681 Gilgard
Dog 454 Toxicroak
Mightyena 262 Mightyena
Pear 103 Nassie
Shizu 134 Showers
Scraggy 559 Scraggy
Guru 210 Granbull
Run 745 Lugargan