Puzzle Solver

Last week I posted a new project to Github. It’s called Puzzle Solver. It is a very basic breadth first search solver for board puzzles.

I have a few puzzles from Israel that have the theme of placing tiles on a board in a specific way. I wanted to try and write a program to solve these types of puzzles. It is a bit more complicated than just a recursive search as tiles can be rotated.

The program only solves for the puzzle listed below, but eventually I want to get it to solve arbitrary puzzles by only requiring the pieces, the board size, and a function indicting “valid state”

Example

From www.thinkinggames.com(Source: www.thinkinggames.com)

The solution from running the program yielded 4 solutions:

Starting
Solution # 1 = 
Place [["Star","Bull","Tria"]] at position 0,0
Place [["Yell"],["Tria"],["Squig"]] at position 3,0
Place [["Squig"],["Star"],["Yell"]] at position 4,0
Place [["Squig","Yell","Bull"]] at position 0,1
Place [["Bull"],["Yell"],["Tria"]] at position 0,2
Place [["Tria","Star"]] at position 1,2
Place [["Star","Squig","Bull"]] at position 1,3
Place [["Tria"],["Bull"]] at position 4,3
Place [["Squig","Yell","Star"]] at position 1,4

 [ [ 'Star', 'Bull', 'Tria', 'Yell', 'Squig' ],
  [ 'Squig', 'Yell', 'Bull', 'Tria', 'Star' ],
  [ 'Bull', 'Tria', 'Star', 'Squig', 'Yell' ],
  [ 'Yell', 'Star', 'Squig', 'Bull', 'Tria' ],
  [ 'Tria', 'Squig', 'Yell', 'Star', 'Bull' ] ] 

Solution # 2 = 
Place [["Star","Bull","Tria"]] at position 0,0
Place [["Squig"],["Tria"],["Yell"]] at position 3,0
Place [["Yell"],["Star"],["Squig"]] at position 4,0
Place [["Squig","Yell","Bull"]] at position 0,1
Place [["Bull"],["Yell"],["Tria"]] at position 0,2
Place [["Tria","Star"]] at position 1,2
Place [["Star","Squig","Bull"]] at position 1,3
Place [["Tria"],["Bull"]] at position 4,3
Place [["Squig","Yell","Star"]] at position 1,4

 [ [ 'Star', 'Bull', 'Tria', 'Squig', 'Yell' ],
  [ 'Squig', 'Yell', 'Bull', 'Tria', 'Star' ],
  [ 'Bull', 'Tria', 'Star', 'Yell', 'Squig' ],
  [ 'Yell', 'Star', 'Squig', 'Bull', 'Tria' ],
  [ 'Tria', 'Squig', 'Yell', 'Star', 'Bull' ] ] 

Solution # 3 = 
Place [["Star"],["Bull"],["Tria"]] at position 0,0
Place [["Squig"],["Yell"],["Bull"]] at position 1,0
Place [["Bull","Yell","Tria"]] at position 2,0
Place [["Tria"],["Star"]] at position 2,1
Place [["Star"],["Squig"],["Bull"]] at position 3,1
Place [["Squig"],["Yell"],["Star"]] at position 4,1
Place [["Yell","Tria","Squig"]] at position 0,3
Place [["Squig","Star","Yell"]] at position 0,4
Place [["Tria","Bull"]] at position 3,4

 [ [ 'Star', 'Squig', 'Bull', 'Yell', 'Tria' ],
  [ 'Bull', 'Yell', 'Tria', 'Star', 'Squig' ],
  [ 'Tria', 'Bull', 'Star', 'Squig', 'Yell' ],
  [ 'Yell', 'Tria', 'Squig', 'Bull', 'Star' ],
  [ 'Squig', 'Star', 'Yell', 'Tria', 'Bull' ] ] 

