Problem 59: XOR Decryption

Problem 59 source code

C++

#include <algorithm>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <limits>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

namespace {

using i64 = std::int64_t;

struct Options {
    std::string file = "resources/documents/0059_cipher.txt";
    bool run_checkpoints = true;
};

bool parse_string_after_prefix(const std::string& arg,
                               const std::string& prefix,
                               std::string& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    value = tail;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_string_after_prefix(arg, "--file=", options.file)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return true;
}

std::vector<int> parse_cipher_csv(const std::string& payload) {
    std::vector<int> values;
    std::string token;

    for (char c : payload) {
        if ((c >= '0' && c <= '9')) {
            token.push_back(c);
        } else if (!token.empty()) {
            values.push_back(std::stoi(token));
            token.clear();
        }
    }
    if (!token.empty()) {
        values.push_back(std::stoi(token));
    }

    return values;
}

std::string decrypt_with_key(const std::vector<int>& cipher, const std::string& key) {
    std::string out;
    out.resize(cipher.size());

    for (std::size_t i = 0; i < cipher.size(); ++i) {
        out[i] = static_cast<char>(cipher[i] ^ key[i % key.size()]);
    }

    return out;
}

int text_score(const std::string& text) {
    int score = 0;

    for (char c : text) {
        const unsigned char uc = static_cast<unsigned char>(c);
        if (uc < 9 || uc > 126) {
            return -1000000;
        }
        if (c == ' ') {
            score += 3;
        }
        if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
            score += 2;
        }
    }

    auto count_occurrences = [&](const std::string& needle) {
        int cnt = 0;
        std::size_t pos = 0;
        while (true) {
            pos = text.find(needle, pos);
            if (pos == std::string::npos) {
                break;
            }
            ++cnt;
            pos += needle.size();
        }
        return cnt;
    };

    score += 40 * count_occurrences(" the ");
    score += 25 * count_occurrences(" and ");
    score += 20 * count_occurrences(" of ");
    score += 20 * count_occurrences(" to ");
    return score;
}

i64 ascii_sum(const std::string& text) {
    i64 total = 0;
    for (char c : text) {
        total += static_cast<unsigned char>(c);
    }
    return total;
}

i64 solve(const std::string& file_path) {
    std::ifstream input(file_path);
    if (!input) {
        throw std::runtime_error("Could not open cipher file: " + file_path);
    }

    std::ostringstream buffer;
    buffer << input.rdbuf();
    const std::vector<int> cipher = parse_cipher_csv(buffer.str());

    int best_score = std::numeric_limits<int>::min();
    std::string best_text;

    for (char a = 'a'; a <= 'z'; ++a) {
        for (char b = 'a'; b <= 'z'; ++b) {
            for (char c = 'a'; c <= 'z'; ++c) {
                const std::string key = {a, b, c};
                const std::string text = decrypt_with_key(cipher, key);
                const int score = text_score(text);
                if (score > best_score) {
                    best_score = score;
                    best_text = text;
                }
            }
        }
    }

    return ascii_sum(best_text);
}

bool run_checkpoints() {
    const std::string key = "abc";
    const std::string plain = "hello world";
    std::vector<int> cipher;
    cipher.reserve(plain.size());
    for (std::size_t i = 0; i < plain.size(); ++i) {
        cipher.push_back(static_cast<unsigned char>(plain[i]) ^ key[i % key.size()]);
    }

    if (decrypt_with_key(cipher, key) != plain) {
        std::cerr << "Checkpoint failed for XOR roundtrip" << '\n';
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }

    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    try {
        std::cout << solve(options.file) << '\n';
    } catch (const std::exception& ex) {
        std::cerr << ex.what() << '\n';
        return 3;
    }

    return 0;
}

Python

import sys

def parse_cipher_csv(payload):
    values = []
    token = ""
    
    for c in payload:
        if '0' <= c <= '9':
            token += c
        elif token:
            values.append(int(token))
            token = ""
    
    if token:
        values.append(int(token))
    
    return values

def decrypt_with_key(cipher, key):
    out = []
    for i in range(len(cipher)):
        decrypted_char = cipher[i] ^ ord(key[i % len(key)])
        out.append(chr(decrypted_char))
    return ''.join(out)

def text_score(text):
    score = 0
    
    for c in text:
        uc = ord(c)
        if uc < 9 or uc > 126:
            return -1000000
        if c == ' ':
            score += 3
        if ('a' <= c <= 'z') or ('A' <= c <= 'Z'):
            score += 2
    
    def count_occurrences(needle):
        cnt = 0
        pos = 0
        while True:
            pos = text.find(needle, pos)
            if pos == -1:
                break
            cnt += 1
            pos += len(needle)
        return cnt
    
    score += 40 * count_occurrences(" the ")
    score += 25 * count_occurrences(" and ")
    score += 20 * count_occurrences(" of ")
    score += 20 * count_occurrences(" to ")
    
    return score

def ascii_sum(text):
    total = 0
    for c in text:
        total += ord(c)
    return total

def solve(file_path):
    try:
        with open(file_path, 'r') as input_file:
            cipher_data = input_file.read()
    except Exception:
        raise RuntimeError(f"Could not open cipher file: {file_path}")
    
    cipher = parse_cipher_csv(cipher_data)
    
    best_score = float('-inf')
    best_text = ""
    
    for a in range(ord('a'), ord('z') + 1):
        for b in range(ord('a'), ord('z') + 1):
            for c in range(ord('a'), ord('z') + 1):
                key = chr(a) + chr(b) + chr(c)
                text = decrypt_with_key(cipher, key)
                score = text_score(text)
                if score > best_score:
                    best_score = score
                    best_text = text
    
    return ascii_sum(best_text)

