38
\$\begingroup\$

Sometimes when I'm typing out an IPv4 address, I get all the numbers right, but I forget to type one or more periods. I'd like to have a program (or function) that takes my broken IPv4 address and outputs all possible valid placements of the missing periods.

Input

The input will always be a string that is a transformation of a valid IPv4 address (see particulars below). It will always have been transformed solely by the elimination of one or more period characters.

You submission does not need to handle inputs outside of this format.

Output

A collection or list, in no particular order or format, of strings representing all valid IPv4 addresses that can be created from the input by the insertion of period characters into the input.

  • The output may be a language-native list or other ordered or unordered collection type.
  • Alternatively, it may be a string sequence of IPv4 address delimited in some clear way.
    • If you use a single-character delimiter to delimit your string, periods and digits are not allowed as that single-character delimiter. I realize that, unlike numbers, periods as delimiters are not ambiguous (since every fourth period would necessarily be a delimiter) but for the sake of readability, I am disallowing it.

IPv4 address format

While IPv4 addresses are really just a sequence of four binary octets, this challenge uses a restricted dotted decimal format.

  • An IPv4 address is a four decimal values separated by three periods.
  • Each of the four values are in the range 0 to 255, inclusive.
  • Leading zeros are not allowed in any number value. (Standalone one-character 0 is allowed; any other number beginning with a zero is not: 052, 00, etc.)

Test Cases

Input is on the first line, output on second line (here, structured as a comma-separated list of quoted strings, separated by commas, surrounded by [ ], but you may use any reasonable format or structure, as specified above). Some examples have notes on a third line to highlight the application of a particular rule.

192.168.1234
["192.168.1.234", "192.168.12.34", "192.168.123.4"]

192.1681234
["192.16.81.234", "192.168.1.234", "192.168.12.34", "192.168.123.4"]
(Note: 192.1681.2.34 (etc.) is illegal because 1681 is greater than 255)

1921681.234
["19.216.81.234", "192.16.81.234", "192.168.1.234"]

1921681234
["19.216.81.234", "192.16.81.234", "192.168.1.234", "192.168.12.34", "192.168.123.4"]

192.168.1204
["192.168.1.204", "192.168.120.4"]
(Note: 192.168.12.04 is illegal because of leading zero)

192.168.123
["1.92.168.123", "19.2.168.123", "192.1.68.123", "192.16.8.123", "192.168.1.23", "192.168.12.3"]

192.168.256
["192.168.2.56", "192.168.25.6"]
(Note: Any combination that would leave 256 intact is illegal)

120345
["1.20.3.45", "1.20.34.5", "1.203.4.5", "12.0.3.45", "12.0.34.5", "120.3.4.5"]
(Note: 12.03.4.5 (etc.) is illegal due to leading zero.)

012345
["0.1.23.45", "0.1.234.5", "0.12.3.45", "0.12.34.5", "0.123.4.5"]
(Note: the first segment must be 0, because `01` or `012` would be illegal.)

000123
["0.0.0.123"]

(I made these examples by hand, so please alert me to any mistakes you may find.)

\$\endgroup\$
  • \$\begingroup\$ output order is matters? \$\endgroup\$ – YOU Aug 11 '16 at 15:39
  • \$\begingroup\$ @YOU No: "A collection or list, in no particular order or format..." \$\endgroup\$ – apsillers Aug 11 '16 at 15:40
  • \$\begingroup\$ Leading zeros are not allowed: Does that apply to the input too? \$\endgroup\$ – Luis Mendo Aug 11 '16 at 16:23
  • 3
    \$\begingroup\$ So.... "000125" should only return one correct solution... 0.0.0.125? \$\endgroup\$ – Keeta Aug 11 '16 at 17:26
  • 2
    \$\begingroup\$ @Keeta That is exactly correct. (I just added it as a test case.) \$\endgroup\$ – apsillers Aug 11 '16 at 17:26
9
\$\begingroup\$

Pyth, 24 bytes

f&q4lJcT\.!-J`M256jL\../

Try it online

How it works

                      ./Q   all partitions of input
                  jL\.      join each on .
f                           filter for results T such that:
      cT\.                    split T on .
     J                        assign to J
    l                         length
  q4                          equals 4
 &                            … and:
           -J`M256              J minus the list of representations of [0, …, 255]
          !                     is false (empty)