Solution # 4 = 
Place [["Bull"],["Tria"]] at position 0,0
Place [["Tria"],["Yell"],["Bull"]] at position 1,0
Place [["Squig","Yell","Star"]] at position 2,0
Place [["Star","Squig","Bull"]] at position 2,1
Place [["Squig"],["Star"],["Yell"]] at position 0,2
Place [["Tria","Star"]] at position 2,2
Place [["Yell"],["Tria"],["Squig"]] at position 4,2
Place [["Squig","Yell","Bull"]] at position 1,3
Place [["Star","Bull","Tria"]] at position 1,4

 [ [ 'Bull', 'Tria', 'Squig', 'Yell', 'Star' ],
  [ 'Tria', 'Yell', 'Star', 'Squig', 'Bull' ],
  [ 'Squig', 'Bull', 'Tria', 'Star', 'Yell' ],
  [ 'Star', 'Squig', 'Yell', 'Bull', 'Tria' ],
  [ 'Yell', 'Star', 'Bull', 'Tria', 'Squig' ] ] 


------
Found 4 solutions in 1.259 seconds (595885 iterations)...

Possible Improvements

The algorithm could possibly be improved to prevent symmetric attempts from being attempted again.

The project is currently hard coded for a specific puzzle game, but without much effort it should be able to be abstracted out as an object with overridable functions to specify the board size, pieces, and a “isValid” function which returns true or false on whether the search should continue.

Optimal Fence Riddle

A long time ago I found a website with a very interesting riddle. I haven’t been able to find the website again, but I thought I’d do my best to recreate the riddle from my memory and post it here.

You are a farmer that has a square field. Your field neighbors equal square-sized fields north, east, south and west:

Farmer Fence Riddle

Here is the problem. The neighboring fields have roaming cows that love to hang out with each other. The problem is that they keep crossing over your field in order to do so.

These cows, while social, will only visit a neighboring field if they can see those cows.

As an engineer, you decide to build a fence. So you build one like so:

Farm Riddle Fence Example

This X shaped fence prevents any of the cows from one neighboring to see any of the cows from another.

Here’s the question: Can you find a solution that uses less fence?

Age of the Earth and Google Newspaper Archive

After watching Neil deGrasse Tyson hosting “The Clean Room” episode of the Cosmos reboot last Sunday, I decided to look up Clair Cameron Patterson some more on the web. I couldn’t find any videos of him (I guess he really did avoid the limelight) but there are some very interesting stuff on Google Newspaper Search (which, contrary to what many think, still is being hosted by Google).

I searched for old articles mentioning “Age of the Earth” (which was discovered in 1956 by Patterson to be about 4.55 billion years).

First thing I found was a 1925 article which mentions that radiometric dating with uranium and lead would be the most accurate way to measure the Earth’s age. Interesting that it took almost 50 years to actually find out (from the discovery of radiometric dating in 1907 to Clair Patterson’s finding in 1956).

Screen Shot 2014-04-21 at 4.19.42 PM
From the newspaper “The Age” May 9th, 1925

Going back prior to the discovery of radiometric dating, I found multiple articles with widely different predictions.  Check out this 1895 article from “The Free Lance” newspaper discussing Geologist James Geikie‘s view on Lord Kevlin‘s Earth age estimations.

And then in 1904, just three years before the first paper on Radiometric dating was published, this article in the Pittsburgh Press highlighted Ernest Rutherford‘s belief that the “100,000,000” year old earth predictions were too short due to studies of the “dissolution of radium”

Pittsburgh Press, July 9th 1904
Pittsburgh Press, July 9th 1904

Going back to just before Clair Patterson’s discovery, I found a 1953 article with a little bit of Cold War drama.

The Victoria Advocate - Apr 10, 1953
The Victoria Advocate – Apr 10, 1953

It’s a real shame that Google News Archive publicly closed in 2011. Thankfully the site still is still hosting articles, but the nice timeline features and user interface have gone away. Google News Archive used to allow you to see a histogram of mentions of specific keywords in historical newspapers.

Old newspapers give a unique perspective in history. They offer a compelling way to re-live and re-tell stories and discoveries of the past. There are millions of articles waiting to be digitized and searchable.

I hope that we’ll see Google (or some other company) provide enhanced access to that information.

How to Convince Someone to Be Your Technical Cofounder

Throughout the past years, I have been solicited by many friends, friends of friends, and complete strangers to be a technical cofounder/developer on a new project.

For almost all of the projects and startups that have been presented to me, I have declined.

Here are the main reasons why:

Almost always, the offer from the startup goes something like, “You create us an app for free, and we will give you X% of our company/profits in return.”

