# aHHHH! The Beasts are HHHHere!

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

1. A pair of integers indicating a map's size in columns then rows.

2. 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.

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

1. aHHHH! if the beasts killed the player...or nothing if the player won with no beasts remaining

2. The 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 Apr 9 '14 at 8:59
• If I'm understanding correctly, the second example is wrong, because pastebin.com/raw.php?i=CqPJPjTR. – Doorknob Apr 9 '14 at 12:25
• @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: pastebin.com/raw.php?i=FENVAkCH Is my assumption correct? – bobbel Apr 9 '14 at 15:44
• Another question: What if you move a train of walls into a beast that isn't 'pinned down'? pastebin.com/raw.php?i=isN4L6pJ – Claudiu Apr 9 '14 at 16:01
• @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. – Dr. Rebmu Apr 9 '14 at 16:26

# Perl 6: 741 characters, 758 bytes

The golfed version is at the bottom, since it's basically linenoise. Above it is my pre-golfed version. Both are interactive (they'll read as many commands from the input file as they can and then move on to using STDIN to get commands). They try to use the original characters and colors.

Usage is like perl6 beast.p6 beast-input:

use Term::ANSIColor;
class BeastGame {
enum BeastParts <None Player Beast M-Wall S-Wall>;

has @.board;
has Int $.turn = 0; has Int$.score = 0;

method indices (\matcher) {
@.board.pairs.map: {
.key*i X+ .value[].pairs.map: {
.key if .value ~~ matcher
}
}
}
multi postcircumfix:<[ ]> (BeastGame \SELF, Complex \c) is rw { SELF.board[c.im][c.re] }

has Complex $!player; method player {$!player = $.indices(Player) } method Bool { so$.indices(Player) & $.indices(Beast) } method new (@lines) { my @board = @lines.map: {[ %(' ',<O H ~ #> Z=> None, Player, Beast, M-Wall, S-Wall){ .comb } ]} self.bless: :@board } method gist { state @symbol-map = map {colored .key, .value~' on_black'}, (' ',<◄► ├┤ ▒▒ ██> Z=> <default cyan red green yellow>); @.board.map({ @symbol-map[@$_].join }).join("\n")
}

method step ($d) { my$direction = %(:W(0), :L(-1+0i), :R(1+0i), :U(-1i), :D(1i)){$d};$direction // return self;
self.move($.player,$direction);

if ++$!turn %% 2 { for$.indices(Beast).eager -> $c { for (-1-1i,-1+0i,-1i,1-1i,1+0i,-1+1i,1+1i,1i,0i)\ .sort({abs$c + $^d -$!player})
{
last if self.move($c,$_).defined;
}
}
}

self;
}
method move ($cur,$by) {
return $cur if$by == 0;

my $to =$cur + $by; my &cur-is = { self[$cur] ~~ $^o } my &next-is = { self[$to]  ~~ $^o } return if cur-is S-Wall; (self[$to], self[$cur]) = (self[$cur], None)
if next-is None
# Move wall
or cur-is Player | M-Wall and next-is M-Wall and self.move($to,$by)
# Kill Player
or cur-is Beast  and next-is Player
# Squish Beast
or cur-is M-Wall and next-is Beast  and self[$to+$by] ~~ M-Wall|S-Wall and $!score += 2 } } my$width = get.words;
my $game = BeastGame.new(lines[^$width]);
my @commands = '',lines.comb,{$*IN.get.comb}...*; while$game {
$game.step: @commands.shift; print "\e[2J"; print "\e[H"; say$game;
}

say "aHHHH!" unless $game.player; say$game.score;


The golfed version:

my ($u,$s,$m)=0,0;my@b=lines[^get.words].map:{[%(' ',<O H ~ #>Z=>^5){.comb}]} my@a='',lines.comb,{$*IN.get.comb}...*;sub g(\c)is rw {@b[c.im][c.re]}
my&n=->\o{@b.kv.map:{$^k*i X+$^v[].kv.map:{$^l if$^w==o}}}
my&p={$m=n(1)} my&M=->$c,$b{my$t=$c+$b;my&c={$^o==g$c}
my&x={$^o==g$t}
c(4)??0!!$b??(($c,$t)».&g=(0,g$c)
if x(0)||c(1|3)&&x(3)&&M($t,$b)||c(2)&&x(1)||c(3)&&x(2)&&2 <g($t+$b)&&($s+=2))!!1} while n(1)&n(2) {for 1 {M p,%(:W(0),:L(-1),:R(1),:U(-1i),:D(1i)){@a.shift}//last;if$u++%2
{for n(2).eager ->$c{last if M$c,$_ for(-1-1i,-1+0i,-1i,1-1i,1+0i,-1+1i,1+1i,1i,0i).sort({abs$c+$_-$m})}}}
say "\e[2J\e[H",join "\n",map {[~]
(map {"\e[$^v;40m$^k\e[0m"},'  ',<39 ◄► 36 ├┤ 31 ▒▒ 32 ██ 33>)[@$_]},@b} say "aHHHH!" if !p;say$s;


Happy Easter!

• It's code golf rules, so given that, your solution wins...even if I don't myself like Perl very much. ;-) Good work with the console and color! – Dr. Rebmu Apr 30 '14 at 1:35

# Java, 1,843

My first try of solving this puzzle with Java. I know, that there are a lot of improvements to make it shorter. But in the end it works for now.

To try it, you have to create a class C and paste the code. args (strictly speaking a) is for input. The print method of the map is not included since it's not necessary for the puzzle output.

class C{static char                    [][]C;static int A=
0,B=0,D=0,E=0,F=0,G                    = 0 ; public static
void main(String[]a                    ){String []b= a.
split("\n");int c =                    Byte. decode(b .
split(" ")); G=a                    [ 0 ] . replaceAll(
"[^H]","").length()                    ; String d = b [ b.
length - 1 ] ;C=new                    char[c][];for(int e
=1;e<b.length-1;e++                    ) C [ e - 1 ]=b[e].
toCharArray ( ) ; f                    ();boolean X= 0> 1;
for ( char  g : d .                    toCharArray ( ) ) {
switch(g){case 'U':                    h(0,-1);break; case
'D':h(0, 1); break;                    case 'L':h( -1, 0);
break;case'R':h(1,0                    );}if(X)i();X=!X;f(
);}System.out.print                    (D);}static void f(
){for(int a= 0;a<C.                    length;a++)for( int
b=0;b<C[a].length;b                    ++)if(C[a][b]=='O')
{A=b;B= a;}}static void h(int x,int y){E =x;F =y;switch(C[
B +y][A +x]){case 'H':g();break;case ' ':j(A,B);break;case
'~':k();}}static void i(){if(G<1){return;}int[][]l=new int
[G][];int m=0;for(int r=0;r<C.length;r++){for(int c=0;c<C[
r].length; c++){if(C[r][c]=='H'){l[m++]=new int[]{c,r};}}}
for(int[]n:l){o(n,n);}} static void o(int a, int b){
int[]c=d (a,b);E=c;F =c;if(E !=0||F !=0){ j(a,b);} }
static int[]d(int a,int b){int[][]d={{1,3,4},{2,0,5},{6,8,
7},};int[]e=new int[]{0,0};double f=999;for(int r=-1;r<2;r
++){for(int c=-1;c<2;c++){if(C[b+r][a+c]==' '||C[b+r][a+c]
=='O'){int g=a+c-A;                    int h=b+r-B; double
i=Math.sqrt(g*g+h*h                    );if(i<f){e=new int
[]{ c,r};f =i;}else                    if(i==f){if(d[r+1][
c+1]<d[e+1][e                    +1]){e=new int[]{c,
r};}}} }}return e;}                    static void k(){if(
p(E,F,false)){q(E,F                    );} }static void q(
int x,int y){switch                    (C[B+y][A+x]){ case
'~':q(x+E,y+F);case                    'H':case ' ':j(A+x-
E,B+y- F);}} static                    boolean p(int x,int
y,boolean h){switch                    (C[B+y][ A+x]){case
' ':return !h; case                    '~':return h?h:p(x+
E,y +F, false);case                    'H':return h?!h:p(x
+E , y+ F, true) ;}                    return h&&C[B+y][A+
x] == '#' ; }static                    void j(int a,int b)
{char c=C[b][a];if(                    C[b+F][a+E]=='O'){g
();}else if(C[b+F][                    a+E]=='H'){D+=2;G--
;c=C[b][a];C[b][a]=                    ' ';}else{C[b][a]=C
[b+F][a+E];}C[b+F][                    a+E]=c;}static void
g () { System .out.                    print("aHHHH!\n"+D)
;     System      .                    exit  ( 0  ) ;  } }


To run it, try for example:

root@host:/cygdrive/c/workspace/project/bin> java C "5 5
> #####
> #O  #
> # ~ #
> #  H#
> #####
> WWDW"
aHHHH!
0
root@host:/cygdrive/c/workspace/project/bin>


Output of the last big scenario one turn before a beast eats the player:

████████████████████████████████████████████████████████████████████████████████
██▓▓            ▓▓  ▓▓▓▓    ▓▓    ▓▓  ▓▓▓▓      ▓▓  ▓▓▓▓        ▓▓  ▓▓  ▓▓▓▓  ██
██▓▓▓▓  ▓▓                    ▓▓▓▓      ▓▓      ▓▓  ▓▓▓▓                  ▓▓  ██
██▓▓██  ▓▓▓▓      ▓▓▓▓▓▓▓▓            ▓▓    ▓▓▓▓▓▓▓▓    ▓▓        ▓▓▓▓▓▓    ▓▓██
██  ▓▓                ▓▓      ▓▓  ▓▓▓▓  ██▓▓▓▓              ▓▓                ██
██▓▓▓▓    ▓▓▓▓▓▓      ▓▓  ▓▓  ▓▓            ▓▓  ▓▓▓▓  ▓▓    ▓▓    ▓▓    ▓▓    ██
██          ▓▓▓▓    ▓▓    ▓▓  ▓▓  ▓▓▓▓▓▓                        ▓▓    ██▓▓    ██
██          ▓▓▓▓    ██    ▓▓▓▓▓▓  ▓▓            ▓▓  ▓▓▓▓    ▓▓    ▓▓  ▓▓▓▓    ██
██              ▓▓  ▓▓  ▓▓▓▓      ▓▓▓▓  ▓▓  ██                ▓▓▓▓      ▓▓    ██
██  ▓▓▓▓                  ▓▓  ▓▓▓▓▓▓    ▓▓▓▓  ├┤  ▓▓▓▓▓▓▓▓            ▓▓    ▓▓██
██▓▓    ▓▓    ├┤◄►▓▓▓▓▓▓├┤  ▓▓      ▓▓                ▓▓      ▓▓  ▓▓▓▓    ▓▓▓▓██
██          ▓▓            ██  ▓▓  ▓▓▓▓    ▓▓▓▓▓▓      ▓▓  ▓▓  ▓▓  ██        ▓▓██
██▓▓  ▓▓  ▓▓▓▓    ▓▓    ▓▓                  ▓▓▓▓    ▓▓▓▓  ▓▓  ▓▓  ▓▓▓▓▓▓      ██
██              ▓▓      ▓▓      ▓▓      ▓▓    ▓▓├┤        ▓▓▓▓▓▓  ▓▓          ██
██  ▓▓▓▓    ▓▓    ▓▓  ▓▓▓▓      ▓▓              ▓▓  ▓▓  ▓▓          ▓▓        ██
██            ▓▓▓▓      ▓▓      ▓▓    ▓▓                  ▓▓            ▓▓▓▓  ██
██▓▓  ▓▓          ██        ▓▓▓▓▓▓▓▓    ▓▓        ▓▓▓▓▓▓        ██  ▓▓        ██
██    ▓▓      ▓▓  ▓▓      ▓▓                ▓▓                    ▓▓▓▓    ▓▓  ██
██    ▓▓      ▓▓          ██▓▓    ▓▓      ▓▓▓▓    ▓▓    ▓▓                  ▓▓██
██  ▓▓▓▓  ▓▓  ▓▓    ▓▓▓▓                                ▓▓      ▓▓            ██
██        ▓▓▓▓▓▓                ▓▓  ▓▓▓▓    ▓▓    ▓▓    ▓▓      ▓▓            ██
██  ▓▓  ▓▓          ▓▓                        ▓▓▓▓      ▓▓      ▓▓    ▓▓      ██
████████████████████████████████████████████████████████████████████████████████


Without silly line spaces: http://pastebin.com/raw.php?i=QhpxKcCT

So the players way is ending after the moves RRDDDRRRWW, because on the last Wait, the beast to the left will go to the right to eat the player.

Another example of the original big map but different moves:

http://pastebin.com/raw.php?i=nBWjC3PZ

See this animation: http://youtu.be/0DIhEhjWd6s

And the last example with original map and different moves (according to the new beast movement rules):

http://pastebin.com/raw.php?i=NNmgzx7U

• HHHa! :-) Very cool. So long as you've gotten it, care to play a few games and give more test case data on that map? – Dr. Rebmu Apr 11 '14 at 1:43
• I've added a new scenario with original map and different moves. But you can't really follow the steps, because I didn't want to paste all 75 steps to pastebin :) – bobbel Apr 11 '14 at 8:50
• So, I added a video to see the result as an animation! – bobbel Apr 11 '14 at 11:29
• Good video...though it seems to show the beasts move too quickly to be any fun! Should we change the rule so they move every other turn instead of every turn? – Dr. Rebmu Apr 11 '14 at 17:57
• I don't mind. About ten bytes more for me! But I totally agree. It's hard to win like it is now :) – bobbel Apr 11 '14 at 18:15

# C - 1004984 917

Ahh, the beauty of C. Following the spirit of the other answer, I tried to format mine as well :)

I imagine there are still some improvements here and there, but this was really fun to write and golf. The character count includes all necessary spaces and new lines.

#define M(y,x,c) {t[y][x]=32;t[p][q]=c;y=p;x=q;}
#define E {printf("aHHHH!\n%d",Z);exit(0);}
#define A sqrt(pow(X-Q,2)+pow(Y-P,2))*30
#define L (char)(m[s]>>8)
#define G (char)(m[s])
#define B(b) if(T==b)
#define J M(Y,X,79)
#define T t[P][Q]

r,c,X,Y,H,i,j,k,Z,p,q,P,Q,u,v,s,w,m,b={
-1,255,65280,65281,1,511,257,256},t,
x,y;main(){char N;m=b;m
=256;m=255; m=1; scanf("%d %d",&c,&r);
for(;P<r;P++)                    for(Q=0;Q<c&&
scanf("%c",&T                    );T-10&&T-13?
Q++:Q){B(79){                    Y=P;X=Q;}B(72
){y[H]=P ;x[H                    ++]=Q;}}scanf
("%s",N);for(                    ;i<strlen(N);
i++){s=N[i];P                    =p=Y+L;Q=q=X+
G;B(32)J B('~')                  {while(P+=L,Q
+=G,T=='~');B                    (72){u=P+L;v=
Q+G;if(t[u][v]                   ==35||t[u][v]
=='~'){Z+=2;T=                   '~';J}}B(32){
T='~';J}}else                    B(72)E if(r=!r)
for(j=0;j<H;j                    ++){P=y[j];Q=
x[j];if(T-72)continue;v=A;s=0;for(k=0;k<8;k++)
{P=y[j]+(char)(b[k]>>8);Q=x[j]+(char)(b[k]);u=
A;B(32)if((c=v-u+99)>s){s=c;q=Q;p=P;}B(79)E}if
(s)M(y[j],x[j],72)}}printf("%d",Z);}//////////


I tested this with all the sample cases and a few more of mine, and it seems to be working properly. If anyone finds any situation in which it doesn't answer properly, please let me know.

Input is from stdin, and output to stdout. There are no checks for incorrect input. And, it returns the score if the player gets eaten, or if the player is alive after all movements are executed (even if there are still H's around.

Ungolfed version:

#define M(y,x,c) {t[y][x]=32;t[p][q]=c;y=p;x=q;}
#define E {printf("aHHHH!\n%d",Z);exit(0);}
#define A sqrt(pow(X-Q,2)+pow(Y-P,2))*30
#define L (char)(m[s]>>8)
#define G (char)(m[s])
#define B(b) if(T==b)
#define J M(Y,X,79)
#define T t[P][Q]

r, c, X, Y, H, i, j, k, Z, p, q, P, Q, u, v, s, w, m, b = { -1, 255,
65280, 65281, 1, 511, 257, 256 }, t, x, y;
main() {
char N;
m = b;
m = 256;
m = 255;
m = 1;
scanf("%d %d", &c, &r);
for (; P < r; P++)
for (Q = 0; Q < c && scanf("%c", &T);T-10&&T-13?Q++:Q) {
B(79) {
Y=P;
X=Q;
}
B(72) {
y[H]=P;
x[H++]=Q;
}
}

scanf("%s", N);
for (; i < strlen(N); i++) {
s = N[i];
P = p = Y + L;
Q = q = X + G;
B(32)
J
B('~') {
while (P += L, Q += G, T=='~');
B(72) {
u=P+L;
v=Q+G;
if(t[u][v]==35||t[u][v]=='~') {
Z+=2;
T='~';
J
}
}
B(32) {
T='~';
J
}
} else B(72)E
if (r = !r)
for (j = 0; j < H; j++) {
P = y[j];
Q = x[j];
if (T-72)
continue;

v = A;
s = 0;

for (k = 0; k < 8; k++) {
P = y[j] + (char) (b[k] >> 8);
Q = x[j] + (char) (b[k]);
u = A;
B(32)
if ((c = v - u + 99) > s) {
s = c;
q = Q;
p = P;
}

B(79)
E
}
if (s)
M(y[j], x[j], 72)
}
}
printf("%d", Z);
}

• Nice!! Though on @bobbel's input RRRUWWWRRRURWWWWRDRRWWRDWWWWD on the big map, you get 6 while he gets 8. He made a video, you could perhaps print each step and look for any anomaly... – Dr. Rebmu Apr 11 '14 at 21:35
• (noticing of course that I changed the rule to make beasts move every-other-turn when I saw how unplayable the beasts-move-every-turn was...!) – Dr. Rebmu Apr 11 '14 at 21:42
• To be honest: I'm not sure, if my solution works 100% properly, too. But it looks like to me :) – bobbel Apr 11 '14 at 21:46
• @Dr.Rebmu I realized you edited the question around the same time I posted mine. So I just did a quick hack that seemingly worked. I'll re-check it this weekend and update it. I'll also post a "nice" version so that any errors could be easier to spot by other people as well :) – Allbeert Apr 12 '14 at 2:48
• FWIW I solved this today in Rebol and am getting @bobbel's answer of 8 as well. – Dr. Rebmu Apr 12 '14 at 22:40