AUFGABE: Jeden tag eine Änderung des Bankcodes...

[snafu]

@snafu: Kleiner Bug in der Funktion: die funktioniert nur für Codes ≥1000.

Edit: Und geht auch davon aus das der Code jemals wieder erreicht wird, was man ohne Begründung IMHO nicht so einfach annehmen darf.

Woran machst du fest, dass der Code nicht für Zahlen unter 1000 funktioniert? Der Code wird ja als String übergeben und danach werden die Ziffern einzeln betrachtet. Ich sehe da kein Problem mit führenden Nullen, falls das gemeint ist.

Und dass der Code theoretisch endlos laufen könnte, ist doch bei allen bisher gezeigten Lösungen so. Das ist ja vom Prinzip her ein typisches Halteproblem.

[snafu]

Man könnte natürlich einbauen, dass man nach 1 Million Versuchen aufgibt oder sowas. Ansonsten stelle ich mir das Erkennen von Zirkeln schwierig vor, da diese prinzipiell sehr groß sein können. Nur den Fall, dass alle Stellen auf Null stellen könnte man mit aufnehmen bzw wenn sich der Code unmittelbar wiederholt (bei 11 Einsen und ähnliches).

[Sirius3]

@snafu: eine n-stellige Zahl kann maximal 10^n Zustände annehmen. Da der interne Zustand des Automaten auch eine n-stellige Zahl ist, muß sich die Folge spätestens nach 10^n Schritten wiederholen.

[karolus]

Hallo

Der Code geht davon aus das man disjunkte Ringe/Kreise hat. Das muss man ja schon vorher wissen, oder irgendwie begründen können, dass der Graph so aussieht.

Bei der Betrachtung spätestens der Zweiten Zahlenreihe sollte einem schon auffallen das:
1.) jede Kombination nur jeweils einen eindeutigen Vorläufer|Nachfolger hat. ( haben kann!! )
2.) nur über einen begrenzten Vorat (hier 10**4) an Kombinationen iterieren kann.
3.) →irgenwann (<=10**4) Iterationen wieder jeder mögliche Ausgangspunkt erreicht wird.
4.) Aus 1.) folgt auch das es keine Schnittmengen zwischen verschiedenen Ringen geben kann.

Letzlich beweisst mein Code das ja empirisch.

[BlackJack]

@snafu: Okay ich hatte das nicht vorhandene Problem der führenden Nullen gesehen.

Das der Code endlos laufen könnte ist nicht bei allen Lösungen so. Der könnte zudem nicht nur theoretisch endlos laufen sondern auch praktisch, sofern man nicht vorher erklären kann warum jeder Code irgendwann wieder zu sich selbst führt.

Meine erweiterte Frage war ja: „Wie lange brauchen andere Kombinationen und wie viele Kombinationen gibt es, die nie wieder zum Ausgangscode zurückkehren?“

Wenn man also nicht (vorher) erklären kann warum es keine Kombination gibt, bei der nie wieder zum Ausgangscode zurückgekehrt wird, dann ist ein Programm das diese Frage nicht explizit berücksichtigt IMHO fehlerhaft, weil es die Frage nur dadurch beantwortet, weil es nicht hängengeblieben ist.

Und ja, den Fehler habe ich in meinem „von funktional nach OOP“ auch gemacht.

Die Lösungen von sebastian0202 und mein C-Programm berücksichtigen den Fall aber. Seins verwendet die -1 als Kennzeichen und meins 'inf'.

Halteproblem triffts nicht ganz weil es dort ja darum geht, dass ganz allgemein nicht beweisen kann ob ein beliebiges gegebenes Programm zum Ende kommt. Hier haben wir aber ein konkretes Programm, sogar ohne Eingaben von aussen und mit einer endlichen Wertemenge. Ob es hängen bleibt oder nicht, kann man als Grapgenproblem formulieren. Knoten sind die 10.000 Codes. Kanten bestehen zwischen Knoten die für einen Code und dessen Folgecode stehen. Zu beweisen wäre jetzt, dass jeder Code genau einen möglichen Vorgänger hat. Denn er hat auf jeden Fall einen Nachfolger. Wenn jeder genau einen Vor- und Nachgänger hat, dann muss der Graph aus einem oder mehreren Kreisen bestehen und somit käme auch jeder Code wieder zu sich selbst.

