Sobre la serie
Ejecutaré una pequeña serie de desafíos de código de golf que giran en torno al tema de la aleatoriedad. Básicamente será un campo de golf de 9 hoyos , pero se distribuirá en varias preguntas. Puede participar en cualquier desafío individualmente como si fuera una pregunta normal.
Sin embargo, mantendré una tabla de clasificación en todos los desafíos. La serie tendrá más de 9 desafíos (por ahora), uno publicado cada pocos días. Cada usuario que participa en los 9 desafíos es elegible para ganar la serie completa. Su puntaje general es la suma de sus presentaciones más cortas en cada desafío (por lo tanto, si responde un desafío dos veces, solo la mejor respuesta se cuenta para el puntaje). Si alguien ocupa el primer lugar en esta tabla de clasificación general durante 28 días , le otorgaré una recompensa de 500 repeticiones .
Aunque tengo un montón de ideas alineadas para la serie, los desafíos futuros aún no están establecidos en piedra. Si tiene alguna sugerencia, hágamelo saber en la publicación de sandbox relevante .
Hoyo 1: baraja una matriz
La primera tarea es bastante simple: dada una matriz no entera de enteros, baraja aleatoriamente. Sin embargo, hay algunas reglas:
- Cada permutación posible debe devolverse con la misma probabilidad (por lo que la combinación aleatoria debe tener una distribución uniforme). Puede verificar si su algoritmo es uniforme / imparcial al implementarlo en JavaScript en Will it Shuffle , que producirá una matriz de los sesgos; el resultado debería verse tan uniforme como sus Fisher-Yates incorporados u ordenar (orden aleatorio) .
- No debe utilizar ningún método incorporado o de terceros para barajar la matriz o generar una permutación aleatoria (o enumerar todas las permutaciones). En particular, la única función aleatoria incorporada que puede usar es obtener un solo número aleatorio a la vez . Usted puede asumir que cualquier incorporada de azar carreras método del número en O (1) y es perfectamente uniforme en el intervalo solicitado (en un sentido matemático - es posible ignorar los detalles de la representación de punto flotante aquí). Si su idioma le permite obtener una lista de m números aleatorios a la vez, puede usar esta función, siempre que los números m sean independientes entre sí y los cuente como O (m).
- Su implementación no debe exceder una complejidad temporal de O (N) , donde N es el tamaño de la matriz que se barajará. Por ejemplo, no puede "ordenar por números aleatorios".
- Puede barajar la matriz en su lugar o crear una nueva matriz (en cuyo caso, la matriz anterior puede modificarse como desee).
Puede escribir un programa completo o una función y recibir información a través de STDIN, argumento de línea de comando, argumento de función o solicitud y producir salida a través del valor de retorno o imprimiendo en STDOUT (o la alternativa más cercana). Si escribe una función que baraja la matriz en su lugar, no necesita devolverla, por supuesto (siempre que su idioma le permita acceder a la matriz modificada después de que la función regrese).
La entrada y la salida pueden estar en cualquier lista conveniente o formato de cadena, pero deben admitir enteros arbitrarios en el rango -2 31 ≤ x <2 31 . En principio, su código debería funcionar para matrices de hasta 2 31 de longitud , aunque esto no necesariamente tiene que caber en su memoria o completarse dentro de un período de tiempo razonable. (Simplemente no quiero ver límites de tamaño arbitrarios para los bucles de hardcode o algo así).
Este es el código de golf, por lo que gana el envío más corto (en bytes).
Tabla de clasificación
El siguiente fragmento generará una tabla de clasificación en todos los desafíos de la serie.
Para asegurarse de que sus respuestas aparezcan, comience cada respuesta con un título, utilizando la siguiente plantilla de Markdown:
# Language Name, N bytes
¿Dónde N
está el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:
# Ruby, <s>104</s> <s>101</s> 96 bytes
(El idioma no se muestra actualmente, pero el fragmento sí lo requiere y analiza, y puedo agregar una tabla de clasificación por idioma en el futuro).
/* Configuration */
var QUESTION_IDs = [45302, 45447, 46991, 49394, 51222, 66319, 89621, 120472]; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!.FjwQBrX2KXuFkv6p2lChi_RjzM19";
/* App */
var answers = [], page = 1, currentQ = -1;
function answersUrl(index) {
return "https://api.stackexchange.com/2.2/questions/" + QUESTION_IDs.join(";") + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}
function getAnswers() {
$.ajax({
url: answersUrl(page++),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
answers.push.apply(answers, data.items);
if (data.has_more) getAnswers();
else process();
}
});
}
getAnswers();
var SIZE_REG = /\d+(?=[^\d&]*(?:<(?:s>((?!>).)*<\/s>|((?!>).)+>)[^\d&]*)*$)/;
var NUMBER_REG = /\d+/;
var LANGUAGE_REG = /^#*\s*([^\n,]+)(?=,)/;//
function shouldHaveHeading(a) {
var pass = false;
var lines = a.body_markdown.split("\n");
try {
pass |= /^#/.test(a.body_markdown);
pass |= ["-", "="]
.indexOf(lines[1][0]) > -1;
pass &= LANGUAGE_REG.test(a.body_markdown);
} catch (ex) {}
return pass;
}
function shouldHaveScore(a) {
var pass = false;
try {
pass |= SIZE_REG.test(a.body_markdown.split("\n")[0]);
} catch (ex) {}
if (!pass) console.log(a);
return pass;
}
function getAuthorName(a) {
return a.owner.display_name;
}
function getAuthorId(a) {
return a.owner.user_id;
}
function process() {
answers = answers.filter(shouldHaveScore)
.filter(shouldHaveHeading);
answers.sort(function (a, b) {
var aB = +(a.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0],
bB = +(b.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0];
return aB - bB
});
var users = {};
answers.forEach(function (a) {
var headline = a.body_markdown.split("\n")[0];
var question = QUESTION_IDs.indexOf(a.question_id);
var size = parseInt((headline.match(SIZE_REG)||[0])[0]);
var language = headline.match(LANGUAGE_REG)[1];
var user = getAuthorName(a);
var userId = getAuthorId(a);
if (!users[userId]) users[userId] = {name: user, nAnswer: 0, answers: []};
if (!users[userId].answers[question]) {
users[userId].answers[question] = {size: Infinity};
users[userId].nAnswer++;
}
if (users[userId].answers[question].size > size) {
users[userId].answers[question] = {size: size, link: a.share_link}
}
});
var sortedUsers = [];
for (var userId in users)
if (users.hasOwnProperty(userId)) {
var user = users[userId];
user.score = 0;
user.completedAll = true;
for (var i = 0; i < QUESTION_IDs.length; ++i) {
if (user.answers[i])
user.score += user.answers[i].size;
else
user.completedAll = false;
}
sortedUsers.push(user);
}
sortedUsers.sort(function (a, b) {
if (a.nAnswer > b.nAnswer) return -1;
if (b.nAnswer > a.nAnswer) return 1;
return a.score - b.score;
});
var place = 1;
for (var i = 0; i < sortedUsers.length; ++i) {
var user = sortedUsers[i];
var row = '<tr><td>'+ place++ +'.</td><td>'+user.name+'</td>';
for (var j = 0; j < QUESTION_IDs.length; ++j) {
var answer = user.answers[j];
if (answer)
row += '<td><a href="'+answer.link+'">'+answer.size+'</a></td>';
else
row += '<td class="missing"></td>';
}
row += '<td></td>';
if (user.completedAll)
row += '<td class="total">'+user.score+'</td>';
else
row += '<td class="total missing">'+user.score+'</td>';
row += '</tr>';
$("#users").append(row);
}
}
body { text-align: left !important}
#leaderboard {
width: 500px;
}
#answer-list {
padding: 10px;
width: 290px;
float: left;
}
#language-list {
padding: 10px;
width: 290px;
float: left;
}
table thead {
font-weight: bold;
}
table td {
padding: 5px;
}
td.total {
font-weight: bold;
text-align: right;
}
td.missing {
background: #bbbbbb;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="leaderboard">
<h2>Leaderboard</h2>
<p>
Missing scores are shown as grey cells. A grey total indicates that the user has not participated in all challenges and is not eligible for the overall victory yet.
</p>
<table class="_user-list">
<thead>
<tr><td></td><td>User</td>
<td><a href="https://codegolf.stackexchange.com/q/45302/8478">#1</a></td>
<td><a href="https://codegolf.stackexchange.com/q/45447/8478">#2</a></td>
<td><a href="https://codegolf.stackexchange.com/q/46991/8478">#3</a></td>
<td><a href="https://codegolf.stackexchange.com/q/49394/8478">#4</a></td>
<td><a href="https://codegolf.stackexchange.com/q/51222/8478">#5</a></td>
<td><a href="https://codegolf.stackexchange.com/q/66319/8478">#6</a></td>
<td><a href="https://codegolf.stackexchange.com/q/89621/8478">#7</a></td>
<td><a href="https://codegolf.stackexchange.com/q/120472/8478">#8</a></td>
<td></td><td>Total</td>
</tr>
</thead>
<tbody id="users">
</tbody>
</table>
</div>
<table style="display: none">
<tbody id="answer-template">
<tr><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
<tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
sortby(random)
(la razón de la restricción de tiempo) o simplemente.shuffle()
(la razón de la restricción incorporada), que creo que es mucho menos inteligente que tener que implementar Fisher-Yates u otra enfoque.shuffle(array)
lugar denewArray=shuffle(array)
?Respuestas:
Dyalog APL,
2524 bytesPrimero para la solución de 25 caracteres:
i{⊃a[⍺⍵]←a[⍵⍺]}¨?i←⌽⍳⍴a←⎕
Después de algunas transformaciones de equivalencia en lo anterior:
podemos deshacernos de la tarea
i←
y guardar un personaje:{⊃a[⍺⍵]←a[⍵⍺]}¨∘?⍨⌽⍳⍴a←⎕
fuente
80386 código máquina,
4424 bytesHexdump del código:
Gracias a FUZxxl, quien sugirió usar las
rdrand
instrucciones.Aquí está el código fuente (puede ser compilado por Visual Studio):
Otra implementación más de Fisher-Yates. La mayor parte del golf se logró pasando parámetros en registros.
fuente
rdrand
para mierda y risas.Java, 88
101Un barajado básico de Fisher-Yates hace el truco. Tengo la sensación de que se usará con bastante frecuencia aquí, ya que es rápido y fácil de implementar. Aquí hay algo de hacinamiento / asignación, pero honestamente no hay demasiado para jugar al golf; Es corto por naturaleza.
Con algunos saltos de línea:
Esto se baraja en su lugar, modificando la matriz original
s[]
. Programa de prueba:fuente
Math.random()
tiene un tamaño que es una potencia de dos, por lo que esto no cumple con las especificaciones.Python 2, 86 bytes
Esta es una función que baraja la matriz en su lugar sin devolverla, utilizando una implementación sencilla de la baraja Fisher-Yates . Obtener números aleatorios de Python es costoso ...
Gracias a @xnor y @colevk por los consejos.
fuente
while i:i-=1;...
?while
tiende a ser más corto quefor
para este tipo de cosas ...i=len(L)
y colocando la disminución al comienzo del ciclo while.J,
4544 caracteresEsto fue complicado.
Aquí hay una explicación:
# y
: El recuento dey
, es decir, el número de elementos eny
.?@# y
: Un número aleatorio distribuido uniformemente en el rango de1
a(#y)-1
.x { y
: El artículo desde ely
índicex
.(<<<x) { y
: Todos los artículos excepto el artículo en el índicex
eny
.x , y
:y
anexado ax
.x ({ , <^:3@[ { ]) y
: El elemento en la posiciónx
eny
, a continuación, todos los demás elementos.(?@# ({ , <^:3@[ { ]) ]) y
Un aleatorio dey
, luego todos los demás elementos.x {. y
: Los primerosx
elementos tomados dey
.x }. y
: Los primerosx
artículos se redujo desdey
.x ({. , }.) y
: Los primerosx
elementos tomados dey
, luego los primerosx
elementos eliminados dey
x ({. , (?@# ({ , <^:3@[ { ]) ])@}.) y
: Los primerosx
artículos tomadas desdey
, entonces el primerx
artículo dey
procesó como en el número 7.x ({. , ?@#@}. ({ , <^:3@[ { ]) }.) y
: Lo mismo con la caída tirada para salvar a un personaje.u/ y
:u
insertado entre los elementos dey
.< y
: eny
caja .<"0 y
: Cada artículo de eny
caja .i. y
: enteros de0
ay - 1
.i.@# y
: enteros de0
a(#y) - 1
.(<"0@i.@# , <) y
: Números enteros de0
a(#y) - 1
cada uno en cajas y luegoy
en una sola caja. Esto es necesario porque las matrices en J son uniformes. Una caja oculta la forma de su contenido.x u&v y
: como(v x) u (v y)
.> y
:y
abierto , es decir, sin su caja.x ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&> y
la frase del número 12 se aplica a sus argumentos sin caja.({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/ y
la frase del número 21 insertada entre elementos dey
.({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/@(<"0@i.@# , <) y
la frase del número 22 se aplica al resultado de la frase del número 18, o una permutación uniforme de los elementos dey
.fuente
<@<@<@[
también es un misterio ... Esperando explicación. :)from
({
). Y realmente me gusta el&>/
truco para manipular una lista. Estoy seguro de que podría haberlo usado un par de veces antes.Pyth, 25 bytes
Pruébalo aquí.
Otra implementación más de Fisher-Yates. Es esencialmente lo mismo que la solución de Python @ Sp3000, solo en pyth.
Gracias a @Jakube por el truco de intercambio
fuente
Perl,
685644Como muchas otras soluciones, esto utiliza el algoritmo de Fisher-Yates .
Usando el comentario de nutki , se guardan 12 caracteres usando en
$_
lugar de$i
y realizando las operaciones en los índices de la matriz.44:
56:
Este es mi primer codegolf.
fuente
@_[...]
como un valor así. Se puede jugar más al golfsub f{@_[$_,$j]=@_[$j=rand$_,--$_]for 1..@_}
.C,
636160 bytesSolo una implementación directa de Fischer-Yates que ordena la matriz dada en su lugar. Compila y enlaza perfectamente bien con el compilador visual studio (vs2013, no he probado las otras versiones) y el compilador Intel. La firma de la función de aspecto agradable es
s(int array[], int length)
. Estoy legítimamente impresionado de vencer a Python y Ruby.Esto asume que
srand()
se llama y rand () se implementa correctamente, pero creo que esta regla permite eso:Versión bien formateada:
fuente
s(a,m)*a{
, pero no estoy seguro y tampoco quiero probarlo. Es posible que desee hacer unxor
intercambio, como ena[i]^=a[m]^=a[i]^=a[m]
. Esto también evita la necesidad de declarart
.i==m
.s(a,m)int*a
para Visual Studio y el compilador de Intel. No tengo gcc o clang instalados para probar, pero supongo que también se quejarán.t=a[i]
, puede mover lai=rand()%m--
declaración dentro como el índice de matriz.Octava,
8877 bytesOtra implementación de Fisher-Yates ... Debería ser bastante sencillo si agrego los retornos y el espaciado de línea habituales:
Las palabras clave de "fin" realmente matan el puntaje de golf aquí, desafortunadamente.¡Hola, puedo usar "end" en lugar de "endfor" y "endfunction"!fuente
numel
lugar delenght
. ComoJava 8, 77
Es una lambda que toma
int[]
y regresa vacía. Mi primer intento no pareció muy interesante, así que decidí que saliera lanzando una excepción.Programa de prueba:
fuente
Math.random()
?Golflua, 37
¿Cómo ejecutar Golflua?
La entrada se proporciona como una tabla en la variable X. La tabla se baraja en su lugar.
Ejemplo de uso:
fuente
R, 79 bytes
Esta es una implementación sencilla del shuffle de Fisher-Yates. La función R
sample
extrae una muestra aleatoria simple de un tamaño dado de un vector dado con igual probabilidad. Aquí estamos dibujando una muestra aleatoria de tamaño 1 en cada iteración de los enterosi
, ...,n
. Como se indicó en la pregunta, se puede suponer que esto es O (1), por lo que en toda esta implementación debe ser O (N).fuente
Matlab, 67
También implementando Fisher-Yates.
Pensé que era una pena no poder usar la
randperm
función de Matlab . Pero después de jugar un poco, pensé que podría mirar la fuente derandperm
para ver cómo se hace, y me sorprendió ver que solo había una línea:[~,p] = sort(rand(1,n))
=)fuente
Perl, 44
Otro perl en 44 caracteres. Ejemplo de uso:
fuente
Mathematica,
82 90 8393 bytesNota: Esta variación de la mezcla aleatoria de Fisher-Yates es en realidad la solución de Martin Büttner, con algunos códigos par alephalpha.
s
es la matriz de entrada. Nada sofisticado, pero a veces las cosas simples son las más esquivas.fuente
Do
aquí. Es más corto queWhile
.Ruby, 57 bytes
Entrada (como función lambda):
Salida:
fuente
TI-BASIC, 46 bytes
Fuente para el recuento de bytes
fuente
End
.K, 31 caracteres
No es tan corta como la que he puesto antes (que fue descalificado) ... oh bien.
Es un barajado básico de Fisher-Yates. Esto fue construido con mucha ayuda de la lista de correo de Kona .
fuente
JavaScript (ES6), 66
Esta función baraja la matriz en su lugar. También devuelve una matriz de subproductos que NO es la salida barajada y no debe considerarse.
fuente
MATL , 16 bytes
Pruébalo en línea!
Fisher-Yates en MATL. Casi un tercio de este programa está dedicado a la letra
H
, que corresponde a la función del portapapeles en MATL.Básicamente,
H
almacena los elementos no utilizados de la entrada, mientras que la pila realiza un seguimiento de la lista aleatoria.fuente
Japt, 12
¡Intentalo!
-10 (aproximadamente la mitad;) gracias a @Shaggy!
Tenía muchas ganas de probar un lenguaje de golf, y el intérprete de Japt tenía una buena documentación y una forma de probar las cosas en el navegador.
A continuación se muestra la estrategia que tomé:
fuente
Javascript ES6, 69
Es Fisher-Yates.
PD: se puede probar en Firefox
fuente
Pyth, 27 bytes
Pruébalo aquí
Esta es una implementación del shuffle incremental de Fisher-Yates, mencionado aquí en segundo lugar .
fuente
Haskell, 170
Otra solución de Fisher-Yates inspirada en el algoritmo en https://wiki.haskell.org/Random_shuffle .
s
es una función que tiene firma:IOArray Int a -> IO [a]
fuente
CJam - 30
Pruébalo en http://cjam.aditsu.net/
Entrada de ejemplo:
[10 20 30 40 50]
Salida de ejemplo:
3020401050
(agregue unp
al final del código para una impresión bonita)Si se permite que el código tome la entrada de la pila (como una función), entonces los primeros 2 caracteres se pueden eliminar, reduciendo el tamaño a 28.Explicación:
El código es más largo de lo que esperaba, debido a la falta de un operador "swap" para las matrices
(que se implementará más adelante: p)
fuente
_
es O (N) (dentro de un bucle O (N)). Desafortunadamente, no veo una manera de evitar eso en CJam.t
que lo mata, ya que no puede mutar la lista y ahora debe crear una copia.t
, me gustaría mejorarlo en futuras versiones ..JavaScript (ES 6), 61
Puede probarlo aquí simplemente agregando una línea que diga
shuffle = S
(solo Firefox).fuente
STATA, 161
Espera entrada como números separados por espacios. Si lo desea, puedo eliminar los encabezados y los números de observación de la salida, pero de lo contrario, esto es más corto.
fuente
_n
en estoJava, 93 bytes
Ejemplo de uso: http://ideone.com/RqSMnZ
fuente
SQF, 91 bytes
fuente
%x
por%i
.Perl, 41 bytes
Pruébalo en línea!
fuente