Skip to content

Software Development Blogs: Programming, Software Testing, Agile Project Management

Methods & Tools

Subscribe to Methods & Tools
if you are not afraid to read more than one page to be a smarter software developer, software tester or project manager!

Programming

R: Snakes and ladders markov chain

Mark Needham - Thu, 04/09/2015 - 23:02

A few days ago I read a really cool blog post explaining how Markov chains can be used to model the possible state transitions in a game of snakes and ladders, a use of Markov chains I hadn’t even thought of!

While the example is very helpful for understanding the concept, my understanding of the code is that it works off the assumption that any roll of the dice that puts you on a score > 100 is a winning roll.

In the version of the game that I know you have to land exactly on 100 to win. e.g if you’re on square 98 and roll a 6 you would go forward 2 spaces to 100 and then bounce back 4 spaces to 96.

I thought it’d be a good exercise to tweak the code to cater for this:

n=100
 
# We have 6 extra columns because we want to represent throwing of the dice which results in a final square > 100
M=matrix(0,n+1,n+1+6)
rownames(M)=0:n
colnames(M)=0:(n+6)
 
# set probabilities of landing on each square assuming that there aren't any snakes or ladders
for(i in 1:6){
  diag(M[,(i+1):(i+1+n)])=1/6
}
 
# account for 'bounce back' if a dice roll leads to a final score > 100
for(i in 96:100) {
  for(c in 102:107) {
    idx = 101 - (c - 101)  
    M[i, idx] = M[i, idx] + M[i, c]
  }  
}

We can inspect the last few rows to check that if the transition matrix is accurate:

> M[95:100,95:101]
 
   94        95        96        97        98        99       100
94  0 0.1666667 0.1666667 0.1666667 0.1666667 0.1666667 0.1666667
95  0 0.0000000 0.1666667 0.1666667 0.1666667 0.3333333 0.1666667
96  0 0.0000000 0.0000000 0.1666667 0.3333333 0.3333333 0.1666667
97  0 0.0000000 0.0000000 0.1666667 0.3333333 0.3333333 0.1666667
98  0 0.0000000 0.1666667 0.1666667 0.1666667 0.3333333 0.1666667
99  0 0.1666667 0.1666667 0.1666667 0.1666667 0.1666667 0.1666667

If we’re on the 99th square (the last row) we could roll a 1 and end up on 100, a 2 and end up on 99 (1 forward, 1 back), a 3 and end up on 98 (1 forward, 2 back), a 4 and end up on 97 (1 forward, 3 back), a 5 and end up on 96 (1 forward, 4 back) or a 6 and end up on 95 (1 forward, 5 back). i.e. we can land on 95, 96, 97, 98, 99 or 100 with 1/6 probability.

If we’re on the 96th square (the 3rd row) we could roll a 1 and end up on 97, a 2 and end up on 98, a 3 and end up on 99, a 4 and end up on 100, a 5 and end up on 99 (4 forward, 1 back) or a 6 and end up on 98 (4 forward, 2 back). i.e. we can land on 97 with 1/6 probability, 98 with 2/6 probability, 99 with 2/6 probability or 100 with 1/6 probability.

We could do a similar analysis for the other squares but it seems like the probabilities are being calculated correctly.

Next we can update the matrix with the snakes and ladders. That code stays the same:

# get rid of the extra columns, we don't need them anymore
M=M[,1:(n+1)]
 
# add in the snakes and ladders
starting = c(4,9,17,20,28,40,51,54,62,64,63,71,93,95,92)
ending   = c(14,31,7,38,84,59,67,34,19,60,81,91,73,75,78)
 
for(i in 1:length(starting)) {
  # Retrieve current probabilities of landing on the starting square
  v=M[,starting[i]+1]  
  ind=which(v>0)
 
  # Set no probability of falling on the starting squares
  M[ind,starting[i]+1]=0
 
  # Move all existing probabilities to the ending squares
  M[ind,ending[i]+1]=M[ind,ending[i]+1]+v[ind]
}

We can also simplify the powermat function which is used to simulate what the board would look like after a certain number of dice rolls:

# original
powermat=function(P,h){
  Ph=P
  if(h>1) {
    for(k in 2:h) {
      Ph=Ph%*%P
    }
  }
  return(Ph)
}
 
#new 
library(expm)
powermat = function(P,h) {
  return (P %^% h)
}

initial=c(1,rep(0,n))
h = 1
> (initial%*%powermat(M,h))[1:15]
     0         1         2         3 4         5         6 7 8 9 10 11 12 13        14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
[1,] 0 0.1666667 0.1666667 0.1666667 0 0.1666667 0.1666667 0 0 0  0  0  0  0 0.1666667  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
     46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
[1,]  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0   0

One interesting thing I noticed is that it now seems to take way more turns on average to finish the game than when you didn’t need to score exactly 100 to win:

> sum(1 - game)
[1] 999
distrib=initial%*%M
game=rep(NA,1000)
for(h in 1:length(game)){
game[h]=distrib[n+1]
distrib=distrib%*%M}
plot(1-game[1:200],type="l",lwd=2,col="red",
ylab="Probability to be still playing")
2015 04 09 22 48 24

I expected it to take longer to finish the game but not this long! I think I’ve probably made a mistake but I’m not sure where…

Categories: Programming

R: Snakes and ladders markov chain

Mark Needham - Thu, 04/09/2015 - 23:02

A few days ago I read a really cool blog post explaining how Markov chains can be used to model the possible state transitions in a game of snakes and ladders, a use of Markov chains I hadn’t even thought of!

While the example is very helpful for understanding the concept, my understanding of the code is that it works off the assumption that any roll of the dice that puts you on a score > 100 is a winning roll.

In the version of the game that I know you have to land exactly on 100 to win. e.g if you’re on square 98 and roll a 6 you would go forward 2 spaces to 100 and then bounce back 4 spaces to 96.

I thought it’d be a good exercise to tweak the code to cater for this:

n=100
 
# We have 6 extra columns because we want to represent throwing of the dice which results in a final square > 100
M=matrix(0,n+1,n+1+6)
rownames(M)=0:n
colnames(M)=0:(n+6)
 
# set probabilities of landing on each square assuming that there aren't any snakes or ladders
for(i in 1:6){
  diag(M[,(i+1):(i+1+n)])=1/6
}
 
# account for 'bounce back' if a dice roll leads to a final score > 100
for(i in 96:100) {
  for(c in 102:107) {
    idx = 101 - (c - 101)  
    M[i, idx] = M[i, idx] + M[i, c]
  }  
}

We can inspect the last few rows to check that if the transition matrix is accurate:

> M[95:100,95:101]
 
   94        95        96        97        98        99       100
94  0 0.1666667 0.1666667 0.1666667 0.1666667 0.1666667 0.1666667
95  0 0.0000000 0.1666667 0.1666667 0.1666667 0.3333333 0.1666667
96  0 0.0000000 0.0000000 0.1666667 0.3333333 0.3333333 0.1666667
97  0 0.0000000 0.0000000 0.1666667 0.3333333 0.3333333 0.1666667
98  0 0.0000000 0.1666667 0.1666667 0.1666667 0.3333333 0.1666667
99  0 0.1666667 0.1666667 0.1666667 0.1666667 0.1666667 0.1666667

If we’re on the 99th square (the last row) we could roll a 1 and end up on 100, a 2 and end up on 99 (1 forward, 1 back), a 3 and end up on 98 (1 forward, 2 back), a 4 and end up on 97 (1 forward, 3 back), a 5 and end up on 96 (1 forward, 4 back) or a 6 and end up on 95 (1 forward, 5 back). i.e. we can land on 95, 96, 97, 98, 99 or 100 with 1/6 probability.