Ein Kreis kann nur maximal so gross sein wie es verschiedene Kombinationen gibt. Bei vier Stellen kann er also maximal 10.000 Codes umfassen. Eine Million Durchläufe wäre demnach eine sinnvolle Begrenzung für sechsstellige Codes. Alternativ muss man sich nur merken welche Codes man schon gesehen hat, damit man keinen, beziehungsweise nicht die falschen, mehr als einmal berechnet. Das ist eine Abwägung zwischen Laufzeit und Speicherverbrauch.

@karolus: 3. Sehe ich so ohne weitere Erklärung nicht. Es sind Graphen möglich die 1, 2, und 4 erfüllen, bei denen 3 nicht gilt.

[snafu]

@snafu: eine n-stellige Zahl kann maximal 10^n Zustände annehmen. Da der interne Zustand des Automaten auch eine n-stellige Zahl ist, muß sich die Folge spätestens nach 10^n Schritten wiederholen.

Prima. Damit hätte man schon einen guten Wert für's Limit.

[snafu]

Hallo

4.) Aus 1.) folgt auch das es keine Schnittmengen zwischen verschiedenen Ringen geben kann.

Letzlich beweisst mein Code das ja empirisch.

Nicht wirklich. Aus dem Zustand 0000 käme der Code bei den vorliegenden Regeln nicht mehr raus.

Ich wollte 3 zitieren. Bin gerade am Handy...

[karolus]

Hallo

@karolus: 3. Sehe ich so ohne weitere Erklärung nicht. Es sind Graphen möglich die 1, 2, und 4 erfüllen, bei denen 3 nicht gilt.

Da kann ich jetzt nicht ganz folgen, welche sollten das sein? (Wir sind uns doch darüber einig das kein Ring aus der gegebenen Grundmenge "ausbrechen" kann?)
Hätte ich 3. hinter 4.plazieren sollen?

Nicht wirklich. Aus dem Zustand 0000 käme der Code bei den vorliegenden Regeln nicht mehr raus.

'0000' → Nachfolger ist '0000'
Das ist dann lediglich ein Ring der Länge 1, ansonsten werden alle Regeln erfüllt.
Letzlich kommt kein Ring aus seinem "Zustand" heraus, sie sind nur unterschiedlich lang.

[snafu]

Es gibt mindestens eine Situation, wo der Ausgangspunkt nicht mehr erreicht wird. Wie gesagt, bei 0000 fährt er sich fest. Die Quersumme daraus ist Null. Diese wird hinten dran gehangen und es wird kein andere Zustand mehr erreicht. Insofern widerspricht dies deiner Annahme, dass spätestens nach 10^n Versuchen der Ausgangspunkt erreicht wird. Man kann nur folgern, dass nach 10^n Versuchen garantiert kein bis dahin unbekannter Zustand erreicht wird und man somit aufhören kann.

[BlackJack]

@karolus: Das hier sollte 1, 2, und 4 erfüllen:

[codebox=text file=Unbenannt.txt]1->2->3->4
^ |
| v
6<-5[/code]

Jeder hat genau einen Nachfolger, es gibt einen begrenzten Vorrat von 6 Knoten, es wird aber nicht für jeden Knoten nach spätestens 6 Schritten wieder der selbe Knoten erreicht. Daran ändert auch nichts das 4 gilt. Man könnte auch mehrere Komponenten dieser Art haben wenn es mehr Knoten gäbe. Und es könnte zu so einem Kreis auch mehrere ”Zufahrten” geben statt nur einer. Und mehrere ”eingehende Äste” bei den ”Zufahrten”.

Man müsste für ausschliesslich Kreise also noch zeigen, dass jeder Knoten auch genau *einen* Vorgänger hat.

@snafu: Beim Code '0000' hat man wie karolus schon sagte einen Kreis der Länge 0. Das heisst nach genau einem Tag/Schritt hat man den Ausgangszustand wieder erreicht. Da fährt sich nichts fest.

[snafu]

Ich meinte, dass ein Startcode in die Funktion gegeben wird, durch den im weiteren Verlauf irgendwann der Zustand 0000 erreicht wird. Dann käme die Schleife nie wieder zum Startcode zurück.

[karolus]

Hallo

Man müsste für ausschliesslich Kreise also noch zeigen, dass jeder Knoten auch genau *einen* Vorgänger hat.

