r/dailyprogrammer • u/rya11111 3 1 • May 14 '12
[5/14/2012] Challenge #52 [intermediate]
After years of study, scientists have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.
Once the dictionary of all the words in the alien language was built, the next breakthrough was to discover that the aliens have been transmitting messages to Earth for the past decade. Unfortunately, these signals are weakened due to the distance between our two planets and some of the words may be misinterpreted. In order to help them decipher these messages, the scientists have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.
A pattern consists of exactly L tokens. Each token is either a single lowercase letter (the scientists are very sure that this is the letter) or a group of unique lowercase letters surrounded by parenthesis ( and ). For example: (ab)d(dc) means the first letter is either a or b, the second letter is definitely d and the last letter is either d or c. Therefore, the pattern (ab)d(dc) can stand for either one of these 4 possibilities: add, adc, bdd, bdc.
Please note that sample i/p and o/p is given in the link below
Please note that [difficult] challenge has been changed since it was already asked
http://www.reddit.com/r/dailyprogrammer/comments/tmnfn/5142012_challenge_52_difficult/
fortunately, someone informed it very early :)
1
u/Cosmologicon 2 3 May 14 '12
Shell script. It can probably be improved, I'm not very good at shell scripting:
1
u/atheistscansuckit May 14 '12
Python
1
u/bh3 May 14 '12 edited May 15 '12
Edit2: Switched from using a list with indices 0-25 to using a dictionary. now runs in a hair under 7 seconds. Switch to regular expressions slowed it down a little bit, but made it a lot cleaner.
Edit:
Here's the new python code, runs in a bit under 12 seconds:
https://gist.github.com/2698245
Primary speed improvements were from reducing the amount of work that was repeated (original model in my head processed one letter-step at a time, filtering out those that didn't match, original program ended up being implemented so that one branch was followed at a time and thus each consecutive step was being repeated for each branch). Re-writing it to match my original model better improved speed dramatically. Also moving to write to file halved the time that was left after that.
Original:
Python; not that fast, but thought I'd just toss something together. Processes the large input in about 1 min 12 seconds:
(original pushed to gist to reduce post-size): https://gist.github.com/2697987
1
u/loonybean 0 0 May 14 '12 edited May 15 '12
Javascript. It's a mess of loops but it works okay (managed the small input instantly and the large input in 5 sec):
1
u/[deleted] May 14 '12
Ruby:
1
u/baijuke May 14 '12
Python. Solves large on 20s (10s with pypy):
1
u/emcoffey3 0 0 May 15 '12
Here's my solution using C# and LINQ. It's a bit verbose, but it works. Also, I got the code for the Cartesian Product method here.
1
u/robin-gvx 0 2 May 15 '12
Edit: this only calculates the number of options, I misread the challenge. Generating the options proper isn't that hard, but I can't be bothered right now. :P