If we’re on the 96th square (the 3rd row) we could roll a 1 and end up on 97, a 2 and end up on 98, a 3 and end up on 99, a 4 and end up on 100, a 5 and end up on 99 (4 forward, 1 back) or a 6 and end up on 98 (4 forward, 2 back). i.e. we can land on 97 with 1/6 probability, 98 with 2/6 probability, 99 with 2/6 probability or 100 with 1/6 probability.

We could do a similar analysis for the other squares but it seems like the probabilities are being calculated correctly.

Next we can update the matrix with the snakes and ladders. That code stays the same:

# get rid of the extra columns, we don't need them anymore
M=M[,1:(n+1)]
 
# add in the snakes and ladders
starting = c(4,9,17,20,28,40,51,54,62,64,63,71,93,95,92)
ending   = c(14,31,7,38,84,59,67,34,19,60,81,91,73,75,78)
 
for(i in 1:length(starting)) {
  # Retrieve current probabilities of landing on the starting square
  v=M[,starting[i]+1]  
  ind=which(v>0)
 
  # Set no probability of falling on the starting squares
  M[ind,starting[i]+1]=0
 
  # Move all existing probabilities to the ending squares
  M[ind,ending[i]+1]=M[ind,ending[i]+1]+v[ind]
}

We can also simplify the powermat function which is used to simulate what the board would look like after a certain number of dice rolls:

# original
powermat=function(P,h){
  Ph=P
  if(h>1) {
    for(k in 2:h) {
      Ph=Ph%*%P
    }
  }
  return(Ph)
}
 
#new 
library(expm)
powermat = function(P,h) {
  return (P %^% h)
}

initial=c(1,rep(0,n))
h = 1
> (initial%*%powermat(M,h))[1:15]
     0         1         2         3 4         5         6 7 8 9 10 11 12 13        14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
[1,] 0 0.1666667 0.1666667 0.1666667 0 0.1666667 0.1666667 0 0 0  0  0  0  0 0.1666667  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
     46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
[1,]  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0   0

One interesting thing I noticed is that it now seems to take way more turns on average to finish the game than when you didn’t need to score exactly 100 to win:

> sum(1 - game)
[1] 999
distrib=initial%*%M
game=rep(NA,1000)
for(h in 1:length(game)){
game[h]=distrib[n+1]
distrib=distrib%*%M}
plot(1-game[1:200],type="l",lwd=2,col="red",
ylab="Probability to be still playing")
2015 04 09 22 48 24

I expected it to take longer to finish the game but not this long! I think I’ve probably made a mistake but I’m not sure where…

Update

Antonios found the mistake I’d made – when on the 100th square we should have a 1 as the probability of getting to the 100th square. i.e. we need to update M like so:

M[101,101] = 1

Now if we visualise he probability that we’re still playing we get a more accurate curve:

distrib=initial%*%M
game=rep(NA,1000)
for(h in 1:length(game)){
game[h]=distrib[n+1]
distrib=distrib%*%M}
plot(1-game[1:200],type="l",lwd=2,col="red",
ylab="Probability to be still playing")
2015 04 10 23 49 21

Categories: Programming

We throw pie with a little help from our friends

Google Code Blog - Thu, 04/09/2015 - 20:15

Posted by Jon Simantov, Fun Propulsion Labs at Google

Originally posted to the Google Open Source blog

Fun Propulsion Labs at Google* is back today with some new releases for game developers. We’ve updated Pie Noon (our open source Android TV game) with networked multi-screen action, and we’ve also added some delicious new libraries we’ve been baking since the original release: the Pindrop audio library and the Motive animation system.

Pie Noon multi-screen action

Got an Android TV and up to 4 friends with Android phones or tablets? You’re ready for some strategic multi-player mayhem in this updated game mode. Plan your next move in secret on your Android phone: will you throw at an opponent, block an incoming attack, or take the risky approach and wait for a larger pie? Choose your target and action, then watch the Android TV to see what happens!


We used the NearbyConnections API from the most recent version of Google Play Games services to easily connect smartphones to your Android TV and turn our original Pie Noon party game into a game of turn-based strategy. You can grab the latest version of Pie Noon from Google Play to try it out, or crack open the source code and take a look at how we used FlatBuffers to encode data across the network in a fast, portable, bandwidth-efficient way.

Pindrop: an open source game audio library

Pindrop is a cross-platform C++ library for managing your in-game audio. It supports cross compilation to Android, Linux, iOS and OSX. An early version of this code was part of the first Pie Noon release, but it’s now available as a separate library that you can use in your own games. Pindrop handles loading and unloading sound banks, tracking sound locations and listeners, prioritization of your audio channels, and more.

Pindrop is built on top of several other pieces of open source technology:

  • SDL Mixer is used as a backend for actually playing the audio.
  • The loading of data and configuration files is handled by our serialization library, FlatBuffers.
  • Our own math library, MathFu, is used for a number of under-the-hood calculations.

You can download the latest open source release from our GitHub page. Documentation is available here and a sample project is included in the source tree. Please feel free to post any questions in our discussion list.

Motive: an open source animation system

The Motive animation system can breathe life into your static scenes. It does this by applying motion to simple variables. For example, if you’d like a flashlight to shine on a constantly-moving target, Motive can animate the flashlight so that it moves smoothly yet responsively.

Motive animates both spline-based motion and procedural motion. These types of motion are not technically difficult, but they are artistically subtle. It's easy to get the math wrong. It's easy to end up with something that moves as required but doesn't quite feel right. Motive does the math and lets you focus on the feeling.

Motive is scalable. It's designed to be extremely fast. It also has a tight memory footprint -- smaller than traditional animation compression -- that's based on Dual Cubic Splines. Our hope is that you might consider using Motive as a high-performance back-end to your existing full-featured animation systems.

This initial release of Motive is feature-light since we focused our early efforts on doing something simple very quickly. We support procedural and spline-based animation, but we don't yet support data export from animation packages like Blender or Maya. Motive 1.0 is suitable for props -- trees, cameras, extremities -- but not fully rigged character models. Like all FPL technologies, Motive is open source and cross-platform. Please check out the discussion list, too.

What’s Fun Propulsion Labs at Google?

You might remember us from such Android games as Pie Noon, LiquidFun Paint, and VoltAir, and such cross-platform libraries as MathFu, LiquidFun, and FlatBuffers.

Want to learn more about our team? Check out this recent episode of Game On! with Todd Kerpelman for the scoop!


* Fun Propulsion Labs is a team within Google that's dedicated to advancing gaming on Android and other platforms.

Categories: Programming

Quantity Versus Quality Is An Illusion

Making the Complex Simple - John Sonmez - Wed, 04/08/2015 - 16:00

In this video, I respond to a question that I’ve been asked a lot. I produce a lot of stuff, but am I sacrificing quality for quantity? I also talk about how I spent only 3 months to publish my book, Soft Skills. In this video, I respond to a question that I’ve been asked […]

The post Quantity Versus Quality Is An Illusion appeared first on Simple Programmer.

Categories: Programming

Sun Surveyor brings augmented reality to photographers using Google Maps APIs

Google Code Blog - Tue, 04/07/2015 - 23:31

Originally posted to the Google Geo Developers blog

Editor’s note: This post is written by Adam Ratana, developer of Sun Surveyor. Read how Sun Surveyor is using Google Maps APIs to help photographers capture the perfect photo.

Posted by Adam Ratana, developer of Sun Surveyor

I’m a photography enthusiast, and I’m always looking for ways to improve my work. That’s what led me to develop Sun Surveyor, an iOS and Android app that uses Google Maps APIs to visualize the location of the sun and the moon anywhere in the world. The app makes it easy to figure out when the natural lighting will be just right — and get the ideal shot.

Sun Surveyor uses augmented reality to overlay the paths of the sun and moon on a camera’s view, so you can see where in the sky they’ll be at a specific time and place. Photographers can use it to plan their shots ahead of time, and businesses can use it to gauge things like how best to align solar panels to make the most efficient use of the angle of the sun.

