RegEx builder algorithm for MAC address list

[spudw2k]

I've got a tricky one here.  So I have a sorted list of MAC addresses.  I want to write an algorithm that will produce a regular expression that will match each unique MAC address.  

 

For example:

list
12-34-56-34-14-91
12-34-56-80-04-54
12-34-56-80-93-11
12-34-56-EA-76-0F
12-34-56-EA-76-9F
12-34-56-EA-78-11

would yield
12-34-56-(34-14-91|80-(04-54|93-11)|EA-(76-(0F|9F)|78-11))

Demo: https://www.regextester.com/?fam=112582

 

I have some ideas, but I wanted to field this to the forum in case anyone has better ideas or approaches.  

[TheDcoder]

  On 11/20/2019 at 5:20 AM, spudw2k said:

I want to write an algorithm that will produce a regular expression that will match each unique MAC address.

Expand  

If you are planning to write an algorithm for generating regular expressions for matching unique strings in a given set, you can just concatenate all strings with the | meta character which acts as a logical or in your regex.

[spudw2k]

I could, but I am trying to reduce the string length as well.

[TheDcoder]

@spudw2k Okay, good luck

[iamtheky]

Purely pseudo stream of thought, but i think this path may eventually get there

#include<array.au3>

$str = '12-34-56-34-14-91' & @CR & _
'12-34-56-80-04-54' & @CR & _
'12-34-56-80-93-11' & @CR & _
'12-34-56-EA-76-0F' & @CR & _
'12-34-56-EA-76-9F' & @CR & _
'12-34-56-EA-78-11'

local $aSplit[0][6] , $sOut

_ArrayAdd($aSplit , $str , 0 , "-" , @CR)

For $i = 0 to 5

   $sOut &= "(" &  _ArrayToString(_ArrayUnique($aSplit , $i , 0 , 0 , 0) , "|") & ")-"

Next

msgbox(0, '' , stringtrimright($sOut , 1))

 

[UEZ]

Here my try:

expandcollapse popup

#include <array.au3>

Global $sMAC =  '12-34-56-34-14-91' & @CR & _
                '12-34-56-80-04-54' & @CR & _
                '12-34-56-80-93-11' & @CR & _
                '12-34-56-EA-76-0F' & @CR & _
                '12-34-56-EA-76-9F' & @CR & _
                '12-34-56-EA-78-11'

Global $aMACs = StringRegExp($sMAC, "\b[[:xdigit:]-]+\b", 3)

Global $aMACs_splitted[UBound($aMACs)][6], $x, $xx, $y
For $y = 0 To UBound($aMACs) - 1
    $aTmp = StringSplit($aMACs[$y], "-", 3)
    For $x = 0 To UBound($aTmp) - 1
        $aMACs_splitted[$y][$x] = $aTmp[$x]
    Next
Next
Global $sRegEx
For $x = 0 To UBound($aMACs_splitted, 2) - 1
    Dim $aTmp[UBound($aMACs_splitted)]
    For $y = 0 To UBound($aMACs_splitted) - 1
        $aTmp[$y] = $aMACs_splitted[$y][$x]
    Next
    $aTmp = _ArrayUnique($aTmp)
    If $aTmp[0] = 1 Then
        $sRegEx &= $aTmp[1]
    Else
        $sRegEx &= "("
        For $xx = 1 To $aTmp[0]
            $sRegEx &= $aTmp[$xx] & "|"
        Next
        $sRegEx = StringTrimRight($sRegEx, 1) & ")"
    EndIf
    $sRegEx &= "-"
Next
$sRegEx = StringTrimRight($sRegEx, 1)
ConsoleWrite("RegEx pattern: " & $sRegEx & @CRLF)

 

[jchd]

@UEZ that produces a pattern which matches entries not in the input table, like 12-34-56-34-04-11

[UEZ]

  On 11/20/2019 at 5:19 PM, jchd said:

@UEZ that produces a pattern which matches entries not in the input table, like 12-34-56-34-04-11

Expand  

Yep, the idea doesn't work this way. Thanks for hint!

[jchd]

The expected result has an intrisic recursive nature, so the natural code structure shall be (head-first) recursive.

I'll try to write something.

[UEZ]

  On 11/20/2019 at 7:02 PM, jchd said:

The expected result has an intrisic recursive nature, so the natural code structure shall be (head-first) recursive.

I'll try to write something.

Expand  

Yes, I'm just googling for something like "stop if first expression is false"

[Nine]

Seems to be working, at least with the provided string :

expandcollapse popup

#include <array.au3>

