java - una - ¿Por qué este código que usa cadenas aleatorias imprime "hola mundo"?




manejo de cadenas en java (10)

Aleatorio siempre retorna la misma secuencia. Se utiliza para mezclar matrices y otras operaciones como permutaciones.

Para obtener diferentes secuencias, es necesario inicializar la secuencia en alguna posición, llamada "semilla".

El randomSting obtiene el número aleatorio en la posición i (semilla = -229985452) de la secuencia "aleatoria". Luego usa el código ASCII para los siguientes 27 caracteres en la secuencia después de la posición inicial hasta que este valor sea igual a 0. Esto devuelve el "hola". La misma operación se hace para "mundo".

Creo que el código no funcionó para ninguna otra palabra. El chico que programó que sabe muy bien la secuencia aleatoria.

¡Es un código geek muy bueno!

La siguiente declaración impresa imprimiría "hola mundo". ¿Alguien podría explicar esto?

System.out.println(randomString(-229985452) + " " + randomString(-147909649));

Y randomString() ve así:

public static String randomString(int i)
{
    Random ran = new Random(i);
    StringBuilder sb = new StringBuilder();
    while (true)
    {
        int k = ran.nextInt(27);
        if (k == 0)
            break;

        sb.append((char)('`' + k));
    }

    return sb.toString();
}

Aquí hay una pequeña mejora para la answer Denis Tulskiy. Corta el tiempo a la mitad.

public static long[] generateSeed(String goal, long start, long finish) {
    char[] input = goal.toCharArray();

    int[] dif = new int[input.length - 1];
    for (int i = 1; i < input.length; i++) {
        dif[i - 1] = input[i] - input[i - 1];
    }

    mainLoop:
    for (long seed = start; seed < finish; seed++) {
        Random random = new Random(seed);
        int lastChar = random.nextInt(27);
        int base = input[0] - lastChar;
        for (int d : dif) {
            int nextChar = random.nextInt(27);
            if (nextChar - lastChar != d) {
                continue mainLoop;
            }
            lastChar = nextChar;
        }
        if(random.nextInt(27) == 0){
            return new long[]{seed, base};
        }
    }

    throw new NoSuchElementException("Sorry :/");
}

Cuando se construye una instancia de java.util.Random con un parámetro de -229985452 específico (en este caso -229985452 o -147909649 ), sigue el algoritmo de generación de números aleatorios que comienza con ese valor de -147909649 .

Cada Random construido con la misma semilla generará el mismo patrón de números cada vez.


Derivado de la respuesta de Denis Tulskiy , este método genera la semilla.

public static long generateSeed(String goal, long start, long finish) {
    char[] input = goal.toCharArray();
    char[] pool = new char[input.length];
    label:
        for (long seed = start; seed < finish; seed++) {
            Random random = new Random(seed);

            for (int i = 0; i < input.length; i++)
                pool[i] = (char) (random.nextInt(27)+'`');

            if (random.nextInt(27) == 0) {
                for (int i = 0; i < input.length; i++) {
                    if (input[i] != pool[i])
                        continue label;
                }
                return seed;
            }

        }

    throw new NoSuchElementException("Sorry :/");
}

El principal es la clase aleatoria construida con la misma semilla que generará el mismo patrón de números cada vez.


Escribí un programa rápido para encontrar estas semillas:

import java.lang.*;
import java.util.*;
import java.io.*;

public class RandomWords {
    public static void main (String[] args) {
        Set<String> wordSet = new HashSet<String>();
        String fileName = (args.length > 0 ? args[0] : "/usr/share/dict/words");
        readWordMap(wordSet, fileName);
        System.err.println(wordSet.size() + " words read.");
        findRandomWords(wordSet);
    }

    private static void readWordMap (Set<String> wordSet, String fileName) {
        try {
            BufferedReader reader = new BufferedReader(new FileReader(fileName));
            String line;
            while ((line = reader.readLine()) != null) {
                line = line.trim().toLowerCase();
                if (isLowerAlpha(line)) wordSet.add(line);
            }
        }
        catch (IOException e) {
            System.err.println("Error reading from " + fileName + ": " + e);
        }
    }

    private static boolean isLowerAlpha (String word) {
        char[] c = word.toCharArray();
        for (int i = 0; i < c.length; i++) {
            if (c[i] < 'a' || c[i] > 'z') return false;
        }
        return true;
    }

    private static void findRandomWords (Set<String> wordSet) {
        char[] c = new char[256];
        Random r = new Random();
        for (long seed0 = 0; seed0 >= 0; seed0++) {
            for (int sign = -1; sign <= 1; sign += 2) {
                long seed = seed0 * sign;
                r.setSeed(seed);
                int i;
                for (i = 0; i < c.length; i++) {
                    int n = r.nextInt(27);
                    if (n == 0) break;
                    c[i] = (char)((int)'a' + n - 1);
                }
                String s = new String(c, 0, i);
                if (wordSet.contains(s)) {
                    System.out.println(s + ": " + seed);
                    wordSet.remove(s);
                }
            }
        }
    }
}

Lo tengo funcionando en segundo plano ahora, pero ya ha encontrado suficientes palabras para un pangram clásico:

import java.lang.*;
import java.util.*;

public class RandomWordsTest {
    public static void main (String[] args) {
        long[] a = {-73, -157512326, -112386651, 71425, -104434815,
                    -128911, -88019, -7691161, 1115727};
        for (int i = 0; i < a.length; i++) {
            Random r = new Random(a[i]);
            StringBuilder sb = new StringBuilder();
            int n;
            while ((n = r.nextInt(27)) > 0) sb.append((char)('`' + n));
            System.out.println(sb);
        }
    }
}

