C9 Lectures: Stephan T. Lavavej  Standard Template Library (STL), 5 of n
Description
Welcome to another installment of C9 Lectures covering the powerful general C++ library, STL. Joining us once again is the great Stephan T. Lavavej, Microsoft's keeper of the STL cloth (this means he manages the partnership between the owners of STL (dinkumware) and Microsoft, including, of course, bug fixes and enhancements to the STL that ships as part of Visual C++). Simply, Stephan is a C++ library developer.
As is Stephan's nature, he elaborates on technical details in very substantive way. The Standard Template Library, orSTL, is a C++ library of container classes, algorithms, and iterators. STL provides many fundamental algorithms and data structures. Furthermore, the STL is a generalpurpose library: its components are heavily parameterized, such that almost every component in the STL is a template.
In part 5, Stephan digs into the gory details of the member functions employed by his Nurikabe puzzle solver. You must watch part 4 before watching this part!!
Enjoy! Learn!
Books mentioned by Stephen:
The C++ Standard Library: A Tutorial And Reference by Nicolai M. Josuttis
Effective STL by Scott Meyers
[STL Introduction lecture links]
Part 1 (sequence containers)
Part 2 (associative containers)
Part 3 (smart pointers)
Part 4 (Nurikabe solver)  see Wikipedia's article and Stephan's updated source code
Part 5 (Nurikabe solver, continued)
Part 6 (algorithms and functors)
Part 7 (algorithms and functors, continued)
Part 8 (regular expressions)
Part 9 (rvalue references)
Part 10 (type traits)
Code:
https://github.com/Microsoft/nurikabe
Share
Download
Download this episode
 High Quality MP4 (591.4 MB)
 Mid Quality MP4 (412.8 MB)
 High Quality WMV
 MP3
 Low Quality MP4
 Mid Quality WMV
More episodes in this series
C9 Lectures: Stephan T. Lavavej  Standard Template Library (STL), 6 of n
Related episodes
C9 Lectures: Stephan T Lavavej  Advanced STL, 5 of n
C9 Lectures: Stephan T Lavavej  Advanced STL, 4 of n
C9 Lectures: Stephan T Lavavej  Advanced STL, 3 of n
C9 Lectures: Stephan T Lavavej  Advanced STL, 1 of n
C9 Lectures: Stephan T. Lavavej  Standard Template Library (STL), 10 of 10
C9 Lectures: Stephan T. Lavavej  Standard Template Library (STL), 9 of n
C9 Lectures: Stephan T. Lavavej  Standard Template Library (STL), 7 of n
C9 Lectures: Stephan T. Lavavej  Standard Template Library (STL), 6 of n
C9 Lectures: Stephan T. Lavavej  Standard Template Library (STL), 4 of n
C9 Lectures: Stephan T. Lavavej  Standard Template Library (STL), 3 of n
The Discussion

Anyone else having sync issues when it's showing the source code? Thanks.

I do. Sorry about that. We will need to fix this...
C
PS: Fixed!

