Latar Belakang:

Jack adalah labu yang suka menakuti penduduk desa di dekat petak labu setiap Halloween. Namun, setiap tahun setelah seseorang menyalakan lilin di dalam dirinya, ia memiliki waktu terbatas untuk menakuti semua orang sebelum lilin habis, sehingga tidak dapat menakuti penduduk desa lagi karena tidak ada yang bisa melihatnya. Dalam beberapa tahun terakhir, dia hanya mampu menakuti sejumlah kecil desa karena keputusannya yang buruk, tetapi sekarang dia memiliki Anda untuk membantunya, ia akan mampu menakuti desa sebanyak mungkin!

Tugas:

Diberikan daftar lokasi desa dan masa hidup lilin, hasilkan jumlah maksimum desa yang dapat dikunjungi Jack. Anda tidak harus mencetak jalur itu sendiri.

Memasukkan:

Umur lilin dan daftar lokasi desa dalam sistem koordinat Kartesius. Patch labu tempat Jack berasal akan selalu sebesar 0,0. Anda dapat memformat input sesuai keinginan Anda. Untuk menyederhanakan gerakan Jack, ia hanya bisa bergerak secara horizontal, vertikal, atau diagonal, yang berarti lilinnya akan kehilangan 1 atau 1,5 (dia butuh sedikit lebih lama secara diagonal) unit kehidupan setiap gerakan. Lilin menyala ketika umur kurang dari atau sama dengan 0.

Keluaran:

Bilangan bulat dengan jumlah maksimum desa yang dapat dikunjungi Jack sebelum lilin habis.

Aturan:

Ini adalah kode-golf , jadi kode terpendek dalam byte menang. Tidak ada celah standar.

Kasus uji:

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

Jelly, 30 29 27 25 byte

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

Cobalah online!

Rupanya produk dot Jelly hanya mengabaikan ketidakcocokan ukuran daftar dan tidak melipatgandakan elemen tambahan dari array lain, hanya menambahkannya. Memotong 2 byte.

Penjelasan

_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

Java 7, 206 201 byte

Terima kasih kepada @KevinCruijssen karena telah menghemat 5 byte

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

Tidak disatukan

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 ;

}

   }

Scala, 196 byte

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

Tidak Disatukan:

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
}

Penjelasan:

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

JavaScript (ES6), 145

Fungsi rekursif anonim, parameter sadalah umur lilin, parameter ladalah daftar koordinat desa.

Sebuah Pencarian Pertama Kedalaman , berhenti ketika jarak reachs umur lilin

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

Kurang bermain golf, lihat cuplikan di bawah ini

Uji

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

MATL , 27 byte

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

EDIT (26 November 2016): Karena perubahan Xlfungsi, itu harus diganti dalam kode di atas oleh 2$X>. Tautan di bawah ini memasukkan modifikasi itu.

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

The labu jarak antara dua kota terpisah Δ x dan Δ y di setiap koordinat dapat diperoleh sebagai (| Δ x | + | Δ y | + max (| Δ x |, | Δ y |)) / 2.

Kode ini mengikuti langkah-langkah ini:

1. Hasilkan semua permutasi dari koordinat x dan dari y , dan tambahkan a ke setiap 0. Setiap permutasi mewakili jalur yang mungkin.
2. Hitung perbedaan absolut berurutan untuk setiap jalur (ini adalah | Δ x | dan | Δ y | di atas).
3. Dapatkan jarak labu untuk setiap langkah dari setiap jalur.
4. Hitung jumlah kumulatif jarak untuk setiap jalur.
5. Temukan, untuk setiap jalur, jumlah langkah sebelum jarak yang terakumulasi mencapai umur lilin.
6. Ambil maksimum di atas.

Kode yang dikomentari:

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

Python 2.7 , 422 byte

terima kasih kepada NoOneIsHere karena telah menunjukkan peningkatan tambahan!

terima kasih kepada edc65 karena tidak menyimpan daftar tetapi gunakan iterators sebagai gantinya!

Cobalah 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

Penjelasan:

Fungsi menghitung jarak antara dua titik sesuai dengan aturan yang diberikan, loop berulang melalui semua permutasi yang dihasilkan oleh generator dari input dan menghitung jarak, jika jaraknya lebih rendah dari umur lilin itu mengurangi dan menambah tempat ke penghitung, jika penghitung itu lebih besar dari maks saat ini ia menggantinya.

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

PHP, 309 byte

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

Kekuatan benar-benar kasar dan bahkan tidak terlalu pendek. Gunakan seperti:

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

Dengan lebih banyak ruang putih dan disimpan dalam 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) );

Python, 175 byte

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

cadalah umur lilin, ladalah daftar tupel - koordinat desa, vadalah jumlah desa yang dikunjungi, (x,y)adalah pasangan koordinat desa Jack saat ini.

r(t) adalah fungsi yang menghitung jarak ke posisi saat ini dan digunakan untuk mengurutkan daftar sehingga terdekat menjadi l[0] . Rumus yang digunakan adalah | Δx | + | Δy | - mnt (| Δx |, | Δy |) / 2.

Coba di sini!

Raket

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

Pengujian:

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

Keluaran:

2
4

Namun, kode di atas tidak berfungsi untuk nilai negatif x dan y.