Mississippi

[hendrikS]

Was sind wir wohl in deren Augen?

Bestimmt nicht so schlimm wie Du denkst. Jeder hat so seinen Spleen.

Scheme:
Die vielen Klammern haben mich immer davon abgehalten das mal zu probieren.

Und nicht zuletzt:
Gerolds nonmagic Version ist die effizienteste der Varianten.

[pillmuncher]

Wenn wir schon blödeln, dann steuere ich eine Scheme-Lösung bei. Wäre gespannt was man mit Factor zaubern könnte

Factor kann ich nicht, aber Prolog:

Code: Alles auswählen

group(String, Groups) :-
    string_to_list(String, [C|Cs]),
    group(Cs, [C], Groups).

group([C|Cs], [C|Group], Groups) :-
    !,
    group(Cs, [C,C|Group], Groups).
group([C|Cs], Group, [String|Groups]) :-
    group(Cs, [C], Groups),
    string_to_list(String, Group).
group([], Group, [String]) :-
    string_to_list(String, Group).

Code: Alles auswählen

?- group("mississippi",G).
G = ["m", "i", "ss", "i", "ss", "i", "pp", "i"].

Da sieht man auch, wo ich das def _group(s, *ss): herhab

[ms4py]

Hab meine Lösung nochmal überarbeitet^^

Code: Alles auswählen

from itertools import tee, izip

def group(s):
    a, b = tee(s)
    output = list()
    output.append(b.next())
    for prev_char, char in izip(a, b):
        if prev_char == char:
            output[-1] += char
        else:
            output.append(char)
    return output

Prolog weckt düstere Erinnerungen... Konnte das noch nie leiden

[pillmuncher]

Code: Alles auswählen

    a, b = tee(s)
    output = list()
    output.append(b.next())

Das b.next() ist eine gute Idee:

Code: Alles auswählen

def group(cs):
    cs = iter(cs)
    s = cs.next()
    for c in cs:
        if c in s:
            s += c
        else:
            yield s
            s = c
    yield s

Prolog weckt düstere Erinnerungen... Konnte das noch nie leiden

Juhuu! Ein Sprachenkrieg Ich mochte Prolog schon immer, hatte auch nie irgendwelche Verständnis-Probleme (anders als bei Haskell ). Irgendwie scheint es der Verdrahtung meines Gehirns zu entsprechen. Und von Differenzlisten hab ich schon geträumt:

Code: Alles auswählen

?- asserta(append_dl(A - B, B - C, A - C)).
true.

?- append_dl([1,2,3|X] - X, [4,5,6|Y] - Y, Z - []).
X = [4, 5, 6],
Y = [],
Z = [1, 2, 3, 4, 5, 6] .

Gruß,
Mick.

[Nocta]

Fehlt nicht noch was rekursives?

Code: Alles auswählen

def group(s, res=[], i=0, j=1):
    if i >= len(s)-1:
        return res + [s[i]*j]
    if s[i] == s[i+1]:
        return group(s, res, i+1, j+1)
    else:
        return group(s, res + [s[i]*j], i+1)

Das würde ich zwar nicht als elegant bezeichnen aber darum poste ich's weil mir gerade kein guter rekursiver Weg einfällt und irgendjemand hier soll ihn mir offenbaren
(Ist zwar fast schon peinlich, aber ich bin hier ja anonym :p)

[BlackJack]

@Nocta: Ist auch nicht elegant, aber auch rekursiv:

Code: Alles auswählen

def group(xs, zs=''):
    if not xs:
        return ([zs] if zs else [])
    elif zs.startswith(xs[0]):
        return group(xs[1:], zs + xs[0])
    else:
        return ([zs] if zs else []) + group(xs[1:], xs[0])

[ms4py]

Fehlt nicht noch was rekursives?

Da war doch schon die Prolog-Lösung

[pillmuncher]

Vielleicht so? Also ohne Akkumulator?

Code: Alles auswählen

def group(cs, i=0, j=1):
    if j >= len(cs):
        return [cs[i:j]] if cs else []
    elif cs[i] == cs[j]:
        return group(cs, i, j+1)
    else:
        return [cs[i:j]] + group(cs, j, j+1)

Ich habe auch versucht das lazy zu machen, aber das Ergebnis ist zu schrecklich um es zu zeigen. Dann lieber nochmal iterativ:

Code: Alles auswählen

def group(cs):
    if cs:
        i = 0
        for j in xrange(1, len(cs)):
            if cs[i] != cs[j]:
                yield cs[i:j]
                i = j
        yield cs[i:]

Ich glaube, jetzt genügt's dann.

Gruß,
Mick.

[pillmuncher]

Oder doch nicht... Hier noch zwei Versionen mit anonymer rekursiver Funktion:

Code: Alles auswählen

def Y(r): return (lambda f: f(f))(lambda f: r(lambda *xs, **ys: f(f)(*xs, **ys)))

group1 = Y(
    lambda g:
        lambda cs, i=0, j=1:
                ([cs[i:j]] if cs else [])
            if j >= len(cs) else
                (g(cs, i, j+1) if cs[i] == cs[j] else [cs[i:j]] + g(cs, j, j+1))
)

def group2(cs):
    if not cs:
        return []
    return Y(
        lambda g:
            lambda s, c, *cs:
                    (g(s + c, *cs) if c in s else [s][:bool(s)] + g(c, *cs))
                if cs else 
                    ([s + c] if c in s else [s][:bool(s)] + [c])
    )('', *cs)

Ja, ich weiß, wenn man das gesehen hat möchte man sich am liebsten die Augen mit Seife auswaschen.

Danke im Übrigen an sma, der den Y-Kombinator in Python gebaut hat. Ich habe ihn ein wenig angepasst, damit man ihn mit den üblichen *args, **kwargs verwenden kann.

Gruß,
Mick.

[gerold]

Hallo Mik!

Dir ist es vielleicht nicht bewusst, dass ich Python gerne mag weil man sich bei Python "einfach und durchschaubar" auf die Fahne geschrieben hat. Das was du da mit Python anstellst, ist irgendwie die falsche Richtung. Ein "gutes" Python-Programm ist lesbar. Je lesbarer, desto besser. -- Es kann ruhig etwas länger sein und mit Kommentaren versehen werden. Hauptsache verständlich und leicht nachvollziehbar.

mfg
Gerold

[pillmuncher]

Das was du da mit Python anstellst, ist irgendwie die falsche Richtung.

Stimmt. Deswegen würde ich so etwas niemals im Ernst programmieren.

Gruß,
Mick.

[BlackJack]

Und etwas in C: http://paste.pocoo.org/show/150077/