I think the founders of these startups underestimate the amount of the work it takes to build the “app” as well as valuing the X% equity.

The X value could be 100 and still developers would decline to work for free. Startups need to evaluate the way they propose working relationships by providing a clear explanation of their business and why it is worth the risk of a developer.

Here are some questions that every team needs answered and communicated to potential technical cofounders.

1) What does the current status of my startup bring to the table?

Could this developer duplicate this startup themselves? Does the ideas and execution of the business rely on specific expertise of the existing team members? In other words, what makes your current team so special and unique? I can’t stress enough how often the answers to these questions are not offered.

2) What is the problem my business is trying to answer?

This question is almost always overlooked or not communicated effectively. How do you know if this is a real problem? How much does this problem cost an average customer? Who/what says there is a problem, and why does their opinion have any credibility?

Who says that your business has a solution and does the person making the claim hold any credibily?

3) How close are you to closing business with your first customer?

If the answer to this question is more than 3 months, it will be incredibly difficult to convince a technical person to build something for free. You have to remember that decent developers have a very high opportunity cost. They could be working on any number of paying projects/jobs. Every hour they spend working on your project is costing them their hourly rate. It doesn’t mean that your idea isn’t good, it just might not be good enough to be worth the risk.

4) Why can’t I pay this developer?

You need to have a legitimate reason why you can’t pay a developer any amount for their time. Remember, it is very likely that your time is NOT equal to that of a developers. Just because you are working for free doesn’t mean that your opportunity cost is equal to someone else working for free. Could you raise money and pay the developer some discounted rate plus equity? Developers will often pay more attention to combo offers of money and equity as it lowers risk yet.

Startups should approach potential technical confounders the same way they do investors. While investors give you
dollars, developers give you
dollars in the currency of time.

iOS is the Worst Platform for Development

Releasing an application on the App Store is ridiculously inconvenient.

Reason 1: Review Time

The Apple Review period is the greatest and dumbest obstruction facing App Store development. There is no reason for it. The system of human review is inherently inconsistent and unfair. There exists some dry bullshit about “app quality” – a fundamentally flawed approach from the perspective of App discovery. Users don’t discover bad quality apps. If they do, they don’t keep them. It’s a simple system and it works. Google Play works like this.

Why does Apple really have a review board? My theory is a theory for (partly) why Steve Jobs didn’t want Flash on iOS – also a similar reason of why Apple became so loved and Microsoft so hated: Public ignorance.

Early versions of Windows involved very little security measures for executable applications in comparison to today. Who did people blame when their application crashed? Would they say, “Oh no! Sim City just froze! I wish the developers of Sim City would fix these bugs!”

No, people never used to say that. They would say, “Oh no! Sim City just froze! Windows sucks!”

My theory is that Steve Jobs looked at Flash the same way. If someone ended up visiting a buggy Flash website, they would blame the IPhone. The public a decade ago mostly didn’t distinguish between software and operating systems. Today the public is much more aware and educated about this difference. If an App is slow, people are less likely to complain about  their smartphone or mobile OS and more likely to complain to the App developer.

Only a theory, but I think it extends to the App Store review process. Steve Jobs and Apple were afraid that if there were buggy/poor apps in the App Store, people would associate bugs and poor quality with Apple – something very counter to their brand and message.

But with changing times, Apple hasn’t adapted. Guess how long it took me to get my Android app published and available on the Google Play Market? I simply upload the IPA and hit publish. I absolutely love developing for Android because it’s almost as easy as it possibly can be.

Apple’s review process is bloated with inefficiencies. The smallest changes often times involve a brand new week long review process.

Fairness? LOL. How is it fair that one person (reviewer) has complete power over your app publishing. Frustration is a nice word for the feeling one gets seeing their app rejected for a reason that was apparently ignored for another app.

According to Apple’s Responding to an App Rejection pop-up window, “Note that while other currently available apps may appear to be non-compliant, citing these will not be considered a valid reason for overturning a rejection.”

That’s swell of you Apple; looks like so many people reported these inconsistencies that you had to put a response.

Here’s the real problem with this pretentious system. Apple is saying their individual reviewer knows better than the public about which apps are “quality” and which apps aren’t.

