Вопрос: Почему этот код использует случайные строки для печати «hello world»?


Следующий оператор печати напечатает «hello world». Может ли кто-нибудь объяснить это?

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

А также randomString()выглядит так:

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

1580


источник


Ответы:


Когда экземпляр java.util.Randomстроится с определенным параметром затравки (в этом случае -229985452или -147909649), он следует алгоритму генерации случайных чисел начало с этим значением семени.

каждый Randomпостроенный с одним и тем же семенем, будет генерировать одинаковый шаблон чисел каждый раз.


839



Другие ответы объясняют, почему, но вот как.

Учитывая пример Random:

Random r = new Random(-229985452)

Первые 6 чисел, которые r.nextInt(27)генерирует:

8
5
12
12
15
0

и первые 6 чисел, которые r.nextInt(27)генерирует данные Random r = new Random(-147909649)находятся:

23
15
18
12
4
0

Затем просто добавьте эти числа в целочисленное представление символа `(что составляет 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

1078



Я просто оставлю это здесь. Тот, у кого есть много (CPU) времени, чтобы избавиться, не стесняйтесь экспериментировать :) Кроме того, если вы освоили некоторый fork-join-fu, чтобы заставить эту вещь записывать все ядра процессора (просто потоки скучны, правильно?), Пожалуйста, поделитесь ваш код. Буду весьма признателен за это.

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

Вывод:

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

260



Все здесь проделали большую работу по разъяснению того, как работает код, и показывая, как вы можете создавать свои собственные примеры, но вот теоретический ответ информации, показывающий, почему мы можем разумно ожидать, что существует решение, которое в конечном итоге найдет поиск грубой силы.

26 разных строчных букв образуют наш алфавит Σ, Чтобы разрешить генерировать слова различной длины, мы также добавляем символ терминатора для получения расширенного алфавита Σ' := Σ ∪ {⊥},

Позволять αбыть символом, а X - равномерно распределенной случайной величиной над Σ', Вероятность получения этого символа, P(X = α), и его информационный контент, I(α), даются:

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

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

За слово ω ∈ Σ*и это ⊥-завершенный экземпляр ω' := ω · ⊥ ∈ (Σ')*, у нас есть

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

Поскольку генератор псевдослучайных чисел (PRNG) инициализируется 32-битным семенем, мы можем ожидать, что большинство слов длиной до

λ = пол [32 / log₂ (27)] - 1 = 5

чтобы сгенерировать, по меньшей мере, одно семя. Даже если мы будем искать 6-символьное слово, мы все равно будем добиваться успеха примерно в 41,06% случаев. Не слишком потертый.

Для 7 букв мы смотрим ближе к 1.52%, но я не осознавал этого, прежде чем дать ему попробовать:

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

См. Вывод: http://ideone.com/JRGb3l


248



Я написал краткую программу, чтобы найти эти семена:

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

Теперь у меня это работает в фоновом режиме, но уже найдено достаточно слов для классического панграма:

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

( Демо на идеон. )

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


65



Я был заинтригован этим, я запустил этот генератор случайных слов в списке словарных слов. Диапазон: Integer.MIN_VALUE для Integer.MAX_VALUE

Я получил 15131 хитов.

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

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

Печать

the quick browny fox jumps over a lazy dog 

31



Most random number generators are, in fact, "pseudo random." They are Linear Congruential Generators, or LCGs (http://en.wikipedia.org/wiki/Linear_congruential_generator)

LCGs are quite predictable given a fixed seed. Basically, use a seed that gives you your first letter, then write an app that continues to generate the next int (char) until you hit the next letter in your target string and write down how many times you had to invoke the LCG. Continue until you've generated each and every letter.


25



Random always return the same sequence. It's used for shuffling arrays and other operations as permutations.

To get different sequences, it's necessary initialize the sequence in some position, called "seed".

The randomSting get the random number in the i position (seed = -229985452) of the "random" sequence. Then uses the ASCII code for the next 27 character in the sequence after the seed position until this value are equal to 0. This return the "hello". The same operation is done for "world".

I think that the code did not work for any other words. The guy that programmed that knows the random sequence very well.

It's very great geek code!


22



As multi-threading is very easy with Java, here is a variant that searches for a seed using all cores available: 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();
    }
  }
}

20



Derived from Denis Tulskiy's answer, this method generates the seed.

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

13