3
\$\begingroup\$

Introduction

You're an American spy during the heat of the Cold War and you've managed to intercept a Russian message. Immediately you recognise it as a code stick cipher and wrap it around a pencil. Looking at the paper on the pencil, you don't see anything. Then you try a bigger pencil, and you see it.

Challenge

You have to write a program that deciphers a code stick. As this is code golf, the shortest program wins.

You may use any English dictionaries for looking up words. Some examples of dictionaries include:

  • Querying a text file of words
  • Using an inbuilt OS dictionary
  • Querying an online dictionary (screen scraping etc.)
  • Using an external lib

All words MUST be valid English words

Your pencils

Each of your pencils has four equally sized faces and are infinitely long. You have five differently sized pencils:

Pencil 1: Shows 1 character on each face
Pencil 2: Shows 2 characters on each face
Pencil 3: Shows 4 characters on each face
Pencil 4: Shows 6 characters on each face
Pencil 5: Shows 8 characters on each face

All ciphers can be deciphered by placing the start of the paper at the top of the pencil and wrapping it down.

Examples

The following is an example of a cipher:

Hepoge slljghadso bvvbgh

This can be deciphered by wrapping it around Pencil 2:

Side 1 | Side 2 | Side 3 | Side 4
-------+--------+--------+-------
He     | po     | ge     |  s
ll     | jg     | ha     | ds
o      | bv     | vb     | gh

So now you have four combinations:

Hello , pojgbv, gehavb,  sdsgh

You can now perform a dictionary lookup and see that Hello is the only valid word. Therefore, Hello is the cracked cipher.

Note: Deciphered codes may have spaces in. Example: Hello World

Test cases

Ciphers can be inputted in any way apart from being hardcoded. The following are a few test cases. You will not be given the pencil size.

boasonespetrabbittonespongomezesray long
lsbvmii derfghthstthasinlomnrtk fg dndthugssawerpoloasefnxafqeormnaqwge padhndi mbavwgam
lipois lisptloopoolsisp lortfippinglthe asse rtedgoodcodeis the best  of enlymoolfangthe  leamingsoulsgodsingering
antidisebd sldkfdw sld sja dmddystablishjzkapxmjhavzlx dld slzbfmentariabahdjdlljagzlxbxlffnd ldnism is hdbsh spjalcpdhstd flcnda very cbd skd alsbfo kfvwfd xlconvolutehs ska ckw dlc fjzlxbckxd word  hs sla k dk skdnlcjcu dk

Any more test cases would be appreciated

Answers to the test cases

1: astronomy
2: i think therefore i am
3: is lisp the code of the gods
4: antidisestablishmentarianism is a very convoluted word

Script to generate code stick ciphers:

import string, random, math

word = input('Word:\t')
n = int(input('Pencil:\t'))
pencil = int(-((4*(17*n-77))/((n**4)-(19*n**3)+(136*n**2)-(444*n)+566)))

alpha = string.ascii_lowercase+' '
cipher = ''

side = random.randint(1, 4)
sides =['','','','']

for j in range(len(sides)):
    if j+1 == side:
        sides[j] = word
        if len(word)%pencil != 0:
            sides[j] += ' '*(len(word)%pencil)
    else:
        for k in range(math.ceil(len(word)+(len(word)%pencil))):
              sides[j]+=random.choice(alpha)

for l in range(0, math.ceil(len(word)/pencil)*pencil, pencil):
    for m in sides:
        cipher += m[l:l+pencil]

print('Cipher:\t'+cipher)
print('Side:\t'+str(side))
\$\endgroup\$
  • 3
    \$\begingroup\$ Your second test case has at least four perfectly meaningful decryptions. This question is also incomplete in that it says "You can now perform a dictionary lookup" but doesn't provide a dictionary. \$\endgroup\$ – Peter Taylor Aug 28 '14 at 16:39
  • 1
    \$\begingroup\$ The first example uses Pencil 2, not Pencil 1. \$\endgroup\$ – Ypnypn Aug 28 '14 at 21:04
  • \$\begingroup\$ The new third test case is wrong: the closest candidate decryption to the claimed one is is lisp the codeof the gods (sic). Also it's apparently not clear what the output should be. Am I correct to understand that it should be the (assumed unique) candidate decryption which doesn't contain any non-words? (See comment thread on David Carraher's answer). \$\endgroup\$ – Peter Taylor Aug 29 '14 at 11:21
2
\$\begingroup\$

Python - 219 178 172 175

First crack at it. I'm sure there's room for improvement.

edit1: After suggestions, and copying words file to local file named 'w'
edit2: Fixed a bug where it wasn't using the right number of letters per side. Added 3 chars :(

r=range 
s=raw_input()
print[a for a in(''.join(s[m:m+n]for m in r(o*n,len(s),4*n))for o in r(4)for n in(1,2,4,6,8))if not set(a.lower().split())-set(map(str.strip,open('w')))]
\$\endgroup\$
  • \$\begingroup\$ you can save 1 char by removing the space after print, i.e. print[a... \$\endgroup\$ – stokastic Aug 28 '14 at 20:18
  • \$\begingroup\$ Defining and using a synonym r=range should save a couple more characters. And similar to the morse code golf question it is shorter to load the dictionary where needed (same for raw_input), even though it might increase the computing time dramatically. \$\endgroup\$ – Falko Aug 28 '14 at 20:53
  • \$\begingroup\$ I don't think I can do the same thing with raw_input due to the fact that I use it in two places, and it loops many times. \$\endgroup\$ – Bizangles Aug 28 '14 at 22:25
  • \$\begingroup\$ This only works for single word ciphers, not with the other multi-word test cases \$\endgroup\$ – Beta Decay Sep 20 '14 at 9:37
  • \$\begingroup\$ After making sure that my dictionary had all the words (it was missing "gods" and "antidisestablishmentarianism"), this script works properly for all 4 of the test cases. Not sure why you thought it wasn't working, maybe you can explain? \$\endgroup\$ – Bizangles Sep 20 '14 at 14:56
1
\$\begingroup\$

Mathematica 270 230 251


This now requires that all parsed words be found in a dictionary.

f@q_:=
Module[{c=Characters@q,wd,u=DictionaryLookup},
j@d_:=Union[u@d,u[ToLowerCase@d],WordData@d];
Flatten@Select[Flatten[Table[
StringSplit[""<>Flatten@#]&/@Transpose@ArrayReshape[c,{Round[Length@c/(4 m)],4,m},""],{m,{1,2,4,6,8}}],1],!MemberQ[j/@#,{}]&]]

Test Cases

f["boasonespetrabbittonespongomezesray long"]
f["Hepoge slljghadso bvvbgh"]
f["lsbvmii derfghthstthasinlomnrtk fg dndthugssawerpoloasefnxafqeormnaqwge padhndi mbavwgam"]

{"astronomy"}
{"Hello"}
{"i", "think", "therefore", "i", "am"}

\$\endgroup\$
  • \$\begingroup\$ I think you're probably supposed to filter the possibilities to only the ones which don't contain non-words rather than to the ones which do contain words, but the spec could certainly be clearer. \$\endgroup\$ – Peter Taylor Aug 29 '14 at 10:07
  • \$\begingroup\$ Peter T, Yes, but the non-word may actually be a legitimate word that the dictionary for one reason or another does not recognize. In such a case, it's better to return the words that are identified as valid. \$\endgroup\$ – DavidC Aug 29 '14 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.