Thursday, 9 January 2014

Coke Competition Math

Long time no post!

I recently had a Coke Zero and noticed that they had a competition on ( :
Check under specially marked labels on 'Coca-Cola', 'Coca-Cola Zero' and 'Diet Coca-Cola' 600mL bottles to see if you are a winner of $20, $50 or $100.
There is $200k in prizes to be won, so I asked myself: how many of each price is there?

x = number of $20 prizes
y = number of $50 prizes
z = number of $100 prizes
so 20x + 50y + 100z = 200,000
update: I forgot to mention that there are 4,600 prizes, so x + y + z = 4600

With some headscratching I rejigged the problem to:

 x = 5n
y = 8(650-n)
z = 3(n-200)
200 <= n &<= 650 if we want positive results

I then explored that range with excel to see what my best guess is for the distribution of cash:

$20 $50 $100 n
1000 3600 0 200
2000 2000 600 400 Min where x <= y <= z
2005 1992 603 401 Min where x < y < z
2375 1400 825 475 Nearly equal ratios (~1.7/1)
2500 1200 900 500 Nice round numbers
2635 984 981 527 Max where x > y > z

So there we have it, my best guess is the round numbers (though even ratios is nice):

2500 x $20 + 1200 x $50 + 900 x $100 = $200k

update: I found on the answer (n = 300), which wasn't on the label:
 The instant win prizes available to be won (the Cash Prizes) are:

  • (a) 1,500 x cash prizes valued at $20 each;
  • (b) 2,800 x cash prizes valued at $50 each; and
  • (c) 300 x cash prizes valued at $100 each.

Surprising that there is more $50s than $20s.

Wednesday, 16 November 2011


Apparently, posting blogs is totally last year. Either that or I have been busy/slack (take your pick).

Monday, 22 March 2010

Infix search using a Trie data structure

I am authoring a jQuery plugin to enhance drop down selects; UFD: The Unobtrusive Fast-filter Drop-down. Try it out easily on your own app with the bookmarklet. Be amazed. Show your friends.

One of the important requirements was filtering of the the drop down options from the input. The naive way to do this is a linear search through each list item, but this is way too slow for large lists; the list needs to be re-filtered after every keystroke.

I decided on a Trie implementation, which gives great prefix search performance. A Trie stores objects on a tree, constructed by slicing the key-string for each object into characters. Starting at the root, each character maps to a node - see the incoming vertex in the diagram below.

Each node has a map of character to child nodes, and an optional target object. Target objects are placed where the chain of characters maps to the objects key, so you can easily traverse the nodes with a key-string to find a given the target object. The structure is a tree, but the path to a given object is similar to a linked list of each character in the key string.

trie example

The blue nodes are ones that have objects on them - in this example we see the words: to,tea,ted,ten,it,int,into. Notice how objects are on the leaf nodes, unless their key is a substring of another key.

It is easy to see how we can do quick prefix searching:start at the root node (which represents the empty string) and traverse the nodes, consuming each character of the key prefix string. Once the prefix key string is consumed, that subtree has all the matches of the given key prefix.

But what if we want to find all nodes that have a given key infix? After failing to find a better data structure, I decided to hack an extension to the data structure.

Is there a better data structure that I should be using? Suggestions welcome. Anyway:

Instead of starting at the root node, we need an array of start points. During creation I put a reference to each new node in a list. There is one list for every unique character across the whole key set. This means that each list has references to all nodes of that character. These lists of start points are called the infixRoots.

Yes, some of these lists could be quite large. For example, the "e" list for a 1000-item list may have over 1000 items.

Lets look at a filtering example: lets search for the objects that match the infix key "to".

trie example: t

We start by getting the infix list matching the start character ("t") from the infixRoots set. The highlighted nodes and all of their child nodes, by definition, have "t" in their key - no surprises there.

trie example: to

We next iterate over the that list of "t" nodes, creating a new list with child nodes that match the next character; "o". Any node without a match is not added to the new list. We keep iteratively mapping node lists from one character to the next, until we consume the infix keys' characters.

The nodes left in the final set, and all of their child nodes, all are matches. Iterate over each subtree and get the attached objects. In our example above, the nodes representing to,into are found. Had the key top been in the tree, it would also match, as it would be a child of to.

Have a look at the javascript implementation for UFD, the InfixTrie is a self-contained prototype inside the source near the bottom.

Tuesday, 2 March 2010

At last: a proper multi booting OSX/Win7/Linux box lives!

I have nutted out the final few problems with my multi-boot drama.
  • (hd0): MBR - grub2, win7, Liunx
  • (hd1): dataz
  • (hd2): bootable OSX 10.6 with GPT partition, Chameleon booter etc.
I can point my bios to hd2 and OSX boots, but it took ages to get grub2 to boot my OSX disc (hd2).  Ended up being real simple; in /etc/grub.d/40_custom :

menuentry "Mac OSX" {
  set root=(hd2)
  chainloader +1

and then a sudo update-grub

Yay, it boots.  My second major drama was with macFUSE and fuse-ext2; it doesn't work with the 64-bit kernel.  Here is the console output:

toolmans-Mac-Pro:Volumes toolman$ sudo fuse-ext2 /dev/disk2s1 /Volumes/Untitled\ 30
fuse-ext2: version:'0.0.7', fuse_version:'27' [main (../../fuse-ext2/fuse-ext2.c:324)]
fuse-ext2: enter [do_probe (../../fuse-ext2/do_probe.c:30)]
fuse-ext2: leave [do_probe (../../fuse-ext2/do_probe.c:55)]
Mounting /dev/disk2s1 Read-Only.
Use 'force' or 'rw+' options to enable Read-Write mode
fuse-ext2: opts.device: /dev/disk2s1 [main (../../fuse-ext2/fuse-ext2.c:351)]
fuse-ext2: opts.mnt_point: /Volumes/Untitled 30 [main (../../fuse-ext2/fuse-ext2.c:352)]
fuse-ext2: opts.volname:  [main (../../fuse-ext2/fuse-ext2.c:353)]
fuse-ext2: opts.options: (null) [main (../../fuse-ext2/fuse-ext2.c:354)]
fuse-ext2: parsed_options: allow_other,local,noappledouble,ro,fsname=/dev/disk2s1,fstypename=ext2,volname=disk2s1 [main (../../fuse-ext2/fuse-ext2.c:355)]
fuse-ext2: mounting read-only [main (../../fuse-ext2/fuse-ext2.c:371)]
/Library/Filesystems/fusefs.fs/Support/fusefs.kext failed to load - (libkern/kext) link error; check the system/kernel logs for errors or try kextutil(8).
the MacFUSE file system is not available (71)
toolmans-Mac-Pro:Volumes toolman$

The highlighted line is the clincher; the 32-bit kext won't work with 64 bit kernel.  thankfully, I can run 64 bit apps on the 32-bit kernel anyway :)

It took me ages to figure out that chameleon uses


not the default kernel boot file !


By editing the correct file, and updating the kernel flags

Kernel Flags

And now I have grub2 booting to any OS I want, with my ext3 mounting in all OSes :D

Saturday, 12 December 2009

Annoying iE6 bug of the day:

If you add a border on any edge of a < button ..> element, iE6 adds a second, inner border/padding, making your background image offset and the background color to show through! 

This link describes it and a few side step options:

For my purposes, the easiset thing to do was not have a border, and have the parent supply a pseudo border using the background color.  If you find a way to stop iE6 doing this, please let me know!

Wednesday, 28 October 2009


So I decided to get a Freeview decoder, and I ended getting a HD (== terrestrial not satellite) decoder even though I don't yet have a HD TV. I got this YESS DVB-T9900HD is a single tuner unit with a HDMI port and the promise of PVR functionality via the USB port.

It looks a little ghetto with a USB port at the front, but I care not for asthetics anyway. Anyone who remembers my milk crate constructions can attest to that...

The freeview signal is super strong where I am in west AK, and it gets a glitchy signal with no aerial at all. My UHF aerial is well aligned so it gives 100% signal, and the programme guide comes through fine.

was skeptical that the PVR functionality of the unit would work via the USB port, but it does. Unfortunately, the PVR integration is basic and lacks in a number of areas. But its ok; you can pause and rewind TV, schedule and record TV as advertised.

I'm real happy for the price of the unit, but here is the laundry list of what is a bit shit about this unit for anyone else looking for an uber cheap PVR:

  • No integration between freeview EPG listings and the recording feature! I hope other units can do this? Scheduling a recording is like setting a VHS; this channel from then till then, click.
  • Single tuner means it can only buffer the channel you are watching. This is obvious, but a good PVR needs 2+ tuners.
  • I haven't checked, but I expect that the recording is in standard definition irrespective of the HD-ness. I haven't confirmed this one, anyone want to give me a HD screen? Actually I havent even checked the HD signal is HD when "realtime"!
  • Seems to use the disk regularly, not a great buffering technique. For this reason, I don't leave the PVR live buffering 24/7. Use of flash or solid state might dodge that bullet.
  • Seems to not like playing too close to realtime, needs 5+ second buffer, else it glitches and drops audio.

So the PVR is basically like a VHS, except you can do poor-mans timeshifting: start watching the recording before its finished.

Saturday, 17 October 2009

The problem of evil:

Reading a great essay on: The problem of Evil. Here is a quote from it:

Assumption (1): God exists.
Assumption (1a): God is all-knowing.
Assumption (1b): God is all-powerful.
Assumption (1c): God is perfectly loving.
Assumption (1d): Any being that did not possess all three of the above properties would not be God.
Premise (2): Evil exists.
Premise (3): An all-knowing being would be aware of the existence of evil.
Premise (4): An all-powerful being would be able to eliminate evil.
Premise (5): A perfectly loving being would desire to eliminate evil.
Conclusion (6): Evil does not exist. (from (1),(3),(4),(5))
Contradiction: But evil does exist. (from (2))
Conclusion (7): There is no being that is all-knowing, all-powerful, and perfectly loving. (from (2),(3),(4),(5))
Conclusion (8): God does not exist. (from (7),(1d))

The argument's logic is ironclad, and its simple but far-reaching conclusion is that the existence of evil in the world disproves the existence of an omniscient, omnipotent, perfectly loving god. The only way to refute the problem of evil without surrendering the assumption that such a god exists is to deny one of its premises.

I like this argument as it doesn't completely deny God; but it relegates him to (in my view):
  • A God that isn't Perfectly Loving; or
  • A God that doesn't desire to eliminate evil.
To remove any of the other attributes of God is unacceptable (all-knowing, all-powerful), so he must either not exist, or be a bit of a bastard. So lets talk about your beliefs in bastard Gods only - the benevolent ones seem unlikely.