[ MajorFatal @ 24.01.2017. 22:11 ] @
Jeri sam nasvojio čelindž? :) http://marknelson.us/2012/10/0...mment-page-11/#comment-1452544

Challenge Version 2 – A General Purpose Random Compressor
Challenge 1 is interesting because it is nearly, but not assuredly impossible. Challenge 2 is more along the lines of troll bait, because it is patently impossible: create a system to compress and then decompress any file of size 415,241 bytes. In other words, create a compressed file that is smaller than the input, then use only that compressed file to restore the original data.

Unlike Challenge 1, there are no size limitations on Challenge 2. Your compressor and decompressor can be as large as you like. Because the programs have to be able to handle any input data, size is of no particular advantage – there is no data to hide.

This challenge is for the contestant who is sure that he or she has figured out a way to compress the million digit file, but finds that their program takes 100 MB of space. Okay, that’s fine, we shall first see if it can compress the file. It then must be able to correctly compress and decompress a file of the same size. Let’s say, on 1,000 different files.

To keep it simple, the files will be simple permutations of the million digit file – scrambled with an encryption system, or perhaps a random number generator, or whatever. The point is, they should have all the same numeric characteristics as the original file, just organized slightly differently.

Again, I will emphasize that Challenge 2 is at its heart provably impossible to beat. No program can compress all files of a given size, and the chances of any program being able to compress 1,000 different files of this length is so vanishingly small that it can safely be ruled out, even if every computer on earth was working on it from now until we are engulfed in flames during Sol’s red giant phase.

Moj Predlog:

Compression

1. Cut all leading bits whatever they are 0 or 1 (if in the begining there only zeroes cut all zeroes, if they are ones cut all ones from the beggining, if there is only one bit that kind cut that one bit) and the rest of the file save as compresed file under exstension cf1 (compresed file type 1)

2. There are 2 files lenght 451,241 where if you cut all same bits you wil cut whole file those are files containing only zeroes and file contains only ones, if it is such file just write 0 or 1 to determine which type of file is and save under extension cf2 (compressed file type 2)

Decompression:
1. If the first bit in compressed file is 1, then add as much zeroes to fill up to 415,241 bytes, If the very first bit in compressed file is 0 then add as much ones as you need to beggining of file to made up 415,241 bytes file

2. If file is under extension cf2 see what is in it 0 or 1, if it is 0 then make file 415,241 bytes all bits zero, if in compressed file is 1 then do the same but all ones.

I sad on gnjavi kako sam sakrio informacije

I am afraid that you are hiding information in the file system in two different ways.
First, using different file extensions to distinguish file types is very obviously using the file system to save one bit of information.
The second part is more subtle, but it relies knowing the size of the file. If you didn't know the size of the file your algorithm would fail.

A nisam jer je napisao ovo u uslovima challenga: Because the programs have to be able to handle any input data, size is of no particular advantage – there is no data to hide. i ovo: create a system to compress and then decompress any file of size 415,241 bytes.

I neće da isplati pošteno zaradjeni novac! :)






[ Nedeljko @ 25.01.2017. 19:55 ] @
Ilustruj na nekim primerima.
[ djoka_l @ 25.01.2017. 22:22 ] @
Očigledno ne razumeš dobro engleski:

Citat:
create a system to compress and then decompress any file of size 415,241 bytes. In other words, create a compressed file that is smaller than the input, then use only that compressed file to restore the original data.


Dakle, možeš da koristiš SAMO SADRŽAJ komprimovanog fajla, a ne da koristiš ime, ekstenziju ili bilo koji sadržaj koji nije deo sadržaja takvog fajla.

Citat:
Likewise, both problems are governed by one meta-rule which seeks to implement an overarching principle: the point of this is to win algorithmically, not to game the contest. I will disqualify any entry that wins through means such as hiding data in filenames, environment variables, kernel buffers, or whatever. Someone can always find a way to win with monkey business like this, but that is beside the point of the contest. No hiding data.


Drugi deo istog izazova je:

Citat:
This challenge is for the contestant who is sure that he or she has figured out a way to compress the million digit file, but finds that their program takes 100 MB of space. Okay, that’s fine, we shall first see if it can compress the file. It then must be able to correctly compress and decompress a file of the same size. Let’s say, on 1,000 different files.

To keep it simple, the files will be simple permutations of the million digit file – scrambled with an encryption system, or perhaps a random number generator, or whatever. The point is, they should have all the same numeric characteristics as the original file, just organized slightly differently.


Ovih 415,241 bajtova je nekakav slučajan broj, ako imaš algoritam. Poenta je da uz pomoć tog algoritma možeš da komprimuješ i fajl koji predstavlja milion slučajnih brojeva i to 1000 takvih fajlova.

Dakle, prvi deo, napraviti algoritam koji komprimuje SVE fajlove dužine 400k (i dekomprimuje koristeći samo sadržaj fajla) a onda isti algoritam primeniti na 1000 fajlova dužine 375MB koje će postavljač teme dati algoritmu.

