copy pasting the rules from last year’s thread:

Rules: no spoilers.

The other rules are made up aswe go along.

Share code by link to a forge, home page, pastebin (Eric Wastl has one here) or code section in a comment.

  • Sailor Sega Saturn@awful.systems
    link
    fedilink
    English
    arrow-up
    1
    ·
    edit-2
    2 年前

    I decided to double down on 2-2, since bad code is one of life’s little pleasures. Where we’re going we won’t need big-oh notation

    spoiler
    #include <string>
    #include <iostream>
    #include <sstream>
    #include <vector>
    #include <iterator>
    
    template <typename It>
    bool seemslegit(It begin, It end) {
        if (std::distance(begin, end) == 1) {
          return true;
        }
        int a = *begin++;
        int b = *begin++;
        if (a == b || std::abs(a-b) > 3) return false;;
        bool increasing = b > a;
        while (begin != end) {
          int c = *begin++;
          if (b == c || std::abs(b-c) > 3) return false;;
          switch (increasing) {
            case false:
              if (c < b) { b = c; continue; }
              return false;
            case true:
              if(c > b) { b = c; continue; }
              return false;
          }
        }
        return true;
    }
    
    template <typename It>
    void debug(It begin, It end) {
      bool legit = seemslegit(begin, end);
      while (begin != end) {
        std::cout << *begin++ << " ";
      }
      //std::cout << ": " << std::boolalpha << legit << std::endl;
    }
    
    int main() {
      int safe = 0;
      std::string s;
      while (std::getline(std::cin, s)) {
        std::istringstream iss(s);
        std::vector<int> report((std::istream_iterator<int>(iss)),
                                std::istream_iterator<int>());
        debug(report.begin(), report.end());
        if (seemslegit(report.begin(), report.end())) {
          safe++;
          std::cout << "\n\n";
          continue;
        }
        for (int i = 0; i < report.size(); ++i) {
          auto report2 = report;
          auto it = report2.erase(report2.begin()+i);
          debug(report2.begin(), report2.end());
          if (seemslegit(report2.begin(), report2.end())) {
            safe++;
            break;
          }
        }
        std::cout << "\n\n";
     }
      std::cout << safe << std::endl;
    }
    
    Commentary

    Doing this “efficiently” should be possible. since you only need ~2-ish look-back you should be able to score reports in O(n) time. One complication is you might get the direction wrong, need to consider that erasing one of the first two elements could change the direction. But that requires thinking, and shoving all the permutations into a function with ungodly amounts of copying does not.

    • swlabr@awful.systems
      link
      fedilink
      English
      arrow-up
      0
      ·
      2 年前
      re: 2-2

      yeah that’s what I ended up thinking. Just try the brute force and if it’s too slow, maybe I’ll try be smarter about it.

      • gerikson@awful.systems
        link
        fedilink
        English
        arrow-up
        1
        ·
        2 年前
        re: 2-2

        I was convinced that some of the Perl gods in the subreddit would reveal some forgotten lore that solved this in one line but looks like my brute force method of removing one element at a time was the way to go.