Überschneidungen finden und entfernen

[Twilo]

Hallo,

ich habe mehrere PLZ-Bereiche und möchte Überscheidungen finden und beseitigen

aus folgenden Bereichen: 0-10000,14900-15100, 11000-12000,15101, 14000-15000,11500-14500,28001
möchte ich folgendes Ergebnis: 0-10000,11000-15101,28001

Mein Ansatz ist bis jetzt folgender:

Code: Alles auswählen

import re
import string

zipcodeStr = "0-10000,14900-15100, 11000-12000,15101, 14000-15000,11500-14500,28001"

zipcodeStr = zipcodeStr.replace(" ", "")
zipcodeFields = [zipcode for zipcode in zipcodeStr.split(",") if zipcode]

zipcodesList = [0] * 100000
matchStr = re.compile("(\d+)\-(\d+)")
for zipcodeArea in zipcodeFields:
    if zipcodeArea.find("-") > 0:
        match = matchStr.match(zipcodeArea)
        if match:
            zipcodeFrom = int(match.group(1))
            zipcodeTo = int(match.group(2))
            if zipcodeFrom > zipcodeTo:
                zipcodeFrom, zipcodeTo = zipcodeTo, zipcodeFrom
            for i in range(zipcodeFrom, zipcodeTo + 1):
                zipcodesList[i] = 1
        else:
            print "Wrong Zipcode Area %s" % zipcodeArea

    else:
        zipcodesList[int(zipcodeArea)] = 1
        try:
            zipcodesList[int(zipcodeArea)] = 1
        except:
            print "Wrong Zipcode %s" % zipcodeArea


zipcodeFields = []
zipcodeStart = None
zipcodeEnd = None
for i in range(len(zipcodesList)):
    if zipcodesList[i] == 1:
        if zipcodeStart is None:
            zipcodeStart = i
        else:
            zipcodeEnd = i
    else:
        if zipcodeStart is not None:
            if zipcodeEnd is not None:
                zipcodeFields.append("%d-%d" % (zipcodeStart, zipcodeEnd))
            else:
                zipcodeFields.append("%d" % (zipcodeStart))
        zipcodeStart = None
        zipcodeEnd = None

zipcodeStr = string.join(zipcodeFields, ",")

print zipcodeStr

geht das irgendwie eleganter?

Mein Algorithmus ist etwas ineffizient, wenn Bereiche z.B. doppelt angegeben werden oder in ein Bereich zig andere Bereiche fallen. Ich muss auch den höchsten Index kennen, da es sonst zum IndexError kommt.

mfg
Twilo

[EyDu]

Da könnte sich noch der ein oder andere kleine Fehler verstecken, ich habe es nicht wirklich getestet.

Code: Alles auswählen

ranges = [(10,15), (12, 20), (18, 30), (18, 20),
          (40, 50), (60, 60), (70, 100), (80, 90)]
def merge_ranges(ranges):
    tokens = []
    
    for begin, end in ranges:
        tokens.append((begin, 1))
        tokens.append((end, -1))

    tokens.sort()
    
    result = []
    stack = 0
    for position, value in tokens:
        if stack == 0:
            begin = position
            
        stack += value
        
        if stack == 0:
            result.append((begin, position))
    
    return result

[Defnull]

Ungetestet:

Code: Alles auswählen

l = "0-10000,14900-15100, 11000-12000,15101, 14000-15000,11500-14500,28001"
l = [map(int, x.split('-')) if '-' in x else [int(x)]*2 for x in l.split(',')]

def flatten(l):
    l = sorted(l)
    last = l.pop(0)
    for current in l:
        if last[0] <= current[0] <= last[1]+1:
            last[1] = max(last[1], current[1])
            continue
        yield last
        last = current
    yield last

print ', '.join([str(a) if a==b else '%d-%d'%(a, b) for a, b in flatten(l)])

[Barabbas]

Ziemlich raffinierte Lösung, finde ich. Aber die LC in Zeile 2 ist tatsächlich mal überflüssig, oder gibt es da eine total abgefahrene Optimierung - kann ja eigentlich nicht, oder? Aber wie gesagt: Nicht schlecht, das muss man sich schon ein paar mal ansehen - ich zumindest .

Besten Gruß,

bar - "Schleimer" - abbas

[Defnull]

Ja, der war komplett überflüssig. Den hab ich wohl beim mehrmaligen Umsortieren des Codes übersehen

[Twilo]

Hallo,

Ungetestet:

Code: Alles auswählen

l = "0-10000,14900-15100, 11000-12000,15101, 14000-15000,11500-14500,28001"
l = [map(int, x.split('-')) if '-' in x else [int(x)]*2 for x in l.split(',')]

