### 2010 Code Jam problem: "Store Credit"

A fellow on the haskell-beginners mailing list asked for suggestions on how to improve code he'd written to solve a 2010 Code Jam qualifying problem, "Store Credit". Here's the problem statement:

and the solution "4 5". At first one would--well,

Clearly you want to keep around two items, or for a functional version, you want to generate two items as you trudge down the list of prices:

It's pretty clear how to implement this in an imperative language. We'll see what I come up with for a Haskell version.

"You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first)."Then the format of the input is described, and among the things we learn are:

- The prices are all integers.
- "Each test case will have exactly one solution."

`2 1 9 4 4 56 90 3`

and the solution "4 5". At first one would--well,

*I*did--think that violates the promise of only one solution, since two of item 4 or two of item 5 would also add up to the credit amount of 8. I would say that the problem statement is at least a little misleading, and should have said "...would like to buy two*different*items that add up to the entire value of the credit." It's arguably implied by the parenthetical "(smaller number first)", and perhaps the intent is to show the need to read specs carefully.Clearly you want to keep around two items, or for a functional version, you want to generate two items as you trudge down the list of prices:

- an array or vector of integers with C/2 elements
- a mapping that, given a price, returns the position (or positions, given the one example) of the items with that price

It's pretty clear how to implement this in an imperative language. We'll see what I come up with for a Haskell version.

## Comments