The Universe of Discourse

More fair cake-cutting

In a recent article about fair cake division, I said:

Grandma can use the same method … to divide a regular 17-gonal cake into 23 equally-iced equal pieces.

I got to wondering what that would look like, and the answer is, not very interesting. A regular 17-gon is pretty close to a circle, and the 23 pieces, which are quite narrow, look very much like equal wedges of a circle:

This is generally true, and it becomes more nearly so both as the number of sides of the polygon increases (it becomes more nearly circular) and as the number of pieces increases (the very small amount of perimeter included in each piece is not very different from a short circular arc).

Recall my observation from last time that even in the nearly extreme case of , the central angles deviate from equality by only a few percent.

Of particular interest to me is this series of demonstrations of how to cut four pieces from a cake with an odd number of sides:

I think this shows that the whole question is a little bit silly: if you just cut the cake into equiangular wedges, the resulting slices are very close in volume and in frosting. If the nearly-horizontal cuts in the pentagon above had been perfectly straight and along the !!y!!-axis, they would have intersected the pentagon only 3% of a radius-length lower than they should have.

Some of the simpler divisions of simpler cakes are interesting. A solution to the original problem (of dividing a square cake into nine pieces) is highlighted.

The method as given works regardless of where you make the first cut. But the results do not look very different in any case:

The original SVG files are also available, as is the program that wrote them.

[Other articles in category /math] permanent link

Incenters of chocolate-iced cakes

A MathOverflow post asks:

Puzzle 1: Grandma made a cake whose base was a square of size 30 by 30 cm and the height was 10 cm. She wanted to divide the cake fairly among her 9 grandchildren. How should she cut the cake?

Okay, this is obvious.

Puzzle 2: Grandma made a cake whose base was a square of size 30 by 30 cm and the height was 10 cm. She put chocolate icing on top of the cake and on the sides, but not on the bottom. She wanted to divide the cake fairly among her 9 grandchildren so that each child would get an equal amount of the cake and the icing. How should she cut the cake?

This one stumped me; the best I could do was to cut the cake into 27 slabs, each !!\frac{10}3×10×10!! cm, and each with between 1 and 5 units of icing. Then we can give three slabs to each grandkid, taking care that each kid's slabs have a total of 7 units of icing. This seems like it might work for an actual cake, but I suspected that it wasn't the solution that was wanted, because the problem seems like a geometry problem and my solution is essentially combinatorial.

Indeed, there is a geometric solution, which is more interesting, and which cuts the cake into only 9 pieces.

I eventually gave up and looked at the answer, which I will discuss below. Sometimes when I give up I feel that if I had had thought a little harder or given up a little later, I would have gotten the answer, but not this time. It depends on an elementary property of squares that I had been completely unaware of.

This is your last chance to avoid spoilers.

The solution given is this: Divide the perimeter of the square cake into 9 equal-length segments, each of length !!\frac{120}{9}!! cm. Some of these will be straight and others may have right angles; it does not matter. Cut from the center of the cake to the endpoints of these segments; the resulting pieces will satisfy the requirements.

“Wat.” I said. “If the perimeter lengths are equal, then the areas are equal? How can that be?”

This is obviously true for two pieces; if you cut the square from the center into two pieces into two parts that divide the perimeter equally, then of course they are the same size and shape. But surely that is not the case for three pieces?

I could not believe it until I got home and drew some pictures on graph paper. Here Grandma has cut her cake into three pieces in the prescribed way:

The three pieces are not the same shape! But each one contains one-third of the square's outer perimeter, and each has an area of 12 square units. (Note, by the way, that although the central angles may appear equal, they are not; the blue one is around 126.9° and the pink and green ones are only 116.6°.)

And indeed, any piece cut by Grandma from the center that includes one-third of the square's perimeter will have an area of one-third of the whole square:

The proof that this works is actually quite easy. Consider a triangle !!OAB!! where !!O!! is the center of the square and !!A!! and !!B!! are points on one of the square's edges.

The triangle's area is half its height times its base. The base is of course the length of the segment !!AB!!, and the height is the length of the perpendicular from !!O!! to the edge of the square. So for any such triangle, its area is proportional to the length of !!AB!!.

No two of the five triangles below are congruent, but each has the same base and height, and so each has the same area.

Since the center of the square is the same distance from each of the four edges, the same is true for any two triangles, regardless of which edge they arise from: the area of each triangle is proportional to the length of the square's perimeter at its base. Any piece Grandma cuts in this way, from the center of the cake to the edge, is a disjoint union of triangular pieces of this type, so the total area of any such piece is also proportional to the length of the square's perimeter that it includes.

That's the crucial property of the square that I had not known before: if you make cuts from the center of a square, the area of the piece you get is proportional to the length of the perimeter that it contains. Awesome!

Here Grandma has used the same method to cut a pair of square cakes into ten equal-sized pieces that all the have same amount of icing.

