Pregunta ¿Por qué este código que utiliza cadenas aleatorias imprime "hello world"?


La siguiente declaración de impresión imprimiría "hello world". ¿Alguien podría explicar esto?

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

Y randomString() Se ve como esto:

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();
}

1588
2018-03-03 04:38


origen


Respuestas:


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

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


844
2018-03-03 04:40



Las otras respuestas explican por qué, pero aquí está 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 dado Random r = new Random(-147909649) son:

23
15
18
12
4
0

Luego solo agrega esos números a la representación entera del personaje ` (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

1084
2018-03-03 04:55



Lo dejaré aquí. Quien tenga mucho tiempo (de CPU), siéntase libre de experimentar :) Además, si ha dominado fork-join-fu para hacer que esto 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

262
2018-03-03 15:03



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

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

Dejar α ser 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(α), están dados por:

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

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

Por una palabra ω ∈ Σ* y es ⊥-contraparte terminada ω' := ω · ⊥ ∈ (Σ')*, tenemos

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

Dado que el generador de números Pseudoaleatorio (PRNG) se inicializa con una semilla de 32 bits, podemos esperar que la mayoría de las palabras de longitud 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, aún seríamos exitosos el 41.06% del tiempo. No está nada mal.

Para 7 letras estamos mirando más cerca al 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 el resultado: http://ideone.com/JRGb3l


248
2018-03-04 09:49



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 se encontraron suficientes palabras para un pangrama 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);
        }
    }
}

(Demostración en ideone.)

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


65
2018-03-03 18:33



Estaba intrigado por esto, ejecuté este generador de palabras al azar en una lista de palabras del diccionario. Rango: Integer.MIN_VALUE a Integer.MAX_VALUE

Recibí 15131 visitas.

int[] arrInt = {-2146926310, -1885533740, -274140519, 
                -2145247212, -1845077092, -2143584283,
                -2147483454, -2138225126, -2147375969};

for(int seed : arrInt){
    System.out.print(randomString(seed) + " ");
}

Huellas dactilares

the quick browny fox jumps over a lazy dog 

31
2018-04-13 22:47



La mayoría de los generadores de números aleatorios son, de hecho, "pseudoaleatorios". Son generadores congruenciales lineales o LCG (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 carta, luego escriba una aplicación que continúe generando la próxima int (char) hasta que toque la siguiente letra en su cadena objetivo y anote cuántas veces tuvo que invocar el LCG. Continúa hasta que hayas generado todas y cada una de las letras.


26
2018-03-04 10:59



Aleatorio siempre devuelve la misma secuencia. Se usa 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 ASCII código para los siguientes 27 caracteres en la secuencia después de la posición de la semilla hasta que este valor sea igual a 0. Esto devuelve el "saludo". La misma operación se realiza para "mundo".

Creo que el código no funcionó para otras palabras. El tipo que programó sabe muy bien la secuencia aleatoria.

¡Es un gran código geek!


22
2018-03-03 04:54



Como multi-threading es muy fácil con Java, aquí hay una variante que busca una semilla usando todos los núcleos disponibles: http://ideone.com/ROhmTA

import java.util.ArrayList;
import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadFactory;

public class SeedFinder {

  static class SearchTask implements Callable<Long> {

    private final char[] goal;
    private final long start, step;

    public SearchTask(final String goal, final long offset, final long step) {
      final char[] goalAsArray = goal.toCharArray();
      this.goal = new char[goalAsArray.length + 1];
      System.arraycopy(goalAsArray, 0, this.goal, 0, goalAsArray.length);
      this.start = Long.MIN_VALUE + offset;
      this.step = step;
    }

    @Override
    public Long call() throws Exception {
      final long LIMIT = Long.MAX_VALUE - this.step;
      final Random random = new Random();
      int position, rnd;
      long seed = this.start;

      while ((Thread.interrupted() == false) && (seed < LIMIT)) {
        random.setSeed(seed);
        position = 0;
        rnd = random.nextInt(27);
        while (((rnd == 0) && (this.goal[position] == 0))
                || ((char) ('`' + rnd) == this.goal[position])) {
          ++position;
          if (position == this.goal.length) {
            return seed;
          }
          rnd = random.nextInt(27);
        }
        seed += this.step;
      }

      throw new Exception("No match found");
    }
  }

  public static void main(String[] args) {
    final String GOAL = "hello".toLowerCase();
    final int NUM_CORES = Runtime.getRuntime().availableProcessors();

    final ArrayList<SearchTask> tasks = new ArrayList<>(NUM_CORES);
    for (int i = 0; i < NUM_CORES; ++i) {
      tasks.add(new SearchTask(GOAL, i, NUM_CORES));
    }

    final ExecutorService executor = Executors.newFixedThreadPool(NUM_CORES, new ThreadFactory() {

      @Override
      public Thread newThread(Runnable r) {
        final Thread result = new Thread(r);
        result.setPriority(Thread.MIN_PRIORITY); // make sure we do not block more important tasks
        result.setDaemon(false);
        return result;
      }
    });
    try {
      final Long result = executor.invokeAny(tasks);
      System.out.println("Seed for \"" + GOAL + "\" found: " + result);
    } catch (Exception ex) {
      System.err.println("Calculation failed: " + ex);
    } finally {
      executor.shutdownNow();
    }
  }
}

22
2017-10-04 23:13



Derivado de Denis TulskiyLa respuesta de este método es que 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 :/");
}

13
2018-03-07 13:26



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


13
2018-06-13 20:36