Encontre o número com a maior soma de vizinhos

12

O desafio

Dada uma grade de números (10 <= N <= 99) Retorne o número com a soma mais alta dos quatro números adjacentes a ele; esses são os números acima, abaixo, direita e esquerda do número, mas não ele próprio.

  1. O número em si não conta, apenas seus quatro vizinhos.
  2. Um número na borda deve ser tratado como se o número ausente fosse um 0.
  3. Vou projetar o teste para evitar laços.
  4. Os números não se repetem.
  5. Isso é .

Exemplo

Dado

56 98 32 96
12 64 45 31
94 18 83 71

Retorna

18

Um teste real

Dado

98 95 67 66 57 16 40 94 84 37
87 14 19 34 83 99 97 78 50 36
18 44 29 47 21 86 24 15 91 61
60 41 51 26 10 58 11 62 55 71
42 85 56 12 46 81 93 65 49 77
89 13 74 39 54 76 92 33 82 90
96 88 70 79 80 28 25 20 75 68
38 63 17 72 53 48 73 30 45 69
64 35 32 31 23 43 22 52 27 59

Retorna

13

Dado

82 43 79 81 94 36 17 64 58
24 52 13 87 70 18 28 61 69
16 99 75 21 50 44 89 90 51
49 80 63 31 54 65 41 55 38
67 91 76 78 23 86 83 14 73
46 68 62 77 34 48 20 74 10
33 35 26 97 59 66 25 37 32
12 92 84 27 85 56 22 40 45
96 15 98 53 39 30 88 71 29
60 42 11 57 95 19 93 72 47

Retorna

15
Guarda-chuva
fonte
1
" Um número na aresta pode ser tratado como se o número ausente fosse um 0. " - Isso implica que temos uma escolha de como lidar com números em uma aresta da grade. Podemos, portanto, optar por contornar o outro lado da grade?
Shaggy
@ Shaggy No. Isso pode alterar o resultado esperado. Vamos todos fazer da mesma maneira. Texto atualizado s / can / should /
Umbrella
2
esperando a resposta inevitável do MATL
Fatalize
Percebo que a maioria das soluções modifica a entrada de alguma maneira. Isso é convencional aqui? Minha solução (ainda a ser publicada) inclui os bytes necessários para alterar a entrada e estou me perguntando por que muitos outros não.
Umbrella
1
@Umbrella Geralmente, não nos importamos se a entrada é modificada. Estamos interessados ​​em código curto, não em código limpo. Enquanto a saída estiver correta, tendemos a ser bastante permissivos.

Respostas:

9

MATL , 20 15 13 12 bytes

t1Y6Z+tuX>=)

Economizou 5 bytes graças a Emigna, 2 graças a Giuseppe e outro obrigado a Luis Mendo.
Experimente online!

Explicação

t1Y6Z+tuX>=)
t                  Duplicate the (implicit) input.
 1Y6               Push the array [0 1 0; 1 0 1; 0 1 0].
    Z+             Convolve with the input.
       uX>         Get the maximum unique element...
      t   =        ... and compare elementwise.
           )       Index into the input.

fonte
6

APL (Dyalog Unicode) , 31 27 26 24 23 bytes SBCS

-2 graças ao vacas charlatão. -1 graças a ngn.

Função de prefixo tácito anônimo. Toma uma matriz como argumento. Assume ⎕IO( I ndex O rigin) 0que é o padrão em muitos sistemas.

{⊃⍒,(+/--/)⊢∘,⌺3 3⊢⍵}⊃,

Experimente online!

, percorrer (achatar) a entrada

{}⊃ Escolha um elemento a partir dele de acordo com o resultado da seguinte função:

⊢⍵ produzir o argumento (separa 3 3de )

 … ⌺3 3 Aplique a seguinte função a cada bairro 3 por 3:

  ⊢∘, ignorar as informações de ponta em favor do bairro desarrumado (achatado)

  () Aplique a seguinte função tácita àqueles

   -/ a soma alternada (lit. associativo direito menos redução)

   +/- subtraia isso da soma (isso dá a soma de todos os outros elementos)

, passear (achatar) que (o bairro soma)

 produzir os índices que classificariam isso

 escolha a primeira (ou seja, o índice da soma mais alta)

