plasmid

Is it obvious which of the two neighbors is using the plumbing, or are they indistinguishable? Edit:

Oh noes... betrayed by a cookie! What'd I ever do to that poor cookie? Oh, right, I ate it.

Actually, I overlooked that the OP said the ants can jump straight vertically and straight horizontally as well as diagonally. That makes my omission of ants on the opposite color square as the final goal if the grid is colored like a checkerboard (they can contribute to a solution by being jumped), and my counting of only ants that are within a 90 degree cone of the goal (ants can jump horizontally to enter such a cone and contribute to an answer) invalid.

That makes it easy to guarantee release if the prisoners still get to know what time of day they enter the room. Want to take away their watches so they're all forced to follow the same algorithm without knowing when they've entered?

Converting my numbering to the type of numbering that would be used in the OP, my answer implies that if ants start off at y=0 and no higher, then they won't be able to reach y=7. It doesn't ensure that they can somehow reach y=6, it just doesn't rule it out as impossible.

I had done the same analysis as Barc and concluded that it's probably the correct answer because As for coming up with a different strategy That said, I bet bonanova's already thought of that and has a solution that still works with those rules despite my argument that attempts to show it's impossible.

Edit: Out of curiosity, what sort of time and resources do the kids get to solve these problems?

Yep, using the version straight from the post and not the one I tweaked to output a matrix. That block even shows up if I show the code from the command line to make sure I didn't do something silly like forget to save the most recent version from the text editor. Ran it with command line parameters of 30 11 3 just like you did and I'm still getting the same four-step answer. Very bizarre that we're getting different answers from it; it should be completely deterministic.

Must a prisoner commit to moving a card to a particular bin before seeing what's underneath it? Or may he change his mind and pick a different card, or change the chosen card's destination, after seeing what's underneath the card he initially picks up?

I was using the code from post #21; is there another version?

RID abilities generally are given to the baddies or indies and do something nasty to the target (usually kill) and serve as a way of preventing goodies from rampantly outing their roles in order to narrow down the baddies. But this game's mechanics are quite different from most games; the goodies will probably not really want to out their roles anyway because they'll want to try to make it look like they're the hypochondriac to get themselves released by the psychiatrist.

Confirm. Bringing forward some answers to questions etc. from signups into this thread so everyone's on the same page: In the event of one of the Sane being killed, the MPD takes over the dead Sane's wincon and role. NK cannot be affected by any actions except save. The psychologist can, if they wish, choose one player per Day, ("bonanova" for example) and PM with their wish to release them. 2x night role act means they can act as two Night roles, e.g. block and redirect, if they can identify the players. They use this action the same night, yes. Sane and Killers have BTSC until one of the Sane dies, in which case the MPD-turned Sane will not have BTSC with the remaining Sane. Killers always have BTSC. More questions: What events would cause the game to end? All of the Baddies or all of the Sane (including multiple personality if he becomes Sane) leaving the game? For the Baddies' wincon: If the psychologist gets redirected to himself so he gets released from the asylum, does he count as released but not dead and therefore make it impossible for the baddies to win? If the MPD turns Sane, do the baddies need to kill MPD or just the two original Sanes? For the Sane' wincon: If a baddie gets released from the asylum, or if the last baddie gives up and NKs himself (which would generally be very poor form except in extreme cases), would it be unwinnable for the Sane because the baddies couldn't all be lynched? For the Indy: Does he name a player and get their ability, or name a role and get their ability, or have to RID a player to get their ability? Can the indy or multiple personality guy use the abilities of a dead player? Also voting to lynch Barc -- I spied him and he's a baddie.

Here's a concrete example. I tried modifying the code so it generates a matrix of steps to get from each starting point to each goal, just like the matrix I posted earlier, and runs from 1 to 30 so I could directly compare the matrices they produce. They differ at some spots, one of which is the path going from 11 to 3. For some reason it took four steps and went 11/11=1, 11+11=22, 22/11=2, 2+1=3. Obviously a shorter path would be 11/11=1, 1+1=2, 1+2=3. Apparently there are two equally short paths from 11 to 2: {11/11=1, 1+1=2} and {11+11=22, 22/11=2}, and the algorithm ended up storing the second path as the most efficient path to get to 2. However, since it didn't store the path to 2 that creates 1 as an intermediate rather than 22, it wasn't able to discover that you could reach 3 from a path going to 2 through 1 that had a useful intermediate already generated.