The crucial property here was that the square’s center is the same distance from each of its four edges. This is really obvious, but not every polygon has an analogous point. The center of a regular polygon always has this property, and every triangle has a unique point, called its incenter, which enjoys this property. So Grandma can use the same method to divide a triangular cake into 7 equally-iced equal pieces, if she can find its incenter, or to divide a regular 17-gonal cake into 23 equally-iced equal pieces.

Not every polygon does have an incenter, though. Rhombuses and kites always do, but rectangles do not, except when they are square. If Grandma tries this method with a rectangular sheet cake, someone will get shortchanged. I learned today that polygons that have incenters are known as tangential polygons. They are the only polygons in which can one inscribe a single circle that is tangent to every side of the polygon. This property is easy to detect: these are exactly the polygons in which all the angle bisectors meet at a single point. Grandma should be able to fairly divide the cake and icing for any tangential polygon.

I have probably thought about this before, perhaps in high-school geometry but perhaps not since. Suppose you have two lines, !!m!! and !!n!!, that cross at an acute angle at !!P!!, and you consider the set of points that are equidistant from both !!m!! and !!n!!. Let !!\ell!! be a line through !!P!! which bisects the angle between !!m!! and !!n!!; clearly any point on !!\ell!! will be equidistant from !!m!! and !!n!! by a straightforward argument involving congruent triangles.

Now consider a triangle !!△ABC!!. Let !!P!! be the intersection of the angle bisectors of angles !!∠ A!! and !!∠ B!!.

!!P!! is the same distance from both !!AB!! and !!AC!! because it is on the angle bisector of !!∠ A!!, and similarly it is the same distance from both !!AB!! and !!BC!! because it is on the angle bisector of !!∠ B!!.

So therefore !!P!! is the same distance from both !!AC!! and !!BC!! and it must be on the angle bisector of angle !!∠ C!! also. We have just shown that a triangle's three angle bisectors are concurrent! I knew this before, but I don't think I knew a proof.

[ Addendum 20191011: Many illustrated examples. ]

[Other articles in category /math] permanent link

Addenda to recent articles 201910

Several people have written in with helpful remarks about recent posts:

• Regarding online tracking of legislation:

  • Ed Davies directed my attention to www.legislation.gov.uk, an official organ of the British government, which says:

  The aim is to publish legislation on this site simultaneously, or at least within 24 hours, of its publication in printed form.

  M. Davies is impressed. So am I. Here is the European Union (Withdrawal) Act 2018.

  • Nik Clayton showed me the @unitedstates project, whcih among other things has a program that attempts to parse the United States Code and produce a tree-structured output.

  • Twitter user @sunk818 pointed out How I changed the law with a GitHub pull request. The title oversells what actually happened: the codified law contained a minor technical error, which could be corrected without requiring any actual legislation. But the takeaway is that the District of Columbia officially publishes its law to a Github repo.

  This then led me to Standardizing the World’s Legislative Information — One hackathon at a time on the LII's VOXPOPULII blog.

  (Reminder to readers: I do not normally read Twitter, and it is not a reliable way to contact me.)

• Regarding the mysteriously wide letter ‘O’ on the Yeadon firehouse. I had I had guessed that it was not in the same family as the others, perhaps because the original one had been damaged. I asked Jonathan Hoefler, a noted font expert; he agreed.

  But one reader, Steve Nicholson, pointed out that it is quite common, in Art Deco fonts, for the ‘O’ to be circular even when that makes it much wider than the other letters. He provided ten examples, such as Haute Corniche.

  I suggested this to M. Hoefler, but he rejected the theory decisively:

  True; it's a Deco mannerism to have 'modulated capitals'… . But this isn't a deco font, or a deco building, and in any case it would have been HIGHLY unlikely for a municipal sign shop to spec something like this for any purpose, let alone a firehouse. It's a wrong sort O, probably installed from the outset.

  (The letter spacing suggests that this is the original ‘O’.)

• Several people wrote to me about the problem of taking half a pill every day, in which I overlooked that the solution was simply the harmonic numbers.

  • Robin Houston linked to this YouTube video, “the frog problem”, which has the same solution, and observed that the two problems are isomorphic, proceeding essentially as Jonathan Dushoff does below.

  • Shreevatsa R. wrote a long blog article detailing their thoughts about the solution. I have not yet read the whole thing carefully but knowing M. Shreevatsa, it is well worth reading. M. Shreevatsa concludes, as I did, that a Markov chain approach is unlikely to be fruitful, but then finds an interesting approach to the problem using probability generating functions, and then another reformulating it as a balls-in-bins problem.

  • Jonathan Dushoff sent me a very clear and elegant solution and kindly gave me permission to publish it here:

  The first key to my solution is the fact that you can add expectations even when variables are not independent.

  In this case, that means that each time we break a pill we can calculate the probability that the half pill we produce will "survive" to be counted at the endpoint. That's the same as the expectation of the number of half-pills that pill will contribute to the final total. We can then just add these expectations to get the answer! A little counter-intuitive, but absolutely solid.

  The next key is symmetry. If I break a half pill and there are !!j!! whole pills left, the only question for that half pill is the relative order in which I pick those !!j+1!! objects. In particular, any other half pills that exist or might be generated can be ignored for the purpose of this part of the question. By symmetry, any of these !!j+1!! objects is equally likely to be last, so the survival probability is !!\frac1{j+1}!!.

  If I start with !!n!! pills and break one, I have !!n-1!! whole pills left, so the probability of that pill surviving is !!\frac1n!!. Going through to the end we get the answer:

  $$\frac1n + \frac1{n-1} + \ldots + 1.$$

