16
\$\begingroup\$

Synopsis: Find characters that are enclosed by MYPOCKET.

Example Input

MYPHEIF
YFOCKVH
MBNDEIF
TEUFTMY
ESNDUWP
KBOVUVO
CENWFKC
OPYMTEB

Example Output

F   
BND 
EUF   
SNDUW 
BOVUV 
ENWF  

Huh? How did we get that as an output? The "pocket" can sometimes be difficult to see. This will make it clearer:

MYPHEIF
YFOCKVH
MBNDEIF
TEUFTMY
ESNDUWP
KBOVUVO
CENWFKC
OPYMTEB

The letters in bold indicate a ring of characters connected orthogonally to each other consisting of the string MYPOCKET repeated over and over again. Your program should output the characters that are within that ring.

Notes:

  • There will only be one "pocket".
  • Trailing new lines or spaces after lines are allowed.
  • The rest of the grid may also contain characters from MYPOCKET, but not in a way that makes the shape of the ring ambiguous.
  • The M is not always in the top-right corner.
  • The "pocket" can move in either a clockwise or a counter-clockwise direction.
  • The "pocket" won't move in diagonal directions -- that is, each letter is connected left, right, up, or down to the next.

Here's another input you can test your program with.

Example Input

EKCYMOPD
KCOPHAYM
EKNDSEST
JETHACKE
KRMYPOBN

Example Output

  HA
NDSES
 HA
\$\endgroup\$
  • 14
    \$\begingroup\$ What has it got in its nasty little pocketses? \$\endgroup\$ – Doorknob Aug 11 '15 at 22:54
  • \$\begingroup\$ Was this inspired by this challenge from Anarchy Golf? \$\endgroup\$ – xnor Aug 12 '15 at 5:25
  • \$\begingroup\$ @xnor No, it wasn't. (Although it is somewhat similar...) \$\endgroup\$ – absinthe Aug 12 '15 at 5:46
1
\$\begingroup\$

Perl 5, 414

map{$y=0;push@{$h{$_}},[$-,$y++]for@$_;$-++}@l=map[/./g],<>;sub n{($a,$b,$c,$d)=@_;$a==$c&&1==abs$b-$d||$b==$d&&1==abs$a-$c}sub c{my($x,$y,$n)=@_;for(grep{($f=defined$x)?n$x,$y,@$_:1}@{$h{(MYPOCKET=~/./g)[$n%8]}}){($m,$l)=@$_ if!$f;return@r=([@$_],@r)if$n>2&&n(@$_,$m,$l)||c(@$_,$n+1)}''}c;$l[$_->[0]][$_->[1]]=$" for@r;($l[$_]=join'',@{$l[$_]})=~s/^(\w+)\s|\s(\w+)$/$"x($1||$2)=~y%%%c/eg for 0..@l;print join$/,@l

Usage: save as pocket.pl and run with:

perl pocket.pl <<< '<grid>'

I went for a recursive function to brute-force the path, which might not have been the best, but was the first approach I considered.

Whilst it works for both of the current test cases there are some caveats:

  • it includes leading spaces (which I didn't see mentioned in the rules...); and
  • it will definitely not work with a 'pocket' that contains characters in the middle (say U shaped or similar).

I want to continue working on this, but wanted to show that there is interest in the question! Happy to document my process if helpful.

\$\endgroup\$
5
\$\begingroup\$

Python 2.7 571 542 509

import sys
o,l,v,k,w="MYPOCKET",[list(e)for e in sys.stdin],[],enumerate,len
def f(z,q,t):
 for r,c in(z,q+1),(z,q-1),(z+1,q),(z-1,q):
  if w(l)>r>=0 and 0<=c<w(l[r])and o[t]==l[r][c]:
    v.append((r,c))
    if f(r,c,(t+1)%w(o)):return 1
    else:v.pop()
 if z==1 and(0,q)in v or z==0 and(z,q+1)in v:return 1
for i,x in k(l[0]):
 v=[(0,i)]
 if x==o[0]and f(0,i,1):break
for i in range(1,w(l)-1):b=[y for x,y in sorted(v)if x==i];print"".join(["".join(e)if w(e)>0 else" "for e in[l[i][b[j-1]+1:y]for j,y in k(b)][1:]])

Works as a program(banking on a recursive function) and accepting input from stdin.
Demo here.
Testing it (ex1.txt and ex2.txt are the examples from the question)-

$ python pockets.py < ex1.txt
F
BND
EUF
SNDUW
BOVUV
ENWF
$ python pockets.py < ex2.txt 
  HA 
NDSES
 HA  

Ungolfed version with comments -

s="""
EKCYMOPD
KCOPHAYM
EKNDSEST
JETHACKE
KRMYPOBN
"""
li2=[list(e.strip()) for e in s.split("\n") if e.strip()!='']
buf=[]
def find_precious(row, col, c_ind):
    for r,c in[(row,col+1),(row,col-1),(row+1,col),(row-1,col)]:
        if len(li2)>r>=0 and 0<=c<len(li2[r]) and seq[c_ind]==li2[r][c]:
            if (r,c)in buf:return True
            buf.append((r,c))
            if find_precious(r,c,(c_ind+1)%len(seq)):return True
            else:buf.pop()
    if row==1 and (row-1,col) in buf or row==0 and (row,col+1) in buf:return True
    return False

for i,x in enumerate(li2[0]):
    if x==seq[0]:
        buf=[(0,i)]
        if find_precious(0,i,1):break
if len(buf)==1:
    exit("Failed")

#Calculate the middle men
for i in range(1,len(li2)-1):
    b=[y for x,y in sorted(buf)if x==i]
    print "".join(["".join(e)for e in [li2[i][b[j-1]+1:y]for j,y in enumerate(b)][1:]if len(e)>0])

Let me know, if I did something stupid or something can be done better.
I know it's looong, but it's the best I could do :P

\$\endgroup\$
  • \$\begingroup\$ Eh, I'm so bad at Python I'd probably brute-force it //I don't have any knowledge of lambdas in Python...// but nice solution! Still better than none. \$\endgroup\$ – Kurousagi Aug 13 '15 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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