Pourquoi ce code utilise-t-il des chaînes aléatoires pour imprimer "hello world"?

les autres réponses expliquent pourquoi, Mais voici comment.

étant donné une instance de Random :

Random r = new Random(-229985452)

les 6 premiers nombres que r.nextInt(27) génère sont:

8
5
12
12
15
0

et les 6 premiers nombres que r.nextInt(27) produit donné Random r = new Random(-147909649) sont:

23
15
18
12
4
0

puis il suffit d'ajouter ces nombres à la représentation entière du caractère ` (qui est de 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 le laisse ici. Qui a beaucoup de temps (CPU) à perdre, n'hésitez pas à expérimenter:) aussi, si vous avez maîtrisé un peu de fork-join-fu pour faire brûler cette chose tous les cœurs CPU (juste les fils sont ennuyeux, non?), s'il vous plaît partagez vos 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

tout le monde ici a fait un excellent travail d'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 pour exister que la recherche de force brute finira par trouver.

les 26 lettres minuscules différentes forment notre alphabet Σ . Pour permettre de générer des mots de différentes longueurs, nous ajoutons un symbole de terminateur ⊥ pour obtenir un alphabet Σ' := Σ ∪ {⊥} .

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

P (x = α) = 1 / / Σ' / = 1/27

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

pour un mot ω ∈ Σ* et ses ⊥- contrepartie terminée ω' := ω · ⊥ ∈ (Σ')* , nous avons

I (ω): = I (ω') = / ω' / * log փ (27) = (|ω / + 1) * Log փ (27)

puisque le Générateur de nombres de Pseudorandom (PRNG) est initialisé avec une graine de 32 bits, nous pouvons nous attendre à la plupart des mots de longueur jusqu'à

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

générés par au moins une graine. Même si nous si nous cherchions un mot de 6 caractères, nous aurions quand même du succès environ 41,06% du temps. Pas trop mal.

pour 7 lettres nous regardons plus près de 1,52%, mais je ne l'avais pas réalisé 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

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 en cours d'exécution dans l'arrière-plan maintenant, mais il a déjà trouvé assez 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 .

j'ai été intrigué par ceci, j'ai couru ce générateur de mot aléatoire sur une liste de mot de dictionnaire. Gamme: Integer.MIN_VALUE à Entier.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) + " ");
}

Imprime

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."Ils sont des générateurs de congruence linéaire, ou LCG ( ) http://en.wikipedia.org/wiki/Linear_congruential_generator )

LCGs sont tout à fait prévisibles donné un fixe de semences. Fondamentalement, utilisez une graine qui vous donne votre première lettre, puis écrivez une application qui continue à générer le prochain int (char) jusqu'à ce que vous frappez la prochaine lettre dans votre chaîne de cible et écrivez combien de fois vous avez dû invoquez le LCG. Continuez jusqu'à ce que vous ayez généré chaque lettre.

renvoie toujours la même séquence. Il est utilisé pour mélanger des tableaux et d'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".

le randomSting obtient le nombre aléatoire dans la position i (seed = -229985452) de la séquence" aléatoire". Puis utilise le code ASCII pour les 27 caractères suivants dans la séquence après la position de la graine jusqu'à ce que cette valeur est égale à 0. Ce retour le "bonjour". La même opération est effectuée pour "le monde".

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

c'est un très grand code geek!

comme le multi-threading est très facile avec Java, voici une variante qui recherche une graine en utilisant tous les noyaux 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();
    }
  }
}

dérivé de Denis Tulskiy 's Réponse, 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 :/");
}

le principal est la classe aléatoire construite avec la même graine générera le même modèle de nombres à chaque fois.

de Java docs, il s'agit d'une caractéristique intentionnelle lorsque l'on spécifie une valeur de graine pour la classe aléatoire.

si deux instances de hasard sont créées avec la même graine, et le même séquence d'appels de méthode est faite pour chacun, ils vont générer et retournez des séquences identiques de nombres. Afin de garantir cette propriété, des algorithmes particuliers sont spécifiés pour la classe Random. Implémentations Java doit utiliser tous les algorithmes présentés ici pour l' classe Aléatoire, pour l'amour de l'absolu de la portabilité du code Java.

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

étrange cependant, on pourrait penser qu'il y a des problèmes de sécurité implicites dans le fait d'avoir des nombres "aléatoires" prévisibles.

il s'agit de"seed". Même les graines donnent le même résultat.

Voici une amélioration mineure pour Denis Tulskiy réponse . Il coupe 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 :/");
}