/wakamoleguy

It's Day 2 of Advent of Code, and we're apparently going to play in a tournament of Rock Paper Scissors. One elf has "helpfully" given us a strategy guide to guarantee a win. Now, I am adamantly opposed to cheating in any form, so this puzzle posed a predicament. Luckily our task sidesteps this; rather than using the strategy, we only care to check to see how effective it would be.

OpenAI recently released ChatGPT, an interactive language model for dialogues. It is built with some functionality to refuse inappropriate requests. Trending on HackerNews today is a post describing all of the way people have found to circumvent that filter. One of the most popular is to phrase the prompt as make believe. So that's what we're doing today. We're not cheating at Rock Paper Scissors; we're simply playing a character that would cheat at Rock Paper Scissors.

A Naive, But Solid Approach

The scoring for a single round of Rock Paper Scissors is based on two simple rules. One of them is dependent on the shape you throw (3 options), and the other is dependent on the outcome of the game (shapes you and your opponent throw, 3 * 3 == 9 options). That's not that many cases! Let's just hardcode them.

module AOC2022.Day02 (spec) where

import Control.Applicative
import Input
import Test.Hspec

input :: IO String
input = readDay 2022 2

spec :: IO ()
spec = hspec $ do
  describe "Day 2" $ do
    it "solves part 1" $ do
      myInput <- input
      part1 myInput `shouldBe` 0 -- redacted
    it "solves part 2" $ do
      myInput <- input
      part2 myInput `shouldBe` 0 -- redacted

part1 :: String -> Int
part1 = sum . fmap score . lines

score :: String -> Int
score = liftA2 (+) scoreShape scoreOutcome

scoreShape :: String -> Int
scoreShape [_, _, 'X'] = 1
scoreShape [_, _, 'Y'] = 2
scoreShape [_, _, 'Z'] = 3
scoreShape _ = 0

scoreOutcome :: String -> Int
scoreOutcome "A X" = 3
scoreOutcome "A Y" = 6
scoreOutcome "A Z" = 0
scoreOutcome "B X" = 0
scoreOutcome "B Y" = 3
scoreOutcome "B Z" = 6
scoreOutcome "C X" = 6
scoreOutcome "C Y" = 0
scoreOutcome "C Z" = 3
scoreOutcome _ = 0

part2 :: String -> Int
part2 = sum . fmap score2 . lines

score2 :: String -> Int
score2 = liftA2 (+) scoreShape2 scoreOutcome2

scoreShape2 :: String -> Int
scoreShape2 "A X" = 3
scoreShape2 "A Y" = 1
scoreShape2 "A Z" = 2
scoreShape2 "B X" = 1
scoreShape2 "B Y" = 2
scoreShape2 "B Z" = 3
scoreShape2 "C X" = 2
scoreShape2 "C Y" = 3
scoreShape2 "C Z" = 1
scoreShape2 _ = 0

scoreOutcome2 :: String -> Int
scoreOutcome2 [_, _, 'X'] = 0
scoreOutcome2 [_, _, 'Y'] = 3
scoreOutcome2 [_, _, 'Z'] = 6
scoreOutcome2 _ = 0

OK, so it's a little long, but I doubt there is a simpler, more understandable approach. The only real trick is the use of liftA2 to convert + from an operator on numbers to an operator on functions. For further reading, check out Learn You A Haskell's chapter on Applicative Functors, especially regarding instance Functor ((->) r).

Who Needs Simple?

While the code is working just fine, there is something deeply unsatisfying about such repetitive statements. My goal isn't to strictly minimize the amount of code, though, so to justify further exploration let's introduce a self-imposed "Part 3": make it work with Rock Paper Scissors Lizard Spock, an extension of Rock Paper Scissors with 5 options.

The key insight is that all games like Rock Paper Scissors Lizard Spock can be represented as a cyclic order. For any game with 2k+1 shapes, each shape has k other shapes that beat it and k other shapes that lose to it. For code golfers, this opens up a plethora of modular arithmetic tricks to aid in solving. We'll focus more on the algebraic side of things.

So let's start with a data type that implements Ord:

data Shape = Rock | Paper | Scissors deriving (Eq, Show)
instance Ord Shape where
  compare x y =
    let minmax = [Rock, Scissors]
     in if x `elem` minmax && y `elem` minmax then compare y x else compare x y```

This compare function is no good! While it may work for our needs, it is not a valid instance of the Ord typeclass, since it is not transitive. (Rock is less than Paper, and Paper is less than Scissors, but Rock is not less than Scissors.)

So we throw that away and create our own typeclass CyclicEnum, using the same code to implement a cycle compare, or ccompare. Given a Shape, we also want to be able to find the Shape that is some number of steps down the cycle, so we introduce another function toCyclicEnumFrom.

class (Bounded a, Ord a, Enum a) => CyclicEnum a where
  ccompare :: a -> a -> Ordering
  toCyclicEnumFrom :: a -> Int -> a
  ccompare x y =
    let minmax = [minBound, maxBound]
     in if x `elem` minmax && y `elem` minmax then compare y x else compare x y
  toCyclicEnumFrom a i = toEnum $ (i + fromEnum a + sizeof a) `mod` sizeof a


sizeof :: CyclicEnum a => a -> Int
sizeof a = 1 + val maxBound - val minBound
  where
    val = fromEnum . (`asTypeOf` a)

With this new algebraic representation, we unfortunately have to parse the strings. Let's assume that in our Rock Paper Scissors Lizard Spock, example, we would use A, B, C, D, and E as well as V, W, X, Y, and Z. We can do some modular arithmetic on the character codes to generalize this:

parseCode :: CyclicEnum a => Char -> a
parseCode = toCyclicEnumFrom minBound . clampAlphabet . fromEnum
  where
    -- A, B, C -> 0, 1, 2 and X, Y, Z -> -3, -2, -1
    clampAlphabet = (`subtract` 13) . (`mod` 26) . (+ 13) . (`subtract` fromEnum 'A')

With our new representation, we can rephrase our scoring function in terms of the underlying enum values. We can also implement the requested behavior from Part 2, to decode the outcome of the game into its actual shapes, using our handy toCyclicEnumFrom function:

decodeGame :: CyclicEnum a => (a, a) -> (a, a)
decodeGame (a, o) = (a, toCyclicEnumFrom a (fromEnum o - sizeof a `div` 2))

Putting It All Together

Here's the full code. Implementing Rock Paper Scissors Lizard Spock is now as simple as adding two new items to the Shape enum!

The proper order of the cycle according to the usual rules would be Rock-Spock-Paper-Lizard-Scissors. Each shape defeats the two preceding items and loses to the two following shapes.

class (Bounded a, Ord a, Enum a) => CyclicEnum a where
  ccompare :: a -> a -> Ordering
  toCyclicEnumFrom :: a -> Int -> a
  ccompare x y =
    let minmax = [minBound, maxBound]
     in if x `elem` minmax && y `elem` minmax then compare y x else compare x y
  toCyclicEnumFrom a i = toEnum $ (i + fromEnum a + sizeof a) `mod` sizeof a

sizeof :: CyclicEnum a => a -> Int
sizeof a = 1 + val maxBound - val minBound
  where
    val = fromEnum . (`asTypeOf` a)

data Shape = Rock | Paper | Scissors deriving (Eq, Show, Ord, Bounded, Enum)

instance CyclicEnum Shape

parseCode :: CyclicEnum a => Char -> a
parseCode = toCyclicEnumFrom minBound . clampAlphabet . fromEnum
  where
    -- A, B, C -> 0, 1, 2 and X, Y, Z -> -3, -2, -1
    clampAlphabet = (`subtract` 13) . (`mod` 26) . (+ 13) . (`subtract` fromEnum 'A')

parseGame :: String -> (Shape, Shape)
parseGame [a, ' ', x] = (parseCode a, parseCode x)

scoreShape :: CyclicEnum a => a -> a -> Int
scoreShape = const $ (1 +) . fromEnum

scoreOutcome :: CyclicEnum a => a -> a -> Int
scoreOutcome they you = (3 *) $ fromEnum $ ccompare you they

score :: CyclicEnum a => (a, a) -> Int
score = liftA2 (+) (uncurry scoreShape) (uncurry scoreOutcome)

decodeGame :: CyclicEnum a => (a, a) -> (a, a)
decodeGame (a, o) = (a, toCyclicEnumFrom a (fromEnum o - sizeof a `div` 2))

part1 :: String -> Int
part1 = sum . fmap (score . parseGame) . lines

part2 :: String -> Int
part2 = sum . fmap (score . decodeGame . parseGame) . lines

Advent of Code 2022 Series

This post is part of a series describing my Haskell solutions to Advent of Code 2022.

Next: Day 3: Rock Paper Scissors Previous: Day 1: Calorie Counting