Note that the title of this post is not: “Bridge is an easy game.” Bridge is not an easy game. It’s not the mental switch off that something like Apples to Apples is. But contract bridge has a simple, elegant structure, where you can learn the rules in a single session and spend a lifetime trying to get better. Here is my attempt at a straightfoward description of the rules that should allow 4 people who have never played before to try it.
Bridge is played by four people in two partnerships. Partners sit opposite each other at a square or round table. A standard deck of cards is used with 13 cards: A,K,Q,J,10-2 in 4 suits: ♠,♥,♦,♣: Spades, Hearts, Diamonds, and Clubs
If anonymous players are needed, they are often referred to by the compass directions N, E, S, W. North and South are partners, and East and West are partners.
An additional deck can be used to shuffle one deck while another is used.
Bridge is played as a series of hands. One person deals each hand, and the person to their left deals the next hand. A hand consists of two phases, an auction, and the play of the hand. The score for the hand is calculated after the play. The auction results in a contract which affects both the scoring and the play of the hand.
The deck is dealt completely to 4 players, 13 cards to each player.
The core of bridge is the trick. Each player plays a single card in clockwise order. The player who chooses the first card is said to have the lead. They can choose any of the remaining cards in their hand to play. The next 3 players are required to follow suit if possible. That is, if they have a card of the same suit as the card lead, they must play a card of that suit. Failure to do so is called a revoke.
Bridge was invented by a series of improvements on existing games. It’s best learned as a series of small additions to a simple game, which we’ll call Follow Suit:
Deal the cards. The person to the left of the dealer makes the opening lead. They play the first card. The person that plays the highest card in a trick of the suit lead wins the trick. Their partnership gets credit for the trick. One person from each partnership should collect the tricks for their side. The winner of the trick gets to lead to the next trick. Play all 13 tricks. The side with the most tricks wins one point for each trick over 6. First team to 5 points wins.
Counting only the tricks after six is strange. The tricks over six are called “odd tricks”. If you think about it, it makes a certain sense. You only get credit for taking more tricks than the opponenents. If you have 7 tricks and they have six, you have beaten them by 1 trick. Each trick you take after that counts as an additional odd trick. 7 odd tricks would mean taking all the tricks and keeping the opponents from taking any. The first six tricks are referred to as book.
Not The Donald. A trump is a high-powered suit. When there’s a trump suit, the rules of winning a trick change slightly. If someone is out of a suit and plays a trump, then the highest trump played wins. Trumps are straightforward. They give rise to a lot of strategies, but trumps themselves are straightforward.
We’ll call this game Trumps. Play proceeds as in Follow Suit, with the following change. The last card should be dealt to the dealer face up. That suit is now trumps. Play and scoring is the same as in Follow Suit
On every hand of bridge, one player is the dummy. After the opening lead, the dummy puts their hand on the table in 4 columns facing their partner. Dummy’s partner is called the declarer. They should put the trump suit on their right and Declarer’s left, and alternate the suits between red and black. The dummy doesn’t play without instruction from their partner. Not even if there’s only one card left. Dummy should also refrain from giving hints. On dummy’s turn to play, declarer instructs dummy which card to play.
Play and scoring is the same as in Trumps, except that after the opening lead, dealer’s partner puts down their hand, and dealer becomes the declarer.
If your side could choose the trump suit, you’d likely take more tricks than if it was picked at random, or if the opponents picked the trump suit. Both sides would like this privilege, and they compete in an auction for it.
The dealer starts the auction. When it is a player’s turn in the auction they may:
A bid consists of a number of odd tricks and a suit or “No Trump” (NT). The side that makes the last bid gets the trump suit they bid, and they must take the number of odd tricks that they bid.
For the purposes of bidding, the suits and NT are ranked. From lowest
to highest, they are:
♣, ♦, ♥, ♠, NT.
If you choose to bid, it must be either a higher suit or NT than the previous bid, or more odd tricks than the previous bid. This means that the lowest bid is 1♣, and the highest bid is 7NT
The auction ends after either 4 initial passes, called a pass out, or once someone has bid, after 3 passes in a row.
The last bid determines the contract.
A contract is 4 pieces of information:
A contract is written in the order above. Some example contracts:
The declarer is the person on the winning team that first bid the suit. If the contract is NT, it is the person that first bid NT.
Deal the cards and have an auction. Dealer gets the first chance to bid. If there is a pass out, no one gets any points, deal the next hand. The person to the left of the declarer makes the opening lead. Declarer’s partner is the dummy. See if you made your contract. Don’t try and score the hand using full bridge scoring, just see if you made your contract.
The first thing that you need to know about bridge scoring is that you play a rubber which is a race to get two games. Rubber is an old english word meaning tie-breaker. Whenever one team wins two games, the rubber is over.
In bridge you collect points as you try to get to two games. The partnership to win two games gets a substantial bonus, so they usually win the rubber, but it’s not guaranteed.
If you take the number of tricks in the contract, you made your contract. If you take any extra tricks, they are called overtricks. If you didn’t make your contract, each trick that you were short is called an undertrick.
Points that count towards game are written below the line and other points are written above the line. If you make your contract, your contract score goes below the line, and any overtricks go above the line. Tricks are scored as follows: For ♣ or ♦, each odd trick is 20 points. For ♥ or ♠, each odd trick is 30 points. For NT, the first odd trick is 40 points, and the following tricks are 30 points each.
Once you have won a game, you are called vulnerable. Being vulnerable changes the award the opponents get for each undertrick. This helps prevent a blocking strategy where a partnership with one game outbids the opponents and goes down so they can get their second game. Undertricks give points to the opponents above the line. Each non-vulnerable undertrick costs 50 points, and a vulnerable undertrick costs 100 points.
Some examples: No one is vulnerable. The contract is 2♥, North was
the declarer. N-S took 10 tricks. N-S get 60 points below the line and
60 above.
No one is vulnerable. The contract is 4♦, E is the declarer. E-W take 8
tricks. N-S get 100 points above the line.
No one is vulnerable. The contract is 3NT. South is the declarer. N-S
took 9 tricks. N-S get 100 points below the line and no points above the
line. N-S are now vulnerable. N-S are vulnerable. The contract is 2♠.
North is the declarer. N-S took 7 tricks. E-W get 200 points above the
line.
It is eventually important to understand how doubling and redoubling raises the stakes, but initially it’s fine to look it up if you end up playing a doubled or redoubled contract. The one important thing to remember is that doubling and re-doubling actually doubles and redoubles the contract score. So making 2♥X gives you some number of points above the line, and 120 below the line. Making 1♠XX also gives you some number of points above the line and 120 below.
The team that wins two games gets the rubber bonus. The rubber bonus is 700 points if the opponents won no games, and 500 points if the opponents have won one game.
There is also a bonus for bidding and making a contract of 6 or 7. A contract of 6 is called a small slam and a contract of 7 is called a grand slam.
If you are non vulnerable, a small slam is 500 points and a grand is 1000. If you are vulnerable the bonuses are 750 and 1500.
Haskell has a nice type-safe formatting library called formatting.
Underlying it is a bunch of interesting category theory that you don’t
need to know to use the library. It takes advantage of the
OverloadedStrings extension to allow you to write something
like this:
{-# LANGUAGE OverloadedStrings #-}
module Main where
import Formatting
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Lazy as TL
who :: T.Text
who = "world"
main :: IO ()
main = T.putStrLn $ TL.toStrict $ format ("Hello, " % stext % "!") whoNote that using the formatting with the API is a little awkward. We
can improve it by using sformat:
main = T.putStrLn $ sformat ("Hello, " % stext % "!") whoWe can improve it further by using the function fprintLn
supplied by the formatting package:
main = fprintLn ("Hello, " % stext % "!") whoI recently added a nice combinator to make it easier to add
formatting to other APIs. It’s always possible to write a function like
fprintLn above, but if you have a lot of functions that are expecting a
text value (like logging at different levels), it would be a pain to
write a formatted version of each of them. I
wrote a formatted combinator that’s really easy to
use:
main = formatted T.putStrLn ("Hello, " % stext % "!") whoIf you’re doing a lot of formatting, it may make sense to define a specific function, but it’s nice to be able to just drop in formatting somewhere with an additional keyword.
Several years ago, I wanted to write something in Haskell that was a bit bigger than the toys that I had written. I wanted something that did some non trivial IO and some amount of logic. I decided I would write a BitTorrent tracker. You can find it with my most recent updates on github
BitTorrent is still in use, but it isn’t in as popular and isn’t in the news nearly as much. BitTorrent is a peer to peer file sharing protocol that sends a file in chunks, and people connect to peers to get the chunks. It’s common for ISO’s to have torrent links in addition to HTTP downloads. The purpose of a tracker is to help peers find each other. The tracker keeps an associative map between hosts and torrent hashes. It’s important that the tracker only has the hash of a torrent file. They don’t have the file and they don’t know what is in it.
The tracker protocol is essentially a small web service. It doesn’t follow REST principles. There are 2 types of @GET@ requests: @announce@ and @scrape@. An announce request registers a status update of a host, peer, that is interested in a given torrent hash. A peer makes an announce request when it starts downloading, when it completes downloading, and if it is no longer participating in a torrent. In response, the tracker returns a list of peers that are requesting the same torrent hash. Scrape requests ask for information about how many different peers are interested in a given torrent hash, how many are actively downloading, how many are seeding the torrent.
The UDP protocol is a simple request response protocol with a trick to prevent amplification. First a client must make a connection, and the server returns a connection id. The connection id must be supplied along with any further connection ids. The standard requests that a tracker answers all have corresponding binary UDP requests. They use a standard trick of using the same header for all requests, including connection requests, and then allowing the suffix to vary based on the type of request.
The core server is written to take algebraic data types to algebraic data types. For example the core server functions have the types
handleAnnounce :: AnnounceRequest -> AnnounceT AnnounceResponse
handleScrape :: IpVersion -> [ScrapeRequest] -> AnnounceT [ScrapeResponse]where AnnounceT wraps some state and IO. We pass the
IpVersion to handleScrape because we treat Ipv4 and Ipv6 as
completely separate trackers.
This made implementing both the UDP Protocol and the web protocol straightforward. Most of the work is parsing and serializing the binary protocol and only a small amount of logic is specific to either HTTP or UDP.
BitTorrent has a system of encoding callled Bencoding. I implemented a type class for serializing to the encoding. This means that we don’t have to create an intermediate value before serializing, we can serialize directly. In order to make it easier to test, I also implemented the intermediate value, and I made it implement the typeclass. This means that you can write a serialization instance, and it doesn’t need to go through an intermediate value, but you can take the same code and have it produce an intermediate value if you want to verify that it is serializing correctly.
Another thing that I did was to use a church encoded
EitherT type in the web portion. The type has two
continuations, one for success and the other for failure. For chained
computations this avoids re-evaluating the tags on an
Either value. Yes, this was premature optimization. This is
a learning project, and this was interesting to me.
Overall, this was a really useful exercise. I learned a lot about
Data.Binary There are other libraries that are faster for
binary serialization and deserialization, but they all work similarly. I
got to use type families and GADTs for the Bencoding. I solved a real
problem that needed to do real IO including sockets. The
ByteString socket library is really nice, and Haskell’s green
threading and asynchronous IO make using sockets look like C, but
cleaned up. Looking at the code years later, I am still pretty happy
with the code. To be production ready it would need more work, with
things like logging and config files, but I am still pretty happy with
it.
While I was working for Pyrofex, we ran into an interesting problem that could be solved with an Online Tree Hashing mode.
An online hashing mode is one where the data can be streamed into the function and a hash can be calculated without storing the data until the end is reached. Standard linear hashing is online. Except for the parallel implementations, most of the Blake2 tree modes are not online.
Tree modes are usually applied to break up a single piece of data into a hash tree so that updating the hash in response to changes in the data is fast.
In our case we were building the tree structure online. In parallel, new leaf nodes could be created and an arbitrary number of leaf messages could be merged. At any point we could take a node and ask for the final root hash associated with its subtree and any data processed at that node until now.
We wanted to guarantee that the new hashing mode that we were creating would be safe against collisions and extension attacks. For our application we only really needed to protect against collisions, but I wanted the mode to be general and usable in cases that needed protection against extension attacks.
The standard for safety of a hash mode is the paper “Sufficient conditions for sound tree and sequential hashing modes”, by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche.
Tree hash modes use an inner hash function Fn
The paper lists three criteria for a hash mode to be sound:
The mode is Tree-Decodable
This is technical, but the gist is that it should be impossible to construct identical inputs to Fn given two differently shaped trees.
The mode is Message-Complete
This is easy to grasp, as it means that all of the message bits are fed into Fn at some point. If they aren’t, it’s easy to construct a collision (change the bits that are never fed in)
The mode is Final-Node-Separable
The gist of this property is that the final output from the root of the tree cannot be re-used as a chaining value for a larger tree. This is a generalization of extension attacks. Extension attacks matter for keyed hashing like HMAC, but not for public hashing like SHA1. HMAC is a construction from a hash function specifically to prevent extension attacks.
At any point in time, we have a set N of nodes. For each of these nodes, its children if any have already been completely processed, and their chaining values have been processed as well. We have four operations we can do to the set of nodes.
A node is represented as a Blake2 Hash Context. Blake2 is initialized with tree parameters that we bend to fit our application.
Feeding data to a node is simply feeding data into the Hash Context.
To introduce a new leaf node, we simply create a new hash context with the following parameters:
Merging is similar to above, but we set the fanout parameter to the number of child hashes. For each of them, we extract an internal final hash and feed it into the new hash context. For simplicity, we 0 pad the child hashes to a full block, but this doesn’t affect security either way.
In the code that I wrote, with more than 255 children, we just create parents in a loop. I should have done this differently, as it is a security flaw. A simple solution would be to pad the last block with ones if we are merging for more than 255 children. This would make the padding a necessary part of security, but only for exactly 255 children.
To ask a node for its final state, we use Blake2 finalization, but we set both f0 and f1. This distinguishes an internal nodes final state and a root node’s final state. Note that to prevent extension attacks, no internal chaining value can be disclosed.
Message Completeness is easy. We hash all the data that we care about, so our mode is message complete.
Final Node Separability is pretty easy as well. By using the f1 flag only on the final root hash, we guarantee that it can’t be used as an internal node for some larger tree.
Tree Decodability is a little harder to see. Assuming we never merge more than 255 nodes, then the fanout parameter prevents someone from constructing a node that differs in tree structure. You can feed the same data, but the parameters, which form the first block of data, will be different for different tree structures.
I don’t know if there is an application for a mergeable and splittable random number generator outside of our particular application. It was useful in our particular application, and I’m proud of it. In our application, we were generating 256 bit strings to be used as identifiers. We didn’t need any more collision resistance than this, so we used 256 bit internal chaining values. If you are using this to actually hash a tree and not as a PRNG, then your internal chaining value size should match your result value size.
I’ve been interviewing, and one thing that I have found interesting are take home problems. I’ve seen them in so many different forms, and I have done most of them. I did a lot of interviewing at Google, and I grade the take home problem that my current company gives. I wanted to give an overview of the different things that I’ve seen, and then my opinion on what companies should and shouldn’t do.
The first big variable that I have seen is the build environment. There are two broad categories: A controlled environment with a web IDE, or letting the candidate do it on their own. Each type has pros and cons.
These environments lend themselves to shorter timescales and easier grading of the solutions. Because the environment is already set up and ready to go, the candidate can dive right in on the problem. There’s no need to set up the build tooling to go with a problem, or set up version control (the web client can keep an edit history). This means that the candidate needs to allocate less time to the problem. It is also easier to grade the test, as it was written in the same environment where it would be run.
A big con is the lack of a REPL, and the fixed set of libraries. Many languages allow you to interact with the code by writing snippets of code to be evaluated and printed. This is really useful for checking your code before writing a formal unit test. Web environments usually don’t allow this, and they only have a run and submit button. In some ways by fixing the library and hiding the REPL, you are hobbling a language that you are asking the candidate to use. One example problem I solved, I wanted to use NumPy, but it wasn’t available. This is completely unrealistic. There are very few professional circumstances where you would choose Python but prohibit NumPy
I had a really negative experience with Codility. Maybe it would be better if the company had supplied more example tests, but if one of your solutions fails, you don’t have the ability to go back and edit the code. I had over an hour left on my timer. This is completely unrealistic. In ACM competitions for example, if your code fails, they tell you that it fails, but not why. You can then work on it and resubmit.
This gives the candidate much more freedom in terms of libraries and using the REPL. It also introduces many more vagaries into the problem:
I will suggest my answers to these problems. They may not work in a particular case, like if you want to give a Windows or Mac specific take home problem, but in the modern world, enough of the take home problems can be run this way that this advice should work for the overwhelming majority.
Code should be submitted via a webpage as a tarball. In addition to
any other documentation or build instructions, the code should contain a
Dockerfile. This solves both the problem of how to run the code, and the
problem of whether it will run in your environment. Tell the candidate
about the size of the VM that will run their code. Upon submission,
automatically run the code by creating a VM for security, and then in
the VM
docker build -t <tag> && docker run --rm -i tag < input > output
A second best option for this problem is to rely on a language specific package manager. Haskell has cabal, NodeJS has npm, python has pip. This isn’t as repeatable as Docker however. If it’s automated, or if you have at least reasonable feedback loops on code that won’t run in your environment, this isn’t a dealbreaker.
Only one take home problem that I was given specifically asked for unit tests. Asking for unit tests work better in an uncontrolled environment. In a controlled environment, you are essentially supplying the unit tests. If you are doing this, please supply a variety rather than a single example. There is a tradeoff in asking for unit tests. It does make the problem more like real work. However, it makes the problem longer, and there is a limit to how much time it is reasonable to ask a candidate to spend on a take home problem.
In addition to asking for unit tests, I was asked that my code be well documented. I was writing Haskell for this particular problem, so I added Haddock comments on all top level definitions and all arguments. One of the problems with asking for documentation is that in many ways, the problem statement is the documentation. What’s left to document is basically comments about the code and its internals. The externals are specified by the problem. As with unit tests, asking for this works better in an unconstrained environment.
There are two kinds of feedback that a candidate needs: Their code doesn’t run in your environment, and a complete grading of their code. Ideally the running of their code in your environment would be automated, so they can resubmit quickly. Retain their original solution so you can grade them on what changed. Changing the build files is better than changing the actual code. If it’s not automated, you should ensure that the recruiter knows how to run but not grade the solutions, and that the candidate gets timely feedback about whether their solution worked in your environment.
Do you want the candidate to write the code in whatever language they are most comfortable with, or do you want them to use one of the languages that your company uses? My preference would be to allow the candidate to choose, but that can be overridden by circumstances. At Google, we said that interviewing was trying to give the candidate an opportunity to shine, not to plumb the depths of their ignorance. If you will be teaching the candidate the language (you use a niche language), then let them solve it however. If you want to verify that a candidate is comfortable with the language they will be using if they get the job, go with that. If you go this route, pin it to exactly that language.
If a candidate’s code runs successfully, and meets other criteria like performance, then you should review it. If the code passes review (review should be liberal due to time constraints), you could discuss the code in at least one interview. If the problem is smallish and being used as a standalone screen, then you don’t need to discuss it in an interview. Skipping the discussion makes more sense if you are using a constrained, automated environment.
There are several reasons to give candidates a bounded amount of time to complete the problem. For hiring efficiency, you want to give them a bounded amount of time to begin the problem. You don’t want to let a candidate string you along. Two weeks to begin the problem is probably a maximum. The constrained environments automatically take care of timing the candidate by giving them a fixed amount of time to solve the problem.
For an unconstrained environment, you should give the candidate an expected amount of time, and a bounded time window. If you think the problem should take 4 hours, then you should tell the candidate this. You should have them start when they feel they have that much time available, but you should give them a bigger window to submit their solution, like 24 hours. You can request that they submit their code as a git repository for timestamps. If you want timestamps, have them create an initial commit as soon as they start. Yes a candidate can game this, but most won’t.
The reason to give candidates a small amount of time from receiving the problem to submitting their solution is that otherwise it can be difficult to tell a candidate that is in demand and therefore busy, from a candidate that took the full week to actually solve the problem. Git timestamps may give an indication, but a candidate could have worked on it in blocks. By requesting that the candidate block out time and then giving them the problem, you set a tighter bound on how much time they can actually spend.
How do you know how long a problem is? It may take an engineer from your company, who is familiar with the problem, less time than a quality candidate. The best data would come from people that you know are quality, but don’t work at your company. Here’s an idea: use linkedin and have your employees offer to pay people they felt were good engineers at previous companies to solve the problem. Have the candidates sign an NDA. If you get a few to solve your problem and report how long it took them, you can get a feel for how long the problem takes. You can also keep data on how long it takes candidates, but note that this doesn’t track people who gave up. Even with the biases, tracking the data can still be useful.
In 2019 I was given a 3-part take home problem that I just didn’t do. Two of the parts were super simple fizz-buzz style problems. The third was implementing a program to call a REST API. The first two are redundant. If you can do the third, you can program. The third is redundant though too. Python has a library called decorest That already solves this. Even worse, in 2010 I is was fixing a different libary to do this for GWT
What you pick as a problem says something about your company. Make sure that you understand what it says and that it is a message that you want to convey.
Yes, I think that the ability to do it on your own schedule makes candidates willing to spend a little more time on a problem than they would in an interview. I was willing to spend 2 nights in a Hotel to interview at Google, so this is a much lower time commitment. My personal preference is for time boxed unconstrained problem, with a free choice of languages and a follow-up interview. One company said they did a pair programming exercise as the follow-up with the interviewer actually writing some code. I didn’t get to try that, but I was curious about how it would go. I feel that my abilities have shown best in doing this particular kind of problem.