Difference between revisions of "Notes"

Revision as of 11:47, 23 May 2007

links to look at :

• http://www.alexa.com/site/ds/top_500 ( global website ranking based on traffic?)
• http://www.studivz.net/ (german student net)
• http://flickr.com/ (photos)

social net

• http://www.orkut.com/About.aspx?page=keep
• http://myspace.com/
• http://digg.com/ (technology news)

screencasting

• http://en.wikipedia.org/wiki/Xvidcap
• http://www.freecharity.org.uk/2007/04/12/the-secret-to-screencasting-with-ubuntu-and-free-software/

misc

• http://happypenguin.org/show?Project%20LRNJ%3A%20Slime%20Forest (japanese learning game)
• http://happypenguin.org/show?BitRock%20InstallBuilder (bitrock crossplatform installer builder)

print

</nowiki>
<?php
require("cryptutils.php");

// Nr17

/// returns true if bit is set
/// (1 << n) == 2^n   (shiftleft)
function TestBit ($mask,$bitnum) { return ($mask & (1 << $bitnum)) != 0; }

/// condition ? value_if_true : value_if_false
function F($x) {
	$mask = $x*($x+1);
	$res = 0;
	for ($i=0;$i<=4;++$i) $res += TestBit($mask,$i+1) ? (1 << $i) : 0;
	return $res;
}

/// $C is the subset that is being tested,  $C[$i] is x_i of the subset
function SubsetIsCycle ($C) {
	$r = count($C);
	if (F($C[$r-1]) != $C[0]) return false;
	for ($i=1;$i<$r;++$i) if (F($C[$i-1]) != $C[$i]) return false;
	return true;
}

function AsBitString10 ($x) { return strrev(sprintf("%010b",$x)); }
function AsBitString5 ($x) { return strrev(sprintf("%05b",$x)); }

/*
bruteforce
*/

$F_x_arr = array();
for ($x=0;$x<32;++$x) {
	$bitstring = AsBitString10($x*($x+1));
	
	// F(x)
	$tmp = 0;
	for ($i=0;$i<=4;++$i) $tmp += intval($bitstring{$i+2})*(1<<$i);
	$F_x_arr[$x] = $tmp;
	
	//echo "x=$x  x*(x-1)=".$bitstring." $tmp\n";
}

function GenerateChain ($x_0) {
	global $F_x_arr;
	$chain = array( 0=>$x_0 );
	while (1) {
		$Fx = $F_x_arr[$chain[count($chain)-1]];
		if (in_array($Fx,$chain)) break;
		$chain[] = $Fx;
	}
	return $chain;
}

//echo implode(",",$F_x_arr);

$checklist = array();
$cycle = array();
$domain = array();

for ($x=0;$x<32;++$x) {
	$chain = GenerateChain($x);
	//echo "$x : ".implode(",",$chain)."\n";
	
	//$last = $chain[0];
	$last = $chain[count($chain)-1];
	$key = array_shift(array_keys($chain,$last));
	
	// domains
	for ($i=0;$i<count($chain);++$i) 
		if (!in_array($chain[$i],$checklist))
			$domain[$last][] = $chain[$i];
	
	// cycles
	for ($i=$key;$i<count($chain);++$i) 
		if (!in_array($chain[$i],$checklist))
			$cycle[$last][] = $chain[$i];
	
	// checklist
	for ($i=0;$i<count($chain);++$i) 
		if (!in_array($chain[$i],$checklist))
			$checklist[] = $chain[$i];
}

foreach ($cycle as $i=>$vals) {
	sort($domain[$i]);
	$chain = GenerateChain($i);
	echo "C = {".implode(",",$chain)."}\n";
	echo "A(C) = {".implode(",",$domain[$i])."}\n";
	echo "\n";
}
		

/*
Nr.17 a) output :

C = {0}
A(C) = {0,1,2,6,10,11,15,23,25,26,27,28,29}

C = {3}
A(C) = {3}

C = {24,22,30,8,18,21,19,31}
A(C) = {4,5,7,8,9,12,14,16,17,18,19,20,21,22,24,30,31}

C = {13}
A(C) = {13}
*/

?>
</nowiki>