Project Euler - Problem #058

Podtitulek problému č. 58 by mohl být Ulamova spirála. Po zběžném přečtení zadání se mi problém zdá jednoduchý a tak jsem si ho nechal na cestu do vlaku. Mno, potrápil jsem se.

Napsal jsem si kostru kódu, abych otestoval ukázkový příklad a po pár pokusech jsem se opravdu trefil. Tak hurá pozměnit cílové podmínky a je to... Nebylo, problém jsem s Nokií a codepadem nevyřešil a tak došlo na starý dobrý počítač.

Nejdřív jsem narazil na to, že Erastothenovo síto mi už nestačí. Přepsal jsem program do C++ s použitím knihovny GMP. Program se ale nechtěl ani teď dobrat výsledku, tak jsem se podivil a zamyslel. Aha - ostudná a osudová chyba byla, že jsem postupoval po všech číslech spirály a ne jen po diagonálách. Upravil jsem kód a zjistil jsem, že GMP opravdu nepotřebuji.

Kód jsem přepsal zpět do Lua a tam jsem čekal na vyhodnocení cca 10 sekund. To ujde. Ještě jednou jsem se vrátil k C++, tam stejný kód počítá výsledek cca 2 sekundy. Bohužel, ani jeden jazyk nestihne na codepadu timeout.

Kód pro Lua. Kód C++.

Project Euler - Problem #057

Po přečtení diskuze k problému č. 57 jsem se trochu zarděl za svůj přístup hrubou silou, ale kdo to měl vědět?

Scheme má (naštěstí) zabudovanou podporu pro práci se zlomky, krátký kód do šuplíku nikdy neuškodí.

Project Euler - Problem #056

Dal jsem si tu práci a zpracoval jsem problém č. 56 ve Scheme jen s použitím základních funkcí. Tím myslím bez použití set!, do-cyklu nebo "prasáckého" převádění čísla na seznam. "Prasáckého" v tom, že jsem používal převod čísla na řetězec, následně převod řetězce na seznam a konečně namapování funkce, která převede znaky na jejich číselnou reprezentaci (\#1 na 1 atd.).

Očekával jsem, že tak upravený kód bude přinejmenším stejně rychlý jako původní. Jenže jsem byl překvapen, na mém počítači upravený program běžel pomaleji. Ehm, pomaleji - místo zlomku vteřiny necelé dvě vteřiny. Někteří kolegové na Projektu Euler dosahovali delších časů, ovšem jejich stroje jsou s mým dnešním nejspíš handicapované. Necítím se dost fundovaný na to, abych tady rozebral příčiny onoho zpomalení, ale nabízím k nahlédnutí obě dvě varianty řešení.

Původní verze.
Upravená verze.

Project Euler - Problem #055

Lychrel je přirozené číslo, které nemá jednu zajímavou vlastnost. Vezmeme si číslo, otočíme ho a přičteme k němu původní číslo - vyšel nám palindrom? Pokud ano, tak číslo není lychrel. Pokud ne, tak operaci zopakujme s výsledkem. Máme velkou šanci, že dříve nebo později se k palindromu dostaneme. Otázka je, jaká čísla palindrom nevytvoří nikdy. Odpověď na ni neznáme.

Proto je pro zjednodušení v zadání problému č. 55 omezen počet opakování sčítání na 49 kroků - poté je možno číslo prohlásit za lychrel. Kdyby tento limit nebyl, tak bychom zřejmě všichni skončili u čísla 196.

Na pomoc jsem si opět vzal Scheme a tentokrát jsem už snad dodržel všechny zásady, jejichž porušení pravověrným "schemerům" zarývá žhavé jehly pod nehty. I když... Funkce pro převod čísla na seznam by se jistě dala napsat bez pomoci převodních funkcí, ale důležitý je správný výsledek.

Project Euler - Problem #053

V problému č. 53 nebyl opět žádný zádrhel, úkol je velmi lehký.

Rozhodl jsem se ho napsat v jazyku Scheme, abych ho úplně nezapomněl. Řešení není úplně schemovské, protože používám funkci set!, třeba to někdy zkusím bez něj.

Řešení je na codepadu.

Project Euler - Problem #052

Problém č. 52 nemá nějak záludné ani zajímavé řešení. Při řešení jsem poprvé použil třídění obecného pole pomocí funkce qsort z knihovny stdlib.h, takže až budu příště qsort potřebovat, mám to tady jako na dlani.

Project Euler - Problem #049

Problém č. 49 mi šel jako psovi pastva. Příčin bylo hned několik.
V první řadě jsem nepochopil, že hledám aritmetickou posloupnost. V zadání to samozřejmě je:

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

Díky mé nepozornosti jsem hledal trojice prvočísel, navíc bez kontroly jejich délky.

Zvolil jsem samozřejmě přímou cestu hrubou silou: Erastothenovo síto, generátor permutací a hledání aritmetických posloupností v množině čísel.

Hledání posloupností rozvedu, nebyl to pro mě úplně přímočarý úkol. Mám množinu přirozených čísel a mým úkolem je zjistit, jaké aritmetické posloupnosti taková množina může vytvořit. Předpokládám, že pracuji se seřazenou množinou, ve které je každé číslo jen jednou. Můj postup je následující:

1. Zvolím za i první nebo následující číslo množiny. Pokud jsem prošel celou množinu, přejdu k bodu 5.
2. Procházím čísla j, která následují po i.
3. Pro každé d = j - i hledám v množině čísla ve tvaru x = i + n * d, (n > 0). Hledání ukončím u n, pro které nenajdu x.
4. Pokud v předchozím bodě najdu víc než jeden prvek, tak zařadím posloupnost do předběžného výsleku. Znovu k bodu 2, respektive 1.
5. Vyřadím z předběžného výsledku takové posloupnosti, které jsou podmnožinou některé předchozí posloupnosti.

Kód k celému problému je (i s výsledkem!) na codepadu.