Problema de calabaza itinerante

23

Fondo:

Jack es una calabaza que disfruta asustando a los ciudadanos de las aldeas cercanas a su huerto de calabazas cada Halloween. Sin embargo, cada año después de que alguien enciende la vela dentro de él, tiene un tiempo limitado para asustar a todos antes de que la vela se apague, por lo que no puede asustar a más aldeanos porque nadie puede verlo. En los últimos años, solo ha podido asustar a una pequeña cantidad de aldeas debido a su mala toma de decisiones, pero ahora que tiene que ayudarlo, ¡podrá asustar tantas aldeas como sea posible!

Tarea:

Dada una lista de ubicaciones de aldeas y una vida útil de la vela, produzca el número máximo de aldeas que Jack puede visitar. No tiene que imprimir la ruta en sí.

Entrada:

La vida útil de la vela y una lista de ubicaciones de las aldeas en un sistema de coordenadas cartesianas. El parche de calabaza que Jack origina siempre estará en 0,0. Puede formatear la entrada de la forma que desee. Para simplificar los movimientos de Jack, solo puede moverse horizontal, vertical o diagonalmente, lo que significa que su vela perderá 1 o 1.5 unidades de vida (toma un poco más en diagonal) en cada movimiento. La vela se apaga cuando la vida útil es menor o igual a 0.

Salida:

Un número entero igual al número máximo de pueblos que Jack puede visitar antes de que la vela se apague.

Reglas:

Este es el , por lo que gana el código más corto en bytes. Las lagunas estándar no están permitidas.

Casos de prueba:

// Format [lifespan] [list of village coordinates] -> [maximum visit-able villages]

4 -1,0 1,0 2,0 3,0 4,0 5,0 -> 3
4 1,1 2,2 3,3 -> 2
5 1,1 2,1 3,1 4,1 5,0 5,1 -> 4
Yodle
fuente
99
Riéndose por el título
Luis Mendo
3
"Para simplificar los movimientos de Jack" es un poco irónico, esto es mucho más difícil ahora: D
PurkkaKoodari
1
Creo que la salida de su primer caso debería ser 3 si no estoy equivocado
Numberknot
1
@Numberknot No, una vez que una aldea se ha asustado, no caerán en el mismo truco, solo puede asustar a cada aldea una vez.
Yodle
55
Este es un problema difícil de N-Pumpkin, por lo que en general el número máximo de aldeas podría ser difícil de encontrar. ¿Hay un número máximo de pueblos?
edc65

Respuestas:

9

Jalea, 30 29 27 25 bytes

_AṢæ..
0,0ṭṚç2\+\<S
Œ!ç€Ṁ

Pruébalo en línea!

Aparentemente, el producto de puntos de Jelly simplemente ignora un desajuste de tamaño de lista y no multiplica los elementos adicionales de la otra matriz, solo los agrega. Afeita 2 bytes.

Explicación

_AṢæ..              Helper link to calculate distance. Arguments: a, b
_                     subtract the vertices from each other
 A                    take absolute values of axes
  Ṣ                   sort the axes
   æ..                dot product with [0.5]

0,0ṭṚç2\+\<S        Helper link to calculate max cities. Arguments: perm, max
0,0                   create pair [0,0]
   ṭ                  append that to the permutation
    Ṛ                 reverse the permutation (gets the [0,0] to the beginning)
     ç2\              find distances of each pair using the previous link
        +\            find all partial sums
          <           see if each sum was less than the max
           S          sum to count cases where it was

Œ!ç€Ṁ               Main link. Arguments: cities, max
Œ!                    get permutations of cities
  ç€                  find max cities for each permutation using the previous link
    Ṁ                 take the maximum
