179 - Code Breaking

[abishek]

I am trying to solve this problem code breaking.... and there are a few hurdles i'd like to cross




the input says that

There is no implication that n is a

multiple of k.

so does this imply that there may be some letters lost.

for example if the permutation was

3 2 1 for three characters



('?' replaces space for clarity)
plain text: abcd

cypher text: cba??d



so will the input contain

abcd

cba?



please clarify.

[Dominik Michniewski]

Plaintext and cyphertext should have equal length.

I also try to solve this problem but got WA....

Could anyone help me, and post / send me some IO ? I think, that my algorithm is correct (but maybe not very efficient ) ...

Best regards
DM

[junbin]

If n is not a multiple of k, then the extra characters are simply chopped off.

eg:

Entire string:

This is a test!!

Encrypted string: (using mapping 4231)

shiT is e ta!t!s

Total length: 16, k = 4.

If n = 14 however, then the input given will be:


This is a test
shiT is e ta!t

The last 2 characters are simply chopped off. ? will not be used in the input. However, in your output, if there are missing characters, you should use ?.

[Dominik Michniewski]

I think, that I correct implement all this things (but I could be wrong ...)
junbin, Could you post more IO on board or mail it to me ?

Best regards
DM

[junbin]

I made a simple random data generator (source code in QB below).

input:

Code: Select all