$str = _
  '12-34-56-34-14-91' & @CR & _
  '12-34-56-80-04-54' & @CR & _
  '12-34-56-80-93-11' & @CR & _
  '12-34-56-EA-76-0F' & @CR & _
  '12-34-56-EA-76-9F' & @CR & _
  '12-34-56-EA-78-11'

Global $aSplit[0][6]
_ArrayAdd($aSplit , $str , 0 , "-" , @CR)
Global Const $iMaxRow = Ubound($aSplit,1)-1,$iMaxCol = Ubound($aSplit,2)-1
Global $count = 0, $sRegExp = "", $iLevel = 0

Solution (0,0,0, $iMaxRow,$iMaxCol)
MsgBox ($MB_SYSTEMMODAL,"",StringTrimRight ($sRegExp,1))

Func Solution ($lvl,$sr, $sc, $er, $ec)
  $v = Same ($sr,$sc,$er)
  If $sr <> $er and $v <> $er and $lvl = 1 Then
    $sRegExp &= "("
    $iLevel += 1
  EndIf
  $sRegExp &= $aSplit[$sr][$sc]
  if $sc < $ec Then
    $sRegExp &= "-"
    Solution (1,$sr, $sc+1, $v, $ec)
  EndIf
  if $v < $er then
    $sRegExp &= "|"
    Solution (2,$v+1, $sc, $er, $ec)
    $sRegExp &= ")"
  EndIf
EndFunc

Func Same ($sr, $c, $er)
  For $r = $sr+1 to $er
    If $aSplit[$r][$c] <> $aSplit[$sr][$c] Then Return $r-1
  Next
  Return $er
EndFunc

 

[seadoggie01]

  On 11/20/2019 at 8:19 PM, Nine said:

Seems to be working, at least with the provided string :

Expand  

What is this magic!?  He's a wizard, Harry

[jchd]

That gives under par result in case of more varied input.

[seadoggie01]

I broke it... duplicate any address

Edit: Sorry, it does say unique. I missed that.

Edited November 20, 2019 by seadoggie01

[jchd]

Input is supposed to be a sorted array of distinct strings of equal length.

Edited November 20, 2019 by jchd

[iamtheky]

turns out mine worked fine for the example

#include<array.au3>

$str = '12-34-56-34-14-91' & @CR & _
'12-34-56-80-04-54' & @CR & _
'12-34-56-80-93-11' & @CR & _
'12-34-56-EA-76-0F' & @CR & _
'12-34-56-EA-76-9F' & @CR & _
'12-34-56-EA-78-11'

local $aSplit[0][6] , $sOut

_ArrayAdd($aSplit , $str , 0 , "-" , @CR)

For $i = 0 to 5

   $sOut &= "(" &  _ArrayToString(_ArrayUnique($aSplit , $i , 0 , 0 , 0) , "|") & ")-"

Next


; testing the regexp against the original set, with a rogue entry added

$a = stringsplit($str , @CR , 2)
_ArrayDisplay($a)
_ArrayAdd($a , "12-34-56-EA-79-11")



for $i = 0 to ubound($a) - 1
    msgbox(0, '' , stringregexp($a[$i] , stringtrimright($sOut , 1)))
next

 

Edited November 20, 2019 by iamtheky

[mikell]

  On 11/20/2019 at 7:02 PM, jchd said:

I'll try to write something

Expand  

I'm shivering while trying to imagine how such a pattern could be modified if a new item is introduced in the list 

[spudw2k]

  On 11/20/2019 at 8:19 PM, Nine said:

Seems to be working, at least with the provided string

Expand  

Impressive!  I'll have to digest the code.  Nice work

Agreed, it works well with the provided string.  When I added a MAC to the list it ended up with unbalanced parenthesis.

$str = _
  '12-34-56-34-14-91' & @CR & _
  '12-34-56-80-04-54' & @CR & _
  '12-34-56-80-93-11' & @CR & _
  '12-34-56-EA-76-0F' & @CR & _
  '12-34-56-EA-76-9F' & @CR & _
  '12-34-56-EA-78-11' & @CR & _
  '12-34-56-F1-00-22'

 

[spudw2k]

  On 11/20/2019 at 8:51 PM, iamtheky said:

turns out mine worked fine for the example

Expand  

I like the approach.  It looks simple, but I don't think it is matching only the MAC list, but combinations of MAC bytes.

[spudw2k]

Appreciate everyone's brain power and effort on this one.  Fun challenge for me and hopefully ya'll too.

Seen some neat ideas to consider.  @Nine's is closest so far to what I was trying to accomplish.