Vous êtes un jeune geek de la programmation vivant avec vos 2 autres meilleurs amis. Chaque semaine, l'un de vous doit faire toutes les tâches de la maison et vous décidez à qui il revient en choisissant un bâton. Celui qui choisit le bâton le plus court perd et fait toutes les tâches.

Comme vous êtes tous programmeurs et adorez créer des puzzles, vous avez modifié le "Choisissez le bâton le plus court" en un puzzle informatique.

Voici les règles du puzzle.

1. Vous recevrez une matrice 2D, où chaque colonne représente un bâton.
2. Dans chaque colonne, 1 représente une partie du stick et 0 est un espace vide
3. Lorsque vous allez de haut en bas dans chaque colonne, vous en avez au départ 0et dès que vous appuyez sur un 1, le bâton a commencé et le reste de la colonne sera rempli de1 seulement
4. Vous pouvez écrire votre programme pour choisir une colonne. La taille du bâton dans cette colonne détermine le gagnant / perdant. Taille du bâton == nombre de 1 dans cette colonne.
5. Cependant, ce programme ne peut avoir qu'une complexité temporelle linéaire dans le pire des cas.

Comme vous êtes tous programmeurs, vous saurez si le programme de quelqu'un d'autre tire sur la limite de complexité temporelle.

Votre travail consiste à:

• Écrivez un programme ou une fonction qui accepte une entrée au format 2D ou dans un tableau de chaînes.
• L'entrée peut être prise à partir de STDIN / prompt / console ou d'un argument de fonction.
• Si vous lisez l'entrée de STDIN / prompt, vous pouvez supposer que la lecture de l'entrée et sa conversion en un tableau prend 0 fois (même si le code pour le faire doit être là dans votre réponse)
• Déterminez la colonne avec le bâton le plus long.
• La sortie peut être la valeur de retour de la fonction ou STDOUT / console / alert.
• Le programme / fonction doit avoir une complexité temporelle linéaire dans le pire des cas, O(m+n)où mest le nombre de lignes et nle nombre de colonnes.

L'entrée peut être l'un des formats suivants:

Tableau 2D:

[ [0, 0, 0, 0],
  [1, 0, 0, 0],
  [1, 1, 0, 1],
  [1, 1, 1, 1] ]

Tableau de cordes:

[ "0000", "1000", "1101", "1111" ]

L'entrée aura les propriétés suivantes:

• La taille du tableau est inconnue, supposez un rectangle de n'importe quelle taille
• Dans n'importe quelle colonne, venant de haut en bas, si vous voyez un 1, alors tout ce qui suit sera un
• Les colonnes vides (c'est-à-dire de longueur 0) sont autorisées.

Ceci est un code-golf donc le code le plus court gagne ! *

Veuillez expliquer votre code ou donner la version non golfée (pour vérifier la complexité temporelle) ainsi que le format d'entrée que vous attendez.

MISE À JOUR La complexité temporelle linéaire signifie ici O (n + m) où n est la taille de la colonne et m est la taille de la ligne. (Pour ceux qui n'étaient pas clairs)

MISE À JOUR 2 Cela peut certainement être fait en temps linéaire. Et si vous postez une réponse, n'hésitez pas à retarder la publication de la logique / algorithme de quelques jours pour un combat équitable :)

MISE À JOUR 3 Je vais passer en revue toutes les réponses dans quelques heures pour valider la complexité du temps et le programme :)

GolfScript, 45 caractères

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

Prend l'entrée comme un tableau de chaînes, retourne l'index (basé sur 0) de la colonne la plus haute. Il s'exécute en O ( lignes + colonnes ), et chaque itération doit prendre un temps essentiellement constant (au moins en supposant une arithmétique à temps constant). Les seules opérations de tableau / chaîne effectuées dans la boucle sont les recherches d'élément ( =) et la longueur d'une chaîne ( ,), qui prennent toutes deux un temps constant dans GolfScript.

Essayez-le en ligne.

Explication:

Comme la plupart des solutions ici, ce code fonctionne en commençant dans le coin inférieur gauche de la matrice, en remontant ou à droite selon que l'élément actuel de la matrice est 1 ou 0, et en gardant une trace de la colonne où il s'est déplacé pour la dernière fois. .

Au début du programme, j'affecte le tableau d'entrée à la variable ^, sa longueur (c'est-à-dire le nombre de lignes) à y, et 0 à x. La valeur 0 est également laissée sur la pile; lors de la boucle suivante, il sera remplacé par l'index de la colonne la plus haute.

Dans la boucle principale, ^y(=x=extrait le x-ème caractère de la y-1-ème ligne de ^. Cela renvoie en fait le code ASCII du caractère, il 2%est donc nécessaire de supprimer tout sauf le dernier bit. Dans un cas particulier, si yégal à 0 (ce qui peut arriver si la colonne la plus haute trouvée jusqu'à présent atteint la ligne supérieure), le bit recherché proviendra en fait de la dernière ligne de la matrice (indice -1), mais ce qui suit le y*force à zéro, créant ainsi efficacement une ligne de zéros virtuels en haut de la matrice.

Ce qui suit ifexécutera ensuite l'un des deux blocs de code qui le précèdent, selon que le bit recherché est non nul (vrai) ou zéro (faux). Si différent de zéro, il yest décrémenté de un et la valeur actuelle de xremplace l'index de colonne le plus haut de la pile (l'ancienne valeur étant temporairement laissée au-dessus). Si zéro, il xest simplement incrémenté de un (et temporairement laissé sur la pile, au-dessus de l'index de colonne le plus haut).

Enfin, ^0=extrait la première ligne de la matrice, ,retourne sa longueur et la <compare à l'index de colonne temporairement laissé sur la pile (qui sera égal xs'il vient d'être incrémenté). Si l'index est inférieur à la longueur de la ligne, la boucle répète.

Ps. Sur la base de mes tests, il devrait être possible de raccourcir ce programme d'un caractère en remplaçant le test de longueur de chaîne ,<à la fin de la boucle par >, qui coupe la chaîne à l'index donné et renvoie la partie de fin (qui sera vide, et donc faux, en fin de boucle). Cependant, alors que couper une chaîne comme celle-ci semble être implémenté comme une opération à temps constant dans GolfScript (ou, plutôt, dans Ruby, sur lequel GolfScript s'exécute), je n'ai trouvé aucune documentation officielle le disant. Juste pour être sûr, j'ai choisi de proposer la version légèrement plus longue, mais certainement O (1) ci-dessus.

Rubis, 83 75 68 66 63 octets

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

Définit une fonction fqui prend la forme du tableau 2D en entrée.

Je commence en bas à gauche, en gardant une trace de la longueur maximale du bâton (en fait, moins cela) et de la colonne correspondante. Dans chaque colonne, s'il y a encore des 1s au-dessus de la longueur maximale précédente du bâton, je monte le bâton jusqu'à la fin et je me souviens de la nouvelle longueur maximale et de la nouvelle colonne. Cela signifie que j'itère une fois le long des colonnes et au plus une fois le long des lignes (en particulier j'itère jusqu'à la longueur maximale du bâton), ce qui est précisément O(m+n).

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

C, 64 octets

Edit: j'ai appris que la question demande l'emplacement de la colonne la plus longue et non sa longueur.

La première ligne est le code joué et le reste est l'exemple d'invocation.

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

C #: 236 caractères

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

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

PHP 5,4 - 108 octets

(113 si vous incluez le <?php )

Format d'entrée: le tableau sera lu comme une chaîne JSON.

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

Espace blanc ajouté pour plus de lisibilité - tous les retours à la ligne et les espaces de tête peuvent être supprimés.

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

Version réduite:

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

Un peu de voler l'algorithme de Martin ici, mais c'est agréable de jouer avec des langages qui ne sont pas aussi souvent vus ici XD

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

C ++ :: 78

Contrairement à l'autre solution C, il s'agit de l'ensemble du programme. (aucune invocation nécessaire, pas besoin d'indiquer à la fonction la taille du tableau). Malheureusement, cela signifie qu'il est plus long car il maindoit être utilisé à la place d'un nom de fonction à un seul caractère, je dois interpréter l'entrée et ensuite sortir la réponse, où l'autre solution gère cela "ailleurs". Aussi mon premier golf de code.
compilé avec g++ file.cpp -include iostream, exécuté avec ./a 000 010 110 111(par exemple) == tableau de chaînes (je crois que cela est autorisé dans la spécification de la question)

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

La version ci-dessus affiche le meilleur courant trouvé jusqu'à présent à chaque itération. Le dernier chiffre de sortie est la réponse. Le passage du traitement du bas à gauche au lieu du bas à droite et l' 0indexation ont réduit cette solution de 10 (!) Caractères.
le passage à c ++ supprime la soumission d'un caractère de plus car il std::cout<<est plus court que putchar(-48)et il devrait également prendre en charge explicitement plus de 9 sticks avec une sortie appropriée (bien qu'il puisse être plus difficile de différencier chaque sortie)
. Il ne produit désormais le meilleur courant que lorsqu'il monte, ce qui coupe au moins une sortie.
La taille du fichier entier n'est plus que de 78 octets - approche de la seule solution de fonction que l'autreCutilisations de la soumission. (avec beaucoup de code supplémentaire pour supporter ladite fonction).

Comme la description ci-dessous est obsolète:

cest global donc est initialisé avec 0
rest le nombre d'entrées (lignes) +1 (nom du programme)
vest le tableau de chaînes avec v[0]invalide (nom du programme)
Comme il est 0 indexé, rest hors limites, décrémentez donc.
Tandis que r!=0(pointant vers une chaîne valide) et que le caractère cde la chaîne n'est pas le terminateur nul '\0'
si le caractère n'est pas '0',
montez une ligne ( r) et sortez la colonne ( c)
sinon passez à la colonne suivante ( c)

fait

Puis-je même jouer au golf plus loin?

Code non golfé (avec sortie supplémentaire):

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

Il utilise la longueur des chaînes pour connaître le nombre de colonnes et argc pour trouver le nombre de lignes. Commençant dans le coin inférieur droit, il suit ces règles simples: Si la cellule est un bâton, remontez, définissez la réponse à la colonne actuelle. Si la cellule n'est pas un bâton, déplacez-vous vers la gauche. O (n + m): comme il ne se déplace que vers le haut et vers la gauche, il ne peut avoir que max n + m lectures. Il se termine tôt s'il tombe du haut ou de la gauche du tableau.

OCaml - 144 caractères

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)

Prend une int array arrayentrée et commence en bas à gauche, en se déplaçant vers le haut ou vers la droite s'il voit un 1ou un 0. Le nombre de colonnes commence à 0.

Usage

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

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

T-SQL - 71 64

Prend la table A comme entrée

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

Et la requête est

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

SQLFiddle

Cela renvoie la première ligne de la table a ordonnée par r où il y a un 1 dans la chaîne a.

TOP(1) limite le résultat à la première ligne renvoyée.

CHARINDEX('1',A) renvoie la position du premier 1 de la chaîne ou zéro s'il n'est pas trouvé.

WHERE A LIKE'%1%' filtre les lignes où A contient un 1

ORDER BY R assure la lecture du tableau de haut en bas

Delphi 122 caractères

Soupir ... c'est une langue tellement volumineuse.

Mise à jour: a dû ajouter 6 caractères en changeant de fonction le type de retour de I en entier. La fonction était toujours compilée car le programme de test avait un "type I = entier;" laissée par une version antérieure du programme.

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;

schéma - 236 caractères

Encore plus longtemps que la version delphi ... il y a probablement un moyen de le faire beaucoup plus efficacement avec le schéma. Et pire encore - je viens de remarquer que c'est l'ordre 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 est une liste de la forme '((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1)). Je pense que c'est une représentation juste d'une entrée de tableau 2D pour le schéma.

(sl) additionne les n-èmes éléments de chacune des sous-listes d'une liste de listes de nuimbres, donc (s '((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1))) reviendrait (3 2 1 2).

(ul) renvoie l''index 'de la plus grande entrée d'une liste de nombres (en utilisant la fonction d'assistance t), donc (u' (3 2 1 2)) renverra 1 (comme le plus grand élément '3 de la liste' (3 2 1 2) est en position 1).

Raquette 70

Golfé:

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

Suppose que l'entrée est un tableau à deux dimensions, qui dans Racket serait une liste de listes:

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

Non 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

Renvoie l'index de colonne avec le bâton le plus long.

JavaScript, ES6, 76 characters

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

Takes array of array input.

JavaScript ES6, 65 bytes

Takes both input formats

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

Explained:

Iterates from bottom to top. Uses String.prototype.indexOf() or Array.prototype.indexOf() depending on the input on each value. Finds the first index of each row with a 1 from the previous offset, if it finds none then it sets the t variable to the last offset and doesn't perform anymore indexOf calls.