6
\$\begingroup\$

It's almost Christmas, so Santa has to plan his route. You're helping him, for reasons unknown.

Santa needs help planning the route and wants you to give him a solution, but since you're all ungrateful and unwilling to give to the man who has given you so much, so have decided to give him a program with as few bytes as possible to accomplish the following.

The houses Santa needs to visit can be represented by coordinates on the Cartesian plane (the coordinates of the houses need not be integers, there cannot be more than 1 house at any point, and there is no house at the origin). These coordinates will be the input. Starting at the origin, Santa will visit each coordinate and then return to the origin.

Santa rides his sleigh at a constant one unit per second in a straight line between houses. However, when Santa crosses any lattice point (a point with integer x and y coordinates) he stops for one second to eat a cookie (the initial and final crossings of the origin do not count, though crossing it on the path between, say, (-1,-1) and (1,1) would). When he stops at a house, he spends five seconds to deliver a present (so he spends six seconds at houses on lattice points).

Write a program that takes as its input a set of coordinates and prints the smallest number of seconds Santa needs to deliver all of the presents to the houses and return to the origin, rounded to three digits. Take 25% off your code if it also prints any order of coordinates Santa visits that minimizes the time.


Test cases

(1,1) (2,4) (2,2)
==> 14.301
==> (Bonus) (1,1) (2,2) (2,4)

(3,4) (2,-1) (0,-3.5) (1,6)
==> 27.712
==> (Bonus) (0,-3.5) (2,-1) (3,4) (1,6)

This is code golf. Standard rules apply. Shortest code in bytes wins.


Note that this is a modification of the Travelling Salesman Problem, so your program does not need to terminate in any reasonable amount of time for an unreasonable number of inputs (this is a problem in O(n!) after all).

\$\endgroup\$
  • 5
    \$\begingroup\$ You DO realize that this is the Travelling Salesman Problem, right? None of these are going to be particularly fast. \$\endgroup\$ – Deusovi Dec 24 '15 at 8:04
  • 1
    \$\begingroup\$ @Deusovi I forgot to mention that at the end, thanks for the catch. \$\endgroup\$ – Arcturus Dec 24 '15 at 8:08
  • 1
    \$\begingroup\$ You you please provide some test cases? \$\endgroup\$ – flawr Dec 24 '15 at 12:27
  • 3
    \$\begingroup\$ How is this a duplicate? It adds the challenge of trying to find a path with the least lattice crossings. \$\endgroup\$ – LegionMammal978 Dec 24 '15 at 18:19
  • 1
    \$\begingroup\$ I agree with @LegionMammal978. This provides an additional challenge, which I added BECAUSE of that other question. \$\endgroup\$ – Arcturus Dec 24 '15 at 20:33
1
\$\begingroup\$

Perl 6, 198 bytes (264 bytes - 25% bonus)

Managed to actually get this sucker into a Whatever block by inlining the helper functions from the original version.

*.permutations.map({([+] -1,5*@_,|(for (0,0),|@_ Z |@_,(0,0) ->((\i,\j),(\x,\y)){my ($s,\p)=0,i.Rat.nude[1]*j.Rat.nude[1]*abs(i -x).Rat.nude[0];(i+(x -i)*$_/p)%%1&&(j+(y -j)*$_/p)%%1&&$s++ for ^p;sqrt(abs(i -x)²+abs(j -y)²)+(p??$s!!abs(j.Int -y.Int))})),@_}).min

Try it online!

No doubt there are still a few little improvements that can be made. Trickiest part was figuring out how to calculate the number of lattice points crossed. The solution I went with uses the denominators of each X coordinate to calculate an iteration interval that is guaranteed to hit each whole number along with X axis, thus allowing a check for landing on a lattice point. There is a catch, of course, that if there is no movement along X then the lattice points crossed will be the absolute value of the floor value of each Y coordinate.

This will be, nonetheless, very tricky for languages that don't have built in rationals, because of floating point errors (I can already see the .1 + .2 = .3 issue cropping up if any two X or Y coordinates are 10 apart).

Ungolfed version:

*                           #  Whatever block, takes a list of coordinates
.permutations.map({         #  Get all combinations and to each of them ... 
 (                          #   Implicitly return a list consisting of 
  [+]                       #    The sum of
   -1,                      #     -1 (to discount lattice +1 on return to origin)
   5*@_,                    #     5 * number of coordinates (or stops)
   |(for                    #     each value in the loop across 
    (0,0),|@_ Z |@_,(0,0)   #      the coordinates (zipping with the origin 
                            #        first/last for the return)
    ->((\i,\j),(\x,\y)) {   #      deconstructing into i,j,x,y
     my ($s,\p)=0,          #      set S (lattice stops) to 0
       i.Rat.nude[1]        #      set P (x check interval) to denominator of i
       *j.Rat.nude[1]       #       times denominator of p (psuedo lcm)
       *abs(i -x).Rat.nude[0]; #    times x-diff numerator (bc Rat simplification) 
     (i+(x -i)*$_/p)%%1&&   #      check X is whole, if so,
      (j+(y -j)*$_/p)%%1&&  #       check Y is whole, if so,
      $s++                  #        increment S (trip crossed a lattice point)           
     for ^p;                #      do the checks for 0 to P
     sqrt(                  #      implicitly return
      abs(i -x)²+abs(j -y)² #       the distance
     )+(p                   #        plus, if X values were different,
      ??$s                  #         S value, else
      !!abs(j.Int -y.Int)   #         Y difference = vertical lattice crossings
     )
    }                            
   )                        #     
   ,@_)                     #   And the permutation
.min                        #  Find best (smallest) time 

I'll probably add a more readable version because this golfing got unreadable fast.

\$\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.