The ironic truth of the App Store review process is that it actually creates an ecosystem of bad quality apps. Find a critical bug in your app? You can’t just replace the app – you have to go through the entire review process again! What if you have a bug that deletes all users data? What if your server that your app connects to becomes compromised? You still have to wait a week to get that update to your users! Absurd! In a week you can lose your users due to a critical bug.

How does Google approach this problem? There isn’t a problem. On Google Play you can simply replace the app with a new version from their developer console and within hours your users get the new update.

Reason 2: Application Loader

There are multiple tools out there for developers to export IPAs (Phone Gap, Unity, Adobe Air, etc). However, it is impossible to submit your App to the Apple Store unless you use the Application Loader tool that is in XCode. Have Windows? Use Linux? Looks like you’re going to have to open your wallet some more to buy a Mac computer or virtual machine to run Mac OS so you can download XCode and install this stupid Application Loader.

Here’s an obvious question… Why doesn’t Apple allow users to simply use a website upload form to upload their IPA? Is it to sell more OSX licenses?

Can you imagine if Google required users to buy a Chromebook in order to upload Apps using some “application loader” only available on Chrome OS?

Let me also point out the ineptitude of the Application Loader software itself. The Application Loader fails to checks for many issues (missing screenshots etc). For example, I recently uploaded an IPA and received a “green check mark” from the Application Loader indicating the IPA was submitted for review successfully. An hour later I happened to check my email only to see that the IPA was “automatically rejected” because it was missing a screenshot for IPhone 5 size devices… Why didn’t the Application Loader detect this issue? Even more importantly, why didn’t ITunes Connect allow me to get to a “Ready for Upload” state in the first place if I didn’t upload that screenshot?

“So what’s the big deal? Just reupload and resubmit”

Well considering that just building a “signed” IPA can take 20 minutes and submitting an IPA through the Application Loader can take 20 minutes, it is quite annoying to have to go through all of that multiple times throughout the day.

The thing I hate most in iOS development is the time wasted on bullshit. Spending an entire freaking day just trying to get my app submitted then a week to get it on the app store is ridiculous.

Developers Can’t Make Movie Apps Anymore

A few days ago I brainstormed an app idea to help users find movies they want to watch on Redbox and Netflix. A small app, nothing grandiose or too ambitious, but a simple app that would do a job.

In order for me to create these apps, I need to be able to pull (public) information from these services. Redbox inventory differs from location to location, and Netflix’s inventory changes as their movie rights expire and new titles are added.

I’m astonished at the lack of developer support from Netflix and Redbox. As of about a month ago, Netflix shut down its API service to developers.

This change means that developers can’t create an app that helps people find Netflix movies to watch. Even if you want to grab publicly digestible information like the list of movies on Netflix Instant.

Redbox has an API, but you have to apply… and wait… for them to approve of your “application” – basically you have to tell them what you’re building, your business model, etc. Considering I could probably count with one hand the number of Redbox apps out there, I am guessing that Redbox doesn’t quite see eye-to-eye with most developers’ API applications.

Hulu doesn’t even offer an official API and developers have to resort to reverse engineered libraries.  Amazon Instant does have an API, but it is stupidly wrapped under the overly complex Amazon’s Product Advertising API umbrella.

This is sad.

There is a problem in movie discovery, many people struggle to find movies they want to watch, and developers have their hands tied behind their back trying to fix this problem.

“You uploaded an APK with Invalid or Missing Signing Information for Some of Its files” Google Play, Adobe Air Error

Getting

“You uploaded an APK with invalid or missing signing information for some of its files. You need to create a valid signed APK”

while trying to publish your Adobe Air Android app to Google Play?

It’s due to a bug in Air 3.6 (and 3.7 for me). For future reference, you can find out what the error in the signing of an app are by using a tool called jarsigner. This exists in your JDK.

On windows it’s in your JDK path/bin folder. Just open up command prompt/terminal and run:

jarsigner -verify "[PATH TO YOUR APK]"

Here is the error I was getting

jarsigner: java.lang.SecurityException: SHA1 digest error for res/drawable-xhdpi
/icon.png

Here’s how I fixed it. I opened up the APK in 7zip (remember, APK is collection of files zipped together. You can actually open it up) and navigated to that res/rawable-xhdpi folder. What do you know… looks like there are TWO icon.pngs. It’s a bug in Adobe’s latest Air which packages the APK incorrectly by creating duplicated icon.png files. Probably will be fixed in later versions.

