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 failure
Solutions
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=tapeo2=tapeo3=tapeo4=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')--