PurkkaKoodari
fuente
En un comentario, la solicitud de OP para gestionar hasta 1000 aldeas. Pero cualquier respuesta que genere y almacene todas las permutaciones fallará incluso en 15 aldeas (~ 1300 mil millones de permutaciones)
edc65
@ edc65 En ninguna parte dice que los casos tan grandes deben ser comprobables, siempre que el algoritmo funcione teóricamente con suficiente tiempo y memoria. (Los programas que realmente pueden resolver TSP para n ≈ 1000 son tan complejos que ya no sería divertido jugar golf).
PurkkaKoodari
Ok no 1000, pero ni siquiera 15?
edc65
@ edc65 No puedo encontrar un algoritmo que sea rápido y se vea fácilmente implementable en Jelly. Podría considerar hacer una solución más eficiente (por ejemplo, Held-Karp) en otro idioma. Por cierto, ninguna de las respuestas utiliza algoritmos realmente rápidos; el JS one es mejor, pero lento si hay muchas ciudades dentro del alcance.
PurkkaKoodari
5

Java 7 206 201 bytes

Gracias a @KevinCruijssen por guardar 5 bytes

int f(float e,int[]a,int[]b){int x=0,y=0,c=0,d=0,t;float s;for(int i:a){s=(i!=x&b[c]==y)|(i==x&b[c]!=y)?Math.sqrt((t=i-x)*t+(t=b[c]-y)*t)*1:Math.abs(i-x)*1.5;d+=e-s>=0?1:0;e-=s;x=i;y=b[c++];}return d;}

Sin golf

class Travellingpumpkin {

public static void main(String[] args) {

    System.out.println(f( 5 ,new int[] { 1,2,3,4,5,5 } , new int[] { 1,1,1,1,0,1 } ));

}
static int f( double e , int[]a , int[]b ) {
    int x = 0 , y = 0 , c = 0 , d = 0 , t;
    double s ;

    for ( int i : a ) {
    s = ( i != x & b[c] == y )|( i == x & b[c] != y )
         ? Math.sqrt( ( t = i - x ) * t + ( t = b[c] - y ) * t ) * 1
         : Math.abs( i - x ) * 1.5 ;


        d += e-s >= 0 ? 1 : 0 ;
        e -= s ;
        x = i ; y = b [ c++ ] ;
    }
    return d ;

}

   }
Nudo numérico
fuente
2
Agradable, bueno para incluir la forma "no golfista". Aunque si entregaste eso, creo que el revisor del código no lo llamaría descabellado. ;)
Comodín el
+1. Una cosa para jugar al golf: se usa i-xdos veces y b[c]-ydos veces, por lo que puede agregar ,ta las entradas y luego usar esto: en Math.sqrt((t=i-x)*t+(t=b[c]-y)*t)*1lugar de Math.sqrt((i-x)*(i-x)+(b[c]-y)*(b[c]-y))*1.
Kevin Cruijssen
¿Cómo podría funcionar esto en el caso general?
edc65
3

Scala, 196 bytes

def f(l:Int,c:(Int,Int)*)=c.permutations.map(x=>((0,0)+:x sliding 2 map{p=>val Seq(c,d)=Seq((p(0)._1-p(1)._1)abs,(p(0)._2-p(1)._2)abs).sorted
c*1.5+(d-c)}scanLeft 0d)(_+_)takeWhile(_<l)size).max-1

Sin golf:

def g (l: Int, c: (Int, Int)*) = {
    c.permutations
    .map { x =>
        ((0, 0) +: x).sliding(2).map({ p =>
            val Seq(c, d) = Seq((p(0)._1 - p(1)._1) abs, (p(0)._2 - p(1)._2) abs).sorted
            c * 1.5 + (d - c)
        }).scanLeft(0d)(_ + _).takeWhile(_ < l).size
    }.max - 1
}

Explanantion:

def f(l:Int,c:(Int,Int)*)= //defien a function with an int and a vararg-int-pait parameter
  c.permutations           //get the permutations of c, that is all possible routes
  .map(x=>                 //map each of them to...
    ((0,0)+:x                //prepend (0,0)
    sliding 2                //convert to a sequence of consecutive elemtens
    map{p=>                  //and map each of them to their distance:
      val Seq(c,d)=Seq(        //create a sequence of
        (p(0)._1-p(1)._1)abs,  //of the absolute distance between the x points
        (p(0)._2-p(1)._2)abs   //and he absolute distance between the y coordinates
      ).sorted                 //sort them and assign the smaller one to c and the larger one to d
      c*1.5+(d-c)              //we do the minimum difference diagonally
    }                        //we now have a sequence of sequence of the distances for each route
    scanLeft 0d)(_+_)       //calculate the cumulative sum
    takeWhile(_<l)          //and drop all elements that are larger than the candle lifespan
    size                    //take the size
  ).max-1                   //take the maximum, taht is the size of the largest route and subtract 1 because we added (0,0) at the beginning
