Brute Force for Beginners

We can brute force the small input by trying all permutations:

A little thought shows the smallest sum arises from repeatedly pairing up the smallest number of one list with the largest of the other. [If a < b and c < d, then (b - a)(d - c) > 0, that is, ad + bc < ac + bd.]

So an efficient solution is to sort one list in increasing order (sort), sort the other in decreasing order (reverse . sort), multiply them pairwise (zipWith (*)), and sum them (sum).

For once, we use the first line, because it holds more than just the number of test cases: it also contains the number of words in the dictionary.

We solve this with the most obvious method involving lists. We parse each pattern into a list of lists (for instance, a(bc)(ca) becomes [[a], [b, c], [c, a]]), then count the number of words (length $ filter …​) in the dictionary where each letter of the word is an element of the corresponding list of the pattern.

In general, a sweep line algorithm is best for finding all intersections in a set of line segments, but this problem is small enough and special enough for a far simpler algorithm.

Because no 3 lines are concurrent and no 2 lines share an endpoint, we can simply count the number of tuples (Ai, Bi, Aj, Bj) satisfying sgn(Ai - Aj) ≠ sgn(Bi - Bj).

This is rather similar to our solution to Store Credit, so let’s use Data.Vector instead of Data.Array to practice installing a package:

Some of names exported by Data.Vector conflict with those defined in Prelude, so we explicitly list the ones we want.

What does undefined mean? Since we only want the length of the list, the actual contents of the list are irrelevant and never examined. In fact, the program would crash if we tried to compute on an element of the list, which we can verify in an interactive session:

Disappointingly, the inputs are small enough that we can get away with a obvious solution based on lists. Consider a path we wish to create. We split it into its component directory names (splitOn "/") that we then use to generate a list of the path and all its ancestors (map (intercalate "/") . inits).

The handy splitOn function requires installing a package:

Then:

The output contains undesired empty strings, which we could have avoided with tail, but we’ll get rid of them soon enough anyway.

We concatenate all such lists into a monstrous list (concat . map), then remove any duplicates with union: this function removes duplicates from its second argument before computing its union with the first argument. Comparing the lengths of the list before and after adding the new directories yields the answer.

The above is adequate, but for training purposes, let’s write a faster solution based on trees. The idea is similar: for each path, we insert it into a tree, and count the number of times we created a new node.

In conventional languages, we might write code that traverses down a tree and inserts nodes. But this is impure; ideally, we should refrain from modifying a tree in place.

This is easier than it sounds. We’ve had plenty of practice keeping lists pure: functions like concat or union return new lists rather than modify lists in place. We can do the same for trees. One way is to use Data.Tree.Zipper:

This module introduces a TreePos type: a cursor that keeps track of where we are on a tree. We wind up with Haskell that resembles tree-updating code in other languages, but in reality creates a new tree after each operation.

Below, the ins function recursively inserts a path into a tree, at the position indicated by a given TreePos. As we wish to keep track of the number of created nodes, we also bundle an Int with each TreePos which records the number of created nodes.

For clarity, we explicity declare the type of ins even though Haskell’s type inference could figure it out on its own. The Full means the TreePos points to a node of the tree, and not to an empty space between two nodes (which is useful in other contexts).

How often should we declare types? About as often as we should comment code, for type declarations can be thought of as comments. (Only they’re better because compilers can enforce them, and compilers are more reliable than humans.) Thus we should declare types for functions that we expect others to use, and in general, anywhere where it makes code clearer.

To keep our solutions short and sweet, we’ve been omitting type declarations. We made an exception for ins because sooner or later we’ll have to learn how to write a type declaration, and ins is a good candidate to practice on, as it has a non-trivial type.

This is our first encounter with the Maybe data type: the functions firstChild and next return Nothing if there is no first or next child, and otherwise return Just tp where tp is the TreePos of the returned child.

Using maps instead of lists to hold the child nodes would improve lookup times from linear to logarithmic, but this is overkill. Our tree solution runs way faster than our list solution, which already was fast enough.

One sub-problem is simulating gravity on a single column, which is essentially moving all occurrences of "." to one end of a list. For example, "B..R.BR." becomes "…​.BRBR". Haskell’s partition is perfect for this:

The uncurry ()` produces a function that's just like `() (so it also concatenates two lists together) except that it takes its two input lists as a tuple instead of separate arguments. This fits with partition like hand in glove. In other words, it’s shorthand for:

A second sub-problem is figuring out who has won. There may be ways to do this elegantly, but we’ll just bash it out with a list comprehension: for each player, we look for a square that for some orthogonal or diagonal direction ([(1, 0), (0, 1), (1, 1), (1, -1)]), we can walk k steps and always see the player’s piece. As with conventional languages, or and and short-circuit, so the search stops after the first winning combination is found.

This is our first program to feature a Haskell case expression. It looks and feels like case statements in other languages, except there’s no fallthrough.

Our code is wasteful (unboxed arrays might be better; we check squares multiple times; we check directions even if they obviously take us off the board), but it’s fine for the contest.

In a manner akin to Minimum Scalar Product, we attain the minimum by assigning the smallest unassigned digit to the most significant (leftmost) unassigned symbol and repeating until all symbols are assigned.

This is a job for nub, which keeps only the first occurrence of each element in a list. We use the output of nub as a dictionary: the index of a symbol in this list is the digit it represents.

To minimize the number, we minimize the base, which is at minimum the number of distinct symbols, namely, the length of the dictionary.

There are two complications:

It’s much simpler to express all this in Haskell:

We surrounded elemIndex with backticks to turn it into an infix operator. This works on any function that takes at least two arguments. We did so here mostly for fun, but also because elemIndex is a bit like the ∈ binary operator in mathematics.

Again, we encounter the Maybe data type: elemIndex returns Nothing if the given element is not found in the given list, and otherwise returns Just i where i is the index of the element in the list. Since we know for sure that d lies in dict, we know the latter must be true, so we call fromJust to extract i from Just i.

What happens if we call fromJust on Nothing?

You can’t get something from Nothing!