Votación en pluralidad con autómatas celulares

31

Hay un problema realmente importante en los autómatas celulares llamado el problema Mayoritario :

El problema mayoritario o la tarea de clasificación de densidad es el problema de encontrar reglas de autómatas celulares unidimensionales que realicen con precisión el voto mayoritario.

...

Dada una configuración de un autómata celular de dos estados con un total de celdas i + j, i de las cuales están en el estado cero yj de las cuales están en el estado único, una solución correcta al problema de votación eventualmente debe establecer todas las celdas en cero si i> j y eventualmente debe establecer todas las celdas en una si i <j. El estado eventual deseado no se especifica si i = j.

Aunque se ha demostrado que ningún autómata celular puede resolver el problema mayoritario en todos los casos, existen muchas reglas que pueden resolverlo en la mayoría de los casos. El autómata Gacs-Kurdyumov-Levin tiene una precisión de aproximadamente el 78% con condiciones iniciales aleatorias. La regla GKL no es complicada:

  • Radio de 3, lo que significa que el nuevo estado de la celda depende de 7 celdas anteriores: en sí, las 3 celdas a la derecha y las 3 celdas a la izquierda.
  • Si una celda está actualmente O, su nuevo estado es la mayoría de sí misma, la celda a su izquierda y la celda 3 pasos a su izquierda.
  • Si una celda está actualmente 1, su nuevo estado es la mayoría de sí misma, la celda a su derecha y la celda 3 pasos a su derecha.

Aquí hay un ejemplo:

0 1 0 1 1 1 0 1 1 0 1 0 0 1
0 1 1 1 1 1 1 1 0 0 1 1 0 0
0 1 1 1 1 1 1 1 1 0 1 0 0 0
0 1 1 1 1 1 1 1 0 1 0 1 0 0
0 1 1 1 1 1 1 0 1 0 1 0 1 0
0 1 1 1 1 1 0 1 0 1 0 1 1 1
1 1 1 1 1 0 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1

En este ejemplo, el autómata celular calculó correctamente que 8> 6. Otros ejemplos toman períodos de tiempo más largos y producen algunos patrones interesantes mientras tanto. A continuación hay dos ejemplos que encontré al azar.

0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 1
1 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1

Llévandolo al siguiente nivel

Por lo que mi investigación en Internet ha demostrado, casi toda la investigación académica sobre el problema mayoritario se realizó con AC de 2 estados. En este desafío, vamos a expandir el problema mayoritario a las AC de 3 estados . Llamaré a esto el problema de la pluralidad . La pluralidad , o mayoría relativa, se refiere a la condición en la que una de las opciones tiene más votos que cada una de las alternativas, pero no necesariamente una mayoría de todos los votos.

Planteamiento del problema

  1. Hay un autómata celular 1D de 3 estados con radio 3.
  2. Hay 151 celdas con una condición de contorno circular.
  3. Estas celdas tienen un estado inicial aleatorio, con la única condición de que 1 de los 3 estados tenga una pluralidad estricta. "Aleatorio" significa una distribución uniforme independiente para cada celda.
  4. La precisión de una regla es el porcentaje de condiciones iniciales aleatorias (válidas) en las que todas las celdas se sincronizan con el estado correcto (el que tiene pluralidad) dentro de 10000 generaciones .
  5. El objetivo es encontrar una regla con alta precisión,

Casos extremos de pluralidad: cualquier configuración con 50/50/51 es una configuración de inicio válida (ya que existe una pluralidad estricta), mientras que cualquier configuración con 51/51/49 no es válida (ya que no existe una pluralidad estricta).

El espacio de búsqueda es 3 ^ 3 ^ 7 (~ 3e1043), muy fuera del alcance de cualquier búsqueda exhaustiva. Esto significa que deberá utilizar otras técnicas, como algoritmos genéticos, para resolver este problema. También tomará algo de ingeniería humana.

La regla de generación 10000 está sujeta a cambios, dependiendo de los tiempos de ejecución / precisión de las reglas que las personas encuentran. Si es demasiado bajo para permitir tasas razonables de convergencia, entonces puedo aumentarlo. Alternativamente, puedo bajarlo para que sirva de desempate.

Victorioso

