Elige el palo más largo

13

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.

  1. Se le dará una matriz 2D, donde cada columna representa un palo.
  2. En cada columna, 1 representa una porción del palo y 0 es un espacio vacío
  3. Al ir de arriba a abajo en cada columna, inicialmente tienes 0una y tan pronto como tocas un 1, el palo ha comenzado y el resto de la columna se llenará con 1solo
  4. 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.
  5. 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)donde mes el número de filas y nel 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 :)

Optimizador
fuente
2
Yo diría que esto no se puede hacer en O (n + m), ya que cada celda podría contener el valor crucial (es decir, el primer "1" del palo / columna más largo). Por lo tanto, debe mirar cada celda, que toma O (n * m).
Falko
¿Podría haber columnas vacías?
Martin Ender
@Optimizer: Oh, ya veo. Tienes razón. :)
Falko
11
No se puede hacer en O (n + m). Una vez que la entrada se ha convertido a un formato que permite el acceso aleatorio, el procesamiento restante puede ser O (n + m), pero es necesario escribir un programa, y ​​en el peor de los casos, el único 1en 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).
Peter Taylor
2
Si desea permitir que las personas " simplemente hagan una función que acepte una matriz ", la pregunta no debe indicar que deben escribir un programa. Y si necesita soluciones que están en O (N ^ 0.5) donde N es el tamaño de la entrada, no debe pedir soluciones de tiempo lineal. Una solución de tiempo lineal puede leer la entrada completa.
Peter Taylor

Respuestas:

4

GolfScript, 45 caracteres

:^,:y;0:x{^y(=x=2%y*{y(:y;x\}{x):x}if^0=,<}do

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) yy 0 a x. 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 el xcarácter -th de la y-1fila -th en ^. En realidad, esto devuelve el código ASCII del personaje, por lo que 2%es necesario descartar todo menos el último bit. Como un caso especial, si yes 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 lo y*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, yse reduce en uno, y el valor actual de xreemplaza el índice de columna más alto en la pila (con el valor anterior temporalmente dejado encima). Si es cero, xsimplemente 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á igual xsi solo se incrementara) Si el índice es menor que la longitud de la fila, el bucle se repite

PD. 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.

Ilmari Karonen
fuente
6

Ruby, 83 75 68 66 63 bytes

f=->m{m[b=c=i=0].map{(c=i;b-=1)while(r=m[b-2])&&r[i]>0;i+=1};c}

Define una función fque toma la forma de matriz 2D como entrada.

Estoy comenzando en la parte inferior izquierda, haciendo un seguimiento de la longitud máxima del palo (en realidad, menos eso) y la columna correspondiente. En cada columna, si todavía hay 1s por encima de la longitud máxima del palo anterior, subo el palo hasta el final y recuerdo la nueva longitud y columna máximas. Eso significa que estoy iterando una vez a lo largo de las columnas y como máximo una vez a lo largo de las filas (específicamente estoy iterando hasta la longitud máxima del palo), que es precisamente O(m+n).

Martin Ender
fuente
@Optimizer No vi su segunda edición hasta después de que la publiqué, por lo que estaba en el historial de edición de todos modos. Es por eso que lo puse en un spoiler para las personas que quieren resolverlo ellos mismos.
Martin Ender
4

Python 2 - 71, 69, 73, 75 81

j=i=-1
M=input()
for m in M[0]:
 j+=1
 while-i<len(M)and M[i][j]:i-=1;J=j
print J
Falko
fuente
¿Está destinado a ejecutarse en Python 2 o 3? ¿Cómo se supone que debe verse la entrada?
Feersum
1
@feersum Python 2, la matriz de matrices.
Justin
@feersum: Quincunx tiene razón. La entrada es una matriz 2D de entradas, como usted sugirió.
Falko
¿No ise saldrá de los límites si un palo ocupa una columna completa?
xnor
1
Lo sentimos, pero parece que cambiar jpara contar desde 0rompe la condición del bucle i*j.
xnor
2

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.

g(int m,int n,int**a,int*r){for(*r=n;n*m;a[m][n]?m--,*r=n:--n);}