nphhuatvsbkwuj
jwnuutbpvahskh
abcdefghijklmnopqrstuvwxyz
vvpzxfszg
xvgsvfpzz
abcdefghijklmnopqrstuvwxyz
bhjhyzkhe
hkhyhjzbe
abcdefghijklmnopqrstuvwxyz
clxgujhxqqlc
hqcqculgjxxl
abcdefghijklmnopqrstuvwxyz
khbgzbkjme
zbjbkekghm
abcdefghijklmnopqrstuvwxyz
ltpvafbcidanro
ntvdbfpaoclrai
abcdefghijklmnopqrstuvwxyz
ficpeyclhwt
plcfiywceht
abcdefghijklmnopqrstuvwxyz
bmfwptyioc
ywcbotfmpi
abcdefghijklmnopqrstuvwxyz
daioxnkwvrszimks
iwrmvnsozkksadxi
abcdefghijklmnopqrstuvwxyz
fpjwmertpuev
jvfpuerwmtpe
abcdefghijklmnopqrstuvwxyz
ofmttkxtcqsa
ktmaqttcfxos
abcdefghijklmnopqrstuvwxyz
qjceclyo
eojccqyl
abcdefghijklmnopqrstuvwxyz
zoxrlsbtsmef
rmzbesxftslo
abcdefghijklmnopqrstuvwxyz
dyuskaeenkc
sekkycuande
abcdefghijklmnopqrstuvwxyz
wpjkwpyni
njpkwwiyp
abcdefghijklmnopqrstuvwxyz
kvtlckisiudpyg
gvysipktdkculi
abcdefghijklmnopqrstuvwxyz
nhpfcxcqxg
gqfccxhnpx
abcdefghijklmnopqrstuvwxyz
qcfsnezm
qsfzmecn
abcdefghijklmnopqrstuvwxyz
djezwps
jedspwz
abcdefghijklmnopqrstuvwxyz
ouoffjoinlo
oooolnifjfu
abcdefghijklmnopqrstuvwxyz
saiscchk
ciakscsh
abcdefghijklmnopqrstuvwxyz
srkyqnfptlx
ypxkqsnltfr
abcdefghijklmnopqrstuvwxyz
nuwcokbls
ocslwkunb
abcdefghijklmnopqrstuvwxyz
adkooubkb
kuobdbkoa
abcdefghijklmnopqrstuvwxyz
ebgtyiruaumfpx
xaeupbfgyrmtiu
abcdefghijklmnopqrstuvwxyz
kntlibkotp
ktlobitkpn
abcdefghijklmnopqrstuvwxyz
yvfegyggs
yggvsegyf
abcdefghijklmnopqrstuvwxyz
jfpqdbqvqlem
mqqbqvjlepfd
abcdefghijklmnopqrstuvwxyz
jktlsnehczhqhw
sqtnjchhkelzwh
abcdefghijklmnopqrstuvwxyz
vopexipptsrtgono
xpiosrpvtogpeotn
abcdefghijklmnopqrstuvwxyz
lkisfbxblttvfm
ftfxsivbltlmkb
abcdefghijklmnopqrstuvwxyz
yiqjjiffl
iifjfyqjl
abcdefghijklmnopqrstuvwxyz
phvxnkageq
qvhepkangx
abcdefghijklmnopqrstuvwxyz
kvgrkvl
vvklkrg
abcdefghijklmnopqrstuvwxyz
nqleqpwjbnbjlhz
nbbjqlqzpwenlhj
abcdefghijklmnopqrstuvwxyz
oozygvukq
gyoqoukzv
abcdefghijklmnopqrstuvwxyz
ulcmobkddizphk
kudbkmcidzolph
abcdefghijklmnopqrstuvwxyz
owkpjbcddt
kwodtbdcjp
abcdefghijklmnopqrstuvwxyz
ihrkjfwdkposd
jiodkrsfdwhpk
abcdefghijklmnopqrstuvwxyz
dxausgymskgp
ygskdaxugpsm
abcdefghijklmnopqrstuvwxyz
mgwbdzvvzgrqzkb
kwdgvzbvzrbqgmz
abcdefghijklmnopqrstuvwxyz
jkjqele
ekjlejq
abcdefghijklmnopqrstuvwxyz
zhmxxnwokvsxdur
uxsvnkwhxxrdmoz
abcdefghijklmnopqrstuvwxyz
luicwpwvtybvfhbx
xctpiwuvbhlvfywb
abcdefghijklmnopqrstuvwxyz
zkuupjprpb
pzupjpbkru
abcdefghijklmnopqrstuvwxyz
uadrgvf
agvrufd
abcdefghijklmnopqrstuvwxyz
bxmkygobvm
gkxvmyobmb
abcdefghijklmnopqrstuvwxyz
vothbqnrjqe
qhjoqvretbn
abcdefghijklmnopqrstuvwxyz
rzcubzz
bzrzzuc
abcdefghijklmnopqrstuvwxyz
dhaixgsv
dsgahxiv
abcdefghijklmnopqrstuvwxyz
yfhpgicaytl
igtpahfycyl
abcdefghijklmnopqrstuvwxyz
ikzsmvidxnupizj
msizkjxpnziuidv
abcdefghijklmnopqrstuvwxyz
bbvzarydjmxe
mdvberjbzxay
abcdefghijklmnopqrstuvwxyz
ehtwgjwwkpe
etegwjkwphw
abcdefghijklmnopqrstuvwxyz
fzerxhgut
rzhfxtueg
abcdefghijklmnopqrstuvwxyz
agybwcsgx
acwxbgsgy
abcdefghijklmnopqrstuvwxyz
ulzdrstmzwer
dezrumlwszrt
abcdefghijklmnopqrstuvwxyz
vyfdsviwujpj
ivwjfyjdvsup
abcdefghijklmnopqrstuvwxyz
zkhrgsibyhrz
gsihhzyrzkbr
abcdefghijklmnopqrstuvwxyz
ishidim
midsiih
abcdefghijklmnopqrstuvwxyz
teyibhqewel
lbeieqethwy
abcdefghijklmnopqrstuvwxyz
jhtgspeyvrbm
hvrpjeymgtbs
abcdefghijklmnopqrstuvwxyz
qrdryuydhsgy
ysgrhqyudryd
abcdefghijklmnopqrstuvwxyz
jpajscgbvfu
ubsgpjjavcf
abcdefghijklmnopqrstuvwxyz
vmlqrzaobpe
zreabmpovql
abcdefghijklmnopqrstuvwxyz
xmzazwhfl
hzlmwxfaz
abcdefghijklmnopqrstuvwxyz
ccjbzzoaqtk
ocqjakztbzc
abcdefghijklmnopqrstuvwxyz
swvrhlpbdygwpf
pvhsblypfgwdrw
abcdefghijklmnopqrstuvwxyz
ykhysymiu
ykmysuhyi
abcdefghijklmnopqrstuvwxyz
zrvmiwpioaw
iprvozwaiwm
abcdefghijklmnopqrstuvwxyz
vjlvvqkdrd
vvkvrqljdd
abcdefghijklmnopqrstuvwxyz
zijzhggrny
hgjizygrzn
abcdefghijklmnopqrstuvwxyz
phmivswfcmdemvru
pvdummmcrwfisveh
abcdefghijklmnopqrstuvwxyz
dxyjzkrojmtrnaqx
koqjrytjradmznxx
abcdefghijklmnopqrstuvwxyz
qvigdvjpgk
givqdkgpvj
abcdefghijklmnopqrstuvwxyz
eqngcrdeaefmr
ergfrcqaenedm
abcdefghijklmnopqrstuvwxyz
csvjesqxvfx
fscvesjvxqx
abcdefghijklmnopqrstuvwxyz
lcopxmg
gcpmoxl
abcdefghijklmnopqrstuvwxyz
ucfbgkspx
pksxcfbgu
abcdefghijklmnopqrstuvwxyz
idnchixwfcjtyq
xcntjdchifwqyi
abcdefghijklmnopqrstuvwxyz
ijwvvvsnkqcfubj
icnfvsbukvjqvwj
abcdefghijklmnopqrstuvwxyz
nsbirsvqbrxzq
qxbbsvirsrqnz
abcdefghijklmnopqrstuvwxyz
rulbluonvnwjd
unllrnowdvjub
abcdefghijklmnopqrstuvwxyz
pqfwjoadvlu
opwqjdvufla
abcdefghijklmnopqrstuvwxyz
muvxlgiuw
ulxvumwig
abcdefghijklmnopqrstuvwxyz
ryehwztbigactrxd
xachibrtrgdtweyz
abcdefghijklmnopqrstuvwxyz
nftrzjavunghc
ugnnczvjfthar
abcdefghijklmnopqrstuvwxyz
mjjittqkcjfrkf
cftfkjtjijrmqk
abcdefghijklmnopqrstuvwxyz
vxqtxqvgdubv
xqqxvuvbgdtv
abcdefghijklmnopqrstuvwxyz
wzqyshcsmfegu
uyqwschzmegsf
abcdefghijklmnopqrstuvwxyz
xtwvnkvrfzi
rzktvnfivwx
abcdefghijklmnopqrstuvwxyz
tyvtmdjzqmc
mtmvyzctdjq
abcdefghijklmnopqrstuvwxyz
odjkynpvthbkccl
ktdnhbjcvpoklcy
abcdefghijklmnopqrstuvwxyz
jxygrmayaesstnq
rtaasxmgyyjqnes
abcdefghijklmnopqrstuvwxyz
utboalr
autorlb
abcdefghijklmnopqrstuvwxyz
ggxwmmppuh
wmpxmggpuh
abcdefghijklmnopqrstuvwxyz
trwqrgmyqdwbu
rrwdugmqwybtq
abcdefghijklmnopqrstuvwxyz
egnatlfibbbyb
betaibgyfnlbb
abcdefghijklmnopqrstuvwxyz
neuzbcvuiqez
znzqvueueicb
abcdefghijklmnopqrstuvwxyz
rqazxgmwlzfwcj
mzjwfqlgrzwxca
abcdefghijklmnopqrstuvwxyz
#