El ganador es la persona que presenta la regla CA de radio 3 con la mayor precisión de todos los concursantes.

Su envío debe incluir ...

  • Una descripción de la regla (usando el código Wolfram si es necesario)
  • La tasa de precisión y el tamaño de la muestra.
  • Una explicación de tamaño razonable de cómo descubrió la regla, incluidos los programas que escribió para resolverla, o cualquier ingeniería "manual". (Esta es la parte más interesante, ya que todo lo demás son solo números en bruto).

Trabajo prioritario

  • Un artículo de Juille y Pollack , que describe cómo evolucionaron una regla de 2 estados con un 86% de precisión.
  • Este artículo utilizó r = 3, 149 celdas, CA de 2 estados. No trató sin embargo a la mayoría resuelve el problema, pero en lugar de encontrar rápidamente las reglas que resultan en una alternancia de todo- 1-todos- 0patrón. A pesar de estas diferencias, sospecho que muchas técnicas serán similares.
  • Un documento (no muy útil porque está detrás de un muro de pago) de Wolz y de Oliviera, que actualmente tienen el récord de 2 estados
PhiNotPi
fuente
Estaba muy decepcionado / sorprendido de encontrar que esto no tiene nada que ver con la Votación en pluralidad .
gato
2
@cat Realmente siento que sí. El estado de cada celda podría representar su "voto" (elección de 1 de 3 candidatos), y el objetivo es determinar el ganador de la elección.
PhiNotPi
2
Este es un desafío de código interesante. No soy golfista, así que siempre es un placer ver este tipo de rompecabezas.
Draco18s

Respuestas:

6

Tipo de GKL más escalada, 61.498%

  • Si una celda es un 0, mira las celdas 3 a la izquierda, 1 a la izquierda y a sí misma. Establecer el valor a la mayoría. Si es un empate, quédese como está.

  • Si una celda es un 1, mira las celdas 3 a la derecha, 1 a la derecha y a sí misma. Establecer el valor a la mayoría. Si es un empate, quédese como está.

  • Si una celda es un 2, mira las celdas 2 a la izquierda, 2 a la derecha y 3 a la derecha. Establecer el valor a la mayoría. Si es un empate, quédese como está.

Obtuve 59453 de un total de 100000, 59.453%

Algunas mutaciones y escaladas resultaron en 61498/100000 = 61.498%.

Probablemente probaré un poco más y publicaré más información más adelante.

Michael Stocker
fuente
3
Probablemente debería incluir la regla real de 61.498% para que las personas puedan verificarla.
Martin Ender
Probablemente deberías hacer las pruebas que harás.
Erik the Outgolfer
5

"Solo tira los 2 y haz GKL" - 55.7%

No es tan fácil adivinar cuál sería una buena regla, así que intenté al menos llegar a algo que obtuviera un puntaje superior a 1/3. La estrategia es tratar de obtener la respuesta correcta cuando el estado mayoritario es 0 o 1, y aceptar la pérdida si es 2. Obtuvo un puntaje de 56.5% en 100,000 ensayos, que de alguna manera es ligeramente mejor de lo que se esperaría de multiplicar 78% ( puntaje de GKL) * 2/3 (fracción del tiempo cuando la respuesta es 0 o 1) = 52%.

Más concretamente, la estrategia es la siguiente:

  • Si la celda es 0 o 1, tome la mayoría de las 3 celdas como en la estrategia GKL, pero ignore cualquier vecino que sea 2. Si es un empate, deje la celda sin cambios.
  • Si la celda es 2, elija la que sea más numerosa de 0 o 1 en todo el vecindario. Si es un empate, elija el valor más a la izquierda que sea 0 o 1. Si todos los vecinos son 2, quédese 2.

Usé este código para probar:

#include <iostream>
#include <algorithm>
#include <string.h>
#include <random>
#include <cassert>

#define W 151
#define S 3
#define R 3

typedef int state;

struct tape {
    state s[R+W+R];
    state& operator[](int i) {
        return s[i + R];
    }
    template<typename Rule> void step(Rule r) {
        for(int i = 0; i < R; i++) s[i] = s[W + i];
        for(int i = 0; i < R; i++) s[R + W + i] = s[R + i];
        for(int i = 0; i < W; i++) {
            s[i] = r(s + R + i);
        }
        memmove(s + R, s, W * sizeof(*s));
    }