/* usage:
    m = number of rows
    n = number of columns
    a = 1-based 2D array such that a[i][j] gives the value at the ith row and jth column
    r = address of return value 
    Returns (to r) the 1-indexed location of a column with the longest length, or 0 if n=0
    */

int main()
{
    int flat[4*4] = {1, 0, 0, 0,
                     1, 0, 0, 1,
                     1, 1, 0, 1,
                     1, 1, 1, 1};
    int*twoD[4] = {flat-1,flat+3,flat+7,flat+11};
    int ret;
    g(4,4,twoD-1,&ret);
    printf("%d", ret);
    return 0;
}

// old function which determines longest length (65 bytes)
f(int m,int n,int**a,int*r){for(*r=m;n*m;a[m][n]?m--:--n);*r-=m;}
Feersum
fuente
¡Impresionante! ¿Puede deshacerse de los ints en la firma de la función por casualidad o no funciona debido a los punteros allí?
Martin Ender
1
La entrada solo debe contener la matriz. No puede decirle al programa sobre el tamaño de la matriz.
Optimizador
Espera, ¿eso realmente funciona? Esto parece devolver la longitud del palo más largo y no su posición: ideone.com/YEzqzl
Martin Ender
2
@Optimizer que es básicamente imposible en C.
Martin Ender
Podría ser, pero esa es la pregunta :)
Optimizer
2

C #: 236 caracteres

int p(int[,] a){int y=0,s=0,i=0,x;for(;++y<=a.GetUpperBound(0);)for(x=i;x<=a.GetUpperBound(1);){if(a[y,x++]==0)break;s=y;i++;}return s;}

sin golf:

int p(int[,] a)
{
    int selectedRow=0;
    int maxLength=0;
    for(var y = 0; y<=a.GetUpperBound(0); y++)
        for(var x=maxLength; x<=a.GetUpperBound(1); x++)
        {
            if(a[y,x++]==0)
                break;
            selectedRow=y;
            maxLength++;
        }
    return selectedRow;
}
Stephan Schinkel
fuente
2

PHP 5.4 - 108 bytes

(113 si incluye el <?php )

Formato de entrada: la matriz se leerá como una cadena JSON.

php longest_stick.php "[[0, 0, 0, 0],[1, 0, 0, 0],[1, 1, 0, 1],[1, 1, 1, 1]]"

Se agregaron espacios en blanco para facilitar la lectura: se pueden eliminar todas las líneas nuevas y espacios iniciales

<?php
$t=count($s=json_decode($argv[1]))-1;
foreach($s[0] as $k=>$_)
    while($s[$t][$k]) {
        $t--;
        $l = $k;
    }
echo $l?:0;

Versión minimizada:

<?php $t=count($s=json_decode($argv[1]))-1;foreach($s[0] as $k=>$_)while($s[$t][$k]){$t--;$l=$k;}echo $l?:0;

Es como robar el algoritmo de Martin aquí, pero es bueno jugar con lenguajes que no se ven con tanta frecuencia aquí XD

Niet the Dark Absol
fuente
@ MartinBüttner He "robado" su algoritmo, por lo que debería ser O (n + m) ahora. Creo que es correcto XD
Niet the Dark Absol
Puede reemplazar $s=json_decode($argv[1]);$t=count($s)-1;con $t=count($s=json_decode($argv[1]))-1;(-3 bytes).
Blackhole
@Blackhole De hecho puedes. ¡Gracias!
Niet the Dark Absol
@Blackhole Creo que eso rompería la funcionalidad. Realizará las tareas incluso si no se cumple la condición.
Niet the Dark Absol
@Blackhole Todavía lo rompe, me temo que XD $t--solo debe suceder si se cumple la condición.
Niet the Dark Absol
2

Cobra - 98

def f(a)
    s,x,y=0,0,a.count-1
    while y+1and x<a[0].count
        while a[y][x],y,s=y-1,x
        x+=1
    print s
Οurous
fuente
2

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 maindebe 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)

