So, yeah, I’m writing on this blog again. Hi. Very little chance anyone is reading but I am once again using this to share… stuff. It’s just me now, but if you are for some reason looking through the archives, first, find something better to read, but second, check the author’s name before sending me an angry email about how stupid my blog post was. It might not be me. Probably is, but maybe not.

I’m a software engineer by trade so I like to write code, solve puzzles, that kind of thing. I’ll be (occasionally?) posting interesting programming puzzles and my approach to them so that other engineers can point and laugh.

The reason for this post is Riddler by 538. Each week they post a puzzle and people submit answers and then they tell the answer on the following Sunday. I just discovered it and this was the first puzzle I’ve attempted to solve. They won’t post the answer until tomorrow so I’m not sure if I am right. I think I’m wrong actually.

Here’s the problem:

You go to buy a specific car, whose fair price we’ll call

N. You have absolutely no idea whatNis and the dealer, sadistic capitalist that he is, won’t tell you. The dealer enjoys a good chase, though, so without directly revealing the value ofN, he takes five index cards and writes down a number on each of them:N,N+100,N+200,N+300 andN+400. Important: the guy’s sadistic but not a math major. The numbers on the cards arenumbers, not algebra equations.He presents the cards to you, one at a time, in random order. (For example, if the price on the second card is $100 more than the first, you can’t be sure if those are the two smallest prices, the two largest, or somewhere in between.) Each time he shows you a card, you must either pay the price on that card, or ask to see the next card. You cannot go back to previous cards. If you make it to the fifth and final card, then that is what you must pay. If you play the dealer’s game optimally,

how much should you expect to payon average above the fair priceN?

Aside from declaring that you wouldn’t buy a car from this dealer (h/t Kevin H.) how do you go about answering this question? I’ve actually submitted 3 answers (so far!) and I’m not very confident about my current one. Here’s the first (definitely wrong) answer:

My strategy is to take the first price that is lower than the first price offered. So if the first price is the lowest offered, I will end up paying last price, which will be the max price a total of 5% of the time.

20% chance 1st number is best price and I pay last price

25% I pay N + 100 = 25

25% I pay N + 200 = 50

25% I pay N + 300 = 75

25% I pay N + 400 = 100

20% * 250 = 50

20% chance 1st number is 2nd best price I pay min * N = 0

20% chance 1st number is 3rd best price.

50% I will pay min

50% I will pay N + 100 = 50.

20% * 50 = 10

20% chance 1st number is 4th best price.

33% I will pay min

33% I will N + 100 = 33

33% I will pay N + 200 = 66

100 * 20% = 20

20% chance 1st number is 5th best price.

25% I will pay min

25% I will pay N + 100 = 25

25% I will pay N + 200 = 50

25% I will pay N + 300 = 75

150 * 20% = 3050 + 0 + 10 + 20 + 30 = $

110.

So, $110 is my answer. Seems reasonable, and I think that’s what most people would intuitively come up with, but it’s wrong. Here’s why: it doesn’t use any of the information we have seen except that first price. By only looking for a price that is lower than the first price we miss out on opportunities to take a better current price than what we must take at the end.

For example, let’s say the true cost of the car is $5000, and the first price offered is $5000. Then I look at the second price and it’s $5400. Ugh! I should have taken the first one, but oh well, I can’t. But using that method above, what price would I end up with? Well, it depends on the distribution of the remaining three prices. Since none will be lower than $5000, I will take whatever the last one is, which could be $5300. But I KNOW that $5100 is out there.

With that in mind, I wrote some code (C++) to find a better solution. This code uses the Standard Template Library to get all the permutations of the price cards. That’s 5-factorial (5!) or 120 possibilities. The basic strategy here is to build a list of possible outcomes based on what I’ve seen so far, calculate an EV (expected value) for the remaining cards, compare it to my current offered price, and then decide whether to take the current price or see another card.