output:

Code: Select all

chkndjfilgmbeaqvy?rxtwzu?pso
beghafdicknpqjomrltwyzsxv?u
hafcdgbepinklojmxqvstwru?y????z?
cgjhfiakbdleosvtrumwnpxq??????y?z???
eibhadgcjfoslrknqmtpy?v?ux?w?z
kbgchfejndmaliypuqvtsx?r?ozw
decaifhbjgnomksprltqxywu?z?v??
dhgbifajecnrqlspktomx??v?zu?yw
nmahofjbecgipdkl??qx?vzruswy?t??
cdahifgjkelbopmtursvwqxn??y????????z
kicbfajgheldwuonrmvstqxp???z?y??????
fcdaehgbnklimpojvstquxwr???y???z
clgakfdijbehoxsmwrpuvnqt???y?????z??
jegachbkidfuprlnsmvtoq???wy?x??z?
ecbdfihagnlkmorqjpwutvx?zsy
gbhmkjednlifcaupv?yxsr?zwtqo
hgicdfebjarqsmnpoltk???wxzyv?u
agcbhfdeiokjpnlmqwsrxvtuy??z????
cabgfedjhinmlkqoputsrxvw??zy
akbhjicgfedlvmsutnrqpow?x???y???z
ecbgafhdmkjoinplusrwqvxt??z?y???
fkdaegjbihcqvolprumtsn??zw???x??y
hgebafidcqpnkjormlzywtsx?vu
ieachbdgfrnjlqkmpo?wsuztvyx
cfhlimjdbnkgeaqtvzw?xrp?yuso
ajbcfehdgiktlmpornqsu?vwzy?x??
adifbhcgejmrokqlpnsv?xtzuyw
gkjbldcfehiaswvnxporqtum???z???????y
eickadjgflhbquowmpvsrxtn????y??????z
hdbmacgliefokjpnxtr?qsw?yuv??z??
imfeahdnkbjgclw?tsovr?ypxuqz
fagdhbceniolpjkmvqwtxrsu?y???z??
ecbjhfgidaomltrpqsnkywv??z??xu
cagfebdjhnmlikqoutsprxv??zwy
aefkgijdblcomnhptuzvxysq?r???w
cehbaifgdlnqkjropmuwzts?xyv
blgfkdacihjmnepzutyroqwvx??s
cbajifhdgemlktsprnqowvu??z?x?y
bkfeahjdmlcgioxsrnuwqzyptv
egfhcbalkdijqsrtonmxwpuv?????zy?????
ndbgcfehimjloak?sqvrutwx?y??pz
cbfgadejimnhklqptuorsxw??vyz
ohmbiegnfdcjlak?w?qxtv?usry?pz
kgebfdohcnilmjpa?wurvt?xs?y??z?q
bhcjaedifglrmtkonspqv?w?uyx?z?
eagdbcflhnkijmsourpqtzv?ywx?
hcebfagjdirmolpkqtns?wyvzu??x?
fdibjakgcehqotmulvrnps?z?x?w??y??
cbgfadejinmhklqputorsxw??vyz
aedgfcbhlknmjiosrutqpvzy??xw
hgfdbaiejcrqpnlksotm??zxvu?y?w
cedbaokngilhmjfrtsqp?z?vx?w?yu
dhcikflbgajeptouwrxnsmvq???????z?y??
ajbedfhkgiclumpoqsvrtnw?x?z?????y
dbhaecigfmkqjnlrpovtzswu?yx
afiecbghdjornlkpqmsx?wutyzv
egcadilfjhbkqsompuxrvtnw???y??????z?
bfehjiackdlgnrqtvumowpxsz?????y?????
fjdhabckgelirvptmnowsqxu????yz??????
bdgecfaiknljmhprusqtowy?zx?v
hckdbifejgasnvomtqpurl?y?zx?????w
eajildfgbckhqmvuxprsnowt?y??????z???
fdijahglebckrpuvmtsxqnow????y????z??
fehgcjdbikaqpsrnuomtvl????y?zx??w
ifkjbadhegctqvumlosprn????xwz???y
fdbhieagcomkqrnjplxvtz?wsyu
bkdigjaechfmvotrulpnsqx?z???w?y??
dkbmcfaelgjnhiryp?qtoszux?vw
abgdehcifjkpmnqlrostyvwzu?x
fcdkagbiehjqnovlrmtpsu?yz?w?x????
ahgbdfciejqpkmolrnszytvxu?w
edciabghjfonmsklqrtpyxw?uv???z
apelbmjkhfcognidq?u?r?z?xvs?w?yt
kofdmaebhlginjcz?us?ptqw?vx?yr
dcbaeijhgfnmlkostrqpxwvuy????z
agjcfblihkdmentwpsoyvuxqzr
cbdgefjihamlnqoptsrkwvx?yz???u
gbecfdaniljmkhupsqtro?wzx?yv
iefghbcadrnopqkljm?wxyztusv
ifcbhnakjgedmlwtqpv?oyxusr?z
aknejmfcilbdhgoy?sx?tqwzprvu
lecghifadjbmkyrptuvsnqwozx
eacmdlgbjfhkirnpzqytowsuxv
bdiceakfgjhmotnplvqrusxz?y?w?????
fadcbihegojmlkrqnpxsvut?zwy
gondmphfejbcliakw??t??xvuzrs?yq?
cijmfhlgadbkepvwzsuytnqoxr
lfhicgmeajbkndztvwqu?soxpy?r
eabkdcgijfhplmvonrtuqs?wx?zy?????
dhcbegflimjkaquportsyvzwxn
kdjefciagbhvoupqntlrms?z???y?w?x?
bedhaijfkcgmposltuqvnrx?z?w????y?
kcgaodjibeflhnmzrvp?syxqtu?w??
kfihagcjdneobmlzuxwpvrys?t?q??
bcgdafeijnkhmlpqurotswx?yv?z
fgdabecmnkhiljturopsq??yvwzx
lachbfgjmdikeynpuostwzqvxr
bgjdckieaflhnsvpowuqmrxtz???????y???
bgfalkehjdicnsrmxwqtvpuoz??y????????
ifnblhadgjekmcwt?pzvoruxsy?q

