Category Archives: Uncategorized

Puzzle: Forty-Seven and Four Sevens

The 4 small squares have a side length of 7; the large square has a side length of 47.

foursevens

What is the area of the grey region?

Bracket: A bracket-only programming language.

I just came up with a lambda-calculus-based language with my roommate. (Warning!: assumes familiarity with lambda calc.)

EDIT: Curly and square brackets are unnecessary and confusing. Future versions of Bracket will be nice and round:
(XY) –> (()XY)
{XY} –> (XY)
[X] –> (X)

This leads to a single elegant function (), which can take 0-3 arguments:
() is the lambda metaprocedure
(X) is an identifier
(XY) is the procedure X applied to argument Y
(MXY) is the metaprocedure M applied to arguments X and Y

This simplifies the language, and should therefore make code much more readable. It also helps me achieve my goal of creating the purest form of LISP: one in which there are no data types and no keywords — only parentheses. (Everything (must (be parentheses))).

ENDEDIT.

Here’s the syntax for Bracket:
(XY): the lambda expression λX.Y, where X is an identifier and Y is an expression.
[X]: an identifier (variable) unique to X (that is, [], [[]], [potato] are all unique identifiers.)
{XY}: the expression X applied to Y. Equivalently, {} is just used for grouping, but all lambda expressions must be explicitly grouped with anything they are applied to.

For example, ([][]) is the identity function, [x] is an identifier, and {([][])[x]} = [x].

A program is just an expression that evaluates to a list* of numbers**, which can be translated into a string of characters with
{{P([]([[]]{{C{{[]I}O}}[[]]}))}N}
(the Bracket syntax for Pλx.λy.C(xIO)yN)
Where:
P is the program
C is a function that prepends an ASCII character to a string
I is a function that increments an ASCII character once
O is the ASCII null character 0x00 or \0
N is the empty string “”

*lists are represented in Church encoding, “Higher-order function” style.
**numbers are Church numerals (see the same article)

Now that that’s out of the way, here’s a “Hello World” program: (actually prints “HW” for the sake of brevity)

{{([]([[]]([[[]]]([[[[]]]]{{[[[]]][]}{[[]]{[[[]]][[[[]]]]}}}))))([]([[]]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[][[]]}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}))}{{([]([[]]([[[]]]([[[[]]]]{{[[[]]][]}{[[]]{[[[]]][[[[]]]]}}}))))([]([[]]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[]{[][[]]}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}))}([[[]]]([[[[]]]][[[[]]]]))}}

And here it is in the new, 300% rounder version of Bracket:

(((()(())(()((()))(()(((())))(()((((()))))(((((())))(()))(((()))((((())))((((())))))))))))(()(())(()((()))((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))(((()(())(()((()))(()(((())))(()((((()))))(((((())))(()))(((()))((((())))((((())))))))))))(()(())(()((()))((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((())((()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))(()(((())))(()((((()))))((((()))))))))

Skepticism and Credulity on Facebook

I’m increasingly convinced that many (most?) people think in a fundamentally credulous way. By which I mean they tend to assume things are true by default, unless there’s a strongly compelling reason not to.

Here’s an example from a comment on a spammy Facebook event I got invited to:

put your hand in a fist
kiss ur hand 10 times
say ur crush 15 times
post this on 2 events
then look at ur hand

The way these things spread is through credulity: people read it, want it to be true that something will happen if they follow the simple instructions, so they assume it is true and follow through. (Of course, they would probably admit, if pressed, that it’s not really likely to do anything, but they at least believe it’s plausible — despite the absurdity of it.)

I think the core of skepticism isn’t requiring an unusually high level of proof or evidence to believe something, or even requiring any strong evidence at all, but rather thinking about whether or not to believe something in the first place. Once you’ve asked yourself “is this possible based on what I know,” the answer is obvious, but many people don’t ask themselves that question at all. For them, “but what if it is?” is all the convincing they need.

On a related note, the event promised a “Facebook Phone” to the first 10,000 people to spam 100 of their friends with invitations to it. None of the six thousand people to join so far thought to check whether such a phone exists, let alone whether the event was official.

It links to a similar event promising Dr.-Dre-branded headphones. None of the 8,000 people who’ve joined it thought to wonder why Facebook would divulge private information (such as event invitations) to Dr. Dre, or what either party would gain from such as promotion.

This sort of thing goes a long way towards explaining, for example, why we can’t seem to find funding for astronomy, while astrologers rake in hundreds of millions of dollars every year. (For comparison: the world’s largest radio telescope, the Arecibo Observatory, currently has an annual budget of only $2 million and is in danger of closing.)

Efficient nearest-neighbor algorithm

I just thought this up last night: (math/CS warning)

Let’s say you have a large collection of points in a plane, and you need to find the closest point to point P. The obvious (and inefficient) way is to calculate the distance to every point, which requires N square roots and takes far too long to be useful in some cases (such as an early draft of Voronoid that didn’t work out because of this inefficiency). Here’s a better way I came up with:

  • For every point Q, calculate |xQ-xP| and |yQ-yP|. Find the sum and maximum of these values and store them.
  • Find the two points with the smallest sum and the smallest maximum.
  • If the same point has the smallest value for both, you win! That’s the closest point to P. Otherwise…
  • Go through the points again, using the stored values this time. For every point that has a smaller sum than that of the point with the smallest maximum and a smaller maximum than that of the point with the smallest sum, calculate the standard Euclidean distance from P: sqrt((xQ-xP)2+(yQ-yP)2). The closest point to P within this (likely very small) set of points is also the closest point overall.

I’m sure there are absurdly efficient algorithms for doing this better, but this one is very easy to implement (assuming it works, which I’ve sort of heuristically proven). In fact, I might go back and try my early version of Voronoid with this algorithm and see how it runs.

Doodling on an HTML5 canvas

I just tossed this together this morning. Next up: pretty colors!

(Note: Internet Explorer 8 or below can’t do canvases.)

“You have not discovered a potion for remembering, but for reminding”

I found an interesting quote today:

You have not discovered a potion for remembering, but for reminding; you provide your students with the appearance of wisdom, not with its reality. Your invention will enable them to hear many things without being properly taught, and they will imagine that they have come to know much while for the most part they will know nothing. And they will be difficult to get along with, since they will merely appear to be wise instead of really being so.

It could easily be about Wikipedia, Google, or the Internet in general.

Actually, it’s about a much older technology: writing. Specifically, it’s (Plato’s account of) Socrates’ (account of Thamus’) commentary on writing from Phaedrus. Full text here, via an interesting NY Times article on an AI Jeopardist.

What do you think? Was writing worth it? How about the Internet?

(Postscript: relevant comic from Chuck & Beans)

Voronoid: multiplayer puzzle game inspired by graph theory

Voronoid is my final project for CS50. It’s a colorful game based on Voronoi diagrams, with a twist — check it out!
Voronoid Screenshot

[Note: So far, Voronoid supports Chrome and Firefox, on any operating system. It may work in Opera, but probably won’t in IE or Safari.]

Firesheep is Scary! (And a Chrome/Firefox Solution)

Firesheep is a new Firefox plugin that makes it very, very, very easy for anyone to mess with your online accounts. It exploits the unbelievable lack of security in most websites.

One solution (and probably the easiest good one) is to use SSL encryption. That sounds complicated, but it’s usually as easy as entering “https://” instead of “http://” before the URL. I say “usually,” because not all websites support SSL (it’s much more complicated from their end!).

Of course, it’s a pain in the neck to type that in all the time, so here’s a quick solution for Chrome or Firefox. In either browser, it forces “s gmail.com” to redirect to “https://gmail.com/“, for example.

Chrome:
Wrench menu –> Options –> Basics tab –> Default Search section –> Manage –> Add…

Then add the following “search engine” keyword:

Name: SSL
Keyword: s
URL: https://%s

Firefox:
Bookmarks –> Organize Bookmarks –> Unsorted Bookmarks (in the sidebar)
Then Organize –> New Bookmark…

Then add:
Name: SSL
Location: https://%s
Keyword: s

Caveat:
This will force the first page you visit to use SSL, but the website may drop the security for future pages. For example, “s gmail.com” will stay encrypted, because Google is smart, but “s facebook.com” will go back to plain old HTTP after you log in, because Facebook…. isn’t that smart.

Plugins like HTTPS Everywhere (Firefox only, because of technical limitations in other browsers) will automate the process and keep your connection secure all the time.

Lame Joke

Knock Knock.

          Who’s there?

Man.

          man who

Killer Robot vs. Zeno

Zeno of Elea: “Oh, hello there.”
Killer Robot: KILL ALL HUMANS\n
Zeno: “Please don’t.”
Robot: PREPARE TO DIE\n
Z: “And how do you propose to kill me?”
R: MY FIST WEIGHS THIRTY TONS\n
Z: “Ah, but you’re a good eight cubits away!”
R: I HAVE WHEELS\n
Z: “But you can’t get over here all at once. First, you must travel four cubits to reach the half-point, then a further four to reach me.”
R: OF COURSE\nDON\’T WASTE MY TIME\n
Z: “Nice backslashes.”
R: SILENCE, FLESHLING\n
Z: “Anyway, to travel four cubits you must first travel two. To travel two cubits, you must first–”
R: I CAN EXTRAPOLATE YOUR ARGUMENT\nTHIS COULD BE ACCOMPLISHED VIA A SIMPLE RECURSIVE ALGORITHM\n
Z: “Ha! I’d like to see you try. What language are you coded in, BASIC?”
R: THIS IS BLASPHEMY\nI WILL KILL YOU NOW\n
Z: “Sure, just drive over here.”
R: …SEGMENTATION FAULT\n
Z: “Thought so.”