01.09.2011

Conway hra života v jednom riadku APL

Original on http://catpad.net/michael/apl/

Tento program funkcia “Dr.Dobbs”, február 2007

Vysvetlenie

Ak nie ste oboznámení s jeho hra Conveo života alebo APL programovací jazyk, odporúčam konzultovať veľmi stručný popis APL a popis hry Conwaya života. Okrem toho na tejto stránke nájdete APL2 IBM interpret jazyka a niekoľko odkazov.

Tento podrobný popis APL program, ktorý vypíše N generácie počiatočnú konfiguráciu M k hre života bude tiež slúžiť ako stručný a veľmi neformálne kurz APL.

Než začneme sa rozlúštiť (to sa zdá byť správne slovo tu) program LIFE, poďme sa pokúsiť vypracovať stratégiu, ako napísať tento program v jednom riadku, bez ohľadu na to, ako to vyzerá nemožné.
Život je cyklický hra je vo svojej podstate a – iste – algoritmus vykonávania tejto hre podľa všetkého by sa mal skladať z niekoľkých cyklov. To znamená, že hlavné slučky programu je tok generácií. Ďalšie slučka je ten, ktorý kontroluje matice pre výpočet bunky, ktoré sú mŕtve, živé alebo novorodenca. Ešte jedna slučka vypočíta počet susedov každej danej bunke. Teraz si myslím, že to je: nemôžeme použiť ani jediný slučky do jedného riadku, nieto tri vnorené slučky!
Ale počkajte chvíľu – APL umožňuje prekonať takmer všetky, aj tie zúfalej situácii.

Po prvé, nepotrebujeme slučka pre skenovanie matice, pretože APL nám umožňuje pracovať s celou maticou obvykle používať jednu funkciu. To isté platí pre počet susedov. Pokiaľ ide o hlavnú slučku, ktorá govenrs generačná zmena – nebude žiadna taká vec vôbec!

Nech n je počet generácií, chceme počítať. Môžeme zapisovať všetky slučky (tzn. podprogramy, ktoré tvoria telo cyklu), ako jeden veľmi dlhý rad. Teraz všetko, čo musíte urobiť, je vykonať tento riadok.
To nie je dobré – hovorí, že čitateľa. – Čo keď potrebujeme 1000 generácie? Máme napísať 1000 slučiek, ktoré robia to isté potom? Rozhodne nie! Ako sme povedali skôr, všetky tieto slučky robia to isté, tak budeme len napísať iba jednu slučku a potom APL nám pomôže násobiť, že N časov pomocou ρ (ro) funkcie, pretože to je funkcia, ktorá vytvára pole akýkoľvek rozmer. Potom, čo sa tak stane, budeme volať úžasné APL funkciu nazvanú Execute – . Táto funkcia vykoná reťazec považovať to za platný rad APL program. (Takmer rovnaký operátor v Lisp je nazývaná eval). Táto funkcia bude zodpovedná za realizáciu “veľmi dlhé línii” dlhých slučky orgánov.

Nakoniec, budeme musieť počítať všetky susedov každej danej bunke nášho matice. A to je hlavný trik nášho programu.
Poďme predstavujú živé bunky života ako 1 a 0 ako prázdne bunky. Pre náš príklad budeme mať 5×5 a dal v stredu veľmi jednoduchý, ale zaujímavý organizmus zvaný semaforu:

To je, ako sa chová semafór:

Čo máme urobiť pre to, nájsť súčet všetkých susedov každej bunky v danej matici? Počet susedov sa rovná 8, tak, ak budeme posun našej matrice 8 krát v každom možnom smere a potom spočítajte všetky 1s do výslednej bunky – čiastka sa bude rovnať počtu 1s (napr. susedia) okolia danej bunky.

Na nasledujúcom obrázku vidíte všetkých 8 matice po taký posun:

Teraz sa poďme zhrnúť všetky tieto matice okrem pôvodnej:

Tu sa bližšie pozrieť na niektoré z buniek, ktoré smerujú k ich susedom v pôvodnej matici:

Máme matice, kde každá bunka obsahuje číslo susedov živých buniek z pôvodnej matrice!
Teraz, v súlade s pravidlami života tých buniek, ktoré majú 2 alebo 3 susedov žiť v nasledujúcej generácii, zatiaľ čo všetci ostatní zomrú. Prázdne bunky, ktoré majú presne 3 susedov sa narodil v nasledujúcej generácii.
Vykonávanie niekoľkých jednoduchých logických operácií na matrike susedov dostaneme ďalšie generaion nášho semaforu.

S týmto plánom akcií, môžeme začať detailné štúdium tohto programu.
A je to tu:

Dešifrovať programu budeme pohybovať sprava doľava, pretože to je spôsob, akým sa pohybuje APL tlmočníka. Pre väčšie pohodlie (a iba pre väčšie pohodlie, pretože tam je nič v APL, že to diktuje), budeme deliť náš program do logických blokov tak je znázornené na nasledujúcom obrázku:

Týmto spôsobom bude ľahšie sledovať udalosti rozvíjajúce.

Medzi apostrofy je reťazec, ktorý tvorí “telo” Náš hlavný slučky (blok 1):

Prvá vec, čo sa deje tu, je uzavrite operácia vykonaná na pôvodné matice M: ⊂ M. Funkcia uzavrite zmení rad akéhokoľvek rozmeru do skalárne (to znamená, že pole stráca všetkých jeho dimenziách, zatiaľ čo jeho vnútorný obsah zostáva bezo zmeny). Táto situácia je trochu zvláštne, takže obraz sa môže hodiť:

Ďalšie funkcie sa nazýva Rotácia: . Sa otáča maticu zadaného počtu opakovaní vo vzťahu k jeho horizontálnej osi (ako je vidieť z tvaru funkcie). Aby bolo možné pochopiť zmysel tejto funkcie a vysvetliť symbol”na svoje právo, pozrime sa najprv na ľavú argument otáčanie, a to výraz: (V, V ← 1 -1).

Dve akcie prebiehajú tu: premenná v dostane pridelený s vektorom 1 -1 (to je reprezentovaná V ← 1 -1), a táto premenná je okamžite použitý (v skutočnosti sa táto premenná byť mnohokrát v tomto programe ). Tu sa stretávame s novou funkciou -, (čiarka), ktorý sa nazýva Catenate a slúži na spojenie dvoch častí do jedného vektora. Preto sa výraz V, V ← 1 -1 vyhodnotený ako vektor sa skladá zo štyroch častí: 1 -1 1 -1. Ako sme už povedali, vedľajší efekt tohto výrazu je inicializácia premennej V.

Tak, máme nasledujúce (blok 2):

Operátor”(ktorý sa nazýva každá) ovplyvňuje funkciu Otočiť takým spôsobom, že každý prvok z ľavého argument Otočiť dostane zodpovedajúce náprotivok prvok argument righ z Otočiť a otáčania matice M sa stane dvojicu páru.
(Jedno slovo na subjekty: zatiaľ čo funkcie pracujú na poliach alebo Skalár, funkcie, operátory pracujú sami, tj v prípade, že argument funkcie je vždy pole alebo skalár, argument obsluhy, je vždy funkcie).
Samozrejme, že každý operátor použiť s akoukoľvek inú funkciu, z APL.
Poznámka: Táto: v prípade, že jeden z argumentov funkcie je skalárne (a spomeniete si, že pôvodný matica M bol sa zmenil na skalárne v uzavriete), bude to skalárne sa vektor s počtom rovnakých prvkov, ktoré zodpovedajú počtu prvky vektora, čo je ďalší argument funkcie. To znamená, že môžeme vidieť náš výraz:

Teraz je ľahké pochopiť, čo sa deje. Matrix M otáča štyrikrát okolo horizontálnej osi: jeden riadok hore, jeden riadok dole, opäť smerom nahor, a opäť o jeden riadok dole.
Tu je výsledok:

To, čo sme sa sem dostali, je prechodný výsledok, samozrejme. Vlastne sme sa posunúť každý z týchto matíc vľavo a vpravo si uhlopriečky posunie po všetkom. A pretože už máme všetky potrebné znalosti, môžeme to urobiť s týmto výrazom:

Opäť použijeme funkciu otáčania, ale tentoraz to bude rotovať okolo vertikálnej matice osi (ako symbol znamená). Prevádzkovateľ Každý bude pracovať na všetkých štyroch matice v závislosti na ľavom argument Otočiť: vľavo, vpravo, vpravo, vľavo. Okrem toho, získať maximálny zisk premenné V, budeme používať aj tu, a namiesto vektora 1 -1 -1 1 budeme písať (V, V). Otočiť sa tu použiť znovu a je aplikovaný na V samotnej.
Možno, že tento výraz nie je prispeje k objasneniu veci, ale to je tak APL-ako!

Teraz vieme, čo je výsledkom výrazu

Vyzerá. Budeme ju nazývať Blok 3:

Po matica M je posunutý do všetkých šikmo všetko zostáva, je posunúť sa hore, dole, doľava a doprava.
To znamená, že výsledok výrazu

budú:

A výsledok výrazu

budú:

A konečne, je matica pohyboval vo všetkých 8 smeroch. Ak chcete zistiť počet susedov každej bunky musíme vektor sa skladá z matice sme dostali tak ďaleko a zhrnúť všetky prvky vektora. V APL Môžeme to urobiť jednoducho takto:

+ / (Blok 5), (Block 4), (Block 3)

Tu je predstavený iný prevádzkovateľ. To sa nazýva redukcia a vyzerá lomkou: / vložky Redukcia prevádzkovateľovi svoj argument funkcie (v tomto prípade pridania funkcie) medzi všetkými prvkami daného vektora. Všimnite si tiež Catenate funkciu, ktorá vytvorí vektor všetky bloky. Tu je to, čo máme:

(Matica 1 z bloku 5) + (matica 2 z bloku 5) +
(Matica 1 z bloku 4) + (matica 2 z bloku 4) +
(Matica 1 z bloku 3) + (matica 2 z bloku 3) + (matica 3 z bloku 3) + (matice 4 bloku 3).

A teraz máme maticu všetkých susedov. To je výsledkom výrazu, ktorý sme nazvali Blok 6.
(Dodajme, že je tu ešte jedna funkcie vykonávané na výslednej matice – zverejniť: ⊃ To je presný opak uzavrite Táto funkcia ukáže skalárne obsahujúce maticu späť do matice s pôvodné rozmery..).

Ďalším krokom, ako bolo povedané, je nájsť všetky bunky s počtom susedov rovné 2 alebo 3, tak, že budú aj naďalej žiť v nasledujúcej generácii, a nájsť prázdne bunky s počtom susedov vo výške 3, tak, aby nové bunky sa tu narodil.
Po prvé, poďme porovnať matice susedí s matricou naplnený 2S (bod 7) tak, aby výsledok dostaneme maticu núl a jednotiek tak, že tie zodpovedajú bunky majú presne dva susedov:
2 = T ← matice všetkých susedov (blok 6)

Tu opäť dve akcie sa vykonávajú súbežne: premenné T získa hodnota matice susedov a zároveň je v porovnaní s maticou 2s (všimnite si, že skalárne “2″ je rozšírený o maticu, ktorej 2s Rozmery sú rovnaké matrice je v porovnaní s – to je, ako funguje APL).
Tu je návod, ako porovnanie vyzerá v skutočnosti:

A výsledok je:

Ako je vidieť, výsledná matica obsahuje v každej bunke výsledok porovnania zodpovedajúcich buniek argument matice. 1 znamená, že bunky sú si rovní, 0 – inak.

Ak budeme vykonávať logické operácie AND (∧), nad touto a pôvodná matica M (bod 8), ktorý je 1s zostane iba v tých miestach, kde obe matice majú 1s, dostaneme maticu, kde len živé bunky sú tie, ktoré majú presne dva susedov:

Naozaj, v originálnej matica M iba centrálna bunka má práve dva susedov.

Rovnakým spôsobom môžeme nájsť všetky bunky, ktorý má presne tri susedov. Poznámka: Trik: Nie je dôležité, či pôvodná bunka prázdna, alebo živý: musíme nechať živé bunky žiť a naplniť prázdne bunky s novo narodené 1s.
Výsledkom výrazu 3 = T (blok 9), kde T, ako si spomeniete, je matica susedov, bude:

Tieto bunky sa narodil v nasledujúcej generácii.

A konečne, musíme logicky pridávať (pomocou OR (∨) prevádzka) i matice z posledných dvoch výrazov a – voila! – Sme sa počíta budúcej generácie života pre matice M!

Všetci spoločne teraz:
Blok 10 ← matice všetkých susedov, to je
(3 = T) ∨ ∧ M 2 = T ← matice všetkých susedov
dá výsledok:

, Ktorá je skutočne novú generáciu semaforu.

Teraz musíme vytlačiť Výsledná matica a urobíme to pomocou APL výstup funkcie nazvaná Quad: (To je dosť “priradiť” The Matrix, aby túto funkciu).

Sme však neskončil.
Pamätajte si, že až doteraz všetko, čo sme urobili, bolo výpočet jednej generácie. Okrem toho sú všetky aktivity, “zamrznuté” medzi apostrofy. Takže, čo sa stane tento reťazec?

Pozrite sa na bloku 11. Premenná S je priradená reťazcom označil Blok 1. Poznámka znovu: S nie je rovná zmysle (alebo hodnoty), reťazce, S je rovná reťazci sám, tj sekvencie znakov medzi apostrofy. Týmto spôsobom sme sa zdržiavať prevedení Block 1 až do okamihu, keď bude všetko pripravené pre výpočet N generácie života. (Nezabudnite, že blok 1 počíta iba jednu generáciu).

Ak chcete S z vektor znakov do skalárne budeme používať uzavriete funkciu, ktorá je už dobre známe, k nám. Presunutie doľava budeme objavovať nové funkcie - pretvorí (ρ) s ľavým argument n predstavuje počet generácií, chceme počítať. Táto funkcia sa zmení teraz skalárne S do vektora n elementy rovnaké, každý z nich obsahuje Block 1, ktorá je “podprogram”, pre výpočet jednej generácie. Všeobecne teda platí, máme vektor scalars skladajúci sa z vektorov znakov.

Finálny premeniť – ďalšie funkcie Vstúpte do bojov (∈) slúži na vytváranie jednoduchých vektor z poľa sa skladá z ľubovoľného počtu vnorených prvkov. A tak sa náš “komplex” vektor n elementy vnorené stal jeden veľmi dlhý, ale jednoduchý vektor znakov. Menujme to nejako mimoriadne zdôrazniť význam tohto vektora, povedzme, ako matematici často.

Tu je to, čo venovať pozornosť: každý z reťazcov (tj každý blok 1) na vektor a začína sa symbolom M (pôvodné matrice), a končí operátor priradenia ← (ako obvykle, začína sa na pravej strane a na konci je na ľavej strane). To je najviac vpravo charakter – je pôvodná matica M a vektora sám vyzerá takto (vnútorný obsah preskočí):

A sme tu! Teraz je jasné, čo sa deje: keď je String vykonané z prava do ľava, každý novo vypočítané hodnoty matice M (tj každá nová generácia of Life) bude pridelená rovnakú premennú M ako nový pôvodnej matice pre výpočet novej generácie! A počet generácií bude rovná N.

Jediný zostávajúci problém je, čo robiť s najviac vľavo, visí vo vzduchu operátor priradenia ←. Pozrite sa na celý program znovu – na samom konci šípka rovno, aby symbol – Quad – čo je spojenie s vektor a čiarkou (Catenate). Ale nemusí to znamenať, vytlačiť všetko? Presne tak, to je to, čo potrebujeme!

A konečne na konci tejto veľkolepej zákona sme plní funkciu (Execute) – ten už sme zvyknutí. Táto funkcia vykoná symbolický reťazec, ktorý sa tejto funkcie argument. Samozrejme, že by reťazce containg syntakticky správny výraz APL. Takže, čo je to za funkciu? Jedná sa o APL tlmočníka sa tvári ako nevinný funkcie.

No, aký bude výsledok realizáciu našich excellence vektora pár â?
Vpravo – n matrices vytlačený na obrazovke, ktoré predstavujú N generácie života od pôvodného matice M.

QED

© 2005 Michael Gertelman