Can Pac-Man Eat This String?

Question

In the arcade version of the game, Pac-Man eats pac-dots. However, in this challenge, he's hungry for alphanumeric characters and punctuation in a string.

Your task is to create a function that feeds Pac-Man a string, evaluates if he can eat it or not, and returns the string with Pac-Man's location in it.

Pac-Man (<) eats characters from left to right, leaving an underscore or space for each character as he goes, and his goal is to get from the first position-1 to the last position+1:

1. <Pac
2. _<ac
3. __<c
4. ___<

However, Pac-Man's natural enemy, the ghost, will stop him if he encounters one of the letters in the word "GHOST" (not case sensitive). Your function should return the string with Pac-Man's location as he encounters the ghost character:

1. <No!
2. _<o!

The only thing that can defeat a ghost is a power pellet. If Pac-Man reaches a letter in the word "PELLET" (also not case sensitive) before coming to a ghost, he will eat the ghost and keep moving, and that pellet will be used up. Power pellets can stack (ie, in ppgg both ghosts would be eaten). The T character exists as both as a ghost and a pellet, so it can be ignored (treated as any other letter, like a).

1. <Pop
2. _<op
3. __<p
4. ___<

To further clarify, in the string "Pac-Man loses here", the following operations occur:

P <P, +1 Pellet (1 pellet)
a <a
c <c
- <-
M <M
a <a
n <n
  <[space]
l <l, +1 Pellet (2 pellets)
o <o, -1 Pellet (1 pellet)
s <s, -1 Pellet (0 pellets)
e <e, +1 Pellet (1 pellet)
s <s, -1 Pellet (0 pellets)
  <[space]
h <h, ghost wins, returns
e
r
e

Examples

Input: Pacman wins!
Output: ____________<

