Concurso de caída de huevos

8

Tu reto:

Estás en el piso 0 de un edificio infinitamente alto. En cualquier piso, puedes caminar hacia la ventana y dejar caer un huevo. Su objetivo es descubrir el piso más alto que el huevo puede soportar sin romperse. Sin embargo, tiene un máximo de 3 huevos para resolver esto, pero debe minimizar el número de intentos.

En términos formales:

  1. Se le da una función f(n)que devuelve bool(n <= X)para un desconocido X, donde0 <= X
  2. Debe devolver el valor de X(sin acceder directamente a él)
  3. f(n)solo debe devolver Falseun máximo de 3veces (en un solo caso de prueba). Si devuelve Falsemás que eso, entonces su respuesta es descalificada.

Restricciones

Su puntaje es el número total de llamadas que realiza f(n)(en los casos de prueba a continuación)

Si lo desea, puede renunciar a pasar una función y simplemente "simular" la situación anterior. Sin embargo , su algoritmo de resolución no debe saber nada X.

Su algoritmo no debe codificar los casos de prueba, o un máximo X. Si tuviera que regenerar los números, o agregar más, su programa debería ser capaz de manejarlos (con una puntuación similar).

Si su idioma no admite enteros de precisión arbitrarios, puede usar el longtipo de datos. Si su idioma tampoco es compatible, entonces no tiene suerte.

El enésimo caso de prueba se genera utilizando lo siguiente:

g(n) = max(g(n-1)*random(1,1.5), n+1), g(0) = 0o aproximadamente 1.25^n

Casos de prueba:

0,1,2,3,4,6,7,8,10,14,15,18,20,27,29,40,57,61,91,104,133,194,233,308,425,530,735,1057,1308,1874,2576,3162,3769,3804,4872,6309,7731,11167,11476,15223,15603,16034,22761,29204,35268,42481,56238,68723,83062,95681,113965,152145,202644,287964,335302,376279,466202,475558,666030,743517,782403,903170,1078242,1435682,1856036,2373214,3283373,4545125,6215594,7309899,7848365,8096538,10409246,15103057,20271921,22186329,23602446,32341327,33354300,46852754,65157555,93637992,107681394,152487773,181996529,225801707,324194358,435824227,579337939,600264328,827690923,1129093889,1260597310,1473972478,1952345052,1977336057,2512749509,3278750235,3747691805,5146052509

Este es un , ¡y la persona con la puntuación más baja gana!

Nathan Merrill
fuente
2
Relacionado (ver también las preguntas vinculadas en mi comentario sobre eso).
Peter Taylor
1
Pregunta relacionada sobre Puzzling SE (pero también con un número máximo de piso).
Martin Ender
8
Si dejo caer un huevo desde la ventana del piso cero de cualquier edificio, estoy bastante seguro de que se romperá. Problema resuelto 😉
Digital Trauma
55
@NathanMerrill Point es, esto es esencialmente inútil ya que no podemos saber nada sobre la probabilidad de que cada tamaño de x sea, ya que te niegas a especificar qué podemos asumir sobre n . Es imposible escribir una respuesta optimizada si no conocemos todos los parámetros de cómo se ejecuta la puntuación. Si nos dijera "su código se ejecuta en 100 casos de prueba de n = 0 a 99", sería una garantía útil. O si hiciste g independiente de n .
FUZxxl
11
Votación para cerrar: Sin una distribución de probabilidad para replicar de manera justa el proceso de puntuación, el criterio ganador no es objetivo.
FUZxxl

Respuestas:

8

Javascript, 442859 442857 74825 llamadas

function findFloor(f){
    var max = 1;
  var min = 0;

  //First egg.
  var n = 1;
  while (f(max)) {
    min = max;
    n += 1;
    max = tetrahedral(n);
  }

  if (max <= min + 1){
    return min;
  }

  //Second egg.
  do {
    var range = max - min;
    var floor = min + reverseTriangle(range);
    var smashed = !f(floor);
    if (smashed) {
        max = floor;
    } else {
        min = floor;
    }
  } while (!smashed && max > min + 1);

  if (max <= min + 1){
    return min;
  }

  //Third egg.
  while (max > min + 1){
    var floor = min + 1;
    var smashed = !f(floor);
    if (smashed) {
        max = floor;
    } else {
        min = floor;
    }
    if (smashed) {
        break;
    }
  }

  return min;

}

