XSEDE12contest secret message

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Secret Message

This problem was inspired by Project Euler Problem 185.

Encrypting and decrypting messages has been a long standing use of a supercomputer of the day. While not not a state secret cipher, this problem provides a message in a message in a message to uncover. The moral of the story is while there is a well established place for high level highly abstracted languages, algorithmic and performance issues may sometimes dictate other solutions. This problem challenges you to discover algorithm(s) to simplify and solve a well defined logic puzzle, given that for a contest lasting only a few hours, a brute force algorithm could take days of run-time to complete.

Technology

Required tools

• Programming ability
• Understanding of algorithms, data structures, and complexity analysis

Suggested tools

• Use of MPI (Message Passing Interface) or OpenMP or CUDA (Compute Unified Device Architecture)

Description

• Use LittleFe to code, run and solve the following logic problem:

This problem is like the Project Euler 185 (Number mind) problem, except instead of numbers, lowercase letters are used. The integer following each sequence of 15 letters reflects the number of right characters, in the right position.

This problem could have 0, just 1, or possibly many solutions

```whatanswersbein 3
ithecareemplore 3
befreedjustlike 0
howsailoronceto 2
windsaidfreedom 1
vvvvvvvvvvvvvvv 0
naryawordharmed 2
viaourmakingall 2
vvvvvvvvvvvvvvv 0
patternsofgreat 2
worthneedseento 1
beelsefriendnot 0
willtimebetoyou 0
vvvvvvvvvvvvvvv 0
abandonnohopeor 1
startyounotthis 1
vvvvvvvvvvvvvvv 0
sphinxofblackqu 2
artzjudgemyvowq 1
uickzephyrsblow 0
vexingdaftjimpa 1
ckmyboxwithfive 0
dozenliquorjugs 1
wequicklyseized 0
theblackaxleand 2
justsaveditfrom 1
goingpasthimthe 2
quickbrownfoxju 0
mpsoveralazydog 1
```

In a folder named "SecretMessage":

• Your report of work in an ASCII text file named "ReadMe"
• The source code used to solve the problem

What the graders will be looking for:

• Your report should include a description of the steps taken by the team in working to obtain results. State the problems encountered, the possible solutions considered and tried, and the solution that was implemented and benchmarked.
• Discussion of algorithmic and programming tactics taken to minimize run-time.
• Your report should also include observations on additional steps that might be taken to reduce the overall run-time.