Extract a common path

I have a series of path and i want to extract a common path from it to actually replace that common path to make a new physical path.

Can any body help me in designing algo for this purpose.

The series of path sample is as under.

FILE ID      FILE NAME            FILE PATHS
327      abc            $/Programs/Programs Components/Carb.iam
317      cdx            $/Programs/Programs Components/Carb Zip-Tie.ipt
318      xsdf            $/Programs/Programs Components/Carb Slide Boot.ipt
319      sdfs            $/Programs/Programs Components/Carb intake nipple.ipt
320      sdfsfd            $/Programs/Programs Components/Carb Slide.ipt
321      sdfs            $/Programs/Programs Components/5B666F3B-A1E2-5111-247F-92F4CEF9FCC5.ipt
322      sdf            $/Programs/Programs Components/Carb Highspeed needle.ipt
323      sdfs            $/Programs/Programs Components/Carb Intake plate.ipt
324      sdf            $/Programs/Programs Components/Carb Spring.ipt
325      sdfs            $/Programs/Programs Components/C48156DB-0031-1112-481C-A345A39E8D07.ipt
326      sdfs            $/Programs/Programs Components/Carb.ipt
369      sdfs            $/Programs/Programs Components/Carb Zip-Tie.ipt.dwf

I have tried a couple of things so far but not successful yet. I would appreciate a response from the expert community.

Thanks

Syed

snomiAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Bob LearnedCommented:
From this:

   $/Programs/Programs Components/Carb.iam

You want just this:

  Carb.iam

Bob
snomiAuthor Commented:
Hi,

lemme make the list bit interesting to tell u the result

FILE ID      FILE NAME            FILE PATHS
327      abc            $/Programs/Programs Components/Carb.iam
317      cdx            $/Programs/Programs Components/Carb Zip-Tie.ipt
318      xsdf            $/Programs/Programs Components/Carb Slide Boot.ipt
319      sdfs            $/Programs/Programs Components/Carb intake nipple.ipt
320      sdfsfd            $/Programs/Programs Components/Carb Slide.ipt
321      sdfs            $/Programs/Programs Components/5B666F3B-A1E2-5111-247F-92F4CEF9FCC5.ipt
455      dsfds            $/Programs/Test/abc.zip
6588      sdfsdfsfd            $/Programs/Test/Beta/123.txt

the common path in the available file paths is "$/Porgrams"
I want to make a progam in vb.net to get this path from list of paths..

Do ask me again if it's not clear.

Regards

Nauman




Bob LearnedCommented:
Nauman,

Is this going be dynamic, so that you need to calculate the $/Programs, and not pre-determine it?

Bob
JavaScript Best Practices

Save hours in development time and avoid common mistakes by learning the best practices to use for JavaScript.

snomiAuthor Commented:
Hi Bob,

Yes its going to be dynamic. I have only created a sample to explain what i want. The file paths will have some common path.

i cannot predetermine anything .

Regards

Nauman
snomiAuthor Commented:
i am using Split funciton using back slash as the key thing.
But my program logic is not good.


Nauman
Bob LearnedCommented:
Experiment #1:

    Dim list As New ArrayList
    list.Add("$/Programs/Programs Components/Carb.iam")
    list.Add("$/Programs/Programs Components/Carb Zip-Tie.ipt")
    list.Add("$/Programs/Programs Components/Carb Slide Boot.ipt")
    list.Add("$/Programs/Programs Components/Carb intake nipple.ipt")
    list.Add("$/Programs/Programs Components/Carb Slide.ipt")
    list.Add("$/Programs/Programs Components/5B666F3B-A1E2-5111-247F-92F4CEF9FCC5.ipt")
    list.Add("$/Programs/Test/abc.zip")
    list.Add("$/Programs/Test/Beta/123.txt")

    ' Find shortest string.
    Dim shortestIndex As Integer = -1
    Dim shortestLength As Integer = Integer.MaxValue
    Dim itemCount As Integer = list.Count - 1
    For index As Integer = 0 To itemCount
      Dim item As String = list(index)
      If item.Length < shortestLength Then
        shortestLength = item.Length
        shortestIndex = index
      End If
    Next index

    ' Build a StringBuilder for efficiency with the shortest string.
    Dim match As New System.Text.StringBuilder(list(shortestIndex).ToString)

    ' Starting with the shortest string, repetively remove characters
    ' until a match can be found each of the list items.
    Dim done As Boolean = False
    While Not done

      Dim noMatchFound As Boolean = False

      For Each itemCurrent As String In list

        ' Check for no match.
        If Not itemCurrent.StartsWith(match.ToString) Then
          noMatchFound = True

          ' Remove one more character.
          match.Remove(match.Length - 1, 1)
          Exit For
        End If

      Next itemCurrent

      ' Determine if a common match was found, or not.
      ' If we run out of characters to match, then stop.
      If Not noMatchFound OrElse match.Length = 0 Then
        done = True
      End If

    End While


