О серии

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

Несмотря на то, что у меня есть ряд идей для этой серии, будущие проблемы еще не заложены. Если у вас есть какие-либо предложения, пожалуйста, сообщите мне об этом в соответствующей песочнице .

Отверстие 6: Roll d20

Очень распространенный кубик в настольных РПГ - это двадцатигранный кубик ( икосаэдр , широко известный как d20 ). Ваша задача бросить такой кубик. Однако, если вы просто возвращали случайное число от 1 до 20, это было бы немного тривиально. Итак, ваша задача - создать случайную сеть для данного кубика.

Мы будем использовать следующую сеть:

Это треугольная полоса, поэтому ее легко представить в виде списка целых чисел. Например, если вам дают вход:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Это соответствовало бы следующему кубику (забавный факт: это сеть, используемая Магией: Собрание счетчиков жизни / игральные кости).

Тем не менее, это не единственная сеть, представляющая этот кубик. В зависимости от того, как мы разворачиваем лица, существует 60 различных сетей. Вот еще два:

[1, 8, 9, 10, 2, 3, 4, 5, 6, 7, 17, 18, 19, 11, 12, 13, 14, 15, 16, 20]
[10, 9, 18, 19, 11, 12, 3, 2, 1, 8, 7, 17, 16, 20, 13, 14, 4, 5, 6, 15]

Или графически (я не поворачивал метки лица для простоты):

Соревнование

Учитывая список целых чисел, представляющих матрицу (как описано выше) и целое число N, выведите Nнезависимо, равномерно случайные сети d20, соответствующие данному кристаллу. (То есть каждая из 60 возможных сетей должна иметь одинаковую вероятность генерации.)

Конечно, из-за технических ограничений PRNG идеальная однородность будет невозможна. Для оценки единообразия вашего представления следующие операции будут рассматриваться как обеспечивающие абсолютно равномерное распределение:

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

Учитывая эти предположения, ваш алгоритм должен давать идеально равномерное распределение.

Ваша программа должна быть способна генерировать 100 сетей менее чем за секунду (поэтому не пытайтесь генерировать случайные сети, пока одна из них не соответствует матрице, указанной выше).

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

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

Это код гольф, поэтому выигрывает самое короткое представление (в байтах). И, конечно же, самая короткая заявка на пользователя также войдет в общую таблицу лидеров серии.

Примеры выходов

Для ввода

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

60 возможных сетей (при условии, что я не ошибся) в произвольном порядке:

[11, 10, 9, 18, 19, 20, 13, 12, 3, 2, 1, 8, 7, 17, 16, 15, 14, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[8, 7, 17, 18, 9, 10, 2, 1, 5, 6, 15, 16, 20, 19, 11, 12, 3, 4, 14, 13]
[3, 12, 13, 14, 4, 5, 1, 2, 10, 11, 19, 20, 16, 15, 6, 7, 8, 9, 18, 17]
[3, 4, 5, 1, 2, 10, 11, 12, 13, 14, 15, 6, 7, 8, 9, 18, 19, 20, 16, 17]
[11, 19, 20, 13, 12, 3, 2, 10, 9, 18, 17, 16, 15, 14, 4, 5, 1, 8, 7, 6]
[4, 14, 15, 6, 5, 1, 2, 3, 12, 13, 20, 16, 17, 7, 8, 9, 10, 11, 19, 18]
[2, 10, 11, 12, 3, 4, 5, 1, 8, 9, 18, 19, 20, 13, 14, 15, 6, 7, 17, 16]
[4, 5, 1, 2, 3, 12, 13, 14, 15, 6, 7, 8, 9, 10, 11, 19, 20, 16, 17, 18]
[10, 2, 1, 8, 9, 18, 19, 11, 12, 3, 4, 5, 6, 7, 17, 16, 20, 13, 14, 15]
[3, 2, 10, 11, 12, 13, 14, 4, 5, 1, 8, 9, 18, 19, 20, 16, 15, 6, 7, 17]
[7, 8, 1, 5, 6, 15, 16, 17, 18, 9, 10, 2, 3, 4, 14, 13, 20, 19, 11, 12]
[13, 12, 11, 19, 20, 16, 15, 14, 4, 3, 2, 10, 9, 18, 17, 7, 6, 5, 1, 8]
[16, 15, 14, 13, 20, 19, 18, 17, 7, 6, 5, 4, 3, 12, 11, 10, 9, 8, 1, 2]
[15, 16, 17, 7, 6, 5, 4, 14, 13, 20, 19, 18, 9, 8, 1, 2, 3, 12, 11, 10]
[20, 13, 12, 11, 19, 18, 17, 16, 15, 14, 4, 3, 2, 10, 9, 8, 7, 6, 5, 1]
[5, 4, 14, 15, 6, 7, 8, 1, 2, 3, 12, 13, 20, 16, 17, 18, 9, 10, 11, 19]
[10, 11, 12, 3, 2, 1, 8, 9, 18, 19, 20, 13, 14, 4, 5, 6, 7, 17, 16, 15]
[4, 3, 12, 13, 14, 15, 6, 5, 1, 2, 10, 11, 19, 20, 16, 17, 7, 8, 9, 18]
[19, 20, 13, 12, 11, 10, 9, 18, 17, 16, 15, 14, 4, 3, 2, 1, 8, 7, 6, 5]
[1, 8, 9, 10, 2, 3, 4, 5, 6, 7, 17, 18, 19, 11, 12, 13, 14, 15, 16, 20]
[8, 1, 5, 6, 7, 17, 18, 9, 10, 2, 3, 4, 14, 15, 16, 20, 19, 11, 12, 13]
[18, 9, 8, 7, 17, 16, 20, 19, 11, 10, 2, 1, 5, 6, 15, 14, 13, 12, 3, 4]
[12, 3, 2, 10, 11, 19, 20, 13, 14, 4, 5, 1, 8, 9, 18, 17, 16, 15, 6, 7]
[2, 3, 4, 5, 1, 8, 9, 10, 11, 12, 13, 14, 15, 6, 7, 17, 18, 19, 20, 16]
[10, 9, 18, 19, 11, 12, 3, 2, 1, 8, 7, 17, 16, 20, 13, 14, 4, 5, 6, 15]
[9, 8, 7, 17, 18, 19, 11, 10, 2, 1, 5, 6, 15, 16, 20, 13, 12, 3, 4, 14]
[16, 17, 7, 6, 15, 14, 13, 20, 19, 18, 9, 8, 1, 5, 4, 3, 12, 11, 10, 2]
[17, 7, 6, 15, 16, 20, 19, 18, 9, 8, 1, 5, 4, 14, 13, 12, 11, 10, 2, 3]
[1, 5, 6, 7, 8, 9, 10, 2, 3, 4, 14, 15, 16, 17, 18, 19, 11, 12, 13, 20]
[9, 18, 19, 11, 10, 2, 1, 8, 7, 17, 16, 20, 13, 12, 3, 4, 5, 6, 15, 14]
[16, 20, 19, 18, 17, 7, 6, 15, 14, 13, 12, 11, 10, 9, 8, 1, 5, 4, 3, 2]
[5, 1, 2, 3, 4, 14, 15, 6, 7, 8, 9, 10, 11, 12, 13, 20, 16, 17, 18, 19]
[8, 9, 10, 2, 1, 5, 6, 7, 17, 18, 19, 11, 12, 3, 4, 14, 15, 16, 20, 13]
[13, 20, 16, 15, 14, 4, 3, 12, 11, 19, 18, 17, 7, 6, 5, 1, 2, 10, 9, 8]
[6, 15, 16, 17, 7, 8, 1, 5, 4, 14, 13, 20, 19, 18, 9, 10, 2, 3, 12, 11]
[6, 5, 4, 14, 15, 16, 17, 7, 8, 1, 2, 3, 12, 13, 20, 19, 18, 9, 10, 11]
[7, 6, 15, 16, 17, 18, 9, 8, 1, 5, 4, 14, 13, 20, 19, 11, 10, 2, 3, 12]
[19, 18, 17, 16, 20, 13, 12, 11, 10, 9, 8, 7, 6, 15, 14, 4, 3, 2, 1, 5]
[14, 15, 6, 5, 4, 3, 12, 13, 20, 16, 17, 7, 8, 1, 2, 10, 11, 19, 18, 9]
[17, 18, 9, 8, 7, 6, 15, 16, 20, 19, 11, 10, 2, 1, 5, 4, 14, 13, 12, 3]
[6, 7, 8, 1, 5, 4, 14, 15, 16, 17, 18, 9, 10, 2, 3, 12, 13, 20, 19, 11]
[14, 13, 20, 16, 15, 6, 5, 4, 3, 12, 11, 19, 18, 17, 7, 8, 1, 2, 10, 9]
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[7, 17, 18, 9, 8, 1, 5, 6, 15, 16, 20, 19, 11, 10, 2, 3, 4, 14, 13, 12]
[15, 6, 5, 4, 14, 13, 20, 16, 17, 7, 8, 1, 2, 3, 12, 11, 19, 18, 9, 10]
[9, 10, 2, 1, 8, 7, 17, 18, 19, 11, 12, 3, 4, 5, 6, 15, 16, 20, 13, 14]
[2, 1, 8, 9, 10, 11, 12, 3, 4, 5, 6, 7, 17, 18, 19, 20, 13, 14, 15, 16]
[12, 13, 14, 4, 3, 2, 10, 11, 19, 20, 16, 15, 6, 5, 1, 8, 9, 18, 17, 7]
[17, 16, 20, 19, 18, 9, 8, 7, 6, 15, 14, 13, 12, 11, 10, 2, 1, 5, 4, 3]
[18, 17, 16, 20, 19, 11, 10, 9, 8, 7, 6, 15, 14, 13, 12, 3, 2, 1, 5, 4]
[18, 19, 11, 10, 9, 8, 7, 17, 16, 20, 13, 12, 3, 2, 1, 5, 6, 15, 14, 4]
[11, 12, 3, 2, 10, 9, 18, 19, 20, 13, 14, 4, 5, 1, 8, 7, 17, 16, 15, 6]
[15, 14, 13, 20, 16, 17, 7, 6, 5, 4, 3, 12, 11, 19, 18, 9, 8, 1, 2, 10]
[19, 11, 10, 9, 18, 17, 16, 20, 13, 12, 3, 2, 1, 8, 7, 6, 15, 14, 4, 5]
[12, 11, 19, 20, 13, 14, 4, 3, 2, 10, 9, 18, 17, 16, 15, 6, 5, 1, 8, 7]
[20, 16, 15, 14, 13, 12, 11, 19, 18, 17, 7, 6, 5, 4, 3, 2, 10, 9, 8, 1]
[13, 14, 4, 3, 12, 11, 19, 20, 16, 15, 6, 5, 1, 2, 10, 9, 18, 17, 7, 8]
[5, 6, 7, 8, 1, 2, 3, 4, 14, 15, 16, 17, 18, 9, 10, 11, 12, 13, 20, 19]
[14, 4, 3, 12, 13, 20, 16, 15, 6, 5, 1, 2, 10, 11, 19, 18, 17, 7, 8, 9]

Для любой другой сети, просто заменить каждое вхождение iс iго числа на входе (где iнаходится 1-основе).

Связанные проблемы

• Охота на Wumpus
• Рисование 3d сетей - Платоновых тел

Leaderboard

Первый пост серии генерирует таблицу лидеров.

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

## Language Name, N bytes

где Nразмер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:

## Ruby, <s>104</s> <s>101</s> 96 bytes

(Язык в настоящее время не отображается, но фрагмент требует и анализирует его, и я могу добавить таблицу лидеров по языкам в будущем.)

Рубин, 160 байтов (rev B)

17 байтов сэкономлено благодаря предложениям Мартина Бюттнера.

->a,n{n.times{k=rand 60
%w{ABCD@GHIJKLMNEFPQRSO PFENOSRQHG@DCMLKJIAB GFPQHIA@DENOSRJKBCML}.map{|b|k.times{a=b.chars.map{|i|a[i.ord-64]}}}
k>29&&a.reverse!
p a}}

Рубин, 177 байт (версия A)

->n,a{n.times{k=rand(60)
h=->b{k.times{|j|a=(0..19).map{|i|a[b[i].ord-64]}}}
h['ABCD@GHIJKLMNEFPQRSO']
h['PFENOSRQHG@DCMLKJIAB']
h['GFPQHIA@DENOSRJKBCML']
k>29&&a.reverse!
p a}}

объяснение

Можно генерировать все возможные ориентации путем поворота вокруг одной грани (в 3 раза), одной вершины (в 5 раз) и двух ребер (в 2 раза). Но не просто лицо и края. Оси должны иметь правильное соотношение, и вращения должны выполняться в правильном порядке, иначе могут произойти странные вещи.

Я так и сделал (хотя я понимаю, что Мартин сделал это по-другому)

Все ориентации тетраэдра могут быть созданы комбинацией следующих трех операций симметрии:

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

б) Вращение вокруг 3-кратной оси, диагональной 2-кратным осям, проходящей через вершину и грань.

