Cześć. Dziś nieco bardziej praktycznie. Pokażę jak w łatwy sposób wygenerować proste krzyzówki, przedstawię kod, algorytm i przypatrzymy się złożoności obliczeniowej takiej operacji.. ;)
Ok, pierw przygotujmy sobie słownik.
Każde generowanie krzyżówke musi miec zasób słów i pytań do nich. Zazwyczaj są to kilku tysięczne (może kilkunasto tysięczne) zbiory danych. Ja się posłużę mała, pierwszą lepszą z Internetu bazą danych posiadającą 132 rekordy w dwóch tabelach – hasło i pytanie.
Dane trzymam w pliku tekstowym – nic wyszukanego. Separatorem jest „-„, więc wygląda to tak:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 | ACE - wybielacz z reklamy ACETON - zmywacz manikiurzystki ACHTEL - ósmak ADAM - stracił żebro, zyskał żonę ADAMASZEK - tkanina na obrusy ADAMOWO - jezioro w województwie wielkopolskim ADAMSYT - trujący gaz bojowy ADENAUER - kanclerz RFN w latach 1951-55 ADEPT - zwolennik jakiejś doktryny ADIEU - francuskie żegnaj ADIUNKT - pracownik naukowy ADIUSTATOR - kolega korektora ADIUTANT - ordynans ADONIS - miłek wiosenny ADORATOR - absztyfikant ADORATORKA - admiruje lubego ADRES - dane dla poczty ADWENT - okres postu z roratami AERATOR - ręczny spulchniacz gleby AERONAUTA - pilot zeppellina AEROTERAPIA - leczenie powietrzem atmosferycznym BIBUŁA - papier w suszce BICZ - bat do chłosty BIDET - oddolny natrysk BIDON - manierka kolarza BIEDA - niedostatek BIEDAK - żyje w niedostatku BIELAK - jaśniejszy od szaraka BIGA - dwukółka BIGBIT - muzyka rockowa BIGOS - myśliwski z kiełbasą BILA - wpada do łuzy BILARD - stół z łuzami BILE - wpadają do łuzy BILET - uprawnia do przejazdu CZECHY - państwo z Pragą CZEK - zastępuje gotówkę CZEP - wąs powoju CZERŃ - kolor żałoby CZESNE - opłata za naukę w szkole CZŁAPY - potocznie zniszczone obuwie CZOP - szpunt, zatyczka CZOPEK - mała zatyczka CZORT - kaduk, szatan CZUB - na głowie dudka CZUWAK - kolejowy hamulec automatyczny CZWÓRA - stopień szkolny CZYNEL - talerz perkusisty CZYNSZ - opłata za lokal DERBY - wyścigi trzylatków DES - "D" z bemolem DESA - tu kupisz antyk DESSAU - niemiecki port nad Muldą DĘBINA - drzewostan liściasty DIABETYK - potocznie: cukrzyk DIALOG - rozmowa DIANA - była synowa Elżbiety II DINAR - waluta Iraku DION - Celine, piosenkarka kanadyjska DIPOL - typ anteny DISCO - rytmiczna muzyka ETEN - z niego etanol ETER - dawna narkoza ETIUDA - ćwiczenie muzyczne ETNA - dymi na Sycylii ETOLA - futrzany szal FAKS - telefoniczna kserokopiarka FAKT - zdarzenie FALA - morski bałwan FALEZA - klif, urwisko brzegu morskiego FALSTART - błąd sprintera FAŁ - w olinowaniu żaglowca GIWERA - potocznie pistolet GLAZURA - polewa, szkliwo GLEBA - grunt, ziemia GLEMP - obecny prymas Polski GLENN - pierwszy Amerykanin w kosmosie GLĘDA - maruda, nudziarz (potocznie) IDEAŁ - okaz bez wad IDEOLOG - partyjny teoretyk IDEOWIEC - człowiek oddany wielkiej sprawie IDIOM - zwrot trudny do tłumaczenia IDIOTA - utwór Dostojewskiego KALO - strata na wadze towaru KALWIN - Jan, reformator religijny ŁKANIE - ukryty płacz ŁOBUZ - często psoci ŁOJOTOK - choroba skóry głowy ŁOMOT - łoskot ŁOMŻA - na trasie Grajewo-Ostrołęka ŁONO - natury lub Abrahama ŁOPATA - narzędzie dla działkowicza ŁOPATKI - można na nie kogoś położyć ŁOPOT - trzepot chorągwi ŁOSIAK - ciele klępy ŁOSKOT - odgłos uderzenia MAMBO - kubański taniec MAMER - więzienie potocznie MAMROT - osoba mrukliwa MAMUT - słoń z epoki lodowcowej MAN - wyspa jak ciężarówka MANAT - lamantyna MANDAT - policyjna grzywna MANELA - dawna bransoletka MANELE - drobiazgi ODIUM - wstręt do czegoś, niechęć ODLEW - wyrób z giserni ODŁOGI - ugory ODŁÓG - ugór ODŁÓW - łapanie zwierzyny łownej SESJA - obrady SEZAM - bajkowy skarbiec SEZAMKI - prostokątne ciasteczka SĘKARKA - rodzaj obrabiarki do drewna SĘKI - szpecą deskę SFERA - powierzchnia kuli ZGRED - ramol, wapniak ZGRYZ - korygowany przez ortodontę ZIBI - pseudonim Bońka ZICO - były piłkarz z Brazylii ZIELARKA - zbiera miętę i rumianek ZIELE - angielska przyprawa ZIĘĆ - mąż córki ZIMA - pora roku ze śnieżycami ZIN - rysował piórkiem i węglem ZIOMEK - rodak ZIS - rosyjski samochód KAŁAN - kuzyn łasicy znad Pacyfiku KAMAS - grał w KAMASZ - but z cholewką KAMIS - firma znana kucharzom KANA - biblijne miejsce cudu |
Krzyżówkę w takiej formie będziemy generować:
Ok, to pierw zobaczmy jak wygląda algorytm, który sam w sobie trudny nie jest.
1. Pobierz słowo które ma być wynikiem.
2. Określ jego długość i zapamiętaj.
3. Weź pierwszą litere z wyniku.
4. Losuj wyraz z bazy.
5. Sprawdź czy wylosowany wyraz zawiera aktualną litere z wyniku.
6. Jeśli tak wybierz ten wyraz jako słowo pasujące do aktualnej litery wyniku.
7. Usuń wyraz wylosowany z bazy danych. Wróć do 3 pkt i weź kolejną literę.
8. Jeśli nie, wróc do do pkt 4.
9. Wyświetl wynik.
Trudne nie jest i raczej intuicyjne. Implementacja równiez nie jest jakoś bardzo złożona. Ja zrobiłem to na 3 listach. Doimplementowałem tez wiązanie pytań do wybranych haseł.
Zastosowanie losowania powoduje że ilość kombinacji jest spora (rośnie wraz ze wzrostem ilości rekordów w bazie danych). Stworzę teraz 2 krzyżówki w odstepnie kilku minut od każdej. Dla hasła PROGRAMOWANIE.
Pierwsza:
I pytania:
1. typ anteny
2. ramol, wapniak
3. narzędzie dla działkowicza
4. muzyka rockowa
5. stół z łuzami
6. w olinowaniu żaglowca
7. wyspa jak ciężarówka
8. rodak
9. okres postu z roratami
10. dwukółka
11. pilot zeppellina
12. wpada do łuzy
13. ćwiczenie muzyczne
No i druga:
No i standardowo pytania:
1. szpunt, zatyczka
2. admiruje lubego
3. odgłos uderzenia
4. partyjny teoretyk
5. kanclerz RFN w latach 1951
6. drzewostan liściasty
7. słoń z epoki lodowcowej
8. trzepot chorągwi
9. potocznie pistolet
10. ćwiczenie muzyczne
11. dymi na Sycylii
12. typ anteny
13. ręczny spulchniacz gleby
Jak widać powtórzyły się 2 pytania. W innych miejscach i inna litera z nich jest wykorzystywana do zbudowania wyniku. Skąd powtórzenie? Po pierwsze mamy małą bazę danych – czyli łatwiej jest trafić w coś kilka razy. Po drugie nasze losowanie jest średnio losowe. Chociaż pewnie problemem jest mała baza danych.
Co z zasobami jakie wymaga generowanie krzyżówki. Hm, zalezy to od implementacji. Nie unikniemy jednak jakiś struktur danych do przechowywania bazy danych.. No, możemy jakoś odczytywać to z pliku, ale to zwolni cały proces. Nie unikniemy kilku pętli.
Założoność obliczeniowa zależy więc od długości słowa które jest wynikiem oraz od.. Tego z jakis liter jest ono zbudowane. Prawdopodobieństwo występowania liter w słowach jest różne, oto jak się ono przedstawia:
| znak | [%] | znak | [%] | znak | [%] | znak | [%] |
|---|---|---|---|---|---|---|---|
| a | 8.91 | t | 3.98 | l | 2.10 | ż | 0.83 |
| i | 8.21 | c | 3.96 | ł | 1.82 | ś | 0.66 |
| o | 7.75 | y | 3.76 | , | ?.?? | ć | 0.40 |
| e | 7.66 | k | 3.51 | b | 1.47 | f | 0.30 |
| z | 5.64 | d | 3.25 | g | 1.42 | ń | 0.20 |
| n | 5.52 | p | 3.13 | ę | 1.11 | q | 0.14 |
| r | 4.69 | m | 2.80 | h | 1.08 | ź | 0.06 |
| w | 4.65 | u | 2.50 | ą | 0.99 | v | 0.04 |
| s | 4.32 | j | 2.28 | ó | 0.85 | x | 0.02 |
Sprawdźmy :) Zmierzę teraz ile trwać będzie stworzenie krzyzówki dla AAAAA i BBBBB. Wyniki:
| [ns] | 1 próba | 2 próba | 3 próba | średnia |
| AAAAA | 1549511 | 2346793 | 1578596 | 1824966 |
| BBBBB | 2043962 | 7869597 | 6009842 | 5307800 |
Czyli potwierdziło się, że częstotliwość pojawiania się liter w słowach ma znaczenie przy procesie tworzenia krzyzówki.
Oczywiście tyczy się to naszej bazy danych. Jeśli stworzymy bazę danych z wyrazami które będą tworzyć razem równą co do wartości sumę wystąpień A i B – wyniki się zmienią. Tabela która przedstawia procentowe prawdopodobieństwo zaczerpnąłem z tego miejsca. Gdzie czytamy:
Lista została utworzona wg próbki korpusu języka polskiego.
Ok, teraz czas na kod. W pliku dataK.txt znajduje się dokładnie ta baza która jest wyżej.
Pierw samo użycie klasy:
1 2 3 4 5 6 7 8 9 10 11 12 13 | public static void main(String[] args) { KrzGen ne=null; try { ne = new KrzGen("AAAAA"); } catch (FileNotFoundException ex) { } ne.Generate(); ne.show(); } |
Gdzie w konstruktorze przekazujemy wynik krzyżówki.
i sama klasa KrzGen:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | import java.io.File; import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.List; import java.util.Random; import java.util.Scanner; /** * * @author Matt */ public class KrzGen { private List<String> dane = new ArrayList<String>(); private List<String> pytania = new ArrayList<String>(); //listy przechowuje dane i pytania oddzielnie private String wynik=null; private int dlugosc_wyniku; private class Haslo{ String haslo; int i; int przeciecie; String pytanie; } //kazde haslo jest obiektem klasy Haslo private List<Haslo> wynikKoncowy = new ArrayList<Haslo>(); //przechowuje wynik koncowy, calosc wygenerowanych haseł public KrzGen(String n) throws FileNotFoundException { this.wynik=n; this.dlugosc_wyniku=this.wynik.length(); String temp[]; File file = new File("d:/daneK.txt");//otwieram plik Scanner in = new Scanner(file); String t=null; while(in.hasNext()){ t=in.nextLine(); temp=t.split("-"); //dziele linie wg separatora dane.add(temp[0]);//dane do danych pytania.add(temp[1]);//pytanai do pytań } } public void Generate(){ Random r = new Random(System.nanoTime());//inicjalizacja boolean nieznaleziono=true; while(wynikKoncowy.size() != dlugosc_wyniku)//dopóki wynik koncowy nie bedzie tak //dlugi jak dlugosc wyniku podanego w konsruktorze { for(int i=0;i<dlugosc_wyniku;i++){//od 1 do ostatniego znaku wyniku nieznaleziono=true; while(nieznaleziono){//dopóki nie znaleziono int rr = r.nextInt(dane.size());//losuj liczbe int mniejsza od wielkosci danych String tmp = dane.get(rr);//wybierz slowo wylosowane for(int j=0;j<tmp.length();j++){ if(wynik.charAt(i) == tmp.charAt(j)){ //jesli jakis znak wylosowanego slowa sie zgadza z aktualnie przetwarzana litera wyniku Haslo nastepne = new Haslo(); nastepne.haslo=tmp; nastepne.i=i; nastepne.przeciecie=j; nastepne.pytanie=pytania.get(rr); //tworze obiekt wynikKoncowy.add(nastepne);//dodaje go do listy koncowej dane.remove(rr);//usuwam z danych pytania.remove(rr);//usuwanie pytanie nieznaleziono=false;//markuje ze znaleziono } if(nieznaleziono==false) break;//koncze petle przeszukiwan jak i pętle //przeszukiwan liter } } } } } public void show(){ for(int i=0;i<wynikKoncowy.size();i++){ System.out.println(wynikKoncowy.get(i).haslo+"przy: "+(wynikKoncowy.get(i).przeciecie+1)+"" + "\n" + "Pytanie:"+wynikKoncowy.get(i).pytanie); //wyswietlam pytanie, miejse przeciecia z wynikiem i haslo } } } |
Mam nadzieje że wpis ciekawy ;)
Mateusz Mazurek
Gdzie można znaleźć bazę danych z podobnymi hasłami?
Interesuje mnie wykonanie innego projektu, ale także z hasłami krzyżówkowymi.
Nie mam pojęcia :(