2021-11-01

This is a 1 dimensional version of win detection in Connect Four.

Warmup

Write the all_match_nz function that returns True when all of the elements of the input list are the same and not zero.

all_match_nz :: [Player] -> Bool

It makes sense to say all_match_nz [] == True, but make sure that all_match_nz [0,0,0,0] == False.

Skip Counter

A board consists of X, O, and blank squares.

X..XOX.XOX.X

A player wins with four evenly spaced markers. In this case, there are four evenly spaced X’s (indices 3, 5, 7, and 9), so X wins this game.

Another example is:

X.O.XOOXO..OX.X.X
  ^  ^  ^  ^
0         1
01234567890123456

In this case player O wins starting at index 2 and going up 3 squares at a time (indices 2, 5, 8, and 11).

This board has no winning player:

X.O.X...XOO

You should not claim that the board is won by “.” (“player 0”) starting at index 1 and going up by 2.

Goal

Your goal is to produce a function that returns True when a “skip counter” board is won. There are two big-picture steps:

1. Produce a list of all possible sequences of indices to examine. (Use the maximum length of a board as input.)

    all_candidates :: Int -> [[Int]]
    all_candidates max = undefined
   

   Example showing steps of length 1 and 2.

    all_candidates 7 ==
        [[0,1,2,3],[0,2,4,6],[1,2,3,4],[2,3,4,5],[3,4,5,6]]
   

2. Given a board, check all of those index lists to see if any of them correspond to four of the same pieces.

    skip_won [1,0,1,0,1,0,1] == True
    skip_won [1,1,1,1,0,0,0] == True
    skip_won [0,1,0,2,0,2,0] == False
   

Technical

We will represent the board by a list of numbers

X..XOX.XOX.X

is represented by

nums = [1,0,0,1,2,1,0,1,2,1,0,1]

Since this is supposed to be a simplified game, let’s start with a working getPlayer function that returns 0 for any position off the board.

getPlayer :: Int -> [Int] -> Int
getPlayer pos nums 
   | 0<= pos && pos < length nums  = nums !! pos
   | otherwise  = 0

In the example above, getPlayer 4 nums == 2 and getPlayer 100 nums == 0.

Walkthrough

1. Given a starting position and a step size, we generate a list of 4 numbers starting at the given position and increasing each time by the step size.

    step1 :: Int -> Int -> [Int]
    step1 start step = undefined
   

2. Given a starting position and a maximum step size, generate all of the possible steps from 1 through the maximum.

    step2 :: Int -> Int -> [[Int]]
    step2 start maxstep = undefined
   

3. Given a maxlen, generate all of the possible sequences of positions with starting positions 0 to maxlen.

    step3 :: Int -> [[Int]]
    step3 maxlen = undefined
   

4. Give True if every element of the list is “on the board” (in the range 0 through size-1).

    on_board :: Int -> [Int] -> Bool
    on_board size xs = False
   

5. Output every input list that is on_board, ignore the others.

    only_on_board :: Int -> [[Int]] -> [[Int]]
    only_on_board size xss = xss
   

   You will use this function to clean up your final results, keeping only the ones that fit on a board.

6. Check to see if a single sequence wins the board.

    skip_won_1 :: Board -> [Int] -> Bool
   

7. Check to see if any sequence wins the board.

    skip_won :: Board -> Bool.
   

If you prefer, your win detection functions can output the winning Player. That makes declaring who won easier… but it is not important.