function reverseTriangle(x) {
    return Math.ceil((-1 + Math.sqrt(1 + 8 * x)) / 2);
}

function tetrahedral(n) {
    return n * (n + 1) * (n + 2) / 6;
}

Prueba aquí

Puntuaciones para cada caso de prueba individual:

0: 1, 1: 4, 2: 4, 3: 3, 4: 5, 6: 6, 7: 6, 8: 6, 10: 6, 14: 7, 15: 8, 18: 8, 20: 7, 27: 10, 29: 9, 40: 12, 57: 10, 61: 14, 91: 16, 104: 16, 133: 16, 194: 17, 233: 16, 308: 24, 425: 26, 530: 28, 735: 31, 1057: 33, 1308: 38, 1874: 32, 2576: 47, 3162: 45, 3769: 43, 3804: 55, 4872: 52, 6309: 63, 7731: 69, 11167: 69, 11476: 80, 15223: 90, 15603: 75, 16034: 82, 22761: 69, 29204: 110, 35268: 101, 42481: 105, 56238: 126, 68723: 113, 83062: 113, 95681: 160, 113965: 149, 152145: 148, 202644: 187, 287964: 238, 335302: 175, 376279: 258, 466202: 250, 475558: 247, 666030: 256, 743517: 237, 782403: 245, 903170: 278, 1078242: 256, 1435682: 408, 1856036: 304, 2373214: 401, 3283373: 286, 4545125: 328, 6215594: 510, 7309899: 616, 7848365: 458, 8096538: 683, 10409246: 754, 15103057: 787, 20271921: 653, 22186329: 957, 23602446: 754, 32341327: 1141, 33354300: 1033, 46852754: 984, 65157555: 839, 93637992: 1539, 107681394: 1130, 152487773: 1605, 181996529: 1845, 225801707: 1760, 324194358: 2346, 435824227: 2244, 579337939: 2670, 600264328: 2620, 827690923: 3047, 1129093889: 3334, 1260597310: 3813, 1473972478: 4076, 1952345052: 3946, 1977336057: 3599, 2512749509: 4414, 3278750235: 3600, 3747691805: 5580, 5146052509: 4751

Cómo funciona:

1 huevo:

Cuando hay un huevo, la mejor estrategia es subir 1 piso a la vez y regresar el piso directamente debajo del piso donde se rompe primero.

2 huevos:

Cuando tenemos dos huevos, el número máximo de pisos que tenemos que verificar será el n más pequeño para el cual T n es mayor que el rango de pisos que tenemos que verificar. T n es el enésimo número de triángulo. El primer lanzamiento se realizará en el enésimo piso. El segundo lanzamiento se realizará n - 1pisos por encima del primer lanzamiento. El lanzamiento enésimo se hará n - m + 1pisos por encima del m - 1lanzamiento en th. Después de que el huevo se rompa, se necesitarán n - mtiradas para determinar el piso mediante el primer método.

3 huevos:

Con el primero de nuestros huevos debemos determinar un límite superior para el piso más alto. Originalmente, hice esto duplicando el número de piso cada vez. Después de analizar el algoritmo para 2 huevos, pensé que tal vez sería mejor si cada vez que tiramos el huevo, los lanzamientos máximos para encontrar el piso correcto con 2 huevos aumentarían en 1. Esto puede satisfacerse usando los números tetraédricos. Después de que se rompa el primer huevo, podemos usar los métodos anteriores para los huevos restantes.

El máximo de gotas de huevo que requiere para determinar que el piso debe ser óptimo. Sin embargo, probablemente se podría encontrar un mejor algoritmo donde el promedio de gotas de huevo es mejor.

El numero uno
fuente
4

Java, 68985 llamadas

