Mengapa kode ini menggunakan string acak mencetak "hello world"?

Pernyataan cetak berikut akan mencetak "hello world". Adakah yang bisa menjelaskan ini?

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

Dan randomString()terlihat seperti ini:

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

Ketika sebuah instance java.util.Randomdibangun dengan parameter seed tertentu (dalam kasus ini -229985452atau -147909649), ia mengikuti algoritma pembuatan bilangan acak yang dimulai dengan nilai seed tersebut.

Setiap Randomdibangun dengan benih yang sama akan menghasilkan pola angka yang sama setiap kali.

Jawaban lain menjelaskan mengapa, tapi begini caranya.

Diberikan contoh Random:

Random r = new Random(-229985452)

6 angka pertama yang r.nextInt(27)menghasilkan adalah:

8
5
12
12
15
0

dan 6 angka pertama yang r.nextInt(27)menghasilkan diberikan Random r = new Random(-147909649)adalah:

23
15
18
12
4
0

Kemudian tambahkan saja angka-angka itu ke representasi integer karakter `(yaitu 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

Saya hanya akan meninggalkannya di sini. Siapa pun yang memiliki banyak waktu (CPU), jangan ragu untuk bereksperimen :) Juga, jika Anda telah menguasai beberapa fork-join-fu untuk membuat benda ini membakar semua core CPU (hanya utas yang membosankan, kan?), Silakan bagikan kode Anda. Saya akan sangat menghargainya.

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

Keluaran:

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

Semua orang di sini melakukan pekerjaan yang luar biasa untuk menjelaskan cara kerja kode dan menunjukkan bagaimana Anda dapat membangun contoh Anda sendiri, tetapi inilah jawaban teoretis informasi yang menunjukkan mengapa kita dapat mengharapkan solusi yang ada sehingga pencarian brute force pada akhirnya akan ditemukan.

26 huruf kecil yang berbeda membentuk alfabet kami Σ. Untuk memungkinkan menghasilkan kata dengan panjang yang berbeda, kami selanjutnya menambahkan simbol terminator ⊥untuk menghasilkan alfabet yang diperluasΣ' := Σ ∪ {⊥} .

Membiarkan αmenjadi simbol dan X variabel acak terdistribusi secara seragam berakhir Σ'. Peluang untuk memperoleh simbol itu P(X = α), dan konten informasinya I(α), diberikan oleh:

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

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

Untuk satu kata ω ∈ Σ*dan ⊥-mitra yang diberhentikan ω' := ω · ⊥ ∈ (Σ')*, kami punya

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

Karena Pseudorandom Number Generator (PRNG) diinisialisasi dengan seed 32-bit, kita dapat mengharapkan sebagian besar kata panjang hingga

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

untuk dihasilkan oleh setidaknya satu biji. Bahkan jika kita mencari kata 6-karakter, kita masih akan berhasil sekitar 41,06% dari waktu. Tidak terlalu buruk.

Untuk 7 huruf kami melihat mendekati 1,52%, tetapi saya tidak menyadarinya sebelum mencobanya:

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

Lihat hasilnya: http://ideone.com/JRGb3l

Saya menulis program cepat untuk menemukan benih ini:

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

Saya menjalankannya di latar belakang sekarang, tetapi sudah menemukan cukup kata untuk pangram klasik:

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 di ideone. )

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

Saya tertarik dengan ini, saya menjalankan generator kata acak ini pada daftar kata kamus. Rentang: Integer.MIN_VALUE ke Integer.MAX_VALUE

Saya mendapat 15.131 hit.

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

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

Cetakan

the quick browny fox jumps over a lazy dog 

Faktanya, kebanyakan generator angka acak adalah "pseudo random." Mereka adalah Linear Congruential Generator, atau LCGs ( http://en.wikipedia.org/wiki/Linear_congruential_generator )

LCG cukup dapat diprediksi karena memiliki benih yang tetap. Pada dasarnya, gunakan seed yang memberi Anda surat pertama Anda, kemudian tulis aplikasi yang terus menghasilkan int (char) berikutnya hingga Anda menekan huruf berikutnya dalam string target Anda dan tulis berapa kali Anda harus menggunakan LCG. Lanjutkan sampai Anda membuat setiap huruf.

Karena multi-threading sangat mudah dengan Java, berikut adalah varian yang mencari seed menggunakan semua core yang tersedia: 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();
    }
  }
}

Acak selalu mengembalikan urutan yang sama. Ini digunakan untuk mengocok array dan operasi lainnya sebagai permutasi.

Untuk mendapatkan urutan yang berbeda, perlu menginisialisasi urutan di beberapa posisi, yang disebut "seed".

RandomSting mendapatkan nomor acak di posisi i (seed = -229985452) dari urutan "acak". Kemudian gunakan kode ASCII untuk 27 karakter berikutnya dalam urutan setelah posisi seed sampai nilai ini sama dengan 0. Ini mengembalikan "halo". Operasi yang sama dilakukan untuk "dunia".

Saya pikir kode itu tidak berfungsi untuk kata lain. Orang yang diprogram yang mengetahui urutan acak dengan sangat baik.

Ini kode geek yang sangat hebat!

Prinsipnya adalah Kelas Acak dibangun dengan benih yang sama akan menghasilkan pola angka yang sama setiap kali.

Berasal dari jawaban Denis Tulskiy , metode ini menghasilkan benih.

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

Dari dokumen Java, ini adalah fitur yang disengaja ketika menentukan nilai seed untuk kelas Random.

Jika dua instance Random dibuat dengan seed yang sama, dan urutan pemanggilan metode yang sama dibuat untuk masing-masing, mereka akan menghasilkan dan mengembalikan urutan angka yang identik. Untuk menjamin properti ini, algoritma tertentu ditentukan untuk kelas Acak. Implementasi Java harus menggunakan semua algoritma yang ditunjukkan di sini untuk kelas Acak, demi portabilitas absolut kode Java.

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

Anehnya, Anda akan berpikir ada masalah keamanan implisit dalam memiliki nomor 'acak' yang dapat diprediksi.

Ini tentang "benih". Biji yang sama memberikan hasil yang sama.

Berikut ini adalah perbaikan kecil untuk jawaban Denis Tulskiy . Itu memotong waktu setengah

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

Ini semua tentang seed input . Benih yang sama memberikan hasil yang sama setiap saat. Bahkan Anda menjalankan kembali program Anda lagi dan lagi itu adalah output yang sama.

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

}

Keluaran

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