# Can Pac-Man Eat This String?

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.

• So the pellets have no expiration date? – Rɪᴋᴇʀ Jun 30 '16 at 11:42
• Are trailing tabulations accepted in the output? – Katenkyo Jun 30 '16 at 11:50
• +1 for the fact that "here" is where pacman loses. Clever test case. – Olivier Dulac Jun 30 '16 at 17:06
• > [I]n this challenge, he's hungry for alphanumeric characters and punctuation in a string. ... Yacc-man? – Kaz Jul 1 '16 at 1:13
• Now I see a camouflaged grey pacman with black lips every time i look at the < symbol... – QBrute Jul 1 '16 at 5:49

# Jelly, 34 33 bytes

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


Try it online!

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

• I'd start worrying when you can read it fluently :) – quetzalcoatl Jul 1 '16 at 13:59

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

• Nice abuse of capturing groups! – Leaky Nun Jun 30 '16 at 11:45
• @LeakyNun Abuse? That's what balancing groups are made for. :D – Martin Ender Jun 30 '16 at 11:45
• Hey look, a Retina answer that looks remotely like the regex I use – cat Jun 30 '16 at 14:47

# Python 2, 114113 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:]

• Your function returns None, not the answer. And how do you count 107? I count 110. – Stefan Pochmann Jul 3 '16 at 11:18
• @StefanPochmann the double-spaces are tabs and its allowed to print the answer rather than returning it – Blue Jul 3 '16 at 16:38
• @muddyfish Ah, thanks. They don't seem to be tabs here, though, not even when I go to "edit". And the problem clearly states "return"... are there site-wide rules overruling it or so? (I'm pretty new here and don't know) – Stefan Pochmann Jul 3 '16 at 21:26
• @StefanPochmann tabs are eaten by SE (normally converted to 4 spaces). Unless explicitly stated printing in a function is allowed. The OP probably didn't mean to override this though – Blue Jul 4 '16 at 5:59
• I think it's reasonable to say that it should always either return if it's a function or read from stdin and print. I'll change to reading from stdin, which should be shorter anyway. – Arfie Jul 4 '16 at 8:31

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

# Pyth, 5348 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.

• which only people who know Pyth can understand Well, like pretty much the rest of the code, naturally – Luis Mendo Jun 30 '16 at 14:43
• @LuisMendo To be fair to people who don't know Pyth, I'm pretty sure most of them could understand that the set intersection between one singleton set and another set having any members is equivalent to the singleton set's member being a member of the larger set :P – FryAmTheEggman Jun 30 '16 at 15:01
• @FryAmTheEggman so obviously !!@ is just a trigraph for }, right? :p – CAD97 Jun 30 '16 at 17:00

# MATL, 3736 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


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

# C#, 269256232212 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);
}

• You can replace types in variabledeclerations using the var-keyword. e.g. var temp = ' ' + input; The for loop can be rewritten to save 4 chars: for(var i = 0; i++ < s.Length;) – CSharpie Jun 30 '16 at 18:35
• You can use commas to declarations "int i=0,p=0;string P="PELpel",G="GHOSghos",t=' '+x;" and the change from @CSharpie, making the loop "for(;i++<s.Length;)". Additionally, you can "Console.Write(s);" directly for a total of 235 bytes. – Nickson Jun 30 '16 at 18:51
• I think it should also work without the else saving 5 more characters. And by starting the loop at i = 1 you should be able to remove the last if as the code can be executed every time. – Frozn Jun 30 '16 at 21:10
• You can get rid of your c declaration and just inline the s[i] access for 5 characters. – user19547 Jun 30 '16 at 21:29
• Is it worth assigning P="PELpel" and G="GHOSghos"? You only use them once each. Am I missing something, or is that just 4 extra characters? Also, do you need the else? "PELpel".Contains(c) and "GHOSghos".Contains(c) should be mutually exclusive. – jpmc26 Jul 1 '16 at 0:34

# Pyth, 4746 44 bytes

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


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

• Use Z instead of G and change f! to f!h – Leaky Nun Jun 30 '16 at 13:19
• @LeakyNun Just figured that out in another tab too. Thanks. – PurkkaKoodari Jun 30 '16 at 13:23
• I think the t in "ghost" should be removed – Leaky Nun Jun 30 '16 at 13:35
• If we keep golfing our solutions, what is the defining difference between our solutions? – Leaky Nun Jun 30 '16 at 13:36
• @LeakyNun I'm not sure which of these is closer, but my first attempt got me 43 bytes, and I don't think I need to add a third answer. Maybe we should work together in the Pyth chatroom? – FryAmTheEggman Jun 30 '16 at 13:54

## Lua, 198190184185 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

• Remove d=c:lower() and search for the uppercase characters as well – Leaky Nun Jun 30 '16 at 12:46
• and 1or s and 1or s s and s – Leaky Nun Jun 30 '16 at 12:50
• @LeakyNun didn't see that would be shorter to just write all letters... Thanks. Also, the second comment mentioned something I changed, but only in the ungolfed >_< – Katenkyo Jun 30 '16 at 12:53
• print(('').rep('_',i)..','..z:sub(i+1)) – Leaky Nun Jun 30 '16 at 13:03
• @LeakyNun I'm working around a similar solution, but the problem comes from the fact that i can be nil – Katenkyo Jun 30 '16 at 13:05

## Python 3, 176157150149134133 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

• ﹐Remove x=c.upper() and search for lowercase matches – Leaky Nun Jun 30 '16 at 11:50
• You can save some by writing some expressions on the same line separated by a ; rather than having each on its own line. Also you can use Python 2 which allows you to use spaces as first intendation level and tabs as second one. – Denker Jun 30 '16 at 11:51
• n=i=0, not n=0 and i=0. t[i]="_" instead of t[i] = "_", the same for t[i] = "<". return''.join(t), remove that space. – Erik the Outgolfer Jun 30 '16 at 11:52
• @LeakyNun There is uppercase in the testcases. – TuxCrafting Jun 30 '16 at 11:53
• @TùxCräftîñg No, they mean "GgHhOoSs" and "PpEeLl". – Erik the Outgolfer Jun 30 '16 at 11:53

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

• Nice answer, and welcome to the site! Which version of python are you using? You might want to specify that. Also, I haven't tested it, but you might be able to do while s[x:]*l to take off 4 bytes. – James Jul 7 '16 at 8:21

# 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
}


# 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 :)

• Welcome to Programming Puzzles & Code Golf! Some tips:There are a lot of unneccessary whitespaces between operators. Removing them would save a good amount of bytes. Also you can use Python 2, which allows you to use spaces as first intendation level and tabs for the other ones. – Denker Jul 1 '16 at 8:27
• You can replace the first return "_"*c + "<" + s[c:] with just a break as that code will be executed after the for loop anyways. – Arfie Jul 1 '16 at 12:41
• Try it online! I got 183 bytes by the way. Is there a trailing newline you counted? – Pavel Dec 31 '16 at 0:03

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)

• You can save a few bytes by putting all the guards on the same line, e.g. n!(c:s)|elem c"blah"=blah|elem c"blah"=blah|0<1=blah. – Daniel Wagner Jul 2 '16 at 0:15
• @Daniel Wagner Nice tip, thanks! – MarLinn Jul 2 '16 at 13:13
• Can you add a TIO link? I keep getting errors when i try to make it work. – Pavel Dec 30 '16 at 23:57

# 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);}


# 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;
}

• Pac-Man's not losing when it's supposed to be. – tildearrow Jul 2 '16 at 7:36
• Hi @tildearrow, thanks for reviewing my code! I'll update my post. – tachma Jul 2 '16 at 17:37
• I think this can be golfed more. Try removing newlines/spaces after if(), and removing spaces around !=, ||, =, -, and <=. Also, doesn't cin>>input work instead of getline? You can also condense around ;. – NoOneIsHere Jul 2 '16 at 20:51
• @NoOneIsHere, thanks for your comment! I'm actually new to code-golfing, so I'll try to golf my code some more and update my post. If you have any other helpful advice on code-golfing, I'd really appreciate it. – tachma Jul 3 '16 at 8:08
• You can look at Tips for C/C++ golfing. – NoOneIsHere Jul 3 '16 at 15:10

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 :) • Welcome to PPCG! – FlipTack Dec 30 '16 at 22:36 # 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 <.

• iirc flags like -p count as one byte each. – Pavel Dec 31 '16 at 0:00
• @Pavel It's complicated. If the normal invocation without -p already used -, e.g. perl -e -> perl -pe, then the - is free. But I think the perl -e` version is longer because of quoting, so I think I cannot use that here. – hvd Dec 31 '16 at 0:14