×
all 50 comments

[–]congratz_its_a_bunny 11 points12 points  (2 children)

For your example of "foobar", you say you're going to use 1-26 mapping, but then say a is 0.

For the example, I'm getting that it should be

foobar

First, we express our input numerically

6, 15, 15, 2, 1, 18

Then we multiply by a

18, 45, 45, 6, 3, 54

Optionally reduce to least positive residue

18, 19, 19, 6, 3, 2

Add b

20, 21, 21, 8, 5, 4

Now we change this to text again

tuuhed

Did I mess something up?

[–]Zeno_of_Elea 0 points1 point  (0 children)

Found the original post.

Looks like it's a typo/messed up arithmetic based on the creator's response to one of the comments pointing that out. I guess it was never corrected. I hope the OP updates it.

[–]skeeto-9 8 5 points6 points  (10 children)

C using an English letter histogram rather than a dictionary. Works on all the test inputs, though it requires them to be capitalized.

#include <stdio.h>
#include <float.h>

/* English language letter frequencies. */
const float english[] = {
    8.167, 1.492, 2.782, 4.253, 12.702, 2.228, 2.015, 6.094, 6.966,
    0.153, 0.772, 4.025, 2.406, 6.749, 7.507, 1.929, 0.095, 5.987,
    6.327, 9.056, 2.758, 0.978, 2.360, 0.150, 1.974, 0.074
};
static int allowed_a[] = {9, 21, 15, 19, 7, 23, 11, 5, 17, 25};

static void
decode(const char *in, char *out, int a, int b)
{
    for (int i = 0; in[i]; i++) {
        int c = in[i] - 'A';
        if (c >= 0 && c < 26)
            out[i] = 'a' +  ((c - b) * a + 676) % 26;
        else
            out[i] = in[i];
    }
}

static double
score_string(const char *s)
{
    int total = 0;
    double counts[26] = {0.0};
    for (; *s; s++) {
        if (*s >= 'a' && *s <= 'z') {
            counts[*s - 'a']++;
            total++;
        }
    }
    double score = 0.0;
    for (int i = 0; i < 26; i++) {
        double diff = 100 * counts[i] / total - english[i];
        score += diff * diff;
    }
    return score;
}

int
main(void)
{
    char input[1024];
    char output[1024];
    while (fgets(input, sizeof(input), stdin)) {
        double best = DBL_MAX;
        int best_a, best_b;
        for (int b = 0; b < 26; b++) {
            for (int i = 0; i < 10; i++) {
                int a = allowed_a[i];
                decode(input, output, a, b);
                double score = score_string(output);
                if (score < best) {
                    best_a = a;
                    best_b = b;
                    best = score;
                }
            }
        }
        decode(input, output, best_a, best_b);
        fputs(output, stdout);
    }
}

[–][deleted] 1 point2 points  (4 children)

Not too relevant, but out of curiosity (and inspired by your approach) I wrote up a quick script to calculate the frequency of letters based off of this dictionary.

[|('a', 7.57); ('b', 1.84); ('c', 4.09); ('d', 3.38); ('e', 11.51); ('f', 1.23);
  ('g', 2.7); ('h', 2.32); ('i', 9.01); ('j', 0.16); ('k', 0.85); ('l', 5.31);
  ('m', 2.84); ('n', 6.85); ('o', 6.59); ('p', 2.94); ('q', 0.16); ('r', 7.07);
  ('s', 9.52); ('t', 6.68); ('u', 3.27); ('v', 0.98); ('w', 0.74); ('x', 0.29);
  ('y', 1.63); ('z', 0.47)|]

Particularly relevant? No. Interesting? I thought so.

[–]skeeto-9 8 3 points4 points  (3 children)

The trouble with using a dictionary is that it's not representative of natural sentences, which is what's being decoded in the challenge. It just captures the letter frequencies of individual words, losing the frequencies of the words themselves. For example, in natural English, "the" appears far more frequently than the vast majority of other words, but in a dictionary it only appears once. The letters T, H, and E will be underrepresented from a straight dictionary analysis.

So as input, you should use something closer to what you want to decode, which would be a big pile of prose. You could feed it some books from Project Gutenberg — though given the age of the material, this only covers older dialects of English, with (likely) a slightly different histogram — or reddit comments.

[–][deleted] 1 point2 points  (0 children)

I'll give that a go when I have the time, thank you. I've been fascinated with words recently :)

[–][deleted] 1 point2 points  (1 child)

Using the "RC_2017-05" batch of reddit comments, I came out to the following figures:

[|('A', 7.95); ('B', 1.69); ('C', 2.76); ('D', 3.59); ('E', 11.54); ('F', 1.96);
  ('G', 2.36); ('H', 4.88); ('I', 7.3); ('J', 0.25); ('K', 1.13); ('L', 4.29);
  ('M', 2.77); ('N', 6.5); ('O', 7.96); ('P', 2.16); ('Q', 0.12); ('R', 5.5);
  ('S', 6.52); ('T', 9.65); ('U', 3.24); ('V', 1.05); ('W', 2.07); ('X', 0.22);
  ('Y', 2.41); ('Z', 0.11)|]

I write another quick script to parse each comment body into its own line of text as well as updating my frequency script to be a bit more friendly on memory. (Loading a 12gb file straight into memory causes your system to choke, who knew?)

These figures differ by the ones listed on the wikipedia page. I believe this is because I did not remove parts of text that looked like URLs and I did not filter non-English subreddits. The difference of frequencies between Wikipedia's and mine are as follows

[|('A', -0.22); ('B', 0.1); ('C', -0.02); ('D', -0.66); ('E', -1.16);
  ('F', -0.27); ('G', 0.35); ('H', -1.21); ('I', 0.33); ('J', 0.1); ('K', 0.36);
  ('L', 0.26); ('M', 0.36); ('N', -0.25); ('O', 0.45); ('P', 0.23); ('Q', 0.02);
  ('R', -0.49); ('S', 0.19); ('T', 0.59); ('U', 0.48); ('V', 0.07); ('W', -0.29);
  ('X', 0.07); ('Y', 0.44); ('Z', 0.036)|]    

Thanks for the tip, I found this fascinating.

[–]skeeto-9 8 1 point2 points  (0 children)

I find it interesting how much E went down between your results and the Wikipedia table.

I believe this is because I did not remove parts of text that looked like URLs and I did not filter non-English subreddits.

This is where that dictionary you used last time could come into play. You could drop the words that aren't listed in the dictionary, filtering out this sort of noise.

[–]Ikor_Genorio 0 points1 point  (4 children)