Input: Pacman loses wah-wah :(
Output: _______________<h-wah :(

Input: PELLET PELLET GHOST
Output: ___________________<

Input: Hello World!
Output: <Hello World!

Input: <_!@12<_<_<
Output: ___________<

This is code-golf--lowest score in bytes wins.

Answer 1

Jelly, 34 33 bytes

Œl“ʋʋ“ṁḍ»ċ€Ð€IF+\‘0ṭi0ð’”_×;”<;ṫ@

Try it online!

I think I'm finally starting to understand Jelly. Feels a bit scary.

Answer 2

Retina, 55 38 bytes

i`^(([elp])|[^ghos]|(?<-2>.))*
$.&$*_<

Try it online! (The first line just allows running several test cases at once.)

Explanation

The problem is essentially to find the longest prefix that doesn't have an unmatched closing parenthesis. Except that we can use either e, l or p in place of ( and either g, h, o or s in place of ).

Hence, this solution is almost a textbook example of balancing groups. I won't go into too much detail about how they work, as this code is essentially the same as the standard example you can read up on in my SO answer on balancing groups.

The entire program is therefore a single regex substitution. The i activates case-insensitivity. Then we either match a pellet with [elp] and increment the depth counter (in the form of the capture stack of group 2), or we match something that isn't a ghost with [ghos] or we match a ghost with . and decrement the depth counter by popping from stack 2. Of course, in principle this allows matching a pellet with the [^ghos] section or a non-ghost with the . section, but thanks to greedy matching and the way the regex is backtracked, these possibilities are never attempted by the regex engine.

The substitution then uses two Retina specific features: $* repeats the character to its right as many times as specified by the token on its left. That token is $.& which is the length of the entire match. This just means that we replace each character in the match with a _. And then we also append a < to those underscores. The part of the input that isn't eaten simply remains unaffected by the substitution.

Answer 3

Python 2, 114 113 108 bytes

s=raw_input()
p=i=0
for c in s:
 p+=(c in'plePLE')-(c in'ghosGHOS')
 if p<0:break
 i+=1
print'_'*i+'<'+s[i:]

Answer 4

Python 2, 89 bytes

Sometimes my stubborn determination to make Python a functional language has its benefits.

def f(s,l=1):l+=(s[:1]in'plePLE')-(s[:1]in'ghosGHOS');return s*l and'_'+f(s[1:],l)or'<'+s

(Slightly) ungolfed:

def f(s, l=1):
    l += (s[:1] in 'plePLE') - (s[:1] in 'ghosGHOS')
    return (s * l) and ('_' + f(s[1:], l)) or ('<' + s)

Builds up the result string using recursion. The update to l (for "lives") adds 1 for pellets (True - False == 1), subtracts 1 for ghosts (False - True == -1), and adds 0 for any other character. It also adds 0 when s is the empty string, thanks to Python's slicing and the fact that '' in any_str == True, so the pellet and ghost cancel.

The return statement uses test and b or a in place of a if test else b to save one byte. The recursion base case occurs when either the string ends or Pac-Man runs out of pellets, succinctly represented as s*p, which equals '' (and therefore evaluates to false) when either s == '' or p == 0.

Answer 5

Pyth, 53 48 44 bytes

4 bytes thanks to @Pietu1998 for the !!@ -> } trick (which only people who know Pyth can understand)

++*Jf<@+sM._m-!!@d"PELpel"!!@d"GHOSghos"Q_1T00\_\<>QJ
++*Jf<@+sM._m-!!@d"PEL"!!@d"GHOS"rQ1_1T00\_\<>QJ
++*Jf<@+sM._m-}d"PEL"}d"GHOS"rz1_1T00\_\<>zJ

Test suite.

Answer 6

MATL, 37 36 35 bytes

tkt'ghos'mw'pel'm-Ys1=Y>&)g95*60bhh

Try it online!

Explanation

tkt      % Input string implicitly. Duplicate, convert to lower case, duplicate
'ghos'm  % True for "ghost" characters
w'pel'm  % Swap to bring lowercase copy to top. True for "pellet" characters
-Ys      % Subtract, cumulative sum. Pac-Man can reach until the first "1"
1=       % True for entries that equal 1
Y>       % Cumulative maximum. This gives false until the first true is found, and
         % true from there on
&)       % Split original string in two parts, given by the zeros and ones respectively
g95*     % Convert the first part into ones and multiply by 95. This gives a numerical
         % array containing number 95 (ASCII for '_')
60       % Push 60 (ASCII for '<')
b        % Bubble up second part of original string
hh       % Concatenate the three strings/arrays, automatically converting to char

Answer 7

C#, 269 256 232 212 211 Bytes

First ever post on here, so this is probably a lot longer than it could be (and probably because it is in C#). Any tips on where I could shorten it would be great!

Thank you to everyone in the comments who helped me!

Golfed version

static void p(string x){int p=0,i=0;string t='<'+x;var s=t.ToCharArray();for(;++i<s.Length;){if("PELpel".Contains(s[i]))p++;if("GHOSghos".Contains(s[i])&&--p<0)break;s[i]='<';if(i>0)s[i-1]='_';}Console.Write(s);}

Ungolfed version

static void p(string x) {
 int p = 0, i = 0;
 string t = '<' + x;
 var s = t.ToCharArray();
 for (; ++i < s.Length;) {
  if ("PELpel".Contains(s[i])) p++;
  if ("GHOSghos".Contains(s[i]) && --p < 0) break;
  s[i] = '<';
  if (i > 0) s[i - 1] = '_';
 }
 Console.Write(s);
}

Answer 8

JavaScript (ES6), 98 bytes

s=>s.replace(/./g,c=>p<0?c:(p+=/[elp]/i.test(c)-/[ghos]/i.test(c))<0?"<"+c:"_",p=0)+"<".slice(p<0)

Explanation: p maintains the current number of pellets. If it's already negative, we just return the character and move on, so that the rest of the string is untouched. Otherwise, we examine the current character, and if that makes p become negative, we insert the < character, otherwise we replace the current character with _. Finally, if p never becomes negative, we suffix a < to the string.

Answer 9

Lua, 198 190 184 185 163 Bytes

Ok, I admit, this is long. Very long. Lua has some tools to play around with strings, but it is limited, same goes for conditionals that takes lots of spaces.

Edit: thanks @LeakyNun for saving me 9 bytes :) Lost some bytes to fix a bug

Edit 2: 163 Bytes solution found by @LeakyNun

i=0p=0n=...for c in n:gmatch"."do
p=p+(c:find"[ghosGHOS]"and-1or c:find"[pelPEL]"and 1or 0)if p<0then
break else i=i+1 end end print(('_'):rep(i)..'<'..n:sub(i+1))

Old 185

p=0z=(...):gsub(".",function(c)p=p+(c:find"[ghosGHOS]"and-1or
c:find"[pelPEL]"and 1or 0)s=p<0 and 1or s
return s and c or'_'end)_,i,s=z:find"(_+)"print((s or'')..'<'..z:sub(1+(i or 0)))

Ungolfed

i=0                        -- number of characters eaten
p=0                        -- pellet counter
n=...                      -- shorthand for the argument
for c in n:gmatch"."       -- iterate over each characters in the input
do
  p=p+(c:find"[ghosGHOS]"  -- if the current char is a GHOST
        and-1              -- decrement the pellet counter
      or c:find"[pelPEL]"  -- if it's a PELLET
        and 1              -- increment it
      or 0)                -- else, leave it alone
  if p<0                   -- if we try to eat a ghost without pellet
  then 
    break                  -- stop iterating
  else
    i=i+1                  -- else, increment our score
  end
end

print(('_'):rep(i)         -- print i*'_'
  ..'<'                    -- appended with Pacman
  ..n:sub(i+1))            -- appended with the remaining characters if we died

Answer 10

Pyth, 47 46 44 bytes

++*\_Kh+f!h=+Z-}Jr@zT0"pel"}J"ghos"Uzlz\<>zK

Try it online. Test suite.

Quite a different approach from Leaky Nun's, and I'm quite sure this can be golfed further.

Answer 11

Python 3, 176 157 150 149 134 133 124 bytes

Define a function named f which take the string as argument

def f(s):
 n=i=0
 for c in s:
  if c in"GgHhOoSs":
   if n:n-=1
   else:break
  n+=c in"PpEeLl";i+=1
 return"_"*i+"<"+s[i:]

Can be probably be golfed more

Thanks to everyone who commented :D

Answer 12

Python 3, 114 110 bytes

My first code golf.

Thanks to Dr Green Eggs and Iron Man for saving 4 bytes.

l,x=1,0
f,y,s="ghosGHOS","pelPEL",input()
while s[x:]*l:l+=(s[x]in y)-(s[x]in f);x+=l>0
print("_"*x+"<"+s[x:])

Utilises the evaluation of booleans to one and zero to condense a logical AND to a multiplication. (0*0=0, 1*0=0, 1*1=1). I hope this is a good first try.

Answer 13

Ruby, (119 bytes)

q=i=0;a=$**" ";a.split(//).each{|c|q+=((c+?p=~/[ple]/i)^1)-((c+?g=~/[ghos]/i)^1);q<0?break : i+=1};p ?_*i+?<+a[i..-1]

There is probably some things i'm missing as I am new to this...

Ruby is my friend :)

Answer 14

Haskell, 119 113 Bytes

Thanks to Daniel Wagner for 6 bytes less.

p=(0!)
n!(c:s)|elem c"ghosGHOS"=if n<1then '<':c:s else(n-1)&s|elem c"elpELP"=(n+1)&s|0<1=n&s
_!_="<"
n&s='_':n!s

Call it as p "Hello World!".

The 1then is an edge case that is interpreted correctly in my GHC (7.10), but it throws of most syntax highlighters. So it might be interpreted differently in your compiler as well.

Ungolfed:

pacman string = go 0 string

-- | In the golfed version: (!)
go _   []                   = "<"                            -- won
go pellets (char:string)
 | char `elem` "ghosGHOS"
 = if pellets < 1        then '<':char:string                -- lost
                         else nextStep (pellets - 1) string  -- ghost
 | char `elem` "elpELP"
 =                            nextStep (pellets + 1) string  -- pellet
 | otherwise
 =                            nextStep  pellets      string  -- anything else

-- | In the golfed version: (&)
nextStep pellets string = '_':(go pellets string)

Answer 15

C, 237 bytes

#include<stdio.h>
#include<string.h>
main(p,i,j){char s[99];fgets(s,99,stdin);for(p=i=0;s[i];++i){if(strchr("GHOSghos",s[i])){if(p)p--;else break;}else if(strchr("PELpel",s[i]))p++;}j=i-(s[i]==0);while(j--)printf("_");printf("<%s",s+i);}

Answer 16

Python3, 211 184 bytes

The argument 's' is a string

def f(s):
    p=c=0
    for i in s:
        if i in "gGhHoOsS":
            if p<1:break
            else:p-=1
        if i in "pPeElL":p+=1
        c+=1
    return"_"*c + "<" + s[c:]

I would appreciate any golfing tips as this is my first code golf attempt

Thanks for commenting :)

Answer 17

C++, 315 373 327 Bytes

(Note: still golfing)

#include <iostream>
#include <string>
using namespace std;
int main(){string input;getline(cin, input);
if(input.find("Pac-Man loses")!=string::npos||input.find("Pacman loses")!=string::npos)
    cout<<"<"<<input.substr(15,input.length()-1);
else{for(unsigned i=0;i<=input.length();++i)
    cout << "_";
cout<<"<";
}return 0;
}

Answer 18

Powershell, 185

{$l=1;$o="";for($i=0;($i -lt $_.Length) -or (($o+="<") -and 0); $i++){if ($_[$i] -match '[pel]'){$l++}if($_[$i] -match '[ghos]'){$l--}if(!$l){$o+="<"+$_.substring($i);break}$o+="_"}$o}

Ungolfed:

("Pacman wins!",
"Pacman loses wah-wah :(",
"PELLET PELLET GHOST",
"Hello World!"
) | 
% {
    $l=1;$o="";
    for($i = 0; ($i -lt $_.Length) -or (($o+="<") -and 0); $i++) {
        if ($_[$i] -match '[pel]') { $l++ }
        if ($_[$i] -match '[ghos]') { $l--}
        if (!$l) { $o+="<"+$_.substring($i); break }        
        $o += "_"
    }
    $o
}

Answer 19

Perl, 54 (52+2) bytes

s/([pel](?1)*[ghos]|[^ghos
])*/'_'x(length$&).'<'/ei

Needs -p to be specified in the command-line options.

Explanation:

The -p option causes the statement to be wrapped in a read-modify-print loop, where during each loop iteration, $_ contains a line of input, including the line delimiter.

The regex is largely the same idea as in the Retina answer.

Call the search pattern ([pel](?1)*[ghos]|[^ghos ])* "acceptable". Then it can be recursively defined as:

A string is "acceptable" if:

• It is a character in PELLET except for T, followed by an acceptable string, followed by a character in GHOST except for T.
• It is a character not in GHOST except for T that is not a newline character.
• It is a concatenation of any number (including 0) of acceptable strings.

This definition allows more pellets than ghosts: a PEL character may be matched as either a pellet character, or a non-ghost character.

The empty string is considered acceptable, therefore the regex is guaranteed to match at position 0, where the longest acceptable substring will be matched.

This longest acceptable substring is then matched by underscores of equal length, followed by <.