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
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)
h <h, ghost wins, returns


Input: Pacman wins!
Output: ____________<

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

Output: ___________________<

Input: Hello World!
Output: <Hello World!

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

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

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

19 Answers 19


Retina, 55 38 bytes


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


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.

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

Jelly, 34 33 bytes


Try it online!

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

  • 5
    \$\begingroup\$ I'd start worrying when you can read it fluently :) \$\endgroup\$ Commented Jul 1, 2016 at 13:59

Python 2, 114 113 108 bytes

for c in s:
 p+=(c in'plePLE')-(c in'ghosGHOS')
 if p<0:break
  • \$\begingroup\$ Your function returns None, not the answer. And how do you count 107? I count 110. \$\endgroup\$ Commented Jul 3, 2016 at 11:18
  • \$\begingroup\$ @StefanPochmann the double-spaces are tabs and its allowed to print the answer rather than returning it \$\endgroup\$
    – Blue
    Commented Jul 3, 2016 at 16:38
  • \$\begingroup\$ @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) \$\endgroup\$ Commented Jul 3, 2016 at 21:26
  • \$\begingroup\$ @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 \$\endgroup\$
    – Blue
    Commented Jul 4, 2016 at 5:59
  • \$\begingroup\$ 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. \$\endgroup\$
    – Arfie
    Commented Jul 4, 2016 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, 53 48 44 bytes

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


Test suite.

  • 17
    \$\begingroup\$ which only people who know Pyth can understand Well, like pretty much the rest of the code, naturally \$\endgroup\$
    – Luis Mendo
    Commented Jun 30, 2016 at 14:43
  • 4
    \$\begingroup\$ @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 \$\endgroup\$ Commented Jun 30, 2016 at 15:01
  • 1
    \$\begingroup\$ @FryAmTheEggman so obviously !!@ is just a trigraph for }, right? :p \$\endgroup\$
    – CAD97
    Commented Jun 30, 2016 at 17:00

MATL, 37 36 35 bytes


Try it online!


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


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#, 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] = '_';
  • 1
    \$\begingroup\$ 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;) \$\endgroup\$
    – CSharpie
    Commented Jun 30, 2016 at 18:35
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Taylor G
    Commented Jun 30, 2016 at 18:51
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Frozn
    Commented Jun 30, 2016 at 21:10
  • 1
    \$\begingroup\$ You can get rid of your c declaration and just inline the s[i] access for 5 characters. \$\endgroup\$
    – user19547
    Commented Jun 30, 2016 at 21:29
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – jpmc26
    Commented Jul 1, 2016 at 0:34

Pyth, 47 46 44 bytes


Try it online. Test suite.

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

  • \$\begingroup\$ Use Z instead of G and change f! to f!h \$\endgroup\$
    – Leaky Nun
    Commented Jun 30, 2016 at 13:19
  • \$\begingroup\$ @LeakyNun Just figured that out in another tab too. Thanks. \$\endgroup\$ Commented Jun 30, 2016 at 13:23
  • 2
    \$\begingroup\$ I think the t in "ghost" should be removed \$\endgroup\$
    – Leaky Nun
    Commented Jun 30, 2016 at 13:35
  • \$\begingroup\$ If we keep golfing our solutions, what is the defining difference between our solutions? \$\endgroup\$
    – Leaky Nun
    Commented Jun 30, 2016 at 13:36
  • \$\begingroup\$ @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? \$\endgroup\$ Commented Jun 30, 2016 at 13:54

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

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


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
  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
    break                  -- stop iterating
    i=i+1                  -- else, increment our score

print(('_'):rep(i)         -- print i*'_'
  ..'<'                    -- appended with Pacman
  ..n:sub(i+1))            -- appended with the remaining characters if we died
  • \$\begingroup\$ Remove d=c:lower() and search for the uppercase characters as well \$\endgroup\$
    – Leaky Nun
    Commented Jun 30, 2016 at 12:46
  • \$\begingroup\$ and 1or s and 1or s s and s \$\endgroup\$
    – Leaky Nun
    Commented Jun 30, 2016 at 12:50
  • \$\begingroup\$ @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 >_< \$\endgroup\$
    – Katenkyo
    Commented Jun 30, 2016 at 12:53
  • \$\begingroup\$ print(('').rep('_',i)..','..z:sub(i+1)) \$\endgroup\$
    – Leaky Nun
    Commented Jun 30, 2016 at 13:03
  • \$\begingroup\$ @LeakyNun I'm working around a similar solution, but the problem comes from the fact that i can be nil \$\endgroup\$
    – Katenkyo
    Commented Jun 30, 2016 at 13:05

