L'acte de lutter complètement avec le pied de quelqu'un d'autre. Allons Pokemon Shiritori! --Qiita
Le commentaire disait: "Je pense que c'est difficile si vous ne le mettez pas dans une sorte de problème d'optimisation." Donc, en référence au code que j'ai essayé de presser avec le nom de la station avant (ou presque tel quel), le code pour rechercher Pokemon squeeze avec le problème d'optimisation. J'ai écrit.
La logique est exactement la même que celle des articles que j'ai écrits dans le passé, alors jetez-y un œil. J'ai recherché le nom de station le plus long en Python - Qiita
Il n'y a pas d'astuce là-dedans, alors je suis passé de inutilement </ del> Python 2 à Python 3.
En outre, la réglementation a été ajustée pour correspondre à celle du premier article (modifiée pour faire la distinction entre les points troubles et semi-troubles).
J'utiliserai les données présentées dans le premier article. (Tous les 890 animaux) 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
#Tableau normalisé
#Minuscule->lettre majuscule
regtable = dict(zip("Ayeo", "Aiueoya Yuyo"))
#Source (début) et puits (fin)
SOURCE = "s"
SINK = "t"
##Une fonction qui trouve un chemin fermé passant par un point spécifié
##Les routes fermées trouvées sont supprimées des bords(Si non trouvé, laissez-le tel quel)
def one_cycle(edges, start):
path = [start]
#Recherche de priorité de profondeur (pile)
#Énumérer les branches depuis le début
stack = [e[1] for e, cnt in edges.items() if e[0] == start and cnt > 0]
while len(stack) > 0:
#Choisissez une succursale
e_new = (path[-1], stack[-1])
edges[e_new] -= 1
path.append(stack[-1])
#Terminez lorsque vous revenez au point d'origine
if stack.pop() == start:
return path
#Lister les branches à partir du point courant
dest_avail = [e[1] for e, cnt in edges.items() if e[0] == e_new[1] and cnt > 0]
if len(dest_avail) == 0:
#Impasse:Rewind 1 étape
edges[e_new] += 1
path.pop()
else:
#Liste des destinations
stack += dest_avail
#Je n'ai pas trouvé de route fermée
return None
##Sortez de la route fermée d'Euler
def euler_cycle(edges, start):
edges_tmp = edges.copy()
#Tout d'abord, trouvez une route fermée:Recherche de priorité de profondeur(edges_Le chemin fermé emprunté à tmp est supprimé)
cycle = one_cycle(edges_tmp, start)
assert cycle is not None
cycle_add = cycle
while len(edges_tmp) > 0:
#Sélectionnez les points sur la route fermée qui ont les branches restantes
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:
#Abandonnez car il y a un autre composant de liaison
break
else:
#Trouver une autre route fermée
cycle_add = one_cycle(edges_tmp, next_start[0])
assert cycle_add is not None
#Connectez-vous avec la fermeture d'origine au point de départ sélectionné
idx = cycle.index(next_start[0])
cycle = cycle[:idx] + cycle_add + cycle[idx+1:]
return cycle
#Initialiser le solveur et définir les contraintes
def make_solver(edges, vertexes, constraints):
solver = pulp.LpProblem("Shiritori", pulp.LpMaximize)
#Le débit circulant vers chaque branche correspond à une variable
#Variable entière
variables = dict((e, pulp.LpVariable(e, lowBound=0, cat="Integer")) for e in edges.keys())
#Fonction objective:Débit total maximum
solver += sum(variables.values())
#Contraintes
#1 flux de la source et 1 de l'évier
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
#La somme du flux qui sort et du flux qui entre pour chaque sommet correspond(s,Autre que 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])
#Limite de débit
for e, maxflow in edges.items():
solver += 0 <= variables[e] <= maxflow
#Ajout de contraintes sur la méthode de limitation de branche
#"Il y a une ou plusieurs transitions d'un point inclus dans le cycle à un autre 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:
#Normaliser la lecture
yomi_norm = "".join([regtable.get(c, c) for c in p["name"]])
if yomi_norm[-1] == "-": yomi_norm = yomi_norm[:-1]
#Au temps de Nidoran ♂, Nidoran ♀
yomi_norm = yomi_norm.replace("♂", "Masculin")
yomi_norm = yomi_norm.replace("♀", "Femme")
#Lorsque le polygone 2
yomi_norm = yomi_norm.replace("2", "Tsu")
#Au moment du polygone Z
yomi_norm = yomi_norm.replace("Z", "Zet")
pokemons.append((p["name"], yomi_norm, p["id"]))
##Créer un graphique pour le rasage
#Liste des succursales (et numéro):Graphique dirigé
#Créez également une liste pour chaque branche (premier et dernier caractères)
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))
#Ajouter une source et synchroniser
vertexes = set(itertools.chain(*edges.keys()))
for v in vertexes:
edges[(SOURCE, v)] = 1
edges[(v, SINK)] = 1
# *****
#Résoudre avec la programmation entière comme problème de débit maximal
length_tmp = 0
solution_tmp = None
constraints = []
while True:
solver, variables = make_solver(edges, vertexes, constraints)
solver.solve()
if solver.status != pulp.constants.LpStatusOptimal:
#Il n'y a pas de telle solution:La solution actuelle est la solution finale
break
#En excluant la branche qui sort de s et la branche qui va dans t,
#Durée de la pression (en supposant qu'il n'y ait pas de sauts) (nombre de mots)
length_upper = int(pulp.value(solver.objective)+0.01) - 2
# *****
#Traiter le résultat
#Lister les branches à utiliser
#Pour la simplicité t->Ajoutez le chemin de s et gardez-le fermé
#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
#Trouver Euler fermé (fixé à s car vous pouvez commencer n'importe où)
cycle = euler_cycle(edges_sub, SOURCE)
# cycle: s -> X1 -> ... -> Xn -> t ->Avec s, de X1 à Xn->Le nombre est len(cycle)-4
length_lower = len(cycle) - 4
sys.stderr.write("{0}/{1} ".format(length_lower, length_upper))
if length_lower == length_upper:
#Graphique concaténé
print("Graphique concaténé", file=sys.stderr)
if length_tmp < length_lower:
#Mise à jour de la solution
length_tmp = length_lower
solution_tmp = cycle
#Confirmé par la solution actuelle
break
else:
#Pas un graphe concaténé
#Si vous ne pouvez pas mettre à jour la solution, vous avez terminé
print("Graphique non connecté", file=sys.stderr)
if length_upper <= length_tmp:
break
if length_tmp < length_lower:
#Au moins j'ai trouvé une meilleure solution que l'actuelle
length_tmp = length_lower
solution_tmp = cycle
print("Essayez de trouver une nouvelle solution", file=sys.stderr)
#À partir de la prochaine fois, «il y a une ou plusieurs transitions entre les points inclus dans le cycle et d'autres points».
#Ajout de la condition
vertexes_cycle = [v for v in vertexes if v in cycle]
vertexes_outofcycle = [v for v in vertexes if v not in cycle]
#Énumérer ces transitions
list_added_edges = [e for e in itertools.product(vertexes_cycle, vertexes_outofcycle) if e in edges]
if len(list_added_edges) == 0:
#S'il n'y a pas une telle transition depuis le début, elle se termine
break
constraints.append(list_added_edges)
# *****
##Convertir en liste
print("Nombre de Pokémon", length_tmp, file=sys.stderr)
for e1, e2 in zip(solution_tmp[1:-3], solution_tmp[2:-2]):
#Sélectionnez et sortez un Pokémon qui s'applique aux premier et dernier caractères donnés
used = edges_pokemon[(e1, e2)].pop()
print("{0} {1} {2:03d} {3}".format(e1, e2, used[1], used[0]))
if __name__ == "__main__":
main()
Il n'y a pas toujours une façon de faire le plus long shitori. Voici un exemple de la pression la plus longue.
Pef 684 Pelo Puff
Hué 795 Feroche
Eco 300 Eneko
Copo 875 Coo Lippo
Popo 016 Poppo
Poma 393 Poccama
Fabriqué 851 Maruyakude
Déci 719 Diancy
Shii 773 Silvadi
Eve 826 Iolb
Buki 197 Blacky
Kiwa 764 Kuwawa
Wako 189 Watakko
Kodo 620 Kojondo
Doto 887 Drapart
Toga 365 Todozerga
Guy 058 Guardy
Ite 074 Ishitsubute
Theo 223 Teppo
Ome 277 Oosbame
Mema 469 Mega Yamma
Mami 069 Madatsubomi
Mitsu 150 Miu Deux
Acupoint 213 Acupoint
Bora 306 Boss Godra
Rata 020 Rata
Tama 102 Tamatama
Maki 056 Mankey
Kipi 010 Caterpy
Phi Phi 035 Phi Phi
Pisi 036 Pixie
Abri Ferida 090
Dao 051 Doug Trio
Ome 021 Onisuzume
Méduse Mege 072 Meno
Gega 094 Genger
Hochet 105 Hochet
Raw 026 Light Chu
Uto 071 Utsubot
Tru 777 Togedemaru
Lula 124 Rougela
Raiko brut 243
Wui 059 Windy
Bon 133 Eve
Bon 557 Ishizumai
Iku 095 Iku
Kuna 044 Kusa Hana
Nasa 043 Nazonokusa
Sago 222 Sunnygo
Goki 067 Gorky
Kiki 203 Kirin Riki
Kiri 192 Kimawari
Lézard Lido 005
Dodo 084 Dodo
Méduse Doge 073 Dok
Gega 658 Geckouga
Gala 115 Garula
Las 754 Larantes
SK 123 Strike
Kuma 204 Kunugi Dama
Mata 296 McNosita
Tabo 273 Tanebo
Boss 642 Perte de boulon
Débardeur Suku 435 Suka
Kuto 169 Crobat
Lancer 468 Togekiss
Sumi 121 Star Moi
Mim 413 Minomadam
Boue 508 Moland
Miroir Dora 436 Dora
Las 381 Latios
Sumi 406 Subomy
Michi 412 Minomucci
Chim 308 Charlem
Mudo 397 Mukubird
Dora 532 Dokkoler
Ruth 645 Landros
Spa 097 Sleeper
Parkia Paa 484
Ada 617 Aguilder
Daki 539 Dageki
Kia 318 Kivania
Suis 482 Agnom
Muru 238 Mouture
Ruri 298 Ruri
Lima 217 Ringma
Mad 756 Machade
Dochi 339 Dojotchi
Chim 421 Cherim
Muru 396 Muckle
Lupa 272 Runpapa
Pow 086 Pow Wow
Upa 194 Upa
Pato 047 Parasect
Toku 176 Togetic
Kuto 303 Kuchito
Topi 175 Togepy
Piyu 172 Pichu
Yushi 361 Yukiwarashi
Shira 117 Seedra
Ruth 380 Latias
Sp 434 Skampoo
Puru 592 Pururiru
Lua 249 Lugia
Annonce 348 Armald
Dochi 886 Dronchi
Chi Chi 170 Jeong Chi
Chita 152 Chicorita
Tatsu 870 Tyrate
Tsutsukera 731 Tsutsukera
Ruth 280 Lars
Sp 096 Sommeil
Pra 142 Ptera
Ruth 370 Love Cass
Lance Sua 015
Ama 283 Ametama
Mad 802 Marshadow
Dom 294 Dogome
Muma 200 Muuma
Mad 268 Mayurd
Doo 085 Dodrio
Ota 139 Omster
Tatsu 116 Tatsu
Tour 614 Ours de Thoune
Amo 255 Achamo
Moco 877 Morpeco
Koku 054 Kodak
Club Kubu 098
Buba 126 Buba
Bada 323 Bakuda
Nez Daz 476 Dy
Zuto 041 Zubat
Toto 118 Tosakinto
Péage 011 Transel
Lula 792 Lunaara
Ruth 131 Laplace
Amortisseur Sua 769
Atsushi 159 Alligators
Tsuya 495 Tsutaja
Yama 193 Yan Yanma
Mama 264 ours de masse
Mago 219 Magcalgo
Goya 076 Goronha
Yama 661 Yayakoma
Mashi 156 Magmarashi
Shira 561 Symboler
Raki 113 chanceux
Kia 281 Kirlia
Aw 119 Azumaou
Uki 185 Usokki
Texture 278 Camome
Meco 551 Megroco
Kota 019 Collata
Tama 862 Tachifu Saguma
Mashi 655 Mafoxy
Lustre Shira 609
Laa 045 Rafflesia
Abo 023 Abo
Boda 373 Bowmanda
Doug 275 Darting
Guga 207 Griger
Jauge 537 Gamageroge
Gera 657 Gekogashira
Lara 608 Lampler
Rad 409 Rampard
Doya 885 Drameshiya
Yaya 854 Yabacha
Yade 850 Yakude
Dene 702 Dedenne
Nema 800 Necrozuma
Mani 739 Mackencani
Nibi 725 Nyaby
Bini 494 Victorini
Près de 700 Nymphia
Ayu 841 Apprew
Yumi 872 Yuki Hami
Miyu 778 Mimikyu
Yuko 478 Yukimenoko
Koff 619 Kojofu
Fube 669 Flavebe
Beba 859 Belover
Bani 871 Bachin Uni
Nima 431 Nyalmar
Maca 686 Maeika
Tortue 833 Cam Turtle
Meta 648 Meloetta
Poulpe 852 Tatakko
Café 580 Koalhee
Hika 829 Himenka
Tortue 834 Kajirigame
Meva 636 Meralba
Baya 710 Bucketcha
Yam 674 Yan Cham
Muna 890 Mugen Dyna
Nai 598 Natrey
Iko 744 Ivanko
Kori 527 Koromori
Lille 605 Wrigley
Reza 384 Épave Uza
Zata 889 Le Magenta
Bambou 590 Tamagetake
Keso 265 Chemusso
Soo 791 Solgaleo
Oge 861 Oronge
Obtenez 649 Genosect
Tra 364 Todogler
Rat 310 Leibold
Lancer 641 Torneros
Suda 849 Limiteur
Daka 554 Dharmacca
Manchette 786 Kapu Tetefu
Fude 543 Fushide
Ded 225 Livré
Doco 749 Dorobanco
Kori 528 Kokoromori
Arrière 470 Leafia
Aa 823 armure Gaa
Ag 799 Akji King
Guya 768 Gusokumusha
Yaki 512 Yanacky
Kima 760 Kiteruguma
Mayo 618 Magyo
Yoshi 746 Yoshi
Sina 770 Shirodesuna
Naki 538 Nageki
Kigo 610 Kibago
Goda 812 Gorilander
Daro 524 Dangoro
Rom 479 Rotom
Muna 518 Mushana
Nara 328 Knuckler
Rat 814 Pied de rabbin
Lancer 357 Tropius
Serpent Serpent Subi 843
Viva 329 Vibrava
Bao 550 Baslao
Araignée Omo 752 Onishizu
Mou 873 Mosnow
Udo 793 Utsuroid
Dode 748 Dohideide
Deu 181 Denryu
Uu 845 Uu
Uu 692 Udeppou
Uchi 438 Uchi
Chiki 616 Chobo Maki
Kisa 286 Kinogassa
Saya 844 Sadaija
Yami 302 Yami Lami
Mimi 504 Minezumi
Mini 415 Miel Mitsu
Nizo 061 Nyorozo
Zor 570 Zoroa
Ayo 763 Amarjo
Yori 506 Yoteri
Lilu 447 Liol
Lulu 701 Lucable
Luo 404 Luxio
Odo 611 Onondo
Doro 691 Doramidro
Rod 407 Ros Raid
Doa 549 Dredia
Ako 762 Amamaiko
Koshi 401 Koroboshi
Shimo 751 Shizukumo
Moyu 529 Mogru
Yuo 460 Yukinoo
Oshi 234 Odoshishi
Navire 682 Shushup
Puga 564 Protoga
Gaz 689 Gamenodes
Suna 581 Swanna
Naro 287 Namakero
Inférieur 315 Roselia
Aji 761 Amakaji
Jigo 783 Jarango
Gobe 446 Gobe
Bef 153 Feuille de laurier
Fute 425 Fute
Teya 797 Tekkaguya
Yag 199 Yad King
Gua 471 Gracia
Ash 736 Agojimushi
Shiko 667 Shiko
Koshi 664 Kofukimushi
Shigo 589 Chevalgo
Goyo 293 Gonyonyo
Yoku 164 Yornozuku
Kune 827 Kusune
Nera 775 Nekora
Lai 309 Lacrai
Ize 314 Ilmise
Zeka 523 Zebraika
Kate 688 Kametete
Ted 597 Tessed
Dotsu 533 Dotekkotsu
Tsude 805 Tunde Tunde
Deda 050 Digda
Daki 503 Daikenki
Champignon Kiko 285
Koshi 767 Kosokumushi
Cerf 585 Shikijika
Clé 083 Camonegi
Gimo 860 Gimo
Mobo 465 Mojumbo
Bole 708 Boclay
Leva 165 Ladyba
Bab 325 Spring Boo
Buta 136 Booster
Graine 531 Tabunne
Neyu 755 Nemash
Yuri 459 Yuki Kaburi
Lire 345 Lire
Radi 260 Lag Large
Jiko 782 Jaraco
Photoshop 304 Cocodora
Ruth 579 Rankles
Scorpi 451 Scorpi
Piku 440 Pimpuku
Qui 707 Cleffi
Je suis 221 Innomu
Muna 517 Munna
Poire 771 Namakobushi
Shima 522 Shima
Mau 594 Mamanbow
Umu 220 Ulim
Muji 429 Muumaji
Jibi 496 Janobi
Bima 100 Billiri Dama
Machi 556 Malakacchi
Chino 573 Chiracino
Nochi 206 Nokochi
Ciné 548 Chuline
Néo 178 Natio
Ochi 161 Otachi
Chico 509 Choroneko
Koku 402 Korotok
Araignée 690 Kuzmo
Moko 180 Mokoko
Koku 403 Kolink
Kuyu 541 Kurumayu
Yushi 480 Yukushi
Simi 492 Shaimi
Mim 856 Mim Brim
Muku 398 Muku Hawk
Kur 488 Creseria
Anu 730 Achilleine
Numa 759 Nuikoguma
Mane 439 Manne
Nay 177 Nati
Il 717 Ibertal
Luo 448 Lucario
Ochi 162 Otachi
Chibu 499 Chaobu
Buta 693 Broster
Tata 458 Tamanta
Tashi 363 Tamazarashi
Shiga 342 Shizariger
Gato 444 Gabite
Toss 411 Trideps
Sous-nom Sume 276
Meka 586 Mebukijika
Clé 798 Kamitsurugi
Guido 681 Gilgard
Chien 454 Sklog
Guna 262 Graena
Poire 103 Nassie
Shizu 134 Douches
Zugu 559 Zurugu
Guru 210 Grand Bull
Courir 745 Lugargan
Recommended Posts