Solving the NP-complete problem in XKCD

Posted by Adam Tuttle on Stack Overflow See other posts from Stack Overflow or by Adam Tuttle
Published on 2008-09-26T20:30:38Z Indexed on 2012/07/08 3:16 UTC
Read the original article Hit count: 512

The problem/comic in question: http://xkcd.com/287/

General solutions get you a 50% tip

I'm not sure this is the best way to do it, but here's what I've come up with so far. I'm using CFML, but it should be readable by anyone.

<cffunction name="testCombo" returntype="boolean">
    <cfargument name="currentCombo" type="string" required="true" />
    <cfargument name="currentTotal" type="numeric" required="true" />
    <cfargument name="apps" type="array" required="true" />

    <cfset var a = 0 />
    <cfset var found = false />

    <cfloop from="1" to="#arrayLen(arguments.apps)#" index="a">
    	<cfset arguments.currentCombo = listAppend(arguments.currentCombo, arguments.apps[a].name) />
    	<cfset arguments.currentTotal = arguments.currentTotal + arguments.apps[a].cost />
    	<cfif arguments.currentTotal eq 15.05>
    		<!--- print current combo --->
    		<cfoutput><strong>#arguments.currentCombo# = 15.05</strong></cfoutput><br />
    		<cfreturn true />
    	<cfelseif arguments.currentTotal gt 15.05>
    		<cfoutput>#arguments.currentCombo# > 15.05 (aborting)</cfoutput><br />
    		<cfreturn false />
    	<cfelse>
    		<!--- less than 15.05 --->
    		<cfoutput>#arguments.currentCombo# < 15.05 (traversing)</cfoutput><br />
    		<cfset found = testCombo(arguments.currentCombo, arguments.currentTotal, arguments.apps) />
    	</cfif>
    </cfloop>
</cffunction>

<cfset mf = {name="Mixed Fruit", cost=2.15} />
<cfset ff = {name="French Fries", cost=2.75} />
<cfset ss = {name="side salad", cost=3.35} />
<cfset hw = {name="hot wings", cost=3.55} />
<cfset ms = {name="moz sticks", cost=4.20} />
<cfset sp = {name="sampler plate", cost=5.80} />
<cfset apps = [ mf, ff, ss, hw, ms, sp ] />

<cfloop from="1" to="6" index="b">
    <cfoutput>#testCombo(apps[b].name, apps[b].cost, apps)#</cfoutput>
</cfloop>

The above code tells me that the only combination that adds up to $15.05 is 7 orders of Mixed Fruit, and it takes 232 executions of my testCombo function to complete.

Is there a better algorithm to come to the correct solution? Did I come to the correct solution?

© Stack Overflow or respective owner

Related posts about language-agnostic

Related posts about np-complete