• I have gotten feedback from several people about my Haskell type constructor clutter, which I will write up separately, probably, once I digest it.

Thanks to everyone who wrote in, even people I forgot to mention above, and even to the Twitter person who didn't actually write in.

[Other articles in category /addenda] permanent link

Neatness counts

I recently mentioned a citation listing on one of the pages of the United States Code at LII. It said:

(Pub. L. 85–767, Aug. 27, 1958, 72 Stat. 904; Pub. L. 86–342, title I, § 106, Sept. 21, 1959, 73 Stat. 612; Pub. L. 87–61, title I, § 106, June 29, 1961, 75 Stat. 123; Pub. L. 88–157, § 5, Oct. 24, 1963, 77 Stat. 277; Pub. L. 89–285, title I, § 101, Oct. 22, 1965, 79 Stat. 1028; Pub. L. 89–574, § 8(a), Sept. 13, 1966, 80 Stat. 768; Pub. L. 90–495, § 6(a)–(d), Aug. 23, 1968, 82 Stat. 817; Pub. L. 91–605, title I, § 122(a), Dec. 31, 1970, 84 Stat. 1726; Pub. L. 93–643, § 109, Jan. 4, 1975, 88 Stat. 2284; Pub. L. 94–280, title I, § 122, May 5, 1976, 90 Stat. 438; Pub. L. 95–599, title I, §§ 121, 122, Nov. 6, 1978, 92 Stat. 2700, 2701; Pub. L. 96–106, § 6, Nov. 9, 1979, 93 Stat. 797; Pub. L. 102–240, title I, § 1046(a)–(c), Dec. 18, 1991, 105 Stat. 1995, 1996; Pub. L. 102–302, § 104, June 22, 1992, 106 Stat. 253; Pub. L. 104–59, title III, § 314, Nov. 28, 1995, 109 Stat. 586; Pub. L. 105–178, title I, § 1212(a)(2)(A), June 9, 1998, 112 Stat. 193; Pub. L. 112–141, div. A, title I, §§ 1519(c)(6), formerly 1519(c)(7), 1539(b), July 6, 2012, 126 Stat. 576, 587, renumbered § 1519(c)(6), Pub. L. 114–94, div. A, title I, § 1446(d)(5)(B), Dec. 4, 2015, 129 Stat. 1438.)

My comment was “Whew”.

But this wouldn't have been so awful if LII had made even a minimal effort to clean it up:

• Pub. L. 85–767, Aug. 27, 1958, 72 Stat. 904
• Pub. L. 86–342, title I, § 106, Sept. 21, 1959, 73 Stat. 612
• Pub. L. 87–61, title I, § 106, June 29, 1961, 75 Stat. 123
• Pub. L. 88–157, § 5, Oct. 24, 1963, 77 Stat. 277
• Pub. L. 89–285, title I, § 101, Oct. 22, 1965, 79 Stat. 1028
• Pub. L. 89–574, § 8(a), Sept. 13, 1966, 80 Stat. 768
• Pub. L. 90–495, § 6(a)–(d), Aug. 23, 1968, 82 Stat. 817
• Pub. L. 91–605, title I, § 122(a), Dec. 31, 1970, 84 Stat. 1726
• Pub. L. 93–643, § 109, Jan. 4, 1975, 88 Stat. 2284
• Pub. L. 94–280, title I, § 122, May 5, 1976, 90 Stat. 438
• Pub. L. 95–599, title I, §§ 121, 122, Nov. 6, 1978, 92 Stat. 2700, 2701
• Pub. L. 96–106, § 6, Nov. 9, 1979, 93 Stat. 797
• Pub. L. 102–240, title I, § 1046(a)–(c), Dec. 18, 1991, 105 Stat. 1995, 1996
• Pub. L. 102–302, § 104, June 22, 1992, 106 Stat. 253
• Pub. L. 104–59, title III, § 314, Nov. 28, 1995, 109 Stat. 586
• Pub. L. 105–178, title I, § 1212(a)(2)(A), June 9, 1998, 112 Stat. 193
• Pub. L. 112–141, div. A, title I, §§ 1519(c)(6), formerly 1519(c)(7), 1539(b), July 6, 2012, 126 Stat. 576, 587, renumbered § 1519(c)(6), Pub. L. 114–94, div. A, title I, § 1446(d)(5)(B), Dec. 4, 2015, 129 Stat. 1438.

