Resolver el problema del secretario

13

El problema del secretario es un famoso problema descrito de la siguiente manera:

  1. Necesitas una nueva secretaria
  2. Tienes N solicitantes que puedes entrevistar uno a la vez
  3. Puede calificar a cada solicitante después de la entrevista. Su sistema de puntaje nunca le dará a dos solicitantes el mismo puntaje
  4. Después de entrevistar a un solicitante, debe dar un "sí" o un "no" inmediatos.
  5. Quieres al solicitante con la puntuación más alta

La solución es entrevistar a los primeros floor(N/e)solicitantes y luego aceptar al primer solicitante que tenga una puntuación más alta que todos los solicitantes anteriores. Si ninguno de los solicitantes es superior, devuelva el último solicitante. Curiosamente, esto le da al solicitante principal el 1/eporcentaje del tiempo. ese refiere al número de Euler . Para obtener el valor de e, puede usar un código incorporado logo codificarlo con al menos 5 puntos decimales.

Entrada:

Una matriz no vacía de enteros únicos no negativos no más de 2^31-1.

Salida:

Un entero que representa al candidato elegido. Para ser claros, el algoritmo es:

  1. Encuentre el elemento máximo en los primeros floor(N/e)elementos de la matriz.
  2. Itere a través de los elementos restantes y devuelva el primer elemento que sea más alto que el máximo encontrado en el paso 1.
  3. Si ninguno de los elementos es más alto, devuelva el último elemento.

Por ejemplo, digamos que su matriz era [2,7,4,3,9,20], así N = 6y floor(N/e) = 2. Los primeros 2 elementos de la matriz son [2,7]. El máximo de [2,7]es 7. Los elementos restantes son [4,3,9,20]. El primer elemento que es mayor que 7es 9, entonces volvemos 9.

Casos de prueba:

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

Su solución debe ser O(n)dónde nestá la longitud de la matriz. Si su idioma tiene una función incorporada que encuentra el máximo de una matriz, puede suponer que la función toma O(n)(y es de esperar que lo haga).

Se aplican las lagunas estándar, y este es un , ¡así que haga la respuesta más corta en su idioma favorito!

Nathan Merrill
fuente
1
¿Qué se edebe usar?
afuous
2
@voidpigeon supongo que de en.wikipedia.org/wiki/E_(mathematical_constant)
Pomo
1
Ah, ahora entiendo cómo funciona el algoritmo. Pensé que su segundo párrafo significaba que nunca entrevistaría a los candidatos después del piso (n / e) en absoluto.
Pomo de la puerta
1
Pregunté específicamente porque en algunos idiomas, es más corto definir una variable con 5 puntos decimales de precisión que usar realmente el incorporado e(por ejemplo, Python, donde e=2.71828es más corto que import math;math.E)
Mego
1
Nota: "1 / e por ciento del tiempo" sería realmente malo. Es una probabilidad de 1 / e, que es aproximadamente el 37% de las veces
edc65

Respuestas:

4

Jalea, 13 bytes

L:Øe³ḣȯ-Ṁ<i1ị

Definitivamente un algoritmo O (n) , con suerte una implementación O (n) . Pruébalo en línea!

Cómo funciona

L:Øe³ḣȯ-Ṁ<i1ị  Main link. Argument: A (list of scores)

L              Get the length of A.
 :Øe           Divide the length by e, flooring the result.
    ³ḣ         Retrieve the that many scores from the beginning of A.
      ȯ-       Logical OR; replace an empty list with -1.
        Ṁ      Compute the maximum of those scores.
         <     Compare each score in A with that maximum.
          i1   Find the first index of 1 (0 if not found).
            ị  Retrieve the element of A at that index (the last one if 0).
Dennis
fuente
3

CJam, 20 bytes

q~___,1me/i<:e>f>1#=

Funciona de manera similar a la sugerencia de Dennis.

q~___                     Read array, duplicate three times
      ,                   Consume one to find the length
       1me/i              Push e then divide and take floor
            <             Take that many elements from the list
             :e>          Find maximum (Thanks to Dennis)
                f>        Label array elements larger than this as 1
                  1#      Find the first one (won't be in set of elements we've looked in)
                    =     Take that element from the final copy of the array. -1 gives us the last element as required