public static long solve(Predicate<Long> eggSurvives) {
  long bestFloor = 0, e1 = 1, e2;

  for(long callsDone = 2; eggSurvives.test(e1); bestFloor = e1, e1 += callsDone * callsDone++);

  for(e2 = bestFloor;; bestFloor = e2) {
    e2 += Math.max((long)Math.sqrt(e1 - e2), 1);

    if(e2 >= e1 || !eggSurvives.test(e2)) {
      break;
    }
  }

  for(long e3 = bestFloor + 1; e3 < e2 && eggSurvives.test(e3); e3++) {
    bestFloor = e3;
  }

  return bestFloor;
}

Resultados de la prueba:

0: 1 1: 4 2: 4 3: 4 4: 4 6: 6 7: 6 8: 6 10: 7 14: 6 15: 7 18: 7 20: 8 27: 10 29: 10 40: 10 57: 10 61: 9 91: 9 104: 11 133: 18 194: 20 233: 18 308: 18 425: 17 530: 17 735: 28 1057: 31 1308: 30 1874: 30 2576: 39 3162: 47 3769: 60 3804: 34 4872: 65 6309: 37 7731: 48 11167: 79 11476: 39 15223: 56 15603: 82 16034: 93 22761: 88 29204: 111 35268: 110 42481: 127 56238: 126 68723: 135 83062: 117 95681: 115 113965: 137 152145: 138 202644: 115 287964: 234 335302: 223 376279: 244 466202: 220 475558: 193 666030: 214 743517: 225 782403: 230 903170: 338 1078242: 223 1435682: 303 1856036: 384 2373214: 453 3283373: 542 4545125: 459 6215594: 525 7309899: 600 7848365: 388 8096538: 446 10409246: 466 15103057: 650 20271921: 822 22186329: 899 23602446: 698 32341327: 804 33354300: 1065 46852754: 1016 65157555: 1408 93637992: 1390 107681394: 1638 152487773: 1283 181996529: 1877 225801707: 2067 324194358: 1842 435824227: 3110 579337939: 2983 600264328: 1817 827690923: 2450 1129093889: 2981 1260597310: 3562 1473972478: 4237 1952345052: 2244 1977336057: 3585 2512749509: 2893 3278750235: 3101 3747691805: 5182 5146052509: 4107

Programa de prueba:

import java.util.function.Predicate;

public class Eggs {
  private static long totalCalls;
  private static long calls;

  public static void main(String[] args) {
    for(long maxFloor : new long[] {0,1,2,3,4,6,7,8,10,14,15,18,20,27,29,40,57,61,91,104,133,194,233,308,425,530,735,1057,1308,1874,2576,3162,3769,3804,4872,6309,7731,11167,11476,15223,15603,16034,22761,29204,35268,42481,56238,68723,83062,95681,113965,152145,202644,287964,335302,376279,466202,475558,666030,743517,782403,903170,1078242,1435682,1856036,2373214,3283373,4545125,6215594,7309899,7848365,8096538,10409246,15103057,20271921,22186329,23602446,32341327,33354300,46852754,65157555,93637992,107681394,152487773,181996529,225801707,324194358,435824227,579337939,600264328,827690923,1129093889,1260597310,1473972478,1952345052,1977336057,2512749509L,3278750235L,3747691805L,5146052509L}) {
      long resultingFloor = solve(f -> {
        calls++;
        return f <= maxFloor;
      });

      if(resultingFloor != maxFloor) {
        throw new RuntimeException("Disqualified");
      }

      System.out.print(maxFloor + ": " + calls + " ");
      totalCalls += calls;
      calls = 0;
    }

    System.out.println("\nCalls = " + totalCalls);
  }

  public static long solve(Predicate<Long> eggSurvives) {
    long bestFloor = 0, e1 = 1, e2;

    for(long callsDone = 2; eggSurvives.test(e1); bestFloor = e1, e1 += callsDone * callsDone++);

    for(e2 = bestFloor;; bestFloor = e2) {
      e2 += Math.max((long)Math.sqrt(e1 - e2), 1);

      if(e2 >= e1 || !eggSurvives.test(e2)) {
        break;
      }
    }

    for(long e3 = bestFloor + 1; e3 < e2 && eggSurvives.test(e3); e3++) {
      bestFloor = e3;
    }

    return bestFloor;
  }
}

