Tävlingsprogrammering/Uppgifter/IP-adresser

IP-adresser

En IPv4-address består av fyra heltal mellan 0 och 255 (som inte får ha några inledande nollor), separerade av punkter. T.ex. är 1.0.3.255 en giltig address, medan 1.0.03.255, 1.0.3.256 och 1.0.3 inte är giltiga addresser. Skriv ett program som läser in en sekvens av siffror och räknar ut hur många giltiga IPv4-adresser som kan skapas genom insättning av tre punkter i sekvensen. Sekvensen består av minst 4 och högst 12 siffror.

Exempel 1

Sekvens ? 291841
Antal: 7

Exempel 2

Sekvens ? 00000
Antal: 0

Exempel 3

Sekvens ? 255255255255
Antal: 1

Exempel 4

Sekvens ? 0000
Antal: 1

Exempel 5

Sekvens ? 20142014
Antal: 6

Lösning

Givet en viss siffersekvens, kan man beräkna på hur många olika sätt man kan placera den första punkten i IP-adressen. Genom att tillkalla denna funktionalitet rekursivt kan man sedan fortsätta sätta ut punkter i sekvensen tills man antingen satt ut 4 punkter eller tills man nått sekvensens slut. Om man satt ut 4 punkter och även nått slutet av sekvensen har man funnit ett sätt att placera punkterna. För att sätta ut första punkten i sekvensen går man igenom de möjliga inledande delsekvenserna som går att ta ur sekvensen som är mindre än 256 och kallar funktionen rekursivt med den kvarvarande delen av sekvensen och ökar antalet punkter med en.

Lösning i Python:

import sys

def ip(s, points):
    global sum
    if points == 4:
        if len(s) == 0:
            sum += 1
        return
    i = 1
    while i <= len(s) and int(s[:i]) < 256:
        if int(s[:1]) == 0: # Med inledande nolla går det endast att plocka ut en inledande delsekvens.
            ip(s[i:], points+1)
            break
        else:
            ip(s[i:], points+1)
        i += 1

sum = 0
print "Sekvens ? ",
sek = sys.stdin.readline().split()[0]
ip(sek, 0)
print "Antal", sum