Pourquoi ce code utilisant des chaînes aléatoires affiche-t-il «bonjour le monde»?

La déclaration d'impression suivante imprimerait "bonjour le monde". Quelqu'un pourrait-il expliquer cela?

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

Et randomString()ressemble à ceci:

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

Lorsqu'une instance de java.util.Randomest construite avec un paramètre de départ spécifique (dans ce cas -229985452ou -147909649), elle suit l'algorithme de génération de nombres aléatoires commençant par cette valeur de départ.

Chaque Randomconstruit avec la même graine générera à chaque fois le même schéma de nombres.

Les autres réponses expliquent pourquoi, mais voici comment.

Étant donné une instance de Random:

Random r = new Random(-229985452)

Les 6 premiers nombres r.nextInt(27)générés sont:

8
5
12
12
15
0

et les 6 premiers nombres qui r.nextInt(27)génèrent donnés Random r = new Random(-147909649)sont:

23
15
18
12
4
0

Ajoutez ensuite ces nombres à la représentation entière du caractère `(qui est 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

Je vais juste le laisser ici. Quiconque a beaucoup de temps (CPU) à perdre, n'hésitez pas à expérimenter :) De plus, si vous avez maîtrisé un fork-join-fu pour que cette chose brûle tous les cœurs du processeur (seuls les threads sont ennuyeux, non?), Veuillez partager votre code. Je l'apprécierais grandement.

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

Production:

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

Tout le monde ici a fait un excellent travail pour expliquer comment le code fonctionne et montrer comment vous pouvez construire vos propres exemples, mais voici une réponse théorique d'information montrant pourquoi nous pouvons raisonnablement nous attendre à une solution que la recherche par force brute trouvera finalement.

Les 26 lettres minuscules différentes forment notre alphabet Σ. Pour permettre de générer des mots de différentes longueurs, nous ajoutons en outre un symbole de terminaison ⊥pour produire un alphabet étendu Σ' := Σ ∪ {⊥}.

Soit αun symbole et X une variable aléatoire uniformément répartie Σ'. La probabilité d'obtenir ce symbole P(X = α)et son contenu d'information I(α)sont données par:

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

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

Pour un mot ω ∈ Σ*et son ⊥-homologue terminé ω' := ω · ⊥ ∈ (Σ')*, nous avons

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

Étant donné que le générateur de nombres pseudo-aléatoires (PRNG) est initialisé avec une graine 32 bits, nous pouvons nous attendre à la plupart des mots de longueur allant jusqu'à

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

à générer par au moins une graine. Même si nous devions rechercher un mot à 6 caractères, nous réussirions quand même environ 41,06% du temps. Pas trop mal.

Pour 7 lettres, nous nous rapprochons de 1,52%, mais je ne l'avais pas réalisé avant de l'essayer:

#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;
    }
}

Voir la sortie: http://ideone.com/JRGb3l

J'ai écrit un programme rapide pour trouver ces graines:

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

Je l'ai maintenant en arrière-plan, mais il a déjà trouvé suffisamment de mots pour un pangram classique:

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

( Démo sur ideone. )

Ps. -727295876, -128911, -1611659, -235516779.

Cela m'a intrigué, j'ai exécuté ce générateur de mots aléatoires sur une liste de mots du dictionnaire. Plage: Integer.MIN_VALUE à Integer.MAX_VALUE

J'ai eu 15131 hits.

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

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

Impressions

the quick browny fox jumps over a lazy dog 

La plupart des générateurs de nombres aléatoires sont, en fait, «pseudo aléatoires». Ce sont des générateurs congruentiels linéaires, ou LCG ( http://en.wikipedia.org/wiki/Linear_congruential_generator )

Les LCG sont assez prévisibles étant donné une semence fixe. Fondamentalement, utilisez une graine qui vous donne votre première lettre, puis écrivez une application qui continue de générer le prochain int (char) jusqu'à ce que vous frappiez la lettre suivante dans votre chaîne cible et notez combien de fois vous avez dû appeler le LCG. Continuez jusqu'à ce que vous ayez généré chaque lettre.

Le multi-threading étant très simple avec Java, voici une variante qui recherche une graine en utilisant tous les cœurs 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();
    }
  }
}

Random renvoie toujours la même séquence. Il est utilisé pour mélanger les tableaux et autres opérations comme permutations.

Pour obtenir différentes séquences, il est nécessaire d'initialiser la séquence dans une certaine position, appelée "graine".

RandomSting obtient le nombre aléatoire dans la position i (seed = -229985452) de la séquence "random". Utilise ensuite le code ASCII pour les 27 caractères suivants dans la séquence après la position de départ jusqu'à ce que cette valeur soit égale à 0. Cela renvoie le "bonjour". La même opération est effectuée pour "monde".

Je pense que le code n'a pas fonctionné pour d'autres mots. Le gars qui a programmé qui connaît très bien la séquence aléatoire.

C'est un très bon code geek!

Le principe est que la classe aléatoire construite avec la même graine va générer le même modèle de nombres à chaque fois.

Dérivée de la réponse de Denis Tulskiy , cette méthode génère la graine.

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 :/");
}

Dans les documents Java, il s'agit d'une fonctionnalité intentionnelle lors de la spécification d'une valeur de départ pour la classe Random.

Si deux instances de Random sont créées avec la même graine et que la même séquence d'appels de méthode est effectuée pour chacune, elles généreront et renverront des séquences de nombres identiques. Afin de garantir cette propriété, des algorithmes particuliers sont spécifiés pour la classe Random. Les implémentations Java doivent utiliser tous les algorithmes présentés ici pour la classe Random, dans un souci de portabilité absolue du code Java.

http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Random.html

Curieusement cependant, on pourrait penser qu'il y a des problèmes de sécurité implicites à avoir des nombres «aléatoires» prévisibles.

Il s'agit de "semence". Les mêmes graines donnent le même résultat.

Voici une amélioration mineure pour la réponse de Denis Tulskiy . Cela réduit le temps de moitié

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 :/");
}

Il s'agit de la graine d' entrée . La même graine donne les mêmes résultats tout le temps. Même si vous réexécutez votre programme encore et encore, c'est la même sortie.

public static void main(String[] args) {

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

}

private static void randomString(int i) {
    Random ran = new Random(i);
    System.out.println(ran.nextInt());
    System.out.println(ran.nextInt());
    System.out.println(ran.nextInt());
    System.out.println(ran.nextInt());
    System.out.println(ran.nextInt());

}

Production

-755142161
-1073255141
-369383326
1592674620
-1524828502
------------
-755142161
-1073255141
-369383326
1592674620
-1524828502