    state unanimous() {
        state st = (*this)[0];
        for(int i = 1; i < W; i++) {
            if((*this)[i] != st)
                return -1;
        }
        return st;
    }
};

std::ostream& operator<<(std::ostream& s, tape& t) {
    for (int i = 0; i < W; i++)
        s << t[i];
    return s;
}

state randomize(tape& t) {
    static std::mt19937 rg(390332);
    begin:
    int c[S]{};
    for(int i = 0; i < W; i++) {
        state s = rg() % S;
        c[s]++;
        t[i] = s;
    }
    state* smax = std::max_element(c, c + R);
    int nmaj = 0;
    for (int n : c) nmaj += n == *smax;
    if (nmaj > 1) goto begin;
    return smax - c;
}

template<bool PrintSteps, typename Rule> int simulate(Rule r, int trials, int giveup) {
    int successes = 0;
    for(state s = 0; s < S; s++) {
        state t[2 * R + 1];
        for(int i = 0; i <= 2 * R; i++) t[i] = s;
        assert(r(t + R) == s);
    }
    while(trials--) {
        tape tp;
        state desired = randomize(tp);
        int steps = giveup;
        while(steps--) {
            tp.step(r);
            state u = tp.unanimous();
            if(~u) {
                bool correct = u == desired;
                if(PrintSteps) {
                    std::cout << correct << ' ' << giveup - steps << '\n';
                }
                successes += correct;
                break;
            }
        }
    }
    return successes;
}


struct ixList {
    int n;
    int i[2 * R + 1];
};



state rule_justTossOutThe2sAndDoGKL(const state* t) {
    const ixList ixl[] = {
        { 3,{ -3, -1, 0 } },
        { 3,{ 0, 1, 3 } },
        { 6,{ -3, -2, -1, 1, 2, 3 } } 
    };
    int c[S]{};
    for (int i = 0; i < ixl[*t].n; i++)
        c[t[ixl[*t].i[i]]]++;
    if (c[0] > c[1]) return 0;
    if (c[1] > c[0]) return 1;
    if (*t < 2) return *t;
    for (int i = -R; i <= R; i++)
        if (t[i] < 2) return t[i];
    return 2;
}

int main()
{
    int nt = 100000;
    int ns = simulate<false>(rule_justTossOutThe2sAndDoGKL, nt, 10000);

    std::cout << (double)ns / nt << '\n';
    return 0;
}
Feersum
fuente
El puntaje es más alto de lo que cabría esperar porque aumenta con el límite de generación. La puntuación del 78% de GKL es en realidad para un límite muy pequeño de unos cientos de gens más o menos. En contraste, 10,000 gens le darían a GKL una mayor tasa de precisión, probablemente en línea con los resultados que está obteniendo.
PhiNotPi
2

"Solo roba lo que sea mejor y evoluciona", bleh

Editar: en su estado actual, esta respuesta, en lugar de encontrar mejores patrones, encuentra una mejor muestra aleatoria.

Esta respuesta codifica / decodifica soluciones enumerando todos los estados como números ternarios (primero el dígito menos significativo). La solución para 59.2%:

000000000010010010000000000000000000000000000000000000000000010000010000110000000
000000000010010010000000000111111101111111111111111111000011000010011011000011010
000000000012010011001000000021111111111120111211111111000000000000011010000010000
000011000010022110000000202000000002000000000020000000001010000000011011000011010
020000000010010010001000000111101111111111111111111111010011000011111111010011010
000000000010010010000000000111111111101111111111112111000011010110111011010011011
000000000010010010000000000010000000000000000100002011000000000100011010020010000
000020020010010010000200000111102111111111111111111101000011010010111011000011011
000100000010010010000000000121111111111111111111111111000210000012011011002011010
000000000010010110000000000111112112111111111001111111000010000010011011000011010
000000000010010120000200000111211111111111111111110111110011010011100111010011011
000000000010010010000000000011111111111111111111111111000011010010111211210012020
010000000010010010020100020111110111111111111111111110010111010011011111010111011
002000000010010010000000000111110111111111211111111111001111111111111111111111111
000000000110010010000000000111111111111111211111111111010111011111111111011111011
001000000010010010000000000011111101111111111111110111000011010010111011010011010
001000000010010110000000000111111111111111102111110111010111011111111111011111101
000000000210010010000000000111111111111111111111011111010011010011111111010111011
000000000010010010000000000112111111111111111111101011000000000000011010000010000
000000000010010010000000000111111111111111111111111111000011010010111011010011011
000200000012010010000000000111111111111112111111111111000010000210011211001011010
000000000010010211000002000111111111111111111111111111000001010010111011010011010
000021200010210010000101100111111111111211111110110211010111021111111101010111111
000000000010010010000000000111111111111101111111111111010011010111111111010110021
000200000010010010000000010111111111101111111121112111000210001010011011000011010
000000000010010010000000000111111111111111111111111111210011010021111111010111011
000020000010010010000000000111111111111111111111111111000011010010121011010011012