That's the result of s/; /<li>/g, nothing more.

(I wonder if that long citation at the end is actually two citations.)

[Other articles in category /IT] permanent link

The pain of tracking down changes in U.S. law

Last month when I was researching my article about the free coffee provision in U.S. federal highway law, I spent a great deal of time writing this fragment:

under the Federal-Aid Highway Act of 1978

I knew that the provision was in 23 USC §131, but I should explain what this means.

The body of U.S. statutory law can be considered a single giant document, which is "codified" as the United States Code, or USC for short. USC is divided into fifty or sixty “titles” or subject areas, of which the relevant one here, title 23, concerns “Highways”. The titles are then divided into sections (the free coffee is in section 131), paragraphs, sub-paragraphs, and so on, each with an identifying letter. The free coffee is 23 USC §131 (c)(5).

But this didn't tell me when the coffee exception was introduced or in what legislation. Most of Title 23 dates from 1958, but the coffee sign exception was added later. When Congress amends a law, they do it by specifying a patch to the existing code. My use of the programmer jargon term “patch” here is not an analogy. The portion of the Federal-Aid Highway Act of 1978 that enacted the “free coffee” exception reads as follows:

ADVERTISING BY NONPROFIT ORGANIZATIONS

Sec. 121. Section 131(c) of title 23, United States Code, is amended—
  (1) by striking out “and (4)” and inserting in lieu thereof “(4)”; and
  (2) by striking out the period at the end thereof and inserting in lieu thereof a comma and the following: “and (5) signs, displays, and devices advertising the distribution of nonprofit organizations of free coffee […]”.

(The “[…]” is my elision. The Act includes the complete text that was to be inserted.)

The act is not phrased as a high-level functional description, such as “extend the list of exceptions to include: ... ”. It says to replace the text ‘and (4)’ with the text ‘(4)’; then replace the period with a comma; then …”, just as if Congress were preparing a patch in a version control system.

Unfortunately, the lack of an actual version control system makes it quite hard to find out when any particular change was introduced. The code page I read is provided by the Legal Information Institute at Cornell University. At the bottom of the page, there is a listing of the changes that went into this particular section:

(Pub. L. 85–767, Aug. 27, 1958, 72 Stat. 904; Pub. L. 86–342, title I, § 106, Sept. 21, 1959, 73 Stat. 612; Pub. L. 87–61, title I, § 106, June 29, 1961, 75 Stat. 123; Pub. L. 88–157, § 5, Oct. 24, 1963, 77 Stat. 277; Pub. L. 89–285, title I, § 101, Oct. 22, 1965, 79 Stat. 1028; Pub. L. 89–574, § 8(a), Sept. 13, 1966, 80 Stat. 768; Pub. L. 90–495, § 6(a)–(d), Aug. 23, 1968, 82 Stat. 817; Pub. L. 91–605, title I, § 122(a), Dec. 31, 1970, 84 Stat. 1726; Pub. L. 93–643, § 109, Jan. 4, 1975, 88 Stat. 2284; Pub. L. 94–280, title I, § 122, May 5, 1976, 90 Stat. 438; Pub. L. 95–599, title I, §§ 121, 122, Nov. 6, 1978, 92 Stat. 2700, 2701; Pub. L. 96–106, § 6, Nov. 9, 1979, 93 Stat. 797; Pub. L. 102–240, title I, § 1046(a)–(c), Dec. 18, 1991, 105 Stat. 1995, 1996; Pub. L. 102–302, § 104, June 22, 1992, 106 Stat. 253; Pub. L. 104–59, title III, § 314, Nov. 28, 1995, 109 Stat. 586; Pub. L. 105–178, title I, § 1212(a)(2)(A), June 9, 1998, 112 Stat. 193; Pub. L. 112–141, div. A, title I, §§ 1519(c)(6), formerly 1519(c)(7), 1539(b), July 6, 2012, 126 Stat. 576, 587, renumbered § 1519(c)(6), Pub. L. 114–94, div. A, title I, § 1446(d)(5)(B), Dec. 4, 2015, 129 Stat. 1438.)

Whew.

Each of these is a citation of a particular Act of Congress. For example, the first one

Pub. L. 85–767, Aug. 27, 1958, 72 Stat. 904

refers to “Public law 85–767”, the 767th law enacted by the 85th Congress, which met during the Eisenhower administration, from 1957–1959. The U.S. Congress has a useful web site that contains a list of all the public laws, with links — but it only goes back to the 93rd Congress of 1973–1974.

