Проблема с тыквой

23

Задний план:

Джек - тыква, которая любит пугать жителей деревень возле тыквенного участка каждый Хэллоуин. Однако каждый год после того, как кто-то зажигает свечу внутри него, у него есть ограниченное количество времени, чтобы напугать всех до того, как свеча сгорит, таким образом, он не может больше напугать жителей деревни, потому что никто его не видит. В прошлые годы он смог напугать лишь небольшое количество деревень из-за своего плохого принятия решений, но теперь, когда он попросил вас помочь ему, он сможет напугать как можно больше деревень!

Задача:

Учитывая список населенных пунктов и продолжительность жизни свечей, выведите максимальное количество деревень, которые Джек может посетить. Вам не нужно печатать сам путь.

Входные данные:

Срок службы свечи и список населенных пунктов в декартовой системе координат. Тыквенный патч, из которого происходит Джек, всегда будет в 0,0. Вы можете отформатировать ввод по своему усмотрению. Чтобы упростить движения Джека, он может двигаться только горизонтально, вертикально или по диагонали, а это означает, что его свеча будет терять 1 или 1,5 (по диагонали) единицы жизни за каждый ход. Свеча перегорает, когда срок службы меньше или равен 0.

Выход:

Целое число, равное максимальному количеству деревень, которые Джек может посетить, прежде чем погаснет свеча.

Правила:

Это , поэтому выигрывает самый короткий код в байтах. Стандартные лазейки не допускаются.

Тестовые случаи:

// 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
источник
9
Хихикает над названием
Луис Мендо
3
«Упростить движения Джека» довольно иронично, сейчас это намного сложнее: D
PurkkaKoodari
1
Я думаю, что ваш первый вывод дела должен быть 3, если я не ошибаюсь
Numberknot
1
@Numberknot Нет, после того, как деревня напугана, они не попадутся на одну и ту же уловку, он может напугать каждую деревню только один раз.
Йодль
5
Это проблема N-Pumpkin Hard, поэтому в целом максимальное количество деревень может быть трудно найти. Существует максимальное количество деревень?
edc65

Ответы:

9

Желе, 30 29 27 25 байт

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

Попробуйте онлайн!

По-видимому, точечный продукт Jelly просто игнорирует несоответствие размера списка и не умножает дополнительные элементы другого массива, просто добавляет их. Сбривает 2 байта

объяснение

_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
источник
В комментарии OP запрос на управление до 1000 деревень. Но любой ответ, который генерирует и хранит все перестановки, потерпит неудачу даже в 15 деревнях (~ 1300 миллиардов перестановок)
edc65
@ edc65 Нигде не говорится, что такие большие случаи должны быть проверяемыми, если алгоритм теоретически работает при достаточном времени и памяти. (Программы, которые могут на самом деле решить TSP для n ≈ 1000, настолько сложны, что больше не было бы забавно играть в гольф.)
PurkkaKoodari
Хорошо, не 1000, но даже не 15?
edc65
@ edc65 Я не могу найти алгоритм, который был бы быстрым и выглядел бы легко реализуемым в Jelly. Я мог бы найти более эффективное решение (например, Хелд-Карп) на другом языке. Кстати, ни один из ответов не использует действительно быстрые алгоритмы; JS лучше, но медленнее, если в радиусе много городов.
PurkkaKoodari
5

Java 7, 206 201 байт

Спасибо @KevinCruijssen за сохранение 5 байтов

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 ;

}

   }
Numberknot
источник
2
Хорошо, хорошо, в том числе "ungolfed" форма. Хотя, если бы вы включили это, я думаю, что рецензент кода не назвал бы это безволосым. ;)
Wildcard
+1. Одна вещь для игры в гольф: вы используете i-xдва и b[c]-yдва раза, так что вы можете добавить ,tв поля, а затем использовать это: Math.sqrt((t=i-x)*t+(t=b[c]-y)*t)*1вместо Math.sqrt((i-x)*(i-x)+(b[c]-y)*(b[c]-y))*1.
Кевин Круйссен
Как это может сработать в общем случае?
edc65
3

Scala, 196 байт

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
corvus_192
источник
3