Un simmons
fuente
$W=no se ejecuta en tiempo lineal.
Dennis
Urgh, tienes razón. ¿Hay alguna forma mejor de encontrar el máximo en CJam que conozcas?
A Simmons
1
:e>(Reducir al máximo)
Dennis
@ Dennis Gracias!
A Simmons
2

Java, 128 118 bytes

a->{int c=(int)(a.length/Math.E),i=0,m=-1,t=0;for(;i<a.length;i++){t=a[i];if(i<c)m=t>m?t:m;if(t>m)return t;}return t;}

Sangrado:

static Function<Integer[], Integer> secretary2 = a -> {
    int c = (int) (a.length/Math.E),     // c = floor(N/E)
        i = 0, m = -1, t = 0;            // declare vars early to save bytes
    for (;i<a.length;i++) {              // for each element of input
        t = a[i];                        // cache element to save bytes
        if (i<c)                         // if before c
            m = t>m ? t : m;             // m = max(m, element)
        if (t>m)                         // if element > m
            return t;                    // return: we've found our best
    }                                    // if never found a good element
    return t;                            // return the last element
};
CAD97
fuente
2

JavaScript (ES6) 64

(a,l=a.length/Math.E,x)=>(a.every(v=>--l>0?x>v?1:x=v:(z=v)<x),z)

Menos golf

(
 a, 
 l=a.length/Math.E, // limit for stage 1
 x // init at undefined
)=>(
  a.every(v => --l > 0 // checking for >0 no need to floor
          ? x>v?1:x=v // stage 1, find max in x, always return truthy
          : (z=v)<x ) // stage 2, set z to current value and exit early if z>x
  , z // at last z has the last seen value
)

Prueba

f=(a,l=a.length/Math.E,x)=>(a.every(v=>--l>0?x>v?1:x=v:(z=v)<x),z)

console.log=x=>O.textContent+=x+'\n'

;[ 
 [0], [100], [0,1], [1,2,3],
 [100, 45],
 [45, 100],
 [1, 4, 5],
 [1, 5, 4],
 [5, 4, 1],
 [5, 1, 4],
 [4, 1, 5],   
 [10, 68, 52, 48, 81, 39, 85, 54, 3, 21, 31, 59, 28, 64, 42, 90, 79, 12, 63, 41, 58, 57, 13, 43, 74, 76, 94, 51, 99, 67, 49, 14, 6, 96, 18, 17, 32, 73, 56, 7, 16, 60, 61, 26, 86, 72, 20, 62, 4, 83, 15, 55, 70, 29, 23, 35, 77, 98, 92, 22, 38, 5, 50, 82, 1, 84, 93, 97, 65, 37, 45, 71, 25, 11, 19, 75, 78, 44, 46, 2, 53, 36, 0, 47, 88, 24, 80, 66, 87, 40, 69, 27, 9, 8, 91, 89, 34, 33, 95, 30],
[56, 7, 37, 73, 90, 59, 65, 61, 29, 16, 47, 77, 60, 8, 1, 76, 36, 68, 34, 17, 23, 26, 12, 82, 52, 88, 45, 89, 94, 81, 3, 24, 43, 55, 38, 33, 15, 92, 79, 87, 14, 75, 41, 98, 31, 58, 53, 72, 39, 30, 2, 0, 49, 99, 28, 50, 80, 91, 83, 27, 64, 71, 93, 95, 11, 21, 6, 66, 51, 85, 48, 62, 22, 74, 69, 63, 86, 57, 97, 32, 84, 4, 18, 46, 20, 42, 25, 35, 9, 10, 19, 40, 54, 67, 70, 5, 44, 13, 78, 96]
].forEach(t=>{
  var r=f(t)
  console.log(r+' : '+t)
})
<pre id=O></pre>

edc65
fuente
1

Ruby, 64 bytes

