Baba is golf, flag is win

Question

If you haven't played the game Baba is You, I think you really should. Whether you’ve played it or not, have a go at implementing it as a code golf.

The idea behind this challenge is to have a bit more complicated, non-standard task with a bit longer answers.

Game rules

Alas, the challenge is not to implement the entire game, impressive though that may be (I'm sure there is a single 05ab1e instruction for it. If not, someone should submit an issue. It's a gross omission from the language 😉). This will be a simplified version of the game:

• There are only 3 entities: Baba, Rock and Flag and the corresponding nouns (lowercase baba, rock and flag)
• There is only one operator - is
• There are only 3 properties: you, win and push
• Everything is always stop (N.b. stop is not a property which exists on the board) This prevents anything from overlapping and makes the management of the game grid simpler.
• Because everything is always stop, there is an alternate win condition. You can win if:
  • noun is you and noun is win -- just like in the original
  • noun which is you attempts to push something which is win, but that something cannot move (whether because it's not push, or it is push and is somehow blocked form moving). See examples for more details.
• Just like in the main game text (nouns you, win and push and the operator is) are always push
• There is only one level. This one:

. . . . . . . . . . . . .
. r i p . . . . R R R . .
. . . . . . . R . . . R .
. b i y . B . R . F . R .
. . . . . . . R . . . R .
. f i n . . . . R R R . .
. . . . . . . . . . . . .

where uppercase letter correspond to entities and lowercase to their respective nouns. . is empty, p is push, y is you and n is win (originally I've implemented walls, and there was a namesake crash so I've made win n instead).

• The grid is parsed for rules just like in the original game. There are two types of rules:
  • noun is property, for example baba is you or flag is push. These type of rules are referred to as behaviours.
  • noun is noun, for example baba is rock. These type of rules are referred to as swaps. Since this grid does not have two of any of the nouns, one does not have to worry about the case like rock is rock (which would, otherwise, affect the execution of other rules)
• The rules work only from left to right, and from top to bottom.
• The only allowed moves are up, down, left and right. No idle, no undo.
• When a move is made, every entity which is you attempts to move in the direction specified.
• The order of actions in a single step is as follows:
  • Search the grid for all the current rules
  • Parse the rules into behaviours and swaps
  • Apply all the swaps to the grid in an alphabetical order (Only one swap per cell)
  • Perform an action for the turn according to the behaviours

Here is an example game where the rule rock is push has been changed into rock is win.

Golfing challenge rules

Your task is to implement the above game of Baba is You, using the smallest number of source code bytes (the usual). Your program will take a sequence of moves as an input, and output 1, or True, or otherwise something meaningful if this sequence of moves leads to a victory on the above grid (and only on this grid. Just hardcode it in). Otherwise, the program will output 0, or False or nothing.

You can assume that every sequence of moves is a valid sequence in any format. I've used symbols ^V<>^ for example, but you're most welcome to assume it's udlr instead.

You can assume any input sequence either ends on a win, or does not lead to one. This means you do not have to worry about there being any more moves past the winning one. If such sequence is passed to your program, it's an undefined behaviour and your program can do anything.

I've implemented this version of the game in python. You can find it here. Some of the more tricky behaviour is specified in the readme (If you find any weird edge cases I haven't thought of let me know or send me a PR). There is a minimal self-contained version of the code in /golf/golfing_full.py and the abbreviated version in /golf/golfing_short.py. The sum total comes to 1930 bytes (sans the test at the end).

Test cases