int c;main(int r,char**v){for(r--;r*v[r][c];v[r][c]-48?std::cout<<c,r--:++c);}

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 0indexació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 corto putchar(-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 otroCpresentació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:

ces global, por lo que se inicializa con 0
res el número de entradas (filas) +1 (nombre del programa)
ves la matriz de cadenas v[0]que no es válida (nombre del programa)
Como está indexado 0, restá fuera de límites, por lo tanto, disminuya.
Si bien r!=0(apuntando a una cadena válida) y el carácter cen la cadena no es el terminador nulo '\0'
si el carácter no es '0',
suba una fila ( r) y muestre la columna ( c)
o vaya a la siguiente columna ( c)

hecho

¿Puedo incluso golf esto más lejos?

Código no protegido (con salida adicional):

#include <stdio.h>
#include <string.h>

int main(int argc, char* argv[])
{
  int rows = argc-1;
  int cols = strlen(argv[1]);
  int ans;

  printf("rows: %d, cols: %d\n",rows, cols);

  while((rows)&&cols)
  {
    if (argv[rows][cols-1]-'0')
    {
      printf("stick @%d,%d\n",cols,rows);
      ans = cols;
      rows--;
    }
    else
    {
      printf("no stick @%d,%d\n",cols,rows);
      cols--;
    }
  }
  printf("%d",ans);
}
Utiliza la longitud de las cadenas para encontrar el número de columnas y argc para encontrar el número de filas. Comenzando en la esquina inferior derecha, sigue estas reglas simples: si la celda es un palo, luego sube, configura la respuesta a la columna actual. Si la celda no es un palo, entonces muévase hacia la izquierda. O (n + m): como solo se mueve hacia arriba y hacia la izquierda, solo puede tener lecturas máximas de n + m. Sale temprano si se cae de la parte superior o izquierda de la matriz.

Baldrickk
fuente
1

OCaml - 144 caracteres

let s a=Array.(let rec f i j m=if i=0then m else if a.(i).(j)=0then if j=length a.(i)-1then m else f i(j+1)m else f(i-1)j j in f(length a-1)0 0)

Toma una int array arrayentrada como, y comienza desde abajo a la izquierda, moviéndose hacia arriba o hacia la derecha si ve a 1o a 0. El recuento de columnas comienza en 0.

Uso

 s [| [| 0; 0; 0; 0 |]; [| 0; 0; 1; 0|]; [| 1; 0; 1; 0 |]; [| 1; 1; 1; 0 |]; [| 1; 1; 1; 1 |] |];;
 - : int = 2

Sin golf

let s a = Array.(
  let rec f i j m = (* m is the longest stick seen so far *)
    if i=0 then m (* A column is full: this is the longest possible stick and j=m anyway *)
    else if a.(i).(j)=0 then (* current column is shorter than a previously seen stick *)
      if j=length a.(i)-1 then m (* we have examined all columns, just return m *)
      else f i(j+1) m (* start examining next column *)
    else f (i-1) j j (* current column is longer than all the ones previously seen. Check how long the stick is *)
  in
  f (length a-1) 0 0)
Virgile
fuente
0

T-SQL - 71 64

Toma la tabla A como entrada

SELECT IDENTITY(INT, 1, 1) R, A INTO A
FROM (VALUES
 ('0000')
,('1000')
,('1101')
,('1111')
) AS A(A)

Y la consulta es

SELECT TOP(1)CHARINDEX('1',A)FROM A WHERE A LIKE'%1%' ORDER BY R

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 1

ORDER BY R asegura que la tabla se lea de arriba hacia abajo

MickyT
fuente
¿Puedes explicar qué está pasando en ese código? : D Sin experiencia con T-SQL
Optimizer
Ya veo, ¿entonces el filtrado en cada fila no es una operación O (n * m)? es decir, no la complejidad del tiempo lineal.
Optimizador
Dificil de decir. El motor SQL verificará todas las filas para un 1 en la columna. Solo devolverá la primera fila de arriba hacia abajo que califique. Entonces, en esta situación, escanea toda la tabla. Filtra las filas con la columna que contiene 1. Ordena los resultados en la columna de identidad y devuelve el primer resultado.
MickyT
Míralo así: ¿Qué pasa si tus filas son como "0000", "0000", "0000", "0001"? En este caso, tendrá que ir hasta la última fila y hasta el último carácter de la fila para descubrir la presencia de 1
Optimizer
1
Entonces sí, es O (m * n) entonces :)
Optimizer
0

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.

