The Two Googles

Copied from a twitter thread with some minor edits. Opinions are my own, not those of my employer.

There are two Googles. The real-life one which is a massive for-profit company (which does some awesome things, treats it employees well, is very progressive in many ways, etc. But: it's still a massive for-profit corporation.) And then there's the imaginary Google that a lot of Googlers and Google users have in their mind. The imaginary Google is probably different for everyone, but think of like, if the EFF wrote a lot more code? Or, imagine if every engineer at Google was a huge believer in Net Neutrality and the Free Software philosophy and the power of technology to make society fairer. More importantly, imagine if decisions at Google were made democratically by those people, rather than by the executive team. Now you have some idea what Imaginary Google looks like. (Also there are zero neo-nazis at Imaginary Google. None at all. It's great.)

Anyway, here's the tricky part. A lot of us (including me, not sure if I made that clear on Twitter), in a weird way which is hard to describe, kinda believe we're working at Imaginary Google. Is that because A Few Years Ago Google was slightly closer to Imaginary Google than today's IRL Google? Or does it just seem that way because we look at the past with rose-tinted glasses? Hard to say. I bring it up because it's a useful framing for certain issues if you're hoping to get Google to change its position on something. The specific example that prompted me to write this was the revelation that Google is a donor to the Federalist Society which I don't know much about but I gather that it's not what you'd call a progressive organization. If you follow news about Google, you can probably think of other examples where Google has taken actions to remind you that it's not the idealistic Imaginary Google you sometimes think it is. Anyway, what I mean about "framing" is that once you remind yourself about the two Googles, your response to Google doing something that seems shocking isn't, "How could we possibly being doing this? This isn't what Google stands for!" but instead, "This is what Google stands for. Our actions are clear. But, let's change that please. Let's not take this position."


Polkadot Postcards

Remember that Kickstarter I helped kickstart, Polkadot ____? Well, they reached their funding goal about a month later, and I recently got my reward: Postcards and a button!

Woohoo! Looking forward to the book.


Why coming out still matters

If you're a part of the gay blogosphere/tweetosphere/tumblrosphere, you already know by now that Anderson Cooper has acknowledged he is gay, in an email to Daily Beast reporter Andrew Sullivan. Before sharing the email itself, Sullivan admits that it's really not a big deal. So many celebrities have come out in the last few years that it's, as he says, kind of a "non-event" now. But in Anderson Cooper's email, he explains eloquently why the act of coming out is still a big deal, not just for him, but for all of us:
I’ve also been reminded recently that while as a society we are moving toward greater inclusion and equality for all people, the tide of history only advances when people make themselves fully visible. There continue to be far too many incidences of bullying of young people, as well as discrimination and violence against people of all ages, based on their sexual orientation, and I believe there is value in making clear where I stand.
Nothing changes people's minds about gay people in quite the same way as seeing more gay people out there in the world, among their own friends, family, and coworkers, and in the public eye. The next time Mitt Romney or someone else says something about the gays, maybe people will think of Anderson Cooper, rather than thinking of an abstract and weird group of people they'll never know and can't relate to at all.

Of course, this is also a big deal for him personally. If you've never had to "come out" about something, whether it's your sexual orientation, gender identity, or some aspect of your past that you had previously kept hidden, you might not relate to this, but coming out feels like such a huge weight off your shoulders, like being weirdly trapped and then suddenly free of that trap. Maybe you already knew, maybe everyone already knew. But to actually come out and say it publicly is still a big deal for him. So I'm happy for him as well, not just for the effect this will have on the rest of the gay community.


Top 9 reasons to ride Metro in Los Angeles

This post has been in my drafts folder for months. Time to get it finished up and actually post it. My top 9 reasons to ride Metro in L.A.:

9. People in Los Angeles are sort of shocked when you arrive somewhere and they ask if you were able to find parking easily, and you tell them you took a bus. "You took a what? You can do that? Really?!"

8. Most of the train stations have interesting art in them, totally different in each one. I think if I was an artist, I'd rather have people see my art every day on the way to work, rather than going to a museum, staring at it for a few minutes, pretending to "get it" and then going home.

7. This one's sort of obvious: Gas is expensive. Metro tickets are cheap.

6. No matter where you're going, finding a parking spot in LA is always terrible.

5. Paying for that parking spot? Also usually terrible.

4. When you don't have to focus on driving, you can actually do other things while you're en route. Check email, play games, let your mind go blank.

3. If you want to go to bars or other alcohol-based venues, you don't need a designated driver. I get so nervous when people say they only drank a "little bit" so they're "totally fine to drive," don't you?

2. You can take the Silver Line or the 550 and be in the carpool lane on the 110, even when you're by yourself. I like carpool lanes.

1. While a train or bus is slowing down or speeding up, you can lean against the inertial forces and pretend you're doing that Smooth Criminal lean. Until you fall over and then you're not so smooth.

Kickstarter is not an investment

In case you haven't heard of it, there's this great site called Kickstarter. If you have an idea for a documentary, video game, or other product you're trying to get off the ground, you can post it on Kickstarter, detailing the process you're going to go through, what you need money for, etc. Then anyone who likes your idea can donate as much as they want. In return, they usually get a copy of the product (if it's something easily copy-able like a video game) or some other little trinket from the creator. For example, I donated to the "Polkadot" book series a few months ago.

Kickstarter, and sites like it, have come up in conversation a few times with people I know. And there is a sense from some people that it's a "scam" because you don't get any real return on your investment. Call me crazy, but I think there's something nice about a donation where you don't expect anything back. You just do it because you believe in the thing you're donating to. Not that you necessarily believe it will become massively profitable, and you want a cut of those profits, but maybe you just believe the world will be a slightly better place if that product exists than if it doesn't. It's a donation, not an investment. And there's something kind of nice about that, don't you think?



This week marks my six month anniversary (0.5th anniversary?) at Google. I feel like I should have something inspiring to say about that. Mostly I feel like I know enough to know that there's a ton I don't know. In other words, I feel like I'm still so new that I don't have anything particularly awe-inspiring to say yet. But I'll piece together some scattered thoughts as best I can.

I can say it's awesome to be working at a company where so much information is shared with employees, and where we always try do the right thing. Not necessarily what's best for Google in the short term, but what's best for our users and for the internet. It's awesome to work at a company that has a sense of humor. It's awesome how much energy goes into improving the tools that Googlers use every day, which makes us happier and more productive. Some of those tools are also used by people outside of Google, and it's awesome that Google makes a lot of them open to the world. It's awesome to work on a product that's used by a zillion people every day. It's awesome to have people tell me they're die-hard fans of that other product, because it makes me feel like I'm a warrior in some sort of epic battle (even though I'm not).

I don't know what else to say right now. Ask me again in another six months.


Polkadot ____

I've been thinking about backing a Kickstarter project for a little while now, but nothing particularly jumped out at me as something I cared enough about to fund with my own money. But today, I came across a project for a "gender non-binary children's book" called Polkadot ____. I'm assuming that's because the books will be called "Polkadot Goes to Preschool" or "Polkadot Does a Silly Dance" or "Polkadot Wears Polkadot Pants" or something, and that you don't actually pronounce it "Polkadot Blank" -- but who knows? According to the Kickstarter page:
Our series begins when our main character Polkadot; a child who was not assigned a gender, is at an age when their gender identity is still forming and emerging.  The first book in our series is entitled, "Polkadot Goes to Preschool." While Polkadot is the main character of the series, and therefore their gender identity is central, this series of books celebrate the beauty and validity of ALL gender identities.
I won't pretend to know what it's like to be transgender, but I can imagine that reading this book, or better yet, growing up in a world where you're surrounded by people who have read this book, can only  make it easier. To suggest to kids that the idea that maybe "I was born as a boy, therefore I'm a boy, it's that simple" might be wrong, it's a definite step in the right direction. So I threw the author a few dollars. Why not?

I also wrote up this blog post, which might bring in a few more for them, and it didn't even cost me anything! Now the trickier question. Should I try and get the word out to pro-LGBT people who might also contribute? Or should I instead get the word out to anti-LGBT groups, so that they can cause a big "controversy" over the fact that a book might teach children that people are different from each other, so that then even more pro-LGBT people will contribute, to spite the anti-LGBT people?


Haskell adventure: Project Euler #191

I thought I'd try to be like one of the cool Haskell kids and do one of those literate programming blog posts. That means you can copy and paste this whole blog post into a .lhs file and it will actually compile. This is about how I solved Project Euler problem 191 in Haskell. So if you're trying to work through the problems on your own, don't read this yet!

Let's get to it. Already read the problem statement? Cool.

> import Control.Monad ( guard )
> import Data.List ( groupBy
>                  , isInfixOf
>                  , sort 
>                  )

One of the most obvious things you might want to do, especially since the problem statement used the word "string," would be to represent the O's, L's, and A's as Chars. But I think it's nicer to use a distinct type like this:

> data Day = O | L | A
>   deriving ( Eq, Show )

As you'll see, it will also be helpful to have a list of the three possible "day" values:

> days :: [Day]
> days = [O, L, A]

Then we can represent a student's attendance record as a list of those values. (I'm calling it Record1 here because I'm later came up with a better representation, as you'll see.)

> type Record1 = [Day]

How do we know whether a particular record is prize-winning or not? This is more or less just a translation of what the problem tells us.

> prize1 :: Record1 -> Bool
> prize1 record = (not $ [A,A,A] `isInfixOf` record) && notLateTwice record
> notLateTwice :: Record1 -> Bool
> notLateTwice record = case filter (== L) record of
>   (L:L:_) -> False
>   _       -> True

Now we can attack the actual question: After n days, how many prize strings are possible? For n=0, there is only one, namely, an empty record:

> prizes1 :: Int -> [Record1]
> prizes1 0 = [[]]

On the nth day, take all the prize-winning strings from the (n-1)th day, and for each one, tack on an O, L, and A. Now you have three times as many strings, and you can check each of them to see if they're prize-winning. (We don't have to check the non-prize-winning strings from day n-1, because once you've lost the prize, there's no way to get it back.)

