lego

Solving the "ghost" word game.

Ghost is played as follows: First player names a letter. Each subsequent player adds a letter to the front or back of the word fragment so far. If a player names a word of at least four letters, she loses. If a player is challenged to name a word containing the fragment he produced, and cannot, he loses (otherwise the challenger loses.)

Example play: H -> GH -> GHO -> NGHO -> ONGHO -> challenge -> STRONGHOLD

Who wins with optimal play in two-player Ghost?

I wrote some code to find out. You can see it here: https://gist.github.com/mgritter/60514d8591b62cfc08f8fdf0bf020f11

Collapse )
lego

(no subject)

Here's the letter I sent my representative about just one part of the R tax plan:

Representative Lewis,

The recently released tax reform legislation proposes to tax the tuition waivers that graduate students receive as part of their teaching and research work. Currently up to $5,250 in tuition per year is exempt from taxation.

I am writing to express my concern about the impact this will have on students who can least afford it, and on education in Minnesota and the United States. I was a graduate student at Stanford, before working for a startup company and ultimately returning to Minnesota, where I had done my undergraduate studies. The paycheck I received for teaching assistantships and research assistantships was far less than I could have been earning in industry. It was a struggle to find housing that was affordable and yet close enough to campus that it didn't interfere with my studies. While I was not living in poverty, many students with families found it much harder to make ends meet.

I, at least, had low student debt and the prospect of high-paying employment in my field of study. I was also attending a prestigious university and a department that was well-funded.
A decade later, costs of attending college have gone up. Students who form the bulk of college and university teachers for the next generation face very difficult choices.

For a concrete example, Stanford's current minimum rate for a TA is $9,630 per quarter for half-time work. (The other half is, of course, dedicated to classes and research.) At $38,520/year under the Republican tax plan, the student would owe taxes on $22,320 salary and $10,260 of tuition waivers. At the 12% bracket this comes to $5,853 in federal income tax. More than one-fifth of that, $1,231, is due to tax on money that the graduate student never sees: it is paid by the university, to the university. $1000 is a lot of money to a graduate student, even at Stanford.

Adding to the tax burden of those at the very start of their careers, who may just be starting their families, can only discourage people from graduate education. But Minnesota needs a next generation of PhDs to train its students in science, mathematics, and the humanities. Our educational strength is a key driver of economic growth.

Mark Gritter
lego

Selecting Strings in Solidity

For a personal project implementing procedurally generated content on Ethereum, I would like to find the most efficient way to accomplish the following in Solidity:


if ( n == 0 ) {
buf.append( "unicorn" );
} else if ( n == 1 ) {
buf.append( "raven" );
} else if ( n == 2 ) {
buf.append( "sparrow" );
} else if ( n == 3 ) {
...


Solidity puts string literals in an inefficient binary encoding in the compiled format. In memory, there is one 256-bit integer for the string length, and then as many 32-byte memory chunks as are necessary to hold the string. In the compiled form this is somewhat better with a compact representation of the length, but a 256-bit big-endian number representing the string:


/* "src/testchoice.sol":790:813 buf.append( "unicorn" ) */
tag_42
0x40
dup1
mload
swap1
dup2
add
0x40
mstore
0x7 <== length
dup2
mstore
0x756e69636f726e00000000000000000000000000000000000000000000000000 <== string literal
0x20
dup3
add
mstore
/* "src/testchoice.sol":790:793 buf */
dup5
swap1
/* "src/testchoice.sol":790:813 buf.append( "unicorn" ) */
0xffffffff
/* "src/testchoice.sol":790:800 buf.append */
tag_43
/* "src/testchoice.sol":790:813 buf.append( "unicorn" ) */
and
jump // in


The next obvious thing to try is a literal array. This would have some disadvantages for the final design, but it might be more efficient in gas usage:


string[11] memory animals = [ "unicorn", "raven", "sparrow", "scorpion",
"coyote", "eagle", "owl", "lizard",
"zebra", "duck", "kitten" ];
buf.append( animals[n] );


And a somewhat less-obvious route is to efficiently pack the strings into a single literal, and then extract the portion that I need. (I have to implement my own string append function anyway.)


string memory animals = "unicornravensparrowscorpioncoyoteeagleowllizardzebraduckkitten";
if ( n == 0 ) {
buf.appendPacked( animals, 0, 6);
} else if ( n == 1 ) {
buf.appendPacked( animals, 6, 5 );
} else if ( n == 2 ) {
buf.appendPacked( animals, 11, 7 );
...


How do they compare? I compiled each version in isolation as part of a contract, and tested each for gas usage using Remix's Javascript VM (at https://ethereum.github.io/browser-solidity/)

nested if: code size 4460 bytes, gas costs 22710, 22548, 22602

static array: code size 4198 bytes, gas costs 24682, 24682, 24682

packed literal: code size 3676 bytes, gas costs 22798, 22879, 22744

The packing makes a big difference on code size, and it runs nearly as efficiently as the original. The static array is significantly more expensive, though it does provide some code size benefits.
lego

Plotting the Barnsley Fern in 1812?

The play "Arcadia" features a precocious young woman discovering fractal geometry (and the second law of thermodynamics in an amazing two-fer.) A contemporary mathematician explains that actually drawing a strange attractor by hand would require years and years of effort. Here's a sample fractal we can use for comparison, the Barnsley Fern: https://en.wikipedia.org/wiki/Barnsley_fern It's described by four linear transformations, which require four multiplications and up to six additions per application.

Logarithms are not a 19th-century invention. They're a 17th-century invention. So anybody who can add by hand can multiply quickly as well, through the use of a published book of logarithms. Because the ability to plot accurately by hand is limited too, we don't need very many digits of accuracy.

Here's the Barnsley Fern with just 2000 data points, clearly recognizable as a plant shape.

canvas.png

So how quickly could our 19th-century heroine compute these 2000 points? Slide rules had already been invented (though their modern form had to wait until 1859.) Sadly, I cannot come up with a good reference for the actual speed of human calculation on, say, 8-digit numbers such as Kepler performed. If we allow Thomasina a leisurely 1 minute per lookup, then she can perform about 7.5 iterations per hour of work. 2000 iterations are then 267 hours, or a mere seven modern work-weeks. Challenging to accomplish, but not impossible either for a dedicated worker.
lego

A Chomsky Hierarchy Puzzle

http://tracery.io/ is a tool to generate text. Its input is a mostly context-free grammar, and it outputs random instances of the language defined by that grammar.

Why only mostly context-free? Tracery has two special features. The first is that the outcome of a rule expansion can be saved for later, as a new rule.

So, for example, the grammar

{ 
  "origin":"[a:#letters#]#a# #a# #a#",
  "letters":["a","a#letters#"]
}


defines "letters" in a standard way as the regular language a, aa, aaa, aaaa, ... But when we expand "origin" we take whichever string of 'a's got generated and bind it to the new rule "a". So "origin" produces the language "a a a", "aa aa aa", "aaa aaa aaa", ...

Moreover, Tracery includes modifiers that can be applied to the expansion of a rule. Most are things like "capitalize the first letter" or "add -s or -es as appropriate." But Tracery 2 (the dev version, unfortunately not the one with the live editor) includes a "replace" modifer in the standard implementation. That lets us take the previous example a step further:

{ 
  "origin":"[a:#letters#]#a##a.replace(a,b)##a.replace(a,c)#",
  "letters":["a","a#letters#"]
}


Now this language is definitely not context-free. In fact, it's the canonical example of a context-sensitive language.

Here's the puzzle: is Tracery, or Tracery-with-replace, powerful enough to implement any context-sensitive language? How could we show that? If not, what is the class of languages that it can implement?
lego

The Puppy Functor

We introduce a finite category Pup. A standard representation is the objects {inside, outside} and in addition to the identities there are two morphisms that form a bijection:

door: inside -> outside
door -1: outside -> inside

The literature conventionally refers to these operations as "let the dog out" and "let the dog in", respectively.

A "puppy functor" P is defined as follows, and is applicable only to categories in which products exist:

P(S) = S x ( inside or outside )

P( 1S : S->S ) = f x 1

P(f : S->T ) = f x ( door or door-1 ) for all other morphisms

In the resulting category, any action must be accompanied by letting the dog outside or letting the dog back inside, as no function maps to the inside or outside identity. Further, any bijective morphism involves letting the dog out and then back in again (or the reverse), because

P(1) = P( ff -1 ) = P( f )P( f -1 )

Categories with endomorphisms (other than the identity, of course) cannot have a puppy functor. In fact, the only categories which have a puppy functor are those whose graphs are bipartite. The practical aspect of this restriction implies that dog owners cannot expect to perform any third task between letting the dog out and letting the dog back in.
lego

Back from Tintri sales kickoff

Tintri has historically held its sales kickoff in the Bay Area to be close to headquaters. This year we went to Las Vegas instead, at the Hard Rock Hotel and Casino. I don't like going to Las Vegas; among the reasons is cigarette smoke and the Hard Rock is no exception.

The Hard Rock's theme meant guitars everywhere. Literally propped up on some of the food serving tables.

Tintri's outside speakers this year were a little different. We had a performance by Butterscotch (a beatboxer) and talks by Vancouver social entrepreneur Mark Brand and filmmaker Nirvan Mullick, of "Caine's Arcade" fame. We participated in a Cardboard Challenge where we made games out of cardboard (and other items, like leftover party favors from the previous night.) You can see my team's two-person maze in action here: https://goo.gl/photos/Z66EprrvTFrugjfA8

Mark Brand made us all promise to leave the world better than we found it. The only other thing I can clearly remember from his speech, unfortunately, is that people keep wanting to show up and cook food for the homeless despite not actually knowing how to cook. I think he also had a few anecdotes about testing one's assumptions, and about not becoming a reality TV star.

Hard Rock has three poker tables which are often empty. They have a nightly 8pm $70 poker tournament that usually doesn't run. But the Tintri federal team showed up en masse so we had a fun time losing to one of the Tintri sales engineers. (A few other tourists showed up as alternates, and one of them chopped with Ronnie.) I busted in fourth after hitting an ace out of position against a set.

Tintri had a good year and there is encouraging news for the year to come. We won a partner award from CDW and they hope to expand their Tintri business, which is potentially very big. I harangued the Central region sales team to make more use of me--- last year I visited Wisconsin and Seattle, and had calls with customers in Chicago and Florida, but didn't meet any Minnesota, Iowa, Nebraska, or Missouri customers.
lego

Peter Thiel

Before the election, I thought that Peter Thiel's support for Trump was just Silicon Valley "disruptive" thinking at its worst. If the system isn't working, let's try something different (without a lot of thought as to whether it's actually better.) After all, Peter Thiel would not be the one suffering, so from his perspective it would be a risk-free experiment. He even tried making the case that we should take Trump seriously but not literally.

Foolishly, I did not realize that billionaires always have a hedge in place. In Thiel's case, it's citizenship in New Zealand, which he somehow in 2011 obtained despite not fulfilling a five-year residency requirement.
lego

Retiring another interview question

I've been talking to people who have built cloud services that communicate with on-premises equipment (like storage arrays or routers.) One of my questions has been: "can you give me an example of some difficulties, or customer requirements, that you've encountered about the device-to-cloud communication channel?"

The clearest sign of somebody who has not deployed to production is that they don't know of any, or the best they can come up with is "use a web proxy."

Here's my list, which I'm pretty sure is incomplete.

1. Some customers want to know the exact IP address and port you will connect to, and hard-code it in their firewall. Want to change cloud service providers? Forget it. Want to scale via DNS load balancing, or add a second server in Europe? Are you really going to go back and tell all those customers to open up more holes? Probably not.

2. Customers want you to use an HTTPS proxy. (No problem, everybody expects that.)

3. The HTTPS proxy is username and password protected. (No big deal.)

4. There are multiple ways to provide the username and password to the proxy. Are all of them supported? (Oops, we didn't turn on GSSAPI/Kerberos until a customer specifically requested it.)

5. Some customers install a proxy that spoofs HTTPS, so you get a certificate mismatch. Does your code give up at that point, or ignore the error and do application-level authentication and application-level encryption? (If so, what is the point of HTTPS? Well, some customers won't support HTTP going out.)

6. Some proxies support HTTPS but not WebSockets.

7. The customer wants you to use a web proxy, and also to configure that web proxy to only allow your box access to one server.

8. An isolated storage network is standard. Some customers put the admin interface on a separate network too. (This is not too different from having no access at all.)

9. Some proxies have maximum connection lifetimes or maximum request sizes configured.