Pourquoi ce code à l'aide des chaînes aléatoires print "hello world"?

Question

Je suis tombé sur ce morceau de code, et trouvé ça plutôt intéressant. L'impression suivante instruction print "hello world". Quelqu'un pourrait-il m'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();
    for (int n = 0; ; n++)
    {
        int k = ran.nextInt(27);
        if (k == 0)
            break;

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

    return sb.toString();
}

Answer 1

Les autres réponses expliquer pourquoi, mais voici comment:

new Random(-229985452).nextInt(27)

Les 6 premiers numéros de la ci-dessus aléatoire génère sont:

8
5
12
12
15
0

et les 6 premiers numéros new Random(-147909649).nextInt(27) génère:

23
15
18
12
4
0

Puis il suffit d'ajouter ces numéros à l'entier de la représentation du caractère ` (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

Answer 2

Lorsqu'une instance de java.util.Random est construit avec un paramètre graine (dans ce cas - -229985452 ou -147909649), on suit la génération de nombre aléatoire de l'algorithme commence avec cette valeur de départ.

Chaque Random construit avec la même graine va générer le même modèle de numéros à chaque fois.

Answer 3

Je vais juste le laisser ici. Celui qui a beaucoup d' (CPU) de temps à perdre, n'hésitez pas à expérimenter :) Aussi, si vous avez maîtrisé fork-join-fu pour faire de cette chose brûler tous les cœurs du PROCESSEUR (juste les threads sont ennuyeux, non?), merci de partager votre code. Je vous en serais très reconnaissante.

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

Sortie:

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

Answer 4

Tout le monde ici a fait un bon travail en expliquant comment fonctionne le code et en montrant comment vous pouvez construire vos propres exemples, mais voici une information de réponse théorique en montrant pourquoi on peut raisonnablement s'attendre à une solution pour que la force brute de recherche finiront par trouver.

Les 26 lettres minuscules de notre alphabet Σ. Pour permettre de générer des mots de différentes longueurs, nous avons encore ajouter un terminator symbole ⊥ de rendement de l'étendue de l'alphabet Σ' := Σ ∪ {⊥}.

Laissez - α être un symbole et X une variable aléatoire uniformément distribué sur Σ'. La probabilité d'obtention de ce symbole, P(X = α), et son contenu de l'information, I(α), sont donnés par:

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

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

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

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

Depuis le Générateur de nombres Pseudo-aléatoires (PRNG) est initialisé avec un 32 bits de la graine, on peut s'attendre à la plupart des mots de longueur jusqu'à

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

pour être généré par au moins une graine. Même si nous étions à la recherche pour une de 6 caractères, de mots, nous en serions encore à succès sur 41.06% du temps. Pas trop mal.

Pour 7 lettres nous regardons de plus près à 1,52%, mais je n'avais pas réalisé qu'avant de lui donner un essai:

#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

Answer 5

J'ai écrit un programme rapide de 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);
                }
            }
        }
    }
}

J'ai en cours d'exécution en arrière-plan, mais il est déjà trouvé assez de mots pour un classique pangram:

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.