Reisendes Kürbis-Problem

23

Hintergrund:

Jack ist ein Kürbis, der es genießt, die Bürger der Dörfer in der Nähe seines Kürbisbeetes an jedem Halloween zu erschrecken. Jedes Jahr, nachdem jemand die Kerze in ihm angezündet hat, hat er eine begrenzte Zeit, um alle zu erschrecken, bevor die Kerze ausgebrannt ist. Dadurch kann er keine Dorfbewohner mehr erschrecken, weil ihn niemand sehen kann. In den vergangenen Jahren konnte er aufgrund seiner schlechten Entscheidungsfindung nur eine kleine Anzahl von Dörfern erschrecken, aber jetzt, wo er Sie zur Hilfe hat, wird er in der Lage sein, so viele Dörfer wie möglich zu erschrecken!

Aufgabe:

Geben Sie die maximale Anzahl der Dörfer aus, die Jack besuchen kann, wenn Sie eine Liste mit Orten im Dorf und eine Kerzenlebensdauer angegeben haben. Sie müssen den Pfad nicht selbst drucken.

Eingang:

Die Lebensdauer der Kerze und eine Liste der Orte in einem kartesischen Koordinatensystem. Das Kürbisfeld, aus dem Jack stammt, wird immer bei 0,0 liegen. Sie können die Eingabe beliebig formatieren. Um Jacks Bewegungen zu vereinfachen, kann er sich nur horizontal, vertikal oder diagonal bewegen, was bedeutet, dass seine Kerze bei jeder Bewegung entweder 1 oder 1,5 Lebenseinheiten verliert (diagonal dauert er etwas länger). Die Kerze brennt aus, wenn die Lebensdauer kleiner oder gleich 0 ist.

Ausgabe:

Eine ganze Zahl, die der maximalen Anzahl von Dörfern entspricht, die Jack besuchen kann, bevor die Kerze ausbrennt.

Regeln:

Das ist , also gewinnt der kürzeste Code in Bytes. Standardlücken sind nicht erlaubt.

Testfälle:

// 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
Jodler
quelle
9
Kichern um den Titel
Luis Mendo
3
"Um Jacks Bewegungen zu vereinfachen" ist ein bisschen ironisch, das ist jetzt viel schwieriger: D
PurkkaKoodari
1
Ich denke, Ihre erste Ausgabe sollte 3 sein, wenn ich mich nicht irre
Numberknot
1
@Numberknot Nein, wenn ein Dorf einmal Angst hat, fällt es nicht mehr auf den gleichen Trick. Er kann jedes Dorf nur noch einmal erschrecken.
Yodle
5
Dies ist ein N-Kürbis-Problem, weshalb es im Allgemeinen schwierig sein kann, die maximale Anzahl von Dörfern zu finden. Es gibt eine maximale Anzahl von Dörfern?
Edc65

Antworten:

9

Jelly, 30 29 27 25 Bytes

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

Probieren Sie es online!

Anscheinend ignoriert Jellys Skalarprodukt nur die Nichtübereinstimmung der Listengröße und multipliziert die zusätzlichen Elemente des anderen Arrays nicht, sondern fügt sie nur hinzu. Spart 2 Bytes.

Erläuterung

_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
quelle
In einem Kommentar OP-Anfrage zur Verwaltung von bis zu 1000 Dörfern. Aber jede Antwort, die alle Permutationen generiert und speichert,
schlägt
@ edc65 Nirgendwo heißt es, dass Fälle, die so groß sind, testbar sein müssen, solange der Algorithmus theoretisch funktioniert, wenn genügend Zeit und Speicher zur Verfügung stehen. (Programme, die TSP für n ≈ 1000 lösen können, sind so komplex , dass das Golfen keinen Spaß mehr macht.)
PurkkaKoodari
Ok, nicht 1000, aber nicht einmal 15?
EDC65
@ edc65 Ich kann keinen Algorithmus finden, der schnell und einfach in Jelly zu implementieren wäre. Ich könnte versuchen, eine effizientere Lösung (z. B. Held-Karp) in einer anderen Sprache zu finden. Übrigens verwendet keine der Antworten tatsächlich schnelle Algorithmen; der JS ist besser, aber langsam, wenn es viele Städte in Reichweite gibt.
PurkkaKoodari
5

Java 7, 206 201 Bytes

Vielen Dank an @KevinCruijssen für das Speichern von 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 ;

}

   }
Zahlenknoten
quelle
2
Schön, gut mit dem "ungolfed" Formular. Obwohl, wenn Sie das in drehten, denke ich, dass der Code-Rezensent es nicht ungolfed nennen würde. ;)
Wildcard
+1. Eine Sache zum Golfen: Sie verwenden i-xzweimal und b[c]-yzweimal, so dass Sie ,tzu den Ints hinzufügen können, und verwenden Sie dann diese: Math.sqrt((t=i-x)*t+(t=b[c]-y)*t)*1anstelle von Math.sqrt((i-x)*(i-x)+(b[c]-y)*(b[c]-y))*1.
Kevin Cruijssen
Wie könnte dies im allgemeinen Fall möglicherweise funktionieren?
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

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
}