Adão
fonte
Isso foi rápido. Você veio preparado? ;)
Umbrella
3
@Umbrella Não, eu apenas uso uma linguagem de programação que é rápida de programar.
Adám
3
Como é isso {⊃⍒,{+/1↓⍉4 2⍴⍵}⌺3 3⊢⍵}⊃,? Edit: or even{⊃⍒,{⊢/+⌿4 2⍴⍵}⌺3 3⊢⍵}⊃,
user41805
@ Cowquack Eu sempre esqueço esse truque.
Adám 20/06/19
2
-1 byte:{⊃⍒,(+/--/)⊢∘,⌺3 3⊢⍵}⊃,
ngn
5

Gelatina , 22 bytes

;€0ZṙØ+SṖ
,ZÇ€Z+$/ŒMœị

Experimente online!

Não ter built-ins de convolução como MATL e Dyalog Esquecer que seu idioma tem embutidos de convolução (obrigado @dylnan) dói, mas podemos ficar bem sem eles, parcialmente graças a ŒMe œị. Primeiro, uma função auxiliar para calcular vizinhos em apenas uma direção, que acidentalmente transpõe a entrada:

;€0Z         Append a zero to each row, then transpose.
    ṙØ+S     Rotate by +1 and −1 (Ø+ = [1,-1]) and sum these.
        Ṗ    Pop the last row.

Visualmente, o cálculo é:

1 2 3   ;€0   1 2 3 0   Z   1 4 7   ṙØ+     2 5 8   0 0 0     S   2  5  8   Ṗ   2  5  8
4 5 6  ————→  4 5 6 0  ——→  2 5 8  ————→  [ 3 6 9 , 1 4 7 ]  ——→  4 10 16  ——→  4 10 16
7 8 9         7 8 9 0       3 6 9           0 0 0   2 5 8         2  5  8       2  5  8
                            0 0 0           1 4 7   3 6 9         4 10 16

Interpretação: a célula (x, y) deste resultado é a soma dos vizinhos horizontais da célula (y, x). (Por exemplo, aqui vemos que f (A) [2,3] = 16 = 7 + 9 = A [3,1] + A [3,3] .)

Então, a principal função:

,ZÇ€            Pair the input with its transpose and apply helper to both.
    Z+$/        Fold by Z+, i.e., turn [X,Y] into transpose(X)+Y.
                Now we've summed the horizontal and vertical neighbors for each cell.
        ŒM      Find the 2D index of the maximal value.
          œị    2D-index (into the original input).
Lynn
fonte
1
Que tal æc?
dylnan
ah, eu não sabia disso :) Estou muito ocupado para jogar golfe, então fique à vontade para escrever uma resposta usando-o.
Lynn
5

Gelatina , 18 bytes

5BæcµḊṖ)
ZÇZ+ÇŒMœị

Experimente online!

A função auxiliar encontra os vizinhos de cada elemento em cada linha. A função principal faz isso nas linhas e as colunas encontram o elemento que possui a soma máxima da vizinhança.

5BæcµḊṖ)
5B           bin(5): 1,0,1
  æc         Convolve with [[1,2,9],[other rows]] (for example): [[1,2,10,2,9],...]
    µ        New chain.
       )     Apply this to each element:
     Ḋ       Remove the first element.
      Ṗ      Remove the last element.
             Gives [[2,10,2],...]

ZÇZ+ÇŒMœị   
Z            Zip the matrix
 Ç           Apply helper function
  Z          Zip again. Yields the sum of the vertical neighbors of each element.
   +         Add:
    Ç        The sum of each element's horizontal neighbors.
     ŒM      Find the multidimensional index of the maximal element.
       œị    Index back into the original matrix.
dylnan
fonte
2

Python 2 , 127 bytes

def f(a):n=len(a[0]);b=sum(a,[])+[0]*n;print b[max(range(len(b)-n),key=lambda i:b[i-1]*(i%n>0)+b[i+1]*(i%n<n-1)+b[i-n]+b[i+n])]

Experimente online!

Lynn
fonte
2

Estêncil , 1 + 10 = 11 bytes (não concorrente)

Opção de linha de comando:  1 computação 1 geração

y⊃⍨⊃⍒,
+/N

Experimente online!

y da entrada original nivelada,
⊃⍨ escolha
 a primeira
 em ordem decrescente
, da

+/ somas dos
N bairros de von neumanN sem ser

