Week 12 Tutorial

In this week’s tutorial, we’ll look at working with multiple linked lists, manipulating stacks and queues, some simple recursions, and implementing a simple Final Card-Down player.

Multiple Linked Lists

We’ve seen how to deal with one linked list… what about more?

How might I append one List to another?
How might I prepend one List to another?
How might I interleave, or “zip”, values from two lists?

That is, given two lists $l_1:=5\to3\to1\varnothing$ and $l_2:=2\to4\to6\varnothing$ , the result would be $l:=5\to2\to3\to4\to1\to6\to\varnothing$ .
How might I insert values into the list in order?

That is, given the same two lists the result would be $l:=1\to2\to3\to4\to5\to6\to\varnothing$ .

Stacks and Queues

In lectures, we’ve seen how ADTs allow us to define separate implementations that may radically differ in their approach, but which conform to the same interface.

We saw the Stack ADT again: a stack is a last-in-first-out data structure. We also saw how to implement it with linked lists; here’s Stack.h:

Stack.h

// Will determine how big stackData will be.
#define STACK_SIZE 1000

// An ADT, at last!
typedef struct _stack *Stack;

// create a new Stack
Stack newStack (void);

// destroy a stack
void destroyStack (Stack s);

// this is our add function, 'char elt' = character element.
void stackPush (Stack s, char elt);

// returns the topmost element
char stackTop (Stack s);

// this is our pop function -- takes an element off.
char stackPop (Stack s);

Another simple data structure is a first-in-first-out data structure the queue. The operations on a queue are to enqueue and dequeue a value.

What might a Queue ADT interface look like?
How might we implement one using a linked list to store values?
How might we implement one using a Stack?

Simple Recursion

Hofstadter’s Law: It always takes longer than you expect, even when you take into account Hofstadter’s Law. — Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid

In lectures, we’ve seen the basics of programming recursively: we define a function that has a base case, and a recursive case.

What is a base case? What does a base case define?
What is a recursive case?
Why do we need base cases?

A trivial example of a recursion is to calculate the triangle numbers. The sequence of triangle numbers goes:

$\{0, 1, 3, 6, 10, \cdots\}$

Here’s its definition, mathematically.

$\begin{array}{rcl} \mathrm{tri}(0)&=&0\\ \mathrm{tri}(n)&=&n+\mathrm{tri}(n-1) \end{array}$

What’s the base case of $\mathrm{tri}$ ?
What’s the recursive case of $\mathrm{tri}$ ?
How might we implement a function int tri (int n)?

We can transform some recursive functions into iterations, and some iterative functions into recursions.

We’ve already seen a recursion, and calculated it iteratively:

$\mathbf{z}_n \mapsto {\mathbf{z}_{n-1}}^2 + \mu$

How might we define escapeSteps recursively?

Playing The Final Card-Down

There are three parts to assignment 2: the first two – to test, and implement, the Game ADT – you’ve already seen and should be working hard on. The third part is to implement an artificial intelligence that plays the game.

We’ve provided a header file, player.h, which looks a lot like this:

player.h

// The player of Final Card-Down. v1.1.0
//
// !!! DO NOT CHANGE THIS FILE !!!

#ifndef PLAYER_H
#define PLAYER_H

#include "Game.h"

// This function is to be implemented by the AI.
// It will be called when the player can take an action on their turn.
// The function is called repeatedly until they make the action
// END_TURN.
// If the player's turn is skipped, this funciton is not called for that
// player.
playerMove decideMove(Game game);

#endif

What do we need to do to implement the simplest player.c?
- You might want to look at the valid moves diagram

basicPlayer.c

// An initial A.I. player for Final Card-Down : Tutorial Edition
//
// Written on 2017-10-??
// Tutorial: dayHH-lab (Tutor)
// (e.g. mon13-spoons (Grace Hopper))


#include "Game.h"
#include "player.h"

// The playerMove struct, from the Game.h file:
// typedef struct _playerMove {
//    // Which action to play.
//    action action;
//    // Declare which color must be played on the next turn.
//    // This is only used when playing a DECLARE.
//    color nextColor;
//    // Which card to play (only valid for PLAY_CARD).
//    Card card;
// } playerMove;

// This function is to be implemented by the A.I.
// It will be called when the player can make an action on their turn.
//
// !!!!!   The function is called repeatedly, until   !!!!!
// !!!!!      they make the action `END_TURN`.        !!!!!
//
// If the player's turn is skipped, this funciton
// is *not* called for that player.
//
// Don't forget about the `isValidMove` function -- it's a handy way
// to work out before you play a move whether or not it will be valid
// (and you should only ever be making valid moves).
//
// You can also use it to help you work out where you are at in the
// game, without needing to look through all of the previous state
// yourself --
//
// Looking at the diagram of valid moves at any given point in the game,
// we can see that at the start of the game, it's valid to:
//   - call somebody out for forgetting to SAY_UNO / SAY_DUO / SAY_TRIO,
//   - draw a card,
//   - play a card, *if* you have a valid card that you can play.
//
// It's not valid to end your turn unless you've done some other
// action/s (again, see the diagram).
//
// We can take advantage of that for our very simple A.I. to determine
// where we are at in our turn, and thus what move we should make.

playerMove decideMove(Game game) {

    // Start out by making a move struct, to say what our move is.
    playerMove move;

    // Set our move to be END_TURN, and check whether that's
    // a valid move -- if it is, then just end our turn (for now).
    move.action = END_TURN;

    // If it's not valid to end turn, we must need to make
    // some other action...
    //
    // What actions are valid at this point?
    if (!isValidMove(move)) {
        move.action = // ?????
    }

    return move;
}

You need to work with your lab partner to implement a player.c; in the lab today, you should get started on that.

In the next competition rounds, we’ll run games with all the submitted players, so you should submit a compiling player.

Next Week…

… is our last week! Have a party!

(… and maybe think about the various things we’ve learned over the course of this semester!)