->a{m=a[0...c=a.size/Math::E].max
a[c..-1].find{|n|n>m}||a[-1]}
afuo
fuente
2
@Doorknob Recorre los elementos del primer piso (N / e) una vez para encontrar el máximo, luego recorre el resto de la lista en el peor de los casos comparando cada elemento con el máximo. Solo hay una comparación por elemento en ambas partes.
afuous
Ah, eso es correcto. Leí mal y pensé que estabas encontrando el máximo en cada iteración.
Pomo de la puerta
1
De hecho, creo que sigue siendo O (n) si solo lo haces a.finden el segundo paso, aunque obviamente es mucho menos eficiente.
histocrat
1
Puede usar (0...c)para un rango que excluya c.
histocrat
@histocrat Sí, debería ser O (2n) que es O (n)
No es que Charles
1

PARI / GP , 70 bytes

Esto puede tener problemas en versiones anteriores de gp cuando se le da un singleton, pero funciona al menos desde la revisión 18487.

v->m=vecmax(v[1..t=#v\exp(1)]);for(i=t+1,#v,v[i]>m&&return(v[i]));v[#v]
Charles
fuente
1

JavaScript (ES6), 79 bytes

a=>(m=Math.max(...a.splice(0,a.length/Math.E)),a.slice(a.findIndex(x=>x>m))[0])

Funciona porque findIndexregresa -1en caso de falla, pero a.slice(-1)[0]devuelve el último elemento de la matriz como se desee.

Neil
fuente
1

Python 2, 87 bytes

a=input()
t=int(len(a)/2.71828)
m=max(a[:t]+[-1])
for x in a[t:]:
 if x>m:break
print x

El usuario ingresa a la matriz como una lista, con corchetes y comas. Python 2input() comando de es conveniente aquí.

Ya sea que terminemos o no el proceso temprano, contratamos a la última persona que fue entrevistada.

Mathmandan
fuente
1

Perl 6, 43 bytes

Creo que esto es O (n)

{@^a.first(*>max @a[^floor @a/e])//@a[*-1]}
Teclas de acceso rápido
fuente
1

Python 3.5; 110 bytes:

def Interview(h):k=max(h[0:int(len(h)/2.71828)-1]);n=max(h[int(len(h)/2.71828)-1:len(h)-1]);return max([k, n])

Básicamente, lo que hace lo anterior es que primero toma una matriz proporcionada, "h" , siempre que incluya más de 5 elementos (por ahora ...), encuentra el valor máximo en la primera (longitud de la matriz (len (h )) / Número de Euler (a 5 decimales)) elementos de esa matriz y luego devuelve ese valor como "k". Además, "n" es el valor máximo en el resto de la matriz. Finalmente, el valor devuelto por la función es el valor máximo en una matriz que contiene "k" y "n".

Nota: La max()función de Python es complejidad O (n).

A continuación se muestra una versión más legible, sin código de golf del código anterior que tiene una matriz aleatoria y única de 10 elementos, para confirmar que funciona:

import random, math

def Interview():
    k = max(h[0:int(len(h)/math.e)-1])
    n = max(h[int(len(h)/math.e)-1:len(h)-1])
    return max([k, n])

h = random.sample(range((2*31)-1), 10)

print(Interview(h))
R. Kap
fuente
Bienvenido a PPCG! Puede separar por coma sus importaciones. Además, no necesita generar la matriz usted mismo, por lo que puede eliminar esa parte del código (simplemente tenga la matriz como parámetro de la función)
Nathan Merrill
@NathanMerrill Sí, estaba pensando en hacer eso, pero luego pensé que realmente no te gustaría, pero ahora que sé que realmente no importa, editaré mi respuesta. Además, gracias por el consejo sobre la coma que separa mis importaciones. ¡Me había olvidado por completo de eso!
R. Kap
Otros consejos: tiene muchos espacios en blanco innecesarios (después de las comas, entre signos de igual. Tampoco necesita una declaración impresa al final.
Nathan Merrill
@NathanMerrill ¡Gracias por los consejos! ¡Los tendré en cuenta a medida que practique más golf de códigos! :)
R. Kap