Você é um jovem nerd de programação que vive com seus outros 2 melhores amigos. Toda semana, um de vocês tem que fazer todas as tarefas da casa e decide quem é a vez de escolher um pedaço de pau. Quem escolhe o menor palito perde e faz todas as tarefas.
Como todos vocês são programadores e adoram criar quebra-cabeças, você modificou o "Escolha o menor bastão" em um quebra-cabeça de computador.
Aqui estão as regras do quebra-cabeça.
- Você receberá uma matriz 2D, onde cada coluna representa um bastão.
- Em cada coluna, 1 representa uma parte do manche e 0 é um espaço vazio
- Ao passar de cima para baixo em cada coluna, inicialmente você tem
0
e, assim que clicar em um1
, o stick é iniciado e o restante da coluna será preenchido1
apenas com - Você pode escrever seu programa para escolher uma coluna. O tamanho do stick nessa coluna determina o vencedor / perdedor. Tamanho do stick == número de 1s nessa coluna.
- No entanto, esse programa pode ter apenas uma complexidade linear no pior dos casos.
Como todos vocês são programadores, saberão se o programa de outra pessoa está gravando o limite de complexidade de tempo.
Seu trabalho é:
- Escreva um programa ou função que aceite entrada em formato 2D ou matriz de strings.
- A entrada pode ser obtida no STDIN / prompt / console ou em um argumento de função.
- Se você estiver lendo a entrada do STDIN / prompt, poderá presumir que a leitura da entrada e a conversão para uma matriz leva 0 tempo (mesmo que o código para fazê-lo precise estar presente na sua resposta)
- Determine a coluna com o bastão mais longo.
- A saída pode ser o valor de retorno da função ou para STDOUT / console / alerta.
- O programa / função deve ter complexidade linear de pior caso,
O(m+n)
ondem
é o número de linhas en
o número de colunas.
A entrada pode ser um dos seguintes formatos:
Matriz 2D:
[ [0, 0, 0, 0],
[1, 0, 0, 0],
[1, 1, 0, 1],
[1, 1, 1, 1] ]
Matriz de cordas:
[ "0000", "1000", "1101", "1111" ]
A entrada terá as seguintes propriedades:
- O tamanho da matriz é desconhecido, assuma um retângulo de qualquer tamanho
- Em qualquer coluna, de cima para baixo, se você vir 1, tudo abaixo será um
- Paus de colunas vazias (ou seja, comprimento 0) são permitidos.
Este é um código de golfe, portanto o código mais curto vence ! *
Por favor, explique seu código ou forneça a versão simples (para verificar a complexidade do tempo) junto com qual dos dois formatos de entrada você espera.
ATUALIZAÇÃO Complexidade de tempo linear aqui significa O (n + m) em que n é o tamanho da coluna e m é o tamanho da linha. (Para aqueles que não estavam claros)
ATUALIZAÇÃO 2 Isso definitivamente pode ser feito em tempo linear. E se você estiver postando uma resposta, fique à vontade para adiar a publicação da lógica / algoritmo por alguns dias para uma luta justa :)
ATUALIZAÇÃO 3 Vou analisar todas as respostas em algumas horas para validar a complexidade do tempo e o programa :)
fonte
1
na entrada é a última célula. é necessário ler toda a entrada. Mesmo que a biblioteca padrão de uma linguagem falsifique o acesso aleatório ao stdin, nos bastidores ela está armazenando buffer e, portanto, o tempo gasto é Omega (n * m).Respostas:
GolfScript, 45 caracteres
Recebe a entrada como uma matriz de seqüências de caracteres, retorna o índice (com base em 0) da coluna mais alta. Ele é executado nas iterações O ( linhas + colunas ), e cada iteração deve levar essencialmente tempo constante (pelo menos assumindo aritmética de tempo constante). As únicas operações de array / string executadas dentro do loop são pesquisas de elementos (
=
) e o comprimento de uma string (,
), ambas com tempo constante no GolfScript.Experimente online.
Explicação:
Como a maioria das soluções aqui, esse código funciona iniciando no canto inferior esquerdo da matriz, avançando para cima ou para a direita, dependendo se o elemento atual da matriz é 1 ou 0, e acompanhando a coluna onde foi movida pela última vez .
No início do programa, atribuo a matriz de entrada à variável
^
, seu comprimento (ou seja, o número de linhas)y
e de 0 ax
. O valor 0 também é deixado na pilha; durante o loop a seguir, ele será substituído pelo índice da coluna mais alta.No loop principal,
^y(=x=
extrai ox
caracterey-1
-th da linha -th em^
. Na verdade, isso retorna o código ASCII do caractere; portanto,2%
é necessário descartar tudo, exceto o último bit. Como um caso especial, se fory
igual a 0 (o que pode acontecer se a coluna mais alta encontrada até agora chegar até a linha superior), o bit procurado na verdade virá da última linha da matriz (índice -1), mas o seguintey*
força a zero, criando efetivamente uma linha virtual com todos os zeros na parte superior da matriz.A seguir,
if
será executado um dos dois blocos de código que o precede, dependendo se o bit pesquisado for diferente de zero (verdadeiro) ou zero (falso). Se diferente de zero,y
é decrementado por um, e o valor atual dex
substitui o índice de coluna mais alto da pilha (com o valor antigo temporariamente deixado em cima). Se zero,x
é simplesmente incrementado por um (e temporariamente deixado na pilha, no topo do índice de colunas mais alto).Por fim,
^0=
extrai a primeira linha da matriz,,
retorna seu comprimento e a<
compara com o índice da coluna temporariamente deixado na pilha (que será igualx
se apenas tiver sido incrementado). Se o índice for menor que o comprimento da linha, o loop repete.Ps. Com base nos meus testes, deve ser possível reduzir esse programa em um caractere, substituindo o teste de comprimento da string
,<
no final do loop por>
, que corta a string no índice especificado e retorna a parte final (que estará vazia e portanto, falso, no final do loop). No entanto, enquanto cortar uma string como essa parece ser implementado como uma operação de tempo constante no GolfScript (ou melhor, no Ruby, que o GolfScript executa sobre), não encontrei nenhuma documentação oficial dizendo isso. Apenas para garantir, escolhi a versão um pouco mais longa, mas definitivamente a versão O (1) acima.fonte
Ruby,
8375686663 bytesDefine uma função
f
que assume o formato de matriz 2D como entrada.fonte
Python
2-71, 69, 73, 7581fonte
i
sairá dos limites se um bastão ocupar uma coluna inteira?j
para contar de0
quebra a condição do loopi*j
.C, 64 bytes
Edit: eu aprendi que a pergunta pede a localização da coluna mais longa e não o seu comprimento.
A primeira linha é o código de golfe e o restante é a invocação de amostra.
fonte
int
s na assinatura da função por acaso ou isso não funciona devido aos ponteiros lá?C #: 236 caracteres
ungolfed:
fonte
PHP 5.4 - 108 bytes
(113 se você incluir o
<?php
)Formato de entrada: a matriz será lida como uma sequência JSON.
Espaço em branco adicionado para facilitar a leitura - todas as novas linhas e espaços à esquerda podem ser removidos.
Versão reduzida:
Tipo de roubar o algoritmo de Martin aqui, mas é bom brincar com linguagens que não são vistas com tanta frequência aqui XD
fonte
$s=json_decode($argv[1]);$t=count($s)-1;
por$t=count($s=json_decode($argv[1]))-1;
(-3 bytes).$t--
só aconteça se a condição for atendida.Cobra - 98
fonte
C ++ :: 78
Diferente da outra solução C, este é o programa inteiro. (nenhuma chamada é necessária, não há necessidade de informar à função o tamanho da matriz). Infelizmente, isso significa que é mais longo, pois
main
deve ser usado, em vez de um único nome de função de caractere. Tenho que interpretar a entrada e, em seguida, enviar a resposta, onde a outra solução lida com isso "em outro lugar". Também meu primeiro código de golfe.compilado com
g++ file.cpp -include iostream
, executado com./a 000 010 110 111
(por exemplo) == matriz de strings (acredito que isso seja permitido na pergunta)A versão acima gera o melhor atual encontrado até agora em cada iteração. O dígito final de saída é a resposta. A mudança do processamento da parte inferior esquerda em vez da parte inferior direita e a
0
indexação reduziram essa solução em 10 (!) Caracteres.mudar para c ++ reduz o envio de mais um caractere, pois
std::cout<<
é mais curtoputchar(-48)
e também deve suportar explicitamente mais de 9 varas com saída adequada (embora possa ser mais difícil diferenciar cada saída) Aremoção do campo de resposta e a saída cortam diretamente outros 6 caracteres. Agora, ele só produz a melhor corrente quando sobe, o que elimina, pelo menos, parte da produção.
O arquivo inteiro agora tem apenas 78 bytes de tamanho - aproximando-se da solução de função única que o outro
C
usos de envio. (com muito código extra para dar suporte à referida função).Como a descrição abaixo está desatualizada:
Posso jogar golfe ainda mais?
Código não jogado (com saída extra):
fonte
OCaml - 144 caracteres
Toma uma
int array array
entrada como e começa a partir de baixo à esquerda, movendo-se para cima ou para a direita se vir a1
ou a0
. A contagem de colunas começa em0
.Uso
Ungolfed
fonte
T-SQL -
7164Toma a tabela A como entrada
E a consulta é
SQLFiddle
Isso retorna a primeira linha da tabela a ordenada por r, onde existe um 1 na sequência a.
TOP(1)
restringe o resultado à primeira linha retornada.CHARINDEX('1',A)
retorna a posição do primeiro 1 na string ou zero se não for encontrado.WHERE A LIKE'%1%'
filtra para linhas onde A contém um 1ORDER BY R
garante que a tabela seja lida de cima para baixofonte
Delphi 122 chars
Suspiro ... é uma linguagem tão volumosa.
Atualização: teve que adicionar 6 caracteres na função de alteração do tipo de retorno de I para inteiro. A função ainda compilada como o programa de teste tinha um "tipo I = inteiro;" sobra de uma versão anterior do programa.
fonte
"0000", "0010", "1111"
Em segundo lugar, a sua resposta não está a cumprir o requisito de complexidade de tempo linearesquema - 236 caracteres
Ainda mais que a versão delphi ... provavelmente existe uma maneira de fazer isso de maneira muito mais eficiente com o esquema. E pior ainda - acabei de notar que é a ordem m * n.
l é uma lista da forma '((0 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1)). Eu acho que é uma representação justa de uma entrada de matriz 2D para o esquema.
(sl) soma os n-ésésimos elementos de cada uma das sub-listas de uma lista de listas de números, portanto (s '((0 0 0 0) (1 0 0 0) (1 0 0 0) (1 1 0 1) (1 1 1 1))) retornaria (3 2 1 2).
(ul) retorna o 'índice' da maior entrada de uma lista de números (usando a função auxiliar t), portanto (u '(3 2 1 2)) retornará 1 (como o maior elemento' 3 na lista ' (3 2 1 2) está na posição 1).
fonte
Raquete 70
Golfe:
Assume que a entrada é uma matriz bidimensional, que em Racket seria uma lista de listas:
Ungolfed:
Retorna o índice da coluna com o stick mais longo.
fonte
1
's?1
na matriz ou apenas na linha inferior).JavaScript, ES6, 76 caracteres
Toma matriz de entrada da matriz.
fonte
JavaScript ES6, 65 bytes
Toma ambos os formatos de entrada
Explicado:
Repete de baixo para cima. Usa
String.prototype.indexOf()
ouArray.prototype.indexOf()
depende da entrada em cada valor. Localiza o primeiro índice de cada linha com 1 do deslocamento anterior; se não encontrar nenhum, define at
variável para o último deslocamento e não realiza maisindexOf
chamadas.fonte
indexOf
funciona em qualquerO(log n)
ouO(n)
, então o algoritmo geral nunca estarão emO(m + n)
O(m+n)