If you want to avoid upgrading your Air SDK, all you need to do is delete one of those two icon.png files from the zip file.

Command line way to do it (will delete both):
zip -d [YOUR APK.APK] res/drawable-xhdpi/icon.png

Now, if you tried uploading this APK you might get an error about the APK not being zipaligned. Due to us deleting files the APK is no longer zip aligned. Which means we have to re align the file.

Navigate to your Android Developer Tools (ADT) folder. Under the SDK’s /tools you’ll see that zipalign. You’ll need to do

zipalign -f -v -c 4 “Your APK” “Your APK 2”

Reupload the new APK (remember if you don’t put an absolute path it’ll be in the same directory as where zipalign is) and it should be accepted.

Oh the joys of Adobe Air for mobile development.

Simple Circle Packing

I am working on a new game which is was in need of an algorithm to pack characters as close together without touching. Here is a demo of my algorithm:

Get Adobe Flash player

And the code (uses TweenLite)

import flash.display.MovieClip;
import flash.geom.Point;
import flash.events.Event;
import flash.utils.Timer;
import flash.events.TimerEvent;
import com.greensock.TweenLite;

var mcs:Array = [];
var radius:Number = 5;
var c:Point = new Point(stage.stageWidth / 2,stage.stageHeight / 2);
var animationTime:Number = .5;

function addMC(e:Event= null)
{
	var mc:MovieClip = new MovieClip();
	mc.cacheAsBitmap=true;
	mc.graphics.lineStyle(1);
	mc.graphics.beginFill(Math.random()*0xFFFFFF);
	mc.graphics.drawCircle(0,0,radius);
	mc.graphics.endFill();
	mc.x = c.x;
	mc.y = c.y;
	addChild(mc);
	mcs.push(mc);
}
var t:Timer = new Timer(animationTime*1000,1500);
t.addEventListener(TimerEvent.TIMER,function(e:Event):void{
   addMC();
   arrange();
   });
addMC();
arrange();
t.start()
function arrange()
{
	var curDistanceAwayFromCenter:Number = radius * 2;
	var numMoved = 0;
	var n:Number = mcs.length;
	// Place the very first circle in the center, as the algorithm won't work for n==1
	mcs[0].x = c.x;
	mcs[0].y = c.y;
	numMoved++;
	while (numMoved < n)
	{
		/*R*SIN(180/n) = r
		SIN(180/n) = r/R;
		ARCSIN(r/R) = 180/n
		n = 180/ARCSIN(r/R)
		*/
		var numberToFit:int = Math.PI/Math.asin(radius/curDistanceAwayFromCenter);
		if (numberToFit > mcs.length-numMoved)
		{
			numberToFit = mcs.length - numMoved;
		}
		for (var j:int = 0; j < numberToFit; j++)
		{
			var cur:MovieClip = mcs[numMoved];
			// ang to center
			var ang:Number = Math.PI * 2 * j / numberToFit;
			var np:Point = new Point();
			np.x = c.x + Math.cos(ang) * curDistanceAwayFromCenter;
			np.y = c.y + Math.sin(ang) * curDistanceAwayFromCenter;
			// this if improves performance a tiny bit, would probably be way more performant if we detected if this was in the "last" circle, if not then we don't need to loop through it anymore
			if (np.x !== cur.x || np.y !== cur.y)
				TweenLite.to(cur,animationTime,{x:np.x,y:np.y})
			numMoved++;
		}
		curDistanceAwayFromCenter +=  radius * 2;

	}
}

Note that this doesn’t pack circles optimally in a space. That is a much harder problem. I was looking for a solution that would “cluster” the characters.

Annoying to Very Annoying Newsletter Practices

I really… really hate newsletters from websites I don’t want them from. What I hate even more is the unsubscribing process that websites employ. It’s like cancelling a gym membership.

Annoying Newsletter Practices

 

My flow of frustration in the unsubscribing process. Some websites employ a Hotel California approach in newsletters – you can check out any time you’d like but you can never leave.

Is it unreasonable for me to demand that I shouldn’t have to log in to a website to unsubscribe from their email list?