Python 3, 176 157 150 149 134 133 124 bytes

Define a function named f which take the string as argument

def f(s):
 for c in s:
  if c in"GgHhOoSs":
   if n:n-=1
  n+=c in"PpEeLl";i+=1

Can be probably be golfed more

Thanks to everyone who commented :D

  • 1
    \$\begingroup\$ ﹐Remove x=c.upper() and search for lowercase matches \$\endgroup\$
    – Leaky Nun
    Commented Jun 30, 2016 at 11:50
  • \$\begingroup\$ 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. \$\endgroup\$
    – Denker
    Commented Jun 30, 2016 at 11:51
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jun 30, 2016 at 11:52
  • \$\begingroup\$ @LeakyNun There is uppercase in the testcases. \$\endgroup\$ Commented Jun 30, 2016 at 11:53
  • \$\begingroup\$ @TùxCräftîñg No, they mean "GgHhOoSs" and "PpEeLl". \$\endgroup\$ Commented Jun 30, 2016 at 11:53

Python 3, 114 110 bytes

My first code golf.

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

while s[x:]*l:l+=(s[x]in y)-(s[x]in f);x+=l>0

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.

  • \$\begingroup\$ 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. \$\endgroup\$
    – DJMcMayhem
    Commented Jul 7, 2016 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}


("Pacman wins!",
"Pacman loses wah-wah :(",
"Hello World!"
) | 
% {
    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 += "_"

Python3, 211 184 bytes

The argument 's' is a string

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

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

Thanks for commenting :)

  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – Denker
    Commented Jul 1, 2016 at 8:27
  • 1
    \$\begingroup\$ You can replace the first return "_"*c + "<" + s[c:] with just a break as that code will be executed after the for loop anyways. \$\endgroup\$
    – Arfie
    Commented Jul 1, 2016 at 12:41
  • \$\begingroup\$ Try it online! I got 183 bytes by the way. Is there a trailing newline you counted? \$\endgroup\$
    – Pavel
    Commented Dec 31, 2016 at 0:03

Haskell, 119 113 Bytes

Thanks to Daniel Wagner for 6 bytes less.

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

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.


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)
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Jul 2, 2016 at 0:15
  • \$\begingroup\$ @Daniel Wagner Nice tip, thanks! \$\endgroup\$
    – MarLinn
    Commented Jul 2, 2016 at 13:13
  • \$\begingroup\$ Can you add a TIO link? I keep getting errors when i try to make it work. \$\endgroup\$
    – Pavel
    Commented Dec 30, 2016 at 23:57

C, 237 bytes

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)
else{for(unsigned i=0;i<=input.length();++i)
    cout << "_";
}return 0;
  • 1
    \$\begingroup\$ Pac-Man's not losing when it's supposed to be. \$\endgroup\$
    – tildearrow
    Commented Jul 2, 2016 at 7:36
  • \$\begingroup\$ Hi @tildearrow, thanks for reviewing my code! I'll update my post. \$\endgroup\$
    – tachma
    Commented Jul 2, 2016 at 17:37
  • \$\begingroup\$ 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 ;. \$\endgroup\$ Commented Jul 2, 2016 at 20:51
  • \$\begingroup\$ @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. \$\endgroup\$
    – tachma
    Commented Jul 3, 2016 at 8:08
  • 1
    \$\begingroup\$ You can look at Tips for C/C++ golfing. \$\endgroup\$ Commented Jul 3, 2016 at 15:10

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

  • 1
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$
    – FlipTack
    Commented Dec 30, 2016 at 22:36

Perl, 54 (52+2) bytes


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


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

  • \$\begingroup\$ iirc flags like -p count as one byte each. \$\endgroup\$
    – Pavel
    Commented Dec 31, 2016 at 0:00
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – hvd
    Commented Dec 31, 2016 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.