Skip to content

Archive for November, 2010

26 prisoners and a light bulb logic problem in python

Nov 14 10
by mat

I was sent a interesting logic problem by samsamsam which is as follows (or very similar):

Q: How can the prisoners tell, with certainty, that all 26 of them have visited the central living room with the light bulb.

Riddle:
26 prisoners are in solitary cells, unable to see, speak or communicate in any way from those solitary cells with each other. There’s a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his own cell. Everyday, the warden picks a prisoner at random, and that prisoner goes to the central living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 26 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven’t been to the living room), all 26 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Solution

I won’t explain the solution in words as that might ruin it if you were planning on figuring it out, instead I have posted some python code that calculates the probability of number of days it will take.

# -*- coding: utf-8 -*-
from random import randint

bin=[]
binstep=50

# Loop 
for i in xrange(0,50000):

	nopris=26
	light=0
	count=0
	days=0

	# Create a set of prisoners with value 0 or 1
	# for having visited the room when light is off
	p=[]
	for i in range(0,nopris):
		p.append(0)

	# Until all prisoners have switched light on and have
	# been counted
	while count<nopris-1:
		x=randint(0,nopris-1)
		# First person to be picked is the counter
		if days==0:
			counter=x
			p[x]=1
		# Counter adds one if light is on and resets it
		elif x==counter and light==1:
			light=0
			count+=1
		# If light is off and prisoner hasn't turned light 
		# on before he does so
		elif p[x]==0 and light==0:
			p[x]=1
			light=1
		else:
			pass
		days+=1
		

	# Expand our bin if it isn't big enough
	while days>len(bin)*binstep:
		bin.append(0)
	bin[days/binstep]+=1	
	

# Just chucking data into a histogram type layout
# to speed up processing afterwards (I'm crap at
# openoffice stuff)
for i in range(0,len(bin)):
	print i*binstep+binstep/2,",",bin[i]

For 50k iterations I got the following output:

$ python prisoners.py
25 , 0
75 , 0
125 , 0
175 , 0
225 , 0
275 , 0
325 , 2
375 , 31
425 , 162
475 , 636
525 , 1659
575 , 3492
625 , 5448
675 , 7134
725 , 7755
775 , 7103
825 , 5758
875 , 4341
925 , 2884
975 , 1701
1025 , 909
1075 , 511
1125 , 255
1175 , 124
1225 , 63
1275 , 25
1325 , 4
1375 , 2
1425 , 1

Which shown as a histogram looks like:

Histogram for the 26 prisoners problem (50k iterations)

Histogram for the 26 prisoners problem (50k iterations)

Let me know how you’d improve this method or any other cool logic problems I can have a go at :)

Orange San Francisco (ZTE Blade) for £87.10 with cashback

Nov 6 10
by mat

Orange are offering a really nice large screen android phone for a great price, so I picked one up for my dad and flashed a custom rom onto it. They have dubbed the device the San Francisco, but it is otherwise known as a ZTE blade (specs on wikipedia)

How to get it for £87.10

  • +£12 Go through a cashback website like quidco and click through to the orangeshop
  • Once at the website goto orangeshop student select PAYG and enter your NUS code or just enter 000000000000000 they don’t verify it!!! for a 10% discount (this was a tip off from someone at droidcon, but I didn’t manage to catch name please let me know if it was you and you can have the credit)
  • £99 + £10 Topup Select San Fransisco in Gray or San Fransisco in White
  • -£9.90 Your 10% discount will now be applied ^_^ Choose which tariff you want, I chose dolphin as you get free internet and 300 texts when you topup £10
  • Total £87.10, win!

It’s a good phone and it’s very easy to flash a custom rom onto if you don’t like the orange one. I got the rom and followed the guide at modaco.

Review of day 2 of droidcon uk 2010

Nov 3 10
by mat

Following on from the review of the previous day at droidcon uk 2010, Here is a brief review of the second day at the conference. Apologies for the terrible photos and some fragmented text!

Again as this is quite a long post here is a mini table of contents to speed it up:

Excellence in the Android User Experience

Romain Nurik talks about creating applications with great UX and great UI, this follows on from a similar presentation he has posted up on slideshare.

Roman Nurik making android pretty

Roman Nurik making android pretty

Android reuse models

Mark Murphey discussed some of the ways in which we can reduce lots of android developers reinventing the wheel everytime we need something. There are a few methods that a developer can use for distributional:

  • Souce Code
  • As an Application
  • As a jar
  • Library
  • Combine the two above methods, and distribute a jar in a library. As we don’t live in a perfect world source code cannot always be distributed (Remember to create a licence)

Libraries can be used to solve problems for people who want free and paid versions of the app, and don’t want to maintain two versions of the code. Google have shown a google example by creating the LVL code as a library for app developers to use.

Resource name collisions can still be a problem, but this can be solved by using a prefix that is unlikely to be used by the child application. Mark shows an example of this in his color mixer widget that uses “cwac_colormixer” as a prefix. You can find lots of mark’s cool projects on his github: githubcom/commonsguy

Mark went on to discuss that we need a place to collect code to reuse and mentioned building a community website for this purpose, also saying “I can’t write a website to save my soul, I ain’t doing it!”

During the talk/questions, a great open source view was mentioned Swipe view by @jasonfry which is like view flipper but the animations between the views are not static and more like the home screen.

Make it fun

This was basically a demo of using the Unity 3D framework for creating applications that can be run on iphone/ipad/android/wii/computer. Seemed to have some cool features but I will let them do their own sales talk.

Monetize your apps in emerging markets

This was an interesting talk by a guy from movend who discussed the concept of marketing your apps to emerging markets. For a lot of people in emerging markets the phone is the only access to the internet, social networking, and gaming/entertainment device.

He had some intersting statistics on mobile phone payments. Asia Pacific accounts for $62.8 million in mobile phone payments and the rest of the world only accounts for $45.8 million. The market for mobile app revenue is estimated at $135million for 2009 and at $4 billion for 2010.

Market is extremely fragmented, android market does not exist in certain countries/handsets. Try to get your application pre-loaded onto a phone and target what specific users like. Apparently the Chinese like to play mmorpg the most. Micro-transactions are a great was to add value to a free application.

Android has a “dude” problem

Lady geek and ladygeektv

This presentation started with a great slide:

Ladygeek android penis

Ladygeek android penis


Only 5% women want an android phone whereas 50% want an iphone. She goes on to discuss why we as developers should care. Apparently women buy more gadgets than men, and between the ages of 25-39 there are more female gamers than men!

She then used this awesome droid advert as a demonstration of how android is currently marketed which contains the awesome quote of “Race horse duct taped to a scud missile, fast”

Android behind the scenes

Sony Erricson sharing some behind the scenes information about how they work on android.

They were constantly trying to remind developers that they are very open and are contributing changes upstream to the android project. They are interested in decoupling applications from android so that signature apps are built on top rather than into android. I believe they said this was the case for their sexy timescape view:

Sony Ericsson Timescape

Sony Ericsson Timescape

Sony Erricson want to be very in touch with devs and they don’t believe creating seperate communities will help anything and instead will provide support in current communities such as stackoverflow and google groups.

They briefly mentioned the Ericsson application awards 2011 which has a theme of “Connected things” and has 4 prizes of 15,000 each with phones awarded throughout different stages of the competition. They will also provide live beta testers to evaluate your application.

Other

We had a quick play on some of the cool new android tablets.

Android Tablet

Android Tablet

There were some free android usb sticks, which someone said were from orange but there was no branding on or nearby them.

Android 2gb usb stick

Android 2gb usb stick