Posts by gashtio

Ok and the code OP showed should be similarly proved right? Like so :

Summation from i = 1 to N
Summation from j = x, where x = 2^i

Thus N * Summation from j = x, where x = 2^i = {1,2,4,8,16...}

If you look on wiki_summation. In the growth rate section it tells you that: Summation from i to N of c^i = THETA(c^n).
In our case c = 2, thus Summation from i to N of 2^i = THETA(2^n);

Thus N * Summation from j = x, where x = 2^i
= N * THETA(2^n)
= THETA(n*2^n)

"Summation from i to N of c^i" is exactly what the code does, you're confusing the second loop with something that it is not :). Maybe you're considering "Summation from j = x, where x = 2^i" as O(2^N) and summing that N times, which does indeed result in O(N * 2^N), but a better bound can be found. Here's a picture that might clear things up:

The User-agent field is mainly used for formatting the response accordingly (e.g. for mobile phones) and shouldn't result in an error code(4xx). The 405 you're getting means that the method used in the request (POST) is not allowed. If you examine the headers of the response from google.com you'll see "Allow: GET, HEAD" so you'll have to change the request method to either of those.

On a side note, if you're only going to be sending text and not binary data, you don't need the "multipart/form-data" content type.

You can use BinaryFormatter 's Serialize and Deserialize methods instead of StreamWriter / StreamReader . Here's a little sample I wrote (with no error checking at all):

Receiver

static void Main(string[] args)
{
    TcpListener listener = new TcpListener(IPAddress.Any, 5005);
    listener.Start();
    Console.WriteLine("Server started.");

    Socket client = listener.AcceptSocket();
    Console.WriteLine("Accepted client {0}.\n", client.RemoteEndPoint);

    List<string> l = null;

    using (NetworkStream ns = new NetworkStream(client))
    {
        BinaryFormatter bf = new BinaryFormatter();
        l = (List<string>)bf.Deserialize(ns);
    }

    if (l != null)
        foreach (var item in l)
            Console.WriteLine(item);

    client.Close();
    listener.Stop();
}

Sender

static void Main(string[] args)
{
    TcpClient client = new TcpClient();
    client.Connect(new IPEndPoint(IPAddress.Parse("127.0.0.1"), 5005));
    Console.WriteLine("Connected.");

    List<string> l = new List<string>() { "Lorem", "ipsum", "dolor", "sit", "amet" };

    BinaryFormatter bf = new BinaryFormatter();
    NetworkStream ns = client.GetStream();
    bf.Serialize(ns, l);
    Console.WriteLine("Data sent.");

    ns.Close();
    client.Close();
}

I didn't test it, but here are the problems I saw:

First, your bounds check is incorrect - if((row == size) || (row < 0) || (column > size) || (column < 0)) should be if((row >= size) || (row < 0) || (column >= size) || (column < 0)) Second, you aren't backtracking at all - you're just picking a single path and following it as far as possible. To correct that you have to replace all the [B]else[/B] if s in the "tries each possible move" block with just if s, and if all of them fail, return the current position's state to unused (0). In pseudocode that would be something like this:

function next_move(x, y, level)
    board[x][y] = level
    if(level == side*side)
        print solution
        return found
    
    for each possible move (u,v) from (x,y)
        next_move(u, v, level+1)

    board[x][y] = 0

Then just call next_move(startx, starty, 1) from the main procedure.

And last, using simple backtracking results in an exponential algorithm that will take ages even for the current maximum you've set (20). You should consider using Warnsdorf's heuristic (or simply put, the next square you choose is the one that has the least possible moves left) which will bring down the complexity to linear in the total number of squares.

I see... why do they provide these make_heap functions then?

Because you might have an existing collection that you want to turn into a heap in-place, instead of duplicating the elements using push es into a priority_queue .