Das könnte man ja beweisen indem man Ausgangsregel umgekehrt anwendet, und beides vergleicht.

Code: Alles auswählen

from itertools import product
from collections import Counter

def iter_code(code): 
    nextcode = code
    while True:
        nextcode = nextcode[1:] + (sum(nextcode) % 10,)
        if code == nextcode:
            return
        yield nextcode 
        
def iter_reverse(code):
    previous = code
    while True:
        y = (previous[-1] - (sum(previous[:-1])%10)) % 10
        previous = (y,) + previous[:-1]
        if  previous == code:
            return
        yield previous
        
                            

def main( function ):
    pool = set(product(range(10),repeat=4))
    ringcounter = Counter()    
    while pool:
        codering = [pool.pop()]
        codering.extend(list( function(codering[0])))
        pool = pool.difference(codering)
        ringcounter[len(codering)] += 1
    
    print("{}\nErgebnis unter Verwendung der Funktion {}: ".format('_' * 10, function.__name__))        
    kontrolle = 0
    for key, value in ringcounter.items():
        kontrolle += key * value
        print( "\t{} Codereihen aus {} Codes".format(value, key))
    print('_'*10)
    print("kontrollsumme ist {}\n{}\n".format(kontrolle, '=' * 20))
    return ringcounter
                
            
print(main(iter_code) == main( iter_reverse))

Ich meinte, dass ein Startcode in die Funktion gegeben wird, durch den im weiteren Verlauf irgendwann der Zustand 0000 erreicht wird. Dann käme die Schleife nie wieder zum Startcode zurück.

Dazu müsste ein Vorläufer > (0, 0, 0, 0) existieren der viermal in Folge eine (Quersumme modulo 10) == 0 produziert, ohne einen Übertrag.
Versuchen wir es mal mit: (0, 0, 1, 9) → (0, 1, 9, 0) → (1, 9, 0, 0) → (9, 0, 0, 0) … war wohl nix!

[snafu]

Zumindest bei mir war ja eine variable Anzahl an Stellen erlaubt. Für 0000 gilt es offenbar nicht, habe es auch nicht im Detail überprüft. Wenn ich gleich zuhause bin, dann schau ich mal ob ich ein belastbares Beispiel zum Widerlegen deines Punkt 3 finde.

[BlackJack]

@karolus: Hat natürlich gleich mal den doppelten Aufwand und funktioniert auch nur weil diese Bedingung gilt. Würde sie das nicht tun, sähe man das Ergebnis nie weil das Programm irgendwann mit einem `MemoryError` abbrechen würde. Eventuell nachdem vorher das System durch's swappen fast zum Stillstand gekommen ist.

Mal in Java mit einem einfachen Test ob jeder Code genau einen Vorgänger hat:

Code: Alles auswählen

import java.util.ArrayList;
import java.util.List;

public class Main {

    private static final int DIGIT_COUNT = 4;
    private static final int CODE_COUNT = (int) Math.pow(10, DIGIT_COUNT);
    private static final CodeInfo[] codeInfos = new CodeInfo[CODE_COUNT];
    private static final List<Cycle> cycles = new ArrayList<>();

    private static class CodeInfo {
        int nextCode;
        int cycleIndex = -1;

        CodeInfo(int nextCode) {
            this.nextCode = nextCode;
        }
    }

    private static class Cycle {
        int firstCode;
        int length = 0;

        Cycle(int firstCode) {
            this.firstCode = firstCode;
        }
    }

    private static int crossSum(int n) {
        int sum = 0;
        while (n > 0) {
            final int digit = n % 10;
            sum += digit;
            n = Math.floorDiv(n, 10);
        }
        return sum;
    }

    private static int calculateNextCode(int code) {
        return code * 10 % CODE_COUNT + crossSum(code) % 10;
    }

    private static void initializeCodeInfos() {
        for (int code = 0; code < codeInfos.length; code++) {
            codeInfos[code] = new CodeInfo(calculateNextCode(code));
        }
    }

    private static boolean hasJustCycles() {
        boolean[] hasIncoming = new boolean[codeInfos.length];

        for (CodeInfo info : codeInfos) {
            if (hasIncoming[info.nextCode]) return false;
            hasIncoming[info.nextCode] = true;
        }
        for (boolean b : hasIncoming) if (!b) return false;
        return true;
    }