[Ovu poruku je menjao djoka_l dana 25.01.2017. u 23:35 GMT+1]
[ djoka_l @ 25.01.2017. 22:31 ] @
A evo i zašto tvoj "algoritam" ne radi.

Pretpostavimo da fajl na početku ima 1-7 bitova koji se ponavljaju. Dakle, ti NE MOŽEŠ da uštediš bajt jer se fajl ujpisuje u BAJTOVIMA. Poslednji bajt ćeš morati da dopuniš nečim, recimo nulama. Kako ćeš znati koliko mesta u desno treba da šiftuješ bitove?

Primer:

Fajl počinje sa 1011 a završava se sa 00000000

Dobićeš komprimovani fajl koji počinje sa
011 a završava se isto sa 8 nula.

Koliko jedinica treba da dodaš na početak fajla? (1 do 8)
[ MajorFatal @ 26.01.2017. 01:28 ] @
Citat:
Nedeljko:
Ilustruj na nekim primerima.


Volim matematičare zato što se sažeto a opet precizno izražavaju. ŠTA da ilustrujem na nekim primerima? Dao sam link do "izazova", prepisao ceo sadržaj challenga, svoj predlog kako bi moglo da se odradi, njegov odgovor...

Ako treba pojašnjenje za predlog veoma je jednostavno: odseci vodeće bitove bilo koje da su vrednosti 0 ili 1, a kad dekompresuješ i kad pročitaš prvi bit kompresovanog fajla onda znaš koja je vrednost (0 ili1) bitova koji su odsečeni (kontra od tog prvo pročitanog) pa samo nadopuniš do dužine fajla koju se on zeznuo da da unapred, ovo ne važi samo za dva fajla onaj sa svim nulama i onaj sa svim jedinicama jer kad bi njima odsekao vodeće bitove odsekao bi ceo sadržaj fajla, pa zato za ta dva fajla posebna ekstenzija i u sadržaju dovoljno samo po jedan bit (ako je moguće) da naznači koje je vrednosti bio sadržaj originalnog fajla i onda samo napraviš ceo originalni fajl od tih bitova pošto već znaš koje je dužine potrebno da bude. Pošto je tražio da se naprvi sistem koji bi kompresovao a zatim i dekompresovao svaki (bilo koji) fajl dužine 415,241 bajtova time je zadatak ispunjen?


Citat:
djoka_l:
Očigledno ne razumeš dobro engleski:

Citat:
create a system to compress and then decompress any file of size 415,241 bytes. In other words, create a compressed file that is smaller than the input, then use only that compressed file to restore the original data.


Dakle, možeš da koristiš SAMO SADRŽAJ komprimovanog fajla, a ne da koristiš ime, ekstenziju ili bilo koji sadržaj koji nije deo sadržaja takvog fajla.


Ne razumem dobro engleski ali tu piše da mogu da koristim samo taj kompresovani fajl da restore the original data, da je hteo da kaže to što ti tvrdiš morao bi da napiše use only the content of that compressed file to restore the original data?


Citat:
Likewise, both problems are governed by one meta-rule which seeks to implement an overarching principle: the point of this is to win algorithmically, not to game the contest. I will disqualify any entry that wins through means such as hiding data in filenames, environment variables, kernel buffers, or whatever. Someone can always find a way to win with monkey business like this, but that is beside the point of the contest. No hiding data.


Citat:
“Because the programs have to be able to handle any input data, size is of no particular advantage – there is no data to hide


Pa dobro, al ovo mu više važi za prvi čelindž jer tu ima smisla da ne bi neko sakrio podatke negde pa ih onda samo isporučio tvrdeći da ih je komresovao, za drugi i nema baš mnogo smisla što i on sam kaže kompresor može biti veliki koliko hoćeš jer "there is no data to hide", tu više ne možeš da profitiraš ni ako sve moguće fajlove te veličine sakriješ u kompresor pa tvrdiš da si podatke kompresovao na samo jedan bit ili koliko god, jer sad moraš nekako da razlikuješ te pothranjene fajlove tj. da signaliziraš koji se zahteva da se restore a za to ti opet treba 2^N različitih uputstava, osim toga ne krijem podatke ni na kakav način koji bi se mogao nazvati krivenje podataka kao u primeru sa imenima fajlova gde preručuješ podatke iz fajla u ime a bez krompesije, koristim osobine fajl sistema to da, ali ne krijem nikakve podatke nigde, dokaz je da slobodno može da odabere skraćenice za ekstenzije kakve god želi, ako ja krijem nekakve podatke iz fajla to ne bi mogao :)

Drugi deo istog izazova je:

Citat:
This challenge is for the contestant who is sure that he or she has figured out a way to compress the million digit file, but finds that their program takes 100 MB of space. Okay, that’s fine, we shall first see if it can compress the file. It then must be able to correctly compress and decompress a file of the same size. Let’s say, on 1,000 different files.

