Solved

Recursive Word Builder?

Posted on 2012-03-23
7
249 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
  • 4
  • 3
7 Comments
 
LVL 85

Accepted Solution

by:
Mike Tomlinson earned 500 total points
Comment Utility
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
Comment Utility
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
Comment Utility
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
Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

 
LVL 85

Expert Comment

by:Mike Tomlinson
Comment Utility
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 85

Expert Comment

by:Mike Tomlinson
Comment Utility
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
Comment Utility
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 85

Expert Comment

by:Mike Tomlinson
Comment Utility
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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

A long time ago (May 2011), I have written an article showing you how to create a DLL using Visual Studio 2005 to be hosted in SQL Server 2005. That was valid at that time and it is still valid if you are still using these versions. You can still re…
It was really hard time for me to get the understanding of Delegates in C#. I went through many websites and articles but I found them very clumsy. After going through those sites, I noted down the points in a easy way so here I am sharing that unde…
Excel styles will make formatting consistent and let you apply and change formatting faster. In this tutorial, you'll learn how to use Excel's built-in styles, how to modify styles, and how to create your own. You'll also learn how to use your custo…
In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're interested in additional methods for monitoring bandwidt…

762 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now