The app uses multiple Google Maps APIs, including the Elevation API, the Time Zone API, the Google Maps SDK for iOS and the Google Maps Android API. The Android API, which includes Street View, was particularly helpful. It allowed me to overlay the path of the sun and moon on any Street View location anywhere in the world. For programming details, see this blog post.

The following screen captures give you a sense of how the app works. They show overlays on top of the iconic Half Dome in Yosemite National Park. The first shows the paths of the sun (yellow line) and moon (blue line) over an aerial view of Yosemite Valley. The green line shows the distance between the photographer and the object to be photographed — in this case, Half Dome.

This next screen capture shows how the app looks when in Street View mode. Again, the yellow line shows the sun’s path, and the blue line shows the moon’s path. The green line represents the horizon. You can see how the app lets you plan the right time to get a shot of the sun behind Half Dome: in this particular instance, 8:06 am.

Nearly 500,000 people around the world have downloaded the free version of Sun Surveyor, and many have paid for the full edition. They’re taking remarkable photos as a result, and what started as a hobby for me has turned into a business — thanks to Google Maps APIs.

Categories: Programming

Neo4j: The learning to cycle dependency graph

Mark Needham - Tue, 04/07/2015 - 21:59

Over the past couple of weeks I’ve been reading about skill building and the break down of skills into more manageable chunks, and recently had a chance to break down the skills required to learn to cycle.

I initially sketched out the skill progression but quickly realised I had drawn a dependency graph and thought that putting it into Neo4j would simplify things.

I started out with the overall goal for cycling which was to ‘Be able to cycle through a public park':

MERGE (:Goal:Task {name: "Be able to cycle through a public park"})

This goal is easy for someone who’s already learnt to cycle but if we’re starting from scratch it’s a bit daunting so we need to break it down into a simpler skill that we can practice.

The mini algorithm that we’re going to employ for task breakdown is this:

  1. Can we do the given task now?
  2. Break the task down into something simpler and return to 1.

One of the things to keep in mind is that we won’t get the break down perfect the first time so we may need to change it. For a diagram drawn on a piece of paper this would be annoying but in Neo4j it’s just a simpler refactoring.

Going back to cycling. Since the goal isn’t yet achievable we need to break that down into something a bit easier. Let’s start with something really simple:

MERGE (task:Task {name: "Take a few steps forward while standing over the bike"})
WITH task
MATCH (goal:Goal:Task {name: "Be able to cycle through a public park"})
MERGE (goal)-[:DEPENDS_ON]->(task)

In the first line we create our new task and then we connect it to our goal which we created earlier.

Graph  9

After we’ve got the hang of walking with the bike we want to get comfortable with cycling forward a few rotations while sitting on the bike but to do that we need to be able to get the bike moving from a standing start. We might also have another step where we cycle forward while standing on the bike as that might be slightly easier.

Let’s update our graph:

// First let's get rid of the relationship between our initial task and the goal
MATCH (initialTask:Task {name: "Take a few steps forward while standing over the bike"})
MATCH (goal:Goal {name: "Be able to cycle through a public park"})
MATCH (goal)-[rel:DEPENDS_ON]->(initialTask)
DELETE rel
 
WITH initialTask, goal, ["Get bike moving from standing start", "Cycle forward while standing", "Cycle forward while sitting"] AS newTasks
 
// Create some nodes for our new tasks
UNWIND newTasks AS newTask
MERGE (t:Task {name: newTask})
WITH initialTask, goal, COLLECT(t) AS newTasks
WITH initialTask, goal, newTasks, newTasks[0] AS firstTask, newTasks[-1] AS lastTask
 
// Connect the last task to the goal
MERGE (goal)-[:DEPENDS_ON]->(lastTask)
 
// And the first task to our initial task
MERGE (firstTask)-[:DEPENDS_ON]->(initialTask)
 
// And all the tasks to each other
FOREACH(i in RANGE(0, length(newTasks) - 2) |
  FOREACH(t1 in [newTasks[i]] | FOREACH(t2 in [newTasks[i+1]] |
    MERGE (t2)-[:DEPENDS_ON]->(t1) 
)))
Graph  10

We don’t strictly need to learn how to cycle while standing up – we could just go straight from getting the bike moving to cycling forward while sitting. Let’s update the graph to reflect that:

MATCH (sitting:Task {name: "Cycle forward while sitting"})
MATCH (moving:Task {name: "Get bike moving from standing start"})
MERGE (sitting)-[:DEPENDS_ON]->(moving)

Graph  11

Once we’ve got the hang of those tasks let’s add in a few more to get us closer to our goal:

WITH [
  {skill: "Controlled stop using brakes/feet", dependsOn: "Cycle forward while sitting"},
  {skill: "Steer around stationary objects", dependsOn: "Controlled stop using brakes/feet"},
  {skill: "Steer around people", dependsOn: "Steer around stationary objects"},
  {skill: "Navigate a small circular circuit", dependsOn: "Steer around stationary objects"},
  {skill: "Navigate a loop of a section of the park", dependsOn: "Navigate a small circular circuit"},
  {skill: "Navigate a loop of a section of the park", dependsOn: "Steer around people"},
  {skill: "Be able to cycle through a public park", dependsOn: "Navigate a loop of a section of the park"}
 
] AS newTasks
 
FOREACH(newTask in newTasks |
  MERGE (t1:Task {name: newTask.skill})   
  MERGE (t2:Task {name: newTask.dependsOn})
  MERGE (t1)-[:DEPENDS_ON]->(t2)
)

Finally let’s get rid of the relationship from our goal to ‘Cycle forward while sitting’ since we’ve replaced that with some intermediate steps:

MATCH (task:Task {name: "Cycle forward while sitting"})
WITH task
MATCH (goal:Goal:Task {name: "Be able to cycle through a public park"})
MERGE (goal)-[rel:DEPENDS_ON]->(task)
DELETE rel

And here’s what the final dependency graph looks like:

Graph  13

Although I put this into Neo4j in order to visualise the dependencies we can now query the data as well. For example, let’s say I know how to cycle forward while sitting on the bike. What steps are there between me and being able to cycle around a park?

MATCH (t:Task {name: "Cycle forward while sitting"}),
      (g:Goal {name: "Be able to cycle through a public park"}),
      path = shortestpath((g)-[:DEPENDS_ON*]->(t))
RETURN path

Graph  14

Or if we want a list of the tasks we need to do next we could restructure the query slightly:

MATCH (t:Task {name: "Cycle forward while sitting"}),
      (g:Goal {name: "Be able to cycle through a public park"}),
      path = shortestpath((t)<-[:DEPENDS_ON*]->(g))
WITH [n in nodes(path) | n.name] AS tasks
UNWIND tasks AS task
RETURN task
 
==> +--------------------------------------------+
==> | task                                       |
==> +--------------------------------------------+
==> | "Cycle forward while sitting"              |
==> | "Controlled stop using brakes/feet"        |
==> | "Steer around stationary objects"          |
==> | "Steer around people"                      |
==> | "Navigate a loop of a section of the park" |
==> | "Be able to cycle through a public park"   |
==> +--------------------------------------------+
==> 6 rows

That’s all for now but I think this is an interesting way of tracking how you’d learn a skill. I’m trying a similar approach for some statistics topics I’m learning about but I’ve found the order of tasks isn’t so linear there – interestingly much more a graph than a tree.

Categories: Programming

Ho Ho Ho! Google's Santa Tracker is now open source

Google Code Blog - Tue, 04/07/2015 - 18:40

Posted by Ankur Kotwal, Software Engineer

The holiday spirit is about giving and though we’re early into April, we’re still in that spirit. Today, we’re announcing that Google's Santa Tracker is now open source on GitHub at google/santa-tracker-web and google/santa-tracker-android. Now you can see how we’ve used many of our developer products to build a fun and engaging experience that runs across the web and Android.