def run_checkpoints():
    key = "abc"
    plain = "hello world"
    cipher = []
    
    for i in range(len(plain)):
        cipher.append(ord(plain[i]) ^ ord(key[i % len(key)]))
    
    if decrypt_with_key(cipher, key) != plain:
        return False
    
    return True

def main():
    file_path = "resources/documents/0059_cipher.txt"
    run_checkpoints_flag = True
    
    # Parse command line arguments
    args = sys.argv[1:]
    for arg in args:
        if arg == "--skip-checkpoints":
            run_checkpoints_flag = False
        elif arg.startswith("--file="):
            file_path = arg[7:]
    
    if run_checkpoints_flag and not run_checkpoints():
        sys.exit(2)
    
    try:
        result = solve(file_path)
        print(result)
    except Exception as e:
        sys.stderr.write(str(e) + "\n")
        sys.exit(3)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.nio.file.*;
import java.util.*;

public class Euler59 {

    private static class Options {
        String file = "resources/documents/0059_cipher.txt";
        boolean runCheckpoints = true;
    }

    private static boolean parseStringAfterPrefix(String arg, String prefix, StringBuilder value) {
        if (!arg.startsWith(prefix)) {
            return false;
        }
        String tail = arg.substring(prefix.length());
        if (tail.isEmpty()) {
            return false;
        }
        value.setLength(0);
        value.append(tail);
        return true;
    }

    private static boolean parseArguments(String[] args, Options options) {
        for (String arg : args) {
            if ("--skip-checkpoints".equals(arg)) {
                options.runCheckpoints = false;
                continue;
            }
            StringBuilder value = new StringBuilder();
            if (parseStringAfterPrefix(arg, "--file=", value)) {
                options.file = value.toString();
                continue;
            }
            System.err.println("Unknown argument: " + arg);
            return false;
        }
        return true;
    }

    private static List<Integer> parseCipherCsv(String payload) {
        List<Integer> values = new ArrayList<>();
        StringBuilder token = new StringBuilder();

        for (char c : payload.toCharArray()) {
            if (c >= '0' && c <= '9') {
                token.append(c);
            } else if (token.length() > 0) {
                values.add(Integer.parseInt(token.toString()));
                token.setLength(0);
            }
        }
        if (token.length() > 0) {
            values.add(Integer.parseInt(token.toString()));
        }

        return values;
    }

    private static String decryptWithKey(List<Integer> cipher, String key) {
        char[] out = new char[cipher.size()];
        for (int i = 0; i < cipher.size(); i++) {
            out[i] = (char)(cipher.get(i) ^ key.charAt(i % key.length()));
        }
        return new String(out);
    }

    private static int textScore(String text) {
        int score = 0;

        for (char c : text.toCharArray()) {
            int uc = (int)c;
            if (uc < 9 || uc > 126) {
                return -1000000;
            }
            if (c == ' ') {
                score += 3;
            }
            if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
                score += 2;
            }
        }

        int theCount = countOccurrences(text, " the ");
        int andCount = countOccurrences(text, " and ");
        int ofCount = countOccurrences(text, " of ");
        int toCount = countOccurrences(text, " to ");

        score += 40 * theCount;
        score += 25 * andCount;
        score += 20 * ofCount;
        score += 20 * toCount;

        return score;
    }

    private static int countOccurrences(String text, String needle) {
        int count = 0;
        int pos = 0;
        while ((pos = text.indexOf(needle, pos)) != -1) {
            count++;
            pos += needle.length();
        }
        return count;
    }

    private static long asciiSum(String text) {
        long total = 0;
        for (char c : text.toCharArray()) {
            total += (int)c;
        }
        return total;
    }

    private static long solve(String filePath) throws IOException {
        String content = Files.readString(Paths.get(filePath));
        List<Integer> cipher = parseCipherCsv(content);

        int bestScore = Integer.MIN_VALUE;
        String bestText = "";

        for (char a = 'a'; a <= 'z'; a++) {
            for (char b = 'a'; b <= 'z'; b++) {
                for (char c = 'a'; c <= 'z'; c++) {
                    String key = "" + a + b + c;
                    String text = decryptWithKey(cipher, key);
                    int score = textScore(text);
                    if (score > bestScore) {
                        bestScore = score;
                        bestText = text;
                    }
                }
            }
        }

        return asciiSum(bestText);
    }

    private static boolean runCheckpoints() {
        String key = "abc";
        String plain = "hello world";
        List<Integer> cipher = new ArrayList<>();
        for (int i = 0; i < plain.length(); i++) {
            cipher.add((int)plain.charAt(i) ^ key.charAt(i % key.length()));
        }

        if (!decryptWithKey(cipher, key).equals(plain)) {
            System.err.println("Checkpoint failed for XOR roundtrip");
            return false;
        }

        return true;
    }

    public static void main(String[] args) {
        Options options = new Options();
        if (!parseArguments(args, options)) {
            System.exit(1);
        }

        if (options.runCheckpoints && !runCheckpoints()) {
            System.exit(2);
        }

        try {
            System.out.println(solve(options.file));
        } catch (Exception ex) {
            System.err.println(ex.getMessage());
            System.exit(3);
        }
    }
}