If the first price I see is $5000, then the remaining possible prices are $4600, $4700, $4800, $4900, $5100, $5200, $5300, and $5400. Let’s say we see another card and it is $5200. Now the remaining possible prices are $4800, $4900, **$5100**, $5300, and $5400. Notice that I’ve bolded $5100 here. That’s because I KNOW that $5100 is guaranteed to be in my list of prices. I can safely see another price knowing that there’s definitely a better price than my current $5200.

Here’s the code for any C++ people:

// CarDealer20160110.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <algorithm> #define PRICE_COUNT 5 #define PRICE_INC 100.f #define MAX_PRICE_DIFF ((PRICE_COUNT - 1) * PRICE_INC) #define min(a,b) (((a) < (b)) ? (a) : (b)) #define max(a,b) (((a) > (b)) ? (a) : (b)) bool HasBeenSeen(const float *seen, int seenCount, float val) { // we could rewrite this as a set or something if PRICE_COUNT gets large for(int i = 0; i < seenCount; i++) if(seen[i] == val) return true; return false; } void PossibleRemainingPrices(const float *seen, int seenCount, float *remaining, int &remainCount, float *guaranteed, int &guaranteeCount) { float loSeen = *seen; float hiSeen = *seen; for(int i = 1; i < seenCount; i++) { loSeen = min(loSeen, seen[i]); hiSeen = max(hiSeen, seen[i]); } float minRem = hiSeen - MAX_PRICE_DIFF; float maxRem = loSeen + MAX_PRICE_DIFF; remainCount = 0; guaranteeCount = 0; for(float val = minRem; val <= maxRem; val += PRICE_INC) { if(!HasBeenSeen(seen, seenCount, val)) { remaining[remainCount] = val; remainCount++; if(val > loSeen && val < hiSeen) { guaranteed[guaranteeCount] = val; guaranteeCount++; } } } } float AverageFloatArray(const float *values, int count) { if(count == 0) return 0; float total = 0; for(int i = 0; i < count; i++) total += values[i]; return total / (float)count; } float GetBestPrice(const float *prices, int count) { float remainingPoss[PRICE_COUNT * 2] = {}; int remCount = 0; float guaranteed[PRICE_COUNT] = {}; int gCount = 0; // we automatically look at first 2 float currentPrice = prices[0]; int seenCount = 1; while(seenCount < PRICE_COUNT) { currentPrice = prices[seenCount]; seenCount++; PossibleRemainingPrices(prices, seenCount, remainingPoss, remCount, guaranteed, gCount); // simplest case if(remainingPoss[0] > currentPrice) return currentPrice; float ev = AverageFloatArray(remainingPoss, remCount); if(gCount == 0) { // average remaining possibles and compare to current if(currentPrice < ev) return currentPrice; } else { float minG = guaranteed[0]; float maxG = guaranteed[gCount - 1]; if(minG > currentPrice && ev > currentPrice) return currentPrice; } } return currentPrice; } float AveragePrice() { float prices[PRICE_COUNT]; for(int i = 0; i < PRICE_COUNT; i++) { prices[i] = (i * PRICE_INC); } float fTotalPricePaid = 0; int nTrials = 0; do { for(int i = 0; i < PRICE_COUNT; i++) { printf("%.0f ", prices[i]); } float pricePaid = GetBestPrice(prices, PRICE_COUNT); printf(" - Price paid = %.0f\n", pricePaid); fTotalPricePaid += pricePaid; nTrials++; } while(std::next_permutation(prices, prices + PRICE_COUNT)); float fAvgPrice = fTotalPricePaid / (float)nTrials; printf("Avg Price paid = %.4f\n", fAvgPrice); return fAvgPrice; } int _tmain(int argc, _TCHAR* argv[]) { AveragePrice(); return 0; }

Running this code for all 120 permutations gives this output:

0 100 200 300 400 – Price paid = 400

0 100 200 400 300 – Price paid = 300

0 100 300 200 400 – Price paid = 400

0 100 300 400 200 – Price paid = 200

