Mateusz Mazurek – programista z pasją

Python, architektura, ciekawostki ze świata IT

Algorytmika Programowanie

Generator prostych krzyżówek – Java

Cześć! Cieszę się, że mnie odwiedziłeś/aś. Zanim przejdziesz do artykułu chciałbym zwrocić Ci uwagę na to, że ten artykuł był pisany kilka lat temu (2013-02-16) miej więc proszę na uwadzę że rozwiązania i przemyślenia które tu znajdziesz nie muszą być aktualne. Niemniej jednak zachęcam do przeczytania.

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ć:

krzyzowka_krak

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:
pierwsza1

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:

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 ;)

Dzięki za wizytę,
Mateusz Mazurek

A może wolisz nowości na mail?

Subskrybuj
Powiadom o
guest

Witryna wykorzystuje Akismet, aby ograniczyć spam. Dowiedz się więcej jak przetwarzane są dane komentarzy.

2 komentarzy
Inline Feedbacks
View all comments
Damian

Gdzie można znaleźć bazę danych z podobnymi hasłami?
Interesuje mnie wykonanie innego projektu, ale także z hasłami krzyżówkowymi.