Data generator:

Code: Select all

OPEN "Data.in" FOR OUTPUT AS #1

FOR i = 1 TO 100
  temp$ = ""

  n = INT(RND * 10) + 7
  FOR j = 1 TO n
    temp$ = temp$ + CHR$(INT(RND * 26) + ASC("a"))
  NEXT j

  work$ = temp$
  temp2$ = ""
  FOR j = 1 TO n
    x = INT(RND * LEN(work$) + 1)
    temp2$ = temp2$ + MID$(work$, x, 1)
    work$ = LEFT$(work$, x - 1) + MID$(work$, x + 1)
  NEXT j

  PRINT #1, temp$
  PRINT #1, temp2$
  PRINT #1, "abcdefghijklmnopqrstuvwxyz"
NEXT i



PRINT #1, "#"

CLOSE

Slightly harder data set (not random)

Code: Select all

aaaaabbbbbcccccdddddeeeeefffff
aaaabacbbbcbddccdceeededfffeff
1234567890
aaaaabbbbbcccccdddddeeeee
aaaabacbbbcbddccdceeededf
1234567890
aaaaabbbbbcccccddddd
aaaabacbbbcbddccdcee
1234567890
aaaaabbbbbccc
aaaabacbbbcbd
1234567890
aaaaabbb
aaaabacb
1234567890
aaaaabb
aaaabac
1234567890
#