Santa Tracker isn’t just about watching Santa’s progress as he delivers presents on December 24. Visitors can also have fun with the winter-inspired games and an interactive North Pole village while Santa prepares for his big journey throughout the holidays.

Below is a summary of what we’ve released as open source.

Android app
  • The Santa Tracker Android app is a single APK, supporting all devices running Ice Cream Sandwich (4.0) and up. The source code for the app can be found here.
  • Santa’s village is a canvas-based graphical launcher for videos, games and the tracker. In order to span 10,000 pixels in width, the village uses the Android resource hierarchy in a unique way to scale graphics without needing assets for multiple density buckets, thereby reducing the APK size.
  • Games on Santa Tracker Android are built using a combination of technologies such as JBox2D (gumball game), Android view hierarchy (memory match game) and OpenGL with a purpose-built rendering engine (jetpack game).
  • To help with user engagement, the app uses the App Indexing API to enable autocomplete support for Santa Tracker games from Google Search. This is done using deep linking.
Android Wear
  • The custom watch faces on Android Wear provide a personalized touch. Having Santa or one of his friendly elves tell the time brings a smile to all. Building custom watch faces is a lot of fun but providing a performant, battery friendly watch face requires certain considerations. The watch face source code can be found here.
  • Santa Tracker uses notifications to let users know when Santa has started his journey. The notifications are further enhanced to provide a great experience on wearables using custom backgrounds and actions that deep link into the app.
On the web
  • Santa Tracker on the web was built using Polymer, a powerful new library from the Chrome team based on Web Components. Santa Tracker’s use of Polymer demonstrates how easy it is to package code into reusable components. Every scene in Santa's village (games, videos, and interactive pages) is a custom element, only loaded when needed, minimizing the startup cost of Santa Tracker.
  • Santa Tracker’s interactive and fun experience is built using the Web Animations API, a standardized JavaScript API for unifying animated content - this is a huge leap up from using CSS animations. Web Animations can be written imperatively, are supported in all modern browsers via polyfills and Polymer uses them internally to create its amazing material design effects. Examples of these animations can be found using this GitHub search.
  • Santa believes in mobile first; this year's experience was built to be optimized for the mobile web, including a fully responsive design, touch gesture support using Polymer, and new features like meta-theme color and the application manifest for add to homescreen.
  • To provide exceptional localization support, a new i18n-msg component was built, a first for Web Components. Modeled after the Chrome extension i18n system, it enables live page-refresh for development but has a build step for optimization.

Now that the source code is also available, developers can see many of the parts that come together to make Santa Tracker. We hope that developers are inspired to make their own magical experiences.

Categories: Programming

New Advanced services in Apps Script

Google Code Blog - Mon, 04/06/2015 - 22:18

Posted by Kalyan Reddy, Developer Programs Engineer

Originally posted on the Google Apps Developer blog

Apps Script includes many built-in Google services for major products like Gmail and Drive, and lately, we've been working to add other APIs that developers have been clamoring for as advanced Google services. Today, we are launching seven more advanced services, including:

Like all other advanced services in Apps Script, they must first be enabled before use. Once enabled, they are just as easy to use as built-in Apps Script services -- the editor provides autocomplete, and the authentication flow is handled automatically.

Here is a sample using the Apps Activity advanced service that shows how to get a list of users that have performed an action on a particular Google Drive file.


function getUsersActivity() {
var fileId = 'YOUR_FILE_ID_HERE';
var pageToken;
var users = {};
do {
var result = AppsActivity.Activities.list({
'drive.fileId': fileId,
'source': 'drive.google.com',
'pageToken': pageToken
});
var activities = result.activities;
for (var i = 0; i < activities.length; i++) {
var events = activities[i].singleEvents;
for (var j = 0; j < events.length; j++) {
var event = events[j];
users[event.user.name] = true;
}
}
pageToken = result.nextPageToken;
} while (pageToken);
Logger.log(Object.keys(users));
}

This function uses the AppsActivity.Activities.list() method, passing in the required parameters drive.fileId and source, and uses page tokens to get the full list of activities. The full list of parameters this method accepts can be found in the Apps Activity API's reference documentation.

Categories: Programming

Rolling upgrade of Docker applications using CoreOS and Consul

Xebia Blog - Mon, 04/06/2015 - 21:17

In the previous blog post, we showed you how to setup a High Available Docker Container Application platform using CoreOS and Consul. In this short blog post, we will show you how easy it is to perform a rolling upgrade of a deployed application.

Architecture

In this blog post we will use the same architecture but for the deployment we used Vagrant instead of Amazon AWS which is a little bit snappier to use  :-).

coreos-vagrant-cluster

In the Vagrant architecture we have replaced the AWS Elastic Load Balancer with our own consul-http-router Load Balancer and moved it inside the cluster. This is a HA proxy which dynamicly routes traffic to any of the http routers in the cluster.

Getting Started

In order to get your own container platform as a service running on vagrant, clone the repository and start your cluster.


git clone https://github.com/mvanholsteijn/coreos-container-platform-as-a-service.git
cd coreos-container-platform-as-a-service/vagrant
vagrant up
...
vagrant up
Bringing machine 'core-01' up with 'virtualbox' provider...
Bringing machine 'core-02' up with 'virtualbox' provider...
Bringing machine 'core-03' up with 'virtualbox' provider...
...
Checkout the cluster

After the cluster has started, you can use the following command to checkout whether your cluster is fully operational. You should see 5 units running on each machine.

for node in 1 2 3 ; do
  vagrant ssh -c "systemctl | grep consul" core-0$node
done
...
consul-http-router-lb.service loaded active running consul-http-router-lb
consul-http-router.service loaded active running consul-http-router
consul-server-announcer.service loaded active running Consul Server Announcer
consul-server-registrator.service loaded active running Registrator
consul-server.service loaded active running Consul Server Agent

 

Deploying the application

Once the cluster is running, you can deploy or paas-monitor application. This happens in two stages. First you submit the template.

fleetctl submit paas-monitor\@.service

Then, you load and start the new instances.

fleetctl load paas-monitor\@{1..6}.service
fleetctl start paas-monitor\@{1..6}.service
fleetctl list-units | grep paas-monitor

You can now see the paas-monitor in operation on your machine by opening http://paas-monitor.127.0.0.1.xip.io:8080 and clicking on start.  You should see something like shown in the table below. Leave this running while we are going to update the application!

host release message # of calls avg response time last response time 47ea72be3817:1337 v1 Hello World from v1 53 8 11 cc4227a493d7:1337 v1 Hello World from v1 59 11 8 04a58012910c:1337 v1 Hello World from v1 54 7 6 090caf269f6a:1337 v1 Hello World from v1 58 7 7 096d01a63714:1337 v1 Hello World from v1 53 7 9 d43c0744622b:1337 v1 Hello World from v1 55 7 6 Updating the application

Now we are going to update your application. Normally, we would expect that you specify a higher version of the Docker image into unit file. But instead of changing the version of the image to be executed change the value of the environment variable RELEASE in the unit template file  paas-monitor\@.service.

sed -i -e 's/--env RELEASE=[^ ]*/--env RELEASE=v2/' paas-monitor\@.service

Now we have changed the unit template file, you should destroy the old unit file and submit the new one.

fleetctl destroy paas-monitor\@.service
fleetctl submit paas-monitor\@.service

Now you have two options, a slow one and a fast one.

Slow Option

The slow option is to  iterate over the running instances, stop them one by one, destroy them and start a new instance based on the newly submitted template. Because this is boring, repetitive work we have created a small script that does this :-)


./rolling-upgrade.sh paas-monitor\@.service

Fast Option

The fast option is to start 6 new ones and stop all 6 old ones after the new ones are running.

fleetctl load paas-monitor\@1{1..6}.service
fleetctl start paas-monitor\@1{1..6}.service
fleetctl list-units | grep 'paas-monitor\@1[1-6].service' | grep running
fleetctl stop paas-monitor@{1..6}.service
fleetctl destroy paas-monitor@{1..6}.service