    private static void createCycles() {
        for (int startCode = 0; startCode < codeInfos.length; startCode++) {
            if (codeInfos[startCode].cycleIndex == -1) {
                final Cycle cycle = new Cycle(startCode);
                int cycleIndex = cycles.size();
                int code = startCode;
                do {
                    cycle.length++;
                    final CodeInfo info = codeInfos[code];
                    info.cycleIndex = cycleIndex;
                    code = info.nextCode;
                } while (code != startCode);
                cycles.add(cycle);
            }
        }
    }

    private static void printCodeAndDayCount(int code) {
        System.out.printf(
                "Code %04d wird nach %d Tagen wieder erreicht.%n",
                code,
                cycles.get(codeInfos[code].cycleIndex).length);
    }

    private static void printCyclesInfo() {
        final int cycleCount = cycles.size();
        System.out.printf("Es gibt %d Zyklen.%n", cycleCount);
        for (int cycleIndex = 0; cycleIndex < cycleCount; cycleIndex++) {
            final Cycle cycle = cycles.get(cycleIndex);
            System.out.printf(
                    "Zyklus %d hat Länge %d und enthält Code %04d.%n",
                    cycleIndex,
                    cycle.length,
                    cycle.firstCode);
        }
    }

    public static void main(String[] args) {
        initializeCodeInfos();
        if (!hasJustCycles()) {
            System.out.println("Es gibt Codes die nie wieder erreicht werden.");
            return;
        }
        createCycles();
        printCodeAndDayCount(1986);
        printCyclesInfo();
    }
}

Falls sich jemand über den so gar nicht objektorientierten Stil wundert: Ich wollte möglichst wenig Speicher verbrauchen und eine bessere Laufzeit haben als das für jeden Startcode erneut durchzurechnen. Quasi ein Prototyp für den C64.

[BlackJack]

Juhuu, mit dem Ansatz schaffe ich es auf dem C64 in unter einer Minute für alle 10.000 Codes den Folgecode zu berechnen, zu prüfen ob jeder Code genau *einen* Vorgänger hat → alles Kreise, und die Gruppen/Kreise zu bestimmen/markieren. Ausgabe:
[codebox=text file=Unbenannt.txt]run
Folgecodes berechnen...
Pruefen ob jeder Code zyklisch ist...
Zyklen erstellen...
Code 1986 wird nach 1560d wiederholt.
Es gibt 12 Zyklen.
Zyklus 0: len 1, 1. Code 0000
Zyklus 1: len 1560, 1. Code 0001
Zyklus 2: len 312, 1. Code 0002
Zyklus 3: len 5, 1. Code 0005
Zyklus 4: len 1560, 1. Code 0010
Zyklus 5: len 1560, 1. Code 0012
Zyklus 6: len 1560, 1. Code 0015
Zyklus 7: len 312, 1. Code 0020
Zyklus 8: len 5, 1. Code 0050
Zyklus 9: len 1560, 1. Code 0111
Zyklus 10: len 1560, 1. Code 0113
Zyklus 11: len 5, 1. Code 0555
Laufzeit: 56983ms

ready.[/code]
Der Speicher ist ganz gut ausgenutzt. Von den ca. 50 Kilobyte die für Programm und Daten zur Verfügung stehen sind nur noch ca. 6 Kilobyte frei.
[codebox=c file=Unbenannt.c]#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define CODE_COUNT 10000
#define MAX_CYCLE_COUNT 100

typedef struct
{
uint16_t next_code;
uint8_t cycle_index;
} CodeInfo;

typedef struct
{
uint16_t first_code;
uint16_t length;
} Cycle;

typedef struct
{
uint8_t length;
Cycle items[MAX_CYCLE_COUNT];
} Cycles;

static CodeInfo code_infos[CODE_COUNT];
static Cycles cycles;

uint8_t cross_sum(uint16_t code)
{
uint8_t sum = 0;
div_t tmp;

while (code) {
tmp = div(code, 10);
code = tmp.quot;
sum += tmp.rem;
}
return sum;
}

void code_infos_init(void)
{
register uint16_t code;
register CodeInfo *info;

for (info = code_infos, code = 0; code < CODE_COUNT; ++info, ++code)
{
info->next_code = code % (CODE_COUNT / 10) * 10 + cross_sum(code) % 10;
info->cycle_index = 0xff;
}
}

