dtm: (Default)

Okay, I've gone and deleted my livejournal. I don't know if I'm going to resume blogging, but if I do it'll be here and not there.

In the meantime, here's a cute little result about the sum of Fibonacci numbers that I worked out while answering a question from a friend's child:

(Using the convention that F0=0 and F1=F2=1)

dtm: (lizard)
I was pointed at this entry about being Jewish in 2016 in the US, and the ways in which it means always being an outsider in ways that are frequently erased, and I was once again reminded of the ways I react to things that were informed by my having grown up where I did, which is in the Philadelphia suburbs.

Read more... )
dtm: (lizard)
In my previous post, I said I was working on a version of my old killfile script as a chrome extension.

Well, that's now happened! And I have it as both a firefox and a chrome extension. (Same source, mostly.) I still need to go through and clean out the list of supported sites, but note that in addition to the sites it supports directly, it also supports any site that uses disqus through an iframe. (Like rawstory.com, wired.com, and many, many others; sadly, Shakesville uses disqus in a different manner that I can't handle yet)

  1. Killfile for chrome

  2. Killfile for firefox

The chrome extension can also be found by going to the chrome webstore and searching for it; the firefox addon can't be found by going to the main page and searching because firefox has a review process for addons that's really slow. It might be reviewed by Christmas.

On chrome, your killfile list is shared across all your devices if you sign into chrome and do the chrome sync thing. On firefox, it's strictly local.

The full source is on github.
dtm: (lizard)

So many, many, many moons ago (over seven years!) I posted about a greasemonkey script that provided a comment killfile. (See that page if you're unfamiliar with the concept)

It was popular and useful for a while, but mostly succumbed to bit rot while I was at Google and I hadn't had a chance to play with the code in a modern web environment until recently.

I now have an experimental version of my old killfile redone as a chrome extension, and am looking for a few early tester volunteers to find out the places it should work that it doesn't yet. I'm also interested to see if the chrome sync stuff works for people who aren't me. (in theory, all your chrome devices should know about who you've tagged as a troll)

Now I'm providing even less support for this version than I provided for that greasemonkey script, so don't even bother asking unless you feel comfortable following the steps on this page under the heading "Steps on adding extensions from other websites".

But if you'd like to test this thing send me an email at martin -at- snowplow -dot- org.

dtm: (Default)
Hey, you, are you making a website that accepts credit card numbers? Or phone numbers, or any kind of long number or code that your annoying users want to enter with spaces and dashes? Are you about to add a message that says something like "no spaces or hyphens"? STOP. Just stop, right now. If you've already done that, go and fix it. NOW

There is no excuse for doing that. If you find yourself in the position of writing code to pull some data out of a web form and can't at the same time strip the spaces and hyphens your users put in there so that they'd type the stupid sixteen digits correctly, then you need to find another line of work. Or at least ask on stackoverflow.com if your framework makes massaging input like that stupidly difficult.

Are you a website owner who pays people to make forms that take credit card numbers or phone numbers, and have they given you a form with the text "no spaces or hyphens"? Send it back. Demand that they fix it, and if it's going to cost significantly more than any other change would, find someone else to do it.

Integrating with a third-party site to take the credit card information? Demand that they let your customers enter the numbers they need to with as many spaces and hyphens as they want. (And if they won't, find another site to integrate with)

Oh, and also: A pulldown menu for US states? That's just wrong too.

This message brought to you by an encounter with www.aa.com, who should be able to afford a better website.

Edited to add: If you're at a loss as to how to do this and are groaning about digging into your db code, at the very least implement step 1 on this page, which will ease the pain of the vast majority of your users. (That page describes some simple javascript you can add to such fields so that users can enter them however they want, but the form still has only numbers when it's submitted)
dtm: (Default)
So here's a bit of a geeky post, but not so terribly geeky that I'm hiding the bulk behind a cut link.

"true" and "false" are simple concepts, right? Different programming languages seem to have hugely different ideas of what they are:

In C, 0 is false, any other integer is true, and the coercion rules make a null pointer false, and any other pointer true. Anything else is a compile error.

C++ follows (inherits?) the C rule, and adds true and false as things that are true and false.

In shell, 0 is a true exit value; any other exit value is false. Inside [ ], empty strings are false and other strings (such as "0" or "1") are true.

In Python, 0, 0.0, -0.0, False, None, the empty string, empty tuples, lists, and dicts are all false. Anything else (such as the string '0') is true. (A note on 0.0 vs -0.0: they're both == according to python, and both false, but print differently. One can be turned into the other by multiplying by -1)

In Perl, 0, the empty string, and undef are false, and since evaluation as a boolean imposes scalar context, an empty array or hash variable is also false. Anything else (including arrayref or hashref values to empty structures) is true. Note that because perl helpfully autoconverts like a $SOME_NOUN_HERE, the string "0" and 0.0 are to perl identical to 0, and therefore false. (hence the Perl idiom "0 but true") A full discussion of the quirks of perl around various representations of zero could probably fill a small book, but I'll note that other consequences are that the expression -0 is true, but -0.0 is false.

In Ruby, false and nil are false, anything else (including 0, the empty string, and an empty Array or Hash) is true.

In Javascript, 0, null, undefined, the empty string, false and NaN are false. Anything else (such as an empty Array, or empty Object) is true.

In Java, (since the autoboxing introduced in Java 1.5) true and Boolean.TRUE are true, false and Boolean.FALSE are false, ((Boolean) null) is a runtime exception, and anything else is a compile error.

In Haskell, True is true, False is false, and anything else is a compile error.

Google Go behaves like Java 1.4 or Haskell - true is true, false is false and anything else is a compile error.

Scala appears to behave the same way - true is true and false is false. Anything else (including an instance of RichBoolean, or of java.lang.Boolean) is a compile error.

In Common Lisp, nil, aka the empty list, is false. Anything else - including 0, the empty string or empty vectors of other types - is true.
dtm: (Default)
This morning, I sent an email to the letter-to-the-editor email address of the Burlington County Times. It's the first time I've done so, and I'm afraid I was rather long, so I doubt it'll get published. (And if it is, I'm afraid of how it'll get edited down) I may clean it up, reworded slightly, and send it to my representative, for all the good it'll do.

It's about HR3, so I suppose I should put a bit of a trigger warning on the letter text for discussion of a bill that discusses rape.

What I sent )
dtm: (Default)
I wan't sure when I wrote the previous post, but now I am: there are in fact two distinct Rock-Paper-Scissors 7-degree extensions.

The gory details )
dtm: (Default)
We visited family in northern Wisconsin over New Year's, and one of the things that happened there is that we were introduced to the show "The Big Bang Theory", and I watched the whole first season on DVD.

So we've been working our way through the second season's DVDs here the past few weeks. As you may know if you've seen the show, in one episode this season they introduce the game of "Rock, Paper, Scissors, Lizard, Spock" (a game originally described here as "Rock Paper Scissors Spock Lizard"), an extension of "Rock, Paper, Scissors". (I'm going to call this game "RPSSL" in this post)

This got me thinking more generally about extensions to "Rock, Paper, Scissors", (hereafter, RPS) so let me define:
A degree-n RPS extension, where n is an odd number >= 3, is a two-player game in which players secretly select one of n symbols and then simultaneously reveal their choices; assuming the player selected differently from each other, the winner of the game is determined by the game's ruleset. The ruleset of an RPS extension must specify that every token wins against (n-1)/2 of the other tokens, and loses against the other (n-1)/2 tokens.

So RPSSL is a degree-5 RPS extension, because for any choice player A makes, exactly two choices for player B will let A win (and exactly two will let B win).

Two RPS extensions are equivalent if you can obtain one from the other merely by renaming tokens.

So here's what I've come up with:

  • There's at least one degree-n RPS extension for every odd n >= 3.
  • Up to equivalency, there's only one degree-5 RPS extension.
  • Up to equivalency, there are at most two degree-7 RPS extensions.

