Computar minimax de uma matriz

19

Considere uma matriz xcomo [1 5 3 4]e um número n, por exemplo 2. Escreve todas Length- nsubarrays deslizantes: [1 5], [5 3], [3 4]. Permita que o minimax da matriz seja definido como o mínimo dos máximos dos blocos deslizantes. Portanto, neste caso, seria o mínimo de 5, 5, 4, o que é 4.

Desafio

Dada uma matriz xe um número inteiro positivo n, produza o minimax conforme definido acima.

A matriz xconterá apenas números inteiros positivos. nsempre será no mínimo 1e no máximo o comprimento de x.

A computação pode ser feita por qualquer procedimento, não necessariamente como definido acima.

Código de golfe, menos bytes ganha.

Casos de teste

x, nresultado

[1 5 3 4], 2                    4
[1 2 3 4 5], 3                  3
[1 1 1 1 5], 4                  1
[5 42 3 23], 3                 42
Luis Mendo
fonte

Respostas:

19

Dyalog APL, 4 bytes

⌊/⌈/

Este é um trem de função monádico que espera matriz e número inteiro como argumentos da direita e da esquerda, respectivamente.

Experimente com o TryAPL .

Como funciona

Um trem de duas funções é o topo , o que significa que a correta é chamada primeiro (com os dois argumentos) e a esquerda é chamada em cima (com o resultado como argumento único).

Uma monádica f/simplesmente reduz seu argumento em f. No entanto, se chamado de forma diádica, f/é n-wise reduz e leva o tamanho da fatia como argumento à esquerda.

⌊/⌈/    Monadic function. Right argument: A (array). Left argument: n (list)

  ⌈/    N-wise reduce A by maximum, using slices of length n.
⌊/      Reduce the maxima by minimum.
Dennis
fonte
Espere ... Como você reduz algo que já foi reduzido? Não é apenas um elemento singular?
Cyoce 15/02
@Cyoce A redução N-wise produz uma matriz de máximos. Por exemplo, 2 ⌈/ 1 2 3 4calcula o máximo de (1 2) (2 3) (3 4), então ele retorna 2 3 4.
Dennis15 /
Está bem. Eu pensei que isso significava que um N-wise reduzir deu os primeiros N elementos e reduzi-los com a função, por exemplo, um 2-wise reduzir é apenas um normal, reduzir
Cyoce
Quantos bytes devem ser contados como? 1 ou 2?
Njpipeorgan
11
@njpipeorgan Isso depende da codificação. APL tem a sua própria página de código legado (que antecede Unicode por várias décadas), e codifica e como um único byte cada.
Dennis
7

CJam (11 bytes)

{ew::e>:e<}

Demonstração online

Peter Taylor
fonte
3
Um programa completo seria q~ew::e>:e<, que é também 11 bytes
GamrCorps
5

Ruby 39 bytes

->(x,n){x.each_slice(n).map(&:max).min}

Onde x é a matriz en é o número pelo qual ela deve ser dividida.

Ryantk
fonte
Não quer dizer each_cons?
Não que Charles
3

Pitão, 10 bytes

hSmeSd.:QE

Explicação:

           - autoassign Q = eval(input())
      .:QE -   sublists(Q, eval(input())) - all sublists of Q of length num
  meSd     -  [sorted(d)[-1] for d in ^]
hS         - sorted(^)[0]

Recebe entrada no formulário list newline int

Experimente aqui!

Ou execute um conjunto de testes!

Ou também 10 bytes

hSeCSR.:EE

Explicação:

      .:EE -    sublists(Q, eval(input())) - all sublists of Q of length num 
    SR     -   map(sorted, ^)
  eC       -  transpose(^)[-1]
hS         - sorted(^)[0]

Teste aqui

Azul
fonte
3

Oracle SQL 11.2, 261 bytes

SELECT MIN(m)FROM(SELECT MAX(a)OVER(ORDER BY i ROWS BETWEEN CURRENT ROW AND :2-1 FOLLOWING)m,SUM(1)OVER(ORDER BY i ROWS BETWEEN CURRENT ROW AND:2-1 FOLLOWING)c FROM(SELECT TRIM(COLUMN_VALUE)a,rownum i FROM XMLTABLE(('"'||REPLACE(:1,' ','","')||'"'))))WHERE:2=c;

Sem golfe

SELECT MIN(m)
FROM   (
         SELECT MAX(a)OVER(ORDER BY i ROWS BETWEEN CURRENT ROW AND :2-1 FOLLOWING)m,
                SUM(1)OVER(ORDER BY i ROWS BETWEEN CURRENT ROW AND :2-1 FOLLOWING)c
         FROM   (
                  SELECT TRIM(COLUMN_VALUE)a,rownum i 
                  FROM XMLTABLE(('"'||REPLACE(:1,' ','","')||'"'))
                )
       )
WHERE :2=c;
Jeto
fonte
2

MATL , 6 bytes

YCX>X<

Experimente online!

YC    % Implicitly input array and number. Build a matrix with columns formed
      % by sliding blocks of the array with size given by the number
X>    % maximum of each column
X<    % minimum of all maxima
Luis Mendo
fonte
2

Gelatina, 6 bytes

ṡ»/€«/

Experimente online!

Como funciona

ṡ»/€«/  Main link. Left input: A (list). Right input: n (integer)

ṡ       Split A into overlapping slices of length n.
 »/€    Reduce each slice by maximum.
    «/  Reduce the maxima by minimum.
Dennis
fonte
2

JavaScript (ES6), 84 83 72 bytes

(x,y)=>Math.min(...x.slice(y-1).map((a,i)=>Math.max(...x.slice(i,i+y))))

Agradecimentos a user81655 por ajudar a eliminar 11 bytes