Esta respuesta se desarrolló a partir del 55.7% de feersum, utilizando el siguiente código. Este código requiere libop , que es mi biblioteca personal de solo encabezado C ++. Es muy fácil de instalar, solo hazlo git clone https://github.com/orlp/libopen el mismo directorio donde guardaste el programa. Sugiero compilar con g++ -O2 -m64 -march=native -std=c++11 -g. Para un desarrollo rápido, también sugiero precompilar libop ejecutando el comando anterior en libop/op.h.

#include <cstdint>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <random>

#include "libop/op.h"

constexpr int MAX_GENERATIONS = 500;
constexpr int NUM_CELLS = 151;

std::mt19937_64 rng;

double worst_best_fitness;

// We use a system with okay-ish memory density. We represent the ternary as a
// 2-bit integer. This means we have 32 ternaries in a uint64_t.
//
// There are 3^7 possible states, requiring 4374 bits. We store this using 69
// uint64_ts, or little over half a kilobyte.

// Turn 7 cells into a state index, by encoding as ternary.
int state_index(const int* cells) {
    int idx = 0;
    for (int i = 0; i < 7; ++i) {
        idx *= 3;
        idx += cells[6-i];
    }
    return idx;
}

// Get/set a ternary by index from a 2-bit-per-ternary encoded uint64_t array.
int get_ternary(const uint64_t* a, size_t idx) {
    return (a[idx/32] >> (2*(idx % 32))) & 0x3;
}

void set_ternary(uint64_t* a, size_t idx, int val) {
    assert(val < 3);
    int shift = 2*(idx % 32);
    uint64_t shifted_val = uint64_t(val) << shift;
    uint64_t shifted_mask = ~(uint64_t(0x3) << shift);
    a[idx/32] = (a[idx/32] & shifted_mask) | shifted_val;
}


struct Rule {
    uint64_t data[69];
    double cached_fitness;

    Rule(const char* init) {
        cached_fitness = -1;
        for (auto i : op::range(69)) data[i] = 0;
        for (auto i : op::range(2187)) set_ternary(data, i, init[i] - '0');
    }

    double fitness(int num_tests = 1000);

    Rule* random_mutation(int num_mutate) const {
        auto new_rule = new Rule(*this);

        auto r = op::range(2187);
        std::vector<int> indices;
        op::random_sample(r.begin(), r.end(),
                          std::back_inserter(indices), num_mutate, rng);

        for (auto idx : indices) {
            set_ternary(new_rule->data, idx, op::randint(0, 2, rng));
        }

        new_rule->cached_fitness = -1;
        return new_rule;
    }

    int new_state(const int* cells) const {
        return get_ternary(data, state_index(cells));
    }

    void print_rule() const {
        for (auto i : op::range(2187)) {
            std::cout << get_ternary(data, i);
            if (i % 81 == 80) std::cout << "\n";
        }
    }
};


struct Automaton {
    uint64_t state[5];
    int plurality, generation;

    Automaton() : generation(0) {
        for (auto i : op::range(5)) state[i] = 0;

        int strict = 0;
        while (strict != 1) {
            int votes[3] = {};
            for (auto i : op::range(NUM_CELLS)) {
                int vote = op::randint(0, 2, rng);
                set_ternary(state, i, vote);
                votes[vote]++;
            }

            // Ensure strict plurality.
            plurality = std::max_element(votes, votes + 3) - votes;
            strict = 0;
            for (auto i : op::range(3)) strict += (votes[i] == votes[plurality]);
        }
    }