And anyway, just knowing that it is Public law 85–767 is not (or was not formerly) enough to tell you how to look up its text. The laws must be published somewhere before they are codified, and scans of these publications, the United States Statutes at Large, are online back to the 82nd Congress. That is what the “72 Stat. 904” means: the publication was in volume 72 of the Statutes at Large, page 904. This citation style was obviously designed at a time when the best (or only) way to find the statute was to go down to the library and pull volume 72 off the shelf. It is well-deisgned for that purpose. Now, not so much.

Here's a screengrab of the relevant portion of the relevant part of the 1978 act:

The citation for this was:

Pub. L. 95–599, title I, §§ 121, 122, Nov. 6, 1978, 92 Stat. 2700, 2701

(Note that “title I, §§ 121, 122” here refers to the sections of the act itself, not the section of the US Code that was being amended; that was title 23, §131, remember.)

To track this down, I had no choice but to grovel over each of the links to the Statutes at Large, download each scan, and search over each one looking for the coffee provision. I kept written notes so that I wouldn't mix up the congressional term numbers with the Statutes volume numbers.

It ought to be possible, at least in principle, to put the entire U.S. Code into a version control system, with each Act of Congress represented as one or more commits, maybe as a merged topic branch. The commit message could contain the citation, something like this:

    commit a4e2b2a1ca2d5245c275ddef55bf8169d72580df
    Merge: 6829b2dd986 836108c2ba0
    Author: ... <...>
    Date:   Mon Nov 6 00:00:00 1978 -0400

        Surface Transportation Assistance Act of 1978

        P.L. 95–599
        92 Stat. 2689–2762
        H.R. 11733   

        Merge branch `pl-95-599` to `master`

    commit 836108c2ba0d5245c275ddef55bf8169d72580df
    Author: ... <...>
    Date:   Mon Nov 6 00:00:00 1978 -0400

        Federal-Aid Highway Act of 1978 (section 121)

        (Surface Transportation Assistance Act of 1978, title I)
        P.L. 95–599
        92 Stat. 2689–2762
        H.R. 11733

        Signs advertising free coffee are no longer prohibited
        within 660 feet of a federal highway.

    diff --git a/USC/title23.md b/USC/title23.md
    index 084bfc2..caa5a53 100644
    --- a/USC/title23.md
    +++ b/USC/title23.md
    @@ -20565,11 +20565,16 @@ 23 U.S. Code § 131. Control of outdoor advertising
     be changed at reasonable intervals by electronic process or by remote
     control, advertising activities conducted on the property on which
    -they are located, and (4) signs lawfully in existence on October 22,
    +they are located, (4) signs lawfully in existence on October 22,
     1965, determined by the State, subject to the approval of the
     Secretary, to be landmark signs, including signs on farm structures or
     natural surfaces, or historic or artistic significance the
     preservation of which would be consistent with the purposes of this
    -section.
    +section, and (5) signs, displays, and devices advertising the
    +distribution by nonprofit organizations of free coffee to individuals
    +traveling on the Interstate System or the primary system. For the
    +purposes of this subsection, the term “free coffee” shall include
    +coffee for which a donation may be made, but is not required.
    +
     *(d)* In order to promote the reasonable, orderly and effective 

Or maybe the titles would be directories and the sections would be numbered files in those directories. Whatever. If this existed, I would be able to do something like:

  git log -Scoffee -p -- USC/title23.md

and the Act that I wanted would pop right out.

Preparing a version history of the United States Code would be a dauntingly large undertaking, but gosh, so useful. A good VCS enables you to answer questions that you previously wouldn't have even thought of asking.

This article started as a lament about how hard it was for me to track down the provenance of the coffee exception. But it occurs to me that this is the response of someone who has been spoiled by plenty. A generation ago it would have been unthinkable for me even to try to track this down. I would have had to start by reading a book about legal citations and learning what “79 Stat. 1028” meant, instead of just picking it up on the fly. Then I would have had to locate a library with a set of the Statutes at Large and travel to it. And here I am complaining about how I had to click 18 links and do an (automated!) text search on 18 short, relevant excerpts of the Statutes at Large, all while sitting in my chair.

My kids can't quite process the fact that in my childhood, you simply didn't know what the law was and you had no good way to find out. You could go down the the library, take the pertinent volumes of the USC off the shelf, and hope you had looked in all the appropriate places for the relevant statutes, but you could never be sure you hadn't overlooked something. OK, well, you still can't be sure, but now you can do keyword search, and you can at least read what it does say without having to get on a train.

Truly, we live in an age of marvels.

[ Addendum 20191004: More about this ]

[Other articles in category /law] permanent link

Free coffee again

Last month I mentioned that, while federal law generally prohibits signs and billboards about signs within ⅛ mile of a federal highway, signs offering free coffee are allowed.