output:

Code: Select all

4632150?987?
4632150?987?
34621590?87?
234615890?7?
2314658970??
2143658709

NOTE: Only the first 2 has a definite answer. From number 3 onwards, there are multiple answers. My code gives the first answer it finds, but since the question states that there will always be a definite answer, you may not want to test for these.

[Dominik Michniewski]

Thanks junbin for this input - I try to check it with my code
But I thought, that any two strings which we can use to find permutation and which have duplicate letters makes answer indeterminate

Best regards
DM

PS> I write message if I got Accepted on this problem

[junbin]

Thanks junbin for this input - I try to check it with my code
But I thought, that any two strings which we can use to find permutation and which have duplicate letters makes answer indeterminate

Best regards
DM

PS> I write message if I got Accepted on this problem

does not make the answer indeterminate... look at my aabbcc, etc. example.. it's clearly solvable.

[Dominik Michniewski]

My code gets WA at judge system , but it produce the same output as you post junbin ...
I don't know what I'm doing wrong
Can I send you my code ?

Best regards
DM

[junbin]

There's not much point for you to send your code to me.. since I have very little time to check it.. (university semester just started).

Anyway, here are some suggestions:

1) Make sure you do not check overbounds (ie: If it is length n, check to n'th character, not n-1 or n+1).

2) Be careful of extra characters (ie: n is not a multiple of k)