Симметрия икосаэдра является надмножеством симметрии тетраэдра. На изображении ниже от https://en.wikipedia.org/wiki/Icosahedron желтые и красные грани определяют два разных тетраэдра (или, альтернативно, один октаэдр), в то время как края, общие для двух синих граней, находятся в трех парах на прямые углы (и лежат на гранях куба.)

Все ориентации икосаэдра могут быть получены с помощью упомянутых выше операций симметрии плюс дополнительная 5-кратная операция.

Вращения вокруг трех из четырех упомянутых осей представлены волшебными струнами между ''метками. Вращение вокруг второй 2-кратной оси отличается, и может быть сделано только путем обращения массиваa[] .

Разгружен в тестовой программе:

f=->a,n{
  n.times{                     #Iterate n times, using the result from the previous iteration to generate the next
    k=rand(60)                 #pick a random number

    h=->b{                     #helper function taking a string representing a transformation
      k.times{|j|              #which is performed on a using the number of times according to k
        a=(0..19).map{|i|a[b[i].ord-64]}
      }
    }

    #Rotate about axes k times (one 5-fold, one 3-fold, two 2-fold)
    #The first three axes have coprime rotation orders
    #And the rotations themselves take care of the modulus operation so no need to add it.
    #The second 2-fold rotation is equivalent to reversing the order
    #And is applied to the last 30 numbers as it is not coprime with the first 2-fold rotation.

    h['ABCD@GHIJKLMNEFPQRSO']  #rotate k times about 5-fold axis
    h['PFENOSRQHG@DCMLKJIAB']  #rotate k times about 3-fold axis
    h['GFPQHIA@DENOSRJKBCML']  #rotate k times about 2-fold axis
    k>29&&a.reverse!
    p a
  }
}