    void print_state() {
        for (int i = 0; i < 151; ++i) std::cout << get_ternary(state, i);
        std::cout << "\n";
    }

    bool concensus_reached() {
        int target = get_ternary(state, 0);
        for (auto i : op::range(NUM_CELLS)) {
            if (get_ternary(state, i) != target) return false;
        }

        return true;
    }

    void next_state(const Rule& rule) {
        uint64_t new_state[5] = {};

        std::vector<int> cells;
        for (auto r : op::range(-3, 4)) {
            cells.push_back(get_ternary(state, (r + NUM_CELLS) % NUM_CELLS));
        }

        for (auto i : op::range(NUM_CELLS)) {
            set_ternary(new_state, i, rule.new_state(cells.data()));
            cells.erase(cells.begin());
            cells.push_back(get_ternary(state, (i + 4) % NUM_CELLS));
        }

        for (auto i : op::range(5)) state[i] = new_state[i];
        generation++;
    }
};


double Rule::fitness(int num_tests) {
    if (cached_fitness == -1) {
        cached_fitness = 0;
        int num_two = 0;
        for (auto test : op::range(num_tests)) {
            Automaton a;
            while (a.generation < MAX_GENERATIONS && !a.concensus_reached()) {
                a.next_state(*this);
            }

            if (a.generation < MAX_GENERATIONS &&
                get_ternary(a.state, 0) == a.plurality &&
                a.plurality == 2) num_two++;

            cached_fitness += (a.generation < MAX_GENERATIONS &&
                               get_ternary(a.state, 0) == a.plurality);

            if (cached_fitness + (num_tests - test) < worst_best_fitness) break;
        }

        if (num_two) std::cout << cached_fitness << " " << num_two << "\n";

        cached_fitness;
    }

    return cached_fitness;
}



int main(int argc, char** argv) {
    std::random_device rd;
    rng.seed(42); // Seed with rd for non-determinism.

    const char* base = 
        "000000000010010010000000000000000000000000000000000000000000000000010000000000000"
        "000000000010010010000000000111111111111111111111111111000010000010011011000011010"
        "000000000010010010000000000111111111111111111111111111000000000000011010000010000"
        "000000000010010010000000000000000000000000000000000000000010000010011011000011010"
        "000000000010010010000000000111111111111111111111111111010011010011111111010111011"
        "000000000010010010000000000111111111111111111111111111000011010010111011010011011"
        "000000000010010010000000000000000000000000000000000000000000000000011010000010000"
        "000000000010010010000000000111111111111111111111111111000011010010111011010011011"
        "000000000010010010000000000111111111111111111111111111000010000010011011000011010"
        "000000000010010010000000000111111111111111111111111111000010000010011011000011010"
        "000000000010010010000000000111111111111111111111111111010011010011111111010111011"
        "000000000010010010000000000111111111111111111111111111000011010010111011010011010"
        "000000000010010010000000000111111111111111111111111111010011010011111111010111011"
        "000000000010010010000000000111111111111111111111111111011111111111111111111111111"
        "000000000010010010000000000111111111111111111111111111010111011111111111011111111"
        "000000000010010010000000000111111111111111111111111111000011010010111011010011010"
        "000000000010010010000000000111111111111111111111111111010111011111111111011111111"
        "000000000010010010000000000111111111111111111111111111010011010011111111010111011"
        "000000000010010010000000000111111111111111111111111111000000000000011010000010000"
        "000000000010010010000000000111111111111111111111111111000011010010111011010011011"
        "000000000010010010000000000111111111111111111111111111000010000010011011000011010"
        "000000000010010010000000000111111111111111111111111111000011010010111011010011010"
        "000000000010010010000000000111111111111111111111111111010111011111111111011111111"
        "000000000010010010000000000111111111111111111111111111010011010011111111010111011"
        "000000000010010010000000000111111111111111111111111111000010000010011011000011010"
        "000000000010010010000000000111111111111111111111111111010011010011111111010111011"
        "000000000010010010000000000111111111111111111111111111000011010010111011010011012"
    ;

    // Simple best-only.
    std::vector<std::unique_ptr<Rule>> best_rules;
    best_rules.emplace_back(new Rule(base));
    worst_best_fitness = best_rules.back()->fitness();
    while (true) {
        const auto& base = *op::random_choice(best_rules.begin(), best_rules.end(), rng);
        std::unique_ptr<Rule> contender(base->random_mutation(op::randint(0, 100, rng)));

        // Sort most fit ones to the beginning.
        auto most_fit = [](const std::unique_ptr<Rule>& a, const std::unique_ptr<Rule>& b) {
            return a->fitness() > b->fitness();
        };

        if (contender->fitness() >= best_rules.back()->fitness()) {
            std::cout << contender->fitness();
            double contender_fitness = contender->fitness();
            best_rules.emplace_back(std::move(contender));
            std::sort(best_rules.begin(), best_rules.end(), most_fit);
            if (best_rules.size() > 5) best_rules.pop_back();
            std::cout << " / " << best_rules[0]->fitness() << "\n";
            worst_best_fitness = best_rules.back()->fitness();

            if (contender_fitness == best_rules.front()->fitness()) {
                best_rules.front()->print_rule();
            }
        }
    }

    return 0;
}
orlp
fuente
0