Or, if you want to guarantee a O(nlogn) bound of a sort, you can use make_heap alongside sort_heap to produce heap sort (although library implementations of std::sort usually have optimizations so it doesn't degenerate to O(n^2)).

There's a newline between 1010101a and 1a, which has a different character code from 'a', so you get an additional true in your vector.

Use _tprintf( TEXT("%s"), lpszDevName ); instead. You'll also have to #include <tchar.h> .

Here's some code that issues a GET request and writes the response to file. I tested it on Windows only, but it should work on Linux, too.

It doesn't exactly "fill the search box, and click submit button", but should be enough to get you started.

#ifdef WIN32
	#define _CRT_SECURE_NO_WARNINGS
	#include <stdio.h>
	#include <string.h>
	#include <Ws2tcpip.h>
	#define LASTERROR WSAGetLastError()
	#define close_socket(sockfd) closesocket(sockfd)
	#define cleanup(sockfd) { closesocket(sockfd); WSACleanup(); }
	#pragma comment( lib, "WS2_32.lib" )
#else
	#include <unistd.h>
	#include <stdio.h>
	#include <string.h>
	#include <sys/types.h>
	#include <sys/socket.h>
	#include <arpa/inet.h>
	#include <netdb.h>
	#include <errno.h>
	typedef int SOCKET;
	#define INVALID_SOCKET -1
	#define SOCKET_ERROR -1
	#define LASTERROR errno
	#define close_socket(sockfd) close(sockfd)
	#define cleanup(sockfd) close(sockfd)
#endif

#define OUTPUTFILE "response.html"
#define MAXDATASIZE 8000 // max number of bytes we can get at once

//--------------------------------------------------------------------------------------

static void * get_in_addr( struct sockaddr * sa )
{
	if ( sa->sa_family == AF_INET ) // IPv4 address
		return &(((struct sockaddr_in *)sa)->sin_addr);
	else // IPv6 address
		return &(((struct sockaddr_in6 *)sa)->sin6_addr);
}

//--------------------------------------------------------------------------------------

int main()
{
	FILE * hOutput;
	SOCKET sockfd;
	char Buffer[MAXDATASIZE];
	struct addrinfo hints, *pResults, *p;
	int ret;

	char szDotDecimalIp[INET6_ADDRSTRLEN];
	const char * szQuery = "/search?q=web+automation+c%2B%2B";
	const char * szHost = "www.google.com";
	char szHttpRequest[1024];
	
#ifdef WIN32
	const int op_timeout_ms = 2000; // Timeout for send/recv
	WSADATA wsa;
	WSAStartup( MAKEWORD(2,2), &wsa );
#endif

	// ---- Get the IPs of the host
	memset( &hints, 0, sizeof hints );
	hints.ai_family	  = AF_UNSPEC;
	hints.ai_socktype = SOCK_STREAM; // TCP socket
	if ( (ret = getaddrinfo( szHost, "http", &hints, &pResults )) != 0 )
	{
#if …

The problem lies in the loop filling the bitmap data.

You can make a simple calculation of how many bytes you are writing - 3 each iteration, width*height/3 iterations - a total of width*height bytes, not pixels. Essentially, you're writing to every third pixel, hence the diagonal lines.

To correct the problem you should just replace the j+=3 in the loop with j++ .

This code should only hang if you lift the key while the worker thread is executing this:

while(WaitForSingleObject(input->run, 0) != WAIT_OBJECT_0)
{
	SetWindowTextA(input->hWnd, "Hello");
	Sleep(500);
	SetWindowTextA(input->hWnd, "Goodbye");

but not this:

Sleep(500);
}

The problem is that SetWindowText actually sends WM_SETTEXT (sends, not posts) so it blocks until the main thread handles it. But after setting the event the main thread is stuck waiting on hThread and you get a deadlock.

To avoid that you should post the message instead of sending it (bear in mind that you can't post WM_SETTEXT, so you'll have to define your own message and handle it in the main thread procedure).

Hmm, sorry, I thought that by dynamic you meant that you just get your address from a DHCP server and still connect directly to the internet, not behind a router.

Anyway, I don't think this can be done easily, your best shot is probably to connect to a HTTP server which reports your external IP, such as www.whatismyip.com, and parse the reply.

You can use this (and probably add some error checking):

// Gets the local IP address
// IPv4 address and little-endian machine are assumed

#include <cstdio>
#include <ws2tcpip.h>
#pragma comment(lib, "ws2_32.lib")

int main()
{
	WSADATA wsadata;
	WSAStartup( MAKEWORD(2, 2), &wsadata );

	char buffer[256];
	struct addrinfo * result;
	struct addrinfo hints = { 0 };
	hints.ai_family = AF_INET;

	gethostname( buffer, sizeof(buffer) ); // Get the standard host name for the local computer.
	getaddrinfo( buffer, NULL, &hints, &result );

	printf( "%s\n", buffer );
	struct addrinfo * ptr = result;
	while( ptr )
	{
		ULONG addr = ((struct sockaddr_in *)ptr->ai_addr)->sin_addr.S_un.S_addr;

		if (
			( ( addr              ) != 0x0100007F ) &&	// 127.0.0.1
			( ( addr & 0x000000FF ) != 0x0000000A ) &&	// 10.0.0.0/8 range
			( ( addr & 0x00000FFF ) != 0x000010AC ) &&	// 172.16.0.0/12 range
			( ( addr & 0x0000FFFF ) != 0x0000A8C0 )		// 192.168.0.0/16 range
			// ... other ranges you want to skip ...
			)
		{
			getnameinfo( ptr->ai_addr, ptr->ai_addrlen, buffer, sizeof(buffer), NULL, NULL, NI_NUMERICHOST );
			printf( "%s\n", buffer );
		}

		ptr = ptr->ai_next;
	}

	freeaddrinfo( result );
	WSACleanup();


	return 0;
}

You can achieve the same using gethostname() and the deprecated gethostbyname() by iterating through the h_addr_list list in the hostent * returned by gethostbyname().

You are taking the address of a char pointer to get string and taking the address of a char to get the character itself - these are the problems with cout << "Characters:" << &temp << endl and while(&temp[i]!=0) ; In the former, you're taking the address of the pointer temp , while in the latter you're checking whether the address of the i-th element of temp is NULL, which is never true hence the segmentation fault.

The right thing to do is check if the i-th element itself is NULL, not its address.

On a side note, string operations are usually slow, so you might want to avoid doing filename+=temp[i] ; Also, if DataMemory is an ordinary contiguous array with element size of 4 bytes, and step is always 1, then you can omit the whole if(i==3) block.

And finally, a much easier way to get the filename would be to just do string filename( temp ) - this constructor treats temp as a C string and automatically scans the memory pointed by the argument until it finds a 0.

Yes, that's right - you add a node with the same coordinates but different f/g/h costs - that's the duplication I was talking about.

The "g_score[y]" solution uses an array which maps all nodes with the same coordinates to the same element of the array(and consequently each coordinate has only 1 set of f/g/h values associated with it).

In the solution I posted, no such array exist but rather each node has coordinates + f/g/h costs associated with it. Because the priority queue sorts the nodes by their f value, you're guaranteed to first get the one closest to the target, and when you encounter a node with the same coordinates you just skip it (it's inserted in the closed set the first time you see it).

You can do fine using the STL's priority queue with some modification of that pseudocode - namely always inserting the neighbours in the PQ, unless they are in the closed set. This will result in having duplicate nodes (with different f/g costs) in the PQ, so each time you pop a node, you have to check if it's already in the closed set.

i.e the pseudocode becomes (I'll be referring to the openset as PQ):

while PQ is not empty
	x := the top node of PQ
	remove x from PQ
	if x = goal
		return reconstruct_path(goal.came_from)

	if x in closedset
		continue

	add x to closedset

	foreach y in neighbor_nodes(x)
		if y in closedset
			continue

		y.came_from = x
		y.g_score = x.g_score + dist_between(x,y)
		y.h_score = heuristic_estimate_of_distance(y, goal)
		y.f_score = y.g_score + y.h_score // this is useless...

		add y to PQ

return failure

The author of the wikipedia article probably had in mind using a priority queue, which supports the DecreaseKey operation. That way the queue won't get bloated with duplicate items and you'll have a performance gain.

Just extract the bytes from the string and then append the file contents. One way to do that is to create another vector and copy the header and contents there:

#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>

void HexDump( char ch ) { std::cout << std::setw(2) << std::setfill('0') << (short)ch << " "; }

int main()
{
	// ---- Prepare POST header and file data

	char randomBytes[] = { 0x67, 0x0, 0x45, 0x3, 0x0 , 0x3, 0x65, 0x32 };
	std::vector< char > vFileData( randomBytes, randomBytes + _countof(randomBytes) );

	std::string PHP_Script	= "/";

	std::string Post_Request =
		"POST " + std::string( PHP_Script ) + " HTTP/1.1\r\n"; // etc., etc.

	// ---- Allocate a buffer large enough for the whole request
	std::vector< char > vRequestBytes( Post_Request.size() + vFileData.size() );

	// ---- Copy header into final buffer
	std::vector< char >::iterator it = std::copy( Post_Request.begin(), Post_Request.end(), vRequestBytes.begin() );

	// ---- Copy content into final buffer
	std::copy( vFileData.begin(), vFileData.end(), it );

	// ---- Dump buffer
	std::cout << std::hex << std::setiosflags( std::ios_base::uppercase );
	std::for_each( vRequestBytes.begin(), vRequestBytes.end(), HexDump );
	std::cout << std::endl;

	return 0;
}

If you don't want to create another buffer, you can assemble the header into a char array(vector), get the size of the contents file, allocate a buffer large enough for the array and the file, then copy the header in the beginning of the buffer and fread the file data immediately after it.

Generally, you should avoid using std::string for assembling a HTTP request …

You're probably missing comdlg32.lib in your linker settings.

By the way, the Common File Dialog API has been superseded by the Common Item Dialog API.

As firstPerson said, the last digits can be obtained by modular exponentiation.
Getting the first digits requires some mathematical trickery, but nothing too special.

I've commented the code so it shouldn't be hard to understand.

#include <cstdio>
#include <cmath>
typedef unsigned int UINT;
typedef unsigned long long ULL;

//--------------------------------------------------------------------------------------
// Calculates a^n mod k
//--------------------------------------------------------------------------------------
UINT modexp( UINT a, UINT n, UINT k )
{
	//	using the fact that (a*b) % m = ((a%m) * (b%m)) % m:
	//
	//		 	 |	1				n = 0
	//	a^n % m	=	<	( (a%m) * ((a^(n-1))%m) ) % m	n is odd
	//		 	 |	(a^2 % m)^(n/2) % m		n is even

	// promote a and k to 64-bit integers,
	// since we need to calculate squares of 32-bit ints
	ULL base = a;
	ULL mod = k;

	ULL res = 1;
	while ( n > 0 )
	{
		if ( n & 1 ) // n is odd
			res = (res * base) % mod;

		n /= 2;
		base = (base * base) % mod;
	}

	return (UINT)res; // after taking the modulo, res fits nicely into an UINT
}

UINT get_last_k( UINT a, UINT n, UINT k )
{
	UINT mod = 1;
	while ( k-- ) mod *= 10; // 10^k

	return modexp( a, n, mod ); // last k digits of a^n = a^n % 10^k
}

//--------------------------------------------------------------------------------------
// Calculates the first k digits of a^n
//--------------------------------------------------------------------------------------
//#define log10(x) log(x)/log(10.0)

UINT get_first_k( UINT …

You have to process the WM_CTLCOLORSTATIC message in the parent window (WM_CTLCOLOREDIT should you change the edit box style so it is neither disabled nor read-only). It is sent by the control to its parent before being drawn, passing its device context in the WPARAM, so you can change text/background color in the message handler.

The code would be something like this:

case WM_CTLCOLORSTATIC:
{
	HDC hEdit = (HDC)wParam;

	SetTextColor( hEdit, RGB(0, 0, 0) );
	SetBkColor  ( hEdit, RGB(255, 255, 255) );

	// Do not return a brush created by CreateSolidBrush(...) because you'll get a memory leak
	return (INT_PTR)GetStockObject( WHITE_BRUSH );
}

The return value is the brush used to paint the background. Also, the MSDN documentation is incorrect, the brush is not deleted by the system (at least not on Vista/7) so if you need a custom color brush, create it once and delete it when the window closes.

Bear in mind that the system overrides the text color of disabled controls, so you wouldn't be able to change it this way. Instead, you can specify ES_READONLY when creating the edit box (the text will be selectable, though).

It's always nice to see people posting tutorials, but I have to disagree with both pieces you posted.

You need not do any of these things, because that's the compiler's job - making the machine code optimal. Precalculating constants and rearranging expressions in weird ways only makes code hard to read and follow. You should write code that is easy to maintain and leave optimizations to the compiler - it usually does a better job than you would anyway :).

Here are some codes and the pertinent parts of the disassembly using MSVC 2008 and /O2 for optimization:

#include <cstdio>
#define _USE_MATH_DEFINES
#include <cmath>

double DegToRad( const double& lfDeg )
{
	return lfDeg * (M_PI / 180.0);
}

int main()
{
	double lfDeg = 0.0;

	scanf( "%lf", &lfDeg );
	double lfRad = DegToRad( lfDeg );

	printf( "%lf\n", cos( lfRad ) );

	return 0;
}

double lfRad = DegToRad( lfDeg );
00BF1023  fld         qword ptr [esp+40h]				// push lfDeg on top of the FPU stack
00BF1027  fmul        qword ptr [__real@3f91df46a2529d39 (0BF2110h)] 	// multiply top of FPU stack with 0.017453... (0x3f91df46a2529d39 in memory)

The compiler premultiplied M_PI / 180.0 and inlined the function without even hinting.

...
int a, b, c, d;
scanf( "%d %d %d %d", &a, &b, &c, &d );

int res = a * b + a * c + a * d;

printf( "%d\n", res );
...

00CC1022  mov         ecx,dword ptr [esp+14h] 	// load b into ecx
00CC1026  mov         edx,dword ptr [esp+18h] …

HTTP headers must end with a CR/LF line, so you should add sprintf(Get_Request, "%s\r\n", Get_Request); at the end to get it working.

Also, when recv() -ing, you shouldn't use strlen(Response) as the length argument, since your buffer isn't initialized, so strlen will pretty much return random numbers. Instead, use sizeof(Response) - 1 and then add the terminating null character with Response[iResult] = '\0'; .

And a second thing, gethostbyname has been deprecated for a long time, you should consider using getaddrinfo .

You can call ISpVoice::Speak asynchronously and then use the ISpVoice::WaitUntilDone method, which does exactly what you want.

pVoice->Speak( szText, SPF_ASYNC, NULL );
pVoice->WaitUntilDone( 3000 ); // 3 seconds

The problem lies here HashTable = new (nothrow) ListSet [size]; .

Short explanation:

You are allocating an array of ListSet objects and handing the returned pointer to a Set * . This is not how inheritance works - you should allocate an array of Set pointers instead, and then allocate a ListSet object for each pointer. In code, that is:

int nSize = ...;
Base ** ppStuff = new Base * [nSize];
for( int i = 0; i < nSize; ++i )
	ppStuff[i] = new Derived();

...

for( int i = 0; i < nSize; ++i )
	delete ppStuff[i];
delete [] ppStuff;

Long explanation:

Every class that has virtual functions has a static virtual table - that's essentially an array of function pointers, one for each virtual function. Hidden from the programmer, the compiler adds a member variable - a pointer to that v-table. So your Set class actually looks something like this (in pseudocode):

class Set
{
public:
	typedef string T;
	virtual void Add(const T& key) = 0;
	virtual bool Contains(const T& key) = 0;
	virtual void Print() = 0;
	virtual void Remove(const T& key) = 0;

	function_ptr * __vfptr; // a pointer to a function pointer
	static function_ptr __vftable[] = { &Set::Add, &Set::Contains, &Set::Print, &Set::Remove };
	__vfptr = &Set::__vftable[0];
};

and the ListSet class:

class ListSet : public Set
{
	...

	static function_ptr __vftable[] = { &ListSet::Add, &ListSet::Contains, &ListSet::Print, &ListSet::Remove }; // this table is different from the Set one
	__vfptr = …

You can use one of the Marshal::StringToHGlobalAnsi/Auto/Uni methods to copy the string into unmanaged memory, and then clean up with Marshal::FreeHGlobal when you're done.

There's an example here that does exactly that.

Assuming 2^n takes O(1) time, the complexity is O(log* n), that is, the iterated logarithm of n.

This happens because StreamReader::ReadLine returns nullptr when the end of stream is reached (which is the case when reading an empty file).

That means that on line 8 of your code line is now nullptr , and not the initial empty string. Since they do not compare equal to each other, the second if statement is entered, and because nullptr does not have a string representation, nothing is printed between the two 2's.

To observe the correct behavior, change the last part to:

if ( String::IsNullOrEmpty( line ) )
{
	MessageBox::Show("1" + line + "1");
}
else
{
	MessageBox::Show("2" + line + "2");
}

The recv() function will return <= 0 if either a socket error occurs or the socket has been closed on the server side. If none of these are true, it will just block, waiting for data. So, I'm guessing your problem is that you didn't close the socket.

If, for some reason, you wish to still have it open after the transfer, you should count the bytes you receive from recv() and exit the loop when you're done, like so:

int cbFileSize = ...;

			...

			int cbTotalReceived = 0;
			while(int i = ::recv(sock , buffer , 1 , 0) > 0)
			{
				cout << i;
				in.write(buffer , 1);
				cbTotalReceived += i;
				if( cbTotalReceived >= cbFileSize ) break;
			}

Also, on a side note, send larger batches of data instead of just 1 byte - it's much more efficient.

There are quite a few things wrong :).

- All the "mdim_ = mdim_;" stuff is useless.

- In the Matrix(int cols) constructor, mdim_ remains uninitialized and you're getting a crash - you should set it to cols.

- The SetElement() function is incorrect, it should read:

void Matrix::SetElement(int m, int n, double d)
{
	data_[(m - 1) * ndim_ + n - 1] = d;
}

- In WriteToFile(), the correct formula is:

myfile << data_[i * ndim_ + j] << " ";

The idea is that you've processed i rows, each having ndim_ columns, plus j more columns from the current row.

Also, you need to open the file just once, not in each innermost iteration.

And you should probably do some error checking when adding (are the matrices the same size), setting element (is it within bounds), etc.

What is the desired direction of the ray? If it is +Z, just specify (0,0,1) for rayDirection.

Currently you're generating something rather strange - a direction parallel to the line, defined by the points (0,0,0) and (shotOrigin._41, 0, shotOrigin._43) from line 4 of your code.

Otherwise, the conversion from world to model space is correct. And btw, the call to D3DXMatrixIdentity() is redundant.