Restore IP
Challenge: Restore IP Addresses
An IPv4 address consists of exactly four non-negative whole numbers, separated by single dots. Each number is between 0 and 255 (inclusive) and cannot have leading zeros, unless it is 0.
For example, the following are valid IPv4 addresses:
1.1.1.1255.255.255.255192.168.0.123.25.1.194
While the following are not:
01.1.1.01256.255.255.255192.168.00.1a23.b25.1.194
A database containing IPv4 addresses has gotten out of order up by addresses losing their dots. Your job is to restore it. You'll write a generator restore-ip such that it takes a @t cord containing only numerical digits and returns a set of all the @t cords with dots inserted into the given digits to create a valid IPv4 address.
We also want to crash if the input given is clearly invalid. Your generator should crash in the following cases:
If the input contains any characters other than digits.
If the input length is greater than 12.
Example usage:
> +restore-ip '12345678'
{'1.234.56.78' '123.45.6.78' '12.34.56.78' '123.45.67.8' '123.4.56.78'}> +restore-ip '1234567890123456'
dojo: naked generator failure> +restore-ip '111a'
dojo: naked generator failureSolutions
These solutions were submitted by the Urbit community as part of a competition in ~2024.3. They are made available under the MIT License and CC0. We ask you to acknowledge authorship should you utilize these elsewhere.
Solution #1
By ~nodsup-halnux. Clearly written, well-commented, and very Hoonish.
:: +restore-ip: An algorithm that takes a cord
:: of digits, and tries to generate valid ips.
:: If digit cord length is <4, returns ~
:: If digit cord length is >12, crashes (!!)
:: If non-numerics present, crashes (!!)
:: Otherwise, return a (set @t) of results.
::
|^
:: Bar-ket (|^) buck arm.
:: $ arm has control flow and tests basic cases
:: before handing off input tape to the main
:: algorithm for finding IPs.
:: Returns a (set @t).
::
|= [tcord=@t]
^- (set @t)
:: We need a tape for our work. Convert.
::
=/ ttape (trip tcord)
:: We use length twice, so pin a variable.
::
=/ lentape (lent ttape)
:: Are all of our characters digits? If not, crash
::
?. =((lent (skip ttape is-digit)) 0) !!
:: Is our length less than 4? If so, return ~
::
?. (gte lentape 4)
`(set @t)`(silt `(list @t)`~)
:: Is our tape greater than 12? If so, crash.
::
?. ?!((gth lentape 12)) !!
:: Finally, lets call the algorithm.
::
(first-loop ttape)
:: This is a structure used for generating our IPs
:: in the algorithm below. An IPv4 consists of four
:: octets (8 bits), making a 32 bit address.
::
+$ octets $: o1=tape
o2=tape
o3=tape
o4=tape
==
:: ++is-digit: Checks to see if an inputed character
:: is a valid digit from 0-9. Used by the skip
:: gate as a negative filter, to check for
:: non-numeric characters in cord input.
:: Interestingly, our tapes are made up of @tD's,
:: but checking equality with an @t works.
:: Returns a loobean.
::
++ is-digit
|= [c=@t]
^- ?
:: Check if c is any numeric digit. Return true
:: If we find a digit.
::
?| =(c '0') =(c '1') =(c '2')
=(c '3') =(c '4') =(c '5')
=(c '6') =(c '7')
=(c '8') =(c '9')
==
:: ++range-ok: Small gate for seeing if our octet
:: from the octets structure is between 1 and 255
:: (inclusive). Note slav crashes if we have a
:: cord that starts with zero - this is guarded
:: against by the ++check-ip control flow.
:: Returns a loobean.
::
++ range-ok
|= [q=tape]
^- ?
=/ testnum (slav %ud (crip q))
&((gth testnum 0) (lth testnum 255))
:: ++check-ip: Given a octet from the octets struct
:: checks the following: If first character is a
:: zero AND length is 1, return %.y. Else, Check if
:: our characters are < 4 in length, and number they
:: represent is in range.
:: Returns a loobean
::
++ check-ip
|= [octet=tape]
^- ?
:: Prove octet not ~, expose i/t faces for use.
::
?~ octet !!
:: Is our first digit zero?
::
?: =('0' i.octet)
:: If it is, only a string of length 1 is valid
::
?: =((lent octet) 1)
%.y
:: Otherwise, return false.
::
%.n
::If it is not zero, then test length and range
::
?: &((lth (lent octet) 4) (range-ok octet))
%.y
:: Our length/range test failed, so return false.
::
%.n
:: ++build-ip: Given the octets structure, build a
:: valid IP. Assumes we checked our octet and all
:: tests passed.
:: Returns a cord.
::
++ build-ip
|= [ip=octets]
^- @t (crip "{o1.ip}.{o2.ip}.{o3.ip}.{o4.ip}")
:: General comments about loops below:
:: Splitting up the loops into three gates makes it
:: easier to read, with the drawback that our gate
:: inputs for loops 2 and 3 get a bit long and our
:: run-time might go up a bit. As our input cords
:: are no longer than 12 characters, computational
:: efficiency isn't a serious issue.
::
:: ++first-loop: First of three loops. Variable i is
:: set, which represents the dot separation between
:: our first and second octet, conceptually.
:: Calls second-loop, and then union merges the
:: results into the result1 variable.
:: Returns a (set @t).
::
++ first-loop
|= [iptape=tape]
^- (set @t)
:: Paramters for our trap.
::
=/ i 1
=/ len (lent iptape)
=/ result1 `(set @t)`~
|-
^- (set @t)
:: Is i less than tape length?
::
?: (lth i len)
::If so, compute j, and call second-loop. Then
:: merge second loop results in to result1.
::
=/ j (add i 1)
%= $
result1 (~(uni in result1) (second-loop i j iptape))
i +(i)
==
::If i bound is hit, return result1.
::
result1
:: ++second-loop: Structurally, this is the same
:: as first-loop. Takes i and j as input,
:: and sets up k for third-loop.
:: Returns a (set @t)
::
++ second-loop
|= [i=@ud j=@ud iptape=tape]
^- (set @t)
:: Paramters for our trap.
::
=/ result2 `(set @t)`~
=/ len (lent iptape)
|-
^- (set @t)
:: Is j less than tape length?
::
?: (lth j len)
:: If so, compute k, and call third-loop. Then
:: merge third loop results in to result2.
::
=/ k (add j 1)
%= $
result2 (~(uni in result2) (third-loop i j k iptape))
j +(j)
==
::If j bound is hit, return result1.
result2
:: ++third-loop: This is the main body of code for
:: generating IP addresses. It takes ijk and
:: finds octet, which are stored in the octets
:: structure. Validity checks (above) are called,
:: and if they pass, a valid IP is generated and
:: inserted into the results3 variable.
:: Returns a (set @t)
::
++ third-loop
|= [i=@ud j=@ud k=@ud iptape=tape]
^- (set @t)
:: Paramters for our trap.
::
=/ len (lent iptape)
=/ result3 `(set @t)`~
|-
^- (set @t)
:: Is j less than tape length?
::
?: (lth k len)
:: If so...now we do something different!
:: Pin gen-ip to sample, and insert each octet
:: into the octets structure. Use current ijk
:: to figure out our individual octets.
::
=/ gen-ip
^- octets
:^ o1=(limo (scag i iptape))
o2=(limo (slag i (scag j iptape)))
o3=(limo (slag j (scag k iptape)))
o4=(limo (slag k iptape))
:: Main checks on octet. Do they all pass?
::
?: ?& (check-ip o1.gen-ip)
(check-ip o2.gen-ip)
(check-ip o3.gen-ip)
(check-ip o4.gen-ip)
==
:: If they do, build a valid IP.
:: Place results in result3. Increase k.
::
%= $
result3 (~(put in result3) (build-ip gen-ip))
k +(k)
==
:: If they do not, lets increase k and
:: try the next IP.
::
%= $
k +(k)
==
:: k has hit bound, return result3.
::
result3
--Solution #2
By ~ramteb-tinmut. Another great solution, well written and commented.
:: restore-ip.hoon
:: A generator to parse valid IPv4 format addresses from an input cord
::
|= input=@t
:: Ensure output type
::
^- (set cord)
=<
:: cord to tape
::
=/ input-tape (trip input)
:: Check for forbidden characters
::
?> (validate-input input-tape)
:: Return an empty set if the tape is less than minimum required to form a valid IP
::
?: (lth (lent input-tape) 4)
`(set cord)`~
:: Otherwise proceed to create a set of possible valid ips
::
(do-tape [input-tape "" 1 0 `(set cord)`~])
|%
:: This is our core logic where the input tape is repeatedly parsed for combinations of IP octets, and the set of possible IPs is assembled
::
++ do-tape
|= [input-tape=tape found-ip=tape count=@ud found-octets=@ud ip-set=(set cord)]
:: 4 found octets mean we may have a vali IP, if the tape is exhausted
::
?: =(found-octets 4)
?: =(0 (lent input-tape))
(~(put in ip-set) (crip found-ip))
ip-set
:: If we haven't got a full set of octets, and our remaining tape can't be split, we catch that here
::
?: |(=(count 4) (gth count (lent input-tape)))
ip-set
:: Divide the tape in to a head & tail, based on current split count
::
=/ head (scag count input-tape)
=/ tail (slag count input-tape)
:: Check if the head is a valid octet, and weld it to our existing tape
::
?: (is-octet head)
=/ updated-ip (weld found-ip ?:((lth found-octets 3) (snoc head '.') head))
:: tisdot was the missing ingredient to get recursion on the remaining tape, and ensure all possible combinations are sought.
::
:: We're updating the value of the ip-set with the return value of an additional call to this do-tape arm; with the counter is reset, along with our updated-ip tape, which contains the new valid octet, and the current tail as our new input tape
::
=. ip-set
$(input-tape tail, found-ip updated-ip, count 1, found-octets +(found-octets), ip-set ip-set)
:: This new subject is then fed into another, inner recursive loop, with the count incremented until we either find a new octet or exhaust the string
::
$(count +(count))
:: If we didn't get a match, this is where we also feed back in on the outer loop with the split counter incremented
::
$(count +(count))
:: Takes a tape, and ensures it fulfils requirement for an IPv4 octet
::
++ is-octet
|= input=tape
:: If candidate is only 1 digit, then it's always valid:
::
?: =((lent input) 1)
%.y
:: If candidate starts with 0, then it must have length 1
::
?: &(=((head input) '0') (gth (lent input) 1))
%.n
:: Candidate as a number must be =< 255
::
?: (gth (rash (crip input) dem) 255)
%.n
%.y
:: Checks a input tape for illegal chars and length restrictions
::
++ validate-input
|= input=tape
=/ allowed "1234567890"
?&
:: Ensure input =< 13
::
(lth (lent input) 13)
:: Ensure all elements are numbers:
::
(levy input |=(a=@ !=((find `(list @t)`~[a] allowed) ~)))
==
--Unit Tests
Following a principle of test-driven development, the unit tests below allow us to check for expected behavior. To run the tests yourself, follow the instructions in the Unit Tests section.
/+ *test
/= restore-ip /gen/restore-ip
|%
:: test for failures
++ test-01
%- expect-fail
|. (restore-ip 'a')
++ test-02
%- expect-fail
|. (restore-ip '1234567890123')
++ test-03
%- expect-fail
|. (restore-ip '111a1111')
++ test-04
%- expect-fail
|. (restore-ip '111111@1')
++ test-05
%- expect-fail
|. (restore-ip '11111111111^')
:: tests for success
++ test-06
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~)
!> (restore-ip '1')
++ test-07
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~)
!> (restore-ip '11')
++ test-08
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~)
!> (restore-ip '111')
++ test-09
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['1.1.1.1'])
!> (restore-ip '1111')
++ test-10
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['1.1.1.11' '1.1.11.1' '1.11.1.1' '11.1.1.1'])
!> (restore-ip '11111')
++ test-11
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['1.1.1.111' '1.1.11.11' '1.1.111.1' '1.11.1.11' '1.11.11.1' '1.111.1.1' '11.1.1.11' '11.1.11.1' '11.11.1.1' '111.1.1.1'])
!> (restore-ip '111111')
++ test-12
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['1.1.11.111' '1.1.111.11' '1.11.1.111' '1.11.11.11' '1.11.111.1' '1.111.1.11' '1.111.11.1' '11.1.1.111' '11.1.11.11' '11.1.111.1' '11.11.1.11' '11.11.11.1' '11.111.1.1' '111.1.1.11' '111.1.11.1' '111.11.1.1'])
!> (restore-ip '1111111')
++ test-13
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['1.1.111.111' '1.11.11.111' '1.11.111.11' '1.111.1.111' '1.111.11.11' '1.111.111.1' '11.1.11.111' '11.1.111.11' '11.11.1.111' '11.11.11.11' '11.11.111.1' '11.111.1.11' '11.111.11.1' '111.1.1.111' '111.1.11.11' '111.1.111.1' '111.11.1.11' '111.11.11.1' '111.111.1.1'])
!> (restore-ip '11111111')
++ test-14
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['1.11.111.111' '1.111.11.111' '1.111.111.11' '11.1.111.111' '11.11.11.111' '11.11.111.11' '11.111.1.111' '11.111.11.11' '11.111.111.1' '111.1.11.111' '111.1.111.11' '111.11.1.111' '111.11.11.11' '111.11.111.1' '111.111.1.11' '111.111.11.1'])
!> (restore-ip '111111111')
++ test-15
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['1.111.111.111' '11.11.111.111' '11.111.11.111' '11.111.111.11' '111.1.111.111' '111.11.11.111' '111.11.111.11' '111.111.1.111' '111.111.11.11' '111.111.111.1'])
!> (restore-ip '1111111111')
++ test-16
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['11.111.111.111' '111.11.111.111' '111.111.11.111' '111.111.111.11'])
!> (restore-ip '11111111111')
++ test-17
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['111.111.111.111'])
!> (restore-ip '111111111111')
++ test-18
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['1.9.99.91' '1.99.9.91' '1.99.99.1' '19.9.9.91' '19.9.99.1' '19.99.9.1' '199.9.9.1'])
!> (restore-ip '199991')
++ test-19
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['1.99.99.91' '19.9.99.91' '19.99.9.91' '19.99.99.1' '199.9.9.91' '199.9.99.1' '199.99.9.1'])
!> (restore-ip '1999991')
++ test-20
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['19.99.99.91' '199.9.99.91' '199.99.9.91' '199.99.99.1'])
!> (restore-ip '19999991')
++ test-21
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['199.99.99.91'])
!> (restore-ip '199999991')
++ test-22
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~)
!> (restore-ip '1999999991')
++ test-23
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['9.8.7.6'])
!> (restore-ip '9876')
++ test-24
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['9.8.7.65' '9.8.76.5' '9.87.6.5' '98.7.6.5'])
!> (restore-ip '98765')
++ test-25
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['9.8.76.54' '9.87.6.54' '9.87.65.4' '98.7.6.54' '98.7.65.4' '98.76.5.4'])
!> (restore-ip '987654')
++ test-26
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['9.87.65.43' '98.7.65.43' '98.76.5.43' '98.76.54.3'])
!> (restore-ip '9876543')
++ test-27
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['98.76.54.32'])
!> (restore-ip '98765432')
++ test-28
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~)
!> (restore-ip '987654321')
++ test-29
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['1.1.25.61' '1.12.5.61' '1.12.56.1' '1.125.6.1' '11.2.5.61' '11.2.56.1' '11.25.6.1' '112.5.6.1'])
!> (restore-ip '112561')
++ test-30
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['1.12.56.11' '1.125.6.11' '1.125.61.1' '11.2.56.11' '11.25.6.11' '11.25.61.1' '112.5.6.11' '112.5.61.1' '112.56.1.1'])
!> (restore-ip '1125611')
++ test-31
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['1.112.56.111' '11.12.56.111' '11.125.6.111' '11.125.61.11' '111.2.56.111' '111.25.6.111' '111.25.61.11'])
!> (restore-ip '111256111')
++ test-32
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~)
!> (restore-ip '111256111111')
++ test-33
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['100.0.0.1'])
!> (restore-ip '100001')
++ test-34
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['100.0.100.1'])
!> (restore-ip '10001001')
++ test-35
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['10.0.100.100' '100.10.0.100' '100.100.10.0'])
!> (restore-ip '100100100')
++ test-36
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['10.10.10.101' '10.101.0.101' '101.0.10.101'])
!> (restore-ip '101010101')
++ test-37
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~)
!> (restore-ip '1010101010')
++ test-38
%+ expect-eq
!> `(set @t)`(silt `(list @t)`~['0.1.1.111' '0.1.11.11' '0.1.111.1' '0.11.1.11' '0.11.11.1' '0.111.1.1'])
!> (restore-ip '011111')
--Last updated