Vilhelm Sjöberg brought to my attention the 2015 U.S. Supreme Court decision in Reed v. Town of Gilbert. Under the Reed logic, the exemption for free coffee may actually be unconsitutional. The majority's opinion states, in part:

The Sign Code is content based on its face. It defines the categories of temporary, political, and ideological signs on the basis of their messages and then subjects each category to different restrictions. The restrictions applied thus depend entirely on the sign’s communicative content.

The court concluded that the Sign Code (of the town of Gilbert, AZ) was therefore subject to the very restrictive standard of strict scrutiny, which required that it be struck down unless the government could demonstrate both that it was necessary to a “compelling state interest” and that it be “narrowly tailored” to achieving that interest. The Gilbert Sign Code did not survive this analysis.

Although the court unanimously struck down the Sign Code, a concurrence, written by Justice Kagan and joined by Ginsburg and Breyer, faulted the majority's reasoning:

On the majority’s view, courts would have to determine that a town has a compelling interest in informing passersby where George Washington slept. And likewise, courts would have to find that a town has no other way to prevent hidden-driveway mishaps than by specially treating hidden-driveway signs. (Well-placed speed bumps? Lower speed limits? Or how about just a ban on hidden driveways?)

Kagan specifically mentioned the “free coffee” exception as being one of many that would be imperiled by the court's reasoning in this case.

Thanks very much to M. Sjöberg for pointing this out.

[Other articles in category /law] permanent link

How do I keep type constructors from overrunning my Haskell program?

Here's a little function I wrote over the weekend as part of a suite for investigating Yahtzee:

  type DiceChoice = [ Bool ]
  type DiceVals   = [ Integer ]
  type DiceState = (DiceVals, Integer)

  allRolls :: DiceChoice -> DiceState -> [ DiceState ]
  allRolls [] ([], n) = [ ([], n-1) ]
  allRolls [] _ = undefined

  allRolls (chosen:choices) (v:vs, n) =
      allRolls choices (vs,n-1) >>=
          \(roll,_) -> [ (d:roll,  n-1) | d <- rollList ]
            where rollList = if chosen then [v] else [ 1..6 ]       

I don't claim this code is any good; I was just hacking around exploring the problem space. But it does do what I wanted.

The allRolls function takes a current game state, something like

    ( [ 6, 4, 4, 3, 1 ], 2 )

which means that we have two rolls remaining in the round, and the most recent roll of the five dice showed 6, 4, 4, 3, and 1, respectively. It also takes a choice of which dice to keep: The list

    [ False, True, True, False, False ]

means to keep the 4's and reroll the 6, the 3, and the 1. The allRolls function then produces a list of the possible resulting dice states, in this case 216 items:

   [ ( [ 1, 4, 4, 1, 1 ], 1 ) ,
     ( [ 1, 4, 4, 1, 2 ], 1 ) ,
     ( [ 1, 4, 4, 1, 3 ], 1 ) ,
     …
     ( [ 6, 4, 4, 6, 6 ], 1 ) ]

This function was not hard to write and it did work adequately.

But I wasn't satisfied. What if I have some unrelated integer list and I pass it to a function that is expecting a DiceVals, or vice versa? Haskell type checking is supposed to prevent this from happening, and by using type aliases I am forgoing this advantage. No problem, I can easily make DiceVals and the others into datatypes:

    data DiceChoice = DiceChoice [ Bool ]
    data DiceVals   = DiceVals [ Integer ]
    data DiceState = DiceState (DiceVals, Integer)

The declared type of allRolls is the same:

    allRolls :: DiceChoice -> DiceState -> [ DiceState ]

But now I need to rewrite allRolls, and a straightforward translation is unreadable:

    allRolls (DiceChoice []) (DiceState (DiceVals [], n)) = [ DiceState(DiceVals [], n-1) ]
    allRolls (DiceChoice []) _ = undefined
    allRolls (DiceChoice (chosen:choices)) (DiceState (DiceVals (v:vs), n)) =
        allRolls (DiceChoice choices) (DiceState (DiceVals vs,n-1)) >>=
            \(DiceState(DiceVals roll, _)) -> [ DiceState (DiceVals (d:roll), n-1) | d <- rollList ]
              where rollList = if chosen then [v] else [ 1..6 ]

This still compiles and it still produces the results I want. And it has the type checking I want. I can no longer pass a raw integer list, or any other isomorphic type, to allRolls. But it's unmaintainable.

I could rename allRolls to something similar, say allRolls__, and then have allRolls itself be just a type-checking front end to allRolls__, say like this:

    allRolls :: DiceChoice -> DiceState -> [ DiceState ]                             
    allRolls (DiceChoice dc) (DiceState ((DiceVals dv), n)) =                        
        allRolls__ dc dv n                                                             

    allRolls__ [] [] n = [ DiceState (DiceVals [], n-1) ]                            
    allRolls__ [] _  _ = undefined                                                   
    allRolls__ (chosen:choices) (v:vs) n =                                           
        allRolls__ choices vs n   >>=                                                  
            \(DiceState(DiceVals roll,_)) -> [ DiceState (DiceVals (d:roll), n-1) | d <- rollList ]
              where rollList = if chosen then [v] else [ 1..6 ]            