- Fastest win
1: >>^>>V
- Fastest loss (you don't actually have to check for loss explicitly)
0: <^<V
- Baba is win
1: <VV<V<<^V>>^<
- Rock is baba
1: <^^^<<V>V<>>
- Rock is you
1: <^^^<<V^<<VV>><<^>><<
- Rock is win
1: <VVV<^<^>V>^^V<<<<^^^>^>>>>VVV<^>>>
- Rock is win but also push
1: <^<<<<V>>>V>VV<<^^^>^<VV>>V<V<^^>^<V>>>>>>>V<^^^^>^<<<<<<<<<
- Baba is flag
0: <V<<<<V>>V>^^>>^^>>^>>V
- Baba is you is win
0: <V<<<<V>>V>>^^VV>^^
- Flag is rock is win
1: <V<<V^<V>>>^^<^>^^<<V^<<VV>>>^>VVVV^^^<<<<^>>^>VVVV>>V^<<V>>^^>>
- Flag is rock is win, but win on what used to be the flag
1: >VV>^^<^>V>^VV<<<<<<<V^>V>>^>V^^<<^>^^<<V^<<VV>>>^>VVVV^^^<<<<^>>^>VVVVV^^>>>>>>
- Rules don't work upside down
0: <V<<<<V>>V>>>^V<<<^>V>>^V<<^>V>>^^^>>^>>V
- Rules don't work backwards
0: <V<<<<V>>V>>>^V<<<^>V>>^V<<^>><^^^>V>V<^<V<VV>>>>^<<<>^^>>^>>V
- Rules (swaps) are applied alphabetically
1: <^<<<<V>>^<<^^>>V^<<VV>>^><V><V><<<VVV>^^<^>>V>^^<^>VVV>VV<<^^^<^>V>^<^>><<V<<^>>>>>V<^<VV<<
- Rules (swaps) are applied alphabetically, case 2
1: <^<<<<V>>^<<^^>>VV<V>V>>VV<<^V<<^>^^^<^>^>VV>V<V<V>^^>V>V>>>^^<<
- Rock is baba is flag
0: <^^^<<V^<<V><VVVVV>>^V<<^>^<^><
- Rock is baba is flag, case 2
0: <^^^<<V^<<V>>>><<<V>>><<<<VVVV>>^V<<<^^>>>><<<<V>>>><<<<^^>>>><
- Walk into the corner for a while and make a circle around the board
1: VVVV>>>>>>>>^^^^^^^>^^>^>^<<<<<<<<<<<<<VVVVVVV^^>>>>>>>>^>
- Win at the last moment
1: >>V>V<<<V<<<^V<<^><^^^^^>>V^<<V><VV><

Answer 1

Python 3, 707 646 615 bytes

e=enumerate
S=eval(input())
exec('''g=[[int(k/10**i)%10FiIrange(11,-2,-1)]FkI[0,71800004440,40004,51902040304,40004,61000004440,0]];g[5][3]=10
R=lambda a,b:(4<a<8)*any([*r[i:i+3]]==[a,1,b]FrI[*g,*zip(*g)]Fi,pIe(r[2:]))
FsIS:
 G=[[([b-3FbI(5,6,7)if R(c+3,b)]+[c])[0]FcIr]FrIg]
 F_I' '*s:G=[*zip(*G)][::-1]
 Fj,rIe(G):
  r=G[j]=[*r]
  Fk,CIe(G[j]):
   l=0 
   if R(C+3,9):
    Fi,cIe(r[:k]):l=(c<2or c>4or R(c+3,8))and[l,i+1][c<1]
    if l<1:0<k and R(r[k-1]+3,10)and E
    else:r[l-1:k]=r[l:k+1];r[k]=0
 g=G
 F_Irange(s):g=[*zip(*g[::-1])]
 FaI5,6,7:R(a,10)and R(a,9)and E'''.replace("I"," in ").replace("F","for "))

Try it online! (all testcases, simulates stdin)

Essentially a rewrite from the ground up, loosely based on MarcinKonowalczyk's golfing_full.ipynb.

Takes input through STDIN as a list of integers, where 0,1,2,3 correspond to left, up, right, down respectively. Throws an error on win and does not throw on loss as per this default.

• -61 bytes: use integers instead of characters, take input through STDIN instead of as function, other small changes
• -31 bytes: exec-replace on for and in

Ungolfed

def grid_has_rule(grid, rule):
    return any(rule in ''.join(row) for g in [grid, zip(*grid)] for row in g)

def print_grid(grid):
    print('\n'.join(''.join(row) for row in grid), end='\n\n')

def play(sequence):
    grid = [[x for x in row] for row in '.............|.rip....RRR..|.......R...R.|.biy.B.R.F.R.|.......R...R.|.fiw....RRR..|.............'.split('|')]

    for step in sequence:
        # (clone)
        new_grid = [row*1 for row in grid]

        # Perform swaps
        # automatically alphabetical order because 'bfr' is sorted
        new_grid = [
            [
                (
                    [b.upper() for b in 'bfr' if grid_has_rule(grid,chr(ord(c)+ord('a')-ord('A'))+'i'+b)] # priorities "<c>ib", then "<c>if", then "<c>ir"
                    +[c] # then no rule: c unchanged
                )[0]
                for c in row
            ]
            for row in grid
        ]

        # we can't modify grid because it stores the current rules
        # grid = new_grid

        # Step
        # re-orient new_grid until movement direction is left
        for _ in range(step):
            # rotate 90 CCW: transpose followed by reflect
            new_grid = [*zip(*new_grid)][::-1]

        for j, row in enumerate(new_grid):
            new_grid[j] = list(row)
            for k, cell in enumerate(new_grid[j]):
                if not grid_has_rule(grid,chr(ord(cell)-ord('A')+ord('a'))+"iy"):
                    # cell is not you
                    new_grid[j][k] = cell
                    continue

                # try pushing left from (j, k)
                # might not be push: B,F,R
                # get the rightmost cell to the left which isn't push:
                last_unpushable_i = [i for i,c in enumerate(new_grid[j][:k]) if c in 'BFR' and not grid_has_rule(grid,c.lower()+'ip')]
                last_unpushable_i = last_unpushable_i[-1] if last_unpushable_i else -1
                last_gap = [i for i,c in enumerate(new_grid[j][:k]) if c=='.' and last_unpushable_i<i] # (maybe slice from list(enumerate))
                if not last_gap:
                    # no gaps left, unpushable
                    if k > 0:
                        if grid_has_rule(grid, chr(ord(new_grid[j][k-1])-ord('A')+ord('a')) + 'iw'):
                            # object can't move and is win
                            return True
                    new_grid[j][k] = cell
                else:
                    # maybe del trick?
                    L = last_gap[-1]
                    new_grid[j][L:k] = new_grid[j][L+1:k+1]
                    new_grid[j][k] = '.'
        grid = new_grid
        # revert orientation (maybe just take this-last instead)
        for _ in range(step):
            # rotate 90 CW: reflect followed by transpose
            grid = [*zip(*grid[::-1])]

        # I'm leaving this here for future debugging
        # print('<^>V'[step])
        # print_grid(grid)

        # Check for you is win condition
        # Doesn't need to be at top because can't have yiw at start
        for a in 'bfr':
            if grid_has_rule(grid, a+'iw') and grid_has_rule(grid, a+'iy'):
                return True

Golfed, commented (old)

# does grid g have the rule u, either horizontally or vertically?
R=lambda g,u:any(u in''.join(r)for g in[g,zip(*g)]for r in g)
e=enumerate
# main: play, given sequence S
# "<^>v" --> [0,1,2,3]
def P(S):
    # generate grid g
    g=[*map(list,['.'*13,'.rip....RRR..','.......R...R.','.biy.B.R.F.R.','.......R...R.','.fiw....RRR..','.'*13])]

    # for each step s
    for s in S:
        G=[ # create a new grid G, which consists of the swaps applied to g
        [
            (
                [b.upper()for b in'bfr'if R(g,chr(ord(c)+32)+'i'+b)]# priorities "<c>ib", then "<c>if", then "<c>ir"
                +[c])[0] # then no swap: plain c
                for c in r
            ]
            for r in g
        ]
        # rotate grid counter-clockwise s times until movement direction pointing left
        for _ in range(s):G=[*zip(*G)][::-1]
        # for each row of the rotated grid G
        for j,r in e(G):
            # side effect of the zip is that it produces tuples
            # no good since we have to modify them
            r=G[j]=[*r]
            # go from left to right in the row
            # this allows us to modify the row
            for k,C in e(G[j]):
                # test if the cell is you
                if R(g,chr(ord(C)+32)+"iy"):
                    l=0 # l shall be 1 more than index of the last empty cell to the left of this cell but not
                        # to the left of an entity that is not push; 0 if none exists
                        # Travel from left to right in the list of cells to the left of this cell
                        # (negative logic) If the cell is an entity and is not push, then l=0
                    for i,c in e(r[:k]):l=(c not in'BFR'or R(g,c.lower()+'ip')) and\
                            [l,i+1][c=='.']                  # otherwise set l=i+1 if c is empty, else l
                    # l<1: no empty cell to the left exists
                    # If not at the edge
                    # and the cell to the left is win, throw a NameError: win
                    if l<1:0<k and\
                        R(g,chr(ord(r[k-1])+32)+'iw') and\
                        E
                    # there is an empty cell at index l-1, so push
                    # shift cells over by one; set the cell you are pushing from to empty
                    else:r[l-1:k]=r[l:k+1];r[k]='.'
        g=G
        # rotate grid clockwise s times until back to normal
        for _ in range(s):g=[*zip(*g[::-1])]
        # test for X is win and X is you:
        for a in'bfr':R(g,a+'iw')and R(g,a+'iy')and E

Answer 2

Python, 1930 1927 1686 bytes

• 1927 (-3) by replacing tabs with spaces
• 1686 (-241) Thanks to @pppery (silently ignoring errors)

This is the 'proof-of-principle' solution. I'm sure some more bytes can be shaved off with better eval tricks.

Expanded code + explanation

Try it online! <- With the tests appended at the end

e=enumerate;v=reversed;t=tuple;z=zip
P=t('ypn');N=t('bfr');E=t('BFR')
exec('''exec('ip%sxP;io%sxN;ie%sxE;tr%s[c cz(*x)];f%s[t(v(r))rx]'%(('=lambda x:',)*5))
exec('rp%sf(tr(g));rm%str(f(g));rh%sf(tr(f(tr(g))));rz%sg'%(('=lambda g:',)*4))
from collections import deque
def et(seq):
 w=deque(maxlen=3);i=3
 _map(w.append,seq):
  i-=1
  if not i:i=1; yield t(w)
def F(g):
 iu=lambda t:(io(t[0])and t[1]=='i')and(io(t[2])or ip(t[2]));s=[]
 rg:
  tet(r):if iu(t):s.append((t[0],t[2]))
 cz(*g):
  tet(c):if iu(t):s.append((t[0],t[2]))
 sorted(s)
def R(r):
 b={n:dict(z(P,(False,)*3))nN};s=[]
 j,ar:
  if ip(a):b[j][a]=True
  else:s.append((j,a))
 b,sorted(s)
def at(p,b):
 len(p)or Z
 if p[0]=='.':p
 elif len(p)==1:Z
 h=lambda c:(ie(c)and b[c]['p'])or c(*P,*N,'i')
 if not h(p[0]):Z
 if p[1]=='.':(p[1],p[0],*p[2:])
 else:q=at(p[1:],b);(q[0],p[0],*q[1:])
S=t('^V<>')
qp=dict(z(S,(rz,rh,rp,rm)));qm=dict(z(S,(rz,rh,rm,rp)))
def T(g,b,s):
 g=qp[s](g);h=[['.'_r]rg];iy=lambda c:ie(c)and b[c]['y'];iw=lambda c:ie(c)and b[c]['n']
 j,re(g):
  k,celle(r):if not iy(cell):h[j][k]=cell;continuep=[h[l][k]lv(range(j))]try: q=at(p,b) l,me(v(q)):h[l][k]=m h[j-1][k]=cellexcept: len(p)and iw(p[0])and Z h[j][k]=cell
 qm[s](h)
def S(g,s):
 h=[[c cr]rg]
 a,bs:
  j,re(g):k,ce(r): if ie(c)and c==a and h[j][k]is c:h[j][k]=b.upper()
 h
def Y(q):
 g=[[c cr]r('.'*13+'|.rip....RRR..|.......R...R.|.biy.B.R.F.R.|.......R...R.|.fin....RRR..|'+'.'*13).split('|')]
 try:
  p(*q,None):b,s=R(F(g))nb: if b[n]['y']and b[n]['n']:Zg=S(g,s)if p:g=T(g,b,p)
 except:1
 0'''.translate({2:"for ",3:"return ",4:".lower()",5:" in ",6:"\n   "}))

Answer 3

J, ^{456 441} 399 bytes

Takes in the list of directions, with V < ^ > as 0 1 2 3.

0=[:+./@,@><@(4 o@,&4(4 o@,&0])13#.inv 36bdnnshw5d 85686 36ba491bbil 85686 36bbvydg17b)([:(([*0=[:+/@,y*w)r)@(([:><@[([+-~/@]*(={.))~&.>/@,~[:<"1@\:~@;e(<@(l,.4-~])~"{~+&4)~])r)(4-[)o(o=:|.@|:~&0)(([*0=[:+/@,y*1|.(w=:e.l&11)*0=p)([((*-.)+_1|.*)2=[:z&.|.(p*0<[)>.2*(y=:e.l&10)*1|.p=:((0=[:(z=:(2*4<3#.|:@,:)/\.)*@[+e.)e-.l&10,(l=:#&e@e.~(4+(e=:1+i.4),.5)&,.)&12))])(r=:3[\"1(,@,|:))@])&.>/@,~<"0@|.@]

Try it online!

Or play around with the version that prints the board after each step.

How it (roughly) works

It goes quite well as an tacit definition, as we're just working on the matrix itself. It maps the characters to numbers according to the list in level.

Ungolfed:

 NB. map stored as base 13, then padded with floors and walls
walls=:4 rot@,&4(4 rot@,&0])13#.inv 36bdnnshw5d 85686 36ba491bbil 85686 36bbvydg17b
 NB. rotate matrix x times
rot=:|.@|:~&0
 NB. BFRW as numbers
objs=:1 2 3 4
 NB. get all 1x3 lists of the original and the transposed matrix
rules=:(3 [\"1 (,@,|:))
 NB. check if rule exists, e.g isrule&10 -> things that can be pushed
isrule =: (#&objs@e.~ (4 + objs ,. 5)&,.)
 NB. 0 2 0 0 1 1 2 1 0 -> 0 2 0 0 2 2 2 0 0
 NB. used for checking which fields can move/get pushed
red=:(2* 4< 3#. |: @ ,:)/\.
 NB. places that can be walked into
pass=:((0 = [: red *@[ + e.)  objs -. isrule&10 , isrule&12)
 NB. win place can't be walked into (not pushable or blocked),
 NB. with a you-entity that walks down -> won
wonpush=: ([ * 0 = [: +/@, (e. isrule&10) * 1 |. (e. isrule&11) * 0 = pass)
 NB. exists entity that is you and win?
wonyou =: ([ * 0 = [: +/@, (e. isrule&10) * (e. isrule&11))
 NB. calculate which places gets moved or pushed down in a step
shifts=:( 2 = [: red&.|. (  pass * 0 < [) >. 2 * (e. isrule&10) * 1 |. pass)
 NB. actually move down entities
move_down=:([ ((*-.)+_1 |.  *) shifts)
 NB. get all rules of the form (objs is objs), sort them, replace them
replace=: ([: > <@[ ([ + -~/@] * (={.))~&.>/@,~ [: <"1@\:~@; objs (<@(isrule ,. 4-~])~"{~ +&4)~ ])
 NB. rotate so movement goes down, check wonpush, move down, rotate back, replace, check wonyou
move=: ([: (wonyou rules)@(replace rules) (4-[) rot rot (wonpush move_down ]) rules@] )
 NB. append moves to the matrix and reduce from right to left with move,
 NB. e.g. 0 move 1 move 0 move walls
sim2=: (<@walls move&.>/@,~ <"0@|.@])
 NB. after everything is finished, does contain matrix only 0? if yes -> won

Answer 4

BaBa Is You, 663 615 bytes

File .l:

00000000: 4143 4854 554e 4721 0501 4d41 5020 0200  ACHTUNG!..MAP ..
00000010: 0000 0000 4c41 5952 b301 0000 0300 0f00  ....LAYR........
00000020: 0000 0c00 0000 0c00 0c00 00ff 0000 0000  ................
00000030: 0000 0000 0000 803f 0000 803f 0000 0100  .......?...?....
00000040: 0080 3fff ffff 024d 4149 4e87 0000 0078  ..?....MAIN....x
00000050: 5e63 2004 5819 3959 19b9 5958 d9b9 9918  ^c .X.9Y..YX....
00000060: 9919 3919 9999 1819 58b8 9958 9840 1a39  [email protected]
00000070: 99d8 18b8 1959 3838 1919 9959 8098 9389  .....Y88...Y....
00000080: 8583 1bcc 061b cbc2 0085 dc40 9a1b c666  [email protected]
00000090: 038a 02a5 ffe3 040c 6059 4ea0 7ddc cc30  ........`YN.}..0
000000a0: 45cc 0c20 08e2 3160 e865 6680 a802 d150  E.. ..1`.ef....P
000000b0: bd40 3770 b3fc ffcf 0894 018b 32fd ff8f  [email protected]...
000000c0: 9045 b618 532f c8fd 5c44 d98b 6c0e a160  .E..S/..\D..l..`
000000d0: 0400 5728 8923 4441 5441 0100 0000 0030  ..W(.#DATA.....0
000000e0: 0000 0078 5e63 4603 0c0c cc0c 70c0 8cc4  ...x^cF.....p...
000000f0: 060a 6270 3135 3380 84c0 4ae1 7220 21b8  ..bp153...J.r !.
00000100: 30d0 7466 10c6 2ecb 0cb6 8199 1000 006d  0.tf...........m
00000110: d701 660f 0000 000c 0000 000c 000c 0000  ..f.............
00000120: ff00 0000 0000 0000 0000 0080 3f00 0080  ............?...
00000130: 3f00 0001 0000 803f ffff ff02 4d41 494e  ?......?....MAIN
00000140: 1600 0000 785e fb4f 1660 e4c4 af8d 91f9  ....x^.O.`......
00000150: ff28 4009 0100 74d2 62ba 4441 5441 0100  .(@...t.b.DATA..
00000160: 0000 0012 0000 0078 5e63 c60d 18d0 a418  .......x^c......
00000170: 9807 0900 00bc 3402 170f 0000 000c 0000  ......4.........
00000180: 000c 000c 0000 ff00 0000 0000 0000 0000  ................
00000190: 0080 3f00 0080 3f00 0001 0000 803f ffff  ..?...?......?..
000001a0: ff02 4d41 494e 0d00 0000 785e fb3f 0ae8  ..MAIN....x^.?..
000001b0: 1202 00e6 5866 a844 4154 4101 0000 0000  ....Xf.DATA.....
000001c0: 0b00 0000 785e 631e 8200 00bf 9a02 1d    ....x^c........

File .ld:

[tiles]
changed_short=016,082,
object082_name=text_phantom
changed_count=2
object016_name=text_feeling
changed=object016,object082,
object016_argtype=2,

Summon a phantom item to detect win

Weaken thing that are on others

feeling and phantom looks bad since image take extra bytes