2
\$\begingroup\$

Problem:

Take input text like this: (all input should be considered strings)

 Upi djpi;f ytu yu[omh pmr yp yjr ;rgy.

And figure out if it was offset left or offset right (on a standard qwerty keyboard as pictured below).

Also only keys that output something to the screen are considered valid, so these keys: caps, shift, tab, enter, delete(backspace), should not be considered when doing this challenge.

qwerty keyboard

Once you have figured out what the offset is, print out the offset and the correct text.

For example the above input would have this output

 text: You should try typing one to the left.
 offset: right

Your program has to 'know' that the sentence is correct before it prints out. (so no asking for user verification). Also no using libraries (should be a given).

All input will begin with a capital and end in a period (the period will not be offset left or right so you won't be able to use it to determine the offset.)

Another example:

U kujw oeife'nnubf xibrwara.

I like programming contests. 

Some input samples to use:

 X'ra 'bs sifa 'ew ai o'aaw.
 Yjod vpmysod sm stnoysto;u ;pmh eptf.
 Rgw x'r ;b rgw g'r qwbr iyr ri v'r.
 Og upi vtrsyr s d,s;; fovyopmstu pg yjr ,pdy vp,,pm rmh;odj eptfd yjrm upi vsm vjrvl upit piy[iy gpt yjpdr eptfd' yjr eptf ayjra smf yjr eptf asmfa str imowir ejrm pggdry ;rgy smf pggdry tohjy. //<< don't put this deciphered text in your answers. 

And bonus option: write your program to be able to handle the input switching offsets.

Example above with switching offset:

Upi djpi;f ytu yu[omh ibw ri rgw kwdr.

text: You should try typing one to the left. 
offset: right -> index[21], then left.

Winning criterion:

  • Faster code gets more points (out of 10) so O(logn) would score more then O(n^2) solutions (obviously).
  • Elegance (out of 20) There is a very elegant and simple solution to this problem. The closer you get to the simple solution the higher your score. (bonus +5 if you think of something simpler then my solution).
  • This is not a code golf, but concise readable code will be scored (out of 10).
  • Bonus is all or nothing for 5 extra points.

So A perfect score would be 40 but you could score up to 50 if you get both bonuses.

bonus +2 if you read all instructions

\$\endgroup\$

closed as off-topic by Johannes Kuhn, flornquake, J B, Paul Prestidge, Toto Sep 23 '13 at 12:20

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Johannes Kuhn, flornquake, J B, Paul Prestidge, Toto
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
  • 6
    \$\begingroup\$ The bonus option is clear cut, but it's the only part of the scoring system which is. The speed criterion could be made objective; concision could be made objective; readability is always going to be up for debate (especially in a context in which languages which don't have "official" style guides are used); and elegance is a dead-cert source of arguments (not to mention that if you get hit by a bus no-one will be able to know which answers would qualify for the bonus). \$\endgroup\$ – Peter Taylor Apr 30 '13 at 15:26
  • 1
    \$\begingroup\$ The easiest way to fix the criteria is to handle the speed one by giving a large test case with a generous time limit (e.g. "Must handle this 10k input in a minute"; generous to account for varying CPU speeds); and then to make it pure code-golf on the basis that elegant answers tend to be short. If you're really worried about readability then discount unnecessary whitespace and count names as 1 unit each unless they can't be changed without breaking the program. \$\endgroup\$ – Peter Taylor Apr 30 '13 at 21:12
  • 1
    \$\begingroup\$ This is a very interesting problem, but I agree that the scoring is weak. For a problem like this, everyone should know what their score is and what the other scores are. Your input as a judge (with criteria that are partially unknown to us) makes the results unclear. \$\endgroup\$ – user7486 May 1 '13 at 8:59
  • 1
    \$\begingroup\$ Is there any possibility that there will be a full stop mid-sentence? As in a comma that has been shifted right. \$\endgroup\$ – Volatility May 3 '13 at 7:10
4
\$\begingroup\$

Python

The original version didn't deal with punctuation too well, so here's a revised version.

r = dict(zip('\\qwertyuio\'asdfghjkl;/zxcvbnm|:"?', 'qwertyuiopasdfghjkl;\'zxcvbnm,Q"AZ'))
l = dict(zip('wertyuiop[\'asdfghjkl;xcvbnm,.{:"<', 'qwertyuiop;\'asdfghjklzxcvbnm,PL:M'))
shifts = {'right': r, 'left': l}

def shift(ciphered):
    letters = set(ciphered)
    if letters & set('p[{,<') or any(i in ciphered for i in ('yjr', 'smf')):
        return 'left'
    elif letters & set('qz\\|/?') or any(i in ciphered for i in ('rgw', '\'bs')):
        return 'right'
    else:
        return 'right' if ciphered.count('w') > ciphered.count('y') else 'left'

def decipher(ciphered):
    ciphered = ciphered.split('.', 1)[0].lower()
    shift_ = shift(ciphered)
    text = ''.join(shifts[shift_].get(i, i) for i in ciphered).capitalize()
    print 'text:', text + '.'
    print 'offset:', 'left' if shift_ == 'right' else 'right'

decipher(raw_input())

This is how it works:

  • If any of the characters p[{,< are in the ciphered string, or yjr or smf (the and and shifted right respectively) are in the string, then the string must have been shifted right.
  • If any of the characters qz\|/? are in the ciphered string, or rgw or 'bs (the and and shifted left respectively) are in the string, then the string must have been shifted left.
  • If neither of the above are true, then we compare the counts of 'w' and 'y' in the string. If there are more 'w's, then it is most likely to have been shifted left, because 'e' is more common than 'u' in English. If not, then it probably would have been shifted right, since 't' is much more common than 'q' in English.
    • The original function used 'w' and 's', however using e/u and q/t will theoretically produce much stabler results, as the frequency differences between the letter pairs are higher than those of the original e/d and q/a.
    • This will work for most strings, however theoretically there might be some strings who will give the wrong output. (If you find one, post the offender in the comments and I will try to make the test more stable)
  • We reverse-shift the string accordingly, to produce the output.

Note that if there is a comma in a string that has been shifted right (ie there is a . in the ciphered string excluding the one at the end), then this will not work, as the function only deciphers the part before the first period in the string.

Here are some sample test results.

\$\endgroup\$
  • \$\begingroup\$ Very clever, And something I hadn't thought of. I will have many more test cases later today and I may switch some of the scoring to how many of the test cases can be run correctly. But +1 for your current solution. \$\endgroup\$ – Ryan May 1 '13 at 14:50
  • \$\begingroup\$ Nice approach and explanation. \$\endgroup\$ – DavidC May 1 '13 at 18:24
2
\$\begingroup\$

Tcl

set right {q w w e e r r t t y y u u i i o o p p {[} {[} \] \] q Q W W E E R R T T Y Y U U I I O O P P {[} {[} \] \] Q a s s d d f f g g h h j j k k l l {;} {;} ' ' a A S S D D F F G G H H J J K K L L {;} {;} ' ' A \\ z z x x c c v v b b n n m m , , \\ \\ Z Z X X C C V V B B N N M M , , \\}
set left {q \] w q e w r e t r y t u y i u o i p o {[} p \] {[} Q \] W Q E W R E T R Y T U Y I U O I P O {[} P \] {[} a ' s a d s f d g f h g j h k j l k {;} l ' {;} A ' S A D S F D G F H G J H K J L K {;} L ' {;} \\ , z \\ x z c x v c b v n b m n , m \\ , Z \\ X Z C X V C B V N B M N , M}
gets stdin data
set len [string length $data]
set min 0
set res {}
foreach {d} {left right} {
   set trans [string map [set $d] $data]
   if {[string first " and " $trans] > 0 || [string first " the " $trans] > 0} {set v 1} {
       if {[regexp {[\]\[]} $trans]} {continue}
       set vocals [regexp -all -nocase {[aeiou]} $trans]
       set v [expr {($vocals * 1. / $len)}]
   }
   if {$v > $min} {
       set res "$trans\noffset: $d"
       set min $v
   }
}
puts $res

I build a map to replace the characters with the next.
If there are strange characters in the output, I'll reject it.
As last chance I take the highest vocal/length count.

I claim the +2

\$\endgroup\$
  • \$\begingroup\$ Because I have (currently) the fastest, most elegant & most readable code, I have a score of 42. \$\endgroup\$ – Johannes Kuhn Apr 30 '13 at 8:42
1
\$\begingroup\$

Lua

The idea is to determine which group of letters is prevailing: ABIUW or JOPY.
The former has frequent letters on next key to the right on the keyboard, the latter - to the left.

local strings = [[
Upi djpi;f ytu yu[omh pmr yp yjr ;rgy.
U kujw oeife'nnubf xibrwara.
X'ra 'bs sifa 'ew ai o'aaw.
Yjod vpmysod sm stnoysto;u ;pmh eptf.
Rgw x'r ub rgw g'r qwbr iyr ri v'r.
Og upi vtrsyr s d,s;; fovyopmstu pg yjr ,pdy vp,,pm rmh;odj eptfd yjrm upi vsm vjrvl upit piy[iy gpt yjpdr eptfd' yjr eptf ayjra smf yjr eptf asmfa str imowir ejrm pggdry ;rgy smf pggdry tohjy.
]]
for str in strings:gmatch'%C+' do
   str = str:lower()
   -- compare total counters of letters ABIUW and JOPY
   local _, left_ctr  = str:gsub('[abiuw]','')
   local _, right_ctr = str:gsub('[jopy]','')
   local offset = left_ctr - right_ctr
   offset = offset / math.abs(offset)  -- offset == (+1) or (-1)
   -- restore original string
   local original = ''
   local keyboard = "asdfghjkl;'?zxcvbnm,'qwertyuiop['"
   for c in str:gmatch'.' do
      local pos = keyboard:find(c, 1, true)
      c = pos and keyboard:sub(pos + offset, pos + offset) or c
      original = original..c
   end
   print('text: '..original:sub(1,1):upper()..original:sub(2))
   print('offset: '..({[-1]='right', 'left'})[offset])
   print()
end

Output:

text: You should try typing one to the left.
offset: right

text: I like progr?mming contests.
offset: left

text: C?ts ?nd dogs ?re so p?sse.
offset: left

text: This contais an arbitarily long word.
offset: right

text: The c?t in the h?t went out to b?t.
offset: left

text: If you create a small dictionary of the most common english words then you can check your output for those words; the word the and the word and are unique when offset left and offset right.
offset: right
\$\endgroup\$
1
\$\begingroup\$

Haskell

Certainly not the fastest or smallest one, but at least now there is a Haskell solution!

The idea

  1. Write in the code the configuration of the keyboard, one string per keyboard line
  2. Generate left and right shifted keyboard and build dictionaries of keys correspondences
  3. Create a ShiftString method that convert a string with right or left dictionary
  4. Write an englishProb function that compute the least square between frequency of a given string and the english language frequencies
  5. Implement a method chooseShift that convert a string to left and right shifted sentences, compute the englishProb on them and return the dictionary minimizing the least square error
  6. Write a solve method that take a string, choose the best dictionary, convert the sentence with it, and format the output as desired
  7. Create the main function that use solve on input

The code

import Data.Char
import Data.List

main :: IO()
main = do
    content <- getContents
    putStr . unlines . map solve . lines $ content

solve :: String -> String
solve s = "text:" ++ shiftString shift sc ++ ".\noffset: " ++ offset shift
    where sc = takeWhile (/='.') s
          shift = chooseShift sc
          offset sh | sh == left = "left"
                    | sh == right = "right"
                    | otherwise = "unknown"

chooseShift :: String -> [(Char, Char)]
chooseShift s = if (englishProb lefted >= englishProb righted) then left else right
    where lefted = shiftString left $ map toLower s
          righted = shiftString right $ map toLower s

englishProb :: String -> Double
englishProb s = squaredDiff stats
    where stats = map (\a@(x:_) -> (x,normalize $ length a)) . group . sort $ s
          normalize a = (fromIntegral a) / (fromIntegral $ length s)
          squaredDiff p = sum . map ((\x -> x*x) .  diff) . filter isAlpha $ p
          diff (c,v) = abs . (v-) $ lookup' c letterFreq
          isAlpha (a,_) = ord(a) >= 97 && ord(a) <= 122

keyboard :: [String]
keyboard = ["qwertyuiop[]\\", "asdfghjkl;'","zxcvbnm,./"," "]

right :: [(Char,Char)]
right = shiftKeyboardWith shiftR
    where shiftR l = (tail l)++[(head l)]

left :: [(Char,Char)]
left = shiftKeyboardWith shiftL
    where shiftL l = (last l):(init l)

shiftString :: [(Char,Char)] -> String -> String
shiftString m s = map (\c -> shiftChar c m) s

shiftChar :: Char -> [(Char, Char)] -> Char
shiftChar k d = reCast $ (\(Just b) -> b) $ lookup (toLower k) d
    where reCast = if (isUpper k) then toUpper else id

shiftKeyboardWith :: ([Char] -> [Char]) -> [(Char,Char)]
shiftKeyboardWith f = zip (concat keyboard) . concat $ map f keyboard

lookup' :: (Eq a) => a -> [(a,b)] -> b
lookup' k d = (\(Just b) -> b) $ lookup k d

letterFreq :: [(Char, Double)]
letterFreq = [ ('a',8.167)
             , ('b',1.492)
             , ('c',2.782)
             , ('d',4.253)
             , ('e',12.702)
             , ('f',2.228)
             , ('g',2.015)
             , ('h',6.094)
             , ('i',6.966)
             , ('j',0.153)
             , ('k',0.772)
             , ('l',4.025)
             , ('m',2.406)
             , ('n',6.749)
             , ('o',7.507)
             , ('p',1.929)
             , ('q',0.095)
             , ('r',5.987)
             , ('s',6.327)
             , ('t',9.056)
             , ('u',2.758)
             , ('v',0.978)
             , ('w',2.360)
             , ('x',0.150)
             , ('y',1.974)
             , ('z',0.074) ]

Compilation

ghc shift.hs
./shift.hs < inputs

Output

text: You should try typing one to the left.
offset: left
text: I like programming contests.
offset: right
text: Cats and dogs are so passe.
offset: right
text: This contais an arbitarily long word.
offset: left
text: The cat 'n the hat went out to bat.
offset: right
text: If you create a small dictionary of the most common english words then you can check your output for those words; the word 'the' and the word 'and' are unique when offset left and offset right.
offset: left
\$\endgroup\$
1
\$\begingroup\$

Python 2.6 390 430 410 408 355 347 354 346 300 chars

Updates:

  1. (Hopefully) fixed a bug with semicolons.
  2. Horrible hack to make the middle row work properly :(
  3. Golfed the hack a bit better
  4. Fixed stupid printing
  5. Realised I can assume left if not right!
  6. Now deals with the whitespace in a much neater way. (after breaking it!)
  7. Trimmed a bit all over
  8. Changed the key condition for left or rightness
  9. Changed some variable names and pruned the lambda
  10. Thanks to Volatility for some much neater ways to do things, and a general golf overhaul (see comments).
  11. Changed the letters it searches for to avoid redundancy (for instance the character r is likely to appear in all shifted sentences).

Golfed with help from Volatility. Algorithm compares the number of times the characters 'awg and mp;[y appear in the text. The first set corresponds to aoseh shifted left, the second to anolpt shifted right. These unshifed letters are highly likely to appear in any sentence (each set should account for ~40% of the letters in a normal sentence) and are indicative of which shift occurred (the shifted letters are unlikely/forbidden to appear in the same sentence when shifted the other way).

To help with choosing which letters to use, I used the frequency of each letter to find the corresponding frequency of characters which appear in shifted sentences using this (slightly golfed for practice) program.

I don't think it handles punctuation very well for instance (commas?). Please leave comments with failure cases and I'll try to make it more robust :)

Usage

$ program.py
'Put text here with any escape characters if it\'s necessary.' 

Code:

s=''.join(dict(zip('|{"?:<',"\['/;,")).get(x,x)for x in input().lower())
h=lambda b:sum(x in b for x in s)
i=h('mpsy;[')>h("'aiwg")
f="  \qwertyuiop[asdfghjkl;'/zxcvbnm,. "
t=''
for x in s:t+=f[f.find(x)+(1,-10)[x=="'a"[i]]*(-1)**i]
print'offset:',('righ','lef')[i]+'t\ntext:',t[:-1].capitalize()+'.'

Explanation:

  • Ignore uppercase and replace "uppercase" symbols (ie capital "Q" shifted left is "|")
  • Choose right if any characters from that small set, else right (this actually is sufficient for all the test cases!). Compare number of indicative 'left' and 'right' characters and chose left or right from this
  • the shift string is as reduced as possible and as a result doesn't deal with the middle line wrapping around. 2 spaces at the start and 1 at the end deals with the whitespace
  • deal with ' if shifted left or a if shifted right by offsetting by 10 in the other direction. whitespace is found at index 0 in s so -1 or +1 match either 2nd or last character in s (both whitespace)
  • print

Failures:
There are failure cases but the code will work with a very high probability if the sentence hasn't been specifically engineered to break it :)

Boo proper nouns: "\"b 'ookw dwkk ib Bwqrib;a gw's."
Right-shifted sentences without the letters anoplt but with some 'fqu
"Wirrmd wirrg ypp." fails whereas "Wirrmd wirrg ypp upi lmpe." succeeds (apologies) Left-shifted sentences without the letters aeosh

\$\endgroup\$
  • 1
    \$\begingroup\$ Here is a bit of golfing I did to your code. It's functionally exactly the same, apart from the use of raw_input(), so you can change it if you want to. It's 301 chars including newlines, and quite legible. ;) \$\endgroup\$ – Volatility May 4 '13 at 2:13
  • \$\begingroup\$ @Volatility that's very cool, I was wondering if there was something I could do with that dict and zip but I've never got round to learning to use zip (this is as good a time as any!). One criticism: your variables don't spell out anything on the lhs :). Mind if I update my post with your work (with credit of course)? \$\endgroup\$ – ejrb May 4 '13 at 11:04
  • \$\begingroup\$ Certainly (ie. I don't mind). If you want to, you can change the variable names as well. (Maybe something like s h i f t will do) ;) \$\endgroup\$ – Volatility May 4 '13 at 11:09
  • \$\begingroup\$ Actually I just realised that the last line should have r.capitalize()[:-1] instead of r.capitalize(). That's 306 characters, sorry -.- \$\endgroup\$ – Volatility May 4 '13 at 11:25
  • \$\begingroup\$ You read my mind (re shift) and now it shall appear I've stolen your idea! Also I don't think *~-0**h works as you expect. ~-0**n = -1 for all n>0 but ~-0**0 = 0 (for some reason). I've replaced it with *(1-2*h) which I think is the best alternative... also raw_input doesn't work if the text starts with an escape character - like the one at the bottom of my post \$\endgroup\$ – ejrb May 4 '13 at 11:35

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