And I can do something similar on the output side also:

    allRolls :: DiceChoice -> DiceState -> [ DiceState ]                             
    allRolls (DiceChoice dc) (DiceState ((DiceVals dv), n)) =                        
        map wrap $ allRolls__ dc dv n                                                  
          where wrap (dv, n) = DiceState (DiceVals dv, n)                              

    allRolls__ [] [] n = [ ([], n-1) ]                                               
    allRolls__ [] _  _ = undefined                                                   

    allRolls__ (chosen:choices) (v:vs) n =                                           
        allRolls__ choices vs n   >>=                                                  
            \(roll,_) -> [ (d:roll, n-1) | d <- rollList ]                               
              where rollList = if chosen then [v] else [ 1..6 ]   

This is not unreasonably longer or more cluttered than the original code. It does forgo type checking inside of allRolls__, unfortunately. (Suppose that the choices and vs arguments had the same type, and imagine that in the recursive call I put them in the wrong order.)

Is this considered The Thing To Do? And if so, where could I have learned this, so that I wouldn't have had to invent it? (Or, if not, where could I have learned whatever is The Thing To Do?)

I find most Haskell instruction on the Internet to be either too elementary

pet the nice monad, don't be scared, just approach it very slowly and it won't bite

or too advanced

here we've enabled the {-# SemispatulatedTypes #-} pragma so we can introduce an overloaded contravariant quasimorphism in the slice category

with very little practical advice about how to write, you know, an actual program. Where can I find some?

[Other articles in category /prog/haskell] permanent link

Typographical mysteries of Yeadon

Here are some pictures I took of the firehouse in Yeadon, PA.

(more images)

Every time I drive past this, I wonder: is that the original letter “O”? Or was there originally a narrow “O” that was lost or damaged, and which couldn't be replaced with a matching letter?

Here's the Google Street View version, from November 2016. The letters are painted green, but the “O” is still the circular one.

[ Addendum 20191004: More about this ]

[Other articles in category /IT/typo] permanent link

Why no disco balls

A couple of months ago I asked why the disco ball had to wait until the 20th century:

The 17th century could produce mirrors by gluing metal foil to the back of a piece of glass, so I wonder why they didn't. They wouldn't have been able to spotlight it, but they certainly could have hung it under an orbiculum. Was there a technological limitation, or did nobody happen to think of it?

I think the lighting issue is the show-stopper. To make good use of a disco ball you really do need a dark room and a spotlight. You can get reflections by hanging the ball under an orbiculum, but then the room will be lit by the orbiculum, and the reflections will be pale and washed out, at best.

Long ago I attended a series of lectures by Atsushi Akera on the hidden prerequisites for technological adoption. For example, you can't have practical skyscrapers without also inventing elevators, and you can't have practical automobiles without also inventing windshield wipers. (And windshields. And tires. And … )

This is an amusing example of the same sort. You can't have practical disco balls without also inventing spotlights.

But now I kinda wonder about the possibility of wowing theatre-goers in 1850 with a disco ball, lit by a sort of large hooded lantern containing a limelight and a (lighthouse-style) Fresnel lens.