When you watch your monitor, you should see the new instance appear one by one.

host release message # of calls avg response time last response time 47ea72be3817:1337 v1 Hello World from v1 53 8 11 cc4227a493d7:1337 v1 Hello World from v1 59 11 8 04a58012910c:1337 v1 Hello World from v1 54 7 6 090caf269f6a:1337 v1 Hello World from v1 58 7 7 096d01a63714:1337 v1 Hello World from v1 53 7 9 d43c0744622b:1337 v1 Hello World from v1 55 7 6 fee39f857479:1337 v2 Hello World from v2 18 7 9 99c1a5aa3b8b:1337 v2 Hello World from v2 2 7 9 Conclusion

CoreOS and Consul provides all the basic functionality to manage your Docker containers and perform rolling upgrade of your application.

 

5 Ways to Destroy Your Productivity

Making the Complex Simple - John Sonmez - Mon, 04/06/2015 - 16:00

Hey you. Yeah, you. Want to know how to absolutely and utterly destroy your productivity? Good. You’ve come to the right place. Being productive is overrated. I mean really. What good does it get you? The more work you get done, the more work you get asked to do. So, here are a few quick […]

The post 5 Ways to Destroy Your Productivity appeared first on Simple Programmer.

Categories: Programming

Increasing the tap area of UIButtons made with PaintCode

Xebia Blog - Sun, 04/05/2015 - 21:04

Whether you're a developer or not, every iPhone user has experienced the case where he or she tries to tap a button (with an image and nothing happens. Most likely because the user missed the button and pressed next to it. And that's usually not the fault of the user, but the fault of the developer/designer because the button is too small. The best solution is to have bigger icons (we're only talking about image buttons, no text only buttons) so it's easier for the user to tap. But sometimes you (or your designer) just wants to use a small icon, because it simply looks better. What do you do then?

For buttons with normal images this is very easy. Just make the button bigger. However, for buttons that draw themselves using PaintCode, this is slightly harder. In this blogpost I'll explain why and show two different ways to tackle this problem.

I will not go into the basics of PaintCode. If you're new to PaintCode have a look at their website or go to Freek Wielstra's blogpost Working With PaintCode And Interface Builder In XCode. I will be using the examples of his post as basis for the examples here so it's good to read his post first (though not strictly necessary).

To get a better understanding of how a UIButton with an image differs from a UIButton drawn with PaintCode, I will first show what a non-PaintCode button would look like. Below we have a PNG image of 25 by 19 pixels (for non-Retina). Apple recommends buttons to be 44 by 44 points so we increase the size of the button. The button has a gray background and we can see that the image stays the original size and is nicely in the center while the touch target becomes big enough for the user to easily tap it.

uibutton-content

The reason it behaves like this is because of the Control settings in the Attribute Inspector. We could let the content align different or even make it stretch. But stretching this would be a bad idea since it's not a vector image and it would look pixelated.

That's why we love PaintCode graphics. They can scale to any size so we can use the same graphic in different places and at different screen scales (non-retina, retina @2x and iPhone 6 plus which uses @3x). But what if we don't want the graphic to scale of to the entire size of the button like above?

A bad solution would be not to use a frame in PaintCode. Yes, the image will stay the size you gave it when you put it in a button, but it will be left-top aligned. Also you won't be able to use it anywhere else.

If you are really sure that you will never use the image anywhere else than on your button you can group your vector graphic and tell it to have flexible margins within the frame and have a fixed width and height. Using the email icon from Freek Wielstra this will look something like this:

Screen Shot 2015-04-05 at 20.39.36

You can verify that this works by changing the size of the frame. The email icon should always stay in the center both horizontal and vertical and it should stay the same size. The same will happen if you use this in a custom UIButton.

Now let's have a look at a better solution that will allow us to reuse the graphic at different sizes and have some padding around it in a button. It's easier than you might expect and it follows the actual rules of a UIButton. The UIButton class has a property named contentEdgeInsets with the following description: "The inset or outset margins for the rectangle surrounding all of the button’s content." That sounds exactly like what we need. Our PaintCode graphics are the content of the buttons right? Unfortunately it's not treated as such since we are doing the drawing ourselves which does not adhere to that property. However we can very easily make it adhere to it:

@IBDesignable
class EmailButton: UIButton {

    override func drawRect(rect: CGRect) {
        StyleKit.drawEmail(frame: UIEdgeInsetsInsetRect(rect, contentEdgeInsets), color: tintColor!)
    }
    
}

And that's really all there is to it. Just make sure to put a frame around your graphics in PaintCode and make it stretch to all sides of the frame. Now you can specify the content insets of your buttons in Interface Builder and you icon will have padding around it.

Screen Shot 2015-04-05 at 20.59.42

R: Markov Chain Wikipedia Example

Mark Needham - Sun, 04/05/2015 - 11:07

Over the weekend I’ve been reading about Markov Chains and I thought it’d be an interesting exercise for me to translate Wikipedia’s example into R code.

But first a definition:

A Markov chain is a random process that undergoes transitions from one state to another on a state space.

It is required to possess a property that is usually characterized as “memoryless”: the probability distribution of the next state depends only on the current state and not on the sequence of events that preceded it.

that ‘random process’ could be moves in a Monopoly game, the next word in a sentence or, as in Wikipedia’s example, the next state of the Stock Market.

The diagram below shows the probabilities of transitioning between the various states:

800px Finance Markov chain example state space svg

e.g. if we’re in a Bull Market the probability of the state of the market next week being a Bull Market is 0.9, a Bear Market is 0.075 and a Stagnant Market is 0.025.

We can model the various transition probabilities as a matrix:

M = matrix(c(0.9, 0.075, 0.025, 0.15, 0.8, 0.05, 0.25, 0.25, 0.5),
          nrow = 3,
          ncol = 3,
          byrow = TRUE)
 
> M
     [,1]  [,2]  [,3]
[1,] 0.90 0.075 0.025
[2,] 0.15 0.800 0.050
[3,] 0.25 0.250 0.500

Rows/Cols 1-3 are Bull, Bear, Stagnant respectively.

Now let’s say we start with a Bear market and want to find the probability of each state in 3 weeks time.

We can do this is by multiplying our probability/transition matrix by itself 3 times and then multiplying the result by a vector representing the initial Bear market state.

threeIterations = (M %*% M %*% M)
 
> threeIterations
> threeIterations
       [,1]    [,2]    [,3]
[1,] 0.7745 0.17875 0.04675
[2,] 0.3575 0.56825 0.07425
[3,] 0.4675 0.37125 0.16125
 
> c(0,1,0) %*% threeIterations
       [,1]    [,2]    [,3]
[1,] 0.3575 0.56825 0.07425

So we have a 56.825% chance of still being in a Bear Market, 35.75% chance that we’re now in a Bull Market and only a 7.425% chance of being in a stagnant market.

I found it a bit annoying having to type ‘%*% M’ multiple times but luckily the expm library allows us to apply a Matrix power operation:

install.packages("expm")
library(expm)
 
> M %^% 3
       [,1]    [,2]    [,3]
[1,] 0.7745 0.17875 0.04675
[2,] 0.3575 0.56825 0.07425
[3,] 0.4675 0.37125 0.16125

The nice thing about this function is that we can now easily see where the stock market will trend towards over a large number of weeks:

> M %^% 100
      [,1]   [,2]   [,3]
[1,] 0.625 0.3125 0.0625
[2,] 0.625 0.3125 0.0625
[3,] 0.625 0.3125 0.0625

i.e. 62.5% of weeks we will be in a bull market, 31.25% of weeks will be in a bear market and 6.25% of weeks will be stagnant,

Categories: Programming

Working with PaintCode and Interface Builder in XCode

Xebia Blog - Sat, 04/04/2015 - 08:00

Every self-respecting iOS developer should know about PaintCode by now, an OSX app for drawing graphics that don't save as images, but as lengths of code that draw graphics. The benefits of this are vastly reduced app installation size - no need to include three resolutions of the same image for every image - and seamlessly scalable graphics.

One thing that I personally struggled with for a while now was how to use them effectively in combination with Interface Builder, the UI development tool for iOS and OSX apps. In this blog I will explain an effective and simple method to draw PaintCode graphics in a way where you can see what you're doing in Interface Builder, using the relatively new @IBDesignable annotation. I will also go into setting colors, and finally about how to deal with views that depend on dynamic runtime data to draw themselves.

First, let's create a simple graphic in PaintCode. Let's draw a nice envelope or email icon. Add a frame around it, and set the constraints to variable so it will adjust to the size of the frame (drag the frame corners around within PaintCode to confirm). This gives us a nice, scalable icon. Save the file, then export it to your xcode project in the language of your choice.

Email icon in PaintCode

Squiggly lines are the best

 

Now, the easiest and most straightforward way to get a PaintCode image into your Interface Builder is to simply create a UIView subclass, and call the relevant StyleKit method in its drawRect method. You can do this too in either Swift or Objective-C; this example will be in Swift, but if you're stuck with the slow Swift compiler in XCode 6.x, you might prefer Objective-C for this kind of simple and straightforward code.

To use it in Interface Builder, simply create a storyboard or xib, drag an UIView onto it, and change its Custom Class to your UIView subclass. Make sure to have your constraints set properly, and run - you should be able to see your custom icon in your working app.

class EmailIcon: UIView {
  override func drawRect(rect: CGRect) {
    StyleKit.drawEmail(frame: rect)
  }
}
Screenshot 2015-04-03 21.36.42

Ghost views, the horror of Interface Builder

 

As you probably noticed though, it's far from practical as it is in Interface Builder right now - all you see (or don't see really) is an empty UIView. I guess you could give it a background color in IB and unset that again in your code, but that's far from practical. Instead, we'll just slap an @IBDesignable annotation onto the UIView subclass. Going back to IB, it should start to compile code, and a moment later, your PaintCode image shows up, resizable and all.

