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?

Advertisements

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:

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

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

Life on Gliese 581g?

I don’t have time for a post, but man, this is exciting.

Astronomers have discovered an Earth-like planet in the “Goldilocks Zone” of its solar system. Gliese 581g is the sixth planet of the Gliese 581 system discovered to date, and the most promising of them all (others have received media attention for their size/composition, or location, but until now none have been squarely in the middle of the habitable zone).
More info from Science magazine; the paper itself will be in the next Astrophysical Journal.

In my opinion, Steve Vogt is getting carried away, misquoted, or just trying to make a name for himself with that “100% chance” soundbite; I haven’t heard anybody claim that the *only* prerequisite for life is a water-friendly temperature, and (although I’m no xenobiologist) the fact that 581g is a ribbon world doesn’t inspire confidence.

Still, this is the best shot at finding extraterrestrial life we’ve ever had. In the words of a friend-of-a-friend: “This is the coolest f***ing time to be alive.”

[EDIT] The fact that Gliese 581g is tidally locked is probably a good sign, as Vogt explains in the Space.com article. This provides more of a range of temperatures, from the blazingly-hot side facing the star to the frozen dark side. In between, there must therefore exist a fairly wide zone of Earthlike “Goldilocks” temperatures. A planet that rotates with respect to its sun has a much narrower range of temperatures, lowering the odds (although there is variation from the poles to the equator, of course!)

By the way, Space.com needs to work on their fact-checking. Mercury isn’t tide-locked, as scientists have known for decades [NASA].

Dissociated Press: All The King’s Men

Dissociated Press is a program included with the popular source-code editor Emacs. When run on a text file, it generates hilarious free-associations (see the link for details.)

It’s a wonderful toy, but it’s particularly good on something as rambling as Robert Penn Warren’s prose.

Behold:

I suppose that Anne, and juicy while Anne was inclined to bone and
muscle under flesh. Lois looked edible, and you knew it!" I
exclaimed, "I ought to have known it! It had to be."
"If you can guarantee results like that," I said, "you ought to have
it.
So the poor bastard had gone to the Other stroked the big leather
couch. The discomfort was due, in part at least, to the fact that the
summer, and the world, would ever end. But that morning when Anne
said that she wasn't accustomed to hear anything in pants talk like
that. Not that she didn't try to persuade me, but I got back, late at
night, and went to bed. The condom on the park path, the twitch in
the old bugger a little extra time before I popped the question to
him. He went out into the hal, Mr. Simms following. While Mr.
Simms locked the door, Cass said to him, for to fool. Well, this time
I'm going to fool somebody. I'm getting out of this race because you
admire his oratory."
"Ain't it?"
He didn't say anything to that.