z=(1..20).map{|i|i} 
f[z,50]

Альтернативное решение 131 байт (неверно из-за подхода двоичного случайного блуждания, дает только приблизительно правильное распределение.)

->a,n{(n*99).times{|i|s=['@DEFGHIABCMNOPQRJKLS','ABCD@GHIJKLMNEFPQRSO'][rand(2)] 
a=(0..19).map{|i|a[s[i].ord-64]}
i%99==98&&p(a)}}

Это схватка (так же, как программы, используемые для шифрования кубика Рубика.)

Конкретные повороты, которые я использую, являются двумя из наиболее очевидных:

-Вращение на 120 градусов (около граней 1 и 20 на первой диаграмме)

-Вращение на 72 градуса (около вершин, общих для 1,2,3,4,5 и 16,17,18,19,20 на первой диаграмме.)

мы подбрасываем монету 99 раз, и каждый раз выполняем одно из этих двух вращений в зависимости от того, голова это или хвост.

Обратите внимание, что чередование этих данных приводит к довольно коротким последовательностям. Например, при правильных ощущениях вращения, поворот на 180 градусов может быть произведен с периодом всего 2.

Машинный код IA-32, 118 байт

HexDump:

60 33 c0 51 8b 74 24 28 8b fa 6a 05 59 f3 a5 e8
21 00 00 00 20 c4 61 cd 6a 33 00 84 80 ad a8 33
32 00 46 20 44 8e 48 61 2d 2c 33 32 4a 00 21 20
a7 a2 90 8c 00 5b b1 04 51 0f c7 f1 83 e1 1f 49
7e f7 51 8b f2 56 8d 7c 24 e0 b1 14 f3 a4 5f 8b
f3 ac 8b ee d4 20 86 cc e3 0a 56 8d 74 04 e0 f3
a4 5e eb ed 59 e2 db 8b dd 59 e2 cc 59 83 c2 14
e2 91 61 c2 04 00