3) Ensure that you check for the special case where k = n

4) Ensure that you check for the special case where k = 1 (ie: no "normal" mapping)

5) When you do the mapping, remember to add in '?'. In particular, be careful of n = 100, k = 20 and the 3rd ciper text only having 1 character.

[Dominik Michniewski]

OK junbin
I got Acc with a little help from little joey

I realize that only one thing which is to consider is:
for strings with several identical characters one after one we must get last of them to mapping ... so:
aaaabbbb
aaabbbba
creates mapping like this:
43287651
but I still think, that mapping 12356784 is still valid for this problem ...
If I'm wrong, could anyone tell me what I'm missing in problem specification ?

Best regards
DM

[little joey]

Dominic:

If more than one periodic permutation could have mapped the plain text to the cyphertext1, then apply the periodic permutation that has the smallest value for k. There will never be more than one shortest permutation function that matches the data.

In your example the smallest value for k is 8, but there are many permutation functions that match the data. According to the problem description, there will be no such cases in the input! (This implies that we need no ambiguity checks, which makes the program easier.)

Consider this example:

Code: Select all

aaaabbccuvwxuvwx
aaaaccbbxwuvxwuv

Here we can find permutation functions with lengths 4,8 and 16. Testing length 4:
- the permutation "aaaa" -> "aaaa" leaves all possible functions valid (1234, 1243, 1324, etc, total of 24);
- the permutation "bbcc" -> "ccbb" limits us to 4 functions (3412, 3421, 4312 and 4321);
- the permutation "uvwx" -> "xwuv" gives only one function: 4312,
- the last permutation is the same as the third.

The answer is unique: 4312, and is compatible with all permutations found.

Now consider:

Code: Select all

aaaabbccuvwxklmn
aaaaccbbxwuvnmlk

Here the first three permutations are the same as in the example above. But the fourth is not; the only valid function for "klmn" -> "nmlk" is 4321, which is not compatible with the first three. Therefore k=4 has no valid function.

Now we test length 8, and by the same reasoning we find one unique function 43128765, which is the answer.

Sorry for this lengthy reply, but I hope it clears matters.

-little joey

PS
junbin's examples are, as far as I checked them, for the most part highly ambiguous and therefore invalid (apart from wasting space on the board). I'd sugest he removes them.

[Dominik Michniewski]

Thanks lilte joey to explaining me this problem
I understand now all

best regrads
DM

[Kallol]

well , I was trying to solve the problem . My programme does not produce the right answers of Jubins Inputs but as Little Joe said, those inputs are not possible, I tried my code with the rest datas. have another question about this problem statement. How can the 3rd sample output be correct in the problem statement.

the input was : abc
the cypertext1 is : bca

so, here k=3
so it changes 123->231

cypertext2 was : abcd
after necessary padding it will be : abcd??
we break it into 2 parts of 3 letters of : "abc" and "d??"
Now,
clearly the 1st part is a copy of the given plaintest to cypertext1. So, 1st part should be changed to bca and with this process the second part would be ??d . But the output is, "cab?d?"

If the sample output is correct, then I am understanding something wrong here. Is there anyone to help me?

[mf]

clearly the 1st part is a copy of the given plaintest to cypertext1. So, 1st part should be changed to bca

It's the other way round. If cyphertext2 contained "bca" (copy of cyphertext1), it would be changed to "abc" (plaintext).
You have to decrypt cyphertext2, but you're encrypting it.

[Kallol]

Oh yea !

Thank you mf . Now I have got accepted. I was just thinking in oposit way. Thanks a lot.