?
Solved

Recursive Word Builder?

Posted on 2012-03-23
7
Medium Priority
?
271 Views
Last Modified: 2012-03-26
I am trying to build an application that will read a pattern and build "words" from two arrays. One array is full of consonants, and one array is full of vowels.

Dim aryConsonants As String() = {"b", "d", "f", "g", "k", "l", "m", "p", "r", "s", "t", "v", "w", "x", "z"}
Dim aryVowels As String() = {"a", "e", "i", "o", "u"}

Open in new window


I need to figure out how to create a function (maybe a recursive one?) where I can pass it a pattern like: "CVCV" and it will look through these letters and create every possible combination from the arrays that matches the pattern.

Some example words for CVCV (consonant-vowel-consonant-vowel):

LANI
CAMA
DIPO

If we pass it this pattern: CVV, it would create words like:

LEI
RAO
TIE

How do I structure this function? I am having trouble with the logic and structure.
0
Comment
Question by:DrDamnit
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
7 Comments
 
LVL 86

Accepted Solution

by:
Mike Tomlinson earned 2000 total points
ID: 37760088
Try this out:  *Form has a TextBox, Button, ListBox and a BackgroundWorker*
Public Class Form1

    Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load
        Dim aryVowels As String() = {"a", "e", "i", "o", "u"}
        Dim aryConsonants As String() = {"b", "c", "d", "f", "g", "h", "j", "k", "l", "m", "n", "p", "q", "r", "s", "t", "v", "w", "x", "y", "z"}

        For Each vowel As String In aryVowels
            Dim ltr As New Letter
            ltr.Value = vowel
            ltr.Type = Letter.LetterType.Vowel
            Letter.Letters.Add(ltr)
        Next

        For Each consonant As String In aryConsonants
            Dim ltr As New Letter
            ltr.Value = consonant
            ltr.Type = Letter.LetterType.Consonant
            Letter.Letters.Add(ltr)
        Next
    End Sub

    Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
        ListBox1.Items.Clear()
        Button1.Enabled = False
        BackgroundWorker1.RunWorkerAsync(TextBox1.Text)
    End Sub

    Private Sub BackgroundWorker1_DoWork(sender As Object, e As System.ComponentModel.DoWorkEventArgs) Handles BackgroundWorker1.DoWork
        Dim pattern As String = e.Argument.ToString.Trim.ToUpper
        Dim words As Dictionary(Of String, Object) = Nothing
        If pattern.Replace("C", "").Replace("V", "") = "" Then
            words = New Dictionary(Of String, Object)
            For Each ltr As Letter In Letter.Letters
                ltr.Visit(pattern, 0, "", words)
            Next
        End If
        e.Result = words
    End Sub

    Private Sub BackgroundWorker1_RunWorkerCompleted(sender As Object, e As System.ComponentModel.RunWorkerCompletedEventArgs) Handles BackgroundWorker1.RunWorkerCompleted
        If Not IsNothing(e.Result) Then
            Dim words As Dictionary(Of String, Object) = DirectCast(e.Result, Dictionary(Of String, Object))
            ListBox1.BeginUpdate()
            ListBox1.Items.AddRange(words.Keys.ToArray)
            ListBox1.EndUpdate()
            MessageBox.Show("Done!")
        Else
            MessageBox.Show("Invalid Pattern")
        End If
        Button1.Enabled = True
    End Sub

    Public Class Letter

        Public Enum LetterType
            Vowel
            Consonant
        End Enum

        Public Value As String
        Public Type As LetterType
        Public Shared Letters As New List(Of Letter)

        Public Overrides Function ToString() As String
            Return Value
        End Function

        Public Sub Visit(ByVal pattern As String, ByVal patternPosition As Integer, ByVal word As String, ByVal words As Dictionary(Of String, Object))
            If patternPosition = pattern.Length Then
                If Not words.ContainsKey(word) Then
                    words.Add(word, Nothing)
                End If
            Else
                Dim Code As String = pattern.Substring(patternPosition, 1)
                If (Code = "V" AndAlso Me.Type = LetterType.Vowel) OrElse (Code = "C" AndAlso Me.Type = LetterType.Consonant) Then
                    word = word & Me.Value
                    For Each ltr As Letter In Letter.Letters
                        ltr.Visit(pattern, patternPosition + 1, word, words)
                    Next
                End If
            End If
        End Sub
    End Class

End Class

Open in new window

0
 
LVL 32

Author Closing Comment

by:DrDamnit
ID: 37760738
Wow. Above and beyond man. Thank you very much.

I will be F8 - stepping through this until I figure out how / why it works. GREATLY appreciated.
0
 
LVL 32

Author Comment

by:DrDamnit
ID: 37760746
You're using background workers, so F8 Steps aren't helping me watch the process. Can you teach me what the concept is behind this? The code is quite elegant. I know what it's doing, but don't know how / why.
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 86

Expert Comment

