19
3
As we learned from the IBM PC AT, YouTube (see video), Wikipedia (see article), and Sesame Street:
The letter H
is the most merciless letter of the alphabet!
(Even when actually composed from two elements in Code Page 437. In fact, it's even MORE merciless that way.)
Like the Aliens in, uhm...er... Aliens, Beasts relentlessly pursue all who would dare come near their eggs. There is no reasoning with them. You must squash them if not to perish.
For this scenario we will assume you're down to your last life, and you've met plain Beasts in a terrain with no eggs (as in the Wikipedia screenshot). You don't have a numeric keypad and can only move directly up/down/left/right...but the beasts apparently have one, and can move diagonally on their turn.
A Beast's choice of move among its options will be the one that minimizes distance from the player. If the distances are equal then tie breaking is done favoring left+up over right+down, but here's the disambiguation matrix to be explicit about it...lowest number to tie-break:
1 3 4
2 H 5
6 8 7
A beast never sleeps, but they are fortunately a bit slower than the player. They move every other turn (giving the player a head start by beginning their alternations on the second turn). They must move if a move is possible, regardless of if that takes them further from the player.
You crush a beast if you move a train of movable walls where it was sitting in a closed gap. These plain beasts are worth 2 points a head.
Input
A pair of integers indicating a map's size in columns then rows.
Row count of lines of input, each of the column size...containing either a solid wall (
#
), a movable wall (~
), a beast (H
), the player (O
) or just a space.Input that will be either U, D, L, R indicating an attempted move by the player... or W to just wait. Note that attempting to push a movable wall which is blocked is legal input, it just will result in no action.
Output
aHHHH!
if the beasts killed the player...or nothing if the player won with no beasts remainingThe score
(Note: For debugging purposes and/or amusement, you'll probably want to be able to output the state at each step; but that's too long to post here.)
Clarifications
Maps are guaranteed to be bounded by solid walls.
The order of who moves in a turn matters for the outcome. Thus: The player always goes first, then the beasts are given an ordering based on their initial map position if you were sweeping across the screen top to bottom left to right. (A row 1 beast moves before a row 2 beast, and two beasts on the same row it would be the one with the lowest column number that would move before the other)
Diagonal moving beasts can move into any open adjacent diagonal space, regardless of if it requires squeezing between walls.
A player can push any number of movable walls in a line provided that there's a space or a beast on the other end. But trying to push a train of walls into a Beast that is not pinned between walls treats the Beast as a wall, and won't allow the move.
A Beast's move decision during a turn is based on the player's location at the beginning of the turn. Its desired optimization of "distance to player" is through an "as the crow flies" calculation. Any approximation which would give the same result as measured from the center of its square to the center of the player's square is fine.
If a Beast can't make what would have been its first preferred move in a turn because a higher priority Beast took its spot, it will take its next best choice as opposed to staying in place (if a move is still possible).
Sample Cases
Simple Crush
Input
5 3
#####
#O~H#
#####
R
Output
2
Preference Matrix -> Death
Input
5 5
#####
#O #
# ~ #
# H#
#####
WWDW
Output
aHHHH!
0
Preference Matrix -> Win
Input
5 5
#####
#O #
# ~ #
# H#
#####
WRD
Output
2
Waiting For the Reaper
Input
5 5
#####
#O #
# ~ #
# H#
#####
WWW
Output
aHHHH!
0
Successful Defeat in the Wikipedia Scenario
Input
40 23
########################################
#~ ~ ~~ ~ ~ ~~ ~ ~~ ~ ~ ~~ #
#~~ ~ ~~ ~ ~ ~~ ~ #
#~# ~~ ~~~~ ~ ~~~~ ~ ~~~ ~#
# ~ ~ ~ ~~ #~~ ~ #
#~~ ~~~ ~ ~ ~ ~ ~~ ~ ~ ~ ~ #
# ~~ ~ ~ ~ ~~~ H ~ #~ #
# O~ ~ # ~~~ ~ ~ ~~ ~ ~ ~~ #
# ~ ~H~~ ~~ ~ # ~~ ~ #
# ~~ ~ ~~~ ~~ ~~~~ ~ ~#
#~ ~ ~~~ ~ ~ ~ ~ ~~ ~~#
# ~ # ~ ~~ ~~~ ~ ~ ~ # ~#
#~ ~ ~~ ~ ~ H ~~ ~~ ~ ~ ~~~ #
# ~ ~ ~ ~ ~ ~~~ ~ #
# ~~ ~ ~ ~~ ~ ~ ~ ~ ~ #
# ~~ ~ ~ ~ ~ ~~ #
#~ ~ # ~~~~ ~ ~~~H # ~ #
# ~ ~ ~ ~ ~ ~~ ~ #
# ~ ~ #~ ~ ~~ ~ ~ ~#
# ~~ ~ ~ ~~ ~ ~ #
# ~~~ ~ ~~ ~ ~ ~ ~ #
# ~ ~ ~ ~~ ~ ~ ~ #
########################################
RRRUWWWRRRURWWWWRDRRWWRDWWWWD
Output
8
Map provided by me, moves and output by @bobbel, corroborated by myself and @Allbeert.
Winning Criteria
I think this is golfable, so I'll go with code golf rules unless people complain.
Extra Credit
Playable Unicode implementation with the double-wide characters to resemble the image!
Do diagonal movements jump over antidiagonal lines of walls? Given that a beast makes a move every turn, how does it break distance ties between two horizontal moves or two vertical moves? Does it move towards where the player was at the start of the turn, or after the player's movement? When you say "train of movable walls", does that mean that the player can push any number of movable walls in a line provided that there's a space or a beast on the other end? – Peter Taylor – 2014-04-09T08:59:57.973
@PeterTaylor Yes you can push any number of walls as long as it's a space or Beast on the other end. Though I had to watch the video again to make sure they could squeeze between walls, and they can. :-) Clarified. The distance calculation is "as the crow flies" and they decide their move on the position at the beginning of the turn. – HostileFork says dont trust SE – 2014-04-09T09:10:02.520
The point of the question about tie-breaking was that if you have
O #H
then the beast can't move towards the player so has to move either up or down, and the symmetry needs breaking. – Peter Taylor – 2014-04-09T09:30:42.583@PeterTaylor Right... I thought that was clarified by the sample data and the "horizontal favoritism => death" vs "horizontal favoritism => win"... by the rule A Beast's choice of move among its options will be the one that minimizes distance from the player, favoring a horizontal move over a vertical one if both are equal. Er... or not? – HostileFork says dont trust SE – 2014-04-09T09:59:45.267
You've given the tie-breaker between a horizontal move and a vertical move. What is the tie-breaker between "move left" and "move right"? What is the tie-breaker between "move up" and "move down"? What is the tie-breaker between "move up-left" and "move up-right"? Etc. – Peter Taylor – 2014-04-09T10:33:07.287
@PeterTaylor Ah, it got more complicated with the diagonal moves, but yes. :-) Okay, a preference matrix added, but suggestions welcome if that's not a good one. – HostileFork says dont trust SE – 2014-04-09T10:52:18.217
Another question: what, if a Beast is directly to the right of the player, and the player moves one up? Should the Beast just move one to the left, because the Beast was calculating with the players start position of this turn? Or should the Beast move left-up? (question according to: *then the beasts are given an ordering based on their initial map position*) – bobbel – 2014-04-09T11:52:37.373
2
If I'm understanding correctly, the second example is wrong, because http://pastebin.com/raw.php?i=CqPJPjTR.
– Doorknob – 2014-04-09T12:25:44.407@Doorknob: actually the player goes first. So the player moves down first, then the beast chooses it's move, which is to move left and eat the hapless hero. Hmm in that case the third example would be wrong ... Also in the reaper example it should only require three waits to get eaten I think – Claudiu – 2014-04-09T14:08:48.987
@Claudiu: the reaper example is in fact wrong... it's only 3 times
– bobbel – 2014-04-09T14:34:48.410W
(for the beast: L, L-U, U). But the Win example is correct, since the player moves first! So before the beast can do it's second move, the player gooifies the beast! (http://pastebin.com/raw.php?i=47A8Hre7)@bobbel: Why would the beast move left on its first move? Instead it would move up since that would bring it closer (sqrt 2 distance instead of 2 distance) – Claudiu – 2014-04-09T14:35:28.620
@Claudiu: because, like Doorknob also explained, the beast will decide it's next step according to the players initial position of the current turn. This is also, what I guessed that OP meant. – bobbel – 2014-04-09T14:39:18.220
@bobbel: Oh yes, I missed that, my mistake. – Claudiu – 2014-04-09T14:46:47.090
@Claudiu Yes, the beasts moving diagonal clarification changed the example... Just 3 waits! Tx, fixed. – HostileFork says dont trust SE – 2014-04-09T15:23:02.343
@bobbel Ah yes, sorry, editing on phone. That'd be correct. Changed to down-wait as better examples not feasible to type :) – HostileFork says dont trust SE – 2014-04-09T15:37:54.437
1
@Dr.Rebmu: generally I like your task very much, but there are many questions to ask for. Thanks for clarifying! So, next: what about this Two-Beast situation: http://pastebin.com/raw.php?i=FENVAkCH Is my assumption correct?
– bobbel – 2014-04-09T15:44:40.8631
Another question: What if you move a train of walls into a beast that isn't 'pinned down'? http://pastebin.com/raw.php?i=isN4L6pJ
– Claudiu – 2014-04-09T16:01:42.703@Claudiu Ahh...you're straining my memory, and the video can't really help with that one since there's no visual way to see the keystrokes. But I don't think you can push beasts, just crush them. Let's assume they are walls in that case...clarified. – HostileFork says dont trust SE – 2014-04-09T16:21:52.077
3@bobbel Man, writing questions is harder than solving them! :-) I say given the Beasts propensity for not staying still, they will take their next best move if available instead of foregoing their move that turn, if a higher priority Beast took their ideal spot. Clarified. – HostileFork says dont trust SE – 2014-04-09T16:26:33.510
Don't worry, to golf this puzzle is a big challenge too. Or who can beat currently about 2,050 bytes? :D By the way: the output of the last scenario is also:
aHHHH!\n0
– bobbel – 2014-04-10T14:40:55.820should 'We all know
H
is the most merciless letter of the alphabet' not be 'We all know├┤
is the most merciless letter of the alphabet'? – kitcar2000 – 2014-05-03T12:41:43.527