Pyth, 17 bytes, very slow

@FjLL\.,^U256 4./

Warning. Do not run. Requires approximately 553 GiB of RAM.

How it works

       ,             two-element list of:
        ^U256 4        all four-element lists of [0, …, 255]
               ./Q     all partitions of input
  jLL\.              join each element of both on .
@F                   fold intersection
\$\endgroup\$
  • \$\begingroup\$ Nice! Just for my own understanding, "all partitions of input" means all possible ways of segmenting the input, right? So you make every possible split and then rejoin the splits with periods, so you end up with loads of candidates like 1.9.2.1.6.8.1.2 and 19.2.1.6.8.1.2 etc.? (But then obviously all the invalid ones get filtered out) \$\endgroup\$ – apsillers Aug 11 '16 at 18:58
  • \$\begingroup\$ @apsillers Correct. \$\endgroup\$ – Anders Kaseorg Aug 11 '16 at 18:58
16
\$\begingroup\$

C (gcc/linux), 125 121 bytes

i;f(char*a){do{char*y=a,s[99],*x=inet_ntop(2,&i,s,99);for(;*x&&!(*x^*y&&*x^46);++x)y+=*x==*y;*x|*y||puts(s);}while(++i);}

Loops over all possible IPv4 addresses, and does a custom comparison that skips over extra dots in the generated ip address (but not in the main comparison address) to decide whether to print or not. Very slow, but should finish within 1 hour on a reasonable PC.

\$\endgroup\$
  • \$\begingroup\$ You can remove the i=0;. \$\endgroup\$ – betseg Aug 11 '16 at 17:43
  • \$\begingroup\$ @ReleasingHeliumNuclei I thought I couldn't (a function must be re-usable), but now I realize that after the function i is 0 again... \$\endgroup\$ – orlp Aug 11 '16 at 17:44
6
\$\begingroup\$

Perl 5, 91 bytes

<>=~/^(([1-9]?|1\d|2[0-4])\d|25[0-5])\.?((?1))\.?((?1))\.?((?1))$(?{print"$1.$3.$4.$5 "})^/

The program expects a single line of a single input and outputs space-delimited list of candidates.

Explanation

The program exploits the backtracking feature of regex to loop over all possibilities of forming a valid IPv4 address from the input string.

^(([1-9]?|1\d|2[0-4])\d|25[0-5])\.?((?1))\.?((?1))\.?((?1))$

The IPv4 regex with optional ., nothing of note here.

(?{print"$1.$3.$4.$5 "})

A code evaluation expression which prints out the content of the capturing groups.

^

Make the match fails and force backtracking.

Example run

$ echo "012345" | perl G89503.pl
0.12.34.5 0.12.3.45 0.1.23.45 0.1.234.5 0.123.4.5
\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 147 141 135 bytes

f=(s,n=0)=>(a=s.split`.`)[3]?a.every(s=>s==`0`|s[0]>0&s<256)?s+' ':'':[...s].map((_,i)=>i>n?f(s.slice(0,i)+`.`+s.slice(i),i):``).join``
<input placeholder=Input oninput=o.textContent=f(this.value)><div id=o style=font-family:monospace;width:1em>Output

Edit: saved 6 bytes thanks to @apsillers. Saved another 6 bytes by copying @YOU's validity test.

