Hey, Ben.
Hey, Matt.
What's new?
Uh, well, I'm sick.
Oh, yeah. You've been, absent, absent from work the last few days with a head cold. Right? Not, not the dreaded lurge.
I have a cold. Yeah. No, I, I have, uh, it's funny actually, because yesterday I, I woke up early because I couldn't sleep cuz I was all, my brain was full of snot and, uh, I came down and I, you know, sat down at my desk here at my house and started working and like 14 hours later I was like, I should go to bed.
Oh my gosh. That.
and it was only because I was just super absorbed in work and kind of trying to distract myself from the fact that I was sick.
In a good way, I hope.
Yeah, it was, I mean, it's like, it's one of those things where, um, I really have to be cognizant of not getting too absorbed in what I'm doing because I know that I will burn myself out if I do that every day. But, um, yesterday it was actually kind of like good therapy. Uh, and I, I sort of like was thinking about, uh, you know, some of the folks at Twitter that are doing that not of their own free will these days.
Oh my gosh.
Um, yeah. And, uh, going like, you know, I have to, I have to be careful cause I, I don't want to
Talking of being careful. Now you and I, I don't wanna usually go out of our way not to mention anything that's particularly contemporary because we like to reorder our episodes as we see fit, and now we're exposed to having to release this one sooner rather than later, otherwise people will, well, that's assuming that by the time you're listening to this Twitter even still exists.
Yeah,
I do hope it does
I mean, you know,
It's survived a lot over the years.
That's true. We, I, we, we are not, that is not the topic for today.
That is not, today's topic
So the fact that has occurred will not be a surprise to our listener. However many...
I would like to point out that it is, I'm excited for you that you are as excited about what you're doing for your day job right now. That you can spend 14 hours straight and, and nash the self limit because you are otherwise burn yourself out in a good way because you choose to.
Yeah. Yeah.
So that's great news.
Yeah. And no that, and it's, it's been fun. They, the day job these days has been quite good, but anyway, that's not what we're talking about
That's not what we're talking about today. No. In fact, we as always have our carefully chosen 20 seconds before clicking record topic which is a surprising, difficult issue that came up in my little open source project. And I was surprised how difficult adding a particular feature was. And I was thinking to myself, this could be like a, one of those coding interview questions that you could give to somebody. And then I don't really like those at the best of days, but, you know, sometimes you have to come up with 'em. And then I thought, well, let's talk about it on a podcast because it's kind of an interesting problem. So the problem is this, let's suppose hypothetically you have a website and because you have very strong opinions about the amount of advertising or otherwise on your website, you want to strictly limit the number of little icons for your advertiser's stroke sponsors to some number.
So I only wanna show, say three icons are the top right hand corner of my website, because any more than that, and it drives me mad and I'm sure it drives my users mad. So that's the starting point. Then suppose you've got multiple sponsors and you have, uh, agreements with those sponsors that say, Hey, I need to show your icon at least one in every n page loads. And you know, those so far you, you have three sponsors and three slots. And so the algorithm has been hard code the three icons into the top of the page and get on with your life. So that's a pretty good algorithm so far. But then imagine a fourth sponsor comes along and you realize suddenly you have to make a runtime determination about which sponsors to show when so that you can hand on heart, go to each sponsor and say, Hey, your icon is being showed this many times and I have metrics to track that so I can actually show people this.
Right. And because the easy route would just be to randomly show them and then hope the law of large numbers comes along to your side and just make sure manually that there is no, uh, there's no, like, it's not impossible for you to show the requisite number of time, uh, of sponsors per time. You know, that that's not fun. I'd like to come up with an algorithm which can provably show that I can get every single sponsor shown and that there will be no issue or it will throw an exception and say, Nope, you've oversold everything. You can't keep everybody happy now and you might have to go to four icons. So that was the problem I was facing and I sat down and I wrote something and it turned out to be substantially more difficult than I thought it should be.
So just to clarify here, this is the promise that you've made to your sponsors
That's correct.
Is that you, you will show their little icon, their image, um, some percentage of the page page loads.
That's correct. Yeah.
So just sort of like thinking of this at, at first pass, like, and you sort of alluded to this, like, it is possible that for more sponsors than three, you, you, you've actually over-committed. Right?
If for example, I said to each sponsor a hundred percent and I had four sponsors and three slots, it's trivial. Well, I can't satisfy that. Right? There's no sequence of, of shift shifting them around that that makes it fair to all my sponsors because they'll all be less than a hundred percent.
Right. Right. OK interesting.
But if I have four and each one is 30% of the time, then obviously it's pretty trivial to just keep cycling them around and, you know, shifting, literally shifting them along, you know, show 1, 2, 3, 2, 3, 4, 3, 4, 1, 4, 1, 2 blah. There you are. They'll get shown a lot more than one in three and that's great. So that's a good solution. And as a human, you'd sit down and work that out. As a computer, you could reasonably, you know, imagine you came up with an algorithm and all it has to do is say, satisfy the constraints that I've agreed a solution to that problem where you have four sponsors and one and three is to have sponsors one and two, and then show three and four on ultimate page loads in the third slot. Right. That also, you know, that the first two sponsors are getting a hundred percent coverage, the other two are getting 50% coverage.
So that's also a solution. Yeah. Yeah. And then that was the, when I wrote the algorithm finally got an algorithm, which didn't immediately blow up. That's what it did. It finally said like, this is perfect. And I realized there was, I was missing a constraint.
Yeah, yeah. You wanna balance them.
Exactly. So you also wanna say for a given frequency, folks who are being shown one in three should be shown a roundabout the same amount. And that's what makes it even more difficult because you've gone from something which is trivially provable. Um, and, and I was thinking about this in terms of, you know, complexity theory. Um, if I, if I set, if, if the forgetting how complicated the, the, the algorithm that generates the solution is, and so let's say the solution is an array of n samples of sponsors, right? So let's say there's just 10 of them and there each, each of those, uh, 10, um, array has a, a, a choice three sponsors at a time,
And I could say that to you and say like, Hey, if you were to just cycle through these one iteratively, then it would, it would meet my commitments. Right? Right. That would be like a, something you could say, um, you can, in a, in a very straightforward way, you can see if it is a solution, right? So it's the, the solution is PO can be checked in polynomial time if we're thinking about like NP and non NP kind of problems, right? Like, so a solution where you're saying is this, um, does this meet the criteria of all of the sponsors individually? You go, well, there, there's 10 slots sponsor one that is shown four times sponsor two is shown four times, and sponsor three is shown four times, whatever. Then that's more than a third of the time. So they're all fine. Okay. This is definitely a correct solution.
And so that becomes one category of difficulty. As soon as you say, I want to minimize the amount of difference between the numbers of times a sponsor has shown it goes into a new category. Because to check that answer, you have to solve the problem yourself. I, I could give you something which like meets the criteria of like, it's definitely one in three or more than one in three, but to prove that it's minimal is also NPR hard or NP difficult or empty, whatever the, the categories are. So it turned out to be more in, more interesting than I than I thought. Um, and there are definitely online algorithms for doing this kind of thing. But what I wanted to do, and this is the, the critical thing, and this isn't gonna get it into one of your, uh, favorite subjects, is I wanted to write tests and
Yeah, I was just gonna say, anytime you're dealing with, with sort of randomness, that becomes tricky. Right?
Exactly. Right. And so when I was explaining this to a friend down the pub the other night, as you do, um, his solution was immediately like a dynamic programming algorithm, which just uses essentially an error metric of like, how often have I shown each one? And then each time you get to choose, so every time the page loads up, it effectively re-chooses another sample. And that's kind of how I solved it as well. That's, that's my solution is like that. But rather than doing a choice every time and or having randomness and or dealing with, you know, well there are lots of servers, each one of the servers has own idea about which solution is what I wanted to be able to write tests. So I wanted to be able to say, generate me a minimal set and then I can compare it against what a human would've chosen for a a, a set a rotation like, uh, that would work and satisfy all those constraints.
Now obviously, like I said at the beginning, if you just did a random thing, you could definitely say, well just pick them with one third probability, you know, scale the probabilities and then just keep picking them and, and see, and then you would, you would get an answer. I'm quite sure you'd get an answer, but you would never be able to write a test that wasn't anything other than seed, the random number generator with a known good seed, run the test for a hundred and gonna go, well, empirically I meet the criteria after a hundred iterations. So that's probably fine. And I don't like that cuz it doesn't, I I I can't tell if the algorithm is wrong or right or anything. It just seems (bleh)
Right. Also, those kinds of tests are super hard to read, but yeah. So let me make sure that I understand what, what you're trying to get at here. So you wanna, you want to build an algorithm that's gonna produce basically a, a script, a list of the configurations that are going to be shown.
Correct.
And maybe, I don't know, just to have the page just rotate through that list. Uh, yeah. Over and over again. Okay, cool. And then your tests then, are you expecting a stable output from the execution of that algorithm? So your test could be like, yeah, solve this problem for these constraints and then it will produce that script and then like in the most basic case, you could literally just assert that, you know, for this configuration with these constraints, it produces this result and if I change the configuration, I will get a different result.
That is exactly.
Is that a fair summary?
Exactly. Correct. Yes. And so for the very simple cases, yes, you can sort of squint and say, well, what would I do as a human? And then obviously modulo ordering that where it doesn't matter. And in fact, I enforce a sort ordering, uh, within the icons just to make its stable, like you said. Uh, yeah, I, that's what most of my tests are. They're like, well, I've got five sponsors and three slots, and then these, these two have this frequency, these three, two have this frequency, this one has to be shown every time. And then this is the only solution that I could think of and maybe it comes up with a slightly different solution. And then I just write, convince myself the solution is equivalent and then say, okay, well that's the one I'm codifying here. It's like my algorithm. So it's a little bit, uh, uh, black box testy or, um, or, or not. The other thing, the other type
And you could send that to all of your sponsors and be like, this is literally what we did.
Exactly. If, if, if they cared
Auditable from that standpoint,
I should like the record to, to, to, to note that my sponsors have shown no indication that they give any kind of care at all about this other than like, I have an agreement that says one in N and I'm sure they'll take my word for it, but I would like them to know that I'm really thought hard about it to make sure I'm giving everyone a fair shot.
Oh yeah. It was a wonderful nerd snipe
when they all started citing n choose K papers and the choice problem and all this kind of stuff. But, um, yeah, it was, it was fun to discover, and as I say, it makes for, I, it might make for an interesting interview question, uh, even if you know how to do it, which I think I do now. I, you know, there's still a lot to discuss in terms of like testability, like we've just been doing here. Um I, in, in, I should say that I did also write as well as all these little unit tests, I did actually write an actual test that says just generate, call the, the code that's gonna use the pre-canned list, um, having created the pre-canned list and do it, you know, sample it a thousand times and let's just make sure that on aggregate, it still actually does keep to all of those criteria. That are like, each sponsor is one in n So that's, that's kind of my integration test there where not only is I'm, I'm like, I'm, I'm sort of rendering the page effectively and then looking at the icons and going like, did these come out? Right? Which tests both the, does the icon thing do the right thing as well as does it correctly call the underlying algorithm? And then does it in fact choose a new and different one of the possible solutions each time round, you know, like round robin or whatever it's doing.
You know, it strikes me that that actually might be a good application of a generative testing or property based testing framework.
Oh, that's interesting. Yeah.
Um, if you, especially if you wanted to be able to sort of dial up or down the amount of time you were willing to spend verifying the algorithm.
Yeah.
Like, you're never gonna be able to get a hundred percent certainty with a generative test, but you can be like, I ran this for 12 hours testing all possible combinations that the generative testing framework could come up with, and all of them satisfied the constraints.
Yeah.
So, you know, I'm not a hundred percent sure that this is correct, but I'm like many, many nines sure that this is correct.
That's really valid. I mean, obviously this is overkill. All this stuff's overkill because given the,
Of course!
N will be three page slots and maybe four, maybe five sponsors total ever, um, again, a perfectly valid solution to this entire problem is Godbolt sits down and writes out the list and then types it into the code. Right. Literally hard codes the list in. That's completely reasonable. But it was a really fun exercise in, in, uh, determining, you know, solving a problem that is actually quite computer science-y.
Uhhuh
. But so the,
So are you gonna le
I was gonna say about the generative, the, the, the thing that strikes me about the generative is that it is easy to given a, you know, a gen generated set of constraints like n slots, m sponsors with this many like, uh, uh, constraints themselves to prove that the result that you got out of the algorithm is correct. Right. That I think is what you're talking about here is like sort of essentially randomly choose the number of slots, randomly choose a bunch of sponsors, call the algorithm, and then you can, using this simple algorithm of like just counting the, the number of occurrences and divided 'em by how many times, uh, how many things you got back, um, you can say, yeah, this definitely hit the constraints that we cared about. Although, again, the balance between sponsors is a bit more subtle in terms of that, right? But ignoring that part for now, you can say, okay, this is ly correct. What you can't do is check that if it turns around and says there's no solution, you can't tell if it's right or not.
Hmm.
So if it picks,
Uh, interesting,
You know, four slots and then 10 sponsors that have to be shown one in seven, whatever, something weird like that, you're like, I don't know, tri, if that's solvable or not, without writing the algorithm myself again, which which defeats the point. So you could again, but it certainly allows you to approach the, um, con uh, the, the conclusion that it'll either blow up incorrectly and tell you that something doesn't fit that you think could fit. But if it does give you a solution, it is a, it is a valid solution. So that is probably okay. Cuz again, if you are, if you are, if you're on the phone to the sponsor
Yeah. Yeah. No, I mean, you could definitely have a, a, a generative test that, like if I was writing something like that, I would first start writing it with, um, constraints that I knew couldn't be solved for, and then I would run the generative test until it blew up having hit one of those constraints just to make sure I had written the generative test properly.
Right. That's true.
Right. And then, and then dial back the constraints until I sort of fit like the very edges of what I thought could be solved and then let it run for a long time and figure out if we agree basically. Right, right, right, right. Um, and then see like, okay, yeah. And then, you know, if you, if it blows up and says, oh, I couldn't come up with a solution for this, then you sort of look at that and go like, oh yeah, no, you're right. There is, I, I can't come up with a solution for that either. Does that mean there's not one? No, but between, you know, the, the algorithm, the tests and me, we can't come up with one. So, um, but yeah, that's super interesting. So I mean, I gotta say though, like, are you gonna leave our listener hanging by not explaining what your solution was? Cuz I feel like,
I mean, we got code. So the, it's it's effectively the dynamic programming solution. So, uh, I have my array of, of, uh, sponsors to fill, and the first thing I do is I sort all of the sponsors by how their current occurrence compares to their, their hoped occurrence. Right. How, how, you know, like, you know, so you start out and nobody's been seen ever, right? So everyone's equally, um, badly placed, right? So at that point you just pick three arbitrarily or out of your list and you put them in. But now they've had, now they've rolled at a hundred percent Right? Which is obviously higher than the, the target that they wanted, and that's fine. Higher is is always better, right? So then on the next iteration you say, okay, who all else needs to be fitted in? And then you sort the sort them still and you say, well, okay, well those three are now at the bottom of the list and,
Maybe the other sponsor gets the to the top of the list now because he, you know, that sponsor is out by a hundred percent or out by 30%, 33% and the others are now like out potentially 50% because they would've been shown half the time. So okay. He's more out than they are, so we need to pick him first. Okay, cool. And then you just pick any of the other two again. Right now you've got those two in and now you update the counts again and say, okay, now we've got a better idea when we're sort of asymptotically approaching the, the, the right numbers for them all, uh, as you do.
Yeah. Okay.
But the other thing that I do, and this is the second constraint, so that will immediately find a, so a, a, a solution to the, the problem of having four where they have to be shown one in three that will immediately follow us, find the solution, it goes 1, 2, 3, 1, 2, 4, we're done.
And you're like, I no, no, I, that's not fair. On three and four, they get shown half as often as one and two, even though they're all paying the same amount of money. Right. Which is effectively what this all amounts to
And so that's too high, and so we're gonna keep going. And then that also gets counted in like their score as to whether or not they should be picked or not is like how behind they are their, their, uh, uh, their contemporaries. And so you just keep going until you hit the, the hit a assist, uh, uh, a set where all of your constraints appear to be, sorry, all your constraints in terms of the number of times of that things are being shown have been met. And there isn't a single standard deviation amongst all of the, the sponsors at the same level where anyone's been put out by more than whatever threshold you've decided is like, that's fine. I think my threshold set to a quarter or something like that. So like everyone has to be pretty much on the same number, maybe one higher than the other. Right? Right. And that means that the algorithm will keep going in, in the case of, you know, like a, um, uh, you know, like a rounding error of like, well, it's 0.3, 3, 3, 3, 3, 3, 3, it'll keep going and adding more and more and more and more until eventually it goes, well, I've, they're close enough now they're within a quarter of a standard deviation over the number of of choices that I'm going to make now. Yeah.
Yeah. I can see you looking and thinking now.
Well, so, so the first thing I'm kind of thinking about here is, so you, you, the, the, the, you're, you're actually able in this algorithm to bucket the sponsors into the, the like fixed frequencies, right?
Yes.
Like you have, sponsors with....I was gonna say.
It's not a continuum because I've, I've phrased it as one in N, right? rather than a 33% or whatever. Now I'm sure I could come up with an equivalent scoring that sort of says, how fair is this? Now, one thing that occurred to me is that, that the algorithm could in fact pick a sponsor that's paying less money to more often than the sponsor who pays more money if there's like competition at one level. So you could imagine weird situations like that, and I haven't put that constraint in yet, but my, my instinct is that you could come up with a, uh, uh, a score that you wanna either maximize or minimize depending on which way you do, about like how good this particular choice is. And then you keep going until either that that score is as high as it could be or as low as you like, it's an error as low as, uh, uh, as you want.
Or maybe you go until it stops changing between iterations and you go, well, this is the best I got, and then if it's not getting any better, you're like, well then no solution exists. Which is kind of where I ended up. Although I just got a hard coded set of like, if you get to a hundred and you can't fit these constraints, then probably that's not, you know, that's not good enough. And so I'm, I'm certain, and maybe somebody who's listening now is jumping up and down in their chair, or is, is walking their dog shouting into the void about like this, well, of course you use, you know, Bresdem's, blah blah, blah algorithm.
Yeah,
But, and if so, please let me know or send me a PR or whatever. It's just, it's one of those things that I enjoyed the intellectual [gibberish], I enjoyed the intellectual challenge of, uh, of trying to think of a solution and probably somebody smarter than me. Yeah. He's gonna say, oh, there's just a close form solution. But as I say, a bunch of math PhDs couldn't come up with an answer in an afternoon
Right. Right. And I mean, it, it's in a lot of ways, I mean, this is kind of like a portfolio optimization problem.
That's the funny thing is it is very similar to our day job
. Yeah. Yeah. That's, that's very interesting. I actually,
I was gonna say it is actually an interesting, um, problem that presumably every online advertiser kind of has to solve as well. They're trying to maximize their profit given X, Y, and Z constraints. Like Google can't show you a hundred ads, it can show you three or four, or debatably, however many, many, many of the actual results are in fact ads in hiding as such. But whatever the idea being is, like I show you the three best and how do you determine those three best, especially quickly.
Right. Right. And then there's the meta portfolio optimization problem where Google has to decide how many slots for advertisers will make us the most money. Right.
Right.
Gosh. So you gotta optimize that portfolio problem based on the greater constraints of like
How many will users tolerate, uh,
Yeah, exactly.
You know, I just pluck three out of of thin air and thought, well, this is, looks like it's, there's enough space on the page for three.
Right, right, right. Hopefully. Did I tell you about, uh, uh, the, the change to, uh, have we ever talked about Bank of Dad? We've talked about Bank of Dad.
I dunno if we've talked about it on air, but we've talked about Bank of Dad.
No, I don't think we have talked about on air.
Which, you know, is a great way bankrupting yourself as you're about to explain,
I mean, you know, for a greater cause. So, so, so for our listener, uh, bank of Dad is this thing that I actually got from a coworker many, many years ago where his dad would, would pay him a ridiculous monthly interest rate for money that was quote unquote deposited in the Bank of Dad, like 5% a month, so long as he calculated the interest properly. And this is, you know, it was like 6, 7, 8, 9 years old. Right. And so I've done this with our kids for a long time, and what happens, what I've discovered is that you gotta make the problem harder and harder and harder, otherwise you're really not getting a good return on your bank of Dad interest payments
Um, because we did, we went from, you know, simple monthly compounding interest to daily compounding interest to, uh, continuous compounding interest to continuous compounding interest. Uh, we actually had a, a version of this where it was like I would give them the interest amount for the month, assuming continuous compounding, and they had to figure out the interest rate.
Oh my word Oh.
Um, so inverting the problem. And now the latest version of this has been a portfolio optimization problem where I say something along the lines of like, okay, you can pick the interest rate and the number of days that that interest is applied. Um, but there's a fee calculation that is a function of those things. And so you have, and so the fees will be deducted from your total interest. And so you have to figure out which combination of interest rate and days results in the highest actual payment to you.
Oh my gosh.
Um, and this has been, and, and of course I now have, I've set myself up now for the future of having like infinitely many dimensions
To by by the, um, by the time they graduate from Bank of Dad, they'll be running their own trading system against the world rightly, or like having to solve the same problems that we do. That's really cool.
Yeah, I mean, we've already, we've already kind of busted out a little bit of Python to try to solve some of these things.
Oh gosh.
So it's, it's leading, it's leading in a good dimension. But yeah, both my kids are, are, um, at least one of them is well versed with this type of problem. And the other one is sort of like looking over the, the one shoulder and going, Oh man that looks hard.
And you're gonna have to come with something more complicated.
Yep, yep.
Yeah. Factorized this large prime number, uh, correctly
Yeah. Yeah. Yes. We, we did have to put a cap on the total amount of money that it's in Bank of Dad. Cuz I started projecting out and I'm like, uh, we're not gonna be able to make the mortgage payments if I keep Like continuing on this pattern, like
It's Donald Knuth who stopped giving out, um, payments, uh, he was doubling the, the reward for every bug you found, wasn't he for a long time. And then when, you know, uh, now we're up to $1,024, it's no joke if someone finds a typo. Yeah. And so, uh, I believe he gives out, um, like checks that are like, not cashable, like they're fake, like Donald Knuth checks. Uh, I had a friend at Google who had one and PR proudly had it on his, on his, uh, uh, desk. But, you know, it wasn't actual real money and, and for good reason really. I mean, that was maybe a mistake on Knuth's part, but whatever.
Yeah. Yeah.
Alright. My friend. Well.
But yeah, those, those, my, those kinds of problems are, are all over the place. Is is sort of my point. Right. And they're very interesting when you find them.
Yeah, they are, they're more places than you might imagine. And most of the time, of course, when people, like, we interview people and it's like we talk about potentially like problems that involve like what big o notation does this particular algorithm have? And then, you know, most of the time the problem is why is this not compiling? Uh, hang on a second. Have you got your environment set up right? Oh, wait a second. Just Yeah, no, put, put, put put another space between these two things over here, please and all that. Yes. And it's never actually a problem that's algorithmic in nature, but every now and then you hit one. Yes. And you're very pleased. Uh,
Yeah. Yeah. Totally. Totally. Cool
All my friend. Well, thank you for listening to my, my problem and, um, if No, no, this is very, this is a great episode. If folks have any, uh, better ideas, then you know, let us know and, uh, I'll see you the next time.
Yep. Bye.