DevProTalk

DevProTalk (http://www.devprotalk.com/index.php)
-   Programiranje (http://www.devprotalk.com/forumdisplay.php?f=23)
-   -   Substitution Cipher (http://www.devprotalk.com/showthread.php?t=10439)

webarto 15. 10. 2011. 03:12
Substitution Cipher
 
Vozdra :)

Mali zadatak, dešifrovati dati input ako su poznate riječi koje su korištene u šifrovanju. Svaki novi red koristi druge zamjene (substituciju). Znači jedan red = jedna pravila itd... Programski jezik nije bitan. Ovo je pre-interview zadatak za Facebook, ja slučajno otvorio, i nemam više pravo tako da just for fun :)

Input:

Kôd:
//dict
hello
there
yello
bob
tom
mabel
says
hi
secret
the
is
to
smile
//secret
45161 01223
x2x 3453 6k
x8z yz67zx 5y x4 y352z
Output:

Kôd:
45161 01223 = there yello
x2x 3453 6k = bob says hi
x8z yz67zx 5y x4 y352z = the secret is to smile

jablan 15. 10. 2011. 09:05
Proklet bio... :)

Kôd:
dict = [
'hello',
'there',
'yello',
'bob',
'tom',
'mabel',
'says',
'hi',
'secret',
'the',
'is',
'to',
'smile',
]
secrets = [
'45161 01223',
'x2x 3453 6k',
'x8z yz67zx 5y x4 y352z',
]

p Hash[secrets.map{|secret|
  words = secret.split ' '
  [secret, dict.permutation(words.length).find{|perm|
    next unless perm.map(&:length) == words.map(&:length)
    match = [words, perm]
    chars = match.map{|e| e.join.chars.to_a}
    next unless chars.map{|e| e.uniq.length}.inject(&:==)
    pairs = chars.inject(&:zip)
    Hash[pairs] == Hash[pairs.map(&:reverse)].invert
  }.join(' ')]
}]
#=> {"45161 01223"=>"there yello", "x2x 3453 6k"=>"bob says hi", "x8z yz67zx 5y x4 y352z"=>"the secret is to smile"}
Mora da može i prostije...

cvele 15. 10. 2011. 10:13
Moze objasnjenje za nas sa jeftinijim ulaznicama ?
Kada dodjes do dela niza sa stringovima iste duzine, recimo 5, kako se odlucujes sa neki od njih ?

jablan 15. 10. 2011. 10:52
Evo malo izmenjene verzije, sa komentarima.

Kôd:
p Hash[secrets.map{|secret|
  words = secret.split ' ' # niz reci u secret frazi
  [secret, dict.permutation(words.length).find{|perm| # za sve kombinacije reci iste duzine kao secret fraza
    match = [words, perm]
    #=>[["x8z", "yz67zx", "5y", "x4", "y352z"], ["the", "secret", "is", "to", "smile"]]
    next unless match.map{|e| e.map(&:length)}.inject(&:==) # eliminisemo sve koje nemaju iste duzine reci kao secret fraza
    chars = match.map{|e| e.join.chars.to_a} # sada ih posmatramo samo kao nizove karaktera
    #=>[["x", "8", "z", "y", "z", "6", "7", "z", "x", "5", "y", "x", "4", "y", "3", "5", "2", "z"], ["t", "h", "e", "s", "e", "c", "r", "e", "t", "i", "s", "t", "o", "s", "m", "i", "l", "e"]]
    next unless chars.map{|e| e.uniq.length}.inject(&:==) # eliminisemo sve koji nemaju isti broj razlicitih slova
    pairs = chars.inject(&:zip) # parovi slova na istim pozicijama
    #=>[["x", "t"], ["8", "h"], ["z", "e"], ["y", "s"], ["z", "e"], ["6", "c"], ["7", "r"], ["z", "e"], ["x", "t"], ["5", "i"], ["y", "s"], ["x", "t"], ["4", "o"], ["y", "s"], ["3", "m"], ["5", "i"], ["2", "l"], ["z", "e"]]
    Hash[pairs] == Hash[pairs.map(&:reverse)].invert # ovo je malo trickish, videti u tekstu
  }.join(' ')]
}]
Poslednja provera pravi dve hashmape, jednu od karaktera sifra -> original, drugu od karaktera original -> sifra, pa "obrne" ovu drugu i uporedi je sa prvom. Da ima nekih neslaganja, neki parovi se ne bi poklapali.

