Google

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 3³⁰, 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!

We win. Again.

If you follow LGBT news at all, you've probably heard that Prop 8 was ruled unconstitutional today. Again. I'd like to be excited, drive up to West Hollywood, wave a rainbow flag and celebrate with the rest of the gayborhood. But I'm a bit less than thrilled because this is the third time we've "won" in court and only one of those times actually led to same-sex couples getting married. All this really means is that we're one step closer to the real win. I know, court cases take a really long time and I need to get used to that.

But for those LGBT people who actually might like to get married, they're being told yet again, wait just a little bit longer. The lawyers have to talk this over just a bit more. Be patient, it'll happen eventually.

In short:

:-/

If Programming Languages Were Types of Music

Thanks to the classic If Programming Languages Were Religions for the inspiration. Actually, it turns out there are a bunch of If Programming Languages Were X things out there.

Assembly would be scales: They're the foundation that all music is based on.

Fortran would be a Gregorian Chant: Ancient and methodical, but still sung occasionally in certain dark places.

C would be Bach: Almost all modern music is based on Bach in one way or another. The music can be pretty elaborate, but if you break it down, it's actually pretty straightforward.



C++ would be Beethoven: To the untrained ear, it sounds just like Bach -- classical and easy to listen to. But once you start listening more closely, it's actually a lot more complicated than most people realize.



Java would be The Beatles: Familiar to almost everyone, simple and uncontroversial, though as time went on, they started adding more stuff to their act and getting a little weirder.





BASIC would be kids music: Everyone liked it when they were younger, but no one takes it seriously once they start listening to anything else.



JavaScript would be Lady Gaga: Everyone knows her hits and thinks they can play them even if they're not a musician, but few know how talented she really is.



Perl would be The Ugliest Piece of Music Ever Written: You're required to make fun of Perl when you write a post like this, right? (Skip to 7:45 if you just want to hear the song.)




Python would be OK Go: You watch them occasionally on YouTube, but you would never listen to a full album from them.




Haskell would be Radiohead: You've heard them a few times, but you've never really understood what they're singing about, or what their fans are talking about.

Ruby would be electronic music: It's not bad or anything, but fans of electronic music act like it's the best music in the world, and rarely listen to anything else. Most people don't see what the big deal is.



Edit: Thank you to commenter Mike for this one: Lisp would be Jazz: It was a big deal when it came out and supposedly it still has a big following, but you can't name a single person who likes it.

I apologize if I left out your favorite programming language. It's either because I'm not familiar with it, or I couldn't think of a good musical analogy. Leave a comment and let me know what type of music it would be.

Prop 8 overturned one year ago

It was one year ago today that Proposition 8 was overturned by a Federal judge, making it legal for same-sex couples to marry in California. Except not really. I used to think that when courts strike down laws, those laws are, you know, not laws anymore. In fact, that's pretty much what happened the last time a court struck down Proposition 8. "But wait!" you say, "That wasn't Prop 8. In fact, that was before Prop 8 even passed!" Right, it was Proposition 22. But see if you can spot the difference between the two:

The complete text of Proposition 22:

This initiative measure adds a section to the Family Code; therefore, new provisions proposed to be added are printed in italic type to indicate that they are new.

SECTION 1. This act may be cited as the "California Defense of Marriage Act."

SECTION 2. Section 308.5 is added to the Family Code, to read:

308.5. Only marriage between a man and a woman is valid or recognized in California.

The complete text (pdf) of Proposition 8:

This initiative measure expressly amends the California Constitution by adding a section thereto; therefore, new provisions proposed to be added are printed in italic type to indicate that they are new.

SECTION 1. Title
This measure shall be known and may be cited as the “California Marriage Protection Act.”

SECTION 2. Section 7.5 is added to Article I of the California Constitution, to read:

SEC. 7.5. Only marriage between a man and a woman is valid or recognized in California.

Prop 8 changes the Constitution, while Prop 22 only changed the Family Code. Much more importantly, Prop 8 has the word "thereto" in it. I think that means they hired more expensive lawyers in the intervening 8 years? Anyway, what was I saying? Right, so it's been a year since this court decision, but same-sex couples still can't actually get married here, because the Proposition 8 proponents are appealing the decision, so there's a stay on the decision. And, the court isn't actually considering their appeal yet because first they need to figure out whether the proponents even have standing to appeal. In other words: It's gonna be a while.

What I want for Christmas

Here we are. Black Friday. The day that the TV box insists is the biggest shopping day of the year, although I suspect that it's a lie -- nowadays, I bet most people are either smart enough to start before Black Friday, or lazy enough to wait until the 23rd or 24th. Or they just buy everything online. Anyway, it's time for you to start deciding who you like enough to buy Christmas presents for, and what in the world they might want. So if by any chance I was going to end up on your list, here's what you should get me:

1. Nothing

Seriously. I have plenty of stuff. So if you really want to spend money this Christmas, spend it on someone who can really use it. Some ideas, in no particular order:

1. Make a Kiva loan. The best part about this one is, you probably get the money back eventually.
2. Vote For Equality. Remember that gay marriage thing? Yeah, it turns out we still don't have it, and this is a great, volunteer-based organization that is really doing the work to make sure we win if this comes to a vote again.
3. Speaking of which, you could also donate to the American Foundation for Equal Rights, who is fighting prop 8 in court right now.
   
4. You've probably heard about The Trevor Project -- a hotline to help LGBT kids who are thinking about committing suicide.
5. I think you've probably heard of Teach For America, which encourages college graduates to teach for a couple years, before or instead of getting a more typical job. Even though they didn't accept me, they're still great.

What other organizations are worth donating to? Let me know in the comments!

Maggie Gallagher on gay teen suicides

Maggie Gallagher of NOM has written about the idea that anti-same-sex marriage groups like hers are responsible for all the gay suicides that have been happening lately. She seems to slightly misunderstand the charge: it's not that gay marriage prevents teen suicides, it's that homophobia is what causes them--and no matter how you try to state it, NOM is of the opinion that same-sex relationships are not as good as opposite-sex ones--NOM is part of that homophobia that gay and perceived-to-be-gay teens are surrounded by. There's a nice, reasonable response to her column from The Bilerico Project where they admit that people like NOM aren't directly responsible for gay suicides, but also explain that they are, in fact, part of the problem.

Toward the end of that post, they say:

If Maggie Gallagher is actually concerned with queer youth as she says she is, perhaps she could donate to the Ali Forney Center to help some teens find a place to stay so that they don't have to get caught up in the violence that she knows so much about. Of course she won't, because she's a clown who doesn't really care about much other than advancing her agenda.

So I posted this on NOM's blog:

Maggie, call this blogger's bluff!

http://www.bilerico.com/2010/10/who_cares_about_queer_youth_not_maggie_gallagher.php

Donate to the Ali Forney Center or the Trevor Project, or even just publically state your support for anti-bullying laws.

As you say, "These kids need help, real help." So do something that will actually give them that support.

Think she'll do it?