Codificado a mano, 57.541%

En realidad, esto solo mira las 5 celdas por encima. Probablemente podría mejorarse aumentando el rango que observa. Funcionó con 100,000 casos de prueba.

Algoritmo:

If above == 0:
   if to the left there are only 2s or there is a 1 separated by 2s
       next state = 2
   else
       next state = 0
If above == 1:
   if to the right there are only 2s or there is a 0 separated by 2s
       next state = 2
   else
       next state = 1
If above == 2:
   ignore 0s to the left if the 0 is left of a 1 on the left
   ignore 1s to the right if the 1 is right of a 0 on the right
   if the closest 0 on the left is closer than the closest 1 on the right
       next state = 0
   else if the closest 1 on the right is closer than the closest 0 on the left
       next state = 1
   else
       next state = 2

Gene:

000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222111111111111111111111111111000222222111111111111111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222222222222222222222222222222000000000222222222222222222
000000000222222222000222222111111111111111111111111111222111111111111111111111111
000000000222222222000222222111111111111111111111111111000000000111111111222111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222111111111111111111111111111000222222111111111111111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222111111111111111111111111111000222222111111111111111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222222222222222222222222222222000000000222222222222222222
000000000222222222000222222111111111111111111111111111222111111111111111111111111
000000000222222222000222222111111111111111111111111111000000000111111111222111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222111111111111111111111111111000222222111111111111111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222111111111111111111111111111000222222111111111111111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222222222222222222222222222222000000000222222222222222222
000000000222222222000222222111111111111111111111111111222111111111111111111111111
000000000222222222000222222111111111111111111111111111000000000111111111222111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222111111111111111111111111111000222222111111111111111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222

Código de prueba:

import java.lang.Math.*
import java.util.*

const val RADIUS = 3;
const val STATES = 3;
const val DIAMETER = 2 * RADIUS + 1
const val TAPE_LENGTH = 151

val CODE_SIZE = pow(STATES.toDouble(), DIAMETER.toDouble()).toInt()

const val GRADE_RUNS = 100000
const val GRADE_MAX_TIME = 10000


operator fun IntArray.inc() : IntArray {
    val next = this.clone()
    var i = 0
    while (i < size) {
        if (this[i] == STATES - 1) {
            next[i] = 0
        } else {
            next[i]++
            break
        }
        i++
    }
    return next
}
val IntArray.index : Int
    get() {
        var total = 0
        for (i in (size - 1) downTo 0) {
            total *= STATES
            total += this[i]
        }
        return total
    }

interface IRule {
    operator fun get(states : IntArray) : Int
}

fun IntArray.equalsArray(other: IntArray) = Arrays.equals(this, other)

class Rule : IRule {

    constructor(rule : IRule) {
        val start = IntArray(DIAMETER)
        var current = start.clone()

        code = IntArray(CODE_SIZE)
        try {
            do {
                code[current.index] = rule[current]
                current++
            } while (!current.equalsArray(start));
        } catch (e : Throwable) {
            println(Arrays.toString(code))
            println(Arrays.toString(current))
            throw e
        }
    }
    constructor(code : IntArray) {
        this.code = IntArray(CODE_SIZE) { if (it < code.size) code[it] else 0 }
    }