0 100 400 200 300 – Price paid = 200

0 100 400 300 200 – Price paid = 200

0 200 100 300 400 – Price paid = 400

0 200 100 400 300 – Price paid = 300

0 200 300 100 400 – Price paid = 100

0 200 300 400 100 – Price paid = 100

0 200 400 100 300 – Price paid = 100

0 200 400 300 100 – Price paid = 100

0 300 100 200 400 – Price paid = 100

0 300 100 400 200 – Price paid = 100

0 300 200 100 400 – Price paid = 100

0 300 200 400 100 – Price paid = 100

0 300 400 100 200 – Price paid = 100

0 300 400 200 100 – Price paid = 100

0 400 100 200 300 – Price paid = 100

0 400 100 300 200 – Price paid = 100

0 400 200 100 300 – Price paid = 100

0 400 200 300 100 – Price paid = 100

0 400 300 100 200 – Price paid = 100

0 400 300 200 100 – Price paid = 100

100 0 200 300 400 – Price paid = 0

100 0 200 400 300 – Price paid = 0

100 0 300 200 400 – Price paid = 0

100 0 300 400 200 – Price paid = 0

100 0 400 200 300 – Price paid = 0

100 0 400 300 200 – Price paid = 0

100 200 0 300 400 – Price paid = 0

100 200 0 400 300 – Price paid = 0

100 200 300 0 400 – Price paid = 0

100 200 300 400 0 – Price paid = 0

100 200 400 0 300 – Price paid = 0

100 200 400 300 0 – Price paid = 0

100 300 0 200 400 – Price paid = 0

100 300 0 400 200 – Price paid = 0

100 300 200 0 400 – Price paid = 0

100 300 200 400 0 – Price paid = 0

100 300 400 0 200 – Price paid = 0

100 300 400 200 0 – Price paid = 200

100 400 0 200 300 – Price paid = 0

100 400 0 300 200 – Price paid = 0

100 400 200 0 300 – Price paid = 200

100 400 200 300 0 – Price paid = 200

100 400 300 0 200 – Price paid = 0

100 400 300 200 0 – Price paid = 200

200 0 100 300 400 – Price paid = 0

200 0 100 400 300 – Price paid = 0

200 0 300 100 400 – Price paid = 0

200 0 300 400 100 – Price paid = 0

200 0 400 100 300 – Price paid = 0

200 0 400 300 100 – Price paid = 0

200 100 0 300 400 – Price paid = 100

200 100 0 400 300 – Price paid = 100

200 100 300 0 400 – Price paid = 100

200 100 300 400 0 – Price paid = 100

200 100 400 0 300 – Price paid = 100

200 100 400 300 0 – Price paid = 100

200 300 0 100 400 – Price paid = 0

200 300 0 400 100 – Price paid = 0

200 300 100 0 400 – Price paid = 100

200 300 100 400 0 – Price paid = 100

200 300 400 0 100 – Price paid = 0

200 300 400 100 0 – Price paid = 100

200 400 0 100 300 – Price paid = 0

200 400 0 300 100 – Price paid = 0

200 400 100 0 300 – Price paid = 100

200 400 100 300 0 – Price paid = 100

200 400 300 0 100 – Price paid = 0

200 400 300 100 0 – Price paid = 100

300 0 100 200 400 – Price paid = 0

300 0 100 400 200 – Price paid = 0

300 0 200 100 400 – Price paid = 0

300 0 200 400 100 – Price paid = 0

300 0 400 100 200 – Price paid = 0

300 0 400 200 100 – Price paid = 0

300 100 0 200 400 – Price paid = 100

300 100 0 400 200 – Price paid = 100

300 100 200 0 400 – Price paid = 100

300 100 200 400 0 – Price paid = 100

300 100 400 0 200 – Price paid = 100

300 100 400 200 0 – Price paid = 100

300 200 0 100 400 – Price paid = 200

300 200 0 400 100 – Price paid = 200

300 200 100 0 400 – Price paid = 200

