Determining If A Boolean Expression Can Be False
My first hunch was that determining if a boolean expression can be false was NP complete. After trying to prove it, I came up for a proof that it’s actually in P:
1) We have any boolean expression S
2) Using a well documented algorithm, we convert it to Conjunctive Normal Form
3) Formula becomes (x1,1 v x1,2 v … v x1,n) Λ (x2,1 v x2,2 v … v x2,n) Λ … Λ (xn,1 v xn,2 v … v xn,n)
4) Since we are trying to solve a setting of x1,1 to xn,n that results in false, that is the same thing as solving for a setting that results in true in the inverted expression
5) Now we have ¬((x1,1 v x1,2 v … v x1,n) Λ (x2,1 v x2,2 v … v x2,n) Λ … Λ (xn,1 v xn,2 v … v xn,n))
6) Applying DeMorgan’s ¬(x1,1 v x1,2 v … v x1,n) v ¬ (x2,1 v x2,2 v … v x2,n) v … v ¬(xn,1 v xn,2 v … v xn,n))
7) Applying DeMorgan’s again (¬x1,1 Λ ¬x1,2 Λ … Λ ¬x1,n) v (¬x2,1 Λ ¬x2,2 Λ … Λ ¬x2,n) v … v (¬xn,1 Λ ¬xn,2 Λ … Λ ¬xn,n))
8) Now we can determine a setting the results in true, by using the ANDed group that doesn’t contain a contradiction. If all the ANDed groups, contain contradictions, then there is no setting that results in true.
9) This setting from step 8 that results in true for ¬S will result in false for S
This came up at work because we were trying to determine if a boolean expression could become false. Knowing this would allow us to make a decision on how to handle the query.
If I have made an error, let me know! If you’re confused about one of the steps, feel free to ask.
Cheers,
Joseph
Pitfalls of Integer.hashCode() and Long.hashCode() With Partitioning
Problem
So we want to partition our data into nice even chunks. If you use Integer.hashCode(), Long.hashCode(), or modding by the number of your partitions then the size of each partition will depend on the distribution of your data and the number of partitions. Here’s a quick example that I wrote up to demonstrate.
Here we have the partition size as 8 and all the numbers are even. I place each number into a bucket by taking the modulus of it. Here are the results:
import java.util.Random;
public class HashCodeIssue {
private static Random random;
public static void main(String [] args) {
int partitions = Integer.parseInt( args[0] );
long seed = Integer.parseInt( args[1] );
random = new Random(seed);
int [] buckets = new int[partitions];
for(int c = 0; c < 100000; c++) {
buckets[hash(getNextNumber()) % partitions]++;
}
for(int c = 0; c< buckets.length; c++) {
System.out.println("size of bucket " + c + ": " + buckets[c]);
}
}
/**
* Using a distribution of numbers divided evenly over
* even numbers.
*/
private static Integer getNextNumber() {
return new Integer(random.nextInt(Integer.MAX_VALUE/2) * 2);
}
/**
* Returning the default hashCode() implementation.
*/
public static int hash(Integer i) {
return i.hashCode();
}
}
jmate@jmate-Satellite-C650D:~/Desktop/hashcode-issue$ java HashCodeIssue 8 890453985
size of bucket 0: 24781
size of bucket 1: 0
size of bucket 2: 24959
size of bucket 3: 0
size of bucket 4: 25163
size of bucket 5: 0
size of bucket 6: 25097
size of bucket 7: 0
jmate@jmate-Satellite-C650D:~/Desktop/hashcode-issue$ java HashCodeIssue 8 234985345
size of bucket 0: 25250
size of bucket 1: 0
size of bucket 2: 24735
size of bucket 3: 0
size of bucket 4: 24866
size of bucket 5: 0
size of bucket 6: 25149
size of bucket 7: 0
Root Cause
Lets take a look at the source code of Integer.hashCode() to find out why the numbers are not being evenly distributed, despite using a hash.
/**
* Returns a hash code for this {@code Integer}.
*
* @return a hash code value for this object, equal to the
* primitive {@code int} value represented by this
* {@code Integer} object.
*/
public int hashCode() {
return value;
}
/**
* Returns a hash code for this {@code Long}. The result is
* the exclusive OR of the two halves of the primitive
* {@code long} value held by this {@code Long}
* object. That is, the hashcode is the value of the expression:
*
* <blockquote>
* {@code (int)(this.longValue()^(this.longValue()>>>32))}
* </blockquote>
*
* @return a hash code value for this object.
*/
public int hashCode() {
return (int)(value ^ (value >>> 32));
}
These hash codes are implemented for speed, as a result they don’t do a good job of jumbling up the numbers. Unfortunately, for developers who want partitions of uniform sizes, this is not a good thing. The issue is that all the values share a common divisor with the the number of partitions (4*2 and y=x*2). As a result, all the values end up in the same buckets.
Solution
There are a couple of solutions to this problem.
1. Adjust The Number Of Partitions
This seems unintuitive at first, but REDUCING the number of partitions to 7 will flatten out the sizes of our partitions because there are a lot less even numbers that share a common divisor with the prime number seven.
jmate@jmate-Satellite-C650D:~/Desktop/hashcode-issue$ java HashCodeIssue 7 890453985 size of bucket 0: 14153 size of bucket 1: 14335 size of bucket 2: 14377 size of bucket 3: 14265 size of bucket 4: 14364 size of bucket 5: 14179 size of bucket 6: 14327 jmate@jmate-Satellite-C650D:~/Desktop/hashcode-issue$ java HashCodeIssue 7 234985345 size of bucket 0: 14193 size of bucket 1: 14256 size of bucket 2: 14374 size of bucket 3: 14362 size of bucket 4: 14267 size of bucket 5: 14321 size of bucket 6: 14227
2. Use A Better Hash
Now a lot of times you have no idea what distribution of numbers you have but you still want to be able to distribution the numbers uniformly over your partitions. Or, you need a particular number of partitions that will have a common divisor with a lot of numbers coming in. A safe way to do this is to use a hash function that jumble up the numbers better. In the code above, instead of using the default hash implementation, I use the md5 hash function.
/**
* Hash function that uses MD5.
*/
private static int hash(Integer i, int partitions)
throws java.security.NoSuchAlgorithmException {
MessageDigest m = MessageDigest.getInstance("MD5");
m.reset();
m.update(toBytes(i));
byte[] digest = m.digest();
BigInteger bigInt = new BigInteger(1,digest);
return bigInt.mod(new BigInteger(1,toBytes(partitions))).abs().intValue();
}
private static byte[] toBytes(Integer ii) {
int i = ii.intValue();
byte[] result = new byte[4];
result[0] = (byte) (i >> 24);
result[1] = (byte) (i >> 16);
result[2] = (byte) (i >> 8);
result[3] = (byte) (i /*>> 0*/);
return result;
}
jmate@jmate-Satellite-C650D:~/Desktop/hashcode-issue$ java HashCodeIssue 8 890453985
size of bucket 0: 12629
size of bucket 1: 12510
size of bucket 2: 12550
size of bucket 3: 12470
size of bucket 4: 12689
size of bucket 5: 12339
size of bucket 6: 12311
size of bucket 7: 12502
jmate@jmate-Satellite-C650D:~/Desktop/hashcode-issue$ java HashCodeIssue 8 234985345
size of bucket 0: 12472
size of bucket 1: 12533
size of bucket 2: 12632
size of bucket 3: 12634
size of bucket 4: 12489
size of bucket 5: 12352
size of bucket 6: 12616
size of bucket 7: 12272
Conclusion
If your performance depends on the size of your partitions, you should take special care when using Integer.hashCode() or Long.hashCode(). By carefully selecting the number of partitions, you can avoid the problem. If you uncertain about the distribution of numbers you have or you cannot change the number of partitions, you should use a hash function that does a better job of jumbling up the numbers.
Now I realize this example was really contrived because the numbers being partitioned were even. I chose it because it’s really simple to understand and illustrate that if you don’t use a good hash function or have the correct number of partitions, this problem is going bite you when your numbers have a special distribution. The last time I saw this problem in the real world is when the numbers we were partitioning on usually had a particular end like XXXXX7831. If you have encountered this problem, post a comment! I am interesting in hearing about it.
High Fructose Corn Syrup vs. Refined Cane Sugar Coca Cola
Motivation
Recently my roommate and I got into an argument over being able to taste the difference between high fructose and cane sugar Cola. I hypothesized that you could taste the difference between the two because of the level of fructose. My roommate disagreed and claimed that fructose would taste similar to the cane sugar and that we would not be able to tell the difference. We decided to settle the dispute by performing an experiment.
Fructose vs Sucrose Experiment
Experiment
The items used in the experiment are High Fructose Coca-Cola, Cane Sugar Mexican Coca-Cola, and tiny slips of paper to put under the cups to secretly indicate what the cup contained. Person A would fill two cups for each type of cola and mark a piece of paper to indicate what was the contents of the cup and hide it underneath the cup. After finishing person A would leave the room and person B would enter the room. Person B would then shuffle the cups without looking at the pieces of paper and call in person A when he finished. Finally, person A had to drinking each cup and write down what was inside each. After writing down all the guesses we compared the guesses to the actual contents. Before repeating the experiment we washed out all cups with water.
Results
First two sets of trials, both my roommate and I were guessing at about chance. However, on the third trial I noticed that one cola was more bubbly than the other. After identifying that it was the high fructose one, I was able to get the answer 100% of the time. My roommate, also following the observation was able to identify the contents 100% of the time. As a result, we called off the experiment because we were able to identify the cola without attributing it to the presence of high fructose corn syrup. We saved the remaining precious cola for consumption during dinner.
Next Steps
Next experiment we will try to use just pure high fructose water and cane sugar water so that we can control the level of bubbliness. Secondly, we need to cover the cups, or have person A and B blind folded, as it might be possible to identify the contents based on the colour of the liquid. Third, instead of doing the two cups for each type, to make the experiment simpler and more rigorous, we should just fill two cups with three cases: high fructose – high fructose, cane sugar – cane sugar, and high fructose – cane sugar. With the two cups for each type, by guessing the first three cups you knew what the last cup was rendering the last guess giving us no additional information.
Additional Reading
The consumerist has an article by Chris Morran about the difference in taste Coca Cola: We Don’t Need To Make A Cane Sugar Version Because You Already Have Mexican Coke. They interviewed Greg Galvez, vice president and general manager of Importation and Commercialization, Coca-Cola North America. He says, “our research shows that there is no perceptible taste difference between the products. Whether sweetened with high fructose corn syrup or sugar, a Coke is a Coke and both are ‘the real thing.” His wording is slightly ambiguous. Is he implying that people cannot taste the difference between the Mexican Coca-cola and the regular Coca-cola or is he saying that if we control all other ingredients then we cannot taste the difference between HFCS and cane sugar?
The Huffington Post has already performed this experiment documented in the article Coca-Cola Taste Test: High Fructose Corn Syrup vs. Sugar. They concluded that 85% of participants could tell the difference and that 80% preferred the taste of the Mexican Cola. None of the articles I found tried to control for the differences in the non sugar ingredients.
Unintuitive Scoping and Javascript Closures
I had this problem at work, and have simplified it and removed all context related to the project so this article can be easily consumed. The problem arises when you try to create a closure onto a local variable initialized in a for loop.
I will begin with an example that matches my scoping intuition, which does not use a closure:
function setupArray() {
var array = new Array();
var i=0;
for (i=0;i<=4;i++) {
var tmp;
tmp = i + 1;
array[i] = tmp;
}
return array;
}
function outputArray() {
var array = setupArray();
for (i=0;i<=4;i++) {
document.write(array[i] + "<br/>");
}
}
outputArray();
With this example, we get the output that matches our intuition:
1 2 3 4 5
Now when we modify the code to use a closure instead and we run into problems.
function setupArray() {
var array = new Array();
var i=0;
for (i=0;i<=4;i++) {
var tmp;
tmp = i + 1;
array[i] = function() {
return tmp;
}
}
return array;
}
function outputArray() {
var array = setupArray();
for (i=0;i<=5;i++) {
document.write(array[i]() + "<br/>");
}
}
outputArray();
Here is the output that I was not expecting.
5 5 5 5 5
All the anonymous functions bind to the same variable reference. It is not creating a new variable for each iteration of the loop. My solution was to just place the contents of the loop into a function.
function setupArrayEntry(i) {
var tmp;
tmp = i + 1;
return function() {
return tmp;
}
}
function setupArray() {
var array = new Array();
var i=0;
for (i=0;i<=4;i++) {
array[i] = setupArrayEntry(i);
}
return array;
}
This fixes the problem.
1 2 3 4 5
After posting this I did some additional research and discovered that this seems to be a common problem that developers encounter. For example, this post extremely valuable in understanding what is going on. The author also provides a similar solution. Check it out!
Android Appendable List – Github
Hey everyone,
Due to some people having issues getting the code to run, I have posted the complete example code on github. Just download the code and open it up in eclipse.
https://github.com/josephmate/AndroidAppendableList
If you don’t know how to use git, you can download a zip file of the sourcecode above, or run this command:
git clone git://github.com/josephmate/AndroidAppendableList.git
Cheers,
Joseph
Creating a Continuously Appendable List – Result
Result ( The left is mine. ):
Big Picture of What’s Going On:
I have a TableLayout that I add rows to when the “+” button is clicked. Each row has a “-” button that knows which table and row it belongs to. That way it has enough information to remove itself from the table.
Code:
public class AppendToAList extends Activity {
TableLayout list;
int rowsSoFar = 0;
@Override
public void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.main);
Button addButton = (Button) findViewById( R.id.add );
// Every time the "+" button is clicked,
// add a new row to the table.
addButton.setOnClickListener( new OnClickListener() {
public void onClick(View view) { addButton(); }
});
list = (TableLayout) findViewById( R.id.list );
// Start with one row.
addButton();
}
/***
* Gets all the information necessary to delete itself from the constructor.
* Deletes itself when the button is pressed.
*/
private static class RowRemover implements OnClickListener {
private TableLayout list;
private TableRow rowToBeRemoved;
/***
* @param list The list that the button belongs to
* @param row The row that the button belongs to
*/
public RowRemover( TableLayout list, TableRow row ) {
this.list = list;
this.rowToBeRemoved = row;
}
public void onClick( View view ) {
list.removeView( rowToBeRemoved );
}
}
public void addButton() {
TableRow newRow = new TableRow( list.getContext() );
Button actionButton = new Button( newRow.getContext() );
actionButton.setText( "Action: " + ++rowsSoFar );
Button removeSelfButton = new Button( newRow.getContext() );
removeSelfButton.setText( "-" );
// pass on all the information necessary for deletion
removeSelfButton.setOnClickListener( new RowRemover( list, newRow ));
newRow.addView( actionButton );
newRow.addView( removeSelfButton );
list.addView( newRow );
}
}
Layout:
<?xml version="1.0" encoding="utf-8"?>
<ScrollView xmlns:android="http://schemas.android.com/apk/res/android"
android:layout_width="fill_parent"
android:layout_height="fill_parent" >
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:orientation="vertical"
android:layout_width="fill_parent"
android:layout_height="fill_parent" >
<TableLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:orientation="vertical"
android:layout_width="fill_parent"
android:layout_height="fill_parent"
android:stretchColumns="0" >
<TableRow
android:layout_width="fill_parent" >
<TextView
android:text="Heading" />
<Button
android:id="@+id/add"
android:text="+" />
</TableRow>
</TableLayout>
<TableLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:id="@+id/list"
android:orientation="vertical"
android:layout_width="fill_parent"
android:layout_height="fill_parent"
android:stretchColumns="0" />
</LinearLayout>
</ScrollView>
I’m off to apply this to my android application!
Cheers,
Joseph
Creating a Continuously Appendable List – Tinkering
My goal is to create a list where the user can continuously append buttons. This is similar to the functionality we see when editing a contact on the android.
First I started tinkering with a LinearLayout and dynamically added some buttons to it.
Here’s the code I came up with:
public class AppendToAList extends Activity {
LinearLayout list;
/** Called when the activity is first created. */
@Override
public void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.main);
list = (LinearLayout) findViewById( R.id.list );
Button b1 = new Button( list.getContext() );
b1.setText( "This is the first textbox" );
Button b2 = new Button( list.getContext() );
b2.setText( "This is the second textbox" );
list.addView(b1);
list.addView(b2);
}
}
And this is the layout:
<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:id="@+id/list"
android:orientation="vertical"
android:layout_width="fill_parent"
android:layout_height="fill_parent"
>
</LinearLayout>
The result looked like this:
Sweet, it worked. Now I am going to add an OnclickListener to one of the buttons to add more buttons:
public class AppendToAList extends Activity {
LinearLayout list;
/** Called when the activity is first created. */
@Override
public void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.main);
list = (LinearLayout) findViewById( R.id.list );
Button addButtons = new Button( list.getContext() );
addButtons.setText( "Add a button." );
addButtons.setOnClickListener( new OnClickListener() {
int buttonsSoFar = 0;
public void onClick(View arg0) {
Button newButton = new Button( list.getContext() );
newButton.setText( "Button: " + ++buttonsSoFar );
list.addView( newButton );
}
});
list.addView(addButtons);
}
}
The result:
There’s a a slight problem. You cannot see the new buttons if you try to add more than eight. Here’s what is looks like when I added 12 buttons:
However, we can just place the LinearLayout inside a ScrollView, to make it scrollable:
<?xml version="1.0" encoding="utf-8"?>
<ScrollView xmlns:android="http://schemas.android.com/apk/res/android"
android:layout_width="fill_parent"
android:layout_height="fill_parent"
>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:id="@+id/list"
android:orientation="vertical"
android:layout_width="fill_parent"
android:layout_height="fill_parent"
>
</LinearLayout>
</ScrollView>
The result:
Now I believe that I have all the tools necessary to mimic the google contact’s continuously appendable list.
Cryptic Stacktrace from Android
I was building a new Activity for my Android application and I came across this error as I was running it:
java.lang.RuntimeException: Unable to start activity ComponentInfo{com.tfc/com.tfc.ui.LearningScreen}: java.lang.RuntimeException: Your content must have a ListView whose id attribute is 'android.R.id.list'
at android.app.ActivityThread.performLaunchActivity(ActivityThread.java:2401)
at android.app.ActivityThread.handleLaunchActivity(ActivityThread.java:2417)
at android.app.ActivityThread.access$2100(ActivityThread.java:116)
at android.app.ActivityThread$H.handleMessage(ActivityThread.java:1794)
at android.os.Handler.dispatchMessage(Handler.java:99)
at android.os.Looper.loop(Looper.java:123)
at android.app.ActivityThread.main(ActivityThread.java:4203)
at java.lang.reflect.Method.invokeNative(Native Method)
at java.lang.reflect.Method.invoke(Method.java:521)
at com.android.internal.os.ZygoteInit$MethodAndArgsCaller.run(ZygoteInit.java:791)
at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:549)
at dalvik.system.NativeStart.main(Native Method)
Caused by: java.lang.RuntimeException: Your content must have a ListView whose id attribute is 'android.R.id.list'
at android.app.ListActivity.onContentChanged(ListActivity.java:236)
at com.android.internal.policy.impl.PhoneWindow.setContentView(PhoneWindow.java:316)
at android.app.Activity.setContentView(Activity.java:1620)
at com.tfc.ui.LearningScreen.onCreate(LearningScreen.java:29)
at android.app.Instrumentation.callActivityOnCreate(Instrumentation.java:1123)
at android.app.ActivityThread.performLaunchActivity(ActivityThread.java:2364)
... 11 more
However, there was nothing wrong with my layout XML:
<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:orientation="vertical"
android:layout_width="fill_parent"
android:layout_height="fill_parent"
>
<TextView
android:layout_width="fill_parent"
android:layout_height="wrap_content"
android:layout_weight="1.0"
/>
<Button
android:layout_width="fill_parent"
android:layout_height="wrap_content"
android:text="Flip"
android:id="@+id/btnFlip"
/>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:orientation="horizontal"
android:layout_width="fill_parent"
android:layout_height="wrap_content"
>
<Button
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:layout_weight="0.5"
android:text="Right"
android:id="@+id/btnRight"
/>
<Button
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:layout_weight="0.5"
android:text="Wrong"
android:id="@+id/btnWrong"
/>
</LinearLayout>
</LinearLayout>
The problem was I accidentally had my Activity extend from ListActivity instead of Activity:
public class LearningScreen extends ListActivity {
@Override public void onCreate(Bundle icicle) {
super.onCreate(icicle);
setContentView(R.layout.learning_screen);
}
}
Here is a link to a problem with the exact same symptom, but turned out to be a completely different cause:
“Your content must have a listview whose id attribute is ‘android.R.id.list’ “
http://groups.google.com/group/android-developers/browse_thread/thread/d4d1d09dea087a71
Hope this helps you if you’re stuck with a similar issue.
Cheers,
Joseph
Javascript to Redirect a Drop Down List (select)
You can redirect using an html select without having to place it in a form, or have the user press a button. The user only needs to change the value.
Check out the following code that you can copy and paste into an html file and take for a test drive:
<html> <head> <title>Drop Down List Redirect</title> </head> <body> <select onchange="top.location.href = 'http://www.google.com/search?q=' + this.options[ this.selectedIndex ].value" > <option value="">None</option> <option value="cute+dogs">Cute Dogs</option> <option value="lasers+beams">Laser Beams</option> <option value="kitty+cat">Kitty Cat</option> </select> </body> </html>
Breaking down the javascript code into more understandable chunks gives:
// 'this' points to the select object after change the item in the drop down list. var drop_down = this; // drop_down.selectedIndex contains the position of the item that was selected from the drop down var selected_index = drop_down.selectedIndex; // drop_down.options contains all of html option elements inside the html select // we need to go to .value to get the 'value="something"' written in the HTML var selected_value = drop_down.options[ selected_index ].value; // changing top.location.href redirects ( unless you only append #blah ) top.location.href = 'http://www.google.com/search?q=' + selected_value
I hope you guys find this helpful!
Cheers,
Joseph
Setting URL using Javascript
Severin just pointed out a much easier way to update the URL using javascript:
<script language="javascript" type="text/javascript"> window.location.href = "/main/some_controller/some_action#some_anchor"; </script>
Thanks Severin!
I have extended this code into an example you can copy and paste into an html file and play around with:
<html>
<head><title>URL Updating</title></head>
<body>
<input type="button"
name="cool"
value="cool"
onclick="window.location.href = window.location.href + '#value=param';" />
</body>
</html>
With Markus, this leaves lots of places for us to place the code. For a link_to_remote, we can place set the window.location.href in the :before or :complete variables. Example:
markus/app/views/ajax_paginate/_initial_paginate_links_alpha.html.erb
<%= link_to_remote "<< " + t('pagination.first'), :url => {
:action => action,
:id => assignment.id,
:filter => filter,
:page => 1,
:per_page => per_page,
:sort_by => sort_by,
:alpha_category => alpha_pagination_options[0],
:update_alpha_pagination_options => "false"
},
:before => "ap_thinking_start('#{table_name}');",
:complete => "ap_thinking_stop(); window.location.href = window.location.href + '#value=param';" %>
Notice that I stuck it right after the :complete => “ap_thinking_stop(); Additionally, notice that we are no longer limited to a’s. We can not apply this to any html objects.
Cheers,
Joseph
leave a comment