[ Addendum: Apparently, nobody but me has ever used the word “orbiculum”. I don't know how I started using it, but it seemsthat the correct word for what I meant is oculus. ]

[Other articles in category /tech] permanent link

Benjamin Wade

Yesterday Katara asked me about impeachment, and in mentioning the impeachment of Andrew Johnson, I realized that I didn't know who would have assumed the presidency, had Johnson been convicted. Who was Johnson's vice president?

Well, I couldn't remember because he didn't have one. Until the ratification of the 25th Amendment in 1967, there was no provision for the replacement of a vice-president except through a normal election.

Under the Presidential Succession Act of 1792, next in line was the President Pro Tempore of the Senate. This is a largely ceremonial position, filled by a senator, and elected by the Senate. The President Pro Tempore in 1868 was Benjamin Wade, senator from Ohio. Wade, as a senator, would be voting on Johnson's conviction and therefore had an enormous conflict of interest: if Johnson was removed, Wade would assume the presidency.

There were calls for Wade to abstain from voting. Which he did. Not! Ha ha, of course he didn't. He voted to convict.

The conviction, famously, fell short by one vote: it went 35–19 in favor of conviction, but they needed 36 votes to convict. Suppose it had gone 36-18, with Wade's vote being the 36th, and Wade taking over the presidency as a result? Wikipedia claims (with plausible citation) that at Wade told at least one other senator what cabinet position he could expect to receive in exchange for his vote to convict.

1. How could those 1792 folks not have foreseen this? Sheesh.

2. Government is hard. Really, really hard.

3. Thinking about the Civil War era of U.S. history, I always have ambivalent feelings. First, hope and relief: “Our current situation could be much worse than it is”, followed by dread: “Our current situation might get much worse than it is”.

[ Maybe I should also mention that many sources suggest that Johnson would have been removed had his successor been someone less divisive than Wade. ]

[Other articles in category /politics] permanent link

Breaking pills

Suppose you have a bottle that contains !!N!! whole pills. Each day you select a pill at random from the bottle. If it is a whole pill you eat half and put the other half back in the bottle. If it is a half pill, you eat it. How many half-pills can you expect to have in the bottle the day after you break the last whole pill?

Let's write !!E(N)!! for the expected number of half-pills. It's easily seen that !!E(N) = 0, 1, \frac32!! for !!N=0,1,2!!, and it's not hard to calculate that !!E(3) = \frac{11}{6}!!.

For larger !!N!! it's easy to use Monte Carlo simulation, and find that !!E(30)!! is almost exactly !!4!!. But it's also easy to use dynamic programming and compute that $$E(30) = \frac{9304682830147}{2329089562800}$$ exactly, which is a bit less than 4, only !!3.994987!!. Similarly, the dynamic programming approach tells us that $$E(100) = \frac{14466636279520351160221518043104131447711}{2788815009188499086581352357412492142272}$$ which is about !!5.187!!.

(I hate the term “dynamic programming”. It sounds so cool, but then you find out that all it means is “I memoized the results in a table”. Ho hum.)

As you'd expect for a distribution with a small mean, you're much more likely to end with a small number of half-pills than a large number. In this graph, the red line shows the probability of ending with various numbers of half-pills for an initial bottle of 100 whole pills; the blue line for an initial bottle of 30 whole pills, and the orange line for an initial bottle of 5 whole pills. The data were generated by this program.

The !!E!! function appears to increase approximately logarithmically. It first exceeds !!2!! at !!N=4!!, !!3!! at !!N=11!!, !!4!! at !!N=31!!, and !!5!! at !!N=83!!. The successive ratios of these !!N!!-values are !!2.75, 2.81,!! and !!2.68!!. So we might guess that !!E(N)!! first exceeds 6 around !!N=228!! or so, and indeed !!E(226) < 6 < E(227)!!. So based on purely empirical considerations, we might guess that $$E(N) \approx \frac{\log{\frac{15}{22}N}}{\log 2.75}.$$

(The !!\frac{15}{22}!! is a fudge factor to get the curves to line up properly.)

I don't have any theoretical justification for this, but I think it might be possible to get a bound.

I don't think modeling this as a Markov process would work well. There are too many states, and it is not ergodic.

[ Addendum 20190919: Ben Handley informs me that !!E(n)!! is simply the harmonic numbers, !!E(n) = \sum_1^n \frac1n!!. I feel a little foolish that I did not notice that the first four terms matched. The appearance of !!E(3)=\frac{11}6!! should have tipped me off. Thank you, M. Handley. ]

[ Addendum 20190920: I was so fried when I wrote this that I also didn't notice that the denominator I guessed, !!2.75!!, is almost exactly !!e!!. (The correct value is !!e!!.) I also suspect that the !!\frac{15}{22}!! is just plain wrong, and ought to be !!e^\gamma!! or something like that, but I need to take a closer look. ]

[ Addendum 20191004: More about this ]

[Other articles in category /math] permanent link

The straight man comes first

Today it occurred to me that in the many comedy duos that feature a “straight man” and a “comedian”, the straight man is invariably named first. The central example, of course, is Abbott and Costello. But we also have:

• Laurel and Hardy
• Burns and Allen
• Rowan and Martin
• Martin and Lewis
• Bert and Ernie

and this even extends to entirely fictitious pairs such as Jeeves and Wooster, Harold and Kumar, or Sam and Max, Freelance Police. Also, if you are a mathematician, Smothers and Smothers. This is why people hate mathematicians.

I did Google search for "Kermit and Fozzie" (hits outnumber "Fozzie and Kermit" by around three-to-one) and "Kermit and Miss Piggy" (hits outnumber "Miss Piggy and Kermit", although only by about 60%.)

Wikipedia says this is no accident!

In vaudeville, effective straight men were much less common than comedians. The straight man's name usually appeared first and he usually received 60% of the take.

But my co-worker Jeff Culverhouse found a counterexample: Silent Bob is certainly the straight man of Jay and Silent Bob.

Wikipedia also has a list of American Comedy Duos. Not all of them follow the straight man / comedian pattern, and I don't recognize many of those that do. More research is needed.

[ Addendum: I wanted to find a gender-neutral term for "straight man", but failed. ]

[Other articles in category /misc] permanent link