Haskell Algorithm/Candy Crush possible Moves

Question

I'm an undergraduate programming student and I'm trying to create a program similar to "candy crush". I'm trying to translate this piece of code here in order to get an idea on how to search for possible moves. This below is a piece of code in Haskell (not entirely sure though)

possibleMoves gf = filter works $ filter valid $ allMoves
where allMoves           = concat [ [((i,j),(i+1,j)), ((i,j),(i,j+1))] | (i,j) <- range ((0,0),(9,9)) ]
      valid (_,(i,j))    = i < 10 && j < 10 -- first coordinate is always correct
      works move@(i1,i2) = let gf' = flipStones gf move
                           in  lookAround i1 gf' || lookAround i2 gf'

lookAround (i,j) gf' = any ((>=3).length) $
    (groupBy combineable $ [ gf' ! (i',j) | i' <- range (max 0 (i-2), min 9 (i+2)) ]) ++
    (groupBy combineable $ [ gf' ! (i,j') | j' <- range (max 0 (j-2), min 9 (j+2)) ])

But, no matter how I try to translate it (obviously I know nothing about Haskell), it makes no sense to me. It's because I can't search the meaning of those symbols, I don't know how to do it. While I know it's a bit lame to ask for help on such stuff, this is a school project and I think I do not have so much time in order to learn the basics on Haskell. Could anybody help me find the truth (ideas on what this function does/how to find the solution on my own etc)? Or maybe give me ideas to make a new nice function on my own.

Thanks for your time

---

(Edit by OP)

Thank you sooooo much! Both answers were very detailed and accurate and I'm trying to create a new function based on the data provided and it seems a lot easier to accomplish this now after those pieces of help!

Also, kobejohn, I'll have a look at your proposed code piece. Thanks very much.

Thanks everyone thank you thank you!

Answer 1

I know you don't want a translation, so i've provided a roughly equivalent implementation in python, using python generators and idioms, to try to illustrate the concept of lazy/stream based result generation.

Given that you're trying to understand how it works, let's look at each part individually. I've laid out the code to make it a little easier to understand, and added type signatures, so you can get a feel for how the parts fit together. You can lookup the symbols used in Learn You A Haskell For Great Good.

type Position = (Int, Int)
type Move = (Position, Position)

possibleMoves :: Position -> [Move]
possibleMoves gf = filter works $ filter valid $ allMoves
    where

        allMoves :: [Move]
        allMoves = concat [ [ ((i,j),(i+1,j))
                            , ((i,j),(i,j+1)) ]
                          | (i,j) <- range ((0,0),(9,9)) ]

        valid :: Move -> Bool
        valid (_,(i,j)) = i < 10 && j < 10

        works :: Move -> Bool
        works move@(i1,i2) = let gf' = flipStones gf move
                             in lookAround i1 gf' || lookAround i2 gf'

This function first generates a list of all possible moves (bound as allMoves) using a list comprehension. The syntax in haskell is a little different from python's list comprehensions. Due to haskell's lazy semantics, this piece of code would best be thought of as a generator that returns a stream of all possible moves.

def allMoves():
    for i in range(0,9):
        for j in range(0,9):
            yield ((i,j),(i+1,j))
            yield ((i,j),(i,j+1))

Then there is a function valid, which checks that a move is legal, and returns True/False depending on the answer.

def valid(move):
    return move[1][0] < 10 && move[1][2] < 10

Finally, a function works, which checks if the result actually does something useful.

def works(move):
    # flipStones returns a new game_field that incorporates the move we're testing
    new_gf = flipStones(game_field, move)
    return lookAround(move[0], new_gf) || lookaround(move[1], new_gf)

Finally, these functions are all tied together in a chain to provide the final answer. The $ symbol may seem confusing at first glance, but just think of it like a pipe operator, piping values from right to left. It can be easily replaced by parentheses.

possibleMoves gf = filter works $ filter valid $ allMoves
-- Is exactly equivalent to
possibleMoves gf = filter works ( filter valid ( allMoves ) )

The functions in the where clause exist only in the scope of possibleMoves. This maps nicely to python inner functions, as you see here.

from itertools import ifilter

# possibleMoves takes
def possibleMoves(game_field):

    def allMoves():
        for i in range(0,9):
            for j in range(0,9):
                yeild ((i,j),(i+1,j))
                yield ((i,j),(i,j+1))

    def valid(move):
        return move[1][0] < 10 && move[1][3] < 10

    def works(move):
        # the gf in scope here is the gf passed to possibleMoves
        new_gf = flipStones(game_field, move)
        return lookAround(move[0], new_gf) && lookAround(move[1], new_gf)

    return ifilter(works, ifilter(valid, allMoves()))

Next, we look at lookAround.

lookAround :: Position -> Position -> Bool
lookAround (i,j) gf' = any ((>=3).length) $
    (groupBy combineable $ [ gf' ! (i',j) | i' <- range (max 0 (i-2), min 9 (i+2)) ]) ++
    (groupBy combineable $ [ gf' ! (i,j') | j' <- range (max 0 (j-2), min 9 (j+2)) ])

This is a function which I can only assume is searching for the same min/max value that you are in your code. The left hand side of the function definition works like a destructuring assignment. (any and groupby are standard with python)

from itertools import groupby

def lookAround(pos1, pos2):
    i, j = pos1[0], pos1[1]
    # look around 2 above/below, grouping into runs of colors, returns list of lists
    list1 = groupby([pos2[(i_, j)] for i_ in range(max(0,i-2), min(9,i+2))])
    # look around 2 left right, grouping into runs of colors, returns list of lists
    list2 = groupby([pos2[(i, j_)] for j_ in range(max(0,j-2), min(9,j+2))])
    # return true if there's a run of 3 or more colours in either direction
    return any(lambda l: len(l)>=3, list1 + list2)

I hope this helps you understand what's going on. The key to the speed of this implementation is the use of lazily generated lists (generators in python). This means that a result can be discarded as soon as it is known that it is not needed, or would result in an invalid answer. The upshot of this is that you only need to do as much work as actually necessary, the downside is that in python, you have to be comfortable with generators (also known as coroutines) and stream-oriented programming.

Good luck with your assignment, I hope this gives you some ideas for increasing the performance of your implementation.