Posted: 4/2/2009 9:45 AM
(Edited: 4/22/2009 6:16 AM)
Post subject: C++ exercises
Quote
Bisqwit
Editor, Active player (297)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
I wrote this code. It is written in C++0x. You can compile it with e.g. Intel C++ Compiler by the following commandline: icc --std=c++0x bisqwitmaze.cc (Sorry, GCC does not support this syntax yet.) 
#include <cstdio>
#include <cstdlib>
#include <wchar.h>
const int w=79, h=23;
static void draw(const wchar_t maze[w*h])
{
    for(int p=0; p<h; ++p)
        std::printf("%.*ls\n", w, maze+p*w);
}
static void gen(wchar_t maze[w*h])
{
    // Mark edges as walls and the interior as space
    for(int p=0; p<w*h; ++p)
        maze[p] = p%w==0||p%w==w-1  // vert walls at l&r
                ||p/w==0||p/w==h-1; // horiz walls at t&b
    // Populate the maze with maze walls
    for(int p=0; p<9999; ++p)
    {
        int r = std::rand(), x,y,x2,y2, hh=h/2, wh=w/2, l, hits=0, pos;
        if(std::rand()%2) // horiz wall
            l=4, // length
            y = y2 = 2*(r%(hh)+1), // an even row starting from 2
            x = 2*(r/(hh)%(wh+2-l)), // an even column
            x2 = x+l;
        else // vert wall
            l=2, // length
            x = x2 = 2*(r%(wh)+1), // an even column starting from 2
            y = 2*(r/(wh)%(hh+2-l)), // an even row
            y2 = y+l;
        // s is a scaling helper function
        auto s = [&pos,l] (int a,int b) { return a + (b-a)*pos/l; };
        for(pos=0; pos<=l; ++pos) hits += maze[s(y,y2)*w + s(x,x2)];
        if(hits != 1) continue; // must hit another wall in exactly 1 spot
        for(pos=0; pos<=l; ++pos) maze[s(y,y2)*w + s(x,x2)] = 1;
    }
    // e = helper function which tells whether the given char is not '\0' or space.
    //     space needs to be recognized due to the scanning order in the loop.
    auto e = [] (wchar_t c) { return c && c != L' '; };
    // Convert maze to text
    for(int y=0, p=0; y<h; ++y)
        for(int x=0; x<w; ++x,++p)
        {
            // Check neighbours (top,bottom,left,right)
            int t = y>0 && e(maze[p-w]), b = y<h-1 && e(maze[p+w]);
            int l = x>0 && e(maze[p-1]), r = x<w-1 && e(maze[p+1]);
            // Convert this spot to a character
            maze[p] =
              L" ~oI" // 0
             L")J\\+" // l
              L"(LF+" // r
              L"=+z+" // l+r
              // 0, t, b, t+b
              [maze[p]*(t + b*2 + l*4 + r*8)];
        }
}
int main()
{
    wchar_t maze[w*h];
    gen(maze);
    draw(maze);
}
It produces this output: 
F=z===z=========z=z=z===z===z=z=z=z=========z=====z=====z===z=====z===z=====z=\
I I   I         I I I   I   I I I I         I     I     I   I     I   I     I I
I ~ o ~ (=====z=+ I I F=+=) ~ I ~ +=======) I F=z=+=z=) I (=+=\ o ~ (=+=\ o ~ I
I   I         I I I I I I     I   I         I I I I I   I   I I I       I I   I
I o +=z=z=z=\ I I ~ I I I F===J (=+=) o (===J I ~ ~ I (=+=) I ~ +=====z=+=+=\ I
I I I I I I I I I   I I I I       I   I       I     I       I   I     I     I I
+=+=J ~ I ~ ~ ~ I o ~ I I +===) (=+=z=+=\ o o ~ F===J (===\ ~ o ~ o o +===) ~ I
I       I       I I   I I I         I   I I I   I         I   I   I I I       I
I (=z=\ L===) o L=+=) ~ ~ L=z=\ F===J o ~ L=+===+=) (=====+=) I (=+=J ~ (=z=\ I
I   I I       I             I I I     I                   I   I   I       I I I
+=z=J L===\ o L=z=) F=======+ ~ ~ (===+ (=z=z=z=z===z===z=+=) I (=+=\ o o I ~ I
I I       I I   I   I       I         I   I I I I   I   I I   I     I I I I   I
I ~ o o o ~ I (=+=) ~ o o o ~ o F===) I o ~ ~ I ~ o ~ o ~ L===+=z===+=+=+=J o I
I   I I I   I   I     I I I   I I     I I     I   I   I         I       I   I I
+===+=+=+=z=J o +=====+=+=+===+=+ o o L=+=\ (=+=\ L===+===\ (=z=J (=z=) ~ o I I
I     I I I   I I     I I       I I I     I     I         I   I     I     I I I
+===) ~ ~ ~ o I ~ o o ~ L===) o +=+=+===\ I o o ~ (=======+===+ o F=+=) F=+=+ I
I           I I   I I         I I       I I I I               I I I     I   I I
I F===z=z===+=J (=+=J o o o o I ~ o (===+ L=+=+=z=\ o o o (===+=+=J F===J o ~ I
I I   I I         I   I I I I I   I     I     I I I I I I     I     I     I   I
+=+=) ~ ~ o F===) L=z=J I L=+=+ (=+=) o I (===+ ~ ~ I I I o (=+=) F=+=) o I o I
I         I I       I   I     I   I   I I     I     I I I I   I   I     I I I I
L=========+=+=======+===+=====+===+===+=+=====+=====+=+=+=+===+===+=====+=+=+=J
I present a number of challenges to the coding-savvy people: 3 points: Change the code to produce loops in the maze. 9 points: Change the code such that it compiles on compilers that do not support C++0x. 13 points: Change the code such that it uses Unicode line-drawing characters, block elements and other geometric shapes for a beautiful outcome. To get you started, the code is already written using the wchar_t type. You don't need to write utf-8 encoders and decoders. 1 point: Change the code such that it may produce locations on the map that are unreachable. 20 points: Complete the above task, and change the code to indicate the unreachable areas somehow (for example, by using "." instead of " " for those unreachable locations). 1 point: Change the code to produce two exits somewhere on the opposing edges of the maze. 15 points: Complete the above task, and change the code to indicate the longest solution path between the two exits (walking the same path twice is not allowed, though crossing the path is allowed). 24 points: Translate the code into LUA. In all of these tasks, particularly artistically written code and nice looking output may both give extra points. Lucky bugs or code that doesn't quite work may reduce your points. Send your solutions to me by a PM. Put the word "maze" somewhere in the message subject. Indicate which challenges you have solved, and which platforms you have compiled the program on. A copy of the solution's output is preferable. Multiple submissions by the same author are accepted; the latter submission overrides the earlier one. This challenge is open until 2009-04-20. I will try to maintain a leaderboard in this post. After the challenge closes, I will post some if not all of the source code submitted. The number of points awarded on each category is subject to change, but I will try to keep it fair. EDIT: Challenge is closed now. Here's a useful hint on C++0x.
Posted: 4/2/2009 5:44 PM
Post subject: Re: C++ exercises
Quote
Warp
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Bisqwit wrote:
13 points: Change the code such that it uses Unicode line-drawing characters, block elements and other geometric shapes for a beautiful outcome. To get you started, the code is already written using the wchar_t type. You don't need to write utf-8 encoders and decoders.
But if you want to print unicode characters, don't you have to decide which encoding you are going to use to print them? After all "unicode characters" are just numerical values between 0 and some millions, or whatever. You just can't print "unicode characters" without deciding which encoding you are going to use to print them.
Posted: 4/2/2009 6:16 PM
Quote
Derakon
Joined: 7/2/2007
Posts: 3960
I find this interesting mostly because I spent some time implementing a growing-tree maze generator and an algorithm for determining tile types for one of my projects: I'm leaving a hollow at the "end" of the maze, hence the open space/loop. Your love of short variable names and terseness makes it a bit hard for me to follow what your code is doing (my average variable name length is probably ten times yours :)). I think you're basically placing wall segments down randomly such that each segment hits another wall precisely once. However, your code to select which character to draw has me completely baffled. You seem to be constructing some kind of string and then indexing into it, but I've never seen the L"" construct before. Some discussion on approaches to your challenges is below; I'm not going to participate in the actual challenge because I have other work I need to do. Creating inaccessible regions should be straightforward; simply allow walls to touch more than one other wall. Doing this while still allowing the maze to be solvable (which I'm arbitrarily deciding means getting from the upper-left to the lower-right) is trickier; one possible approach would be to decide on the solution to the maze ahead of time using a random-walk algorithm, and forbidding any walls from crossing the solution. Of course, you'd need to make certain that your "solution" didn't take up too much of the maze. Similarly, creating loops just involves allowing walls to be created that don't touch any other walls. Longest paths only make sense in a map that has loops (since otherwise there's only one path). In any event, the page I linked above has some exhaustive maze solvers.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Posted: 4/2/2009 9:57 PM
Post subject: Re: C++ exercises
Quote
Bisqwit
Editor, Active player (297)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Warp wrote:
But if you want to print unicode characters, don't you have to decide which encoding you are going to use to print them?
Yes (or not really, you can delegate that stuff to locale handling), but you don't need to encode them in any particular non-ascii way in the source code.
Posted: 4/2/2009 11:17 PM
Quote
Ver_Greeneyes
Joined: 4/2/2008
Posts: 103
Location: The Netherlands
'L' just means 'this should be Unicode', hence the TEXT macro: 
#ifdef UNICODE
#define TEXT(quote) L##quote
#else
#define TEXT(quote) quote
#endif
I've been doing way too many things involving strings this past week.. why couldn't we have just settled on a system years ago and stuck with it? (on ALL PLATFORMS) But I don't want to derail the topic, so carry on :)
Posted: 4/22/2009 6:17 AM
Quote
Bisqwit
Editor, Active player (297)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Wow. No submissions whatsoever :o Well, the challenge is closed now. Derakon gets a cookie for trying.
Posted: 4/22/2009 7:36 AM
Quote
GMan
Joined: 4/7/2008
Posts: 117
Aw dang. I started, I guess I should have submitted :O I had:
    3 points: Change the code to produce loops in the maze. 9 points: Change the code such that it compiles on compilers that do not support C++0x. 13 points: Change the code such that it uses Unicode line-drawing characters, block elements and other geometric shapes for a beautiful outcome. To get you started, the code is already written using the wchar_t type. You don't need to write utf-8 encoders and decoders. 1 point: Change the code to produce two exits somewhere on the opposing edges of the maze.
But then finals started coming up :)
Posted: 4/22/2009 11:55 AM
(Edited: 4/22/2009 12:40 PM)
Post subject: _|￣|o
Quote
Xkeeper
Banned User
Joined: 12/23/2004
Posts: 1850 
C:\lua>lua5.1 maze.lua
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ @                                 @                           @         @ @ @
@ @ @@@@@@@ @@@@@@@@@@@ @@@@@ @@@@@ @ @ @@@@@@@@@ @@@@@ @ @@@@@ @ @@@@@ @ @ @ @
@       @ @                   @ @     @ @               @   @ @       @ @     @
@@@ @@@@@@@@@ @ @@@@@@@ @@@@@ @ @ @@@@@ @@@@@@@ @@@@@@@ @ @@@@@ @@@@@ @ @ @@@@@
@     @       @                   @ @ @     @     @ @   @   @   @ @           @
@@@@@@@@@ @@@@@ @ @ @ @ @@@@@ @@@@@@@ @ @ @ @ @ @ @ @ @ @ @@@@@ @ @@@@@@@@@@@ @
@ @             @ @ @ @ @               @ @   @ @     @   @         @   @     @
@ @ @@@@@ @ @ @@@@@ @ @ @@@@@ @@@@@ @@@@@ @@@@@ @ @ @@@@@ @ @@@@@ @ @ @ @ @@@@@
@         @ @     @   @         @     @           @       @       @   @       @
@ @ @@@@@ @ @@@@@ @ @ @ @ @ @ @@@@@ @@@@@@@@@ @ @ @ @@@@@ @@@@@ @@@@@ @@@@@@@ @
@ @       @     @   @   @ @ @                 @ @                 @           @
@ @@@@@ @ @ @ @@@@@@@@@ @ @ @ @@@@@@@@@ @@@@@ @@@@@ @@@@@@@@@ @ @@@@@ @ @@@@@ @
@   @   @   @                 @                           @   @       @ @ @   @
@ @@@@@@@ @@@@@ @@@@@@@@@@@@@ @ @@@@@@@ @ @@@@@ @@@@@@@@@ @@@@@@@@@ @@@@@@@@@ @
@       @         @     @   @           @ @ @     @         @                 @
@ @@@@@ @ @@@@@@@ @ @ @ @ @@@@@ @@@@@@@@@@@ @ @ @ @ @@@@@@@ @ @ @@@@@@@@@ @@@@@
@       @           @ @       @       @ @   @ @ @     @ @     @ @ @   @       @
@@@@@ @ @ @@@@@@@@@ @ @@@@@ @@@@@@@@@ @ @ @ @ @@@@@ @ @ @ @@@@@ @ @@@@@@@ @@@@@
@     @ @ @         @   @       @ @       @         @               @       @ @
@@@@@ @ @ @ @ @@@@@@@@@ @ @@@@@ @@@@@ @ @@@@@ @ @@@@@ @@@@@ @@@@@ @ @@@@@ @ @ @
@ @   @     @                         @   @   @                   @   @   @   @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@


C:\lua>
It, uh, works, I guess. Kind of funny in that it both allows loops and creates inaccessabilities, even though that really isn't intentional... Just for posterity, this is the output before I trashed the generation code: 
C:\lua>lua5.1 maze.lua
*******************************************************************************
*         *         *       *         *       *     *   *     * *         *   *
**@ @ @ @ @ @ @*@ @ @ @ @*@*@*@*@ @ @ @ @*@ @*@*@*@*@ @ @ @*@*@*@*@*@ @ @ @ @**
*         * *     *   * * *                             *       *     *   *   *
**@*@ @ @ @ @*@*@*@*@ @*@*@*@ @*@*@*@ @ @*@ @ @ @ @*@*@*@ @ @ @ @ @ @ @ @ @ @ *
*     * *   *   * *       *     *     *       *                       * *     *
**@*@ @ @ @*@*@*@*@*@*@*@ @*@*@*@*@*@*@ @ @ @ @*@*@*@*@ @ @ @ @ @ @ @*@*@*@*@**
*     *         *   *       *   *     *         * *     * *           * *     *
* @ @ @ @*@ @*@*@*@*@ @ @ @ @ @ @ @ @*@*@*@*@ @ @*@*@*@*@*@ @ @ @*@*@ @ @ @ @ *
*     *             *     * *                 * * *   * * *           *   *   *
**@ @ @*@*@*@*@ @ @ @ @*@*@*@*@ @*@*@*@*@*@*@ @ @ @ @ @ @ @ @ @ @ @ @*@*@*@*@ *
* *     *       *         *         * *       *   * * *                 * * * *
* @ @ @ @ @*@ @*@*@ @ @ @ @ @ @*@*@*@*@ @ @ @*@ @*@*@*@*@*@*@ @*@*@ @*@ @ @ @**
* * * * * * *       *     *         * * *       * * * *       * *   *   *   * *
* @ @ @ @*@*@*@*@ @*@*@*@*@*@ @ @ @ @*@*@*@*@ @*@*@*@*@*@ @ @ @ @*@ @ @ @ @ @ *
* * * *             *           *     *       * *           * * *             *
* @ @ @ @ @ @*@*@*@ @ @ @*@*@*@*@ @ @ @*@*@*@ @ @ @*@*@*@*@ @ @ @ @ @*@ @ @ @ *
*   *     *       * * *     *   *       *     *   * * *     * *         *     *
* @ @ @ @ @ @ @ @*@*@*@*@ @ @ @ @ @ @ @*@ @*@*@*@*@*@*@*@ @ @ @ @*@*@*@*@*@ @ *
*     *   *       * *   *           *       *     * * *                 *   * *
**@ @ @ @ @ @ @ @ @ @ @*@*@*@*@*@ @ @*@*@*@*@*@ @ @ @ @ @ @ @ @ @*@ @ @ @ @*@**
*     * *   * * *               * * *   * * *     *       * * * *       *   * *
*******************************************************************************


C:\lua>
It fundamentally will not work, so... For refrence, snippets of code (mess of debug shit everywhere, beware): 
	for i = 0, 10000 do
		local x		= math.random(1, halfw) * 2 + 1;
		local y		= math.random(1, halfh) * 2 + 1;
		local x2	= 0;
		local y2	= 0;
		local maxl	= 2;
		if math.random(0, 1) == 0 then
			x2		= math.random(0, 1) * 2 - 1;	-- fancy (i.e. stupid) way of getting -1 or 1
			maxl	= 4;
		else
			y2		= math.random(0, 1) * 2 - 1;
		end;

--		print(string.format(" x %02d  xx %02d    y %02d yy %02d", x, x2, y, y2));
		if m[y][x] == 0 then
			m[y][x]	= 2
			for t = 1, maxl do
--				print(string.format("  x %02d  xx %02d    y %02d yy %02d", x, x + x2, y, y + y2));
				if (x + x2) <= 1 or (y + y2) <= 1 or (x + x2) >= w or (y + y2) >= h then
					maxl	= -1;

				elseif m[y + y2 * 2][x + x2 * 2] >= 1 then
--					m[y     ][x     ]	= 1
					m[y + y2][x + x2]	= 1
					m[y + y2][x + x2]	= 1
					x	= x + x2 * 2;
					y	= y + y2 * 2;
				else
					maxl	= -1;		-- breaking out for lazy people
				end;
			end;
		end;		
		

	end;
Perma-banned
Posted: 4/22/2009 11:57 AM
Quote
Bisqwit
Editor, Active player (297)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Xkeeper wrote:
it both allows loops and creates inaccessabilities, even though that really isn't intentional...
Well, fix that first :) Those are default features that are usually produced by naive/buggy maze generation algorithms; I only included them in the list because for introducing them in that C++ code requires a bit of understanding how it works.