Eres un geek de programación joven que vive con tus otros 2 mejores amigos. Cada semana, uno de ustedes tiene que hacer todas las tareas de la casa y usted decide de quién es el turno escogiendo un palo. El que elige el palo más corto pierde y hace todas las tareas.
Como todos ustedes son programadores y les encanta crear rompecabezas, han modificado el "Elija el palo más corto" en un rompecabezas de computadora.
Aquí están las reglas del rompecabezas.
- Se le dará una matriz 2D, donde cada columna representa un palo.
- En cada columna, 1 representa una porción del palo y 0 es un espacio vacío
- Al ir de arriba a abajo en cada columna, inicialmente tienes
0
una y tan pronto como tocas un1
, el palo ha comenzado y el resto de la columna se llenará con1
solo - Puede escribir su programa para elegir una columna. El tamaño del palo en esa columna determina el ganador / perdedor. Tamaño del palo == número de 1s en esa columna.
- Sin embargo, ese programa solo puede tener una complejidad lineal en el peor de los casos.
Como todos ustedes son programadores, sabrán si el programa de otra persona está disparando el límite de complejidad de tiempo.
Tu trabajo es:
- Escriba un programa o función que acepte entradas en formato 2D o en un conjunto de cadenas.
- La entrada se puede tomar de STDIN / prompt / console o un argumento de función.
- Si está leyendo la entrada de STDIN / prompt, entonces puede suponer que la lectura de la entrada y convertirla en una matriz lleva 0 tiempo (aunque el código para hacerlo debe estar allí en su respuesta)
- Determine la columna con el palo más largo.
- La salida puede ser el valor de retorno de la función o STDOUT / console / alert.
- El programa / función debe tener una complejidad lineal en el peor de los casos,
O(m+n)
dondem
es el número de filas yn
el número de columnas.
La entrada puede ser uno de los siguientes formatos:
Matriz 2D:
[ [0, 0, 0, 0],
[1, 0, 0, 0],
[1, 1, 0, 1],
[1, 1, 1, 1] ]
Matriz de cuerdas:
[ "0000", "1000", "1101", "1111" ]
La entrada tendrá las siguientes propiedades:
- El tamaño de la matriz es desconocido, suponga un rectángulo de cualquier tamaño
- En cualquier columna, de arriba hacia abajo, si ve un 1, todo lo que se muestra a continuación será uno
- Se permiten palos de columnas vacías (es decir, de longitud 0) .
Este es un código de golf, ¡el código más corto gana ! *
Explique su código o proporcione la versión no protegida (para verificar la complejidad del tiempo) junto con cuál de los dos formatos de entrada espera.
ACTUALIZACIÓN La complejidad del tiempo lineal aquí significa O (n + m) donde n es el tamaño de la columna ym es el tamaño de la fila. (Para aquellos que no estaban claros)
ACTUALIZACIÓN 2 Esto definitivamente se puede hacer en tiempo lineal. Y si está publicando una respuesta, siéntase libre de retrasar la publicación de la lógica / algoritmo por un par de días para una pelea justa :)
ACTUALIZACIÓN 3 Revisaré todas las respuestas en un par de horas para validar la complejidad del tiempo y el programa :)
fuente
1
en la entrada es la última celda. Es necesario leer toda la entrada. Incluso si la biblioteca estándar de un idioma falsifica el acceso aleatorio a stdin, debajo de las escenas lo está almacenando en búfer y, por lo tanto, el tiempo necesario es Omega (n * m).Respuestas:
GolfScript, 45 caracteres
Toma la entrada como una matriz de cadenas, devuelve el índice (basado en 0) de la columna más alta. Se ejecuta en iteraciones O ( filas + columnas ), y cada iteración debe tomar esencialmente un tiempo constante (al menos suponiendo una aritmética de tiempo constante). Las únicas operaciones de matriz / cadena realizadas dentro del bucle son búsquedas de elementos (
=
) y tomar la longitud de una cadena (,
), las cuales toman tiempo constante en GolfScript.Pruébalo en línea.
Explicación:
Como la mayoría de las soluciones aquí, este código funciona comenzando en la esquina inferior izquierda de la matriz, caminando hacia arriba o hacia la derecha dependiendo de si el elemento actual de la matriz es 1 o 0, y haciendo un seguimiento de la columna donde se movió por última vez .
Al comienzo del programa, asigno la matriz de entrada a la variable
^
, su longitud (es decir, el número de filas)y
y 0 ax
. El valor 0 también se deja en la pila; durante el siguiente ciclo, será reemplazado por el índice de la columna más alta.Dentro del bucle principal,
^y(=x=
extrae elx
carácter -th de lay-1
fila -th en^
. En realidad, esto devuelve el código ASCII del personaje, por lo que2%
es necesario descartar todo menos el último bit. Como un caso especial, siy
es igual a 0 (lo que puede suceder si la columna más alta encontrada hasta el momento llega hasta la fila superior), el bit buscado en realidad vendrá de la última fila de la matriz (índice -1), pero lo siguiente loy*
fuerza a cero, creando así efectivamente una fila virtual de ceros en la parte superior de la matriz.A continuación
if
, se ejecutará uno de los dos bloques de código que lo preceden, dependiendo de si el bit buscado no es cero (verdadero) o cero (falso). Si no es cero,y
se reduce en uno, y el valor actual dex
reemplaza el índice de columna más alto en la pila (con el valor anterior temporalmente dejado encima). Si es cero,x
simplemente se incrementa en uno (y se deja temporalmente en la pila, encima del índice de la columna más alta).Finalmente,
^0=
extrae la primera fila de la matriz,,
devuelve su longitud y la<
compara con el índice de la columna que queda temporalmente en la pila (que será igualx
si solo se incrementara) Si el índice es menor que la longitud de la fila, el bucle se repitePD. Según mis pruebas, debería ser posible acortar este programa en un carácter reemplazando la prueba de longitud de la cadena
,<
al final del ciclo con>
, que corta la cadena en el índice dado y devuelve la parte final (que estará vacía, y así falso, al final del ciclo). Sin embargo, aunque cortar una cadena como esa parece implementarse como una operación de tiempo constante en GolfScript (o, más bien, en Ruby, que GolfScript ejecuta encima), no he encontrado ninguna documentación oficial que lo diga. Solo para estar seguro, he elegido presentar la versión un poco más larga, pero definitivamente O (1) anterior.fuente
Ruby,
8375686663 bytesDefine una función
f
que toma la forma de matriz 2D como entrada.fuente
Python 2 -
71, 69, 73, 7581fuente
i
se saldrá de los límites si un palo ocupa una columna completa?j
para contar desde0
rompe la condición del buclei*j
.C, 64 bytes
Editar: Aprendí que la pregunta pide la ubicación de la columna más larga y no su longitud.
La primera línea es el código de golf y el resto es la invocación de muestra.
fuente
int
s en la firma de la función por casualidad o no funciona debido a los punteros allí?C #: 236 caracteres
sin golf:
fuente
PHP 5.4 - 108 bytes
(113 si incluye el
<?php
)Formato de entrada: la matriz se leerá como una cadena JSON.
Se agregaron espacios en blanco para facilitar la lectura: se pueden eliminar todas las líneas nuevas y espacios iniciales
Versión minimizada:
Es como robar el algoritmo de Martin aquí, pero es bueno jugar con lenguajes que no se ven con tanta frecuencia aquí XD
fuente
$s=json_decode($argv[1]);$t=count($s)-1;
con$t=count($s=json_decode($argv[1]))-1;
(-3 bytes).$t--
solo debe suceder si se cumple la condición.Cobra - 98
fuente
C ++ :: 78
A diferencia de la otra solución C, este es todo el programa. (no se necesita invocación, no es necesario decirle a la función el tamaño de la matriz). Desafortunadamente, esto significa que es más largo, ya que
main
debe usarse en lugar de un nombre de función de un solo carácter, tengo que interpretar la entrada y luego la salida, donde la otra solución maneja eso "en otro lugar". También mi primer código de golf.compilado con
g++ file.cpp -include iostream
, ejecutado con./a 000 010 110 111
(por ejemplo) == matriz de cadenas (creo que esto está permitido en la especificación de la pregunta)La versión anterior genera el mejor actual encontrado hasta ahora en cada iteración. El último dígito de salida es la respuesta. El cambio del procesamiento desde la parte inferior izquierda en lugar de la parte inferior derecha e
0
indexación redujo esta solución en 10 (!) Caracteres.el cambio a c ++ elimina la presentación por un carácter más, ya que
std::cout<<
es más cortoputchar(-48)
y también debe admitir explícitamente más de 9 palos con la salida adecuada (aunque puede ser más difícil diferenciar cada salida)Eliminar el campo de respuesta y enviarlo directamente corta otros 6 caracteres. Ahora solo genera la mejor corriente cuando se mueve hacia arriba, lo que corta al menos parte de la salida.
El archivo completo ahora tiene solo 78 bytes de tamaño, acercándose a la solución única de la función que el otro
C
presentación de usos. (con un montón de código adicional para admitir dicha función).Como a continuación la descripción está desactualizada:
¿Puedo incluso golf esto más lejos?
Código no protegido (con salida adicional):
fuente
OCaml - 144 caracteres
Toma una
int array array
entrada como, y comienza desde abajo a la izquierda, moviéndose hacia arriba o hacia la derecha si ve a1
o a0
. El recuento de columnas comienza en0
.Uso
Sin golf
fuente
T-SQL -
7164Toma la tabla A como entrada
Y la consulta es
SQLFiddle
Esto devuelve la primera fila de la tabla a ordenada por r donde hay un 1 en la cadena a.
TOP(1)
restringe el resultado a la primera fila devuelta.CHARINDEX('1',A)
devuelve la posición del primer 1 en la cadena o cero si no se encuentra.WHERE A LIKE'%1%'
filtra a las filas donde A contiene un 1ORDER BY R
asegura que la tabla se lea de arriba hacia abajofuente
Delphi 122 caracteres
Suspiro ... es un lenguaje tan voluminoso.
Actualización: tuvo que agregar 6 caracteres al cambiar la función del tipo de retorno de I a entero. La función aún se compiló ya que el programa de prueba tenía un "tipo I = entero"; declaración sobrante de una versión anterior del programa.
fuente
"0000", "0010", "1111"
segundo lugar, su respuesta no cumple con el requisito de complejidad de tiempo linealesquema - 236 caracteres
Incluso más largo que la versión delphi ... probablemente haya una manera de hacerlo mucho más eficientemente con el esquema. Y lo que es peor: acabo de notar que es orden m * n.
l es una lista de la forma '((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1)). Creo que es una representación justa de una entrada de matriz 2D para el esquema.
(sl) suma los elementos n-ésimo de cada una de las sublistas de una lista de listas de números, entonces (s '((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1))) volvería (3 2 1 2).
(ul) devuelve el 'índice' de la entrada más grande de una lista de números (usando la función auxiliar t), por lo que (u '(3 2 1 2)) devolverá 1 (como el elemento más grande' 3 en la lista ' (3 2 1 2) está en la posición 1).
fuente
Raqueta 70
Golfizado:
Asume que la entrada es una matriz bidimensional, que en Racket sería una lista de listas:
Sin golf:
Devuelve el índice de la columna con el palo más largo.
fuente
1
's?1
en la matriz, o solo en la fila inferior).JavaScript, ES6, 76 caracteres
Toma una matriz de entrada de matriz.
fuente
JavaScript ES6, 65 bytes
Toma ambos formatos de entrada
Explicado:
Itera de abajo hacia arriba. Utiliza
String.prototype.indexOf()
oArray.prototype.indexOf()
depende de la entrada en cada valor. Encuentra el primer índice de cada fila con un 1 del desplazamiento anterior, si no encuentra ninguno, establece lat
variable en el último desplazamiento y no realiza másindexOf
llamadas.fuente
indexOf
funciona en cualquieraO(log n)
oO(n)
, por lo general el algoritmo nunca estará enO(m + n)
O(m+n)