Links #1

Links (pages I have enjoyed and you might too):

• http://googleresearch.blogspot.com/2015/06/inceptionism-going-deeper-into-neural.html

• http://languagelog.ldc.upenn.edu/nll/

• OMG the Word-Final Alveopalatals are Cray-Cray Prev

• Fry and Laurie

• http://slatestarcodex.com/2015/07/18/reverse-psychology/

• http://escapedynamics.com/wp-content/uploads/2015/05/Escape-Dynamics-External-Propulsion-WP.pdf

• Programming in assembly in order to speedrun Mario

• http://lesswrong.com/lw/20/the_apologist_and_the_revolutionary/

Random word: pipping

A Practical Introduction to Pyth, Part 1

Today, I executed the following piece of Python code:

assign('Q',eval(input()))
@memoized
def subsets(b):
 return neg([times(Plen(b),assign("J",reduce2(lambda b, Z:times(b,Z),end(Pchr(b))))),Psum(Pmap(lambda d:times(head(d),div(J,end(d))),b))])
@memoized
def gte(G,H):
 return ((subsets(Pmap(lambda d:gte(tail(G),minus(assign_at(d,assign("K",H),neg(1)),neg(Pnot(d)))),Plen(H))) if G else [0,1]) if (head(H) and Psum(tail(H))) else [T,T])
imp_print(reduce2(lambda b, Z:chop(b,Z),gte(head(Q),Psum(tail(Q)))))

This corresponds to the following Pyth code:

L_,*lbJ*FeCbsm*hd/JedbM?&hHstH?GymgtG-XdKH_1_!dlH,01,TTcFghQstQ

Pyth is a programming language which I created, and is deisgned for writing short programs. This program is a solution to the following challenge: http://codegolf.stackexchange.com/questions/53688/probability-to-clear-the-board-or-win

The challenge involves simulating a fairly simple game, and reporting the exact probability of victory. You can read about it at the link.

I'll be explaining exactly how the above Pyth code works, over the coming days.

Part 1: Prefix notation

Let's focus in on the following segment of the code:

*FeCb

The first thing to know about Pyth is that it uses Prefix Notation, also known as Polish Notation. This means 2 things:

1. A function comes before its arguments.
2. Function take a fixed number of arguments, known as their arity.

Because of the prefix notation, it makes the most sense to look at a piece of Pyth code from end to start.

Let's start with b. b is a variable, which functions are being called on. At this point in the code, b is a list of 2 element lists. Each sublist is representing a rational number, and this code is calculating the product of their denominators, or in other words the product of the second elements of each list. Let's suppose the following is the value of b:

[[3, 4], [10, 10], [0, 5]]

Next in the order from right to left is C. C takes one argument, and has a variety of uses, depending on the type of its argument. Since its argument, b, is a list, C performs a matrix transpose operation, making the first element of every list into a single list, then the second, and the third, and so on. Thus, in the example, Cb is the following:

[[3, 10, 0], [4, 10, 5]]

Next to the left is e. e also takes one argument, and its operation also depends on its argument. In fact, most functions in Pyth have different properties based on their arguments' types. e when called on a list returns the last element, making e the end function. Thus, eCb is:

[4, 10, 5]

Now comes something a bit unusual. This first two characters in the code snippet, *F, must be thought of as a unit. * is an arity two function which, as you might expect, multiplies its arguments together. F has a variety of uses, but when it appears immediately after an arity two function is the fold operator. It effectively "folds" the function just prior to it in between the consequtive elements of the sequence following it. You can learn more about folds at Wikipedia.

The result is equivalent to doing the following in an ordinary programming language:

4 * 10 * 5

Giving a result of 200, which is the product of the denominators, as desired.

Those 5 characters of Pyth code were compiled into the Python:

reduce2(lambda b, Z:times(b,Z),end(Pchr(b))

Well, we're 5 characters in, only 56 to go. More to come next time.

Skepticism

I remember reading an article one day, many years ago. It said something to the effect of "A recent study of ancient Roman sculptures by John Q. Thusandsuch has revealed that consistently, throughout history, humans have always considered moderation to be the most attractive. Neither too fat, too skinny, too tall or too short."

I then repeated this to my mother, who pointed out that it was obviously false.

At this point, I thought to myself two things. First, I immediately agreed that the article was obviously false. Second, I noticed that I had been taken in by the article. Some of the reasons that lead me to be taken in were:

1. Appearance of reputability: It was printed in a magazine, if I remember correctly.
2. Description of evidence: It mentioned some study.
3. Scientific overtones: ancient Roman sculptures examined and whatnot.
4. Pleasant/non-jarring conclusion: If it had concluded "And therefore, being under 4 feet tall is incredibly attractive", I would have noticed sooner.

The moral is, get to the facts of the matter. Hard evidence matters, and very little else does, unless no hard evidence can be found. In this case, I would have had to supply the hard evidence myself, but it still would have proven reliable.

The other moral is that it takes practice to actual judge assertions on their merits, and not on their overtones of truthiness. I'd encourage everyone to work on that sort of practice.

Magic Deck Prices

I play Magic: the Gathering. It has a lot of good aspects, but one of its worst aspects is its high prices. There are two major ways to play Magic: Limited and Constructed. In Limited, one opens a couple new packs of randomly assorted cards, makes a deck out of them, and plays a tournament with the result. As far as prices go, this is fairly reasonable.

The problem lies in Constructed. In Constructed, one brings a pre-constructed deck of their choosing to the tournament, and plays it. Due to the variance in power level and availibility of the various cards, the best decks can be quite expensive.

For example, in the most commonly played format, Standard, decks average about $300. Even worse, a given card is only legal in Standard for two years, and so a given deck typically only sticks together for a year. It's slightly better online, where the same decks only cost $200, but it's not much better.

Suppose you want your deck to stay legal for longer. The most commonly played eternal format is Modern, where a paper deck will run anywhere from $500 to $1800, with an average deck around $1000. The most expensive individual card in that format is Tarmogoyf, costing about $200 each. If every card in a deck was that expensive, the deck would cost $12,000.

While that amount seems unimaginable, but in one still popular format, Vintage, the decks average $15,000, and one individual card, Black Lotus, costs $4000.

There is a solution to this problem, however. The solution is Pauper. In Pauper, only the most common cards are legal, and once a card is legal, it stays legal forever. An average deck costs $10 to $50, but if you really push it, you can make an entire deck for under $1, like this one I made today: Golgari Persist, for 78 cents.

I've really enjoyed playing Pauper and Limited, and I think I'll continue in that system.

Simplify, always simplify

Today I learned:

Never overcomplicate your optimization techniques.

Today's code optimization challenge was to find the 30x30 Topelitz matrix with the largest determinant. I was silly, and implemented a genetic algorithm, then a breeding genetic algorithm, which gave me 6.1*10^13. Then, I used simple hill climbing, I got 6.5*10^13 on the first try, which I now believe is maximal. Simpler is better because you can try more simple thigns in the time it takes to try something complicated, and it's hard to guess which will be effective.

The resulting best matrix:

[[0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0]
 [0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1]
 [1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0]
 [0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0]
 [0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1]
 [1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0]
 [0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1]
 [1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1]
 [1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0]
 [0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1]
 [1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0]
 [0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0]
 [0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0]
 [0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0]
 [0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1]
 [1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1]
 [1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 1]
 [1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0]
 [0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0]
 [0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1]
 [1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1]
 [1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1]
 [1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0]
 [0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1]
 [1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1]
 [1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1]
 [1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0]
 [0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1]
 [1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0]
 [0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0]]