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

[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()