The only potential pitfall I can think of is theoretical (at least I can't come up with a concrete example of it right now): Suppose you start from A and need to reach D, which can be reached from B and C. There's an optimal path from A to B in, say, four moves. There's an optimal path from A to C in, say, five moves. So it would look like it would take 4 moves to reach B, 5 to reach C, and therefore a total of 10 to reach D. What if there were some number E that could be reached from A in two moves, and it would take five moves to reach B if E is included the path from A to B, and it would take six moves to reach C if E is included in the path from A to C. So E would not be included in the optimal paths to either B or C. But suppose if you have both B and E in a set already (although such a set would never be formed by the algorithm because they don't form an optimal path), then you could reach C in two moves from {A, B, E}. Bear in mind that this still would involve a total path length from A to C of eight moves, which is far worse than the optimal five, so it would not be preserved as an optimal path. That would create a possible path from A to D in 2 (A to E) + 4 ({A,E} to B) + 2 ({A,B,E} to C) + 1 ({A,B,C,E} to D) = 9 moves instead of 10. I think that such a path might not be detected by this algorithm. But I'm not sure if such a scenario actually exists, or even if it's possible to prove that such a scenario cannot exist.

Unless I'm reading it incorrectly, under Best starts with 10 worst case steps, it seems to say that it takes 10 steps to get from 9 to 13. But that's clearly not optimal. It isn't giving me quite the same answers when I tried running the code. I set $last to 20 and forced $start to just be 9, and it said the worst case was 9 => 14 in 9 steps. Setting $my_start and $my_goal to 9 and 14 and rearranging the operations, it seemed to have taken 9/9 = 1 9-1 = 8 1+1 = 2 9+9 = 18 18+9 = 27 27+8 = 35 18+1 = 19 19+2 = 21 35-21 = 14 It didn't pick a path like 9/9 = 1 1+1 = 2 2+2 = 4 9+4 = 13 (to get to 13 in four steps) 13+1 = 14 (to get to 14 in five steps) My best guess about what's going on is that, when it goes through the "generate" subroutine, it just looks at all the numbers that it reached so far and finds some combination of two numbers that have been reached that leads to a number that hasn't been reached yet, without regard to the number of steps it took to reach the intervening numbers. So for example to reach 14: after one round of "generate" the algorithm will have reached 9+9 = 18 and 9/9 = 1. In the second round it could reach 9-1 = 8 and 1+1 = 2 and 18+9 = 27 and 18+1 = 19. In the third round it could reach 27+8 = 35 and 19+2 = 21. Then in the fourth round it could reach 35-21 = 14. So it only takes four rounds of the generate subroutine to reach 14 via that route which requires nine operations, as opposed to five rounds of generate to reach 14 with the five operations shown above. Essentially, it finds the path that invokes generate the fewest number of times rather than the path that uses the smallest number of operations.

I've been trying to figure out what makes your code run so much faster, and I think I can more or less follow its logic but I'm not sure about one point. If you wanted to get from a starting point of 1 to an ending point of 7, you could do that with 1+1=2 2*2=4 2+1=3 4+3=7 With the algorithm, after you get one path with 1, 2, 4 and another path with 1, 2, 3 it looks like the first of those sets wouldn't allow you to add 4 in the next round because there is already a different path to reach 4, and the second of those sets wouldn't allow you to add 3 in the next round because there is already a different path to reach 3. (This is from the next if (exists($m->{$result})); line.) I'm wondering if it would have a way of discovering that path to 7? For the most part our algorithms seem to agree, but when I set the max size for both algorithms to 30, mine said you can go from 25 to 13 in 4 steps (from the matrix in my earlier post) while yours said that 25 to 13 took 6 steps (when I commented out the if ($start{$s}{$STEPS} == $start{$start_best}{$STEPS}) {and subsequent close bracket surrounding the print statement). A path with four steps is:25/25 = 1 25+1 = 26 1+1 = 2 26/2 = 13

I got the code a little more efficient (thanks to the magical ~~ operator in perl) so it could work with a max value of 30 instead of 10, running for a matter of hours, but it's still far less than the 255 in the OP. The answer was surprising.

Perl's dynamic arrays make things easy to program (relatively). This program works if you have a small range that you're working over -- if the maximum value of the numbers is 10 instead of 255 -- but would be horribly inefficient if you wanted to calculate it for 255. It does give an algorithm that would work in principle, though. If there were an easy way of eliminating redundant arrays and repeated terms within arrays (which I imagine there are a bunch of) then it might be feasible for 255.

Roster: Host (Asylum warden): Kikacat123 1. bonanova 2. Flamebirde 3. plasmid 4. 5. 6. 7. 8. 9. 10. 11. 12. Backups: 1. 2.

It looks like this will be more of a programming exercise than anything. And it looks like it won't be all that amenable to a simple greedy algorithm. (It would probably be solved with some sort of greedy algorithm, but not the simple one I'm thinking of.) For example, getting from 1 to 7 would involve 1+1=2 2*2=4 2+1=3 4+3=7 It takes two steps to generate 3 (1+1=2, 2+1=3) and two steps to generate 4 (1+1=2, 2+2=4). But it does not take [two steps to make 3] + [two steps to make 4] + [a step to combine 3 and 4] = 5 steps to generate 7 because the 1+1=2 is shared by the generation of 3 and 4.