Adão
fonte
É claro que há uma linguagem com um personagem incorporada para os vizinhos.
Umbrella
1
Para ser justo, seu único objetivo é resolver esses tipos de problemas .
Adám 20/06/19
Por que não é competitivo?
Kevin Cruijssen
1
@KevinCruijssen Eu adicionei y ao idioma quando vi que ele precisava de acesso mais fácil à entrada original. Antes disso, você tinha que escrever em (,⍎'input')vez de y.
Adám
1
@ Adám Ah ok, sim, então de fato não é concorrente. Não tinha notado que o desafio foi publicado ontem. Se era um desafio antigo, não concorrente porque o idioma (ou versão do idioma) é mais recente não o torna mais não competitivo na meta atual .
Kevin Cruijssen
2

JavaScript (ES6), 94 bytes

a=>a.map(p=m=(r,y)=>p=r.map((v,x)=>(s=~r[x-1]+~p[x]+~(a[y+1]||0)[x]+~r[x+1])>m?v:(m=s,o=v)))|o

Experimente online!

Quão?

Em vez de procurar o máximo da soma dos 4 vizinhos, procuramos o m mínimo da soma s dos seus complementos únicos. Isso nos permite processar valores indefinidos como zeros, porque:

~undefined === -1
~0 === -1

O mapa interno () é escrito de tal forma que não altera o conteúdo da linha r . Portanto, podemos salvar seu resultado em p para testar os principais vizinhos na próxima iteração.

Nós usamos:

  • ~r[x-1] para a célula esquerda
  • ~r[x+1] para a célula certa
  • ~p[x] para a célula superior
  • ~(a[y+1]||0)[x] para a célula inferior
Arnauld
fonte
1

Java 8, 187 bytes

m->{int r=0,l=m.length,i=l,L,j,S=0,s;for(;i-->0;)for(L=j=m[i].length;j-->0;)if((s=(i<1?0:m[i-1][j])+(i<l-1?m[i+1][j]:0)+(j<1?0:m[i][j-1])+(j<L-1?m[i][j+1]:0))>S){S=s;r=m[i][j];}return r;}

Experimente online.

Explicação:

m->{                           // Method with integer-matrix parameter and integer return
  int r=0,                     //  Result-integer, starting at 0
      l=m.length,              //  Amount of rows
      i=l,                     //  Rows index integer
      L,                       //  Amount of columns
      j,                       //  Column index integer
      S=0,                     //  Largest sum of four cells
      s;                       //  Current sum of four cells
  for(;i-->0;)                 //  Loop over the rows
    for(L=j=m[i].length;j-->0;)//   Inner loop over the columns
      if((s=                   //    Set the current sum to: the sum of:
           (i<1?0:m[i-1][j])   //     Value of the cell to the left, or 0 if out of bounds
          +(i<l-1?m[i+1][j]:0) //     Value of the cell to the right, or 0 if out of bounds
          +(j<1?0:m[i][j-1])   //     Value of the cell down, or 0 if out of bounds
          +(j<L-1?m[i][j+1]:0))//     Value of the cell up, or 0 if out of bounds
         >S){                  //    If this current sum is larger than the largest sum:
        S=s;                   //     Replace the largest sum with this current sum
        r=m[i][j];}            //     And set the result to the current cell
  return r;}                   //  Return the result
Kevin Cruijssen
fonte
1

Javascript ES6, 170 bytes

c=g=>{s=0;n=0;f=m=>m||[];for(i=0;i<g.length;i++)for(j=0;j<g[i].length;j++){s=~~f(g[i-1])[j]+~~f(g[i+1])[j]+~~f(g[i])[j-1]+~~f(g[i])[j+1];b=s>n?g[i][j]+!(n=s):b;}return b}
Jean-Philippe Leclerc
fonte
1
Bem-vindo ao PPCG! Seu código parece assumir que a entrada está armazenada em uma variável chamada g , o que não é permitido . Você deve escrever um programa completo que leia a entrada ou uma função (que é geralmente e de longe a maneira preferida em JS).
Arnauld
1
@Arnauld Obrigado! Eu corrigi o código
Jean-Philippe Leclerc
Você pode adicionar um link TIO para facilitar o teste. (I removido o caso segundo teste para ter o ajuste link em um comentário.)
Arnauld