Category: Geek

I guess I’m into crypto currencies now

I was mad at myself for a long while for not getting into Bitcoin when the price was as low as $10 / btc not too long ago. I guess the main reason why I never invested is because I never fully understood the technology. To be fair I still don’t understand it 100%.

Then came the rise of “altcoins”, the alternative crypto currencies. I got especially excited about DogeCoin. What sets this currency apart from the 100s of other ones?

  1. It started as a joke, “meme” currency and I fucking loves memes
  2. It is dubbed as a “tipping” currency which encourages the flow of the money. The doge community actually donated over $30.000 for the Jamaican bobsled team so they can attend to the winter olympics
  3. Mining is relatively easy even with CPU

With all new crypto currencies there are new marketplaces where you can buy / sell coins. One thing I realized the price of coin is varies wildly depending on how much risk does the seller have to take for a given transaction.

For example: on eBay the price of doge is about £1 / 1000 coins because eBay uses Paypal and Paypal transactions are reversible, while Doge transactions aren’t.

On dogeforsale.com the price currently around £0.6 / 1000 if you buy via UK bank account. The seller still takes a little risk but not nearly as much with Paypal.

And finally there is the cheapest but most complicated way: Buy Doge with BTC. There is absolutely no risk there and you can get a 1000 coins for like £0.42. Naturally I went with this option, which raised an other issue: I have to acquire some BTC. I was using bitbargain.co.uk which is a peer to peer exchange and bought my first 0.5 BTC. Then using coinedup I exchanged them to Doges.

Now for selling i was considering dogeforsale, but got into a price war with some of the other sellers which made the price as low as it no longer worth my time to do it. So I moved on to eBay. As I mentioned selling crypto currencies via paypal is risky. The biggest risk you face is when someone is using a stolen paypal account for the purchase, then later the original owner issues a refund request. There are a few ways to protect yourself though:

  1. Only sell for eBay members with 50+ ratings (100% positive)
  2. Always ask the buyer to send his wallet address from the paypal email address to your email address (so you validate that they actually have access to the email account)

With this I made some good profit, but its still pocket money. I was started looking at profitable ways of mining BTC so I can achieve close to 100% profits. Some people says mining BTC is dead. Well turns out its not strictly true.

I found this cloud mining platform called cex.io which makes it possible to mine profitably with a relative small investment. You can purchase gigahash / sec mining power from them. When you purchase lets say 1 Gh/sec you actually own the hardware behind it (they actually deliver it to your door if you want it). If you don’t want to use the mining power anymore you can sell it back to the system.

The price of Gh/sec is fluctuating (oddly, as I see it correlates to the price of BTC which makes no sense, but whatever), at the moment its at 0.01176013 BTC / Gh. Luckily I found my old external hard drive which held my old BTC wallet with 2.3 BTC in it (talk about found money) and invested a portion of it for 100 Gh / sec. This mining power gave me about 0.02 BTC / day which equals about £7 profit daily. If I convert this to doge that will be around 17.000 doge coins and I can push that on eBay for £14-£17. If I get bored of it, or just want to cash out, I will sell back my Gh and exchange my BTC back to cash.

I’m doing this for about a month now. Lots of research, got scammed a couple of times but it kind of worth it. It is just fun to play broker with these virtual currencies. Yesterday for a little while I was a doge millionaire. Too bad you can’t get a physical, monopoly money-esque version of these coins.

Be Sociable, Share!

Facebook Hacker Cup 2013: My solutions

Task 1: Beautiful strings

When John was a little kid he didn’t have much to do. There was no internet, no Facebook, and no programs to hack on. So he did the only thing he could… he evaluated the beauty of strings in a quest to discover the most beautiful string in the world.

Given a string s, little Johnny defined the beauty of the string as the sum of the beauty of the letters in it.

The beauty of each letter is an integer between 1 and 26, inclusive, and no two letters have the same beauty. Johnny doesn’t care about whether letters are uppercase or lowercase, so that doesn’t affect the beauty of a letter. (Uppercase ‘F’ is exactly as beautiful as lowercase ‘f’, for example.)

You’re a student writing a report on the youth of this famous hacker. You found the string that Johnny considered most beautiful. What is the maximum possible beauty of this string?

Input
The input file consists of a single integer m followed by m lines.