Mientras optimizaba, intenté hacer que el número de intentos con cada huevo fuera aproximadamente igual.

  • El primer huevo sube en número de pisos en función del número de intentos hasta el momento.
  • El segundo huevo salta los pisos en función de la raíz cuadrada del número máximo de intentos que podrían quedar (según el límite inferior y superior establecido por el primer huevo), de modo que el número promedio de intentos para el tercer y último huevo debería ser en promedio ser lo mismo que los intentos para el segundo huevo.
john16384
fuente
2

Ruby, 67466 66026 llamadas

$calls = 0

def drop n 
    $calls += 1
    n <= $x
end

def test
    min = 0
    test = 8
    i = 8
    while drop(test)
        min = test
        test += i*i
        i+=1
    end
    max = test
    test = min+((max-min)**0.4).to_i
    while drop(test)
        min = test
        test = min+((max-min)**0.5).to_i
    end
    return min if min+1 == test
    min += 1 while drop(min+1)
    min
end

Código de prueba:

tests = [0,1,2,3,4,6,7,8,10,14,15,18,20,27,29,40,57,61,91,104,133,194,233,308,425,530,735,1057,1308,1874,2576,3162,3769,3804,4872,6309,7731,11167,11476,15223,15603,16034,22761,29204,35268,42481,56238,68723,83062,95681,113965,152145,202644,287964,335302,376279,466202,475558,666030,743517,782403,903170,1078242,1435682,1856036,2373214,3283373,4545125,6215594,7309899,7848365,8096538,10409246,15103057,20271921,22186329,23602446,32341327,33354300,46852754,65157555,93637992,107681394,152487773,181996529,225801707,324194358,435824227,579337939,600264328,827690923,1129093889,1260597310,1473972478,1952345052,1977336057,2512749509,3278750235,3747691805,5146052509]
tests.each{|n|$x = n;test;$calls}
puts $calls

Resultados:

0: 3, 1: 4, 2: 4, 3: 5, 4: 5, 6: 5, 7: 6, 8: 4, 10: 6, 14: 6, 15: 7, 18: 10, 20: 6, 27: 7, 29: 9, 40: 10, 57: 13, 61: 15, 91: 13, 104: 13, 133: 15, 194: 12, 233: 18, 308: 16, 425: 15, 530: 15, 735: 16, 1057: 32, 1308: 30, 1874: 35, 2576: 35, 3162: 54, 3769: 32, 3804: 29, 4872: 45, 6309: 42, 7731: 55, 11167: 72, 11476: 60, 15223: 55, 15603: 71, 16034: 94, 22761: 82, 29204: 119, 35268: 106, 42481: 123, 56238: 127, 68723: 110, 83062: 95, 95681: 139, 113965: 149, 152145: 149, 202644: 144, 287964: 219, 335302: 189, 376279: 183, 466202: 234, 475558: 174, 666030: 235, 743517: 195, 782403: 235, 903170: 346, 1078242: 215, 1435682: 245, 1856036: 422, 2373214: 448, 3283373: 512, 4545125: 378, 6215594: 502, 7309899: 486, 7848365: 440, 8096538: 496, 10409246: 566, 15103057: 667, 20271921: 949, 22186329: 829, 23602446: 746, 32341327: 799, 33354300: 964, 46852754: 1125, 65157555: 1317, 93637992: 1000, 107681394: 1361, 152487773: 1215, 181996529: 2004, 225801707: 1752, 324194358: 1868, 435824227: 3084, 579337939: 2592, 600264328: 1726, 827690923: 2577, 1129093889: 3022, 1260597310: 2582, 1473972478: 3748, 1952345052: 2035, 1977336057: 3712, 2512749509: 2859, 3278750235: 2888, 3747691805: 5309, 5146052509: 4234

Este algoritmo funciona como mi antiguo algoritmo, pero tiene algunas diferencias:

  1. La primera gota de huevo está en el piso 8

  2. El primer incremento es 8 * 8 = 64

Estos números son el resultado de un ajuste aleatorio a mano.

MegaTom
fuente