Solved

Recursive Word Builder?

Posted on 2012-03-23
7
264 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 500 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
Forrester Webinar: xMatters Delivers 261% ROI

Guest speaker Dean Davison, Forrester Principal Consultant, explains how a Fortune 500 communication company using xMatters found these results: Achieved a 261% ROI, Experienced $753,280 in net present value benefits over 3 years and Reduced MTTR by 91% for tier 1 incidents.

 
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

The Orion Papers

Are you interested in becoming an AWS Certified Solutions Architect?

Discover a new interactive way of training for the exam.

Question has a verified solution.

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

More often than not, we developers are confronted with a need: a need to make some kind of magic happen via code. Whether it is for a client, for the boss, or for our own personal projects, the need must be satisfied. Most of the time, the Framework…
Wouldn’t it be nice if you could test whether an element is contained in an array by using a Contains method just like the one available on List objects? Wouldn’t it be good if you could write code like this? (CODE) In .NET 3.5, this is possible…
There are cases when e.g. an IT administrator wants to have full access and view into selected mailboxes on Exchange server, directly from his own email account in Outlook or Outlook Web Access. This proves useful when for example administrator want…
There's a multitude of different network monitoring solutions out there, and you're probably wondering what makes NetCrunch so special. It's completely agentless, but does let you create an agent, if you desire. It offers powerful scalability …

705 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