4
\$\begingroup\$

Recently I solved a challenge (problem 1 of the 3rd easy problem set of phase 2 of the '19 APL Competition) on abbreviating and expanding IP v6 addresses. For that matter, I had to write two functions, AbbreviateIPv6 and ExpandIPv6. The first function ought to take a character vector of a v6 IP address and abbreviate it like this online tool. The second function ought to undo exactly what the first one did.

I need a community review because these two were among a series of problems rated as easy and while most of them were fairly easy to solve and could be decently solved in a couple of lines, I found really hard to write the AbbreviateIPv6 function so I think I overlooked something. What is more, I failed to find a solution that didn't use regular expressions, which bothered me even more.

First, a helper function:

:Namespace ReplaceFirst
    _ReplaceFirst_ ← {
        ⍝ Operator that replaces the first occurrence of the left operand with the right operand.
        ⍝ e.g. ('ui' ReplaceFirst 'fafa') 'this ui is ui' gives 'this fafa is ui'

        startAt ← ⊃⍸⍺⍺⍷⍵
        stopAt ← startAt + (¯1+≢⍺⍺)×startAt>0
        pruned ← ⍵/⍨ ~(startAt∘<∧≤∘stopAt)⍳≢⍵
        replaceAt ← (>∘0⍴⊢) startAt
        ∊ ((⊂,⍵⍵)@replaceAt) pruned
    }
:EndNamespace

that I used in the AbbreviateIPv6 function:

AbbreviateIPv6 ← {
  ⍝ Monadic function taking character vector as input and returning character vector.
  ⍝ Abbreviates an IP v6 address.
  ⍝ e.g. '2001:0DB8:0000:0042:0000:8A2E:0370:7334' becomes '2001:DB8:0:42:0:8A2E:370:7334'
  ReplFirst←⎕fix 'file://path/to/ReplaceFirst.dyalog'

  reduced ← ('0000' ':0{1,3}' ⎕R (,¨'0' ':'))⍵
  runs ← ⌽ ⍴∘'0:'¨ 1+2×⍳7
  shortened ← {(⍵ ReplFirst._ReplaceFirst_ '') reduced}¨ runs
  ((⊃∘⍋≢¨)⊃⊢) shortened
}

I know I could've defined the _ReplaceFirst_ as a function inside AbbreviateIPv6 specialized for the case I wanted, but I figured the function was getting so long I might as well write a general operator that I might reuse later.

Finally, just for comparison, I was able to write the ExpandIPv6 in a much more compact way:

ExpandIPv6 ← {
    ⍝ Monadic function expecting and returning character vector.
    ⍝ Expands an abbreviated IP v6 address.
    ⍝ e.g. '2041:0:140F::875B:131B' gives '2041:0000:140F:0000:0000:0000:875B:131B'.

    colons ← +/':'=⍵
    intermediate ← ('::' ⎕R(':0'⍴⍨ 3+2×7-colons))⍵
    splits ← (':'∘≠⊆⊢) intermediate
    LeftZeroPadder ← (⍴∘'0')∘(4∘-)∘≢,⊢
    ⊃ {∊⍺':'⍵}/ LeftZeroPadder¨ splits
}
\$\endgroup\$
6
  • \$\begingroup\$ Maybe you could link directly to the specific problem instead of the general page? \$\endgroup\$ – Adám Apr 17 '20 at 2:03
  • \$\begingroup\$ @Adám I can link to the year but I can only find the problem in a pdf, not in a specific URL. \$\endgroup\$ – RGS Apr 17 '20 at 6:37
  • \$\begingroup\$ You can link to the right page though. \$\endgroup\$ – Adám Apr 17 '20 at 7:44
  • \$\begingroup\$ @Adám done! I linked to the challenge page where you can test phase 1 submissions and included a descriptive path to the problem at hand \$\endgroup\$ – RGS Apr 17 '20 at 8:19
  • 1
    \$\begingroup\$ I meant link straight to the right page in the pdf. \$\endgroup\$ – Adám Apr 17 '20 at 9:50
2
\$\begingroup\$

I think using regular expressions is a perfectly sensible approach. What you're missing is probably that Dyalog APL allows setting a Match Limit with ⍠'ML' n where a positive n limits to the first n matches and a negative n limits to the (absolute value of) nth match. With this in mind, I'd use regular expressions extensively:

AbbreviateIPv6 ← {
    collapsed0s ← '\b0{1,3}' ⎕R '' ⊢ ⍵      ⍝ remove up to 3 leading 0s
    runsOf0s ← '\b(0:)*0\b'                 ⍝ 0:0:0:…:0
    nth ← - ⊃⍒ runsOf0s ⎕S 1 ⊢ collapsed0s  ⍝ 1: lengths, ⊃⍒: index of first max
    abbreviated ← runsOf0s ⎕R ':' ⍠'ML' nth ⊢ collapsed0s
    ':::' '^:$' ⎕R '::' ⊢ abbreviated       ⍝ exactly two
}

Try it online!

Notes:

  • The linked online IPv6 compressor gives wrong results, as do many others. This one seems to work, even though it misses the occasional shortening opportunity. I still have not found an online tool that compresses both fully and correctly.
  • If runsOf0s ⎕S 1 doesn't find any runs of 0s, it returns so nth becomes 0, which is fine even though 'ML' 0 means "no limit" because there are no matches.
\$\endgroup\$
2
  • \$\begingroup\$ Lovely, thanks! The ⍠'ML' and the negative argument to it were exactly what I was missing... Also, \b in the regex also matches the beginning of the string, right? Finally, I don't understand if the "edge cases" you mention correspond to maximal compression when the whole IP address is just 0s. \$\endgroup\$ – RGS Apr 17 '20 at 16:11
  • 1
    \$\begingroup\$ @RGS Yes, \b matches any word boundary, even at the edges of a string. The comment was imprecise: Since we substitute 0:0 with : we end up with ::: when counting the surrounding colons (except at beginning or end where we get two, and for all-zero where we get one). \$\endgroup\$ – Adám Apr 17 '20 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.