JavaScript (ES6), 145

Анонимная рекурсивная функция, параметр s- срок жизни свечи, параметр l- список координат деревни.

Depth First Search , остановка , когда расстояние reachs свечи срок службы

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

Меньше в гольфе, смотрите фрагмент ниже

Тест

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
источник
3

MATL , 27 байт

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

РЕДАКТИРОВАТЬ (26 ноября 2016 г.): Из-за изменений в Xlфункции, она должна быть заменена в приведенном выше коде на 2$X>. Ссылки ниже включают эту модификацию.

Попробуйте онлайн! Или проверьте все тестовые случаи .

объяснение

Расстояние тыквы между двумя городами, разделенными Δ x и Δ y в каждой координате, может быть получено как (| Δ x | + | Δ y | + max (| Δ x |, | Δ y |)) / 2.

Код следует за этими шагами:

  1. Генерация всех перестановок координат х и y и добавьте a к каждому 0. Каждая перестановка представляет возможный путь.
  2. Вычислить абсолютные последовательные различия для каждого пути (это | Δ x | и | Δ y | выше).
  3. Получите расстояние тыквы для каждого шага каждого пути.
  4. Вычислить совокупную сумму расстояний для каждого пути.
  5. Найдите для каждого пути количество шагов до того, как накопленное расстояние достигнет продолжительности жизни чандла.
  6. Возьмите максимум из вышеперечисленного.

Код комментария:

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
Луис Мендо
источник
может ли MATL действительно генерировать всю перестановку из 1000 (x, y) пар?
edc65
@ edc65 Нет, это слишком много (есть более 10 ^ 2500 перестановок из 1000 элементов). Я не думаю, что любой язык может
Луис Мендо
В комментарии OP запрос на управление до 1000 деревень. Но любой ответ, который генерирует и хранит все перестановки, потерпит неудачу даже в 15 деревнях (~ 1300 миллиардов перестановок)
edc65
@ edc65 Ах, понятно. 1000 деревень кажутся нереальными, если проблема NP-сложная, как кажется
Луис Мендо
2

Python 2.7 , 422 байта

спасибо NoOneIsHere за указание на дополнительные улучшения!

спасибо edc65 за то, что он не сохранил список, а использовал итераторы!

Попробуйте онлайн!

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

Объяснение:

Функция вычисляет расстояние между двумя точками в соответствии с заданными правилами, цикл перебирает все перестановки, сгенерированные генератором входных данных, и вычисляет расстояние, если расстояние меньше продолжительности жизни свечи, вычитает его и добавляет место к счетчик, если этот счетчик больше текущего максимума, он заменяет его.

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
Gmodjackass
источник
Здравствуйте и добро пожаловать в PPCG! Вы можете сделать current c, и ll m.
NoOneIsHere
Вау, спасибо! пропустил тот
Gmodjackass
В комментарии OP запрос на управление до 1000 деревень. Но любой ответ, который генерирует и хранит все перестановки, потерпит неудачу даже в 15 деревнях (~ 1300 миллиардов перестановок)
edc65
рассмотрим это в какой-то момент, спасибо за голову. Я действительно не читал комментарии, потому что их много.
Gmodjackass
Готово, используя генератор сейчас, вместо того, чтобы хранить все перестановки, которые он генерирует на ходу, следует использовать около O (n) для перестановки.
Gmodjackass
1

PHP, 309 байт

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

Абсолютно грубая сила и даже не очень короткая. Используйте как:

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

С большим количеством пробелов и сохранено в файле:

<?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) );
user59178
источник
1

Python, 175 байт

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время жизни свечи, lсписок кортежей - координаты деревни, vколичество посещенных деревень, (x,y)пара координат деревни, в которой находится Джек.

r(t)это функция, которая вычисляет расстояние до текущей позиции и используется для сортировки списка так, чтобы ближайшим становится l[0]. Используемая формула: | Δx | + | Δy | - мин (| Δx |, | Δy |) / 2.

Попробуй это здесь!

AlexRacer
источник
1

рэкет

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

Тестирование:

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

Выход:

2
4

Однако приведенный выше код не работает для отрицательных значений x и y.

rnso
источник