Mwr247
fonte
Sendo tudo positivo:(x,y,M=Math.max)=>-M(...x.slice(y-1).map((a,i)=>-M(...x.slice(i,i+y))))
edc65 15/02
2

Julia, 51 bytes

f(x,n)=min([max(x[i-n+1:i]...)for i=m:endof(x)]...)

Nada muito inovador. Esta é uma função que aceita uma matriz e um número inteiro e retorna um número inteiro. Ele apenas usa o algoritmo básico. Seria muito mais curto se, mine maxnão exigisse, dividir matrizes em argumentos.

Obtemos cada sub-matriz sobreposta, obtemos o máximo e o mínimo do resultado.

Alex A.
fonte
2

Perl 6 , 32 bytes

{@^a.rotor($^b=>1-$b)».max.min}

Uso:

my &minimax = {@^a.rotor($^b=>1-$b)».max.min}

say minimax [1,5,3,4], 2;    # 4
say minimax [1,2,3,4,5], 3;  # 3
say minimax [1,1,1,1,5], 4;  # 1
say minimax [5,42,3,23], 3;  # 42
Brad Gilbert b2gills
fonte
2

R, 41 35 bytes

Requer que o zoo seja instalado.

function(x,n)min(zoo::rollmax(x,n))

editar - 6 bytes por zoo::rollmaxexistir!

mnel
fonte
2

J, 9 bytes

[:<./>./\

Semelhante à resposta da APL. >./\aplica-se >./(máximo) aos conjuntos (arg esquerdo) do arg direito. Em seguida, <./encontra o mínimo disso, pois está limitado [:.

Casos de teste

   f =: [:<./>./\
   2 f 1 5 3 4
4
   3 f 1 2 3 4 5
3
   3 f 1 1 1 1 5
1
   3 f 5 42 3 23
42
Conor O'Brien
fonte
1

Python 3, 55 bytes.

lambda x,n:min(max(x[b:b+n])for b in range(len(x)-n+1))

Casos de teste:

assert f([1, 5, 3, 4], 2) == 4
assert f([1, 2, 3, 4, 5], 3) == 3
assert f([1, 1, 1, 1, 5], 4) == 1
assert f([5, 42, 3, 23], 3 ) == 42
Morgan Thrapp
fonte
1

Python 2, 50 bytes

f=lambda l,n:l[n-1:]and min(max(l[:n]),f(l[1:],n))

Calcula recursivamente o mínimo de duas coisas: o máximo das primeiras nentradas e a função recursiva na lista com o primeiro elemento removido. Para um caso base da lista com menos de nelementos, fornece a lista vazia, que serve como infinito porque o Python 2 coloca as listas como maiores que os números.

xnor
fonte
1

JavaScript (ES6), 70 bytes

x=>n=>-M(...x.slice(n-1).map((_,i)=>-M(...x.slice(i,i+n)))),M=Math.max

Usando currying , esta função economiza 2 bytes da resposta anterior.

Demo

f=x=>n=>-M(...x.slice(n-1).map((_,i)=>-M(...x.slice(i,i+n)))),M=Math.max
a=[[[1,5,3,4],2,4],[[1,2,3,4,5],3,3],[[1,1,1,1,5],4,1],[[5,42,3,23],3,42]]
document.write(`<pre>${a.map(r=>`${f(r[0])(r[1])==r[2]?'PASS':'FAIL'} ${r[1]}=>${r[2]}`).join`\n`}`)

Patrick Roberts
fonte
1

Mathematica, 23 bytes

Min@BlockMap[Max,##,1]&

Caso de teste

%[{1,2,3,4,5},3]
(* 3 *)
njpipeorgan
fonte
1

Java 7, 128 126 124 bytes

int c(int[]x,int n){int i=-1,j,q,m=0;for(;i++<x.length-n;m=m<1|q<m?q:m)for(q=x[i],j=1;j<n;j++)q=x[i+j]>q?x[i+j]:q;return m;}

Ungolfed & código de teste:

Experimente aqui.

class M{
  static int c(int[] x, int n){
    int i = -1,
        j,
        q,
        m = 0;
    for(; i++ < x.length - n; m = m < 1 | q < m
                                           ? q
                                           : m){
      for(q = x[i], j = 1; j < n; j++){
        q = x[i+j] > q
             ? x[i+j]
             : q;
      }
    }
    return m;
  }

  public static void main(String[] a){
    System.out.println(c(new int[]{ 1, 5, 3, 4 }, 2));
    System.out.println(c(new int[]{ 1, 2, 3, 4, 5 }, 3));
    System.out.println(c(new int[]{ 1, 1, 1, 1, 5 }, 4));
    System.out.println(c(new int[]{ 5, 42, 3, 23 }, 3));
  }
}

Resultado:

4
3
1
42
Kevin Cruijssen
fonte
1

Raquete 84 bytes

(λ(l i)(apply min(for/list((j(-(length l)(- i 1))))(apply max(take(drop l j) i)))))

Ungolfed:

(define f
  (λ (l i)
    (apply min (for/list ((j (- (length l)
                                (- i 1))))
                 (apply max (take (drop l j) i))
                 ))))

Teste:

(f '[1 5 3 4]  2)
(f '[1 2 3 4 5] 3)
(f '[5 42 3 23] 3)

Resultado:

4
3
42
rnso
fonte
1

Clojure, 51 bytes

#(apply min(for[p(partition %2 1 %)](apply max p)))
NikoNyrh
fonte
1

SmileBASIC, 68 bytes

M=MAX(X)DIM T[N]FOR I=.TO LEN(X)-N-1COPY T,X,I,N
M=MIN(M,MAX(T))NEXT

Nada de especial aqui. As entradas são X[]eN

12Me21
fonte