enum ParseResult[+A]:
  case Success(value: A, remaining: String)
  case Failure(message: String)

// A Parser is just a wrapper around a function: String => Result[A]
case class Parser[A](parse: String => ParseResult[A]):

  /**
   * `map` lets us transform the parsed value.
   * If we have a Parser[Int], we can turn it into a Parser[String] etc.
   */
  def map[B](f: A => B): Parser[B] =
    Parser {
      parse(_) match
        case ParseResult.Success(value, rest) => ParseResult.Success(f(value), rest)
        case ParseResult.Failure(msg)         => ParseResult.Failure(msg)
    }

  /**
   * `flatMap` lets us chain parsers: use the result of one to decide
   * what to parse next. This is the heart of combining parsers.
   */
  def flatMap[B](f: A => Parser[B]): Parser[B] =
    Parser {
      parse(_) match
        case ParseResult.Success(value, rest) => f(value).parse(rest)
        case ParseResult.Failure(msg)         => ParseResult.Failure(msg)
    }

  /**
   * `orElse` lets us try one parser, and if it fails, try another.
   * @param other the parser to try
   * @return a parser that parses the orElse parser
   */
  infix def orElse(other: => Parser[A]): Parser[A] =
    Parser { input =>
      parse(input) match
        case s @ ParseResult.Success(_, _) => s
        case _: ParseResult.Failure[?]     => other.parse(input)
    }

  infix def |(other: => Parser[A]): Parser[A] = orElse(other)

  /**
   * `~>` sequences two parsers but keeps only the RIGHT result.
   * Useful for skipping delimiters like '-'.
   * @param next the parser to sequence
   * @return a parser that parses the sequence
   */
  def ~>[B](next: Parser[B]): Parser[B] = flatMap(_ => next)

  /**
   * `<~` sequences two parsers but keeps only the LEFT result.
   * @param next the parser to sequence
   * @return a parser that parses the sequence
   */
  def <~[B](next: Parser[B]): Parser[A] =
    for
      a <- this
      _ <- next
    yield a

object Parser:

  /**
   * Parse a single character that satisfies a predicate
   * @param predicate the predicate to satisfy
   * @param expected the expected character
   * @return a parser that parses the character
   */
  def charWhere(predicate: Char => Boolean, expected: String): Parser[Char] =
    Parser { input =>
      input.headOption match
        case Some(c) if predicate(c) => ParseResult.Success(c, input.tail)
        case Some(c)                 => ParseResult.Failure(s"Expected $expected, but got '${c}'")
        case None                    => ParseResult.Failure(s"Unexpected end of input, expected $expected")
    }

  /**
   * Parse exactly this character
   * @param c the character to parse
   * @return a parser that parses the character
   */
  def char(c: Char): Parser[Char] = charWhere(_ == c, s"'$c'")

  /**
   * Parse a single-digit character and return it as a Char
   * @return a parser that parses the character
   */
  def digit: Parser[Char] = charWhere(_.isDigit, "a digit")

  /**
   * Parse exactly N digits and convert them to an Int
   * @param n the number of digits to parse
   * @return a parser that parses the digits
   */
  def digits(n: Int): Parser[Int] = repeatN(n, digit).map(_.mkString.toInt)

  /**
   * Parse one or more digits and convert them to an Int
   * @return a parser that parses the digits
   */
  def digits(): Parser[Int] = oneOrMore(digit).map(_.mkString.toInt)

  /**
   * Parse a single hex digit and return it as a Char
   * @return a parser that parses the hex digit
   */
  def hexDigit(): Parser[Char] =
    charWhere(c => c.isDigit || (c >= 'a' && c <= 'f') || (c >= 'A' || c <= 'F'), "a hex digit")

  /**
   * Parse exactly N hex digits and return them as a String
   * @param n the number of hex digits to parse
   * @return a parser that parses the hex digits
   */
  def hexDigits(n: Int): Parser[String] = repeatN(n, hexDigit()).map(_.mkString)

  /**
   * Assert the parse is done — no leftover input
   * @return a parser that parses the end of input
   */
  def eof: Parser[Unit] =
    Parser { input =>
      if input.isEmpty then ParseResult.Success((), "")
      else ParseResult.Failure(s"Expected end of input, but got '$input'")
    }

  /**
   * Parse an optional parser
   * @param p the parser to parse
   * @return a parser that parses the optional parser
   */
  def optional[A](p: Parser[A]): Parser[Option[A]] =
    Parser { input =>
      p.parse(input) match
        case ParseResult.Failure(message)     => ParseResult.Success(None, input)
        case ParseResult.Success(value, rest) => ParseResult.Success(Some(value), rest)
    }

  /**
   * Repeat a parser exactly N times, collecting results into a List
   * @param n the number of times to repeat the parser
   * @param p the parser to repeat
   * @return a parser that parses the repeated parser
   */
  def repeatN[A](n: Int, p: Parser[A]): Parser[List[A]] =
    if n <= 0 then Parser(input => ParseResult.Success(List.empty, input))
    else
      for
        head <- p
        tail <- repeatN(n - 1, p)
      yield head :: tail

  /**
   * Repeat a parser zero or more times (never fails)
   * @param p the parser to repeat
   * @return a parser that parses the repeated parser
   */
  def zeroOrMore[A](p: Parser[A]): Parser[List[A]] =
    Parser { input =>
      p.parse(input) match
        case ParseResult.Failure(_)           => ParseResult.Success(List.empty, input)
        case ParseResult.Success(value, rest) =>
          zeroOrMore(p).parse(rest) match
            case ParseResult.Failure(_)            => ParseResult.Success(List(value), rest)
            case ParseResult.Success(values, rest) => ParseResult.Success(value :: values, rest)
    }

  /**
   * Repeat a parser one or more times (fails if zero matches)
   * @param p the parser to repeat
   * @return a parser that parses the repeated parser
   */
  def oneOrMore[A](p: Parser[A]): Parser[List[A]] =
    for
      head <- p
      tail <- zeroOrMore(p)
    yield head :: tail

  /**
   * Match a literal string, character by character
   * @param s the string to match
   * @return a parser that parses the string
   */
  def string(s: String): Parser[String] =
    s.toList match
      case Nil       => Parser(input => ParseResult.Success("", input))
      case c :: rest =>
        for
          _    <- char(c)
          tail <- string(rest.mkString)
        yield s