PDA

Pogčedajte punu verziju : Substitution Cipher


webarto
15. 10. 2011., 04:12
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:

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

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

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


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., 11: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., 11:52
Evo malo izmenjene verzije, sa komentarima.


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., 14: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? :)

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., 16:54
Zapravo, trebalo bi da ima i jednostavniji način:


Š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., 22: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
16. 10. 2011., 00:10
Možeš li u PHP? :)