Challenge

Zaenkrat:
1f
1g
1h
2k
1l
2u
1z
Huh, zdej morem sam še algoritem za spreminjat št. črk pogruntat...trenutni se mi zacikla:(.

TESKAn

Še en mesec je časa.

Thomas..interesting...
Kaksno casovno kompleksnost ima tvoj algoritem ?

lp

Thomas

Ok, imamo znane vrednosti za a, b, c, č, d, in ž. Če bi vedel končno vsoto vseh črk, bi tiste neznane vrednosti, zgeneriral tako, da bi se ujemala s končno vsoto, vmes bi jih pa primerjal s pravilnimi stavki v nekem slovarčku (devetnajst a-jev, dva b-ja). Samo problem, ker ne vem končne vsote in ne znam napisat algoritma, ki bi ti zgeneriral pravilne stavke.

Samo povej, a bi se dalo na tak način pridt do končne rešitve?

Sej naredit stavek, če maš podano začetno število vseh črk, ni tak problem - je relativno enostavno. Preverjanje tut ni problem. Problem je pa najt en algoritem, ki ti bo določu, kolk črk je kerih v stavku. če ma kdo kako idejo - le na plan z njo!

Saj razumem za kaj gre, jaz sem prej vprašal, ČE bi vedel koliko je končno število črk. No kakorkoli že, Thomas, kaj pa tole:

Za črke od "e" do "z" bi v datoteko vpisal do števila 40 (recimo, pač ugibam) z besedami (en e, dva e-ja, ...), potem bi pa napisal algoritem, ki bi ti za vsako črko posebej (bi na random ugibal) izpisal te besede in to po eno besedo (en e, dva e-ja, ...) v drugo datoteko. Ko bi za vse črke to napisal bi preveril če se število črk res ujema z besedami, ki so napisane v datoteki. In to bi ponavljal dokler ne pride do prave rešitve.

Saj to je neke vrste brute force, kajne?

Aha GaPe - maksimalno število te zanima! Vzemi kar toliko, kot sem jest! V tabeli spodaj.

Ampak tako bo po moje dolgotrajno ...

xbite

01 en
02 dva _ -ja
03 tri _ -je
04 štiri _ -je
05 pet _ -jev
06 šest _ -jev
07 sedem _ -jev
08 osem _ -jev
09 devet _-jev
10 deset _-jev
11 enajst _ -jev
12 dvanajst _ -jev
13 trinajst _ -jev
14 štirinajst _ -jev
15 petnajst _ -jev
16 šestnajst _-jev
17 sedemnajst _ -jev
18 osemnajst _-jev
19 devetnajst _ -jev
20 dvajset _-jev
21 enaindvajset _ -jev
22 dvaindvajset _ -jev
23 triindvajset _ -jev
24 štiriindvajset _ -jev
25 petindvajset _ -jev
26 šestindvajset _-jev
27 sedemindvajset _ -jev
28 osemindvajset _-jev
29 devetindvajset _ -jev
30 trideset _ -jev
31 enaintrideset _-jev
32 dvaintrideset _-jev
33 triintrideset _-jev
34 štiriintrideset _-jev
35 petintrideset _-jev
36 šestintrideset _ -jev
37 sedemintrideset _-jev
38 osemintrideset _ -jev
39 devetintrideset _-jev
40 štirideset _ -jev
41 enainštirideset _-jev
42 dvainštirideset _-jev
43 triinštirideset _-jev
44 štiriinštirideset _-jev
45 petinštirideset _-jev
46 šestinštirideset _ -jev
47 sedeminštirideset _-jev
48 oseminštirideset _ -jev
49 devetinštirideset _-jev
50 petdeset _ -jev
51 enainpetdeset _-jev
52 dvainpetdeset _-jev
53 triinpetdeset _-jev
54 štiriinpetdeset _-jev
55 petinpetdeset _-jev
56 šestinpetdeset _ -jev
57 sedeminpetdeset _-jev
58 oseminpetdeset _ -jev
59 devetinpetdeset _-jev
60 šestdeset _-jev
61 enainšestdeset _ -jev
62 dvainšestdeset _ -jev
63 triinšestdeset _ -jev
64 štiriinšestdeset _ -jev
65 petinšestdeset _ -jev
66 šestinšestdeset _-jev
67 sedeminšestdeset _ -jev
68 oseminšestdeset _-jev
69 devetinšestdeset _ -jev
70 sedemdeset _ -jev
71 enainsedemdeset _-jev
72 dvainsedemdeset _-jev
73 triinsedemdeset _-jev
74 štiriinsedemdeset _-jev
75 petinsedemdeset _-jev
76 šestinsedemdeset _ -jev
77 sedeminsedemdeset _-jev
78 oseminsedemdeset _ -jev
79 devetinsedemdeset _-jev
80 osemdeset _-jev
81 enainosemdeset _ -jev
82 dvainosemdeset _ -jev
83 triinosemdeset _ -jev
84 štiriinosemdeset _ -jev
85 petinosemdeset _ -jev
86 šestinosemdeset _-jev
87 sedeminosemdeset _ -jev
88 oseminosemdeset _-jev
89 devetinosemdeset _ -jev
89 enaindevetdeset _-jev
90 devetdeset _-jev

Ja ... okay ... kosilo bo.

Kdor ne bo rešil, lahko pride na Dutch zraven.

hm.. jest mam nov problem ;)