webarto 15. 10. 2011. 13:39
Svaka čast, primljen si, iskreno sam i očekivao da se ti javiš :)

Naći riječi iste dužine, naći poklapanje karaktera, pretpostaviti da su prva poklapanja tačna, uporediti sa drugim šifrovanim riječima, itd...

Napisati sve to poslije 24h rada, fail :D

Zašto imam osjećaj da za ovo u PHP treba dosta više codea? :)

PHP kôd:
function ass_u_me($string_1, $string_2)
{
    $strlen = strlen($string_1);
    
    if($strlen != strlen($string_2))
        return false;
        
    for($i = 0; $i < $strlen; $i++)
    {
        $return[$string_1[$i]] = $string_2[$i];
    }
    return $return;
} 

jablan 15. 10. 2011. 15:54
Zapravo, trebalo bi da ima i jednostavniji način:

Kôd:
Šifra S: | 4 | 5 | 1 | 6 | 1 |
------------------------------
Fraza P: | t | h | e | r | e |
Fraza P odgovara šifri S ako su:
- broj jedinstvenih karaktera u šifri S
- broj jedinstvenih karaktera u frazi P
- broj jedinstvenih parova karaktera (s,p)
isti.

jablan 15. 10. 2011. 21:30
Ako nekog interesuje kako izgleda rešenje u Clojure-u (možda ima gluposti jer mi je prvi program, ako neko ima iskustva neka me ispravi):

http://ideone.com/6EDOI

webarto 15. 10. 2011. 23:10
Možeš li u PHP? :)


Vreme je GMT +2. Trenutno vreme je 13:38.

Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.

Mišljenja, saveti, izjave, ponude ili druge informacije ili sadržaji nastali na Sajtu su vlasništvo onoga ko ih je kreirao, a ne DevProTalk.com, tako da ne morate da se oslanjate na njih.
Autori poruka su jedini odgovorni za ovakve sadržaje. DevProTalk.com ne garantuje tačnost, kompletnost ili upotrebnu vrednost informacija, stavova, saveta ili datih izjava. Ne postoje uslovi pod kojima bi mi bili odgovorni za štetu ili gubitak koji je posledica bilo čijeg oslanjanja na nepouzdane informacije, ili bilo kakve informacije nastale kroz komunikaciju između registrovanih članova.
Web sajt može sadržavati linkove na druge web sajtove na Internetu ili neke druge sadržaje. Ne kontrolišemo niti podržavamo te druge web sajtove, niti smo pregledali bilo kakve sadržaje na takvim sajtovima. Mi nećemo biti odgovorni za legalnost, tačnost ili prikladnost bilo kog sadržaja, oglasa, proizvoda, usluga ili informacije lociranim na ili distribuiranih kroz druge web sajtove, niti za bilo kakvu štetu nastalu kao posledica takvih informacija. DevProTalk.com drži i čuva druga prava vlasništva na web sajtu. Web sajt sadrže materijale zaštićene copyright-om, zaštitne znakove i druge informacije o pravu vlasništva ili softver. Članovi mogu poslatu informacije zaštićene pravima vlasništva njihovih nosilaca i ona ostaju zaštićena bez obzira da li su oni koji prenose te informacije to naveli ili ne. Osim informacija koje su u javnom vlasništvu ili za koje dobijete dozvolu, nemate pravo da kopirate, modifikujete ili na bilo koji način menjate, objavljujete, prenosite, distribuirate, izvršavate, prikazujete ili prodajte bilo koju informaciju zaštićenu pravima vlasništva. Slanjem informacija ili sadržaja na bilo koji deo DevProTalk.com, Vi automatski dozvoljavate i predstavljate garanciju da imate pravo da dozvolite DevProTalk.com ili članovima DevProTalk.com bespovratnu, kontinualnu, neograničenu, globalnu dozvolu da koriste, kopiraju, izvršavaju, prikazuju i distribuiraju takve informacije i sadržaje i da iz takvih sadžaja koriste bilo koji deo u bilo koje svrhe, kao i pravo i dozvolu da koriste gore navedene sadržaje. Svi zaštitni znakovi (trademarks), logotipi, oznake usluga, firme ili imena proizvoda koji se pominju na ovom web sajtu su vlasništvo kojim raspolažu njihovi vlasnici.