Project Euler/59: Difference between revisions
From charlesreid1
| Line 16: | Line 16: | ||
==Approach== | ==Approach== | ||
Part 1: | Part 1: | ||
| Line 44: | Line 39: | ||
(Part 1 should be enough to get us a key...) | (Part 1 should be enough to get us a key...) | ||
Attempted short-circuit: | |||
* This problem uses the Vigenere cipher with a 3-letter key | |||
* Chunk the message into 3s, and line them up vertically. Generate bigrams from 1-2 and 2-3. | |||
* Treat histogram of bigrams for pos 1-2 separate from pos 2-3 | |||
==Flags== | ==Flags== | ||
{{ProjectEulerFlag}} | {{ProjectEulerFlag}} | ||
Revision as of 20:51, 14 April 2025
Problem Statement
This question is about a method of encrypting ASCII text.
Each character in ASCII has some representation (e.g., A=65, *=42, k=107)
Encryption technique is to take text file, convert bytes to ASCII, and XOR each byte with a character from a secret key
Password method: use a password in place of a secret one-time pad; shorter than message, so repeated cyclically throughout method.
You are given a file with encrypted ascii codes, knowledge that plain text must contain common English words, and told encryption key consists of 3 lowercase characters. Decrypt message, find sum of ascii values in original text.
Sample file looks like this: 36,22,80,0,0,4,23,...
Link: https://projecteuler.net/problem=59
Approach
Part 1:
- Create list of most common bigrams in English language
- Sliding window of 2 letters at a time
- For each pair of letters in the ciphertext, for each most common bigram, find the corresponding secret key at that position that would cause this bigram to become the most common bigram
- Keep track of weights too - not just which secret key value would lead to the given bigram, but how common that bigram is
- Keep track of potential secret key values and weights in 3 data structures, one for each potential secret key character; we know which one to use based on character position
Part 2:
- Create list of most common trigrams in English language
- Sliding window of 3 letters at a time
- For each triplet of letters, for each most common trigram, find the corresponding secret key at that position that would cause this trigram to become the most common trigram
Part 3:
- Create list of most common letters in English language, plus weights
- For each "letter" in the ciphertext, for each most common letter, find the corresponding secret key at that position that would cause the ciphertext to become the most common letter
(Part 1 should be enough to get us a key...)
Attempted short-circuit:
- This problem uses the Vigenere cipher with a 3-letter key
- Chunk the message into 3s, and line them up vertically. Generate bigrams from 1-2 and 2-3.
- Treat histogram of bigrams for pos 1-2 separate from pos 2-3
Flags