300 200 100 400 0 – Price paid = 200

300 200 400 0 100 – Price paid = 200

300 200 400 100 0 – Price paid = 200

300 400 0 100 200 – Price paid = 0

300 400 0 200 100 – Price paid = 0

300 400 100 0 200 – Price paid = 100

300 400 100 200 0 – Price paid = 100

300 400 200 0 100 – Price paid = 200

300 400 200 100 0 – Price paid = 200

400 0 100 200 300 – Price paid = 0

400 0 100 300 200 – Price paid = 0

400 0 200 100 300 – Price paid = 0

400 0 200 300 100 – Price paid = 0

400 0 300 100 200 – Price paid = 0

400 0 300 200 100 – Price paid = 0

400 100 0 200 300 – Price paid = 100

400 100 0 300 200 – Price paid = 100

400 100 200 0 300 – Price paid = 100

400 100 200 300 0 – Price paid = 100

400 100 300 0 200 – Price paid = 100

400 100 300 200 0 – Price paid = 100

400 200 0 100 300 – Price paid = 200

400 200 0 300 100 – Price paid = 200

400 200 100 0 300 – Price paid = 200

400 200 100 300 0 – Price paid = 200

400 200 300 0 100 – Price paid = 200

400 200 300 100 0 – Price paid = 200

400 300 0 100 200 – Price paid = 300

400 300 0 200 100 – Price paid = 300

400 300 100 0 200 – Price paid = 300

400 300 100 200 0 – Price paid = 300

400 300 200 0 100 – Price paid = 300

400 300 200 100 0 – Price paid = 300

Avg Price paid = 100.0000

So an answer of $100. A definite improvement! I quickly sent off another submission to 538. Sadly, after looking at the code, I realized: it’s also wrong.

The problem here is that I am making a bad assumption when I calculate the EV of the remaining possible values. I treat them all equally. But I know that if I have a range like {4700, 4800, 4900, 5200, 5300, 5400} and my current price is $5100 that I can probably guarantee that I can get $5200 as a worst-case. Maybe not, but probably. So instead of taking the average of those 6 values I modified the AverageFloatArray function to treat that array like this: {4700, 4800, 4900, 5200, 5200, 5200}. That small change allows us to take some more chances and occasionally get a better price.

Here’s that modified function:

float AverageFloatArray(const float *values, int count, float pivot) { if(count == 0) return 0;float total = 0; int used = 0; for(int i = 0; i < count; i++) { total += values[i]; used++;if(values[i] > pivot) { for(int j = i + 1; j < count; j++) total += values[i]; break; } } return total / (float)count; }

The “pivot” value is whatever my current price is. With that change to the algorithm, here’s the output:

0 100 200 300 400 – Price paid = 400

0 100 200 400 300 – Price paid = 300

0 100 300 200 400 – Price paid = 400

0 100 300 400 200 – Price paid = 200

0 100 400 200 300 – Price paid = 200

0 100 400 300 200 – Price paid = 200

0 200 100 300 400 – Price paid = 400

0 200 100 400 300 – Price paid = 300

0 200 300 100 400 – Price paid = 100

0 200 300 400 100 – Price paid = 100

0 200 400 100 300 – Price paid = 100

0 200 400 300 100 – Price paid = 100

0 300 100 200 400 – Price paid = 400

0 300 100 400 200 – Price paid = 200

0 300 200 100 400 – Price paid = 100

0 300 200 400 100 – Price paid = 100

0 300 400 100 200 – Price paid = 100

0 300 400 200 100 – Price paid = 100

0 400 100 200 300 – Price paid = 100

0 400 100 300 200 – Price paid = 100

0 400 200 100 300 – Price paid = 100

0 400 200 300 100 – Price paid = 100

0 400 300 100 200 – Price paid = 100

0 400 300 200 100 – Price paid = 100

100 0 200 300 400 – Price paid = 400

100 0 200 400 300 – Price paid = 300

100 0 300 200 400 – Price paid = 400