po osmem loopu ni več spremeb... hem hem hem ;)

hm... kdo pa je reku da dobis kosilo Teskan ?? sj nisi resu do konca... ne vellllllllla.. ;)

jao.. do polovice mam tud jest ze resen :))))


1. preštejem znake
2. pokličem funkcijo ki opravlja naslednje:
3. lepo naredim loop cez celo abecedo...
4. pogledam ce ima crka ze kako vrednost (je uporabljena v stavku) al pa ce je ze preassignana (by Thomas)
5. preverim če znak spada v možico črk k jih je predpisal Thomas ;) in mi v tem primeru sforsiram to cifro.
6. pol pa zgeneriram besedo, črko in pripadajoč suffix ( npr: -jev...)
7. ponovno preštejem znake
8. gremo na začetek zanke ter na naslednjo črko
9. ko smo skozi abecedo, pač loopam tole funkcijo tolko časa dolker naj nebi najdu rešitve.... :)

Whoa, kaj sm opazu - tudi Thomasu ne dela pravilno! Da povem, na kaj mislim:

nekaj je že, kar tako naprej! trinajst a-jev, en b, en c, en č, osem d-jev, petinštirideset e-jev, en f, en g, en h, šestnajst i-jev, šestindvajset j-jev, štiri k-je, en l, tri m-je, dvaindvajset n-jev, tri o-je, štiri p-je, deset r-jev, petnajst s-jev, sedem š-jev, triindvajset t-jev, en u, šestnajst v-jev, en z in en ž.

Tle ni en ž, ampak sta dva, kar pomeni, da je v stavku en e in en n manj, so pa zato notri še po en d, v, a, j in a več, itd...hehe.

Pismo, kako naj naredim za preverjanje. Ko mi prešteje za vsako črko posebej, kako naj to potem preverim, če se ujema z besedami.

TESKan, probu programčič. To ni v redu da moraš sam vstavljat število črk. To bi moglo bit avtomatsko.

Thomas je tepec, ki ne obvlada kodnih tabel za schumnike.

Tako je programu vpisal en ZH pod eno X kodno tabelo, pa mu ga program ni štel!

Sicer (mu) program deluje v redu.

nekaj je že, kar tako naprej: sedemnajst a-jev, en b, en c, en č, dvanajst d-jev, oseminštirideset e-jev, en f, en g, en h, enajst i-jev, osemindvajset j-jev, štiri k-je, en l, osem m-jev, dvaindvajset n-jev, pet o-jev, tri p-je, sedem r-jev, sedemnajst s-jev, tri š-je, sedemnajst t-jev, en u, devetnajst v-jev, en z in dva ž-ja!

gape, za preverjanje:
- najprej določi dolžino stavka. To mam jaz tko:

for(i=0;i<1024;i++)
{
if(stavek[i]!=0) stz++;
}

1024 je pač celotna dolžina arraya, v katerem imam stavek.
- pol pa nared eno FOR zanko, moja zgleda tko
(tle me neki forum je6e, za for stavk so pogoji enaki, kot v drugih for zankah, sam da je i manjši od stz+1):