I need to work more with the two different degree-7 extensions I have to prove that they definitely aren't equivalent. Getting some paper and writing it down would probably help, rather than trying to just keep it in my head.

For the other two points, I'll just note that if you re-arrange the tokens in RPSSL into the order:
Rock, Spock, Paper, Lizard, Scissors

And imagine those tokens in a circle, then every token loses to the two tokens that immediately follow it and beats the two that immediately precede it. This shows a general pattern that can work for any n and working out that with five tokens, there must be such an order proves the second point.
dtm: (Default)
This is a draft of something I'm going to email to the office of Howard Kleinhelder, and maybe see if I can turn it into a local letter to the editor.

Howard Kleinhendler, I wanted to vote for you. Not that I knew who you were before you left that automated call I found on my answering machine last night, but I have voted against Chris Smith in every election since I moved to NJ's fourth congressional district. As the Democratic candidate this time around, you would have gotten my vote simply for standing against him.

When I got home and listened to the first 15 seconds of the pre-recorded message you'd left on my answering machine, I swore and punched the delete key; I wish now I'd saved it so that I could quote it to shame you. Have you become confused about what race you're running in, and maybe think you're now running for a seat on the New York City Planning Commission? Are you perhaps an expert in Islamic theology when it comes to the location of religious centers?

If not, why is it any business of yours where Muslims in New York choose to worship? Have you forgotten that this is America, where we are supposed to have higher standards for religious freedom and tolerance than anywhere else on the planet? Did you really want my first introduction to you to be a robocall assuring me that you're at least as full of anti-Muslim bigotry as your opponent?

Don't tell me about September 11th. I remember it well. I remember what a gloriously bright blue the sky was that morning. I remember the news stories on the radio that morning ("Mad Cow disease discovered in Japan"). I remember the minutes between the planes when we could think it was some terrible accident, and the shock of the revelation, after the second plane hit, that this was a deliberate attack. I remember frantically trying to find news websites that were still up to tell us what was going on. I remember over the next several days deliberately avoiding the TV and its endless replay of people jumping from the collapsing towers. And I remember how over the course of the following months and years our country went collectively insane.

I'm sure that the rest of your message, had I listened to it, would have calmly used language about the difference between having the right to do something and whether that's a good idea; that's the usual middle ground politicians attempt to carve out here. But there is no middle ground to be had there - you have declared that the anti-Muslim sentiment of people who were not actually there in Manhattan on that Tuesday trumps America's historic commitment to freedom of religion. You have joined with those who would class Muslims as non-American by definition. As a consequence, I cannot press the button next to your name this November.

I still can't bring myself to vote for Rep. Smith - his long commitment to a reactionary position on reproductive rights guarantees that - but when you see the full breakdown including write-in votes know that the "George Washington" write-in is from me. I know he's ineligible being dead and, more than that, a Virginian, but I'd point you to his letter to the Jewish community in Newport, RI as an example to follow. "To bigotry no sanction, to persecution no assistance" - that's how politicians speak when they want my vote.
dtm: (Default)
Because I've recently read an article on how Microsoft has egg on its face because of this, and because searching on Google for "sort a list randomly in javascript" currently shows the wrong thing to do in the top several hits, here's how to take a list in javascript and shuffle it, or sort it in a truly random order.

Also, yeah, it's been over two months since I last posted, etc.

However, this is just going to be code, and anyone who still has me in the old friends list probably doesn't need their livejournal covered with code, so it goes behind a cut...
Read more... )
dtm: (Default)
Since I seem to have livejournal open again, let me see if I can actually make two posts in a day.

So Katherine is now on the verge of being six. She is also on the verge of reading - she can read simple books to herself at I'd guess about the rate of 5-10 words per minute. She's generally right now able to read extremely slowly books labeled as "2" in the "I Can Read" line, and books labeled as "1" comfortably. (And has been observed to pick up the books on her own)

