[gelöst] Doppelte Zahlen in Zahlenreihe finde

rolle · 6 Juni 2009

Liebe Leute!

Ich muß öfters aus einer Reihe aus etwa 100 Ziffern doppelt darin vorkommende vierstellige Zahlen finden. Die Arbeitsschritte sind mir soweit schon klar, leider habe ich keinen Plan, welche Hilfsprogramme ich nutzen kann, wenn ich das mittels bash-Script lösen möchte. Die Schritte wären also:
- lies die ersten vier Ziffern ein
- vergleiche mit der Zahlenreihe, ob diese Folge öfters als einmal vorkommt
- falls ja, spucke die Reihe aus und mache weiter, falls nein, mache weiter
- lösche die erste Ziffer des Suchbegriffes und füge die nächste aus der Zahlenreihe an
- beginne bei Schritt zwei neu
- beende den Suchlauf am Ende der Zahlenkolonne

Bisher habe ich mich immer nur mit grep und ähnlichem beschäftigt, das bringt mich hier natürlich nicht weiter. Könnt Ihr mir Tips geben, welche Befehle sinnig wären, mein Ziel zu erreichen? Dann kann ich mich durch die entsprechenden Manpages wühlen und daran basteln.

abgdf · 6 Juni 2009

Hallo,

bash ist dafür nicht gemacht.

Ich sage (euch Hardcore-Konsoleros) nicht, daß es nicht mit bash geht (wenn man sich viel Mühe macht und dabei vollkommen unleserlichen Code produziert) (es ginge ja auch in Brainf***), aber z.B. mit Perl wäre es deutlich einfacher.

Gruß

abgdf · 6 Juni 2009

Also, ein doppeltes Vorkommen einer Zahl zu finden, könnte in Perl z.B. so aussehen:

Code:

#!/usr/bin/perl

use warnings;
use strict;

my $a = "2029391155752187917800815691752145081795637536784752115506597167913215680688171036321405805485832255";

my $b = "7521";

my $i;
my $nr = 0;

for ($i = 0; $i < length($a) - 3; $i ++) {
    if (substr($a, $i, 4) eq $b) {
        $nr ++;
    }

    if ($nr > 1) {
        print "$a\n";
        exit();
    }
}

Woher sollen die zu suchenden vierstelligen Zahlen eingelesen werden? Aus der (ca.) hundertstelligen Zahlenfolge selbst?

- falls ja, spucke die Reihe aus

Die Reihe (hundertstellig) oder die Zahl (vierstellig)?

Gruß

Anonymous · 6 Juni 2009

in AWK könnte das die Ausgangssituation werden.

Code:

while read line
 do
 echo "$line" | awk '{print $0; for(i=1;i<length($0)-2;i++)test[substr($0,i,4)]++;for(i in test) if (test[i] > 1) print i}END {print "\n"}'
 done < DATEI

Es wird zeilenweise an AWK übergeben und jeweils die Zeile ausgegeben und wenn mehrere Vorkommen sind dann werden sie unten angezeigt. Im Moment sucht er aber nicht nur alle Zahlenkombinationen sondern BuchstabenZahlenSonderzeichen-Kombinationen so wie sie grade anfallen.

robi

haveaniceday · 6 Juni 2009

Als Shell-fan würde ich mich mit bash beschäftigen.
Wichtig bei den Schleifen ist, dass keine externen Programme wie sed, grep, etc. aufgerufen werden.
Dann können viele Schleifendurchläufe durch die vielen Forks langsam werden.

Haveaniceday

Code:

#!/bin/bash

a="20293911557202952187917800815691752145081795637536784752115506597167913215680688171036321405805485832255"
BOLD="`tput bold`"
NORMAL="`tput sgr0`"
while [ -n "$a" ]
do
        part="${a:0:4}"
        rest="${a:1}"
        match="${rest/$part/${BOLD}${part}${NORMAL}}"
        [ "$rest" != "$match" ] && echo found $part in $match
        a="$rest"
done

abgdf · 7 Juni 2009

Hallo,

ich gehe mal davon aus, daß die vierstelligen Zahlen nacheinander aus der hundertstelligen Zahlenfolge genommen werden sollen. Dann würde das in einem ganzen Perlskript z.B. so aussehen:

Code:

#!/usr/bin/perl

use warnings;
use strict;

my $a = "2029391155752187917800815691752145081795637536784752115506597167913215680688171036321405805485832255";

my @f = ();
my $x = 0;
my $nr;

for (0 .. length($a) - 4) {
    my $b = substr($a, $_, 4);
    for (@f) {
        if ($_ eq $b) {
            $x = 1;
        }
    }
    if ($x) {
        $x = 0;
        next;
    } 

    $nr = 0;

    for (0 .. length($a) - 4) {
        if (substr($a, $_, 4) eq $b) {
            $nr++;
        }
        if ($nr > 1) {
            push(@f, $b);
            last;
        }
    }
}

for (@f) {
    print "$_\n";
}

Aus diesem Code kannst Du zur Not auch einen Einzeiler machen, den Du mit "echo" über eine Pipe aufrufst oder auch in ein bash-Skript einbauen kannst. Das sähe dann z.B. so aus:

Code:

echo 2029391155752187917800815691752145081795637536784752115506597167913215680688171036321405805485832255 | perl -e 'while(<>) { $a = $_; @f = (); $x = 0; $nr; for (0 .. length($a) - 4) { $b = substr($a, $_, 4); for (@f) { if ($_ eq $b) { $x = 1; } } if ($x) { $x = 0; next; } $nr = 0; for (0 .. length($a) - 4) { if (substr($a, $_, 4) eq $b) { $nr++; } if ($nr > 1) { push(@f, $b); last; } } } for (@f) { print "$_\n"; } }'

Nicht sehr schön, so ein Einzeiler, zugegeben :roll:.

Auch die anderen Ansätze finde ich nicht schlecht.

Viele Grüße

rolle · 7 Juni 2009

Na dann habe ich ja einiges zum durchlesen.

Vielen Dank.

abgdf · 7 Juni 2009

... nochmal sehr viel kürzer mit Perls "grep"-Funktion (die aber ganz anders arbeitet als der Unix-"grep"-Befehl):

Code:

echo "2029391155752187917800815691752145081795637536784752115506597167913215680688171036321405805485832255" | perl -e 'chomp($a = <>); @b = (); @c = (); for (0 .. length($a) - 4) { push(@b, substr($a, $_, 4)); } foreach $i (@b) { if (grep /$i/, @c) { next; } if (grep(/$i/, @b) > 1) { push(@c, $i); } } foreach (@c) { print "$_\n"; }'

Gruß

haveaniceday · 7 Juni 2009

abgdf schrieb:
..daß es nicht mit bash geht (wenn man sich viel Mühe macht und dabei vollkommen unleserlichen Code produziert
...

Hmm, wenn ich diesen Thread so mit der Perlsyntax ansehe glaub ich an eine Verwechselung.
Ein Hardcore-Konsolero

framp · 7 Juni 2009

Man kann jeden Code durch nicht sprechende VariablenNamen, fehlende Einrückung und fehlende Kommentare unleserlich machen.

Code:

echo "2029391155752187917800815691752145081795637536784752115506597167913215680688171036321405805485832255" |

perl -e '

# für alle Zeilen
chomp($zeile = <>);

# initialisierung
@zahlen4 = ();
@zahlen4_mehrmals = ();

# bilde 4er Gruppen
for (0 .. length($zeile) - 4) {
        push(@zahlen4, substr($zeile, $_, 4));
        }

# durchlaufe alle 4er Gruppen und prüfe ob sie noch einmal vorkommt
foreach $i (@zahlen4) {
        if (grep /$i/, @zahlen4_mehrmals) {
                next;   # 4er Gruppe schon gefunden
        }

        if (grep(/$i/, @zahlen4) > 1) {
                push(@zahlen4_mehrmals, $i); # neue 4er Gruppe gefunden -> merken
        }
}

# Ergebnisausgabe
foreach (@zahlen4_mehrmals) {
        print "$_\n";
}'

liest sich wohl schon leichter - oder :roll:

Allerdings hätte ich mir bei diesen paar Zeilen auch die zusätzliche TippArbeit mit sprechenden Variablen und Kommentaren geschenkt.

Anonymous · 7 Juni 2009

Na damit hast du ja ne ganze Menge grundverschiedener Lösungsallgorithmen zur Auswahl, die unabhängig der dabei verwendeten Programiersprache ansich schon mal recht bemerkenswert und interessant sind.

Perl über Stackfunktionen
Perl über Doppelschleife
Eine sehr schöne Bashinterne Lösung
AWK über Assoziativem Array

Soll mal (k)einer behaupten wir sind hier nicht creativ

robi

rolle · 10 Juni 2009

Ihr seid toll.

Ich habe mich jetzt mal darangemacht und beginne die Bashlösung zu verstehen. Die Perllösungen kann ich zwar lesen und verstehen, allerdings wollte ich gleich die Gelegenheit nutzen und meine Bashkenntnisse vertiefen. AWK ist mir momentan dann doch noch zu sperrig.
Jedenfalls vielen lieben Dank für Eure Mühen.

}-Tux-{ · 13 Juni 2009

Hmm hier noch eine andere perl Variante.

Code:

#!/usr/bin/perl
use strict;
use warnings;
my $str = "2029391155752187917800815691752145081795637536784752115506597167913215680688171036321405805485832255";
for (0 .. length($str) - 4) {
  my $s = substr($str, $_, 4);
  print "$s\n" if substr($str, $_ + 4, length($str)) =~ /\Q$s\E/;
}

}-Tux-{

framp · 13 Juni 2009

Für Freunde der regulären Ausdrücke :roll: :

Code:

#!/usr/bin/perl -w

use warnings;
use strict;

my %aa = ();
while (<>) {
        while (/(\d{4})/g) {
                pos($_)-=3;
                if (/($1).+\1/ && not exists $aa{$1}) {
                        print "$1\n";
                        $aa{$1}++;
                }
        }
}

abgdf · 13 Juni 2009

... der Code von }-Tux-{ nochmal in Python (2.x):

Code:

#!/usr/bin/env python

a = "2029391155752187917800815691752145081795637536784752115506597167913215680688171036321405805485832255"

for i in range(len(a) - 4):
    s = a[i : i + 4]
    if s in a[i + 4 : ]:
        print s

Gruß

[gelöst] Doppelte Zahlen in Zahlenreihe finde

rolle

abgdf

abgdf

Anonymous

Gast

haveaniceday

abgdf

rolle

abgdf

haveaniceday

framp

Moderator

Anonymous

Gast

rolle

}-Tux-{

framp

Moderator

abgdf