@IBDesignable
class EmailIcon: UIView {
  override func drawRect(rect: CGRect) {
    StyleKit.drawEmail(frame: rect)
  }
}
@IBDesignable view in Interface Builder

like magic

 

Adding color

We can configure our graphic in PaintCode to have a custom color. Just go back to PaintCode and change the Color to 'Parameter' - see image.

Set color to Parameter

Export the file again, and change the call to the StyleKit method to include the color. It's easiest in this case to just pass the UIView's own tintColor property. Going back to Interface Builder, we can now set the default tintColor property, and it should update in the IB preview instantly.

As an alternative, you can add an @IBInspectable color property to your UIView, but I would only recommend this for more complicated UIViews - if they include multiple StyleKit graphics, for example.

@IBDesignable
class EmailIcon: UIView {
  override func drawRect(rect: CGRect) {
    StyleKit.drawEmail(frame: rect, color: tintColor)
  }
}

let's make it Xebia purple, to please the boss

 

Dealing with dynamic properties

One case I had to deal with is an UIView that can draw a selection of StyleKit images, depending on the value of a dynamic model value. I considered a few options to deal with that:

  1. Set a default value, to be overridden at runtime. This is a bit dangerous though; forget to reset or unset this property at runtime and your user will be stuck with some default placeholder, or worse, flat-out wrong information.
  2. Make the property @IBInspectable. This only works with relatively simple values though (strings, numbers, colors), and it has the same problem as the above.

What I needed was a way to set a property, but only from within Interface Builder. Luckily, that exists, as I found out later. In UIView, there is a method called prepareForInterfaceBuilder, which does exactly what it says on the tin - override the method to set properties only relevant in Interface Builder. So in our case:

@IBDesignable
class EmailIcon: UIView {
  // none set by default
  var iconType: String? = nil

  override func drawRect(rect: CGRect) {
    if iconType == "email" {
      StyleKit.drawEmail(frame: rect, color: tintColor)
    }

    if iconType = "email-read" {
      StyleKit.drawEmailRead(frame: rect, color: tintColor)
    }

    // if none of the above, draw nothing
  }

  // draw the 'email' icon by default in Interface Builder
  override func prepareForInterfaceBuilder() {
    iconType = "email"
  }
}

And that's all there is to it. You can use this method to create all of your graphics, keep them dynamically sized and colored, and to use the full power of Interface Builder and PaintCode combined.

Given Enough Money, All Bugs Are Shallow

Coding Horror - Jeff Atwood - Sat, 04/04/2015 - 00:58

Eric Raymond, in The Cathedral and the Bazaar, famously wrote

Given enough eyeballs, all bugs are shallow.

The idea is that open source software, by virtue of allowing anyone and everyone to view the source code, is inherently less buggy than closed source software. He dubbed this "Linus's Law".

Insofar as it goes, I believe this is true. When only the 10 programmers who happen to work at your company today can look at your codebase, it's unlikely to be as well reviewed as a codebase that's public to the world's scrutiny on GitHub.

However, the Heartbleed SSL vulnerability was a turning point for Linus's Law, a catastrophic exploit based on a severe bug in open source software. How catastrophic? It affected about 18% of all the HTTPS websites in the world, and allowed attackers to view all traffic to these websites, unencrypted... for two years.

All those websites you thought were secure? Nope. This bug went unnoticed for two full years.

Two years!

OpenSSL, the library with this bug, is one of the most critical bits of Internet infrastructure the world has – relied on by major companies to encrypt the private information of their customers as it travels across the Internet. OpenSSL was used on millions of servers and devices to protect the kind of important stuff you want encrypted, and hidden away from prying eyes, like passwords, bank accounts, and credit card information.

This should be some of the most well-reviewed code in the world. What happened to our eyeballs, man?

In reality, it's generally very, very difficult to fix real bugs in anything but the most trivial Open Source software. I know that I have rarely done it, and I am an experienced developer. Most of the time, what really happens is that you tell the actual programmer about the problem and wait and see if he/she fixes it – Neil Gunton

Even if a brave hacker communities to read the code, they're not terribly likely to spot one of the hard-to-spot problems. Why? Few open source hackers are security experts. – Jeremy Zawodny

The fact that many eyeballs are looking at a piece of software is not likely to make it more secure. It is likely, however, to make people believe that it is secure. The result is an open source community that is probably far too trusting when it comes to security. – John Viega

I think there are a couple problems with Linus's Law:

  1. There's a big difference between usage eyeballs and development eyeballs. Just because you pull down some binaries in a RPM, or compile something in Linux, or even report bugs back to the developers via their bug tracker, doesn't mean you're doing anything at all to contribute to the review of the underlying code. Most eyeballs are looking at the outside of the code, not the inside. And while you can discover bugs, even important security bugs, through usage, the hairiest security bugs require inside knowledge of how the code works.

  2. The act of writing (or cut-and-pasting) your own code is easier than understanding and peer reviewing someone else's code. There is a fundamental, unavoidable asymmetry of work here. The amount of code being churned out today – even if you assume only a small fraction of it is "important" enough to require serious review – far outstrips the number of eyeballs available to look at the code. (Yes, this is another argument in favor of writing less code.)

  3. There are not enough qualified eyeballs to look at the code. Sure, the overall number of programmers is slowly growing, but what percent of those programmers are skilled enough, and have the right security background, to be able to audit someone else's code effectively? A tiny fraction.

Even if the code is 100% open source, utterly mission critical, and used by major companies in virtually every public facing webserver for customer security purposes, we end up with critical bugs that compromise everyone. For two years!

That's the lesson. If we can't naturally get enough eyeballs on OpenSSL, how does any other code stand a chance? What do we do? How do we get more eyeballs?

The short term answer was:

These are both very good things and necessary outcomes. We should be doing this for all the critical parts of the open source ecosystem people rely on.

But what's the long term answer to the general problem of not enough eyeballs on open source code? It's something that will sound very familar to you, though I suspect Eric Raymond won't be too happy about it.

Money. Lots and lots of money.

Increasingly, companies are turning to commercial bug bounty programs. Either ones they create themselves, or run through third party services like Bugcrowd, Synack, HackerOne, and Crowdcurity. This means you pay per bug, with a larger payout the bigger and badder the bug is.

Or you can attend a yearly event like Pwn2Own, where there's a yearly contest and massive prizes, as large as hundreds of thousands of dollars, for exploiting common software. Staging a big annual event means a lot of publicity and interest, attracting the biggest guns.

That's the message. If you want to find bugs in your code, in your website, in your app, you do it the old fashioned way: by paying for them. You buy the eyeballs.

While I applaud any effort to make things more secure, and I completely agree that security is a battle we should be fighting on multiple fronts, both commercial and non-commercial, I am uneasy about some aspects of paying for bugs becoming the new normal. What are we incentivizing, exactly?

Money makes security bugs go underground

There's now a price associated with exploits, and the deeper the exploit and the lesser known it is, the more incentive there is to not tell anyone about it until you can collect a major payout. So you might wait up to a year to report anything, and meanwhile this security bug is out there in the wild – who knows who else might have discovered it by then?

If your focus is the payout, who is paying more? The good guys, or the bad guys? Should you hold out longer for a bigger payday, or build the exploit up into something even larger? I hope for our sake the good guys have the deeper pockets, otherwise we are all screwed.

I like that Google addressed a few of these concerns by making Pwnium, their Chrome specific variant of Pwn2Own, a) no longer a yearly event but all day, every day and b) increasing the prize money to "infinite". I don't know if that's enough, but it's certainly going in the right direction.

Money turns security into a "me" goal instead of an "us" goal

I first noticed this trend when one or two people reported minor security bugs in Discourse, and then seemed to hold out their hand, expectantly. (At least, as much as you can do something like that in email.) It felt really odd, and it made me uncomfortable.

Am I now obligated, on top of providing a completely free open source project to the world, to pay people for contributing information about security bugs that make this open source project better? Believe me, I was very appreciative of the security bug reporting, and I sent them whatever I could, stickers, t-shirts, effusive thank you emails, callouts in the code and checkins. But open source isn't supposed to be about the money… is it?

Perhaps the landscape is different for closed-source, commercial products, where there's no expectation of quid pro quo, and everybody already pays for the service directly or indirectly anyway.

No Money? No Security.

If all the best security researchers are working on ever larger bug bounties, and every major company adopts these sorts of bug bounty programs, what does that do to the software industry?

It implies that unless you have a big budget, you can't expect to have great security, because nobody will want to report security bugs to you. Why would they? They won't get a payday. They'll be looking elsewhere.

A ransomware culture of "pay me or I won't tell you about your terrible security bug" does not feel very far off, either. We've had mails like that already.

Easy money attracts all skill levels

One unfortunate side effect of this bug bounty trend is that it attracts not just bona fide programmers interested in security, but anyone interested in easy money.

We've gotten too many "serious" security bug reports that were extremely low value. And we have to follow up on these, because they are "serious", right? Unfortunately, many of them are a waste of time, because …

  • The submitter is more interested in scaring you about the massive, critical security implications of this bug than actually providing a decent explanation of the bug, so you'll end up doing all the work.

  • The submitter doesn't understand what is and isn't an exploit, but knows there is value in anything resembling an exploit, so submits everything they can find.

  • The submitter can't share notes with other security researchers to verify that the bug is indeed an exploit, because they might "steal" their exploit and get paid for it before they do.

  • The submitter needs to convince you that this is an exploit in order to get paid, so they will argue with you about this. At length.

The incentives feel really wrong to me. As much as I know security is incredibly important, I view these interactions with an increasing sense of dread because they generate work for me and the returns are low.

What can we do?

Fortunately, we all have the same goal: make software more secure.

So we should view bug bounty programs as an additional angle of attack, another aspect of "defense in depth", perhaps optimized a bit more for commercial projects where there is ample money. And that's OK.

But I have some advice for bug bounty programs, too:

  • You should have someone vetting these bug reports, and making sure they are credible, have clear reproduction steps, and are repeatable, before we ever see them.

  • You should build additional incentives in your community for some kind of collaborative work towards bigger, better exploits. These researchers need to be working together in public, not in secret against each other.

  • You should have a reputation system that builds up so that only the better, proven contributors are making it through and submitting reports.

  • Encourage larger orgs to fund bug bounties for common open source projects, not just their own closed source apps and websites. At Stack Exchange, we donated to open source projects we used every year. Donating a bug bounty could be a big bump in eyeballs on that code.

I am concerned that we may be slowly moving toward a world where given enough money, all bugs are shallow. Money does introduce some perverse incentives for software security, and those incentives should be watched closely.

But I still believe that the people who will freely report security bugs in open source software because

  • It is the right thing to do™

and

  • They want to contribute back to open source projects that have helped them, and the world

… will hopefully not be going away any time soon.

[advertisement] How are you showing off your awesome? Create a Stack Overflow Careers profile and show off all of your hard work from Stack Overflow, Github, and virtually every other coding site. Who knows, you might even get recruited for a great new position!
Categories: Programming

How I met your mother: Story arcs

Mark Needham - Sat, 04/04/2015 - 00:31

After weeks of playing around with various algorithms to extract story arcs in How I met your mother I’ve come to the conclusion that I don’t yet have the skills to completely automate this process so I’m going to change my approach.

The new plan is to treat the outputs of the algorithms as suggestions for possible themes but then have a manual step where I extract what I think are interesting themes in the series.

A theme can consist of a single word or a phrase and the idea is that once a story arc is identified we’ll search over the corpus and find the episodes where that phrase occurs.

We can then generate a CSV file of (story arc) -> (episodeId), store that into our HIMYM graph and use the story arc as another factor for episode similarity.

I ended up with the following script to work out which episodes contained a story arc:

#!/bin/bash
 
find_term() {
  arc=${1}
  searchTerm=${2}
  episodes=$(grep --color -iE "${searchTerm}" data/import/sentences.csv | awk -F"," '{ print $2  }' | sort | uniq)
  for episode in ${episodes}; do
    echo ${arc},${episode}
  done
}
 
find_term "Bro Code" "bro code"
find_term "Legendary" "legen(.*)ary"
find_term "Slutty Pumpkin" "slutty pumpkin"
find_term "Magician's Code" "magician's code"
find_term "Thanksgiving" "thanksgiving"
find_term "The Playbook" "playbook"
find_term "Slap Bet" "slap bet"
find_term "Wrestlers and Robots" "wrestlers"
find_term "Robin Sparkles" "sparkles"
find_term "Blue French Horn" "blue french horn"
find_term "Olive Theory" "olive"
find_term "Thank You Linus" "thank you, linus"
find_term "Have you met...?" "have you met"
find_term "Laser Tag" "laser tag"
find_term "Goliath National Bank" "goliath national bank"
find_term "Challenge Accepted" "challenge accepted"
find_term "Best Man" "best man"

If we run this script we’ll see something like the following:

$ ./scripts/arcs.sh
Bro Code,14
Bro Code,155
Bro Code,170
Bro Code,188
Bro Code,201
Bro Code,61
Bro Code,64
Legendary,117
Legendary,120
Legendary,122
Legendary,136
Legendary,137
Legendary,15
Legendary,152
Legendary,157
Legendary,162
Legendary,171
...
Best Man,208
Best Man,30
Best Man,32
Best Man,41
Best Man,42