Output
Your output should consist of, for each test case, a line containing the string “Case #x: y” where x is the case number (with 1 being the first case in the input file, 2 being the second, etc.) and y is the maximum beauty for that test case.

Constraints
5 ≤ m ≤ 50
2 ≤ length of s ≤ 500

My solution for this problem was fairly straight forward. Not the fastest solution I guess, but it works: get the string, count the unique alpha characters in it and add up the “beauty”

<?php
 
$content = file_get_contents("input.txt");
$content = preg_replace("/\r\n/i","\n",$content);
$rows = explode("\n",$content);
$row_count = $rows[0];
 
if (!is_numeric($row_count)){
	print("invalid input\n");
	exit();
}
 
$handle = fopen("output.txt","w+");
 
for($case=1;$case<=$row_count;$case++){
	$row = $rows[$case];
	$row = strtolower(preg_replace("/[^a-zA-Z]/i","",$row));
 
	if (!strlen($row)){
		print("Case #$case: 0\n");
		fwrite($handle,"Case #$case: 0\n");
		continue;
	}
 
	$letters = array();
	for($j=0;$j<strlen($row);$j++){
		if (!isset($letters[$row[$j]])){
			$letters[$row[$j]] = 1;
		} else {
			$letters[$row[$j]]++;
		}
	}
 
	$total_beauty = 0;
	$current_beauty = 26;
	arsort($letters);
	foreach($letters as $letter => $count){
		$total_beauty+=$count*$current_beauty;
		$current_beauty--;
	}
 
	print("Case #$case: $total_beauty\n");
	fwrite($handle,"Case #$case: $total_beauty\n");
}

Task 2: Balanced Smileys

