carbon-lang/examples/advent2024/day5_common.carbon

// Part of the Carbon Language project, under the Apache License v2.0 with LLVM
// Exceptions. See /LICENSE for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

// https://adventofcode.com/2024/day/5

library "day5_common";

import Core library "range";

import library "io_utils";

fn PageMask(page: i32) -> Core.UInt(100) {
  // TODO: return (1 as Core.UInt(100)) << page;
  return (1 as Core.UInt(100)) << (page as Core.UInt(100));
}

class Rules {
  impl as Core.UnformedInit {}

  fn Read() -> Rules {
    returned var rules: Rules;
    for (i: i32 in Core.Range(100)) {
      rules.disallowed_before[i] = 0;
    }

    var a: i32;
    var b: i32;
    while (ReadInt(ref a) and ConsumeChar('|') and ReadInt(ref b)) {
      rules.disallowed_before[a] |= PageMask(b);
      SkipNewline();
    }
    return var;
  }

  fn IsValidOrder[self: Self](a: i32, b: i32) -> bool {
    return self.disallowed_before[b] & PageMask(a) == 0;
  }

  var disallowed_before: array(Core.UInt(100), 100);
};

class PageList {
  impl as Core.UnformedInit {}

  fn Empty() -> PageList {
    returned var me: PageList;
    me.num_pages = 0;
    return var;
  }

  fn Read() -> PageList {
    returned var me: PageList = Empty();

    var page: i32;
    if (not ReadInt(ref page)) {
      return var;
    }
    me.Add(page);
    while (ConsumeChar(',')) {
      ReadInt(ref page);
      me.Add(page);
    }
    SkipNewline();
    return var;
  }

  fn Add[ref self: Self](page: i32) {
    self.pages[self.num_pages] = page;
    ++self.num_pages;
  }

  fn FollowsRules[self: Self](rules: Rules) -> bool {
    var seen: Core.UInt(100) = 0;
    for (i: i32 in Core.Range(self.num_pages)) {
      let page: i32 = self.pages[i];
      if (seen & rules.disallowed_before[page] != 0) {
        return false;
      }
      seen |= PageMask(page);
    }
    return true;
  }

  fn IsPossibleFirstPage[self: Self](rules: Rules, page: i32) -> bool {
    for (i: i32 in Core.Range(self.num_pages)) {
      if (not rules.IsValidOrder(page, self.pages[i])) {
        return false;
      }
    }
    return true;
  }

  fn ExtractPossibleFirstPage[ref self: Self](rules: Rules) -> i32 {
    for (i: i32 in Core.Range(self.num_pages)) {
      var page: i32 = self.pages[i];
      if (self.IsPossibleFirstPage(rules, page)) {
        self.pages[i] = self.pages[self.num_pages - 1];
        --self.num_pages;
        return page;
      }
    }
    // TODO: Assert.
    return 0;
  }

  fn MiddlePage[self: Self]() -> i32 {
    return self.pages[self.num_pages / 2];
  }

  var pages: array(i32, 24);
  var num_pages: i32;
};