> prizes1 n = do
>   prevPrizeString <- prizes1 (n - 1)
>   nextDay <- days
>   let newString = nextDay:prevPrizeString
>   guard $ prize1 newString
>   return newString

The code after "do" gets evaluated several times, once for each possible combination of a string from prizes1 (n - 1) and a day from [O,L,A]. In another language, you might write this as a double "for" loop, or possibly a list comprehension. I probably could have used a Haskell list comprehension instead but I think this is nicer. Anyway, then we add the 'nextDay' onto the prize string from the (n - 1)th day, and check whether the result is still a prize string. If it is, we "return" it which means it will end up in the list of prize strings for day "n" and if not, the "guard" function ensures it will not be returned.

You may notice that I stuck nextDay onto the front of the list instead of the end. That's just because it's faster and cleaner than writing "++ [nextDay]" although it turns out to be useful later too, as you'll see. You can check that "length $ prizes1 4" is 43 which is a good sign we probably haven't messed up too badly yet. And then "length $ prizes1 30" should be the answer. I fired up ghci and typed it in, and ... nothing. The CPU cranked away but after several seconds, it hadn't come up with anything. The rule of thumb for Project Euler is that your code should run in a minute or less. But I had a sneaking suspicion that there was a solution for this problem that would run almost instantly. So let's optimize!