for(i=0;i {
if(stavek[i]=='a') koncni[0]++;
if(stavek[i]=='b') koncni[1]++;
.....
}

stz -> število znakov v stavku
stavek -> char array dolžine 1024
koncni -> int array dolžine 25, vsako mesto je za eno črko abecede; a je v 0, b je v 1,...

za preverit, če se ujema:
Simpl, jaz mam tko:
- dva int arraya dolžine 25; en za začetne vrednosti, en za končne vrednosti
- pol pa en simpl prireditveni stavek pa ena for zanka:

napaka=0;
for(i=0;i<25;i++)
{
if(zacetni[i]!=koncni[i]) napaka=1;
}

Zdej če se katerikoli vrednosti ne bosta ujemali, nastavi vrednost napaka na 1; Se prav, da moreš stavek tolk časa spreminjat, da ostane vrednost napaka==0. Se prav, da daš eno do...while zanko:

do
{
(generator stavka, štetje, preverjanje,...)
}
while(napaka==1)

Pol pa sam še izpis vrednosti pa stavka...

Ta stavek vsebuje natanko sedeminpetdesetkrat prvo črko, dvakrat drugo črko, enkrat tretjo črko, enaintridesetkrat četrto črko, šestintridesetkrat peto črko, enainosemdesetkrat šesto črko, ničkrat sedmo črko, enkrat osmo črko, ničkrat deveto črko, sedemintridesetkrat deseto črko, dvajsetkrat enajsto črko, dvainpetdesetkrat dvanajsto črko, ničkrat trinajsto črko, enajstkrat štirinajsto črko, enainštiridesetkrat petnajsto črko, šestinpetdesetkrat šestnajsto črko, sedemkrat sedemnajsto črko, štiriinšestdesetkrat osemnajsto črko, devetinštiridesetkrat devetnajsto črko, desetkrat dvajseto črko, sedeminosemdesetkrat enaindvajseto črko, dvakrat dvaindvajseto črko, osemnajstkrat triindvajseto črko, ničkrat štiriindvajseto črko in ničkrat petindvajseto črko abecede.

Thomas: okej, to pa je že hud biznis...

sicer ma pa tvoj program malo napačo: (glej naslednje sporočilo)

Sergio

vsebuje "tri l-je".

Ampak v načelu maš pa prav.

Jaz sem že pognal svoj random generatorček za tole, pa sem ugotovil da se pisanje v datoteke in random ugotavljanje ne splača (porab PREVEČ cajta).

Moram še malo porihtat . Zagotavljam pa da do naslednjega tedna bom imel rezultat .

Nope, brute force res ne gre. S precej optimiziranim algoritmom je blo cca 10^17 možnosti.

Mal preveč, a ne?

/me + serđ + še en sošolec smo danes v šoli skrčili število možnosti na 1*10^12. Ko se mi bo ljubilo napisati program za preverit zadevo (ubistvu so same celoštevilčne operacije - nič stringov)... dobite brute force rešitev.

GaPe: res lahko, vendar ti še vedno ostane OGROMNO možnosti. Tko da po moje se je bolje skoncentrirat na to, da najdemo način, KAKO popravit napačen stavek, da bo bolj pravilen. Zaenkrat sm jaz probau dva načina:

- nardiš stavek, preveriš, začetne vrednosti, ki ne veljajo, nadomestiš z končnimi. Stvar se zacikla.
- Po x - bite - ovi ideji sem spreminjal črke eno naenkrat, če je bila končna vsota črk večja od začetne - prištel ena, če je bila končna manjša od začetne - odštel ena. Zadeva se tut zacikla, ma se mi zdi, da deluje bolje.

Zdej pa iščem ideje - koko se še lahko spreminja stavek? Any idea is welcome.

P.S.:
GaPe, ti slučajno študiraš elektro?

P.P.S.:
Primož: lahko zvem, koko ste zgeneriral te možnosti? Kr če ne gre drugače - mo pa 1*10^12 opcij preverjal.

Danes sem v 1h skupaj spackal program, ki brute force preverja možnosti. Ker trenutno dela samo 2mio kombinacij / s se ga sramujem. Ko bo nekje nad 50mio kombinacij... ga dobite. Vendar bo takole šlo prepočasi, tako, da bo treba probat implementirat matematični postopek po katerem smo prisli do 10^12 možnosti (namig... nihče naj se ne trudi preverjat za katerokoli črko za več kot 64 ponovitev... ni vredno.. in edina črka s to količino - MAX - ampak res MAX z zelo nizko verjetnostjo - je e... vse ostale imajo bistveno manj ponovitev. Sedaj se ravno brute force dokazuje, da je nečesa več kot pet. Ko bo končal... dobite še dodatno skrčeno število možnosti - verjetno vsaj za faktor 10 in takrat napišem do kje sem prišel. In pa še nekaj... preverjat in računat je potrebno samo 12 črk (in ne 25), tako da najbolj črni brute force scenarih pobere približno 30^12 kombinacij (obljubim... da bom vsaj do 10^10 priteral zadevo... če bo le čas)

Cool! Dobr ... dobr ... me veseli.

Js sem pa naštel 14 črk, ki jih je treba preverjat.

Lahko bi napisal program v ASMju, ampak nekako v tem ne vidim smisla. Hitrost ne bi bila bistveno večja, kot v dobro napisanem C programu, dela pa bi bilo bistveno več.