Question Pourquoi ce code utilisant des chaînes aléatoires imprime-t-il "hello world"?


L'instruction d'impression suivante afficherait "Bonjour tout le monde". Quelqu'un pourrait-il expliquer cela?

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

Et randomString() ressemble à ça:

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


origine


Réponses:


Quand une instance de java.util.Random est construit avec un paramètre de graine spécifique (dans ce cas -229985452 ou -147909649), il suit l'algorithme de génération de nombres aléatoires début avec cette valeur de graine.

Chaque Random construit avec la même graine générera le même modèle de nombres à chaque fois.


844
2018-03-03 04:40



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

Étant donné une instance de Random:

Random r = new Random(-229985452)

Les 6 premiers chiffres r.nextInt(27) génère sont:

8
5
12
12
15
0

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

23
15
18
12
4
0

Ensuite, ajoutez simplement ces nombres à la représentation entière du personnage ` (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

1084
2018-03-03 04:55



Je vais juste laisser ça ici. Celui qui a beaucoup de temps (CPU), n'hésitez pas à expérimenter :) Aussi, si vous avez maîtrisé fork-join-fu pour que cette chose brûle tous les cœurs de CPU (les threads sont ennuyeux, non?), Merci de 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();
}

Sortie:

-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



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 montrant pourquoi nous pouvons raisonnablement espérer qu'une solution existera finalement.

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

Laisser α être un symbole et X une variable aléatoire uniformément distribuée 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₂ [P (X = α)] = -log₂ (1/27) = log₂ (27)

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

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

Puisque le générateur de nombres pseudo-aléatoires (PRNG) est initialisé avec une graine de 32 bits, on peut s'attendre à ce que la plupart des mots de longueur

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

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

Pour 7 lettres, nous regardons plus près 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


248
2018-03-04 09:49



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 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.


65
2018-03-03 18:33



J'ai été intrigué par cela, j'ai couru ce générateur de mots au hasard 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 

31
2018-04-13 22:47



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

Les LCG sont tout à fait prévisibles compte tenu d'une graine fixe. 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 lettre suivante dans votre chaîne cible et écrivez combien de fois vous avez dû appeler le LCG. Continuez jusqu'à ce que vous ayez généré chaque lettre.


26
2018-03-04 10:59



Aléatoire retourne toujours la même séquence. Il est utilisé pour mélanger les 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 "random". Puis utilise le ASCII code pour le prochain 27 caractères dans la séquence après la position de départ jusqu'à ce que cette valeur soit égale à 0. Cela retourne le "bonjour". La même opération est faite pour "monde".

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

C'est un très bon code geek!


22
2018-03-03 04:54



Comme le multi-threading est très facile 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();
    }
  }
}

22
2017-10-04 23:13