( Demo en ideone. )

PD. -727295876, -128911, -1611659, -235516779 .


La mayoría de los generadores de números aleatorios son, de hecho, "pseudoaleatorios". Son generadores lineales congruentes, o LCGs ( http://en.wikipedia.org/wiki/Linear_congruential_generator )

Los LCG son bastante predecibles dada una semilla fija. Básicamente, use una semilla que le dé su primera letra, luego escriba una aplicación que continúe generando el siguiente int (char) hasta que golpee la siguiente letra en su cadena de destino y anote cuántas veces tuvo que invocar la LCG. Continúa hasta que hayas generado todas y cada una de las letras.


Las otras respuestas explican por qué, pero aquí es cómo.

Dada una instancia de Random :

Random r = new Random(-229985452)

Los primeros 6 números que r.nextInt(27) genera son:

8
5
12
12
15
0

y los primeros 6 números que r.nextInt(27) genera Random r = new Random(-147909649) dado Random r = new Random(-147909649) son:

23
15
18
12
4
0

Luego simplemente agregue esos números a la representación entera del carácter ` (que es 96):

8  + 96 = 104 --> h
5  + 96 = 101 --> e
12 + 96 = 108 --> l
12 + 96 = 108 --> l
15 + 96 = 111 --> o

23 + 96 = 119 --> w
15 + 96 = 111 --> o
18 + 96 = 114 --> r
12 + 96 = 108 --> l
4  + 96 = 100 --> d

Solo lo dejaré aquí. Quien tenga mucho tiempo de (CPU) de sobra, siéntase libre de experimentar :) Además, si ha dominado algo de fork-join-fu para hacer que esta cosa queme todos los núcleos de la CPU (solo los hilos son aburridos, ¿no?), Por favor comparta tu codigo. Me sería de gran aprecio.

public static void main(String[] args) {
    long time = System.currentTimeMillis();
    generate("stack");
    generate("over");
    generate("flow");
    generate("rulez");

    System.out.println("Took " + (System.currentTimeMillis() - time) + " ms");
}

private static void generate(String goal) {
    long[] seed = generateSeed(goal, Long.MIN_VALUE, Long.MAX_VALUE);
    System.out.println(seed[0]);
    System.out.println(randomString(seed[0], (char) seed[1]));
}

public static long[] generateSeed(String goal, long start, long finish) {
    char[] input = goal.toCharArray();
    char[] pool = new char[input.length];
    label:
    for (long seed = start; seed < finish; seed++) {
        Random random = new Random(seed);

        for (int i = 0; i < input.length; i++)
            pool[i] = (char) random.nextInt(27);

        if (random.nextInt(27) == 0) {
            int base = input[0] - pool[0];
            for (int i = 1; i < input.length; i++) {
                if (input[i] - pool[i] != base)
                    continue label;
            }
            return new long[]{seed, base};
        }

    }

    throw new NoSuchElementException("Sorry :/");
}

public static String randomString(long i, char base) {
    System.out.println("Using base: '" + base + "'");
    Random ran = new Random(i);
    StringBuilder sb = new StringBuilder();
    for (int n = 0; ; n++) {
        int k = ran.nextInt(27);
        if (k == 0)
            break;

        sb.append((char) (base + k));
    }

    return sb.toString();
}

Salida:

-9223372036808280701
Using base: 'Z'
stack
-9223372036853943469
Using base: 'b'
over
-9223372036852834412
Using base: 'e'
flow
-9223372036838149518
Using base: 'd'
rulez
Took 7087 ms

Todos los presentes hicieron un excelente trabajo explicando cómo funciona el código y mostrando cómo puede construir sus propios ejemplos, pero aquí hay una respuesta teórica de información que muestra por qué podemos esperar razonablemente que exista una solución que la búsqueda de fuerza bruta finalmente encuentre.

Las 26 letras minúsculas diferentes forman nuestro alfabeto Σ . Para permitir la generación de palabras de diferentes longitudes, agregamos un símbolo terminador para obtener un alfabeto extendido Σ' := Σ ∪ {⊥} .

Sea α un símbolo y X una variable aleatoria distribuida uniformemente sobre Σ' . La probabilidad de obtener ese símbolo, P(X = α) , y su contenido de información, I(α) , vienen dados por:

P (X = α) = 1 / | Σ '| = 1/27

I (α) = -log₂ [P (X = α)] = -log₂ (1/27) = log₂ (27)

Para una palabra ω ∈ Σ* y su contraparte terminada en ω' := ω · ⊥ ∈ (Σ')* , tenemos

I (ω): = I (ω ') = | ω' | * log₂ (27) = (| ω | + 1) * log₂ (27)

Dado que el generador de números pseudoaleatorios (PRNG) se inicializa con una semilla de 32 bits, podemos esperar que la mayoría de las palabras tengan una longitud de hasta

λ = piso [32 / log₂ (27)] - 1 = 5

Para ser generado por al menos una semilla. Incluso si tuviéramos que buscar una palabra de 6 caracteres, tendríamos éxito aproximadamente el 41.06% del tiempo. No está nada mal.

Para 7 cartas estamos mirando cerca de 1.52%, pero no me había dado cuenta antes de intentarlo:

#include <iostream>
#include <random>

int main()
{
    std::mt19937 rng(631647094);
    std::uniform_int_distribution<char> dist('a', 'z' + 1);

    char alpha;
    while ((alpha = dist(rng)) != 'z' + 1)
    {
        std::cout << alpha;
    }
}

Ver la salida: http://ideone.com/JRGb3l





random