To keep it simple, the files will be simple permutations of the million digit file – scrambled with an encryption system, or perhaps a random number generator, or whatever. The point is, they should have all the same numeric characteristics as the original file, just organized slightly differently.


Ovih 415,241 bajtova je nekakav slučajan broj, ako imaš algoritam. Poenta je da uz pomoć tog algoritma možeš da komprimuješ i fajl koji predstavlja milion slučajnih brojeva i to 1000 takvih fajlova.

Dakle, prvi deo, napraviti algoritam koji komprimuje SVE fajlove dužine 400k (i dekomprimuje koristeći samo sadržaj fajla) a onda isti algoritam primeniti na 1000 fajlova dužine 375MB koje će postavljač teme dati algoritmu.

[Ovu poruku je menjao djoka_l dana 25.01.2017. u 23:35 GMT+1][/quote]

Gde nadje tih 375MB duge fajlove? Ja nisam tako razumeo, on ima jedan taj random fajl dužine 415,241 bajta (random sadržaja) i ako neko tvrdi da ima algoritam koji će da kompresuje takav fajl ali ne može po chalenge 1 da zadovolji sve uslove tj. kompresor je npr. veličine 100 MB, onda će prvo da proveri da li će da uspe da kompresuje taj jedan, a ako uspe to, onda na još 1000 drugih da proveri, ali iste te dužine 415,241 bajta, gde si našao tih 375 MB?

"Dakle, prvi deo, napraviti algoritam koji komprimuje SVE fajlove dužine 400k (i dekomprimuje koristeći samo sadržaj fajla)..." Ne samo sadržaj, nego samo fajl :) : "use only that compressed file to restore the original data"
[ MajorFatal @ 26.01.2017. 01:50 ] @
Citat:
djoka_l:
A evo i zašto tvoj "algoritam" ne radi.

Pretpostavimo da fajl na početku ima 1-7 bitova koji se ponavljaju. Dakle, ti NE MOŽEŠ da uštediš bajt jer se fajl ujpisuje u BAJTOVIMA. Poslednji bajt ćeš morati da dopuniš nečim, recimo nulama. Kako ćeš znati koliko mesta u desno treba da šiftuješ bitove?

Primer:

Fajl počinje sa 1011 a završava se sa 00000000

Dobićeš komprimovani fajl koji počinje sa
011 a završava se isto sa 8 nula.

Koliko jedinica treba da dodaš na početak fajla? (1 do 8)


Pa jednu? :)

E pa vidiš ovo me zanimalo, znači mora da se skrati bar za bajt da bi moglo da se računa da je skraćeno, ne može za bit?

A što se tiče primera, ponašaj se kao postavljač kontesta pa reci unapred koliko su dugački fajlovi za koje želiš sistem koji će da ih skrati, ako bi ti rekao da želiš da skratiš sve fajlove dužine npr. 20 bita, onda bi ja znao na na osnovu dužine 19 bita da fali tačno jedan bit, a na osnovu prvog bita iz "kompresovanog" fajla (nula) znao bih da nedostaje jedinica na početku, ali ako sam dobro razumeo ne može biti fajl od 20 bita već mora ili od 16 ili od 24 jer se fajl, bilo koji,upisuje u bajtovima?

Ma znam ja da nisam nikakav chalenge osvojio, niti da je to ono što je postavljač "izazova" hteo, tema je šaljive prirode, ali možemo da pričamo...da je neki ozbiljniji čelindž da li bi ono "there is no data to hide" bilo obavezujuće za njega, ne može posle da me optužuje da sam "hide data".
[ stopnarkomaniji @ 28.07.2017. 06:01 ] @
Direktive
Citat:
use only that compressed file to restore the original data.

i
Citat:
use only the content of that compressed file to restore the original data


se svode na isto značenje.

Evo zašto:

Ako se prihvati uslov druge direktiva tada se koristi samo sadržaj fajla. Naziv fajla nije sastavni deo sadržaja fajla.

Medjutim, ako je druga direktiva u kolizija sa prvom tada je fajl kompresovan. Ali ekstenzija koju si naveo nije kompresovana.
Pošto se može koristiti samo kompresovan fajl zato se ne može koristiti ekstenzija koja nije kompresovana, sledi da se korišćenjem ekstenzije narušava prva direktiva.

Dakle i iz prve direktive sledi da se može kosristiti SAMO SADRŽAJ kompresovanog fajla!
Zato se može reći da je prva direktiva dovoljno jasno formulisana.

Budimo realni: ti si deo podataka kodirao u naziv fajla. A naziv fajla i sam fajl su zapravo dva fajla.
Koristio si komprimovan fajl dužine 415,241 bajta plus 3 bajta ekstenzije = 415,244 bajta što narušava uslov zadatka.


Još nešto: dužina fajla 415,241 bajtova nije slučajna, a autor čelendža je dao objašnjenje.