function S(A:array of string):integer;var n,c:integer;begin n:=0; repeat c:=Pos('1',A[n]);inc(n) until c>0; result:=c;end;
Penguino
fuente
¿Está haciendo la llamada Pos () en cada fila (en su caso, cadena) de la matriz?
Optimizador
@Optimiser Sí, el programa busca cada cadena en la matriz (usando 'inc (n)') hasta que encuentra un '1'. El primer '1' encontrado será el más alto (o igual más alto) '1', por lo que su posición en la cadena (las cadenas están indexadas en delphi) será la posición de la columna más larga. La rutina falla si no hay '1' en la matriz, pero creo que esto sería una entrada rota ya que entonces no se encontraría un "palo más largo".
Penguino
1
Entonces, en primer lugar, esta es una entrada válida: en "0000", "0010", "1111"segundo lugar, su respuesta no cumple con el requisito de complejidad de tiempo lineal
Optimizer
@Optimizer Sí, eso sería una entrada válida e identifica correctamente el tercer palo. Pero me di cuenta después de hacer la publicación que había convertido mi programa N de orden válido que usaba matrices, en un programa N ^ 2 de orden no válido que usaba cadenas (persiguiendo una reducción de ~ 160 caracteres).
Penguino
0

esquema - 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.

(define (s l) (cond ((eq? (cdr l) '()) (car l)) (else (map + (car l) (s (cdr l)))))) (define (u l) (define (t n p q l) (cond ((eq? l '()) p) ((< n (car l)) (t (car l) q (+ 1 q) (cdr l))) (else (t n p (+ 1 q) (cdr l))))) (t 0 0 1 (s l)))

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

Penguino
fuente
Sumar todas las sublistas es una operación O (m * n).
Martin Ender
0

Raqueta 70

Golfizado:

(define(h m)(for/last([r m]#:final(memv 1 r))(length(takef r even?))))

Asume que la entrada es una matriz bidimensional, que en Racket sería una lista de listas:

(define m 
  '((0 0 0 0)
    (1 0 0 0)
    (1 1 0 1)
    (1 1 1 1)))

Sin golf:

(define (h m)
  ;; step through rows, stopping at the first that contains a 1
  (for/last ([r m] #:final (memv 1 r)) 
    (length (takef r even?)))) ; pop off the leading zeroes to get the column index

Devuelve el índice de la columna con el palo más largo.

Matthew Butterick
fuente
Entonces, ¿básicamente estás revisando cada columna y contando el número de 1's?
Optimizador
Te entiendo. Algoritmo actualizado.
Matthew Butterick
Esto todavía tiene una complejidad en el peor de los casos de O (m * n) (para el caso en el que no hay 1en la matriz, o solo en la fila inferior).
Martin Ender
0

JavaScript, ES6, 76 caracteres

W=a=>(j=>{for(k=i=a.length-1;~i&~j;)a[i][j]?(k=j,i--):j--})(a[0].length-1)|k

Toma una matriz de entrada de matriz.

Optimizador
fuente
0

JavaScript ES6, 65 bytes

Toma ambos formatos de entrada

f=(a,t)=>a.reduceRight((p,c)=>t+1?t:(x=c.indexOf(1,p))+1?x:t=p,0)

Explicado:

Itera de abajo hacia arriba. Utiliza String.prototype.indexOf()o Array.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 la tvariable en el último desplazamiento y no realiza más indexOfllamadas.

George Reith
fuente
indexOffunciona en cualquiera O(log n)o O(n), por lo general el algoritmo nunca estará enO(m + n)
Optimizador de
@Optimizer Yeah se dio cuenta de que era O (m * n) no estaba pensando con claridad.
George Reith
@Optimizer actualizado para serO(m+n)
George Reith