corvus_192
fuente
3

JavaScript (ES6), 145

Función recursiva anónima, el parámetro ses la vida útil de la vela, el parámetro les la lista de coordenadas de la aldea.

Una primera búsqueda de profundidad , deteniéndose cuando la distancia alcanza la vida útil de la vela

f=(s,l,x=0,y=0,v=0,A=Math.abs,X=Math.max)=>X(v,...l.map(([t,u],i,[h,...l],q=A(t-x),p=A(u-y),d=(l[i-1]=h,p+q+X(p,q))/2)=>s<=d?v:f(s-d,l,t,u,1+v)))

Menos golf, vea el fragmento a continuación

Prueba

f=(s,l,x=0,y=0,v=0,A=Math.abs,X=Math.max)=>
  X(v,...l.map(
      ([t,u],i,[h,...l],q=A(t-x),p=A(u-y),d=(l[i-1]=h,p+q+X(p,q))/2)=>
      s<=d?v:f(s-d,l,t,u,1+v)
  ))

// ungolfed version

F=(s, l, 
   x=0, y=0, // current position
   v=0 // current number of visited sites 
  ) =>
   Math.max(v, ...l.map(
     (
       [t,u], i, [h,...l], // lambda arguments
       q = Math.abs(t-x), p = Math.abs(u-y), // locals
       d = (p+q+Math.max(p,q))/2
     ) => (
       l[i-1] = h,
       s <= d 
         ? v 
         : F(s-d, l, t, u, v+1)
     ) 
  ))

;[[4,[[-1,0],[1,0],[2,0],[3,0],[4,0],[5,0]], 3]
,[4, [[1,1],[2,2],[3,3]], 2]
,[5, [[1,1],[2,1],[3,1],[4,1],[5,0],[5,1]], 4]
].forEach(test=>{
  var span=test[0],list=test[1],check=test[2],
      result = f(span, list)
  console.log(result==check?'OK':'KO',span, list+'', result)
})

edc65
fuente
3

MATL , 27 bytes

EH:"iY@OwYc!d|]yyXl++Ys>sX>

EDITAR (26 de noviembre de 2016): debido a cambios en la Xlfunción, debe ser reemplazado en el código anterior por 2$X>. Los enlaces a continuación incorporan esa modificación.

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

La distancia de calabaza entre dos ciudades separadas Δ x y Δ y en cada coordenada se puede obtener como (| Δ x | + | Δ y | + max (| Δ x |, | Δ y |)) / 2.

El código sigue estos pasos:

  1. Genere todas las permutaciones de las coordenadas x y de las coordenadas y , y anteponga a a cada 0. Cada permutación representa una posible ruta.
  2. Calcule las diferencias absolutas consecutivas para cada ruta (estas son | Δ x | y | Δ y | arriba).
  3. Obtenga la distancia de calabaza para cada paso de cada camino.
  4. Calcule la suma acumulativa de distancias para cada ruta.
  5. Encuentre, para cada ruta, el número de pasos antes de que la distancia acumulada alcance la vida útil del chandle.
  6. Tome el máximo de lo anterior.

Código comentado:

E        % Input candle lifespan implicitly. Multiply by 2
H:"      % Do thie twice
  i      %   Input array of x or y coordinates
  Y@     %   All permutations. Gives a matrix, with each permutation in a row
  OwYc   %   Prepend a 0 to each row
  !      %   Transpose
  d|     %   Consecutive differences along each column. Absolute value
]        % End
yy       % Duplicate the two matrices (x and y coordinates of all paths)
Xl       % Take maximum between the two, element-wise
++       % Add twice. This gives twice the pumpkin distance
Ys       % Cumulative sum along each column
>        % True for cumulative sums that exceed twice the candle lifespan
s        % Sum of true values for each column
X>       % Maximum of the resulting row array. Inmplicitly display
Luis Mendo
fuente
¿Puede MATL realmente generar toda la permutación de 1000 (x, y) pares?
edc65
@ edc65 No, eso es demasiado (hay más de 10 ^ 2500 permutaciones de 1000 elementos). No creo que ningún idioma pueda
Luis Mendo
En un comentario, la solicitud de OP para gestionar hasta 1000 aldeas. Pero cualquier respuesta que genere y almacene todas las permutaciones fallará incluso en 15 aldeas (~ 1300 mil millones de permutaciones)
edc65
@ edc65 Ah, ya veo. 1000 aldeas parece poco realista si el problema es NP-difícil, como parece ser
Luis Mendo
2