I pulled out these themes by eyeballing the output of the following scripts:

  • TF/IDF – calculates TF/IDF scores for ngrams. This helps find important themes in the context of a single episode. I then did some manual searching to see how many of those themes existed in other episodes
  • Weighted Term Frequency – this returns a weighted term frequency for ngrams of different lengths. The weights are determined by the skewed random discrete distribution I wrote about earlier in the week. I ran it with different skews and ngram lengths.
  • Named entity extraction – this pulls out any phrases that are named entities. It mostly pulled out names of people (which I used as a stop word list in some other algorithms) but also revealed a couple of themes.
  • Topic modelling – I used mallet to extract topics across the corpus. Most of them didn’t make much sense to me but there were a few which identified themes that I recognised.

I can’t remember off the top of my head if any obvious themes have been missed so if you know HIMYM better than me let me know and I’ll try and work out why those didn’t surface.

Next I want to see how these scripts fare against some other TV shows and see how quickly I can extract themes for those. It’d also be cool if I can make the whole process a bit more automated.

Categories: Programming

String and StringBuilder revisited

Phil Trelford's Array - Fri, 04/03/2015 - 00:03

I came across a topical .Net article by Dave M Bush published towards the tail end of 2014 entitled String and StringBuilder where he correctly asserts that .Net’s built-in string type are reference types and immutable. All good so far.

The next assertion is that StringBuilder will be faster than simple string concatenation when adding more than 3 strings together, which is probably a pretty good guess, but lets put it to the test with 4 strings.

The test can be performed easily using F# interactive (built-in to Visual Studio) with the #time directive:

open System.Text

#time

let a = "abc"
let b = "efg"
let c = "hij"
let d = "klm"

for i = 1 to 1000000 do
   let e = StringBuilder(a)
   let f = e.Append(b).Append(c).Append(d).ToString() 
   ()
// Real: 00:00:00.317, CPU: 00:00:00.343, GC gen0: 101, gen1: 0, gen2: 0
   
for i = 1 to 1000000 do
   let e = System.String.Concat(a,b,c,d)
   ()
// Real: 00:00:00.148, CPU: 00:00:00.156, GC gen0: 36, gen1: 0, gen2: 0

What we actually see is that for concatenating 4 strings StringBuilder takes twice as long as using String.Concat (on this run 0.317ms vs 0.148ms) and generates approximately 3 times as much garbage (gen0: 101 vs gen0: 36)!

Underneath the hood the StringBuilder is creating an array to append the strings into. When appending if the current buffer length is exceeded (the default is 16) then a new array must be created. When ToString is called it may, based on a heuristic, decide to return the builder’s array or allocate a new array and copy the value into that. Therefore the performance of StringBuilder is dependent on the initial capacity of the builder and the number and lengths of the strings to append.

In contrast, String.Concat (which the compiler resolves the ‘+’ operator to) calculates the length of the concatenated string from the lengths of the passed in strings, then allocates a string of the required size and copies the values in, ergo, in many scenarios it will require less copying and less allocation.

When concatenating 2, 3 or 4 strings we can take advantage of String.Concat’s optimized overloads, after this the picture changes as an array argument must be passed which requires an additional allocation. However String.Concat may still be faster than StringBuilder in some scenarios where the builder requires multiple reallocations.

But wait there’s more, going back to the ‘+’ operator, if we assign the integer literal expression 1 + 2 + 3 the compiler can reduce the value to 6, equally if we define the strings as const string then the compiler can apply the string concatenations at compile time leading to, in this contrived example, no cost whatsoever.

The moral of the story is when it comes to performance optimization - measure, measure, measure.

Categories: Programming

FlatBuffers 1.1: a memory-efficient serialization library

Google Code Blog - Thu, 04/02/2015 - 17:51

Posted by Wouter van Oortmerssen, Fun Propulsion Labs at Google*

Originally posted to the Google Open Source blog

After months in development, the FlatBuffers 1.1 update is here. Originally released in June 2014, it’s a highly efficient open source cross-platform serialization library that allows you to read data without parsing/unpacking or allocating additional memory. It supports schema evolution (forwards/backwards compatibility) and optional JSON conversion. We primarily created it for games written in C++ where performance is critical, but it’s also useful more broadly. This update brings:

  • an extensive overhaul to the Java API
  • out-of-the-box support for C# and Go
  • an optional verifier to make FlatBuffers practical in untrusted scenarios
  • .proto parsing for easier migration from Protocol Buffers
  • optional manual assignment of field IDs
  • dictionary functionality through binary search on a key field
  • bug fixes and other improvements thanks to 200+ commits from 28 contributors -- thank you!

Download the latest release from our github page and join our discussion list for more details.

*Fun Propulsion Labs is a team within Google that's dedicated to advancing gaming on Android and other platforms.

Categories: Programming

Is It OK For New Programmers To Blog About What They Are Learning?

Making the Complex Simple - John Sonmez - Thu, 04/02/2015 - 15:00

In this video, I respond to an email from someone who asks for advice as to whether or not they should blog about what they are learning despite being a beginner programmer.

The post Is It OK For New Programmers To Blog About What They Are Learning? appeared first on Simple Programmer.

Categories: Programming

Animate constraints with a simple UIView extension in Swift

Xebia Blog - Wed, 04/01/2015 - 22:01

iOS Developers that are getting started with Auto Layout for the first time often run in trouble once they try to animate their views. The solution is quite simple, but in this post I'll create a simple Swift extension that makes it even easier.

When you don't use Auto Layout, you need to make the changes to your UIView frames inside an animations block. Those changes will then be animated. So without knowing any better, you would do the same for your Auto Layout constraints, which means changing the constraint constants inside the animations block. This doesn't work however, and a quick google search on "how to animate constraints" shows that your need only need to call view.layoutIfNeeded within the animations block after you've made the changes to the constraints.

A simple example of this:

heightConstraint.constant = 100
UIView.animateWithDuration(0.5, animations: { [weak self] in
  self?.view.layoutIfNeeded() ?? ()
})

it's necessary to call it this wat since updating constants of constraints doesn't immediately change the frames of the views affected by those constraints. That's why we need to call layoutIfNeeded, to update all the frames of our views.

Since we just want to be always safe with memory management we'll use a weak reference of self within the closure, even though we know the closure is not retained after the animation runs and the view will not be deallocated before the animation finishes (it's good practice to use weak whenever you can to avoid memory related problems).

The above sample is not a lot of code, but each time you want to animate something with constraints you need to write the same thing. Wouldn't it be much easier to write the following instead?

heightConstraint.constant = 100
view.animateConstraintWithDuration()

We can achieve that by adding an extension to UIView:

extension UIView {
  func animateConstraintWithDuration(duration: NSTimeInterval = 0.5) {
    UIView.animateWithDuration(duration, animations: { [weak self] in
      self?.layoutIfNeeded() ?? ()
    })
  }
}

Default values for the method parameters makes this even nicer. Above we used 0.5 as default duration but of course you can fill in duration you want when calling the method. Also we can add parameters with default values for the other parameters that animateWithDuration has.

The final extension
extension UIView {
  func animateConstraintWithDuration(duration: NSTimeInterval = 0.5, delay: NSTimeInterval = 0.0, options: UIViewAnimationOptions = nil, completion: ((Bool) -> Void)? = nil) {
    UIView.animateWithDuration(duration, delay:delay, options:options, animations: { [weak self] in
      self?.layoutIfNeeded() ?? ()
    }, completion: completion)
  }
}

There we have it. An extremely simple extension method that not only saves us a little bit of code each time we need to animate constraints but is also makes the code a lot cleaner since the name of the method clearly indicates what it does, as apposed to the layoutIfNeeded method within an animations block.

Episode 224: Sven Johann and Eberhard Wolff on Technical Debt

In this episode, Sven Johann and Eberhard Wolff talk about technical debt and how to handle it. They begin by defining external and internal quality and then talk about technical debt as a metaphor for discussing quality with management. They then consider whether technical debt is bad and how to handle it by using Eric […]
Categories: Programming