Now over - winner Nimble - results here: http://forums.overclockers.co.uk/showpost.php?p=18093370&postcount=196
Prize: The winner gets a £5.00 steam purchase of your choice or £5.00 to a charity of your choice.
*** (This isn't as hard as it looks - just a long and verbose post!) ***
The idea of a programming contest was brought up a while ago and never came back, so I adapted a contest I made for uni a while back and hopefully it will work well here so we can do future ones
The challenge is hopefully a good mix between not too easy and not too hard while being slightly tricky. I wrote a solver in about 4-5 hours in about 230 lines of Python, and that was a hacky unoptimized mess - so it's a good project. Comp will run for about 3 weeks so hopefully enough people will submit entries
** Revisions/Errors **
[05/12/10] For Stage 1 - there are two values of n under 1.5 million that produce the largest chain length. You need to go with the smallest of the two - confirm your answers here http://www.jcsecurity.co.uk/ocuk.html
(Apologies for the mistake, it's tricky getting everything perfect!)
Competition Close: 15:00 on 27/12/10 - Winner Announced: 15:00 28/12/10
Rules:
- You may use any language you wish so long as it is executable from a Windows or Linux command line prompt and there should be no GUI (basic command line only)
Typically I would advise C/C++/C#/Python, please check if you want to go with something else first just to make sure. You must use standard language only, i.e no third party libs etc.
- The only major rule is no pre-computing of answers is allowed, it must be done dynamically at run time.
- Please don't cheat and copy code directly from the net, at least without understanding it fully
The Challenge:
Ok the goal of this challenge is to work out a 10 character password to unlock a one-time-pad encrypted secret message. Each of the 10 characters is found by solving sub challenges of varying difficulty.
Your program will take 10 numbers representing the secret message as input command line arguments and will output the decrypted message. The numbers are ascii codes for the 10 characters of the ciphertext. Don't worry about the decryption, it's a very simple XOR operation which is 1 line of code in most languages and is fully explained below (The main focus is on the 10 challenges). So, you need to solve 10 challenges to get all 10 characters of the password, then you can decrypt the secret and profit.
Your program should run as follows: "myProg.exe n1 n2 n3 n4 n5 n6 n7 n8 n9 n10" and it should output "Secret Message: ..." It will also be helpful if you print out the results from each of the 10 stages.
Here is two sets of input ciphertexts / numbers you can use to test the program with, once you get everything correct, you will recognise the decrypted secret message easily.
Set 1: 234, 103, 91, 136, 62, 119, 95, 55, 191, 19
Set 2: 233, 97, 75, 151, 62, 102, 69, 63, 191, 26
So for set 1, you should run your prog as "myProg.exe 234 103 91 136 62 119 95 55 191 19" and you should get out "Secret Message: ----------".
Here are the 10 sub-challenges, some follow on from each other and some are individual.
Stage 1 (medium/easy)
This is known as the 3n+1 or Collatz conjecture problem and is a sequence defined as follows:
If n is even then: n = n/2
Else if n is odd then: n = 3n + 1
The sequence finishes when: n=1
So following these simple rules, if we pick a first number for n to begin the sequence as n = 10 - it creates the following sequence:
eg (n=10) 10 - > 5 -> 16 -> 8 -> 4 -> 2 -> 1 (Chain length: 7)
eg (n=13) 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (Chain length: 10)
You need to work out which starting value of n produces the longest sequence chain where n is greater than 0 and less than or equal to 1500000 (1.5 million). NB: There are two values that produce the largest chain, go with the smaller of the two.
The starting value (n) that makes the longest chain is the answer to this stage. NB: This will take a while to crunch the numbers when executing).
Stage 2 (medium)
Firstly work out (stage1Answer % 9999), that is, take your answer to stage 1 modulus 9999. This effectively transforms a number into the range 0-9999 and makes it easier to work with for this question. % will take the modulus in most languages.
Now make an algorithm to work out the number of letters it would take to represent this result number in written form, ignoring spaces, hyphens and commas but including 'and'. It will need to work with any number between 0 and 9999.
For example, if the result from stage 1 mod 9999 was 189:
Then 189 - "One hundred and eighty nine" = 23 (and is included in the count)
Eg(1). 435 - "four hundred and thirty five" = 24
Eg(2) 16 - "sixteen" = 7
Eg(3) 3017 - "three thousand and seventeen" = 25
The number of letters needed to represent your number is the answer to this stage. This is an interesting thing to code
Stage 3 (easy)
Taking your answer from part 2 and add 1337 to it. Take this result and add all the individual digits together to produce a sum.
e.g 27 + 1337 = 1364 = 1 + 3 + 6 + 4 = 14
eg(1) 145 + 1337 = 1482 = 1 + 4 + 8 + 2 = 15
eg(2) 1734 + 1337 = 3071 = 3 + 0 + 7 + 1 = 11
The sum of the digits is your answer to this stage.
Stage 4 (medium)
Taking your answer from part 3 and work out the factorial of that number.
Factorial is defined as n! = n(n-1) * ... * 2 * 1
and n = stage3Answer
eg(1) 5! = 5 * 4 * 3 * 2 * 1 = 120
eg(2) 3! = 3 * 2 * 1 = 6
The result is the answer to this stage.
Stage 5 (med/hard)
Find the 13370th prime number - you will need to use an algorithm to work out if a number is prime or not via a loop.
A number is prime if it divides only by itself and 1. Google is your friend. This must be done dynamically - no hardcoding the prime number!
The prime number is the answer to this stage.
Stage 6 (easy)
Take the 13370th prime from part 5 and work out the modulus 9999 of it. Then work out the number of letters needed to represent it in word form. This is the same as part 2.
eg: Prime number 2 % 9999 = two = 3
The number of letters is your answer to this stage.
Stage 7 (easy)
Taking your answer from part 6 add together the individual digits to calculate a sum, this is the same as stage 3.
e.g 3 = 3
e.g 564 = 5+6+4 = 15
This sum is the answer to this stage.
Stage 8 (medium)
Find the sum of all the numbers below 5000 that are multiples of 3 or 5.
e.g Below 10 - all multiples of 3 or 5 below 10 are 3,5,6,9 - the sum is 23.
The sum is your answer to this stage.
Stage 9 (hard)
Work out the sum of all primes below 2.5 million - this can use your prime testing algorithm from stage 5 expect around 3 minutes computational time (if your algorithms any good!).
e.g Sum of all primes below 10 - Primes are: 2,3,5,7 = 2+3+5+7 = 17
The sum is the answer to this stage.
Stage 10 (easy)
Work out the the sum of the individual digits in the answer to stage 9.
E.g if the sum from stage 9 is 751 then the answer to this stage is 7+5+1 = 13.
-------------------------------------
11 - The End - (medium)
Ok by now you should have code in place to calculate 1 integer answer for each of the 10 challenges above. Now it is time to use these to decrypt the secret and win the game.
This is basic XOR encryption (one-time-pad) and is a very secure (not now, as hopefully you know the key!).
Firstly you need to transform your 10 answers into valid keys by taking them modulo 255 As follows:
Your program took 10 numbers as input arguments, you now need to XOR each of those given numbers with each of the keys you made above. XORing the first input arg with the answer to stage 1 (mod 255) will give you the first letter of the secret message as an ASCII number.
This should clear up any confusion (% is the modulus operator):
Your program should print out the complete secret message. Note - XOR will give you a number in ASCII, you need to print this number as a character - this is well documented on Google e.g "ascii number to character".
Hints:
The % symbol is the modulus operator in most languages, e.g 5 % 255 will give you 5 mod 255. So working out the modulus is no extra work for you.
The ^ symbol is the XOR operator in most languages e.g 5 ^ 8 will give you 5 XOR 8. So working out the XOR decryption is no extra work for you.
Factorials and Prime numbers are well documented all over the interwebs and Wikipedia - it shouldn't be too hard to get working - but please don't blindly copy algorithms without understanding them - winning is not the only point of this challenge...
List of prime numbers: http://primes.utm.edu/lists/small/10000.txt
ASCII Table: http://www.cs.utk.edu/~pham/ascii.html
Submissions
- Please submit just a single source code file - I don't need things like Visual Studio project files. Just the core source and I will compile it for testing/judging.
- Submit by e-mailing the code as an attachment to [email protected] and post in this thread to confirm your submission
Judging
I will judge submissions based on correctness - i.e I will test them against new inputs and if i get the right secret message out that's good.
My entry is obviously exempt. Assuming there are > 1 correct submissions then I will select based on a combination of efficiency and code quality, language choice will effect efficiency so I wont use just that.
I will post all submission code up here once the deadlines gone and justify the winner selection.
===============================
Good luck and I really hope there > 1 submissions for this
You may use this thread for any questions or help on the stages etc
Prize: The winner gets a £5.00 steam purchase of your choice or £5.00 to a charity of your choice.
*** (This isn't as hard as it looks - just a long and verbose post!) ***
The idea of a programming contest was brought up a while ago and never came back, so I adapted a contest I made for uni a while back and hopefully it will work well here so we can do future ones
The challenge is hopefully a good mix between not too easy and not too hard while being slightly tricky. I wrote a solver in about 4-5 hours in about 230 lines of Python, and that was a hacky unoptimized mess - so it's a good project. Comp will run for about 3 weeks so hopefully enough people will submit entries ** Revisions/Errors **
[05/12/10] For Stage 1 - there are two values of n under 1.5 million that produce the largest chain length. You need to go with the smallest of the two - confirm your answers here http://www.jcsecurity.co.uk/ocuk.html
(Apologies for the mistake, it's tricky getting everything perfect!)
Competition Close: 15:00 on 27/12/10 - Winner Announced: 15:00 28/12/10
Rules:
- You may use any language you wish so long as it is executable from a Windows or Linux command line prompt and there should be no GUI (basic command line only)
Typically I would advise C/C++/C#/Python, please check if you want to go with something else first just to make sure. You must use standard language only, i.e no third party libs etc.
- The only major rule is no pre-computing of answers is allowed, it must be done dynamically at run time.
- Please don't cheat and copy code directly from the net, at least without understanding it fully
The Challenge:
Ok the goal of this challenge is to work out a 10 character password to unlock a one-time-pad encrypted secret message. Each of the 10 characters is found by solving sub challenges of varying difficulty.
Your program will take 10 numbers representing the secret message as input command line arguments and will output the decrypted message. The numbers are ascii codes for the 10 characters of the ciphertext. Don't worry about the decryption, it's a very simple XOR operation which is 1 line of code in most languages and is fully explained below (The main focus is on the 10 challenges). So, you need to solve 10 challenges to get all 10 characters of the password, then you can decrypt the secret and profit.
Your program should run as follows: "myProg.exe n1 n2 n3 n4 n5 n6 n7 n8 n9 n10" and it should output "Secret Message: ..." It will also be helpful if you print out the results from each of the 10 stages.
Here is two sets of input ciphertexts / numbers you can use to test the program with, once you get everything correct, you will recognise the decrypted secret message easily.
Set 1: 234, 103, 91, 136, 62, 119, 95, 55, 191, 19
Set 2: 233, 97, 75, 151, 62, 102, 69, 63, 191, 26
So for set 1, you should run your prog as "myProg.exe 234 103 91 136 62 119 95 55 191 19" and you should get out "Secret Message: ----------".
Here are the 10 sub-challenges, some follow on from each other and some are individual.
Stage 1 (medium/easy)
This is known as the 3n+1 or Collatz conjecture problem and is a sequence defined as follows:
If n is even then: n = n/2
Else if n is odd then: n = 3n + 1
The sequence finishes when: n=1
So following these simple rules, if we pick a first number for n to begin the sequence as n = 10 - it creates the following sequence:
eg (n=10) 10 - > 5 -> 16 -> 8 -> 4 -> 2 -> 1 (Chain length: 7)
eg (n=13) 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (Chain length: 10)
You need to work out which starting value of n produces the longest sequence chain where n is greater than 0 and less than or equal to 1500000 (1.5 million). NB: There are two values that produce the largest chain, go with the smaller of the two.
The starting value (n) that makes the longest chain is the answer to this stage. NB: This will take a while to crunch the numbers when executing).
Stage 2 (medium)
Firstly work out (stage1Answer % 9999), that is, take your answer to stage 1 modulus 9999. This effectively transforms a number into the range 0-9999 and makes it easier to work with for this question. % will take the modulus in most languages.
Now make an algorithm to work out the number of letters it would take to represent this result number in written form, ignoring spaces, hyphens and commas but including 'and'. It will need to work with any number between 0 and 9999.
For example, if the result from stage 1 mod 9999 was 189:
Then 189 - "One hundred and eighty nine" = 23 (and is included in the count)
Eg(1). 435 - "four hundred and thirty five" = 24
Eg(2) 16 - "sixteen" = 7
Eg(3) 3017 - "three thousand and seventeen" = 25
The number of letters needed to represent your number is the answer to this stage. This is an interesting thing to code
Stage 3 (easy)
Taking your answer from part 2 and add 1337 to it. Take this result and add all the individual digits together to produce a sum.
e.g 27 + 1337 = 1364 = 1 + 3 + 6 + 4 = 14
eg(1) 145 + 1337 = 1482 = 1 + 4 + 8 + 2 = 15
eg(2) 1734 + 1337 = 3071 = 3 + 0 + 7 + 1 = 11
The sum of the digits is your answer to this stage.
Stage 4 (medium)
Taking your answer from part 3 and work out the factorial of that number.
Factorial is defined as n! = n(n-1) * ... * 2 * 1
and n = stage3Answer
eg(1) 5! = 5 * 4 * 3 * 2 * 1 = 120
eg(2) 3! = 3 * 2 * 1 = 6
The result is the answer to this stage.
Stage 5 (med/hard)
Find the 13370th prime number - you will need to use an algorithm to work out if a number is prime or not via a loop.
A number is prime if it divides only by itself and 1. Google is your friend. This must be done dynamically - no hardcoding the prime number!
The prime number is the answer to this stage.
Stage 6 (easy)
Take the 13370th prime from part 5 and work out the modulus 9999 of it. Then work out the number of letters needed to represent it in word form. This is the same as part 2.
eg: Prime number 2 % 9999 = two = 3
The number of letters is your answer to this stage.
Stage 7 (easy)
Taking your answer from part 6 add together the individual digits to calculate a sum, this is the same as stage 3.
e.g 3 = 3
e.g 564 = 5+6+4 = 15
This sum is the answer to this stage.
Stage 8 (medium)
Find the sum of all the numbers below 5000 that are multiples of 3 or 5.
e.g Below 10 - all multiples of 3 or 5 below 10 are 3,5,6,9 - the sum is 23.
The sum is your answer to this stage.
Stage 9 (hard)
Work out the sum of all primes below 2.5 million - this can use your prime testing algorithm from stage 5 expect around 3 minutes computational time (if your algorithms any good!).
e.g Sum of all primes below 10 - Primes are: 2,3,5,7 = 2+3+5+7 = 17
The sum is the answer to this stage.
Stage 10 (easy)
Work out the the sum of the individual digits in the answer to stage 9.
E.g if the sum from stage 9 is 751 then the answer to this stage is 7+5+1 = 13.
-------------------------------------
11 - The End - (medium)
Ok by now you should have code in place to calculate 1 integer answer for each of the 10 challenges above. Now it is time to use these to decrypt the secret and win the game.
This is basic XOR encryption (one-time-pad) and is a very secure (not now, as hopefully you know the key!).
Firstly you need to transform your 10 answers into valid keys by taking them modulo 255 As follows:
Code:
Key1 = Stage1Answer % 255
Key 2 = Stage2Answer % 255
...
Key 10 = Stage10Answer % 255Your program took 10 numbers as input arguments, you now need to XOR each of those given numbers with each of the keys you made above. XORing the first input arg with the answer to stage 1 (mod 255) will give you the first letter of the secret message as an ASCII number.
This should clear up any confusion (% is the modulus operator):
Code:
(Stage 1 Answer % 255 ) XOR Arg 1 = First Character of Secret Message
(Stage 2 Answer % 255 ) XOR Arg 2 = Second Character of Secret Message
...
(Stage 10 Answer % 255 ) XOR Arg 10 = Last Character of Secret MessageYour program should print out the complete secret message. Note - XOR will give you a number in ASCII, you need to print this number as a character - this is well documented on Google e.g "ascii number to character".
Hints:
The % symbol is the modulus operator in most languages, e.g 5 % 255 will give you 5 mod 255. So working out the modulus is no extra work for you.
The ^ symbol is the XOR operator in most languages e.g 5 ^ 8 will give you 5 XOR 8. So working out the XOR decryption is no extra work for you.
Factorials and Prime numbers are well documented all over the interwebs and Wikipedia - it shouldn't be too hard to get working - but please don't blindly copy algorithms without understanding them - winning is not the only point of this challenge...
List of prime numbers: http://primes.utm.edu/lists/small/10000.txt
ASCII Table: http://www.cs.utk.edu/~pham/ascii.html
Submissions
- Please submit just a single source code file - I don't need things like Visual Studio project files. Just the core source and I will compile it for testing/judging.
- Submit by e-mailing the code as an attachment to [email protected] and post in this thread to confirm your submission
Judging
I will judge submissions based on correctness - i.e I will test them against new inputs and if i get the right secret message out that's good.
My entry is obviously exempt. Assuming there are > 1 correct submissions then I will select based on a combination of efficiency and code quality, language choice will effect efficiency so I wont use just that.
I will post all submission code up here once the deadlines gone and justify the winner selection.
===============================
Good luck and I really hope there > 1 submissions for this
You may use this thread for any questions or help on the stages etc
Last edited:
mine takes 3 mins from start to finish, on an old box though if that's a good enough excuse...
.
.