Problem B of this year’s qualifier is a simple “greedy-DP” puzzle. We’re given a chain of a binary string with holes, and must determine some cost function’s optimal value over the possible ways to fill it up.

It’s almost as easy to solve as the statement’s length makes it seem, so I’ll try and find something to spice it up.

First off, the input string is given as a dumbed-down ASCII representation of Cody-Jamal’s true Artwork. This can be fixed with a simple stream transcoder:

fixASCII ∷ String → String
fixASCII = map $ \case 'C' → '🌘'
                       'J' → '🌂'
                       '?' → '❓'
                       x   →  x

Now for each prefix of the input mural, we’ll want to know the minimal fee for that part of the mural, so we can deduce the minimal fee after adding a glyph to it, and reap the final fee in the end.

But that won’t work: there’s no way to achieve the “deduction” part. It can be fudged to work, though. We can split the minimal fee information in two: the minimal fee assuming the prefix ends in a moon, and the minimal fee assuming the prefix ends in an umbrella.

The natural way to represent this is with a simple record:

data State = State { (🌘) ∷ Maybe Int, (🌂) ∷ Maybe Int }

Each Int represents the minimal cost of a mural ending in said glyph; Nothing if it’s impossible to end as such. But that’s not perfect yet. Such a representation allows for a pair of Nothings, and… what would we answer if we ended on such a pair? Because of the transition function’s structure, such a pair can never occur. So we really need a representation that reflects that.

According to the kind folks on IRC¹, the standard library to reach for in this case is these.

Except the Haskell setup we’ve got over at GCJ’s is even more primeval than CodinGame’s!² So no libraries for us. Luckily enough, the data type in itself is pretty straightforward.

data These a b = This a | That b | These a b

Err… since I’m not using the library, I might as well give those constructors meaningful names.

data (│) = (:🌘) Int | (:🌂) Int | (:🌘🌂) Int Int

Much better. I won’t reproduce its standard combinators and Bifunctor instances here, they’re just a reproduction of These’s.

With the helpers available, here’s the little utility to compute the final minimal cost from the split state.

minimal ∷ (│) → Int
minimal = merge min

It allows for a delightfully elegant implementation of the transition function.

transition ∷ Int → Int → Char → (│) → (│)
transition x y = \case '🌘' →         (:🌘)   .  (<|🌘)
                       '🌂' →         (:🌂)   .             (<|🌂)
                       '❓' → uncurry (:🌘🌂) . ((<|🌘) &&& (<|🌂))
  where (<|🌘) = minimal . (🌂) (+y)
        (<|🌂) = minimal . (🌘) (+x)

Maybe inserting a small reading key would be in order? So, assuming we could implement things properly using the these package, here’s what the various symbols mean:

• The type name is (│), aiming to evoke horizontal separation, as it is most often used to represent a state of the computation between two mural glyphs.
• (:🌘), (:🌂), (:🌘🌂) are This, That and These, the data constructors holding integer values associated to a moon, an umbrella or both, respectively.³
• (🌘) and (🌂) are first and second from Bifunctor: apply a function to the moon or umbrella aspect of the value.
• (<|🌘) and (<|🌂) are helpers to perform the “append moon” and “append umbrella” operations.

We need dedicated code to create the initial state, as there’s no proto-state that would result in the correct first one if the transition function were blindly applied to it.

start ∷ Char → (│)
start '🌘' = (:🌘) 0
start '🌂' = (:🌂) 0
start '❓' = (:🌘🌂) 0 0

And now solving the problem reduces to a simple fold.

invoice ∷ Int → Int → String → Int
invoice x y (h:t) = minimal $ foldl' (flip (transition x y)) (start h) t

It performs linearly, which is optimal in this case, and solves test sets 1, 2 and 3 without a hitch.

This concludes this qualifier problem B’s solution. The complete code with I/O handling is on my github⁴.

See you soon for problem D!