by:Mike Tomlinson
ID: 37760889
I'm not quite sure how to explain it...describing how a recursive algorithm works is always tricky.  =\

How do you plan on using this?  After more than five characters (approx) in the pattern, the running time is going to get quite long and the return set is going to get huge.
0
 
LVL 86

Expert Comment

by:Mike Tomlinson
ID: 37760893
Here's a more compact version:
Public Class Form1

    Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load
        Dim aryVowels As String() = {"a", "e", "i", "o", "u"}
        Dim aryConsonants As String() = {"b", "c", "d", "f", "g", "h", "j", "k", "l", "m", "n", "p", "q", "r", "s", "t", "v", "w", "x", "y", "z"}

        For Each vowel As String In aryVowels
            Dim ltr As New Letter
            ltr.Value = vowel
            ltr.Type = Letter.LetterType.Vowel
            Letter.Letters.Add(ltr)
        Next

        For Each consonant As String In aryConsonants
            Dim ltr As New Letter
            ltr.Value = consonant
            ltr.Type = Letter.LetterType.Consonant
            Letter.Letters.Add(ltr)
        Next
    End Sub

    Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
        ListBox1.DataSource = Nothing
        ListBox1.Items.Clear()
        Button1.Enabled = False
        BackgroundWorker1.RunWorkerAsync(TextBox1.Text)
    End Sub

    Private Sub BackgroundWorker1_DoWork(sender As Object, e As System.ComponentModel.DoWorkEventArgs) Handles BackgroundWorker1.DoWork
        Dim pattern As String = e.Argument.ToString.Trim.ToUpper
        Dim words As Dictionary(Of String, Object) = Nothing
        If pattern.Replace("C", "").Replace("V", "") = "" Then
            words = New Dictionary(Of String, Object)
            For Each ltr As Letter In Letter.Letters
                ltr.Visit(pattern, 0, "", words)
            Next
        End If
        e.Result = words.Keys.ToList
    End Sub

    Private Sub BackgroundWorker1_RunWorkerCompleted(sender As Object, e As System.ComponentModel.RunWorkerCompletedEventArgs) Handles BackgroundWorker1.RunWorkerCompleted
        If Not IsNothing(e.Result) Then
            Dim words As List(Of String) = DirectCast(e.Result, List(Of String))
            ListBox1.DataSource = words
            MessageBox.Show("Done!")
        Else
            MessageBox.Show("Invalid Pattern")
        End If
        Button1.Enabled = True
    End Sub

    Public Class Letter

        Public Enum LetterType
            Vowel
            Consonant
        End Enum

        Public Value As String
        Public Type As LetterType
        Public Shared Letters As New List(Of Letter)

        Public Sub Visit(ByVal pattern As String, ByVal patternPosition As Integer, ByVal word As String, ByVal words As Dictionary(Of String, Object))
            Dim Code As String = pattern.Substring(patternPosition, 1)
            If (Code = "V" AndAlso Me.Type = LetterType.Vowel) OrElse (Code = "C" AndAlso Me.Type = LetterType.Consonant) Then
                word = word & Me.Value
                If word.Length = pattern.Length Then
                    If Not words.ContainsKey(word) Then
                        words.Add(word, Nothing)
                    End If
                Else
                    For Each ltr As Letter In Letter.Letters
                        ltr.Visit(pattern, patternPosition + 1, word, words)
                    Next
                End If
            End If
        End Sub
    End Class

End Class

Open in new window

0
 
LVL 32

Author Comment

by:DrDamnit
ID: 37768556
This was great. To learn what you did, I built a different, yet similar program to do something else entirely different, and I think I have figured about half of it out.

The one bit I cannot figure out is how you are rotating based on the pattern like an odometer...
0
 
LVL 86

Expert Comment

by:Mike Tomlinson
ID: 37768858
In my last post, lines 72 thru 74 are what allows it to recursively iterate through all the letters and see if they fit the pattern in the next available slot.
0

Featured Post

On Demand Webinar: Networking for the Cloud Era

Did you know SD-WANs can improve network connectivity? Check out this webinar to learn how an SD-WAN simplified, one-click tool can help you migrate and manage data in the cloud.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In my previous two articles we discussed Binary Serialization (http://www.experts-exchange.com/A_4362.html) and XML Serialization (http://www.experts-exchange.com/A_4425.html). In this article we will try to know more about SOAP (Simple Object Acces…
The ECB site provides FX rates for major currencies since its inception in 1999 in the form of an XML feed. The files have the following format (reducted for brevity) (CODE) There are three files available HERE (http://www.ecb.europa.eu/stats/exch…
In this brief tutorial Pawel from AdRem Software explains how you can quickly find out which services are running on your network, or what are the IP addresses of servers responsible for each service. Software used is freeware NetCrunch Tools (https…
How to fix incompatible JVM issue while installing Eclipse While installing Eclipse in windows, got one error like above and unable to proceed with the installation. This video describes how to successfully install Eclipse. How to solve incompa…
Suggested Courses

765 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question