Traveling Pumpkin Problem

Question

Background:

Jack is a pumpkin that enjoys spooking the citizens of the villages near his pumpkin patch every Halloween. However, every year after someone lights the candle inside of him, he has a limited amount of time to spook everyone before the candle burns out, thus being unable to spook any more villagers because nobody can see him. In past years, he has only been able to spook a small amount of villages due to his poor decision making, but now that he has you to help him, he will be able to spook as many villages as possible!

Task:

Given a list of village locations and a candle lifespan, output the maximum number of villages Jack can visit. You do not have to print the path itself.

Input:

The lifespan of the candle and a list of village locations in a Cartesian coordinate system. The pumpkin patch Jack originates from will always be at 0,0. You may format the input in anyway you wish. To simplify Jack's movements, he can only move horizontally, vertically, or diagonally, meaning his candle will either lose 1 or 1.5 (he takes a bit longer diagonally) units of life every move. The candle burns out when the lifespan is less than or equal to 0.

Output:

An integer equal to the maximum number of villages Jack can visit before the candle burns out.

Rules:

This is code-golf, so shortest code in bytes wins. Standard loopholes are not allowed.

Test cases:

// 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

Answer 1

Jelly, 30 29 27 25 bytes

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

Try it online!

Apparently Jelly's dot product just ignores a list size mismatch and doesn't multiply the extra elements of the other array, just adds them. Shaves off 2 bytes.

Explanation

_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

Answer 2

Java 7, 206 201 bytes

Thanks to @KevinCruijssen for saving 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;}

Ungolfed

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 ;

}

   }

Answer 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

Ungolfed:

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

Answer 4

JavaScript (ES6), 145

Anonymous recursive function, parameter s is the candle lifespan, parameter l is the village coordinate list.

A Depth First Search, stopping when the distance reachs the candle lifespan

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)))

Less golfed see the snippet below

Test

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)
})

Answer 5

MATL, 27 bytes

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

EDIT (26 nov 2016): Due to changes in the Xl function, it has to be replaced in the above code by 2$X>. The links below incorporate that modification.

Try it online! Or verify all test cases.

Explanation

The pumpkin distance between two cities separated Δx and Δy in each coordinate can be obtained as ( |Δx| + |Δy| + max(|Δx|, |Δy|) ) / 2.

The code follows these steps:

1. Generate all permutations of x coordinates and of y coordinates, and prepend a to each 0. Each permutation represents a possible path.
2. Compute absolute consecutive differences for each path (these are |Δx| and |Δy| above).
3. Obtain the pumpkin distance for each step of each path.
4. Compute the cumulative sum of distances for each path.
5. Find, for each path, the number of steps before the accumulated distance reaches the chandle lifespan.
6. Take the maximum of the above.

Commented code:

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

Answer 6

Python 2.7, 422 bytes

thanks to NoOneIsHere for pointing out additional improvements!

thanks to edc65 for noting not to save the list but use iterators instead!

Try it online!

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

Explanation:

The function calculates the distance between two points according to the given rules, the loop iterates through all permutations generated by the generator of the input and calculates the distance, if the distance is lesser than the candle lifespan it subtracts it and adds the place to the counter, if that counter is greater than the current max it substitutes it.

ungolfed:

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

Answer 7

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));

Absolutely brute force and not even very short. Use like:

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

With more whitespace and saved in a file:

<?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) );

Answer 8

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

c is the lifespan of the candle, l is a list of tuples - village coordinates, v is the number of visited villages, (x,y) is pair of coordinates of the village Jack is currently in.

r(t) is a function which calculates the distance to the current position and is used to sort the list so that the closest becomes l[0]. The formula used is |Δx| + |Δy| - min(|Δx|, |Δy|) / 2.

Try it here!

Answer 9

Racket

(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))

Testing:

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

Output:

2
4

However, above code does not work for negative values of x and y.