Bob

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Jeff CertainCommented:
Bob,

I like your approach. To make it more efficient, couldn't you remove any text after the last "/" in the shortest string prior to beginning your loop to remove characters?

Jeff
snomiAuthor Commented:
Don't u think the path separator "/"  should be used in place of finding the shortest path. That's what i am getting from the first "FOR LOOP"

Please guide me how are you going through this file paths.

Thanks

Nauman

Bob LearnedCommented:
@Chaosian:
Thanks, Jeff, for that added thinking.  I only thought about this solution for 5 seconds (Highlights the reason for more planning and thought).

Use System.IO.Path.GetDirectoryName(file) to get just the path name from the file name, and you'll benefit from not having to check those obvious ones.

Bob
Bob LearnedCommented:
Ok, Nauman, show me what you have.

Bob
snomiAuthor Commented:
Bob,

That's just a great algo to get the right common path. can u walk me through your code. I am sending the code what i used from urs. I just had to change couple of variables to get it working in mine. U are really good.

        Dim oFilePaths() As DocumentService.FilePath
        Dim oFilePath As DocumentService.FilePath

               Dim shortestIndex As Integer = -1
                Dim shortestLength As Integer = Integer.MaxValue
                Dim itemCount As Integer = oFilePaths.Length - 1

                For index As Integer = 0 To itemCount
                    Dim item As String = oFilePaths(index).Path
                    If item.Length < shortestLength Then
                        shortestLength = item.Length
                        shortestIndex = index
                    End If
                Next index

                ' Build a StringBuilder for efficiency with the shortest string.
                Dim match As New System.Text.StringBuilder(oFilePaths(shortestIndex).Path.ToString)

                ' Starting with the shortest string, repetively remove characters
                ' until a match can be found each of the list items.
                Dim done As Boolean = False
                While Not done

                    Dim noMatchFound As Boolean = False

                    For Each oFilePath In oFilePaths

                        ' Check for no match.
                        If Not oFilePath.Path.StartsWith(match.ToString) Then
                            noMatchFound = True
                            ' Remove one more character.
                            match.Remove(match.Length - 1, 1)
                            Exit For
                        End If

                    Next


                    ' Determine if a common match was found, or not.
                    ' If we run out of characters to match, then stop.
                    If Not noMatchFound OrElse match.Length = 0 Then
                        done = True
                    End If

                End While

Regards

Nauman

NOTE : Please tell me the way to close the question too after i accept the answer from you.

Thanks Again




Bob LearnedCommented:
Well, the way that I chose may not be the best way, but it was a quick experiment.

I determined that what you needed was to take a string, and then match it up against all the other strings in the list, looking for a combination of characters that will match all of the items.

The selection of string is unimportant, so I chose the shortest string to shorten the time it took to remove characters and find a match.

(1) Start with a string
(2) Match the string against all list items
(3) If the string doesn't match all the list items, then remove a character
(4) Keep going until you find a string that matches all the items, or you get an empty string.

Bob
snomiAuthor Commented:
Hi Bob,


Please tell me the way to close the question too after i accept the answer from you.


Nauman

Bob LearnedCommented:
You found it :)

Bob
snomiAuthor Commented:
yes i did, thanks :)

one more thing, if i want to parse through the Path by "/" back slash, what will be the modified form of code.
(somehow i am afraid that only "/" is the safest way to go. Do help me if my fears are correct or not)

Thanks

Nauman

It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Visual Basic.NET

From novice to tech pro — start learning today.