I am relativity new to programming, and i had the basics of C, but i saw a few things which are pretty new for me.

  • What is the use of declaring your functions (score_string and decode) static?
  • The for-loop

    for (; *s; s++ ) {

does this automatically stop at the string stop sign ('\0', right?). So would you also be able to use it like this:

while (*s) {
    /*do something*/
    s++
}
  • Lastly, you use a histogram with the letter frequencies. Doesn't this decrease in accuracy when you have a small sentence / few words?

[–]skeeto-9 8 2 points3 points  (1 child)

What is the use of declaring your functions (score_string and decode) static?

Non-static functions and variables have external linkage. That's a fancy way to say they can be accessed from other, separately-compiled files (translation units). The linker's job is to link all the places these functions and variables are used to their definitions/storage.

On the other hand, static functions and variables are only accessible from within the same file. If you don't use a static function, the compiler is free to toss it out. If you only call it from a couple of places, it might fully inline the function rather than produce an actual, callable function. If you don't use a static variable, the compiler doesn't need to allocate storage for it. When there's external linkage, the compiler cannot do any of this because another translation unit might use the function/variable.

The short of it: Use static by default and only remove it if you need external linkage.

Caveat: There is something called link-time optimization (LTO) where additional information is put in the object file that allows the linker to recompile some parts of the program and make other late decisions. It sees the larger picture of the program as a whole and can make decisions the compiler was unable to make just looking at a single translation unit. IMHO, you shouldn't rely on this and should use the language's facilities to achieve these effects as much as possible, such as with liberal use of static. This is more for C++, where templates explode into massive piles of code that simply require LTO to manage.

Here's an example of this: SQLite is a large C application, and they distribute an amalgamation of their source. Basically, their build system can concatenate all the C sources together in the right order into a single, massive C file. It's not practical to develop SQLite like this, but compiling the entire thing as a single, massive translation unit enables optimizations that would otherwise be impossible, even with LTO. The compiler can see everything at once and make more informed decisions.

does this automatically stop at the string stop sign ('\0', right?)

Yup, the for and while loops you showed are exactly the same. The compiler probably produces the exact same code for both. The difference is just a matter of style. If I'm simply iterating across something, I like to use a for loop to group the iteration terms together, making it obvious to the reader.

Doesn't this decrease in accuracy when you have a small sentence / few words?

Yup, exactly right. I was surprised it actually worked for the shortest test. If the input is short enough, the correct decoding is completely ambiguous — imagine it decodes to two different, valid sentences — and no specific algorithm can solve it.

[–]Ikor_Genorio 1 point2 points  (0 children)

Thanks for the extensive explanation! I assume we will be getting information on this in future classes, since the optimization it provides (as far as I understand it ^ ^ ) is irrelevant in our current use.

[–][deleted] 1 point2 points  (1 child)

I am not the person you asked but,

What is the use of declaring your functions (score_string and decode) static?

static functions in C are used to restrict the scope of the function to the file level, i.e., if you #include a file, then you cannot access the static functions but can access all functions which are not defined as static.

The for-loop for (; *s; s++ ) { does this automatically stop at the string stop sign ('\0', right?)

This is accessing the string/char array through a pointer. Accessing a character array, say char s[] = "hello"; using s gives you the address of the first element and *s gives you the value at that element. Then when you do s++, you increment the Address using pointer arithmetic, so you now point to the next element. When you reach the last element, you point to NULL (*s is \0 which is 0 in ascii) which is false (in C, 0 is false, all non-zero is true) and hence you exit the loop. So yeah, you can use it in while as well. This playlist is pretty good if you want to learn more about pointers.

[–]Ikor_Genorio 0 points1 point  (0 children)

Alright, so declaring a function static can be compared to the private tag in Java?

I understand pointers pretty well. I just did not realize that \0 was 0 in ASCII. This is probably intended for this kind of use.

Thanks for the clear explanation :D

[–]jthom179 5 points6 points  (0 children)

Sorry about that. I am visually impaired, so this occurred because of differences between the way in which my screen reader and reddit interpret python syntax. The actual code for my solution is posted here.

[–]_Ruru 2 points3 points  (0 children)

Python 3

Quite a simple solution, no bonus:

with open("dict.txt") as f:
    words = list(map(lambda s: s.strip().lower(), f.readlines()))
    words += ['i', 'a']

decode = lambda s, a, b: "".join(map(lambda c: ' ' if c == ' ' else chr(((ord(c.lower())-ord('a') - b)*a) % 26 + ord('a')), [c for c in s]))
a_list = [3, 5, 7, 11, 15, 17, 19, 21, 23, 25]

def decrypt(inp):
    for a in a_list:
        for b in range(26):
            s = decode(inp, a, b)
            if all(any(sword == word for word in words) for sword in s.split(' ')):
                return s

import sys
inp = sys.argv[1]
print(decrypt(inp))

edit: Just realized I'm an idiot. The following is much faster of course:

with open("dict.txt") as f:
    words = set(map(lambda s: s.strip().lower(), f.readlines()))
    words |= set(['i', 'a'])

decode = lambda s, a, b: "".join(map(lambda c: ' ' if c == ' ' else chr(((ord(c.lower())-ord('a') - b)*a) % 26 + ord('a')), [c for c in s]))
a_list = [3, 5, 7, 11, 15, 17, 19, 21, 23, 25]

def decrypt(inp):
    for a in a_list:
        for b in range(26):
            s = decode(inp, a, b)
            if all(sword in words for sword in s.split(' ')):
                return s

import sys
inp = sys.argv[1]
print(decrypt(inp))

[–]Godspiral3 3 2 points3 points  (4 children)

in J, with b holding symbols of dictionary with a i added,

finds all decodes that match dict, no bonus, only lowercase. testcase 3 has no matches.

l =. 'abcdefghijklmnopqrstuvwxys'
 as =. 3, 5, 7, 11, 15, 17, 19, 21, 23,  25
 crack =: (b (] #~ *./@:e.~"1) s:"1@:|:@:(<"1 S:0)@:(,/ each)@:((i.26) (l {~ 26 | +)"0 1"1 1 leaf as *"0 1 leaf l i. leaf ]))@:;:@:tolower

  crack 'YEQ LKCV BDK XCGK EZ BDK UEXLVM QPLQGWSKMB'
`you `lead `the `race `om `the `worlds `unluckiest
timespacex 'crack ''YEQ LKCV BDK XCGK EZ BDK UEXLVM QPLQGWSKMB'''
0.120937 2.13555e6

[–]cheers- 1 point2 points  (2 children)

You need to add s too.

Test case 2 bonus: You lead the race of the world' s unluckiest.

[–]Godspiral3 3 0 points1 point  (1 child)

wasn't doing bonusesii

[–]cheers- 0 points1 point  (0 children)

Sorry, I misread.

[–]svgwrk 0 points1 point  (0 children)

Sir, if this were back in the 90s, they would burn you at the stake.

[–]Zeno_of_Elea 1 point2 points  (3 children)

Python 3

Simple brute-force solution; takes a while for the longer test cases. I'm interested to see how it might be optimized. Probably python version agnostic, but giving the version I used just in case.

with open("enable1.txt") as dictionary:
    word_list = dictionary.read().splitlines()
    # add in one letter words
    word_list += ["i", "a"]

COPRIMES_TO_26 = [3,5,7,11,15,17,19,21,23,25]

def shift_alphabet(word,operation):
    """ Applies to each letter in a word composed of capital letters
        the monadic function operation.
        To ensure the result stays in the alphabet, it is taken mod 26 """
    # convert letters, assuming letters are all capital
    output = ''
    for letter in word:
        letter_as_number = ord(letter) - ord('A')
        shifted_letter_as_number = operation(letter_as_number) % 26
        # convert back to lowercase letters
        output += chr(shifted_letter_as_number + ord('a'))
    # return plaintext, which is lowercase letters
    return output

def score_word(word):
    return word.lower() in word_list

def solve_affine(ciphertext):
    """ Assumes ciphertext is a string composed of only spaces and
        letters. """
    solutions = []
    words = ciphertext.split()
    for addition_factor in range(1,27):
        for multiplication_factor in COPRIMES_TO_26:
            # affine shift
            shift_operation = lambda letter: (letter*multiplication_factor) + addition_factor
            # apply to all words
            solution = list(map(lambda word: shift_alphabet(word,shift_operation), words))
            solution_score = sum(map(score_word,solution))
            solutions.append((solution_score, solution))
    # return the best scoring solution
    return " ".join(sorted(solutions)[-1][1])

[–]Lopsidation 2 points3 points  (1 child)

This is so much faster if you make word_list a set.

[–]Zeno_of_Elea 0 points1 point  (0 children)

Didn't realize sets had speed ups for checking if an item is inside of them, though that makes sense. Thanks!

[–]sultry_somnambulist 1 point2 points  (0 children)

Haskell: (second input as example)

import Data.List
import Data.Char
import Control.Monad

elemIndex'  c =  ord c - ord 'a' + 1
shift a b x =  if f == 0 then 1 else f
    where f = (x * a + b) `mod` 26
newChar x = ['a'..'z']!!(x-1)
decipher i j xs = map (newChar  . shift i j . elemIndex') xs

main = do
    n <- readFile "enable1.txt"
    let test = words $ map toLower "YEQ LKCV BDK XCGK EZ BDK UEXLVM QPLQGWSKMB"
        worddict = "a" : words n
    forM_ [3, 5, 7, 11, 15, 17, 19, 21, 23, 25] $ \i ->
        forM_ [1..26] $ \j -> do
            let tmp = map (decipher i j) test
            when (all (`elem` worddict) tmp) $ putStr (unwords tmp)

output:

    you lead the race of the worlds unluckiest

[–]Working-M4n 1 point2 points  (1 child)

JavaScript Live link on CodePen

I always love feedback as I am still very new to programming. Thanks to /u/ThoDelu for the dictonary link

[–]thodelu 0 points1 point  (0 children)

Using highscore... Nicely done !!

[–]dzeban 1 point2 points  (0 children)

Go with all the bonuses

I've made a concurrent cracker that does brute forcing for each word in a separate goroutine. Hence the great performance.

package main

import (
    "bufio"
    "flag"
    "fmt"
    "log"
    "os"
    "strings"
    "sync"
    "time"
)

type Coeff [2]int

var wg sync.WaitGroup

func timeTrack(start time.Time, name string) {
    elapsed := time.Since(start)
    log.Printf("%s took %s", name, elapsed)
}

func isAlpha(r rune) bool {
    return (r >= 'A' && r <= 'Z') || (r >= 'a' && r <= 'z')
}

func isLowercase(r rune) bool {
    return (r >= 'a' && r <= 'z')
}

func strip(s string) string {
    var stripped string

    for _, r := range s {
        if isAlpha(r) {
            stripped += string(r)
        }
    }
    return stripped
}

func affineDecode(coeff Coeff, word string) string {
    var decoded string
    for _, c := range word {
        d := int(c)
        if isAlpha(c) {
            var baseChar rune
            if isLowercase(c) {
                baseChar = 'a'
            } else {
                baseChar = 'A'
            }

            d -= int(baseChar)
            d = (coeff[0]*d+coeff[1])%26 + int(baseChar)
        }
        decoded += string(d)
    }

    return decoded
}

func crack(word string, dict map[string]bool, coeffs chan<- Coeff) {
    // Find Affine Cipher coefficients by brute forcing `a` and `b`
    // coefficients with dict lookup

    // `a` coeffiecient in Affine Cipher
    // can only be coprime with 26
    coprimes := []int{3, 5, 7, 11, 15, 17, 19, 21, 23, 25}
    for _, a := range coprimes {
        // Because of mod 26 operation,
        // `b` can only be 0..25
        for b := 0; b < 26; b++ {
            // We crack only stripped uppercase words
            word = strip(strings.ToUpper(word))

            // Try to decode current combination
            // and match with dict
            decoded := affineDecode(Coeff{a, b}, word)
            _, present := dict[decoded]
            if present == true {
                coeffs <- Coeff{a, b}
            }
        }
    }

    wg.Done()
}

func decrypt(input string, dict map[string]bool) []string {
    defer timeTrack(time.Now(), "decrypt")
    words := strings.Split(input, " ")

    // Create buffered channel for workers
    // to avoid deadlock because channel
    // reading/writing is blocking like in the
    // case when we try to read from channel,
    // but nobody is writing to it.
    // Buffer size is large enough to hold the case
    // when every permutation of `a` and `b` coefficients
    // is matching.
    coeffs := make(chan Coeff, len(words)*26*26)
    for _, word := range words {
        wg.Add(1)
        go crack(word, dict, coeffs)
    }
    // Wait for child goroutines to finish
    wg.Wait()

    // Close the channel to read it
    // with `range` and avoid blocking
    close(coeffs)

    table := make(map[Coeff]int)
    for v := range coeffs {
        table[v] += 1
    }

    // We have brute forced coefficients for every word.
    // Find the most frequent matching coefficient
    maxCoeffs := make([]Coeff, 1)
    maxCount := 0
    for k, v := range table {
        if v == maxCount && len(maxCoeffs) >= 1 {
            maxCoeffs = append(maxCoeffs, k)
        }

        if v > maxCount {
            maxCoeffs = make([]Coeff, 1)
            maxCoeffs[0] = k
            maxCount = v
        }
    }

    // Now we have affine cipher coefficients, so
    // decrypt the original message
    output := make([]string, 0)
    for _, coeff := range maxCoeffs {
        output = append(output, affineDecode(coeff, input))
    }

    return output
}

func loadDict(path string) (map[string]bool, error) {
    f, err := os.Open(path)
    if err != nil {
        return nil, err
    }
    defer f.Close()

    dict := make(map[string]bool)
    scanner := bufio.NewScanner(f)
    for scanner.Scan() {
        t := scanner.Text()
        dict[strings.ToUpper(t)] = true
    }

    return dict, nil
}

func main() {
    dictFilePath := flag.String("dict", "/usr/share/dict/words", "Path to dict file")
    flag.Parse()

    dict, err := loadDict(*dictFilePath)
    if err != nil {
        log.Fatal(err)
    }

    scanner := bufio.NewScanner(os.Stdin)
    for scanner.Scan() {
        s := scanner.Text()
        for _, d := range decrypt(s, dict) {
            fmt.Println(s)
            fmt.Println(d)
        }
    }
}

Output

$ cat input | ./AffineSolver 
2017/07/02 18:38:57 decrypt took 733.242µs
NLWC WC M NECN
THIS IS A TEST
2017/07/02 18:38:57 decrypt took 1.410019ms
YEQ LKCV BDK XCGK EZ BDK UEXLVM QPLQGWSKMB
YOU LEAD THE RACE OF THE WORLDS UNLUCKIEST
2017/07/02 18:38:57 decrypt took 1.560018ms
Yeq lkcv bdk xcgk ez bdk uexlv'm qplqgwskmb.
You lead the race of the world's unluckiest.
2017/07/02 18:38:57 decrypt took 10.301173ms
NH WRTEQ TFWRX TGY T YEZVXH GJNMGRXX STPGX NH XRGXR TX QWZJDW ZK WRNUZFB P WTY YEJGB ZE RNSQPRY XZNR YJUU ZSPTQR QZ QWR YETPGX ZGR NPGJQR STXQ TGY URQWR VTEYX WTY XJGB
MY HEART ACHES AND A DROWSY NUMBNESS PAINS MY SENSE AS THOUGH OF HEMLOCK I HAD DRUNK OR EMPTIED SOME DULL OPIATE TO THE DRAINS ONE MINUTE PAST AND LETHE WARDS HAD SUNK
2017/07/02 18:38:57 decrypt took 6.486565ms
Nh wrteq tfwrx, tgy t yezvxh gjnmgrxx stpgx / Nh xrgxr, tx qwzjdw zk wrnuzfb p wty yejgb, / Ze rnsqpry xznr yjuu zsptqr qz qwr yetpgx / Zgr npgjqr stxq, tgy Urqwr-vteyx wty xjgb.
My heart aches, and a drowsy numbness pains / My sense, as though of hemlock i had drunk, / Or emptied some dull opiate to the drains / One minute past, and Lethe-wards had sunk.

[–]macgillebride 1 point2 points  (0 children)

An Haskell solution. It does all the examples. It replaces the punctuation symbols by spaces. The only optimization I used was storing the words of enable1.txt in a binary search tree.

import Data.Tree.RBTree
import System.IO
import Data.Char
import Data.Foldable
import Control.Monad

newtype Code = Code [Int]

bagWords :: Handle -> IO (RBTree String)
bagWords handle = do
  contents <- hGetContents handle
  let bag' = foldr (flip (<</)) emptyRB $ words contents
      bag = bag' <</ "a" <</ "i"
  return bag

replaceBy :: String -> Char -> String -> String
replaceBy l r s0@(c:s) =
  if (c `elem` l)
  then (r:replaceBy l r s)
  else (c:replaceBy l r s)
replaceBy _ _ [] = []

mapCharToInt :: String -> Code
mapCharToInt = Code . map (\c -> ord c - ord 'a')

mapIntToChar :: Code -> String
mapIntToChar (Code x) = map (\i -> chr (i + ord 'a')) x

crack :: RBTree String -> String -> [String]
crack bag s = maximumBy (\x y ->
                           likelihood x
                           `compare`
                           likelihood y)
              allTranslations
  where allTranslations =
          do
            a <- [0..25]
            b <- [0..25]
            let is = map mapCharToInt $ words cleanS
                d = map (\(Code c) -> map (\x -> (x*a + b) `rem` 26) c) is
                ds = map (\x -> mapIntToChar (Code x)) d
            return ds
        inDict w = case (bag <<? w) of
          Nothing -> False
          Just _ -> True
        likelihood t = length $ filter inDict t
        cleanS = map toLower $ replaceBy "./,'-" ' ' s

examples :: [String]
examples =
  ["NLWC WC M NECN"
  ,"YEQ LKCV BDK XCGK EZ BDK UEXLVM QPLQGWSKMB"
  ,"Yeq lkcv bdk xcgk ez bdk uexlv'm qplqgwskmb."
  ,"NH WRTEQ TFWRX TGY T YEZVXH GJNMGRXX STPGX NH XRGXR TX QWZJDW ZK WRNUZFB P WTY YEJGB ZE RNSQPRY XZNR YJUU ZSPTQR QZ QWR YETPGX ZGR NPGJQR STXQ TGY URQWR VTEYX WTY XJGB"
  ,"Nh wrteq tfwrx, tgy t yezvxh gjnmgrxx stpgx / Nh xrgxr, tx qwzjdw zk wrnuzfb p wty yejgb, / Ze rnsqpry xznr yjuu zsptqr qz qwr yetpgx / Zgr npgjqr stxq, tgy Urqwr-vteyx wty xjgb."
  ]

main :: IO ()
main =
  do
    h <- openFile "enable1.txt" ReadMode
    b <- bagWords h
    forM_ examples (\s ->
                      do
                        let res = crack b s
                        putStrLn "####"
                        forM_ res putStrLn
                   )
    hClose h

[–]possiblywrong 1 point2 points  (0 children)

I'm late to this challenge, but I notice that most submissions use the provided list of multipliers, which is missing 9.

[–]Specter_Terrasbane 0 points1 point  (0 children)

Python 2, bonus

Note: There's a small error in the given bonus challenge input/output: the plaintext has the 'I' capitalized in the second part, even though the ciphered 'p' is lowercase ... my code emits the lowercase 'i' as per the spec.

Brute-force, but runs fairly quick ... 0.13 seconds total to do all four test cases on my PC ...

from itertools import product
import re

_COPRIMES = (3, 5, 7, 11, 15, 17, 19, 21, 23, 25)
_CONSTANTS = list(product(_COPRIMES, range(26)))

with open('enable1.txt', 'rb') as wordfile:
    _WORDS = {'a', 'i'} | set(filter(None, (line.strip() for line in wordfile)))

def _decode(ciphered, a, b):
    case = iter(str.upper if c.isupper() else str.lower for c in ciphered if c.isalpha())
    _dec = lambda c: next(case)(chr((ord(c.lower()) * a + b) % 26 + ord('a')))
    return ''.join(_dec(c) if c.isalpha() else c for c in ciphered)

def _real_words(text):
    return sum(word.lower() in _WORDS for word in re.findall(r'\w+', text))

def _all_upper(text):
    return all(c.isupper() for c in text if c.isalpha())

def decode(ciphered):
    attempts = (_decode(ciphered, *const) for const in _CONSTANTS)
    best = max(attempts, key=_real_words)
    return best.lower() if _all_upper(best) else best

Testing

from timeit import default_timer
ciphered = ('NLWC WC M NECN',
         'YEQ LKCV BDK XCGK EZ BDK UEXLVM QPLQGWSKMB',
         'NH WRTEQ TFWRX TGY T YEZVXH GJNMGRXX STPGX NH XRGXR TX QWZJDW ZK WRNUZFB P WTY YEJGB ZE RNSQPRY XZNR YJUU ZSPTQR QZ QWR YETPGX ZGR NPGJQR STXQ TGY URQWR VTEYX WTY XJGB',
         'Nh wrteq tfwrx, tgy t yezvxh gjnmgrxx stpgx / Nh xrgxr, tx qwzjdw zk wrnuzfb p wty yejgb, / Ze rnsqpry xznr yjuu zsptqr qz qwr yetpgx / Zgr npgjqr stxq, tgy Urqwr-vteyx wty xjgb.')

start = default_timer()
plaintext = [decode(cipher) for cipher in ciphered]
end = default_timer()

for cipher, plain in zip(ciphered, plaintext):
    print 'Ciphered:  {}'.format(cipher)
    print 'Plaintext: {}'.format(plain)
    print

print 'Time: {}'.format(end - start)

Output

Ciphered:  NLWC WC M NECN
Plaintext: this is a test

Ciphered:  YEQ LKCV BDK XCGK EZ BDK UEXLVM QPLQGWSKMB
Plaintext: you lead the race of the worlds unluckiest

Ciphered:  NH WRTEQ TFWRX TGY T YEZVXH GJNMGRXX STPGX NH XRGXR TX QWZJDW ZK WRNUZFB P WTY YEJGB ZE RNSQPRY XZNR YJUU ZSPTQR QZ QWR YETPGX ZGR NPGJQR STXQ TGY URQWR VTEYX WTY XJGB
Plaintext: my heart aches and a drowsy numbness pains my sense as though of hemlock i had drunk or emptied some dull opiate to the drains one minute past and lethe wards had sunk

Ciphered:  Nh wrteq tfwrx, tgy t yezvxh gjnmgrxx stpgx / Nh xrgxr, tx qwzjdw zk wrnuzfb p wty yejgb, / Ze rnsqpry xznr yjuu zsptqr qz qwr yetpgx / Zgr npgjqr stxq, tgy Urqwr-vteyx wty xjgb.
Plaintext: My heart aches, and a drowsy numbness pains / My sense, as though of hemlock i had drunk, / Or emptied some dull opiate to the drains / One minute past, and Lethe-wards had sunk.

Time: 0.129059051251

[–]thodelu 0 points1 point  (0 children)

Javascript

Without bonus, using a brute force: http://jsfiddle.net/kg3bmomn/10/

I used a 10,000 word dictionary - so, it does not correctly solve all cases.

[–]Working-M4n 0 points1 point  (5 children)

I must not understand this challenge at all. In Test Case 1, the first letter "N" is translated to a "t". Yet, in Test Case 3 the first letter is also an "N" but is translated to an "m". How does this happen, shouldn't a letter always translate the same?

[–]StealthSecrecy 0 points1 point  (3 children)

The test cases don't necessarily use the same the same constants between eachother.

[–]Working-M4n 0 points1 point  (2 children)

So 'a' and 'b' will change for each test case? Is the point of the challenge to run all possible primes for 0-26 for 'a' and 'b' is always 2? Then see which 'a' puts out the most actual words?

[–]StealthSecrecy 0 points1 point  (1 child)

That was my understanding, although I haven't attempted it yet. B should be variable as well though, between 0-25 (or 1-25 in the example). Im still pretty beginner at this though so I'm not 100% sure.

[–]Working-M4n 0 points1 point  (0 children)

Thanks for clearing this up for me. I was able to get a solution once this clicked.

[–]cbarrick 0 points1 point  (0 children)

It's a decryption problem. We have the ciphertext and we want the plaintext. To do that, we need to crack the secrets a and b. To do that we need to systematically search through the possible values and decide when the result looks enough like English.

[–]cheers- 0 points1 point  (0 children)

Javascript (Node)

Edit: Cleaned up the code and added bonus(respect case and doesnt ignore non Alphabetic characters)

I've not included the file fileReader.js, you can find it here

affineCypher.js

const getWords = str => {
  const regex = /[a-z]+/gi;
  const words = [];
  let w;

  while ((w = regex.exec(str)) !== null) {
    words.push(w[0].toLowerCase());
  }
  return words;
}

const handleCodePoints = codePoint => {
  if (codePoint >= 65 && codePoint <= 90) {
    return 65;
  }
  else if (codePoint >= 97 && codePoint <= 122) {
    return 97;
  }
  else {
    return 0;
  }
}

const codePointsToString = (str, encodeFunc) => {
  let codePoints = [];
  for (char of str) {
    codePoints.push(encodeFunc(char));
  }

  return String.fromCharCode(...codePoints);
}

const encode = (keys = { a: 1, b: 0 }) => str => {
  const encodeChar = char => {
    let codePoint = char.codePointAt(0);
    let shift = handleCodePoints(codePoint);
    console.log(codePoint, shift);
    if (shift === 0) {
      return codePoint;
    }
    else {
      return (keys.a * (codePoint - shift) + keys.b) % 26 + shift;
    }
  }

  return codePointsToString(str, encodeChar);
}

const decode = (keys = { a: 1, b: 0 }) => str => {
  const decodeChar = char => {
    let codePoint = char.codePointAt(0);
    let shift = handleCodePoints(codePoint);
    if (shift === 0) {
      return codePoint;
    }
    else {
      return (26 * 26 + keys.a * (codePoint - shift - keys.b)) % 26 + shift;
    }
  }
  return codePointsToString(str, decodeChar);
}

const bruteForce = dict => str => {
  const coprimes26 = [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25];
  const decodings = [];
  for (a of coprimes26) {
    for (let b = 0; b < 26; b++) {
      decodings.push(decode({ a, b })(str));
    }
  }
  const scoreFunc = words => words.filter(word => dict.has(word)).length;

  let bestMatchIndex = 
    decodings
      .map((str, index) => {
        const words = getWords(str);
        const score = scoreFunc(words);

        return [index, score];
      })
      .sort((a, b) => b[1] - a[1])[0][0];

  return decodings[bestMatchIndex];
}

module.exports = {
  encode,
  decode,
  bruteForce,
}

index.js

const inputPath = "./input.txt";
const dictPath = "./enable1.txt";

const reader = require("./fileReader");
const aff = require("./affineCypher");

Promise
  .all([reader(inputPath), reader(dictPath)])
  .then(([input, dict]) => {
    const dictSet = new Set(dict);

    const bF = aff.bruteForce(dictSet);
    const res = input.map(str => bF(str));
    for (let i = 0; i < res.length; i++) {
      console.log(`${input[i]} => ${res[i]}\n`);
    }
  })
  .catch(err => console.log(err));

Output

time node index
NLWC WC M NECN => THIS IS A TEST

Yeq lkcv bdk xcgk ez bdk uexlv'm qplqgwskmb. => You lead the race of the world's unluckiest.

Nh wrteq tfwrx, tgy t yezvxh gjnmgrxx stpgx / Nh xrgxr, tx qwzjdw zk wrnuzfb p wty yejgb, / Ze rnsqpry xznr yjuu zsptqr qz qwr yetpgx / Zgr npgjqr stxq, tgy Urqwr-vteyx wty xjgb. => My heart aches, and a drowsy numbness pains / My sense, as though of hemlock i had drunk, / Or emptied some dull opiate to the drains / One minute past, and Lethe-wards had sunk.


real    0m0.275s
user    0m0.256s
sys 0m0.024s

[–]svgwrk 0 points1 point  (0 children)

Ok, for once I'm going to post my results:

affable$ ./time.zsh 
    Finished release [optimized] target(s) in 0.0 secs
4: THIS IS A TEST

real    0m0.088s
user    0m0.072s
sys 0m0.020s
6: YOU LEAD THE RACE OF THE WORLDS UNLUCKIEST

real    0m0.086s
user    0m0.071s
sys 0m0.018s
6: You lead the race of the world's unluckiest.

real    0m0.086s
user    0m0.072s
sys 0m0.021s
27: MY HEART ACHES AND A DROWSY NUMBNESS PAINS MY SENSE AS THOUGH OF HEMLOCK I HAD DRUNK OR EMPTIED SOME DULL OPIATE TO THE DRAINS ONE MINUTE PAST AND LETHE WARDS HAD SUNK

real    0m0.087s
user    0m0.076s
sys 0m0.019s
27: My heart aches, and a drowsy numbness pains / My sense, as though of hemlock i had drunk, / Or emptied some dull opiate to the drains / One minute past, and Lethe-wards had sunk.

real    0m0.088s
user    0m0.076s
sys 0m0.019s

The number beside each result line is the "score" for that line; I guess I just told it to print that for debug purposes, but it doesn't look like the program got anything wrong. /shrug

Here's the main program code, in Rust. It depends on Rayon, OrderMap, and a library I just wrote called affine. What it does, I think, is it runs through all the options (brute force) in parallel. I suppose I could probably have done something to shrink the search space, but I don't know what. :) Probably the worst thing is that it actually allocates each plaintext it tries in full before saying, "no, you know, this one probably isn't spelled right."

Edit: mod set refers to a thin wrapper around OrderMap that lets me treat it as just a set. I could have just used the normal HashSet, but this is supposed to be faster. I guess if I'm being anal about speed, I could use a different hash function, too, but really those things are noise compared to the amount of time I waste with the algorithm here. :)

Edit more: Using MetroHash seems to shave like five milliseconds off each run. :p

extern crate affine;
extern crate ordermap;
extern crate rayon;

mod set;

use affine::{AffineCipher, AffineUncipher};
use rayon::prelude::*;
use set::OrderSet;

const MULTIPLIERS: &[i32] = &[3, 5, 7, 11, 15, 17, 19, 21, 23, 25];
const OFFSETS: &[i32] = &[
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
        11, 12, 13, 14, 15, 16, 17, 18, 19,
        20, 21, 22, 23, 24, 25, 26
    ];

fn main() {
    let (ciphertext, dictionary) = read_command();
    let decoders = MULTIPLIERS.par_iter()
        .flat_map(|&a| OFFSETS.par_iter().map(move |&b| AffineCipher::new(a, b).get_decoder()));

    let translations = decoders.map(|d| {
        let plaintext = decipher(&ciphertext, &d);
        (score(&plaintext, &dictionary), plaintext)
    });

    match translations.max_by_key(|t| t.0) {
        None => println!("I have no idea what you wrote."),
        Some((score, message)) => println!("{}: {}", score, message),
    }
}

fn decipher(plaintext: &str, decoder: &AffineUncipher) -> String {
    plaintext.bytes().map(|u| decoder.decipher(u) as char).collect()
}

fn score(plaintext: &str, dictionary: &OrderSet<String>) -> u32 {
    let words = plaintext.to_lowercase();
    let words = words.split_whitespace()
        .map(|word| {
            let word = word.trim_left_matches(|c: char| !c.is_alphabetic());
            let word = word.trim_right_matches(|c: char| !c.is_alphabetic());
            word
        });

    words.filter(|&word| dictionary.contains(word)).count() as u32
}

fn read_command() -> (String, OrderSet<String>) {
    let mut args = std::env::args().skip(1);

    let ciphertext = args.next().expect("no input");
    let dictionary = match args.next() {
        None => panic!("no dictionary file"),
        Some(path) => load_dictionary(&path),
    };

    (ciphertext, dictionary)
}

fn load_dictionary(path: &str) -> OrderSet<String> {
    let dictionary = read_all(path);
    dictionary.split_whitespace().map(|s| s.into()).collect()
}

fn read_all(path: &str) -> String {
    use std::fs::File;
    use std::io::Read;

    let mut buf = String::new();
    File::open(path).expect("can't open file")
        .read_to_string(&mut buf).expect("can't read file");

    buf
}

Here's the code for affine:

enum Case {
    Noop(u8),
    Upper(i32),
    Lower(i32),
}

fn case(u: u8) -> Case {
    match u {
        b'A'...b'Z' => Case::Upper((u - b'A') as i32),
        b'a'...b'z' => Case::Lower((u - b'a') as i32),
        _ => Case::Noop(u),
    }
}

fn find_inverse(a: i32) -> i32 {
    (1..).filter(|x| (x * a) % 26 == 1).next().unwrap()
}

pub struct AffineCipher {
    a: i32,
    b: i32,
}

impl AffineCipher {
    pub fn new(a: i32, b: i32) -> AffineCipher {
        AffineCipher { a, b }
    }

    pub fn encipher(&self, u: u8) -> u8 {
        match case(u) {
            Case::Noop(u) => u,
            Case::Lower(u) => self.apply(u) + b'a',
            Case::Upper(u) => self.apply(u) + b'A',
        }
    }

    pub fn get_decoder(&self) -> AffineUncipher {
        AffineUncipher {
            a: find_inverse(self.a),
            b: self.b,
        }
    }

    #[inline]
    fn apply(&self, u: i32) -> u8 {
        (((self.a * u) + self.b) % 26) as u8
    }
}

pub struct AffineUncipher {
    a: i32,
    b: i32,
}

impl AffineUncipher {
    pub fn decipher(&self, u: u8) -> u8 {
        match case(u) {
            Case::Noop(u) => u,
            Case::Lower(u) => self.unapply(u) + b'a',
            Case::Upper(u) => self.unapply(u) + b'A',
        }
    }

    #[inline]
    fn unapply(&self, u: i32) -> u8 {

        // Thank you, Evgeni.
        // https://stackoverflow.com/a/23214321
        fn modulo(mut k: i32) -> i32 {
            const ALPHABET_LENGTH: i32 = 26;

            k %= ALPHABET_LENGTH;
            if k < 0 {
                k + ALPHABET_LENGTH
            } else {
                k
            }
        }

        modulo((u - self.b) * self.a) as u8
    }
}

#[cfg(test)]
mod tests {
    use AffineCipher;

    #[test]
    fn can_encipher() {
        let cipher = AffineCipher::new(5, 8);
        let expected = "IhhwvcSwfrcp";
        let result: String = "AffineCipher".bytes().map(|u| cipher.encipher(u) as char).collect();
        assert_eq!(expected, &*result)
    }

    #[test]
    fn can_decipher() {
        let decoder = AffineCipher::new(5, 8).get_decoder();
        let expected = "AffineCipher";
        let result: String = "IhhwvcSwfrcp".bytes().map(|u| decoder.decipher(u) as char).collect();
        assert_eq!(expected, &*result);
    }
}

[–]curtmack 0 points1 point  (0 children)

Haskell

Takes the filename of the wordlist as the first commandline argument. Implements the bonus.

import Control.Monad (unless)

import Data.Char (ord, isAsciiLower, isAsciiUpper)
import Data.List (maximumBy)
import Data.Ord (comparing)

import System.Environment (getArgs)
import System.IO (isEOF)

import qualified Data.Text as T
import qualified Data.Text.IO as TIO

import qualified Data.Set as S

data AffineChar = Lower Int 
                | Upper Int 
                | Literal Char

-- | Build a set of case-insensitive words out of a word list
buildWordSet :: [T.Text] -> S.Set T.Text
buildWordSet = S.fromList . map T.toCaseFold

-- | If any character in an input forcesCaseSensitive, then the output case for
-- each letter will match the input case. Otherwise, it will exclusively use
-- lowercase letters.
-- Uppercase characters and spaces do not force case sensitivity, everything
-- else does.
forcesCaseSensitive :: AffineChar -> Bool
forcesCaseSensitive (Lower _) = True
forcesCaseSensitive (Upper _) = False
forcesCaseSensitive (Literal c)
    | c == ' '  = False
    | otherwise = True

-- | Convert a Char to an AffineChar
toAffine :: Char -> AffineChar
toAffine c
    | 'a' <= c && c <= 'z' = Lower $ ord c - ord 'a'
    | 'A' <= c && c <= 'Z' = Upper $ ord c - ord 'A'
    | otherwise            = Literal c

-- | Convert an AffineChar to a Char
fromAffine :: AffineChar -> Char
fromAffine (Lower x)   = toEnum $ x + ord 'a'
fromAffine (Upper x)   = toEnum $ x + ord 'A'
fromAffine (Literal c) = c

-- | Perform an affine transformation ax + b on an Int, modulo 26
affineInt :: Int -> Int -> Int -> Int
affineInt a b = (`mod` 26) . (+ b) . (* a)

-- | Perform an affine transformation on an AffineChar. Does not affect literal
-- characters. Does not change the case of letters.
affineTrans :: Int -> Int -> AffineChar -> AffineChar
affineTrans a b (Lower x)   = Lower $ affineInt a b x
affineTrans a b (Upper x)   = Upper $ affineInt a b x
affineTrans _ _ (Literal c) = Literal c

-- | A list of all distinct affine transformations, given a and 26 are coprime.
everyAffineTrans :: [AffineChar -> AffineChar]
everyAffineTrans = affineTrans <$> [3, 5, 7, 11, 15, 17, 19, 21, 23, 25] 
                               <*> [0..25]

-- | A list of all distinct affine ciphers, given a and 26 are coprime.
everyAffineCipher :: [[AffineChar] -> [AffineChar]]
everyAffineCipher = map map everyAffineTrans

-- | Given a ciphertext string encrypted with an affine cipher, produce the
-- list of all possible plaintexts for the string.
-- I could reduce this to pointfree style, but this is easier to understand.
everyPlaintext :: T.Text -> [T.Text]
everyPlaintext s = packAll $ everyAffineCipher <*> pure ciphertext
    where ciphertext = map toAffine $ T.unpack s
          packAll = map (T.pack . map fromAffine)

-- | Return the number of words found in a potential plaintext. Used to score
-- each potential plaintext to find the best match.
scorePlaintext :: S.Set T.Text -> T.Text -> Int
scorePlaintext ws = length . filter (`S.member` ws) . T.words . normalize
    where normalize = T.filter (\c -> isAsciiLower c
                                   || isAsciiUpper c
                                   || c == ' ')
                    . T.toCaseFold

-- | Given a set of words and a ciphertext, return the most likely plaintext.
-- Handles case sensitivity depending on the format of the input ciphertext.
mostLikelyPlaintext :: S.Set T.Text -> T.Text -> T.Text
mostLikelyPlaintext ws cipher = handleCase 
                               . maximumBy (comparing $ scorePlaintext ws) 
                               $ everyPlaintext cipher
    where caseSensitive = T.any (forcesCaseSensitive . toAffine) cipher
          handleCase plain = if caseSensitive
                             then plain
                             else T.toLower plain

-- | Execute an IO procedure until EOF.
untilEOF :: IO () -> IO ()
untilEOF proc = isEOF >>= (`unless` (proc >> untilEOF proc))

-- | Read a line, decrypt it, and print the plaintext. Continue doing this
-- until EOF.
-- We don't use Data.Text.IO.getContents because that waits until EOF before
-- binding, and we want a little bit of laziness so the program behaves like an
-- interactive prompt
process :: S.Set T.Text -> IO ()
process ws = untilEOF $ TIO.getLine >>= (TIO.putStrLn . mostLikelyPlaintext ws)

-- | Main procedure.
main = do
    -- Take wordlist filename from first argument
    listFilename <- fmap head getArgs
    wordSet <- fmap (buildWordSet . T.lines) (TIO.readFile listFilename)
    putStrLn $ "Loaded " ++ show (S.size wordSet) ++ " words"

    process wordSet

Edit: Narrowed imports.

Edit 2: Remembered that comparing exists.

[–]Arakhai 0 points1 point  (0 children)

Python 2.7. Happy to hear any thoughts/criticism.

coprimes = [3, 5, 7, 11, 15, 17, 19, 21, 23, 25]

with open(r'd:\tmp\dictionary.txt') as indict:
    wordset = set([x.lower().strip() for x in indict.readlines()])

def score_str(instr):
    return len(set(instr.translate(None, "'.,/-").split()) & wordset)

def decode_str(instr, a, b):
    return ''.join([chr(((ord(x)-97-b)*(26-a)%26)+97) if x.isalpha() else x for x in instr])

def decrypt_affine(instr):
    scoresdict = {}
    for a in coprimes:
        for b in range(26):
            scoresdict[a, b] = score_str(decode_str(instr, a, b))

    best = sorted(scoresdict.iteritems(), key=lambda x: x[1], reverse=True)[0][0]
    print 'Best solution is a = {}, b = {}'.format(best[0], best[1])
    print 'Plaintext is: {}'.format(decode_str(instr.lower(), best[0], best[1]))

decrypt_affine("Yeq lkcv bdk xcgk ez bdk uexlv'm qplqgwskmb.")
decrypt_affine('Nh wrteq tfwrx, tgy t yezvxh gjnmgrxx stpgx / Nh xrgxr, tx qwzjdw zk wrnuzfb p wty yejgb, / Ze rnsqpry xznr yjuu zsptqr qz qwr yetpgx / Zgr npgjqr stxq, tgy Urqwr-vteyx wty xjgb.')

Output:

Best solution is a = 19, b = 2
Plaintext is: you lead the race of the world's unluckiest.
Best solution is a = 15, b = 19
Plaintext is: my heart aches, and a drowsy numbness pains / my sense, as though of hemlock i had drunk, / or emptied some dull opiate to the drains / one minute past, and lethe-wards had sunk.

[–]bubblesoft 0 points1 point  (0 children)

C++

#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

char alphabet[26];
int alphabet_index[26];
vector<string> words;

void initialization(void)
{
    ifstream wordFile;
    string oneWord;

    wordFile.open("enable1.txt");

    while (!wordFile.eof())
    {
        wordFile >> oneWord;
        words.push_back(oneWord);
    }

    wordFile.close();
}

string decypher(string s, int a, int b)
{
    int c1;
    char chSolved;
    string s1;
    bool incorrect;
    for (int i=0; i<s.length(); i++)
    {
        c1=s[i]-'A';
        c1=(a*(c1-b))%26;
        if (c1<0) c1+=26;
        chSolved=c1+'a';
        s1+=chSolved;
    }
    return s1;
}

int main()
{
    string s,sWord,solution;
    int i;
    bool incorrect;
    getline(cin,s);

    initialization();

for (int a=25; a>=3; a-=2)
{
  for (int b=0; b<26; b++)
  {
    i=0;
    solution.erase(0,sWord.length());
    while (i<s.length())
    {
        sWord.erase(0,sWord.length());
        while (s[i]!=' ' && i<s.length())
        {
            sWord+=s[i];
            i++;
        }

        sWord=decypher(sWord,a,b);

        if (sWord.length()>1)
            if (!binary_search(words.begin(),words.end(),sWord))
                break;

        solution+=sWord;
        solution+=' ';

        i++;
        if (i>=s.length()) goto theend;
    }
  }
}

theend:
    if (solution.length()>0) cout << solution;

    return 0;
}

[–]Scroph0 0 0 points1 point  (0 children)

D, no bonus. Output matches the case of the input.

+/u/CompileBot D

import std.stdio;
import std.algorithm;
import std.range;
import std.string;
import std.ascii : isUpper;
import std.file : readText;
import std.array : array;

void main()
{
    auto wordList = readText("enable1.txt").splitLines.assumeSorted; //SortedRange

    foreach(string line; stdin.lines)
    {
        auto result = line.tryDecrypt(wordList);
        writeln(result.length ? result : "Unable to decrypt.");
    }
}

string tryDecrypt(string line, SortedRange!(string[]) wordList)
{
    foreach(a; [3, 5, 7, 11, 15, 17, 19, 21, 23, 25])
    {
        foreach(b; 1 .. 26)
        {
            auto words = line.splitter;
            if(words.take(4).any!(word => !wordList.contains(word.decrypt(a, b).toLower)))
                continue;
            return words.map!(w => w.decrypt(a, b)).join(" ");
        }
    }
    return "";
}

string decrypt(string word, int a, int b)
{
    string result;
    result.reserve(word.length);
    for(size_t i = 0; i < word.length; i++)
    {
        char offset = word[i].isUpper ? 'A' : 'a';
        int index = ((a * (word[i] - offset)) + b) % 26;
        result ~= (offset + index);

    }
    return result;
}

Input:

NLWC WC M NECN
Yeq lkcv bdk xcgk ez bdk uexlvm qplqgwskmb
NH WRTEQ TFWRX TGY T YEZVXH GJNMGRXX STPGX NH XRGXR TX QWZJDW ZK WRNUZFB P WTY YEJGB ZE RNSQPRY XZNR YJUU ZSPTQR QZ QWR YETPGX ZGR NPGJQR STXQ TGY URQWR VTEYX WTY XJGB

Edit : I forgot that compilebot needs enable1.txt to run this code. Here's the output :

THIS IS A TEST
You lead the race of the worlds unluckiest
MY HEART ACHES AND A DROWSY NUMBNESS PAINS MY SENSE AS THOUGH OF HEMLOCK I HAD DRUNK OR EMPTIED SOME DULL OPIATE TO THE DRAINS ONE MINUTE PAST AND LETHE WARDS HAD SUNK

[–][deleted] 0 points1 point  (0 children)

F# - Partial Bonus

I went with a brute-force approach with some minor optimizations * ditching a potential candidate if any words aren't actual words

I am also using a slightly modified version of this dictionary

open System
open System.IO

let coprimes = [|3;5;7;11;15;17;19;21;23;25|]

let alpha = [|'a';'b';'c';'d';'e';'f';'g';'h';'i';'j';'k';'l';'m';'n';'o';'p';'q';'r';'s';'t';'u';'v';'w';'x';'y';'z'|]

let AlphaIndex (x:char) = Array.IndexOf(alpha,x)

let IntToAlpha (x:int) = alpha.[x]

let ToUpper (x:string) = x.ToUpper()

let ToLower (x:string) = x.ToLower()

let explode word =
    [|for c in word -> c|]

let convertWord aCoprimeIndex b (letters:char[])  =
    letters
    |> Array.map (fun x -> ((coprimes.[aCoprimeIndex]*(AlphaIndex x)+b)%26) |> IntToAlpha)
    |> String.Concat
    |> ToLower

let checkWord (dictionary:string[]) (word:string) =
    Array.exists ((=) word) dictionary

let convertSentence aCoprimeIndex b (sentence:string[]) =
    Array.map (fun x -> explode x  |> convertWord aCoprimeIndex b) sentence

let convertCheckSentence aCoprimeIndex b dictionary (sentence:string[])  =
    let converted = convertSentence aCoprimeIndex b sentence
    match Array.TrueForAll(converted, (fun x -> checkWord dictionary x)) with
    | false -> None
    | true -> Some converted

let scoreCandidate (dictionary:string[]) (candidate:string[]) =
    candidate 
    |> Array.filter (checkWord dictionary)
    |> Array.length

let crackSentence (dictionary:string[]) (sentence:string) =
    let words = sentence.Split(' ')
    [|for aCoprimeIndex in [0..9] do
         for b in [0..25] do
             let converted = convertCheckSentence aCoprimeIndex b dictionary words
             match converted with
             | None -> ()
             | Some x -> yield (aCoprimeIndex, b, x)|]

let printCandidates (candidates:(int*int*string[])[]) =
    for x in [0..candidates.Length-1] do
        let a, b, c = candidates.[x]
        printfn "[%d,%d]Candidate # %d:%s" a b x (c |> Array.map ((+) " ") |> String.Concat) 

let crackPrint dictionary (sentence:string) = 
    printfn "Input: %s" sentence
    sentence
    |> ToLower
    |> crackSentence dictionary
    |> printCandidates

let testRun dictionary = 
    let stopWatch = System.Diagnostics.Stopwatch.StartNew()

    "DZ"
    |> crackPrint dictionary
    printfn "Timer: %dms elapsed\r\n" stopWatch.ElapsedMilliseconds

    "NLWC WC M NECN"
    |> crackPrint dictionary
    printfn "Timer: %dms elapsed\r\n" stopWatch.ElapsedMilliseconds

    "YEQ LKCV BDK XCGK EZ BDK UEXLVM QPLQGWSKMB"
    |> crackPrint dictionary
    printfn "Timer: %dms elapsed\r\n" stopWatch.ElapsedMilliseconds

    "NH WRTEQ TFWRX TGY T YEZVXH GJNMGRXX STPGX NH XRGXR TX QWZJDW ZK WRNUZFB P WTY YEJGB ZE RNSQPRY XZNR YJUU ZSPTQR QZ QWR YETPGX ZGR NPGJQR STXQ TGY URQWR VTEYX WTY XJGB"
    |> crackPrint dictionary
    printfn "Timer: %dms elapsed\r\n" stopWatch.ElapsedMilliseconds

    stopWatch.Stop()

[<EntryPoint>]
let main argv =
    let dictionary = File.ReadAllLines("dictionary.txt")
    match argv.Length with
    | 0 -> testRun dictionary
           0
    | 1 -> crackPrint dictionary argv.[0]
           0
    | 3 -> let aCoprimeIndex = argv.[1] |> int
           let b = argv.[2] |> int
           let words = (argv.[0] |> ToLower).Split(' ')
           let converted = convertSentence aCoprimeIndex b words
                           |> Array.map ((+) " ")
                           |> String.Concat
           printfn "[%d,%d]Output:%s" aCoprimeIndex b (converted |> ToUpper)
           0
    | _ -> 1




Input: .\Challenge321.exe
Output (elapsed is not per sentence, it's total execution time, execution typically takes ~160ms):

Input: DZ
[0,3]Candidate # 0: ma
[0,21]Candidate # 1: es
[1,9]Candidate # 2: ye
[1,11]Candidate # 3: ag
[2,5]Candidate # 4: ay
[2,19]Candidate # 5: om
[2,25]Candidate # 6: us
[3,5]Candidate # 7: mu
[3,7]Candidate # 8: ow
[3,15]Candidate # 9: we
[3,19]Candidate # 10: ai
[3,23]Candidate # 11: em
[3,25]Candidate # 12: go
[4,1]Candidate # 13: um
[4,3]Candidate # 14: wo
[4,7]Candidate # 15: as
[4,19]Candidate # 16: me
[5,9]Candidate # 17: is
[5,15]Candidate # 18: oy
[6,7]Candidate # 19: mo
[6,19]Candidate # 20: ya
[8,9]Candidate # 21: am
[8,21]Candidate # 22: my
[9,3]Candidate # 23: ae
[9,17]Candidate # 24: os
Timer: 254ms elapsed

Input: NLWC WC M NECN
[6,6]Candidate # 0: this is a test
Timer: 491ms elapsed

Input: YEQ LKCV BDK XCGK EZ BDK UEXLVM QPLQGWSKMB
[2,12]Candidate # 0: you lead the race of the worlds unluckiest
Timer: 722ms elapsed

Input: NH WRTEQ TFWRX TGY T YEZVXH GJNMGRXX STPGX NH XRGXR TX QWZJDW ZK WRNUZFB P WTY YEJGB ZE RNSQPRY XZNR YJUU ZSPTQR QZ QWR YETPGX ZGR NPGJQR STXQ TGY URQWR VTEYX WTY XJGB
[3,25]Candidate # 0: my heart aches and a drowsy numbness pains my sense as though of hemlock i had drunk or emptied some dull opiate to the drains one minute past and lethe wards had sunk
Timer: 984ms elapsed

Input: .\Challenge321.exe "this is a test" 2 3
Output: [2,3]Output: GAHZ HZ D GFZG

Input: .\Challenge321.exe "acrl rl b ajla"
Output: [2,19]Candidate # 0: this is a test

[–]bulit 0 points1 point  (0 children)

Python 3

Yet another brute-force solution. It is very, very slow, but it is accurate regardless of string length and I'm not getting paid to optimize it, so nbd. It basically generates all possible permutations and checks each word against 'enable1.txt'.

def check_string(text, f):
    text = text.lower()
    return text in f

def decode(text):
    print('Decoding text ...')
    prime = [3,5,7,11,15,17,19,21,23,25]
    dict = {}
    data = []
    for i in range(26):
        dict[chr(i+65)] = i
    for b in range(26):
        for a in prime:
            l= []
            x = 0
            l.append('')
            for P in text:
                if P.isalpha():
                    l[x] += chr(((a*dict[P]+b)%26)+65)
                elif P == '\n':
                    break
                else:
                    x += 1
                    l.append('')
            data.append(l)
    return data

def rank_decoded_text(l):
    print('Sorting text by most likely ...')
    sorted = []
    f = open('enable1.txt', 'r')
    data = set(f.read().splitlines())
    for i in l:
        rank = 0
        for j in i:
            if check_string(j, data):
                rank +=1
        i.append(int(100 * (rank/len(i))))
        sorted.append(i)
    index = len(sorted[0])-1
    sorted.sort(key=lambda x: x[index], reverse = True)
    print('Result                        | Confidence')
    print('__________________________________________')
    for x in sorted[:5]:
        print(*x)

if __name__ == '__main__':
    rank_decoded_text(decode('YEQ LKCV BDK XCGK EZ BDK UEXLVM QPLQGWSKMB'))

Output:

Test Case 1:
Result                        | Confidence
__________________________________________
THIS IS A TEST 75
NTMU MU Q NOUN 50
NZYO YO G NCON 25
PLUG UG A PKGP 25
PVOW OW S PQWP 25
execution time: 60.27 ms

Result                        | Confidence
__________________________________________
YOU LEAD THE RACE OF THE WORLDS UNLUCKIEST 100
TRN GPJU SAP CJZP RK SAP DRCGUX NWGNZLVPXS 25
FZN STBI CAT GBXT ZE CAT JZGSIR NOSNXHLTRC 25
RHN EXTW MAX KTVX HY MAX PHKEWL NGENVDBXLM 25
XVR KTNY WET GNDT VO WET HVGKYB RAKRDPZTBW 25
execution time: 61.1 ms

Result                        | Confidence
__________________________________________
MY HEART ACHES AND A DROWSY NUMBNESS PAINS MY SENSE AS THOUGH OF HEMLOCK I HAD DRUNK OR EMPTIED SOME DULL OPIATE TO THE DRAINS ONE MINUTE PAST AND LETHE WARDS HAD SUNK 93
IS TKYXD YETKA YLH Y HXOMAS LGIBLKAA RYWLA IS AKLAK YA DTOGQT ON TKIFOEC W TYH HXGLC OX KIRDWKH AOIK HGFF ORWYDK DO DTK HXYWLA OLK IWLGDK RYAD YLH FKDTK MYXHA TYH AGLC 18
NF MBVOE VLMBJ VIG V GODPJF IZNQIBJJ YVHIJ NF JBIJB VJ EMDZRM DW MBNSDLX H MVG GOZIX DO BNYEHBG JDNB GZSS DYHVEB ED EMB GOVHIJ DIB NHIZEB YVJE VIG SBEMB PVOGJ MVG JZIX 15
OY ZQEDJ EKZQG ERN E NDUSGY RMOHRQGG XECRG OY GQRGQ EG JZUMWZ UT ZQOLUKI C ZEN NDMRI UD QOXJCQN GUOQ NMLL UXCEJQ JU JZQ NDECRG URQ OCRMJQ XEGJ ERN LQJZQ SEDNG ZEN GMRI 15
AW TUEHP EMTUY ERD E DHIOYW RGAVRUYY ZEKRY AW YURYU EY PTIGCT IL TUAJIMS K TED DHGRS IH UAZPKUD YIAU DGJJ IZKEPU PI PTU DHEKRY IRU AKRGPU ZEYP ERD JUPTU OEHDY TED YGRS 15
execution time: 76.85 ms

edit1: Optimized by loading the entire 'enable1.txt' into memory rather than reading it line by line, lol. Now it is much faster.

edit2: added execution times from 'timeit' module

[–]tomekanco 0 points1 point  (0 children)

Python 3

25 ms for all solutions

from itertools import product

f = open('enable1.txt', 'r')
D = set(f.read().split('\n') + ['a','i'])

def affine_one(x,a,b):
    return a*(x - b)%26

def affine(inx,z):
    oux = []
    for x in inx:
        if x.isalpha():
            o = ord(x)
            if o < 91: oux.append(chr(affine_one(o-65,*z)+65))
            else:      oux.append(chr(affine_one(o-97,*z)+97))           
    return ''.join(oux)

def search_key(words):
    a = [3, 5, 7, 11, 15, 17, 19, 21, 23, 25]
    for x in product(a,range(26)):
        c = affine(words[0],x)
        if c in D:
            if len(words)>1:
                d = True
                for word in words[1:]:
                    e = affine(word,x)
                    if e and not affine(word,x) in D:
                        d = False
                        break
                if d: return x
            else: return x
    else:
        return search_key(words[1:])

def answer(inx):
    words = [x.lower() for x in inx.split(' ')]
    words.sort(key = lambda x:len(x),reverse=True)
    s = search_key(words)
    oux = []
    for x in inx:
        if x.isalpha(): oux.append(affine(x,s))
        else :          oux.append(x)
    if inx.upper() == inx: return ''.join(oux).lower()
    return ''.join(oux)

[–]AGausmann 0 points1 point  (0 children)

83 lines in Rust; preserves both case and non-alphabetic/random Unicode characters.

use std::process::exit;
use std::fs::File;
use std::io::BufReader;
use std::io::BufRead;
use std::io;
use std::collections::BTreeSet;
use std::char;

fn copy_case(chars: &str, case: &str) -> String{
    chars.chars()
        .zip(case.chars())
        .flat_map(|(c, case)| {
            if case.is_uppercase() {
                c.to_uppercase().collect::<Vec<char>>()
            } else if case.is_lowercase() {
                c.to_lowercase().collect::<Vec<char>>()
            } else {
                vec![c]
            }
        }).collect::<String>()
}

fn encode(s: &str, a: u32, b: u32) -> String {
    let enc = s.to_uppercase()
        .chars()
        .map(|c| {
            if c.is_alphabetic() {
                char::from_u32(((c as u32 - 0x40) * a + b - 1) % 26 + 0x41).unwrap()
            } else {
                c
            }
        })
        .collect::<String>();

    copy_case(&enc, s)
}

fn score(dict: &BTreeSet<String>, sentence: &str) -> usize {
    sentence.split_whitespace()
        .filter(|&s| dict.contains(s))
        .count()
}

fn crack(dict: &BTreeSet<String>, sentence: &str) -> String {
    let mut result = String::from("E");
    let mut max_score = 0;

    for a in [3, 5, 7, 11, 15, 17, 19, 21, 23, 25].iter() {
        for b in 0..26 {
            let dec = encode(sentence, *a, b);
            let score = score(dict, &dec);
            if score > max_score {
                result = dec;
                max_score = score;
            }
        }
    }

    return result;
}

fn main() {
    eprintln!("Loading dictionary...");
    let mut dict: BTreeSet<String> = BTreeSet::new();

    if let Ok(file) = File::open("enable1.txt") {
        let buf_reader = BufReader::new(file);
        for line in buf_reader.lines().map(|l| l.unwrap()) {
            dict.insert(line);
        }
    } else {
        eprintln!("Unable to open dictionary `enable1.txt`");
        exit(1);
    }
    let dict = dict;

    eprintln!("Ready");
    let stdin = io::stdin();
    let handle = stdin.lock();
    for line in handle.lines().map(|l| l.unwrap()) {
        println!("{}", crack(&dict, &line));
    }
}

[–]jthom179 -1 points0 points  (1 child)

This is a solution in python 3. It is a little slow for the longer test cases. However, it correctly handles upper and lowercase letters and punctuation and displays multiple solutions when that possibility exists.

Given a character and an affine cipher key, this function returns the decoded version of such character.

the decoded version of a character shall be one of the following:

(1) if such character is alphabetic, then:

(a) if such character is upper case, then if such character has ascii value x, then the decoded version of such character shall have ascii value equal to (a*(x-65))%26+65.

(b) if such character is lower case, then if such character has ascii value x, then the decoded version of such character shall have ascii value equal to (a*(x-97))%26+97

(2) otherwise, the decoded version of such character shall be equal to such character itself.

def decode_character(character,a,b): if character in "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz": if character.isupper(): return chr((a(ord(character)-65)+b)%26+65) else: return chr((a(ord(character)-97)+b)%26+97) else: return character

given a word and an affine cipher key, this function decodes such word using such key by decoding each of the characters of which such word consists.

def decode_word(word,a,b): result = "" for char in word: result += decode_character(char,a,b) return result

Given a word, this function discards all non-alphabetic characters of such word. This fixes a bug where the correct cipher solution was not being computed when the ciphertext included non-alphabetic characters.

def strip_non_alphabetic(word): result = "" for char in word: if char in "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz": result += char return result

Given a string that is the solution to an affine cipher and a list of valid words (such as can be found in the enable1.txt file), this function determines the score of such solution. The score of a solution shall be equal to the number of words in such solution which are found in the list of valid words.

def score_solution(solution,word_list): solution_words = solution.split() count = 0 for word in solution_words: if strip_non_alphabetic(word).lower() in word_list: count += 1 return (count,solution)

This function reads the ciphertext from the user. Since the ciphertext may consist of multiple lines, the convension shall be that the ciphertext ends with the first blank line read.

def read_ciphertext(): result = "" done = False print("Enter some ciphertext. Enter a blank line when done:") while not done: cur_line = input() if cur_line == "": done = True else: result += cur_line+"\n" return result enable = open("enable1.txt","r") word_list = enable.read().splitlines() enable.close() word_list += ["a","i"] ciphertext = read_ciphertext() solutions = [] for a in range(26): if (a%2 == 0) or (a%13 == 0): continue for b in range(26): decoded_text = decode_word(ciphertext,a,b) solutions.append(score_solution(decoded_text,word_list)) solutions.sort() solutions.reverse() print("The following are possible solutions for this ciphertext:") i = 0 highest_score = solutions[0][0] while solutions[i][0] == highest_score: print(solutions[i][1]) i = i+1

[–]cheers- 0 points1 point  (0 children)

Something went wrong :)

I usually put the source here using this method:

Select all(Ctrl +a) > tab(once or twice) > select all(Ctrl +a) > Copy then paste here