100 0 300 400 200 – Price paid = 200

100 0 400 200 300 – Price paid = 200

100 0 400 300 200 – Price paid = 200

100 200 0 300 400 – Price paid = 0

100 200 0 400 300 – Price paid = 0

100 200 300 0 400 – Price paid = 0

100 200 300 400 0 – Price paid = 0

100 200 400 0 300 – Price paid = 0

100 200 400 300 0 – Price paid = 0

100 300 0 200 400 – Price paid = 0

100 300 0 400 200 – Price paid = 0

100 300 200 0 400 – Price paid = 0

100 300 200 400 0 – Price paid = 0

100 300 400 0 200 – Price paid = 0

100 300 400 200 0 – Price paid = 200

100 400 0 200 300 – Price paid = 0

100 400 0 300 200 – Price paid = 0

100 400 200 0 300 – Price paid = 0

100 400 200 300 0 – Price paid = 0

100 400 300 0 200 – Price paid = 0

100 400 300 200 0 – Price paid = 200

200 0 100 300 400 – Price paid = 400

200 0 100 400 300 – Price paid = 300

200 0 300 100 400 – Price paid = 100

200 0 300 400 100 – Price paid = 100

200 0 400 100 300 – Price paid = 100

200 0 400 300 100 – Price paid = 100

200 100 0 300 400 – Price paid = 0

200 100 0 400 300 – Price paid = 0

200 100 300 0 400 – Price paid = 0

200 100 300 400 0 – Price paid = 0

200 100 400 0 300 – Price paid = 0

200 100 400 300 0 – Price paid = 0

200 300 0 100 400 – Price paid = 0

200 300 0 400 100 – Price paid = 0

200 300 100 0 400 – Price paid = 100

200 300 100 400 0 – Price paid = 100

200 300 400 0 100 – Price paid = 0

200 300 400 100 0 – Price paid = 100

200 400 0 100 300 – Price paid = 0

200 400 0 300 100 – Price paid = 0

200 400 100 0 300 – Price paid = 100

200 400 100 300 0 – Price paid = 100

200 400 300 0 100 – Price paid = 0

200 400 300 100 0 – Price paid = 100

300 0 100 200 400 – Price paid = 0

300 0 100 400 200 – Price paid = 0

300 0 200 100 400 – Price paid = 0

300 0 200 400 100 – Price paid = 0

300 0 400 100 200 – Price paid = 0

300 0 400 200 100 – Price paid = 0

300 100 0 200 400 – Price paid = 0

300 100 0 400 200 – Price paid = 0

300 100 200 0 400 – Price paid = 0

300 100 200 400 0 – Price paid = 0

300 100 400 0 200 – Price paid = 0

300 100 400 200 0 – Price paid = 200

300 200 0 100 400 – Price paid = 0

300 200 0 400 100 – Price paid = 0

300 200 100 0 400 – Price paid = 100

300 200 100 400 0 – Price paid = 100

300 200 400 0 100 – Price paid = 0

300 200 400 100 0 – Price paid = 100

300 400 0 100 200 – Price paid = 0

300 400 0 200 100 – Price paid = 0

300 400 100 0 200 – Price paid = 100

300 400 100 200 0 – Price paid = 100

300 400 200 0 100 – Price paid = 200

300 400 200 100 0 – Price paid = 200

400 0 100 200 300 – Price paid = 0

400 0 100 300 200 – Price paid = 0

400 0 200 100 300 – Price paid = 0

400 0 200 300 100 – Price paid = 0

400 0 300 100 200 – Price paid = 0

400 0 300 200 100 – Price paid = 0

400 100 0 200 300 – Price paid = 100

400 100 0 300 200 – Price paid = 100

400 100 200 0 300 – Price paid = 100

400 100 200 300 0 – Price paid = 100

400 100 300 0 200 – Price paid = 100

400 100 300 200 0 – Price paid = 100

400 200 0 100 300 – Price paid = 0

