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><
  • 1
    \$\begingroup\$ @xash, Clarified under 'game rules' in the bullet point starting with 'The grid is parsed for rules...'. Thanks for pointing this out. I guess I'm cursed with knowledge of coding this for a while and playing the original game, so I didn't pick up on the fact that it's not obvious. \$\endgroup\$ – MarcinKonowalczyk Jun 25 at 0:26
  • 1
    \$\begingroup\$ I am not sure this is clear but I don't see any issues. It would be nice if the close voters could point out what they think is unclear. \$\endgroup\$ – Ad Hoc Garf Hunter Jun 25 at 3:59
  • 1
    \$\begingroup\$ After re-reading this a few times, I think I more-less understand the game now, but the description could definitely be friendlier to those unfamiliar :) In particular, I missed some basic introduction to movement, something like "when the player makes a move, it applies to the entity which is you under current rules". But then, if Rock is you - do all the rocks move? What if some of them are blocked? What constitutes a block? It's very much preferable to walk through several such cases in the task rather than just point to examples. \$\endgroup\$ – Kirill L. Jun 25 at 15:23
  • 1
    \$\begingroup\$ Also I don't get the concept of stop, and is it really relevant in your version of the game? For me, the winning conditions - (1) an entity is you and win simultaneously, and (2) a you entity bumps into a non-pushable win entity - look fully self-contained without the need to introduce stop, or maybe am I missing something? \$\endgroup\$ – Kirill L. Jun 25 at 15:23
  • 1
    \$\begingroup\$ Test case which depends on that behavior: >>V>V<<<V<<<^V<<^><^^^^^>>V^<<V><VV>< (assuming I didn't make a mistake) \$\endgroup\$ – Nitrodon Jun 26 at 14:01

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

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):
  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=[]
  tet(r):if iu(t):s.append((t[0],t[2]))
  tet(c):if iu(t):s.append((t[0],t[2]))
def R(r):
  if ip(a):b[j][a]=True
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:])
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']
  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
def S(g,s):
 h=[[c cr]rg]
  j,re(g):k,ce(r): if ie(c)and c==a and h[j][k]is c:h[j][k]=b.upper()
def Y(q):
 g=[[c cr]r('.'*13+'|.rip....RRR..|.......R...R.|.biy.B.R.F.R.|.......R...R.|.fin....RRR..|'+'.'*13).split('|')]
  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)
 0'''.translate({2:"for ",3:"return ",4:".lower()",5:" in ",6:"\n   "}))
| improve this answer | |
  • \$\begingroup\$ @pppery, Point. Fixed now (also pushed fix to git). Also, ' ' is one byte less than '\t', so 1927! Thanks! :P \$\endgroup\$ – MarcinKonowalczyk Jun 25 at 0:17
  • \$\begingroup\$ 1595 bytes. \$\endgroup\$ – pppery Jun 25 at 15:16
  • 1
    \$\begingroup\$ The default rules for IO formats are pretty flexible, so I think you can get rid of the error handling for 1574 bytes. \$\endgroup\$ – pppery Jun 25 at 17:38

Python 3, 707 646 615 bytes

R=lambda a,b:(4<a<8)*any([*r[i:i+3]]==[a,1,b]FrI[*g,*zip(*g)]Fi,pIe(r[2:]))
 G=[[([b-3FbI(5,6,7)if R(c+3,b)]+[c])[0]FcIr]FrIg]
 F_I' '*s:G=[*zip(*G)][::-1]
   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
 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


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

                # 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
                    # 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)
# main: play, given sequence S
# "<^>v" --> [0,1,2,3]
def P(S):
    # generate grid g

    # 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
            # 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\
                    # 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
        # 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
| improve this answer | |

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.


 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
 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
| improve this answer | |

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.