Python 2.7 , 422 bytes

¡Gracias a NoOneIsHere por señalar mejoras adicionales!

¡Gracias a edc65 por observar que no guarda la lista sino que usa iteradores en su lugar!

Pruébalo en línea!

from itertools import permutations
def d(s,e):
    d=0
    while s!=e:
        x=1 if s[0]<e[0] else -1 if s[0]>e[0] else 0
        y=1 if s[1]<e[1] else -1 if s[1]>e[1] else 0
        s=(s[0]+x,s[1]+y)
        d+=(1,1.5)[x and y]
return d
l,m=4,0
for o in permutations([(1,1),(2,2),(3,3)]):
    a,c=l-d((0,0),o[0]),1
    for j in range(len(o)-1):
        a-=d(o[j],o[j+1])
        c+=(0,1)[a>0]
    m=max(c,m)
print m

Explicación:

La función calcula la distancia entre dos puntos de acuerdo con las reglas dadas, el ciclo itera a través de todas las permutaciones generadas por el generador de la entrada y calcula la distancia, si la distancia es menor que la vida útil de la vela, la resta y agrega el lugar al contador, si ese contador es mayor que el máximo actual, lo sustituye.

sin golf:

from itertools import permutations

def distance(start_pos, end_pos):
    distance = 0
    while start_pos != end_pos:
        mod_x = 1 if start_pos[0] < end_pos[0] else -1 if start_pos[0] > end_pos[0] else 0
        mod_y = 1 if start_pos[1] < end_pos[1] else -1 if start_pos[1] > end_pos[1] else 0
        start_pos = (start_pos[0] + mod_x, start_pos[1] + mod_y)
        distance += (1, 1.5)[mod_x and mod_y]
    return distance

lifespan, max_amount = 4, 0
for item in permutations([(1,1), (2,2), (3,3)]):
    lifespan_local, current = lifespan - distance((0,0), item[0]), 1
    for j in range(len(item) - 1):
        lifespan_local -= distance(item[j], item[j + 1])
        current += (0, 1)[lifespan_local > 0]
    max_amount = max(current, max_amount)
print max_amount
Gmodjackass
fuente
Hola y bienvenidos a PPCG! Puedes hacer current c, y ll m.
NoOneIsHere
¡Wow gracias! perdí esa
Gmodjackass
En un comentario, la solicitud de OP para gestionar hasta 1000 aldeas. Pero cualquier respuesta que genere y almacene todas las permutaciones fallará incluso en 15 aldeas (~ 1300 mil millones de permutaciones)
edc65
Lo investigaremos en algún momento, gracias por el aviso. Realmente no leí los comentarios porque hay muchos de ellos.
Gmodjackass
hecho, usando el generador ahora, en lugar de almacenar todas las permutaciones que las genera sobre la marcha, debe usar aproximadamente O (n) para la permutación.
Gmodjackass
1

PHP, 309 bytes

function j($x,$y,$c,$v){if($s=array_search([$x,$y],$v))unset($v[$s]);for($c--,$i=4;$c>0&&$i--;)$m=($n=j($x+[1,0,-1,0][$i],$y+[0,1,0,-1][$i],$c,$v))>$m?$n:$m;for($c-=.5,$i=4;$c>0&&$i--;)$m=($n=j($x+[1,-1,-1,1][$i],$y+[1,1,-1,-1][$i],$c,$v))>$m?$n:$m;return$s?++$m:$m;}echo j(0,0,$argv[1],array_chunk($argv,2));