400 200 0 300 100 – Price paid = 0

400 200 100 0 300 – Price paid = 100

400 200 100 300 0 – Price paid = 100

400 200 300 0 100 – Price paid = 0

400 200 300 100 0 – Price paid = 100

400 300 0 100 200 – Price paid = 0

400 300 0 200 100 – Price paid = 0

400 300 100 0 200 – Price paid = 100

400 300 100 200 0 – Price paid = 100

400 300 200 0 100 – Price paid = 200

400 300 200 100 0 – Price paid = 200

Avg Price paid = 90.0000

So $90. Another improvement! Is that correct? I really doubt it! I sent it to 538 and we (we? lol, I) will find out tomorrow. I suspect that I need to rewrite the entire program to take a dynamic programming approach. Do the problem “backwards.” Build a set of possibilities that I’ve encountered with their outcomes and then use those to calculate more precise EV of situations.

It’s also possible that the 90 is the correct answer for 5 price cards but if we extended this to use 6+ price cards then my current algorithm would fail. That’s where the dynamic programming would help.

I’d work on it more, but I’ve got to take my kid to the batting cages and the answer will be published tomorrow. I really don’t think it will be much lower than 90, but it wouldn’t surprise me if it is 80 or something.

There. I blogged. See you in two years?

” If the first price I see is $5000, then the remaining possible prices are $4600, $4700, $4800, $4900, $5100, $5200, $5300, and $5400. Let’s say we see another card and it is $5200. Now the remaining possible prices are $4800, $4900, $5100, $5300, and $5400. Notice that I’ve bolded $5100 here. That’s because I KNOW that $5100 is guaranteed to be in my list of prices. ”

I was under the impression that the person playing the game was unaware of the possible prices, you simply are shown up to 5 cards with dollar values on them, so i don’t think you can make the assumption that you know 5100 is guaranteed.

The idea was to come up with an optimal strategy that will on average give you the lowest cost paid therefore you would play each game as if you have no prior information. If that’s correct then how could you build an EV with no information on the rest of the set? (this only matters if my understanding of the question was right)

Good question and hey, thanks for reading. So according to the way I read the problem the buyer doesn’t know the prices but he does know that the prices are N, N + 100, N + 200, N + 300, N + 400.

So since you know all the prices are increments of $100, if you see $5000 and $5200 you know that $5100 is one of the prices. N might be $4800 or N might be $5000 but either way, $5100 is on one of the three remaining cards.

Does that make sense? I could be wrong.

I came up with 90 as well (before stumbling across your blog), I *think* it’s correct. My method was to start from the outcome of all 120 permutations and work backwards by pattern. As an example, if the customer sees 4 sequentially increasing values X, X+100, X+200, X+300, then we know X=N or X=N+100. So by agreeing to pay X+300, the customer is paying either N+300 or N+400, so EV = N+350. If they flip the last card, they’ll see either X+400 (confirming N=X) or X-100 (confirming X=N+100), and those two options have an average outcome (EV) of N+200. So flipping the last card is the optimal choice, as it has a lower EV than stopping. Now we can assign the lower EV (N+200) to those two permutations with the shared opening pattern. If you repeat this logic for all 4 card patterns (and assign EVs), then you can do the same for all three card patterns (compare EV of stopping to continuing) and so on. You end up with an average outcome of N+90 across the 120 permutations.

Oh awesome. That’s exactly what I meant by dynamic programming. Thanks for posting. I hope we are right!

Ahh, I was assuming you didn’t know the interval and that all information was hidden and that the values N+1 etc. were just a way to calculate an average lowest cost for the problem. If you’re right, then my answer was way wrong :p

This is a very enjoyable write-up for me, as it directly mirrors the wrong turns I also took while programming the solution. In retrospect, of course, it all feels very “obvious”, but at the time, making assumptions about how the expected value of the remaining cards was their average seemed like the right thing to do.

Thanks very much for posting this. Also, if you’re interested in an N-card implementation, I can send you a Python one!