consonants.....

Eradest · 2008-09-15 16:48:13

Hey guys!
I have a little programming problem, wonder if you can come up with a solution.

It's a simple game: You take a word, e.g. "Linux", then strip off all the vowels (->Lnx) and append the number of missing vowels: "Lnx (3)"

Now I want to write a program (preferably in python, the string operation functions are quite good there) that generates all possible combinations of words.

Little trivial and senseless example:

given: "b (2)"

expected output:
aab
aeb
aib
aob
aub
eab
eeb
...
...
aba
abe
abi
abo
abu
eba
ebe
...
...
baa
bae
bai
...

Now, how can I achieve that? I already tried some recursive approaches, none of which turned out to be promising.
The main problem is that you have to loop through both the positions of the vowels and the vowels itself [a,e,i,o,u].

What do you think?

Dusty · 2008-09-15 17:09:58

You can do it in a triple nested loop, but this also looks like a great place to utilize dynamic programming.

Dusty

Eradest · 2008-09-15 17:12:35

what do you mean, dynamic programming?

Cerebral · 2008-09-15 17:23:52

http://20bits.com/2007/05/08/introducti … ogramming/ <-- he might mean that (first response that came up when I googled for "dynamic programming python")

madhatter · 2008-09-15 22:03:32

Question: Is this a pure programming challenge, or do you need such a script to help you solve such puzzles?
If it's the latter case, I'm guessing you'd need something like a dictionary lookup to filter the big number of possible combinations. If so wouldn't it be easier to just remove the consonants of such an wordlist and then compare?

Sorry, if my question sounds stupid but I wonder why anyone would ask for a solution if it's a challenge, as that would defeat it's purpose.

Xyne · 2008-09-15 22:08:18

EDIT: I hadn't considered that this could be a homework problem until reading the replies following this post... so I've encrypted the program for now
I used recursion to accomplish this in a systematic way (rather than generate all possible mutations and filter them).
Someone remind me to post the encryption method and password later if you want to see the script.

I took this as a fun challenge and got sidetracked implementing it in Perl.

vowel_permutator.pl

U2FsdGVkX1+HwM/GMBnyLLdNfu5fPKsZUIqyA9hurGrljGNIaSM/ecQ8uLPIfLnW
vPAfaoHXwoVfMNx9N2YCjQ76LuAH1SK7pW8fQFF4r0ySMVQYbuy+AQYX93t44eS0
CBHvVzihf4rn7lrihAw9+JgWeYlvsQtT2KJa7WX4m3hYxhIv/mfK2lV4RZRJlENK
nOTfVOzWDJbiJXFqk4eVlEPJOUtCoZgu2EZGo0o0hwpERm4L95phoXIMX93/LDBT
ZW3jKhWx5CQIWmVPaP3bKVStLmvUA1OFxjF0UdMo075z0DPlrMY3gj5RqxB1xVrP
xnYL++uFKnYfYGTc/MTVWRbQFUoQ4Z6xuRdciZUB7JRpiGVitOl2qLTh7Ik1sj/4
mjDH+YBQUE5ev2MLVHTAUylmFv2gKA05MACPq9X5pCm6c0zz3mQUApxfkZGAZ+B7
yq2meVEkjwcS19fxbL1vSnispghCuRlf1YymmV/eD2abJ/O2S9R7hd/wsV2CTtqW
AKyozRmraIUHyFtNrfg/jskpMs8ubZSykxVJt7HskCSu8ojXogH5xtlyhroT/i/l
wdxfhAPO6wWmxYy5W4/vsbyvRgD8+lAXZxLH7EMaWYK35PA+icGQOTgbfcS0brhG
dqOgw+LwFmPouRaOa2zL6Q3sFHYQykEXpRaQkuA5P9qH4k9AK3d9nUE/gMk8Y8az
9eKEbYu3jqsqmUIxcLYZRwvvZ69G5/q/YhcObisNABSUPCf9o3oIlMTuTX1lvAY/
OR/sOjjIV9K0PZIZKK8Ho94oKgiHmI+c+qWiSV6smXk=

Called with:

vowel_permutator.pl b 2

Sample output:

aab
aeb
aib
aob
aub
aba
abe
abi
abo
abu
eab
eeb
eib
eob
eub
eba
ebe
ebi
ebo
ebu
iab
ieb
iib
iob
iub
iba
ibe
ibi
ibo
ibu
oab
oeb
oib
oob
oub
oba
obe
obi
obo
obu
uab
ueb
uib
uob
uub
uba
ube
ubi
ubo
ubu
baa
bae
bai
bao
bau
bea
bee
bei
beo
beu
bia
bie
bii
bio
biu
boa
boe
boi
boo
bou
bua
bue
bui
buo
buu

"lnx 3" => 2500 permutations

Last edited by Xyne (2008-09-15 23:57:32)

Allan · 2008-09-15 23:11:49

This isn't homework is it?

Dusty · 2008-09-15 23:34:45

I'm sure it is, that's why I only gave suggestions (plus I'm busy). Its a really good homework problem for someone studying recursion because the necessity of checking multiple positions stops it being a simple recursize problem and requires the student to think (ie: educate themselves). My guess is Exercise 4 on a 6 question lab. :-D

Dusty

Xyne · 2008-09-15 23:51:12

Allan wrote:

This isn't homework, is it?

Dusty wrote:

I'm sure it is, that's why I only gave suggestions.

Hadn't thought of that (saw problem -> tried to find solution -> posted results).

*edits previous post*

Last edited by Xyne (2008-09-15 23:58:40)

Eradest · 2008-09-16 13:19:08

madhatter wrote:

Question: Is this a pure programming challenge, or do you need such a script to help you solve such puzzles?

Both: This is a board (in the sense of bbs) game played in a rather private community, so I decided to test my (as you have correctly noticed) rather untrained programming skills to write something that generates all possible solutions. After a few hours I noticed myself that the sheer size of output would be big to handpick the results. So if you want to make this really usable you indeed have to implement a dictionary check.
I thought it would be easy enough, but turned out to be quite tricky. After serveral days of failed attempts, I decided I might ask here to get some hints.

You can believe me or not - and I must indeed admit this looks a lot like a homework - but I assure you it's not. However, as you seem quite convinced of my guilt, I do not see any way to prove the opposite (if you do, let me know). Even if I find a solution now, which I will continue to try to do, you can still blame me of just having posted the "school-solution".

Thanks a lot.

Xyne · 2008-09-16 18:44:34

Well, I didn't even suspect that it was a homework problem until two other posters mentioned the possibility (hadn't stopped to think about it). Having read your post, I now believe that it wasn't... you're actually looking for a way to cheat instead

jk

Save the encoded program in a file called "encoded.txt" then decrypt it with this (or whatever else you want to use):

openssl enc -d -base64 -aes-256-cbc -in encoded.txt

password: homer

Last edited by Xyne (2008-09-16 18:45:18)

Arch Linux

#1 2008-09-15 16:48:13

consonants.....

#2 2008-09-15 17:09:58

Re: consonants.....

#3 2008-09-15 17:12:35

Re: consonants.....

#4 2008-09-15 17:23:52

Re: consonants.....

#5 2008-09-15 22:03:32

Re: consonants.....

#6 2008-09-15 22:08:18

Re: consonants.....

#7 2008-09-15 23:11:49

Re: consonants.....

#8 2008-09-15 23:34:45

Re: consonants.....

#9 2008-09-15 23:51:12

Re: consonants.....

#10 2008-09-16 13:19:08

Re: consonants.....

#11 2008-09-16 18:44:34

Re: consonants.....

Board footer