Erklärung:

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
quelle
3

JavaScript (ES6), 145

Anonyme rekursive Funktion, Parameter sist die Kerzenlebensdauer, Parameter list die Dorfkoordinatenliste.

Eine Tiefensuche , zu stoppen , wenn der Abstand reachs die Kerze Lebensdauer

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

Weniger Golfspieler finden Sie im folgenden Ausschnitt

Prüfung

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
quelle
3

MATL , 27 Bytes

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

BEARBEITEN (26.11.2016): Aufgrund von Änderungen in der XlFunktion muss diese im obigen Code durch ersetzt werden 2$X>. Die folgenden Links übernehmen diese Änderung.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

Die Kürbisentfernung zwischen zwei Städten, die in jeder Koordinate Δ x und Δ y voneinander getrennt sind, kann als (| Δ x | + | Δ y | + max (| Δ x |, | Δ y |)) / 2 erhalten werden.

Der Code folgt diesen Schritten:

  1. Generieren Sie alle Permutationen von x- Koordinaten und von y- Koordinaten und stellen Sie a vor jede 0. Jede Permutation repräsentiert einen möglichen Pfad.
  2. Berechne absolute aufeinanderfolgende Differenzen für jeden Pfad (dies sind | Δ x | und | Δ y | oben).
  3. Ermitteln Sie den Kürbisabstand für jeden Schritt jedes Pfades.
  4. Berechnen Sie die kumulative Summe der Entfernungen für jeden Pfad.
  5. Suchen Sie für jeden Pfad die Anzahl der Schritte, bevor die kumulierte Distanz die Lebensdauer des Chandles erreicht.
  6. Nehmen Sie das Maximum der oben genannten.

Kommentierter 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
Luis Mendo
quelle
Kann MATL wirklich alle Permutationen von 1000 (x, y) Paaren erzeugen?
Edc65
@ edc65 Nein, das ist zu viel (es gibt über 10 ^ 2500 Permutationen von 1000 Elementen). Ich denke, keine Sprache kann
Luis Mendo
In einem Kommentar OP-Anfrage zur Verwaltung von bis zu 1000 Dörfern. Aber jede Antwort, die alle Permutationen generiert und speichert,
schlägt
@ edc65 Ah, ich verstehe. 1000 Dörfer scheinen unrealistisch, wenn das Problem NP-schwer ist, wie es scheint
Luis Mendo
2

Python 2.7 , 422 Bytes

danke an NoOneIsHere für den Hinweis auf weitere Verbesserungen!

danke an edc65 für die notierung, die liste nicht zu speichern, sondern iteratoren zu verwenden!

Probieren Sie es 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

Erläuterung:

Die Funktion berechnet den Abstand zwischen zwei Punkten nach den vorgegebenen Regeln, die Schleife durchläuft alle vom Generator der Eingabe erzeugten Permutationen und berechnet den Abstand, wenn der Abstand geringer als die Kerzenlebensdauer ist, subtrahiert sie ihn und addiert den Platz zum Zähler, wenn dieser Zähler größer als das aktuelle Maximum ist, wird er ersetzt.

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
quelle
Hallo und willkommen bei PPCG! Sie können machen current c, und ll m.
NoOneIsHere
Wow, danke! habe das verpasst
Gmodjackass
In einem Kommentar OP-Anfrage zur Verwaltung von bis zu 1000 Dörfern. Aber jede Antwort, die alle Permutationen generiert und speichert,
schlägt
Ich werde mich irgendwann darum kümmern, danke für die Aufmerksamkeit. Ich habe die Kommentare nicht wirklich gelesen, weil es viele davon gibt.
Gmodjackass
Wenn Sie jetzt Generator verwenden, sollten Sie für die Permutation etwa O (n) verwenden, anstatt alle von Generator generierten Permutationen zu speichern.
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));

Absolut brachiale Kraft und nicht einmal sehr kurz. Verwenden Sie wie:

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

Mit mehr Leerzeichen und in einer Datei gespeichert:

<?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
quelle
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

cist die Lebensdauer der Kerze, list eine Liste von Tupeln - Dorfkoordinaten, vist die Anzahl der besuchten Dörfer, (x,y)ist ein Koordinatenpaar des Dorfes, in dem sich Jack gerade befindet.

r(t)ist eine Funktion, die die Entfernung zur aktuellen Position berechnet und verwendet wird, um die Liste so zu sortieren, dass die nächstgelegene Position erreicht wird l[0]. Die verwendete Formel lautet | Δx | + | Δy | - min (| Δx |, | Δy |) / 2.

Probieren Sie es hier aus!

AlexRacer
quelle
1

Schläger

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

Testen:

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

Ausgabe:

2
4

Der obige Code funktioniert jedoch nicht für negative Werte von x und y.

rnso
quelle