Absolutamente fuerza bruta y ni siquiera muy corta. Usar como:

php -r "function j($x,$y,$c,$v){if($s=array_search([$x,$y],$v))unset($v[$s]);for($c--,$i=4;$c>0&&$i--;)$m=($n=j($x+[1,0,-1,0][$i],$y+[0,1,0,-1][$i],$c,$v))>$m?$n:$m;for($c-=.5,$i=4;$c>0&&$i--;)$m=($n=j($x+[1,-1,-1,1][$i],$y+[1,1,-1,-1][$i],$c,$v))>$m?$n:$m;return$s?++$m:$m;}echo j(0,0,$argv[1],array_chunk($argv,2));" 5 1 1 2 1 3 1 4 1 5 0 5 1

Con más espacios en blanco y guardados en un archivo:

<?php 
function j( $x, $y, $c, $v)
{
    if( $s = array_search( [$x,$y], $v ) )
        unset( $v[$s] );

    for( $c--, $i=4; $c>0 && $i--;)
        $m = ( $n=j($x+[1,0,-1,0][$i],$y+[0,1,0,-1][$i],$c,$v) )>$m ? $n : $m;

    for( $c-=.5, $i=4; $c>0 && $i--;)
        $m = ( $n=j($x+[1,-1,-1,1][$i],$y+[1,1,-1,-1][$i],$c,$v) )>$m ? $n : $m;

    return $s ? ++$m : $m;
}
echo j( 0, 0, $argv[1], array_chunk($argv,2) );
usuario59178
fuente
1

Python, 175 bytes

def f(c,l):
 def r(t):p=abs(t[0]-x);q=abs(t[1]-y);return p+q-.5*min(p,q)
 v=0;x,y=0,0
 while c>0 and len(l)>0:
  l.sort(key=r);c-=r(l[0]);x,y=l.pop(0)
  if c>=0:v+=1
 return v

ces la vida útil de la vela, les una lista de tuplas - coordenadas de la aldea, ves el número de aldeas visitadas, (x,y)es un par de coordenadas de la aldea en la que se encuentra Jack actualmente.

r(t)es una función que calcula la distancia a la posición actual y se usa para ordenar la lista de modo que se haga la más cercana l[0]. La fórmula utilizada es | Δx | + | Δy | - min (| Δx |, | Δy |) / 2.

Pruébalo aquí!

AlexRacer
fuente
1

Raqueta

(define (dist x1 y1 x2 y2)     ; fn to find distance between 2 pts
  (sqrt(+ (expt(- x2 x1)2)
          (expt(- y2 y1)2))))

(define (fu x1 y1 x2 y2)       ; find fuel used to move from x1 y1 to x2 y2;
  (let loop ((x1 x1)
             (y1 y1)
             (fuelUsed 0))
    (let* ((d1 (dist (add1 x1) y1 x2 y2))        ; horizontal movement
           (d2 (dist x1 (add1 y1) x2 y2))        ; vertical movement
           (d3 (dist (add1 x1) (add1 y1) x2 y2)) ; diagonal movement
           (m (min d1 d2 d3))) ; find which of above leads to min remaining distance; 
      (cond 
        [(or (= d2 0)(= d1 0)) (add1 fuelUsed)]
        [(= d3 0) (+ 1.5 fuelUsed)]
        [(= m d1) (loop (add1 x1) y1 (add1 fuelUsed))]
        [(= m d2) (loop x1 (add1 y1) (add1 fuelUsed))]
        [(= m d3) (loop (add1 x1) (add1 y1) (+ 1.5 fuelUsed))]))))

(define (f a l)
  (define u (for/list ((i l))
    (fu 0 0 (list-ref i 0) (list-ref i 1))))  ; find fuel used for each point; 
  (for/last ((i u)(n (in-naturals)) #:final (>= i a))
    n))

Pruebas:

(f 4 '((1 1) (2 2) (3 3))) ;-> 2
(f 5 '((1 1) (2 1) (3 1) (4 1) (5 0) (5 1))) ;-> 4

Salida:

2
4

Sin embargo, el código anterior no funciona para valores negativos de x e y.

rnso
fuente