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

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

Actually, this could just as well have been a vector.

And here's the critical thing for creating an edge for an internal node.

Recall that, when we have corner nodes like (0,0),

so if this is the zero zeroth node, it only has two nodes that it connects to.

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.

Here's where you could use your own form of Dijkstra.

Who won is somebody who one that created a path from, for example,

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.

There we go. We're blocking.

So that's your job.

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?

Take a sec.

Here's an answer for upper left corner.

It's just some series of boolean expressions.

Now, we've left two off,

Let's see if, on the fly, I can remember one, so

there'd be another one like, this again is the logical and.

So this would be yet another corner.

And the final corner would be, so

that gives you all four corners. Okay?

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