This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.

Loading...

From the course by University of California, Santa Cruz

C++ For C Programmers, Part B

53 ratings

University of California, Santa Cruz

53 ratings

This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.

From the lesson

Hex as a graph and Inheritance

This module shows how Hex can be played as a game on a graph. This involves its representation as an undirected graph in C++. The module explores the inheritance logic and syntax of C++. A principal example is the base class student and a derived class grad_student.

- Ira PohlProfessor

Computer Science

If we were doing the 11 by 11 case and we were trying to build a graph, we can see that we'd have a 121 nodes there, then we'd use this natural mapping, the natural two dimensional mapping.

And then we'd make a list of nodes, and each node would be connecting a pair of i, j coordinates and we are going to privately store this in this data structure. A vector, a deque of ints. This is not, this is not unique.

But if I have an internal node, an i, j, where they're not equal to zero, they're also not equal to 10. So they're not on the perimeter.

So, there because it's a hexagon, you have the six possible connections, the two above, the two on the same row, and the two below.

And that's what all of these indices, show you. This is how to connect. And this is a mapping of the i, j coordinates into the node numbers. So this is saying, push onto the node a particular, edge connection,

so I just give you a piece of code like that so you can make use of it. When you go to do your own version of this, you're going to need to do the special cases. So the general case is, six things in the middle. Special cases will not involve all the six things. Recall that if you have corners, it is only two nodes, if you have, if there are only. Two nodes adjacent to a corner node, and if you have an edge node that's not a corner, then you have four adjacent nodes. The edge nodes have, if let's say, you're on a, a, a side, you have the above one, the below one, and then two internal ones.

Okay so you'll still need to test among the things you'll need to be able to do is you'll be able to from the code we just looked at get a full graph representation. You'll need to be able to test when the game is over, and who won.

east, so there's some path from east to west. East is all the nodes on this boundary, so it's collection of, in the case of, the 11 by 11, there are 12, there are 11 east nodes here, and 11 west nodes. And you want to see if there's a path from any of these east nodes. That need these west nodes, and if you find a path, doesn't even have to be a shortest path, well, it'll be the only path because when it happens, the game will be over. So it'll be the shortest path from some node on the east to some node on the west and that's where you can use your Dijkstra.

And then. The other thing I want is something like a simple strategy, like extending a longest path.

So, among the things you should be able already to think about is, how would you test, what would be a test for a corner node?

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.