23
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 code-golf, 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
9Giggling at the title – Luis Mendo – 2016-10-24T16:36:24.717
Can the input coordinates be a complex number for each village? – Luis Mendo – 2016-10-24T16:39:26.760
@LuisMendo I wasn't planning on having them unaligned with the grid. – Yodle – 2016-10-24T16:52:11.277
I mean 4-j instead of 4 -1, etc – Luis Mendo – 2016-10-24T17:03:38.730
3"To simplify Jack's movements" is kinda ironic, this is a lot more difficult now :D – PurkkaKoodari – 2016-10-24T17:06:29.800
@LuisMendo Ah, then yes you can take in the numbers in any format you wish. – Yodle – 2016-10-24T17:06:45.160
@Pietu1998 Jack is a simple pumpkin, he only knows how to move in cardinal and ordinal directions :P – Yodle – 2016-10-24T17:10:38.967
1I think your first case output should be 3 if i am not wrong – Numberknot – 2016-10-24T18:02:11.837
@Numberknot Ah you're right, both the first and second test cases should be one lower. I'll modify them as I was trying to test for specific things and forgot that I specified that a lifespan value of 0 meant no light. – Yodle – 2016-10-24T18:09:34.807
Is he visit again at the same village too? – Numberknot – 2016-10-24T18:14:22.247
1@Numberknot No, once a village has been scared they will not fall for the same trick, he can only scare each village one time. – Yodle – 2016-10-24T18:22:59.573
@Yodle Except for next year, of course. – mbomb007 – 2016-10-24T21:22:48.973
1"To simplify Jack's movements..." wouldn't it be simpler if it was
sqrt(2)
instead of1.5
...? Because, you know... squares? – mbomb007 – 2016-10-24T21:25:02.037Can villages be on top of each other (i.e. at the same coordinates)? – ETHproductions – 2016-10-24T22:04:40.667
@mbomb007 I had it like that, but I figured dealing with halves would make it easier to work with. Maybe not though! – Yodle – 2016-10-25T01:10:42.030
@ETHproductions No, only one village can occupy a given x,y pair. – Yodle – 2016-10-25T01:10:44.620
5This 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? – edc65 – 2016-10-25T09:38:02.937
Actually, what is 1.5 here, in real life is
√2
. But, let's simplify things. – Erik the Outgolfer – 2016-10-25T15:39:56.190@edc65 Let's say no more than 1000, but I don't have any large test cases currently. – Yodle – 2016-10-25T16:37:58.170
@EriktheGolfer It sounded easier to me, at least in my head, to have a rational number, but I guess if enough people think sqrt(2) is better, I could change it (I originally had it like that on the sandbox, but changed it for here). Most of the answers already have 1.5 though. – Yodle – 2016-10-25T16:39:14.720
@Yodle Wait; isn't it just me? I did not make a suggestion to replace it with sqrt(2), I just stated a real-life vs. PPCG fact here. In fact, I opposed to it ("But let's simplify things.") – Erik the Outgolfer – 2016-10-25T16:41:40.883
@EriktheGolfer Ah okay sorry, just wanted to make sure I wasn't making it more difficult :P – Yodle – 2016-10-25T16:52:57.490
For test case "5 1,1 2,1 3,1 4,1 5,0 5,1", it seems that the answer be 3 rather than 4. – rnso – 2016-10-29T18:53:00.663
@mso I'm pretty sure it's 4. You go diagonally to 1,1, with 3.5 lifespan left. Then you go right until you reach 0.5 which is 3 moves, all of which have villages. – Yodle – 2016-10-31T13:46:28.183