Difference between revisions of "Notes"

From Ghoulwiki
Jump to: navigation, search
(misc)
Line 20: Line 20:
 
* http://happypenguin.org/show?Project%20LRNJ%3A%20Slime%20Forest  (japanese learning game)
 
* http://happypenguin.org/show?Project%20LRNJ%3A%20Slime%20Forest  (japanese learning game)
 
* http://happypenguin.org/show?BitRock%20InstallBuilder (bitrock crossplatform installer builder)
 
* http://happypenguin.org/show?BitRock%20InstallBuilder (bitrock crossplatform installer builder)
 +
 +
=== print ===
 +
 +
<pre></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></pre>

Revision as of 11:47, 23 May 2007

links to look at :

social net

screencasting

misc

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>