23
\$\begingroup\$

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 , 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
\$\endgroup\$
  • 9
    \$\begingroup\$ Giggling at the title \$\endgroup\$ – Luis Mendo Oct 24 '16 at 16:36
  • 3
    \$\begingroup\$ "To simplify Jack's movements" is kinda ironic, this is a lot more difficult now :D \$\endgroup\$ – PurkkaKoodari Oct 24 '16 at 17:06
  • 1
    \$\begingroup\$ I think your first case output should be 3 if i am not wrong \$\endgroup\$ – Numberknot Oct 24 '16 at 18:02
  • 1
    \$\begingroup\$ @Numberknot No, once a village has been scared they will not fall for the same trick, he can only scare each village one time. \$\endgroup\$ – Yodle Oct 24 '16 at 18:22
  • 5
    \$\begingroup\$ This is a N-Pumpkin Hard problem, so in general the max number of villages could be difficult to find. There is a max number of villages? \$\endgroup\$ – edc65 Oct 25 '16 at 9:38
9
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ In a comment, OP request to manage up to 1000 villages. But any answer that generates and stores all permutations will fail even 15 villages (~1300 billion permutations) \$\endgroup\$ – edc65 Oct 27 '16 at 13:29
  • \$\begingroup\$ @edc65 Nowhere does it say that cases that big need to be testable, as long as the algorithm theoretically works given enough time and memory. (Programs that can actually solve TSP for n ≈ 1000 are so complex they wouldn't be fun to golf anymore.) \$\endgroup\$ – PurkkaKoodari Oct 27 '16 at 13:49
  • \$\begingroup\$ Ok not 1000, but not even 15? \$\endgroup\$ – edc65 Oct 27 '16 at 14:08
  • \$\begingroup\$ @edc65 I can't find an algorithm that would be fast and look easily implementable in Jelly. I might look into making a more efficient solution (e.g. Held-Karp) in another language. BTW, none of the answers use actually fast algorithms; the JS one is better, but slow if there are many cities in range. \$\endgroup\$ – PurkkaKoodari Oct 27 '16 at 14:29
5
\$\begingroup\$

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 ;

}

   }
\$\endgroup\$
  • 2
    \$\begingroup\$ Nice, good on including the "ungolfed" form. Although if you turned that in I think the code reviewer would not call it ungolfed. ;) \$\endgroup\$ – Wildcard Oct 25 '16 at 3:59
  • \$\begingroup\$ +1. One thing to golf: You use i-x twice and b[c]-y twice, so you can add ,t to the ints, and then use this: Math.sqrt((t=i-x)*t+(t=b[c]-y)*t)*1 instead of Math.sqrt((i-x)*(i-x)+(b[c]-y)*(b[c]-y))*1. \$\endgroup\$ – Kevin Cruijssen Oct 25 '16 at 10:49
  • \$\begingroup\$ How could this possibly work in the general case? \$\endgroup\$ – edc65 Oct 27 '16 at 8:07
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ can MATL really generate all permutation of 1000 (x,y) pairs? \$\endgroup\$ – edc65 Oct 26 '16 at 12:55
  • \$\begingroup\$ @edc65 No, that's too much (there are over 10^2500 permutations of 1000 elements). I don't think any language can \$\endgroup\$ – Luis Mendo Oct 26 '16 at 13:32
  • \$\begingroup\$ In a comment, OP request to manage up to 1000 villages. But any answer that generates and stores all permutations will fail even 15 villages (~1300 billion permutations) \$\endgroup\$ – edc65 Oct 27 '16 at 13:30
  • \$\begingroup\$ @edc65 Ah, I see. 1000 villages seems unrealistic if the problem is NP-hard, as it appears to be \$\endgroup\$ – Luis Mendo Oct 27 '16 at 14:30
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Hello, and welcome to PPCG! You can make current c, and ll m. \$\endgroup\$ – NoOneIsHere Oct 25 '16 at 15:45
  • \$\begingroup\$ wow, thanks! missed that one \$\endgroup\$ – Gmodjackass Oct 25 '16 at 16:26
  • \$\begingroup\$ In a comment, OP request to manage up to 1000 villages. But any answer that generates and stores all permutations will fail even 15 villages (~1300 billion permutations) \$\endgroup\$ – edc65 Oct 27 '16 at 13:30
  • \$\begingroup\$ will look into that at some point, thanks for the heads up. I didn't really read the comments because there are many of them. \$\endgroup\$ – Gmodjackass Oct 27 '16 at 19:40
  • \$\begingroup\$ done, using generator now, instead of storing all of the permutations it generates them on the go, should use about O(n) for the permutation. \$\endgroup\$ – Gmodjackass Oct 27 '16 at 19:57
1
\$\begingroup\$

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) );
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.