Skip to content

Instantly share code, notes, and snippets.

@killerstorm
Created September 27, 2012 13:05
Show Gist options
  • Save killerstorm/3793879 to your computer and use it in GitHub Desktop.
Save killerstorm/3793879 to your computer and use it in GitHub Desktop.
coin coloring pseudo-code
// we have three state variables, let's initialize them:
cur_amount = 0; // current amount of inputs
cur_color = COLOR_UNKNOWN; // color of those inputs
ii = inputs.begin(); // inputs iterator
oi = outputs.begin(); //output iterator
for (; oi != outputs.end(); ++oi) { // go through all outputs
want_amount = oi->amount; // amount of output we're matching
// eat inputs if needed
while ((cur_amount < want_amount) // do we need more?
&&
(ii != inputs.end())) // have we reached the end?
{ // eat input pointed to by iterator
if (cur_amount == 0) // brand new color stripe
cur_color = ii->color;
else if (cur_color != ii->color)
// if we already have some, we need to check whether
// coins are of same color. if they are not, they are
// mixed
cur_color = COLOR_MIXED;
cur_amount += ii->amount; // add to out amount
++ii; // and go to next input
}
if (cur_amount < want_amount)
// we could not get enough from inputs
// transaction is invalid if sum(inputs) > sum(outputs)
return false;
oi->color = cur_color; // assign color to output
cur_amount -= oi->amount; // decrease current amount by sum we've used
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment