03.16.08

Tower of Hanoi

Posted in C/C++, Programming at 5:24 pm by Alper

The tower of Hanoi is a mathematical game invented by French mathematician Edouard Lucas in 1883. We are given a tower of eight disks, initially stacked in decreasing size on one of three pegs.

Tower of Hanoi

The objective is to transfer entire tower A to the peg B, moving only one disk at a time and never moving a larger one onto a smaller one.

The algorithm to transfer n disks from A to B in general: We first transfer n - 1 smallest disks to peg C, then move the largest one to the peg B and finally transfer the n - 1 smallest back onto largest (peg B).

The number of necessary moves to transfer n disks can be found by

Tn = 2n - 1.

Here is the sample solution in C:

#include <stdio.h>

void hanoi(int n_disks, char source, char destination, char temp)
{
	static n_move = 0;

	if (n_disks == 1) {
		printf("%d - Move the disk 1 from %c to %cn", ++n_move, source, destination);
	} else {
		hanoi(n_disks - 1, source, temp, destination);
		printf("%d - Move the disk %d from %c to %cn", ++n_move, n_disks, source, destination);
		hanoi(n_disks -1, temp, destination, source);
	}
} 

int main(int argc, char *argv)
{
	int n_disk = 8;
	char source = 'A';
	char destination = 'B';
	char temp = 'C';

	hanoi(n_disk, source, destination, temp);

	return 0;
}

11.21.06

Caching in PHP (Flat-File Caches)

Posted in PHP, Programming at 8:20 am by Alper

Flat-File caches is useful in PHP applications. Applications simply include cached file or directly use it as a file.

The main problem is reading and writing simultaneously in flat-file caching. There are two ways to avoid the problem.

1) Using file locks (flock — Portable advisory file locking).
2) Using temporary files.

Here is an example of flat-file caching with temporary files.

///////////////////////////////////////////////////////////////////////////////
<?php
$cached_file = basename($_SERVER[’PHP_SELF’]) . “.cache”;
if (file_exists($cached_file)) {
include($cached_file);
exit;
}
$temp_file =tempnam(”.”, $cached_file);
$fp_temp = fopen($temp_file, “w”);
ob_start();
?>
<!DOCTYPE HTML PUBLIC “-//W3C//DTD HTML 4.01 Transitional//EN” “http://www.w3.org/TR/html4/loose.dtd”>
<html>
<head>
<meta http-equiv=”Content-Type” content=”text/html; charset=utf-8″>
<title>Caching in PHP (Flat-File Caches)</title>
</head>
<body>
Here is an example of flat-file caching with temporary files.
</body>
</html>
<?php
if ($fp_temp) {
$buffered_contents = ob_get_contents();
fwrite($fp_temp, $buffered_contents);
fclose($fp_temp);
rename($temp_file, $cached_file);
}
ob_end_flush();
?>
///////////////////////////////////////////////////////////////////////////////
Download the code

The specification requires that the action of the rename function be atomic so if more than one process rename its temporary file, the last one succeeds.

It is obvious that our flat-file caching mechanism does not invalidate the cache! Our cache is forever! I will write about Cache Invalidation soon:)

Note :
When safe_mode is enabled, PHP checks whether the directory in which you are about to operate has the same UID (owner) as the script that is being executed.

References
- Advanced PHP Programming by George Schlossnagle.

08.02.06

Hello World!

Posted in Programming at 12:00 pm by Alper

int main(void)
{
printf(”Hello World!”);

return 0;
}