RegEx builder algorithm for MAC address list

[iamtheky]

22 minutes ago, spudw2k said:

but I don't think it is matching only the MAC list, but combinations of MAC bytes.

In what cases does the latter not accomplish the former?

I agree it feels simple and incomplete (like all my RegEx), but in practice it is proving formidable.

 

[spudw2k]

Not saying it doesn't, but my "requirement" is a regex that only matches exact MAC addressed and not combinations.

Edited November 20, 2019 by spudw2k

[spudw2k]

More detail / bigger picture; yes, a MAC list could be done by just concatenating into a pipe delimited string, but I am also dealing with a string length limitation.  

This is a "clever" workaround to address the string length limitation, but it also needs to be precise (only matches exact MAC address in the list).

[Nine]

I modified my code, could you test it further.  Seems it is working better now...

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' & @CR & _
  '12-34-56-F1-00-22' & @CR & _
  '12-34-57-F2-50-60'

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

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

Func Solution ($lvl,$sr, $sc, $er, $ec)
  $v = Same ($sr,$sc,$er)
  If $sr <> $er and $v <> $er and $lvl = 1 Then
    $sRegExp &= "("
  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)
    if $lvl = 1 then $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

 

[jchd]

My take:

expandcollapse popup

Local $a = [ _
    "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", _
    "12-39-56-80-93-11", _
    "14-39-56-EA-76-0F", _
    "52-34-56-80-04-54", _
    "52-36-56-80-04-54" _
]

; 1(2-3(4-56-(34-14-91|80-(04-54|93-11)|EA-7(6-(0F|9F)|8-11))|9-56-80-93-11)|4-39-56-EA-76-0F)|52-3(4-56-80-04-54|6-56-80-04-54)

Local $b = $a       ; argument $a below is Byref and will be modified. Make a solid copy if unchanged $a is needed later
; if necessary, perform array bounds check only once here
Local $res = Prefixes($b)
ConsoleWrite($res & @LF)

; factor out, in regex syntax, commun sub-prefixes from a sorted array of at least two distinct strings of equal length
; indices need $iStart > $iEnd, that is an index range of 2+ entries
Func Prefixes(ByRef $aIn, $iStart = 0, $iEnd = UBound($aIn) - 1)
    If $iStart > $iEnd Then Return
    Local $sMatch, $sPrefix = $aIn[$iStart]
    For $i = $iStart To $iEnd - 1
        $sMatch = Match($sPrefix, $aIn[$i + 1])
        If $sMatch = "" Then
            ExitLoop
        EndIf
        $sPrefix = $sMatch
    Next
    Local $s1, $s2
    If $i > $iStart Then
        For $j = $iStart To $i
            $aIn[$j] = StringTrimLeft($aIn[$j], StringLen($sPrefix))
        Next
        $s1 = $sPrefix & '(' & Prefixes($aIn, $iStart, $i) & ')'
    Else
        $s1 = $aIn[$i]
    EndIf
    If $iStart = $i And $iEnd = $i + 2 Then
        $s2 = $aIn[$i + 1] & "|" & $aIn[$iEnd]
    Else
        $s2 = Prefixes($aIn, $i + 1, $iEnd)
    EndIf
    Return $s1 & ($s2 ? "|" & $s2 : "")
EndFunc

; return the longest common prefix of two distinct strings of same length
Func Match($s1, $s2)
    Local $i = 1
    While StringLeft($s1, $i) = StringLeft($s2, $i)
        $i += 1
    WEnd
    Return StringLeft($s1, $i - 1)
EndFunc

This code may not produce the shortest regex in some pathological cases, for instance a(b|c) is always longer than ab|ac whatever the prefix a and suffixes b and c consist of (entries have fixed length), but thinking twice you see that you can't expect to match exact input entries with a regex having non-nested parenthesized alternations, else any combination of substrings in alternation get matched, which have little chance to be in the input array.  Example:

Input: ["acf", "acg", "bce"]
Wrong regex: (a|b)c(e|f|g)
That would also match "ace", "acf", "bcf", "bcg" which aren't in input array.
Correct regex: ac(f|g)|bce

Also, forcing the prefix a to be longer than 1 character would preclude any input array where entries don't share at least the 2 head characters, failing flat on its nose with the test input I used.

 

EDIT: forgot to mention that I suspect there is room for simplifying the various bound conditions tested here and there but I don't have enough time to dig further at the moment.

Edited November 21, 2019 by jchd

[spudw2k]

2 hours ago, Nine said:

I modified my code, could you test it further.  Seems it is working better now...

Looks pretty solid.  Well done!

 

1 hour ago, jchd said:

My take:

Very nice!  

[jguinch]

Hi all.

It's a long time I didn't write a piece of code here...

I found the subject interesting, I tried for a long time to find a suitable code ...
this is something that can not compete with JC's code 😅

 

Local $sMacList = '' & _
'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-EA-78-19'

Local $sPattern
_generatePattern($sMacList)
ConsoleWrite($sPattern)

Func _generatePattern($str)
   Local $aComb, $sLeft
   Local $aMac = StringRegExp($str, "\N+", 3)
   Local $sFirst = StringRegExp($str, "^[[:xdigit:]]{2}", 1)[0]
   Local $iLen = StringLen(StringRegExpReplace($str, "(?s)\R.+", ""))
   Local $sReplace = StringRegExpReplace($str, "(?m)^" & $sFirst & "(-|$)", "")
   If @extended = UBound($aMac) Then
      $sPattern &= $sFirst & "-"
      If $sReplace <> "" Then _generatePattern($sReplace)
   Else
      $aComb = StringRegExp($str, "(?:^|\R)([[:xdigit:]]{2})(?!.*\R\1)", 3)
      $sPattern &= "("
      For $i = 0 To UBound($aComb) - 1
         $sPattern &= ($i ? "|" : "") & $aComb[$i] & "-"
         $sLeft = StringRegExpReplace(StringRegExpReplace($str, "(?m)" & $aComb[$i] & "-|^(?!" & $aComb[$i] & ")\N+\R?"  , ""), "\R$", "")
         If $iLen <> 2 Then _generatePattern($sLeft)
      Next
      $sPattern &= ")"
   EndIf
   $sPattern = StringRegExpReplace($sPattern, "-(?=[|)])", "")
EndFunc