Perché questo codice che utilizza stringhe casuali stampa “ciao mondo”?

La seguente dichiarazione di stampa dovrebbe stampare “Ciao mondo”. Qualcuno potrebbe spiegarlo?

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

E randomString() assomiglia a questo:

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

Quando un’istanza di java.util.Random viene costruita con un parametro seme specifico (in questo caso -229985452 o -147909649 ), segue l’algoritmo di generazione del numero casuale che inizia con quel valore seme.

Ogni Random costruito con lo stesso seme genererà lo stesso modello di numeri ogni volta.

Le altre risposte spiegano perché, ma ecco come.

Data un’istanza di Random :

 Random r = new Random(-229985452) 

I primi 6 numeri r.nextInt(27) da r.nextInt(27) sono:

 8 5 12 12 15 0 

e i primi 6 numeri che r.nextInt(27) genera in Random r = new Random(-147909649) sono:

 23 15 18 12 4 0 

Quindi aggiungi questi numeri alla rappresentazione intera del carattere ` (che è 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 

Lo lascerò qui. Chiunque abbia un sacco di tempo (CPU) per risparmiare, sentiti libero di sperimentare 🙂 Inoltre, se hai padroneggiato alcuni fork-join-fu per far sì che questa cosa masterizzi tutti i core della CPU (solo i thread sono noiosi, giusto?), Per favore condividi il tuo codice. Lo apprezzerei molto

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

Produzione:

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

Tutti qui hanno fatto un ottimo lavoro nel spiegare come funziona il codice e mostrare come è ansible build i propri esempi, ma ecco una risposta teorica che mostra perché possiamo ragionevolmente aspettarci che esista una soluzione che alla fine la ricerca forza bruta troverà.

Le 26 diverse lettere minuscole formano il nostro alfabeto Σ . Per consentire la generazione di parole di diversa lunghezza, aggiungiamo ulteriormente un simbolo di terminazione per ottenere un alfabeto esteso Σ' := Σ ∪ {⊥} .

Sia α un simbolo e X una variabile casuale uniformsmente distribuita su Σ' . La probabilità di ottenere quel simbolo, P(X = α) e il suo contenuto informativo, I(α) , sono dati da:

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

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

Per una parola ω ∈ Σ* e la sua controparte terminata ω' := ω · ⊥ ∈ (Σ')* , abbiamo

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

Poiché il Pseudorandom Number Generator (PRNG) è inizializzato con un seme a 32 bit, possiamo aspettarci più parole di lunghezza fino a

λ = floor [32 / log₂ (27)] – 1 = 5

essere generato da almeno un seme. Anche se dovessimo cercare una parola di 6 caratteri, avremmo comunque successo circa il 41,06% delle volte. Non troppo malandato.

Per 7 lettere ci stiamo avvicinando all’1,52%, ma non me ne ero reso conto prima di provare:

 #include  #include  int main() { std::mt19937 rng(631647094); std::uniform_int_distribution dist('a', 'z' + 1); char alpha; while ((alpha = dist(rng)) != 'z' + 1) { std::cout << alpha; } } 

Vedi l'output: http://ideone.com/JRGb3l

Ho scritto un programma rapido per trovare questi semi:

 import java.lang.*; import java.util.*; import java.io.*; public class RandomWords { public static void main (String[] args) { Set wordSet = new HashSet(); 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 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 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); } } } } } 

Ce l'ho ora in esecuzione in background, ma ha già trovato abbastanza parole per un pangram classico:

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

( Demo su ideone. )

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

Sono stato incuriosito da questo, ho eseguito questo generatore di parole casuali su una lista di parole del dizionario. Intervallo: Intero.MIN_VALORE a Integer.MAX_VALUE

Ho ottenuto 15131 colpi.

 int[] arrInt = {-2146926310, -1885533740, -274140519, -2145247212, -1845077092, -2143584283, -2147483454, -2138225126, -2147375969}; for(int seed : arrInt){ System.out.print(randomString(seed) + " "); } 

stampe

 the quick browny fox jumps over a lazy dog 

La maggior parte dei generatori di numeri casuali sono, in effetti, “pseudo casuali”. Sono generatori lineari congruenti o LCG ( http://en.wikipedia.org/wiki/Linear_congruential_generator )

Gli LCG sono abbastanza prevedibili dato un seme fisso. In pratica, usa un seme che ti dà la tua prima lettera, quindi scrivi un’app che continua a generare il prossimo int (char) finché non colpisci la lettera successiva nella stringa di destinazione e scrivi quante volte hai dovuto richiamare il LCG. Continua finché non hai generato ogni singola lettera.

Casuale restituisce sempre la stessa sequenza. È usato per mischiare matrici e altre operazioni come permutazioni.

Per ottenere sequenze diverse, è necessario inizializzare la sequenza in una posizione, chiamata “seme”.

Il randomSting ottiene il numero casuale nella posizione i (seed = -229985452) della sequenza “random”. Quindi usa il codice ASCII per il prossimo 27 carattere nella sequenza dopo la posizione di seme fino a quando questo valore è uguale a 0. Questo restituisce “Ciao”. La stessa operazione viene eseguita per “mondo”.

Penso che il codice non ha funzionato per altre parole. Il ragazzo che ha programmato che conosce molto bene la sequenza casuale.

È un ottimo codice per il geek!

Poiché la multi-threading è molto semplice con Java, ecco una variante che cerca una seed utilizzando tutti i core disponibili: 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 { 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 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(); } } } 

Derivato dalla risposta di Denis Tulskiy , questo metodo genera il seme.

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

Il principale è la class casuale costruita con lo stesso seme che genererà lo stesso modello di numeri ogni volta.

Dai documenti Java, questa è una caratteristica intenzionale quando si specifica un valore seme per la class Random.

Se due istanze di Random vengono create con lo stesso seme e viene creata la stessa sequenza di chiamate di metodo per ognuna, genereranno e restituiranno sequenze identiche di numeri. Per garantire questa proprietà, sono specificati algoritmi particolari per la class Random. Le implementazioni Java devono utilizzare tutti gli algoritmi mostrati qui per la class Random, a fini di assoluta portabilità del codice Java.

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

Tuttavia, si potrebbe pensare che ci siano impliciti problemi di sicurezza nell’avere numeri “casuali” prevedibili.

Si tratta di “seme”. Gli stessi semi danno lo stesso risultato.

Ecco un piccolo miglioramento per la risposta di Denis Tulskiy. Dimezza il tempo

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