\$\endgroup\$
  • \$\begingroup\$ is there a difference between [1-9]|0 and [0-9] or \d?? \$\endgroup\$ – YOU Aug 11 '16 at 15:34
  • \$\begingroup\$ @apsillers Ah yes, an earlier version of my code could generate a trailing . which would throw the test, but I think this version is OK. \$\endgroup\$ – Neil Aug 11 '16 at 15:36
  • \$\begingroup\$ @YOU The important bit is that the 0 has a $. (It's also missing a ^, so thanks for drawing my attention to it.) \$\endgroup\$ – Neil Aug 11 '16 at 15:38
  • \$\begingroup\$ @apsillers Sadly splice doesn't work like that, it modifies the array and returns any removed elements. \$\endgroup\$ – Neil Aug 11 '16 at 15:47
4
\$\begingroup\$

Python 3, 232 bytes

import re,itertools as t,ipaddress as k
R=range
i=input()
for d in R(5):
 for p in t.combinations(R(len(i)),d):
  n=i;o=0
  for a in p:n=n[:a+o]+'.'+n[a+o:];o+=1
  try:k.ip_address(n);print(n*(not re.search(r'\D?0\d',n)))
  except:0

Pretty simple: We place periods everywhere and print if the IP address with the periods placed is valid. We check the validity of the IP adresses by (ab)using ipaddress.ip_address, which raises an exception if the input is not a valid IP address. The challenge defines some additional rules that ip_address doesn't handle (namely, that there can be no leading zeroes), so we check for those too with a regular expression, then print.

Outputs each solution on a new line, mixed with an arbitrary number of blank lines.

Example run:

$ echo 012345 | python fixip.py
0.1.23.45
0.1.234.5
0.12.3.45
0.12.34.5
0.123.4.5





$ echo 000123 | python fixip.py
0.0.0.123








_

Here's my older, 248-byte Python 2 solution. The second and third indent levels are \t (raw tab) and \t (raw tab plus space) respectively. This plays really badly with Markdown, so the tabs have been replaced by two spaces.

import socket,re,itertools as t
R=range
i=input()
for d in R(5):
 for p in t.combinations(R(len(i)),d):
  n=i;o=0
  for a in p:n=n[:a+o]+'.'+n[a+o:];o+=1
  try:
   socket.inet_aton(n)
   if n.count('.')==3and not re.search(r'\D?0\d',n):print n
  except:0

Requires the input surrounded with quotes (e.g. "123.456.789"). Outputs each generated IP address on a new line.

Saved 9 bytes thanks to @grawity!

\$\endgroup\$
  • 1
    \$\begingroup\$ Would ipaddress.ip_address() be shorter than aton+manual check? \$\endgroup\$ – grawity Aug 12 '16 at 8:55
3
\$\begingroup\$

Brachylog, 110 bytes

:ef:{".",@N.|.}ac:3f:{@n:"."rz:cacb.}a.
,4yeN,?:N:6i.@nMl4,M:{:7&<256}a
~c[A:B]h:@N:Bc.
:ef:{,"0":"9"y:.m?}ac.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 3, 262 260 bytes

p,l,L,T=set(),-1,len,tuple
while l<L(p):l=L(p);p|={T(z[:i]+(y[:j],y[j:])+z[i+1:])for z in set(p)or[T(input().split("."))]for i,y in enumerate(z)for j in range(1,L(y))}
print(['.'.join(x)for x in p if L(x)==4and all(y=='0'or y[0]!='0'and int(y)<256for y in x)])

No libraries used, but late and longer, may be I am missing some obvious golfing techniques.

Results anyway.

for x in 192.168.1234 192.1681234 1921681.234 1921681234 192.168.1204 192.168.123 192.168.256 120345 012345 000123; do
echo $x | python3 ipv4.py
done;

['192.168.123.4', '192.168.1.234', '192.168.12.34']
['192.16.81.234', '192.168.1.234', '192.168.123.4', '192.168.12.34']
['19.216.81.234', '192.168.1.234', '192.16.81.234']
['19.216.81.234', '192.168.123.4', '192.168.12.34', '192.16.81.234', '192.168.1.234']
['192.168.1.204', '192.168.120.4']
['192.16.8.123', '19.2.168.123', '1.92.168.123', '192.168.1.23', '192.168.12.3', '192.1.68.123']
['192.168.25.6', '192.168.2.56']
['1.20.3.45', '1.203.4.5', '12.0.34.5', '120.3.4.5', '1.20.34.5', '12.0.3.45']
['0.1.23.45', '0.12.3.45', '0.12.34.5', '0.123.4.5', '0.1.234.5']
['0.0.0.123']
\$\endgroup\$
  • 1
    \$\begingroup\$ I thought I'd copy your validity test and wondered whether you need the parentheses around the or clause? \$\endgroup\$ – Neil Aug 11 '16 at 18:36
  • \$\begingroup\$ @Neil, thanks, didn't need those. \$\endgroup\$ – YOU Aug 12 '16 at 1:35

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.