One thing to notice is, we don't really care about absences in the distant past. You only lose the prize if you're absent three consecutive times. And we'll never end up with a string like OAAAO because once you hit the third A, you've already lost your prize and we stop keeping track of you at all. So the function we pass to "guard" can just look for A's at the beginning of the string (remember, more recent days are at the beginning, not the end), rather than using "isInfixOf" to look for an "AAA" sequence anywhere in the string.

> checkRecord :: Record1 -> Bool
> checkRecord (A:A:A:_) = False
> checkRecord (L:ds) = L `notElem` ds
> checkRecord _ = True

If today is your third consecutive absence (A:A:A:_), you don't get a prize. If you were late today, you can still get a prize, but only if you were never late in the past. In all other cases, if you haven't already lost your prize, then you're still eligible for it. Now in the definition for "prizes1," we can just replace "guard $ prize newString" with "guard $ checkRecord newString" and it should be a bit faster. It was still well short of "instant" so I kept looking for better approaches.

Writing "checkRecord" was a step in the right direction, but we were still keeping track of lots of information we didn't actually care about. All that really matters is a student's current absence streak, and total number of times being late. So let's just store those, and not the actual sequences:

> data Record2 = Record2 { consecutiveAbsences :: Int, lates :: Int }
>   deriving ( Eq, Ord, Show )