I've solved both "hard" wikipedia example and the 9th "nikoli" example from Stephan's zip file by human reasoning, without need for "global" backtracking (i.e. "guessing)  only using some limited, localized whatif analysis, and some spatial reasoning for the "9" puzzle. The GIF stepbystep slides are here (please sort by name before viewing).
It is possible that the search might be improved by using the heuristic of working near the known frontier first, with iterative deepening in number of steps considered, instead of demanding a complete answer (solved/contradiction) for each randomly picked point (sure looks like exponential explosion there).
Our goal is to add more knowns to the grid, so we need not pursue guesses which still hasn't produced a definitive determination one way or the other after some threshold number of steps  better abort in the middle and try another guess, in hopes it'll produce its answer fairly quickly, and the new known thus found may well lead to a cascade of new knowns to be found semiautomatically (i.e. with extend/(n1) projection/surround moves which are very easy to make).

Thanks Stephan.
Also I would like to hear about test driven development (TDD) for C++. I used C++/C++CLI/NUnit to leverage all testing goodies at managed side. But it is not a portable solution.

[Will_Ness]
> I've solved both "hard" wikipedia example and the 9th "nikoli" example from
> Stephan's zip file by human reasoning, without need for "global" backtracking
> (i.e. "guessing)  only using some limited, localized whatif analysisYour "5:5 goes RT (if were UP => NO_ROOM("3"))" is what my guessing, teamed up with confinement analysis, determines. I don't know how to implement that any more efficiently. (If you do, I encourage you to try!)
> It is possible that the search might be improved by using the heuristic
> of working near the known frontier first, with iterative deepening in number of steps consideredAgreed. My guessing is expensive because it amplifies the amount of other expensive analysis (mainly confinement) that's run.
> instead of demanding a complete answer (solved/contradiction) for each randomly picked point (sure looks like exponential explosion there).
It's not exponential, because guesses can result in "I'm stumped, guess another cell".
[tivadj]
> Also I would like to hear about test driven development (TDD) for C++.Sorry, I don't know anything about TDD.

3 hours ago, STL wrote
[Will_Ness]
> ... only using some limited, localized whatif analysisYour "5:5 goes RT (if were UP => NO_ROOM("3"))" is what my guessing, teamed up with confinement analysis, determines. I don't know how to implement that any more efficiently. (If you do, I encourage you to try!)
> It is possible that the search might be improved by using the heuristic
> of working near the known frontier first, with iterative deepening in number of steps consideredAgreed. My guessing is expensive because it amplifies the amount of other expensive analysis (mainly confinement) that's run.
yes, "localized whatif analysis" is of course guessing  limited by the virtue of being performed by a human with very limited backtracking capacity. Not being able to keep in mind more than a few moves is what I refer to "localized" here (closeness to frontier), and is what forces me to consider only very shallow moves  what the iterative deepening would achieve, which would suspend (not abort) expensive solve() computation(s) in progress. Or you could use a good scheduler for a massively parallel solution that would run all of them at once, to take care of that automagically.
I've since seen more puzzle examples, on "puzzlenurikabe dot com", where unfortunately the initial frontier expansion stops very early on, and extensive guesswork is unavoidable. There another heuristic sometimes works wonders, which I'm having troubles formalizing  painting all the (remaining) cells initially black, and expanding the islands from there, trying "to get away with as much as possible" guided by square condition mostly, at first, and then trying to push a few cells around to correct the problems which appear.

> what the iterative deepening would achieve, which would suspend (not abort) expensive solve() computation(s) in progress.
The way to implement that would be to make many Grid copies, and call solve() on each of them in succession. You could modify solve() so that you could instruct it to perform only cheap analysis.

Am I correct you are using enumerated types to store values outside the declared range of the type? I admit that C++ already allows this where it allows (Enum()) as a valid expression; however, I would never mix entities like that. I would rather use the underlying type or, if it is needed for resolution, a wrapper class.
BTW, I would really appreciate if enumerated types were true compiletype sets of values in C++, with expressions like (wrapping) increments (++e), (e), (limits<e>) (this one would require compiler magic because builtin types only have min and max as library definitions) and (e = dynamic_cast <Enum> (07)) throwing bad_cast. Of course, these features can be simulated with TMP, but it takes a lot to write such code (and, even worse, to read it).

[giecrilj71pl]
> Am I correct you are using enumerated types to store values outside the declared range of the type?Yes. It's perfectly valid, because I'm using an explicitly specified underlying type. N3126 7.2 [dcl.enum]/7 says: "For an enumeration whose underlying type is fixed, the values of the enumeration are the values of the underlying type."
I started doing this when I noticed that I was manipulating states and coordinates everywhere, and I didn't want to confuse them. By making State an enum, I can't pass an int (like a coordinate) to a function taking a State.
> BTW, I would really appreciate if enumerated types were true compiletype sets of values in C++, with expressions like (wrapping) increments (++e), (e), (limits<e>)
Constants can't be modified, especially compiletime constants, so incrementing and decrementing wouldn't make any sense.
With C++0x type traits, you can request the underlying type of an enum, and then determine its limits.

Well, actually hard to learn STL for a firsthead frontier(novice), however this video or article is for experts of STL.
But I'd better recommend to learn Modern C++. Wow!! it's Fantastic.