    val code : IntArray

    override fun get(states: IntArray) : Int {
        return code[states.index]
    }

    override fun toString() : String {
        val b = StringBuilder()
        for (i in 0 until CODE_SIZE) {
            if (i > 0 && i % pow(STATES.toDouble(), RADIUS.toDouble() + 1).toInt() == 0) {
                b.append('\n')
            }
            b.append(code[i])
        }
        return b.toString()
    }

    fun grade() : Double {
        var succeeded = 0
        for (i in 0 until GRADE_RUNS) {
            if (i % (GRADE_RUNS / 100) == 0) {
                println("${i/(GRADE_RUNS / 100)}% done grading.")
            }
            var tape : Tape
            do {
                tape = Tape()
            } while (tape.majority() == -1);
            val majority = tape.majority()
            val beginning = tape
            var j = 0
            while (j < GRADE_MAX_TIME && !tape.allTheSame()) {
                tape = tape.step(this)
                j++
            }
            if (tape.stabilized(this) && tape.majority() == majority) {
                succeeded++
            }/* else if (beginning.majority() != 2) {
                println(beginning.majority())
                tape = beginning
                for (j in 1..100) {
                    println(tape)
                    tape = tape.step(this)
                }
                println(tape)
            }*/
        }
        return succeeded.toDouble() / GRADE_RUNS
    }

}

fun getRandomState() : Int {
    return (random() * STATES).toInt()
}

class Tape(val tape : IntArray) {

    constructor() : this(IntArray(TAPE_LENGTH) { getRandomState() } )

    fun majority() : Int {
        val totals = IntArray(STATES)

        for (cell in tape) {
            totals[cell]++
        }

        var best = -1
        var bestScore = -1

        for (i in 0 until STATES) {
            if (totals[i] > bestScore) {
                best = i
                bestScore = totals[i]
            } else if (totals[i] == bestScore) {
                best = -1
            }
        }

        return best
    }

    fun allTheSame() : Boolean {
        for (i in 1 until TAPE_LENGTH) {
            if (this[i] != this[0]) {
                return false
            }
        }
        return true
    }

    operator fun get(index: Int) = tape[((index % TAPE_LENGTH) + TAPE_LENGTH) % TAPE_LENGTH]

    fun step(rule : IRule) : Tape {
        val nextTape = IntArray ( TAPE_LENGTH )

        for (i in 0 until TAPE_LENGTH) {
            nextTape[i] = rule[IntArray(DIAMETER) { this[i + it - RADIUS] }]
        }

        return Tape(nextTape)
    }

    fun stabilized(rule : IRule) = allTheSame() && majority() == step(rule).majority()

    override fun toString() : String {
        val b = StringBuilder()
        for (cell in tape) {
            b.append(cell)
        }
        return b.toString()
    }

}

fun main(args : Array<String>) {
    val myRule = Rule(object : IRule {
        override fun get(states: IntArray): Int {
            if (states[3] == 0) {
                if (states[2] == 1) {
                    return 2
                } else if (states[2] == 0) {
                    return 0
                } else if (states[1] == 1) {
                    return 2
                } else if (states[1] == 0) {
                    return 0
                } else {
                    return 2
                }
            } else if (states[3] == 1) {
                if (states[4] == 0) {
                    return 2
                } else if (states[4] == 1) {
                    return 1
                } else if (states[5] == 0) {
                    return 2
                } else if (states[5] == 1) {
                    return 1
                } else {
                    return 2
                }
            } else {
                if (states[2] == 0) {
                    if (states[4] != 1) {
                        return 0
                    }
                } else if (states[4] == 1) {
                    return 1
                }
                if (states[1] == 0 && states[2] != 1) {
                    if (states[5] != 1) {
                        return 0
                    }
                } else if (states[5] == 1 && states[4] != 0) {
                    return 1
                }
                return 2
            }
        }

    })
    var tape = Tape()
    println(myRule.grade())
}

Ejemplo

El numero uno
fuente