Это немного долго, поэтому некоторые объяснения идут в первую очередь. Я использовал почти тот же алгоритм, что и существующий ответ по уровню реки Св . Чтобы сделать свой ответ другим, я взял другие базовые перестановки, которые не обязательно имеют интуитивное геометрическое значение, но как-то более удобны.

Код в основном должен генерировать перестановку, которая представляет собой последовательное применение следующего:

1. Перестановка порядка 3, которую я называю p3, применялась 0 ... 2 раза
2. Перестановка порядка 2, которую я называю q2, применяется 0 или 1 раз
3. Перестановка порядка 5, которую я называю p5, применялась 0 ... 4 раза
4. Другая перестановка порядка 2, которую я называю p2, применялась 0 или 1 раз

Есть много возможных вариантов для этих перестановок. Один из них выглядит следующим образом:

p3 = [0   4   5   6   7   8   9   1   2   3  13  14  15  16  17  18  10  11  12  19]
q2 = [4   5   6   7   0   1   2   3  13  14  15  16  17   8   9  10  11  12  19  18]
p5 = [6   7   0   4   5  14  15  16  17   8   9   1   2   3  13  12  19  18  10  11]
p2 = [1   0   7   8   9  10  11   2   3   4   5   6  16  17  18  19  12  13  14  15]

Этот выбор лучше, чем другие, потому что перестановки здесь имеют длинные последовательности последовательных индексов, которые могут быть сжаты кодированием по длине прогона - всего 29 байтов для 4 перестановок.

Чтобы упростить генерацию случайных чисел, я выбрал степени (сколько раз применяется каждая перестановка) в диапазоне 1 ... 30 для всех из них. Это приводит к большой дополнительной работе в коде, потому что, например, p3становится перестановкой идентификаторов каждый раз, когда она умножается на себя в 3 раза. Тем не менее, в этом случае код меньше, и пока диапазон делится на 30, выходные данные будут иметь равномерное распределение.

Кроме того, мощности должны быть положительными, чтобы операция декодирования по длине прогона выполнялась хотя бы один раз.

Код имеет 4 вложенных цикла; схема выглядит так:

void doit(int n, uint8_t* output, const uint8_t input[20])
{    
    uint8_t temp[20];

    n_loop: for i_n = 0 ... n
    {
        memcpy(output, input, 20);
        expr_loop: for i_expr = 0 ... 3
        {
            power = rand(1 ... 30);
            power_loop: for i_power = 0 ... power
            {
                memcpy(temp, output, 20);
                output_index = 0;
                perm_loop: do while length > 0
                {
                    index = ...; // decode it
                    length = ...; // decode it
                    memcpy(output + output_index, temp + index, length);
                    output_index += length;
                }
            }
        }
        output += 20;
    }
}

Я надеюсь, что этот псевдокод понятнее, чем код встроенной сборки ниже.

_declspec(naked) void __fastcall doit(int n, uint8_t* output, const uint8_t* input)
{
    _asm {
        pushad
        xor eax, eax

        n_loop:
            push ecx

            ; copy from input to output
            mov esi, [esp + 0x28]
            mov edi, edx
            push 5
            pop ecx
            rep movsd

            call end_of_data
#define rl(index, length) _emit(length * 32 + index)
            rl(0, 1)
            rl(4, 6)
            rl(1, 3)
            rl(13, 6)
            rl(10, 3)
            rl(19, 1)
            _emit(0)

            rl(4, 4)
            rl(0, 4)
            rl(13, 5)
            rl(8, 5)
            rl(19, 1)
            rl(18, 1)
            _emit(0)

            rl(6, 2)
            rl(0, 1)
            rl(4, 2)
            rl(14, 4)
            rl(8, 2)
            rl(1, 3)
            rl(13, 1)
            rl(12, 1)
            rl(19, 1)
            rl(18, 1)
            rl(10, 2)
            _emit(0)

            rl(1, 1)
            rl(0, 1)
            rl(7, 5)
            rl(2, 5)
            rl(16, 4)
            rl(12, 4)
            _emit(0)

            end_of_data:
            pop ebx ; load the address of the encoded data
            mov cl, 4

            expr_loop:
                push ecx

                make_rand:
                rdrand ecx
                and ecx, 31
                dec ecx
                jle make_rand

                ; input: ebx => encoding of permutation
                ; output: ebp => encoding of next permutation
                power_loop:
                    push ecx

                    ; copy from output to temp
                    mov esi, edx
                    push esi
                    lea edi, [esp - 0x20]
                    mov cl, 20
                    rep movsb
                    pop edi

                    ; ebx => encoding of permutation
                    ; edi => output
                    mov esi, ebx
                    perm_loop:
                        ; read a run-length
                        lodsb
                        mov ebp, esi

                        _emit(0xd4)             ; divide by 32, that is, split into
                        _emit(32)               ; index (al) and length (ah)
                        xchg cl, ah             ; set ecx = length; also makes eax = al
                        jecxz perm_loop_done    ; zero length => done decoding
                        push esi
                        lea esi, [esp + eax - 0x20]
                        rep movsb
                        pop esi
                        jmp perm_loop

                    perm_loop_done:
                    pop ecx
                    loop power_loop

                mov ebx, ebp
                pop ecx
                loop expr_loop

            pop ecx
            add edx, 20
            loop n_loop

        popad
        ret 4
    }
}

Некоторые забавные детали реализации:

• Я использовал сборку с отступами, как в языках высокого уровня; в противном случае код был бы непонятным беспорядком
• Я использую callи последующие popдля доступа к данным (закодированные перестановки), хранящиеся в коде
• jecxzИнструкция удобно позволяет мне использовать нулевые байты в качестве окончания процесса декодирования длины прогона

• К счастью, число 30 (2 * 3 * 5) почти равно степени 2. Это позволяет мне использовать короткий код для генерации числа в диапазоне 1 ... 30:

          and ecx, 31
          dec ecx
          jle make_rand
  

• Я использую инструкцию «деления общего назначения» ( aam) для разделения байта на битовые поля (3-битная длина и 5-битный индекс); к счастью, в этой позиции в коде cl = 0, так что я извлекаю выгоду из обеих "сторон"xchg