You could also just use a tuple ((Int, Int)) but this way there's no risk of forgetting which field is which. Plus, this syntax is called "record syntax" so it's only appropriate to use it for our "Record" type, right? Right. Now that records aren't just lists, we can't tack on the next O, L, or A with the (:) operator -- we have to actually keep track of what those two Ints should be. That's what the (#) function does. (Why did I choose "#"? No particular reason, I just picked a character.) Anyway, here it is:

> (#) :: Record2 -> Day -> Record2
> r # O = r { consecutiveAbsences = 0 }
> r # L = r { consecutiveAbsences = 0, lates = lates r + 1 }
> r # A = r { consecutiveAbsences = consecutiveAbsences r + 1 }

If you're absent, we increase "consecutiveAbsences" by 1. If not, we reset it to 0. And if you're late, we increase "lates" by 1. Now it's really easy to check whether a particular record is prize-winning:

> prize2 :: Record2 -> Bool
> prize2 r = consecutiveAbsences r < 3 && lates r < 2

And we can do more or less the same thing we did before:

> prizes2 :: Int -> [Record2]
> prizes2 0 = [Record2 0 0]
> prizes2 n = do
>   r <- prizes2 (n - 1)
>   d <- days
>   let r' = r # d
>   guard (prize2 r')
>   return r'

This should be a bit faster, I think, at least in theory. But I was still convinced the "right" solution was instantaneous, and this one definitely wasn't. The problem is, we're still dealing with a number of records on the order of 330, and we really don't need to. If you look at the new Record2 type, you realize that there are only a few distinct records we ever care about: consecutiveAbsences only goes up to 3 and lates only goes up to 2 so there are only 3*2=6 possible records we'll ever care about. So instead of keeping a huge list containing several copies of identical records, we could just keep a list of the six possible records we actually care about, paired with a number indicating how many times that record should appear in the list:

> prizes3 :: Int -> [(Record2, Integer)]
> prizes3 0 = [(Record2 0 0, 1)]
> prizes3 numDays = reduce $ do
>   (record, count) <- prizes3 (numDays - 1)
>   day <- days
>   let record' = record # day
>   guard (prize2 record')
>   return (record', count)

If we leave out the "reduce" this will be the same as "prizes2", except that every record will be paired with a "1" which is kind of useless. The "reduce" function takes all the Record 0 0's and puts them together, then takes all the Record 0 1's and puts them together, and so on, each possible record value being paired with its total count. There are at least a couple ways to do this, but what I did was this:

> reduce :: [(Record2, Integer)] -> [(Record2, Integer)]
> reduce = map f . group . sort where
>   group = groupBy (\(r,_) (s,_) -> r == s)
>   f list@((r,_):_) = (r, sum $ map snd list)

Remember that with the (.) function, it's often easier to read right to left. So the reduce function takes a list of (Record2, Integer) pairs, sorts it, then calls "group" on that sorted list, then maps the function "f" over the result of that. The "group" function groups all the identical records together, returning a list of lists. Then the "f" function reduces each list into a single (Record2, Integer) pair. To get the total number of prize strings after n days, we can't just use "length" anymore; we need to sum the counts from all the pairs:

> prizeCount :: Int -> Integer
> prizeCount = sum . map snd . prizes3

Again, you can check that prizeCount 4 is 43 (really nice of the Project Euler people to give you that sanity check, isn't it?) and then

> answer :: Integer
> answer = prizeCount 30

and it runs instantly! If you didn't know much Haskell before. I hope you learned something from this post, or at least enjoyed kind of half-following along. If you did, maybe you can point out something I did wrong, or a more elegant way to accomplish one of these steps. Either way, leave a comment and let me know what you think!