def flatten(l):
    l = sorted(l)
    last = l.pop(0)
    for current in l:
        if last[0] <= current[0] <= last[1]+1:
            last[1] = max(last[1], current[1])
            continue
        yield last
        last = current
    yield last

print ', '.join([str(a) if a==b else '%d-%d'%(a, b) for a, b in flatten(l)])

ich habs getestet. sieht gut aus

Ziemlich raffinierte Lösung, finde ich. Aber die LC in Zeile 2 ist tatsächlich mal überflüssig, oder gibt es da eine total abgefahrene Optimierung - kann ja eigentlich nicht, oder?

was meinst Du mit "LC in Zeile 2"?

mfg
Twilo

[Barabbas]

Ach, hat sich schon erledigt. Mit "LC" meinte ich "List Comprehension", falls du das meintest.

Gruß,

brb

[pillmuncher]

Im Wesentlichen dieselbe Logik wie bei Defnull, aber mit reduce:

Code: Alles auswählen

ds = "0-10000,14900-15100, 11000-12000,15101, 14000-15000,11500-14500,28001"
rs = [map(int, s.split('-')) if '-' in s else [int(s)]*2 for s in ds.split(',')]

def merged(ss):
    def merge(ranges, (new_lo, new_hi)): # <-- diese Syntax gibts nicht mehr ab Python 3, AFAIR
        old_lo, old_hi = ranges[-1]
        if old_hi < new_lo-1:
            ranges.append([new_lo, new_hi])
        elif old_hi < new_hi:
            ranges[-1][1] = new_hi
        return ranges
    return (lambda head, *tail: reduce(merge, tail, [head]))(*sorted(ss))

print(', '.join([str(a) if a==b else '%d-%d'%(a, b) for a, b in merged(rs)]))

[Twilo]

Hallo,

die Zeile

Code: Alles auswählen

l = [map(int, x.split('-')) if '-' in x else [int(x)]*2 for x in l.split(',')]

funktioniert leider nicht mit python 2.4.

Code: Alles auswählen

Python 2.4.5 (#2, Dec 14 2009, 17:36:33) 
[GCC 3.4.6 [FreeBSD] 20060305] on freebsd6
Type "help", "copyright", "credits" or "license" for more information.
>>> l = "0-10000,14900-15100, 11000-12000,15101, 14000-15000,11500-14500,28001"
>>> l = [map(int, x.split('-')) if '-' in x else [int(x)]*2 for x in l.split(',')]
  File "<stdin>", line 1
    l = [map(int, x.split('-')) if '-' in x else [int(x)]*2 for x in l.split(',')]
                                 ^
SyntaxError: invalid syntax

gibt es ein anderen Einzeiler dafür?

Im Moment habe ich den Code wie folgt abgeändert

Code: Alles auswählen

l = []
for x in l.split(','):
    if '-' in x:
        l.append(map(int, x.split('-')))
    else:
        l.append([int(x)]*2)

mfg
Twilo

[Defnull]

Code: Alles auswählen

l = [map(int, x.split('-')) if '-' in x else [int(x)]*2 for x in l.split(',')]

funktioniert leider nicht mit python 2.4.

Das sollte auch so gehen:

Code: Alles auswählen

l = ['-' in x and map(int, x.split('-')) or [int(x)]*2 for x in l.split(',')]

[Twilo]

Hallo /dev/null,

ja das funktioniert

Ein Problem habe ich noch, wenn jemand auf die Idee kommt und das Semikolon statt dem Komma zur Trennung verwendet, wird eine Exception geworfen, genauso wenn jemand ausversehen zwei Kommas hinter einander eingibt.

Am Anfang könnte man evtl. folgendes machen

Code: Alles auswählen

l = l.replace(";", ",")

nur wie ersetzte ich mehrere Kommas zu eins? Es ist heute definitiv zu warm

mfg
Twilo

[Rebecca]

Code: Alles auswählen

>>> "hallo,,welt".replace(",,", ",")
'hallo,welt'

[Twilo]

Hallo,

Code: Alles auswählen

>>> "hallo,,welt".replace(",,", ",")
'hallo,welt'

das funktioniert leider nicht, wenn 3 oder mehr Kommata verwendet werden.

Geht das nur mit regulären Ausdrücken?

Code: Alles auswählen

import re
re.sub(",+", ",","hallo,,,,,welt")

mfg
Twilo

[BlackJack]

@Twilo: Was ist denn so schlimm daran wenn es bei falschen Eingaben eine Ausnahme gibt? Benutzereingaben still und leise zu korrigieren ist selten eine gute Idee. Wenn der Benutzer etwas falsch eingibt, sollte er darauf hingewiesen werden und die Eingabe sollte zurückgewiesen werden.