Your friend John uses a lot of emoticons when you talk to him on Messenger. In addition to being a person who likes to express himself through emoticons, he hates unbalanced parenthesis so much that it makes him go :(

Sometimes he puts emoticons within parentheses, and you find it hard to tell if a parenthesis really is a parenthesis or part of an emoticon.

A message has balanced parentheses if it consists of one of the following:
- An empty string “”
- One or more of the following characters: ‘a’ to ‘z’, ‘ ‘ (a space) or ‘:’ (a colon)
- An open parenthesis ‘(‘, followed by a message with balanced parentheses, followed by a close parenthesis ‘)’.
- A message with balanced parentheses followed by another message with balanced parentheses.
- A smiley face “:)” or a frowny face “:(”

Write a program that determines if there is a way to interpret his message while leaving the parentheses balanced.
Input

The first line of the input contains a number T (1 ≤ T ≤ 50), the number of test cases.
The following T lines each contain a message of length s that you got from John.
Output

For each of the test cases numbered in order from 1 to T, output “Case #i: ” followed by a string stating whether or not it is possible that the message had balanced parentheses. If it is, the string should be “YES”, else it should be “NO” (all quotes for clarity only)
Constraints
1 ≤ length of s ≤ 100

I spent quite a lot of time, about 40 minutes on this one. I ended up with a recursive function which relies on a regular expression: “/(\(.*)(:\))?(:\()?(\))/U”. This regex will match the parts of the string which are in brackets even if the parts are containing a smiley. Then it is just a loop for counting the opening and closing parentheses.

<?php
 
$content = file_get_contents("input.txt");
$content = preg_replace("/\r\n/i","\n",$content);
$rows = explode("\n",$content);
$row_count = $rows[0];
 
if (!is_numeric($row_count)){
	print("invalid input\n");
	exit();
}
 
function replace_once($haystack, $needle, $replacement){
	$pos = strpos($haystack, $needle);
	if ($pos !== false){
		return substr_replace($haystack, $replacement, $pos, strlen($needle));
	} else {
		return $haystack;
	}
}
 
function is_balanced($string){
 
	preg_match_all("/(\(.*)(:\))?(:\()?(\))/U", $string, $matches);
 
	if (count($matches) && count($matches[0])){
		$remaining = $string;
		foreach($matches[0] as $key => $val){
			$balanced = true;
 
			$remaining = replace_once($remaining, $val, "");
 
			$val = substr($val, 1, strlen($val)-2);
			$balanced = is_balanced($val);
			if (!$balanced){
				return false;
			}
		}
 
		return is_balanced($remaining);
	} else {
 
		$string = str_replace(array(":)",":("),array("",""), $string);
		$open = 0;
		for($i=0;$i<strlen($string);$i++){
			if ($string[$i] == ")"){
				if ($open > 0){
					$open--;
				} else {
					return false;
				}
			}
 
			if ($string[$i] == "("){
				$open++;
			}
		}
 
		if ($open == 0){
			return true;
		} else {
			return false;
		}
	}
 
}
 
$handle = fopen("output.txt","w+");
 
for($case=1;$case<=$row_count;$case++){
	$row = $rows[$case];
 
	if (is_balanced($row)){
		print("Case #$case: YES\n");
		fwrite($handle,"Case #$case: YES\n");
	} else {
		print("Case #$case: NO\n");
		fwrite($handle,"Case #$case: NO\n");
	}
}
 
fclose($handle);

Task 3: Find the min

After sending smileys, John decided to play with arrays. Did you know that hackers enjoy playing with arrays? John has a zero-based index array, m, which contains n non-negative integers. However, only the first k values of the array are known to him, and he wants to figure out the rest.

John knows the following: for each index i, where k <= i < n, m[i] is the minimum non-negative integer which is *not* contained in the previous *k* values of m.

For example, if k = 3, n = 4 and the known values of m are [2, 3, 0], he can figure out that m[3] = 1.

John is very busy making the world more open and connected, as such, he doesn't have time to figure out the rest of the array. It is your task to help him.

Given the first k values of m, calculate the nth value of this array. (i.e. m[n - 1]).

Because the values of n and k can be very large, we use a pseudo-random number generator to calculate the first k values of m. Given positive integers a, b, c and r, the known values of m can be calculated as follows:
m[0] = a
m[i] = (b * m[i - 1] + c) % r, 0 < i < k

Input
The first line contains an integer T (T <= 20), the number of test cases.
This is followed by T test cases, consisting of 2 lines each.
The first line of each test case contains 2 space separated integers, n, k (1 <= k <= 10^5, k < n <= 10^9).
The second line of each test case contains 4 space separated integers a, b, c, r (0 <= a, b, c <= 10^9, 1 <= r <= 10^9).

Output
For each test case, output a single line containing the case number and the nth element of m.

Well, I failed this task. Not because my solution wasn’t working. It wasn’t fast enough in some cases. I considered seed (it is not my first time on the Hacker cup) and tested it with large arrays but I missed a case when my script fails. The key speed up was when I realized that the analyzed array slices are repeating. They are repeating after every Kth element, therefor:

if ($n > $k * 2){
	$n = $k + ($n % $k) -1;
}

It gave me a huge speed up, but apparently not enough. I tried to run my script with the test cases provided by Facebook’s system and it didn’t finish in the 6 minutes limit even on the high-compute Amazon EC2 instances. Epic fail. Well next time. Anyway, my solution for task #3:

<?php
 
set_time_limit(0);
ini_set("memory_limit","2048M");
 
$content = file_get_contents("input.txt");
$content = preg_replace("/\r\n/i","\n",$content);
$rows = explode("\n",$content);
$task_count = $rows[0];
 
if (!is_numeric($task_count)){
	print("invalid input\n");
	exit();
}
 
 
for($case=0; $case < $task_count; $case++){
 
	$m = array();
 
	$tmp = explode(" ",$rows[1+$case*2]);
 
	$n = $tmp[0]; // count($m);
	$k = $tmp[1]; // known length
 
	$tmp = explode(" ",$rows[2+$case*2]);
 
	$a = $tmp[0];
	$b = $tmp[1];
	$c = $tmp[2];
	$r = $tmp[3];
 
	$m[0] = $a;
 
	for ($i=1; $i < $k; $i++){
		$m[$i] = ($b * $m[$i-1] + $c) % $r;
	}
 
	// reduce n
	if ($n > $k * 2){
		$n = $k + ($n % $k) -1;
	}
 
	print($k."\t".$n."\n");
 
	for($i=$k; $i<$n; $i++){
 
		$current_slice = array_slice($m, $i-$k, $k);
 
		asort($current_slice);
		$min = -1;
		while(true){
 
			if (empty($current_slice)){
				$min = $min+1;
				break;
			}
 
			$test = array_shift($current_slice);
 
			if ($test > $min+1){
				$min = $min+1;
				break;
			} else {
				$min = $test;
			}
		}
 
		$m[$i] = $min;
	}
 
	print("Case #".($case+1).": ".$min."\n");
 
 
}
Be Sociable, Share!

Howto: Install OSX Lion under Windows 7 and VMware

So I decided to learn objective C, partly because it’s been a long time since I developed anything besides web apps and partly because I have a couple app ideas in my mind. Anyway, it turns out there is no option to code for the iPhone on Windows 7 (besides Visual Studio. Thanks, but no thanks) so I decided to install OSX Lion using VMware. I read a whole bunch of tutorials on how to do it and finally succeeded. Here is a simple step by step guide so you can try it yourself

What will you need?

  1. You need a bootable OSX Lion image. Not sure how to legally acquire it but here is a link for a torrent file
  2. VMWare Workstation. Now this is a paid software but a quick search on isohunt will help you out. I recommend getting the latest version (9.0) if you can
  3. VMWare hard drive files. You can download them from here (self-extracting exe)
  4. “Additional files”. Various tools

Ready? Let’s install!

  1. Install VMware workstation. Don’t run it just yet.
  2. From “Additional files” extract “macosx_guest_vmware_7.tar.gz” and run “windows.bat” as an Administrator. This will patch VMware workstation to enable you to run OSX
  3. Start the self-extracting “Mac OS X Lion VMware Files.exe” (point #3 in the “What will you need section”
  4. Start VMware workstation and click on “Open a Virtual Machine” and browse to the folder extracted in the previous step. Open “Mac OSX Lion/Mac OS X Lion.vmx”
  5. Click on “Edit virtual machine settings” and remove the CD / DVD drive
  6. Still in “Edit virtual machine settings” click “Add…” then “Hard Disk” then “Use an existing virtual disk and browse to the downloaded OSX Lion image (the big one)
  7. Click “Power on this virtual machine” to launch the virtual machine. If it asks you a random question (can’t remember what exactly was it) answer “I copied it”
  8. The installer should start in a couple of moments. Just follow the installation steps and you are ready to go

Couple of problems / tweaks

  1. The image by default will only work with 1024×768 resolution which can be really annoying. To solve this copy “darvin.iso” from your “Sysprobs Lion Files” to an usb drive and install it on your OSX system. After the install and the reboot you will be able to choose whatever resolution you want
  2. Sound doesn’t work. I’m still trying to figure out how to solve this
  3. I tried to install OSX on my work computer which has an AMD processor but it gave me errors. There are some tutorials around the web to solve that problem, but its time consuming so I just didn’t bother. Just google the exact error message and you will be able to solve it if you really want. The method described here works perfectly for my Intel i7 desktop and my Intel i5 laptop (I guess it should work on any Intel chipset systems)

Have fun

Be Sociable, Share!

Asus Sentelic touchpad tweaks

Currently I’m on holiday and I’m not supposed to work, but I felt fed up with partying and decided to do some coding. Usually I do my coding on my Dell desktop but at the moment it is pretty far away so I stuck with my asus ux31 zenbook. It is a really lightweight yet powerful machine, but it is not optimal for doing serious work. The main reason behind it is the touchpad being absolutely useless with Windows 7 (i know, you vim and emacs geeks are looking down on me at the moment but thats how it is: i use Windows and Eclipse and I’m proud of it). Long story short, I decided to tweak the touchpad as much as possible to make it usable. The result is far from the Macbook’s touchpad experience but it is usable. Here is what I did:

  • Removed the existing Sentelic driver and rebooted windows (windows will install a general plug-and-play touchpad driver)
  • Ran CCleaner to fix up the usual registry mess happening after playing with drivers
  • Downloaded the latest (atm 9.1.7.7) Sentelic driver from here and installed it (reboot windows afterwards)
  • In Mouse Properties > Pointer options I set the pointer speed to be 3 notches from the right
  • In Mouse Properties > Wheel I reduced the Vertical scrolling to be 1
  • In the Finger Sensing Pad options I turned off Type Detection, On pad click and every guestures except: 2F straight up and 2F straight down
  • As a last step i run the registry editor (Start > run regedit) and changed HKEY_CURRENT_USER/Software/AVC/FSP/GearIndex to be 9. I’m not sure if it makes any difference but it supposed to make the pointer movement much smoother even if the pointer speed is set to fairly fast

With these tweaks the touchpad operates in a usable manner. Hope it helps for someone

Be Sociable, Share!