bool has_just_cycles(void)
{
register uint16_t code;
register bool *has_incoming;
bool code_has_incoming[CODE_COUNT];

memset(code_has_incoming, false, sizeof(code_has_incoming));
for (code = 0; code < CODE_COUNT; ++code)
{
has_incoming = &code_has_incoming[code_infos

Code: Alles auswählen

.next_code];
        if (*has_incoming) return false;
        *has_incoming = true;
    }
    for (
        has_incoming = code_has_incoming, code = 0;
        code < CODE_COUNT;
        ++has_incoming, ++code
    ) {
        if (!*has_incoming) return false;
    }
    return true;
}

void create_cycles(void)
{
    register uint16_t code;
    register CodeInfo *info;
    register Cycle *cycle;
    register uint16_t start_code;

    cycles.length = 0;

    for (start_code = 0; start_code < CODE_COUNT; ++start_code)
    {
        if (code_infos[start_code].cycle_index == 0xff) {
            cycle = &cycles.items[cycles.length];
            cycle->first_code = code = start_code;
            cycle->length = 0;
            do {
                ++cycle->length;
                info = &code_infos[code];
                info->cycle_index = cycles.length;
                code = info->next_code;
            } while (code != start_code);
            ++cycles.length;
            if (cycles.length == MAX_CYCLE_COUNT) {
                printf("Mehr als %d Zyklen!\n", MAX_CYCLE_COUNT);
                exit(1);
            }
        }
    }
}

void print_code_and_day_count(uint16_t code)
{
    printf(
        "Code %04d wird nach %dd wiederholt.\n",
        code,
        cycles.items[code_infos[code].cycle_index].length
    );
}

void print_cycles_info(void)
{
    uint8_t i;

    printf("Es gibt %d Zyklen.\n", cycles.length);
    for (i = 0; i < cycles.length; ++i)
    {
        printf(
            "Zyklus %3d: len %4d, 1. Code %04d\n",
            i,
            cycles.items[i].length,
            cycles.items[i].first_code
        );
    }

}

int main(void)
{
    clock_t start_time = clock();
    clock_t end_time;

    puts("Folgecodes berechnen...");
    code_infos_init();
    puts("Pruefen ob jeder Code zyklisch ist...");
    if (!has_just_cycles()) {
        puts("Es gibt Codes die nie wieder erreicht\nwerden.");
        return 1;
    }
    puts("Zyklen erstellen...");
    create_cycles();
    end_time = clock();

    print_code_and_day_count(1986);
    print_cycles_info();
    printf("Laufzeit: %ldms\n", (end_time - start_time) * 1000 / CLOCKS_PER_SEC);

    return 0;
}

[sebastian0202]

Die vier Regeln gelten doch nur, weil wir den Code immer nur um eine Stelle verschieben.
Verschieben wir den Code um die Länge der Quersumme sieht das Ganze meiner Meinung nach anders aus.
Da gibt es Zahlen die immer wiederkehren, was letztendlich bedeutet, dass er sich in einer nie endenden Schleife befindet.

Code: Alles auswählen

def shift_code(code):
    summe = str(quersumme(code))
    abschneiden_ab = (len(code) - len(summe)) * -1
    return code[abschneiden_ab:]+summe

def quersumme(code):
    return sum(map(int, code))

def change_code(code):
    return shift_code(code)

def main():
    alter_code = "1986"
    neuer_code = alter_code
    
    doppelt_vorkommender_code = [0 for i in range(10**len(alter_code))]
    
    durchlauf = 0
    while durchlauf < 10**len(alter_code):
        durchlauf += 1
        neuer_code = change_code(neuer_code)
        doppelt_vorkommender_code[int(neuer_code)] += 1
        
        if neuer_code == alter_code:
            break
   
    print("Wir haben versucht den Ausgangscode (%s) wiederzuerreichen." % alter_code)
    print("Dabei wurde gezählt welche Zahl wie oft vorkam..")
    print("Hier die Zahlen die öfters als einmal vorkamen:")
    for nr, vorkommen in enumerate(doppelt_vorkommender_code):
        if vorkommen > 1: 
            print("Zahl %i kommt %i mal vor" % (nr, vorkommen))

if __name__ == '__main__':
    main()