She's making her own books occasionally by drawing on several pieces of paper, writing stories (using her own invented, phonetic spelling) to go along with them, and asking us to staple the pages together. I should scan in a book she made a few weeks ago and put it up somewhere.

I should know how tall she is right now, but don't. I must remember to measure her when she gets home from my parents' house on Friday. I think she's just under 4' 2" (~ 125 cm.) but am not at all sure.

She's reasonably comfortable with the household computers, and has been able to sit at the family desktop and log into her username for just over a year. Recently, I installed a talk daemon and we've used that once or twice to chat at each other, though never when I wasn't somewhere else in the house. Typing is still a few years off at least.

We got a Wii for Christmas, and I worry a bit at how she tells me that she's scared of games that are too tough for her and refuses to play them, but I think it may be mostly that she doesn't want to play games she's not good at in front of me. For example, this morning I came in and discovered her playing BIT.TRIP.BEAT which is much, much too hard for any six year old. I think my presence flusters her; I'll have to see what I can do to make her more comfortable playing with me.
dtm: (Default)
I was thinking I needed something longer than a facebook status update, but shorter than a blog post.

But then it occurred to me that there's no real minimum length on blog/lj posts, so:

In Larry Niven's compilation N-Space, he includes a story outline and notes for a story he never wrote because he happened on the idea that became Ringworld instead. Anyway, these notes were for a final story to end his Known Space universe by introducing a gigantic game-changing conspiracy that basically demanded everything then come crashing down in one gigantic war. Basically, it was a way to go out with a bang.

I never saw the Star Trek movie that came out this past summer in theaters, but received it on DVD for my birthday a few weeks ago, and just finished watching it. It feels very similar, especially with the musical cues of the TOS music in the closing credits.
dtm: (Default)
Yeah, yeah, haven't posted in ages, etc.

As those few of you who still have me on your friends' lists probably know, I work for Google.

As the rest of you may know, Google's a fantastic employer and many, many more people than we can hire want to work here. In fact, many more people with good resumes want in than would be practical to interview in person. Hence the phone screen, wherein a Google engineer calls you up and assesses whether you should be brought in for an interview.

I do about one phone screen/week, on average.

Sometimes my interviewees manage to seriously annoy me. As a public service, here's how to avoid doing that. Note that many interviewees who did not annoy me still didn't end up with in-person interviews, but that no one who did annoy me did. This is basically a guide for how to avoid totally bombing - if you want a guide for how to actually succeed at a Google interview, look elsewhere.

This applies only to people being interviewed for a technical position (i.e., Software Engineer or Site Reliability Engineer). Not knowing everything on this list does not make you a bad person, nor will I be pissed off at meeting you if you don't know everything on this list. It does mean, though, that you are not ready to phone screen at google for an SWE position.
Cut for friends pages )
dtm: (Default)
Yeah, yeah. First post in a long time, first post of the new year, first post with a new US President, etc. Assume I've groveled sufficiently for not posting in ages.

So the other day I visited a website belonging to a friend and my web-browser completely freaked out, blocking the site and saying that it linked to all sorts of disreputable places. That is to say, it warned that my friend's site was including material from sites that attempted to install all sorts of malware.

Now, this was odd, but occasionally a bad ad can get into an ad network, and then everyone showing those ads accidentally is displaying malware, and I figured that was what happened since when I went back and then visited the site again, all was fine.

Only, after reloading her page I discovered that my friend doesn't run ads on her site.

A more detailed description of what was going on, probably of interest only to techies )
dtm: (Default)
I've been meaning to post this for a while, several months in fact, but I haven't. However, just this morning I discovered Scalzi's Law, and it seemed like a sign.

This is a reconstruction of a conversation I had at Google. It was had in 5-minute chunks over breakfast, over the course of several weeks, and has mostly died down now. I'll try to reconstruct it, but may miss some important bits since I wasn't writing it down at the time. In particular, I may well attribute important bits of the conversation to the wrong person. As background, Google provides us with breakfast if we're there early enough, but only two of us in my group ever are:

me: (looking at D's plate) You're going to regret that.
D: What? ... Oh (unpleasant face)
me: Yeah. The turkey bacon just isn't bacon.
D: The turkey sausage is fine, though.
me: Oh yeah, that's fine. Turkey's a fine meat, and they do make great sausage out of it; it just doesn't make good bacon.
D: (holding up the plate) It's not turkey bacon today.
me: Yeah, this is good.
D: Another day of the adjective-free bacon.
me: yeah, but I can't believe you tried that vegan sausage.
D: Oh, it looked so incredibly wrong I just couldn't pass it up. (tries) Oh bleah! The turkey bacon is disappointing, but that's just wrong. I guess I deserved that.
It gets weirder )
dtm: (Default)
Katherine, last night, after I finished reading her Dr. Seuss's The Lorax:
"Boy I wish I was that boy so I could take that last Truffula seed and plant it to grow the last Truffula tree and cut it down and make the last thneed in the whole world. Then we could use it for a pillow."
dtm: (Default)

For those of you who can't see the picture, when I opened up Amazon's page just now at the top of the page it said:
Kindle: Amazon's Portable Wireless Reading Device

The Amazon Kindle gives you instant access to over 125,000 books, newspapers, magazines and blogs, such as:
  • Freedom's Sisters by Naomi Kritzer
  • Freedom's Gate by Naomi Kritzer
  • Freedom's Apprentice by Naomi Kritzer

I detect a trend
dtm: (Default)
Yeah, yeah. Haven't posted in two months, blah blah blah.

And this isn't going to be a life update post either. Sorry. People who are not CS types (and this is much more academic CS than practical CS stuff) should just skip this post.

Now, I present some gloriously ridiculous, useless code, done primarily to show that I could do this in java, and do so in a typesafe manner.
A demonstration of the Y-combinator in java )
Well that was a bit interesting. Get you head around how it works, if you've never worked all the way through the Y combinator before. The relevant wikipedia article might be useful. The translation from scheme to java was fairly straightforward; the trick was getting all the types to work out properly.

But wait, there's more! That code there isn't really reuseable at all. What's really needed is a version that works with arbitrary types:
A generic version )
Oh, and for those of you worried that I'm giving away internal Google secrets by using the interface com.google.common.base.Function, that's already been open-sourced as part of the Google Collections Library.
dtm: (Default)
Okay, haven't posted in two whole months, I haven't told you what it's like working at Google since the first day, etc. I will say that my lack of blogging here has absolutely nothing to do with my internal-to-Google blog, since I haven't actually signed up for that either.

And this post isn't going to interest most of you who have me on your friends list, but if I waited for that, it'll be another two months or more before I post anything again. So here's a post on something I was thinking about this morning.

I was reading through some of Steve Yegge's old blog ("who is he?", you ask? He's just this guy that used to work at Amazon, now works for Google, and had an Amazon-internal blog that he made mostly public after leaving Amazon. Some of it's interesting) about interviewing programmers and he gave this as an example of the naive solution to the problem "find the nth Fibbonacci number":

static long fib(int n) {
  return n <= 1 ? n : fib(n-1) + fib(n-2);

One of the comments noted that they'd expect any candidate to be able to tell that that implementation as it stands is O(2n).

That didn't feel right to me - I mean, clearly it is O(2n) in the sense that big O provides an upper bound, but it's not a tight bound - that is, it isn't ϴ(2n). So what is a tight bound?

It turns out that this algorithm is actually ϴ(fib(n)), which is to say that it's ϴ(φn), where φ is the golden ratio (1 + √5)/2.

Why is this? Well, I think I'll leave that as an exercise for the reader, or maybe I'll add it later to this post underneath a cut tag. Suffice it to say that there's a nice recurrence relation that defines the number of invocations of fib necessary to calculate the nth Fibbonacci number, and that it requires a bit of fiddling after that, but not too much.

Anyway, that's something I was thinking about this morning.
Page generated Oct. 20th, 2017 08:38 am
Powered by Dreamwidth Studios