this post was submitted on 02 Dec 2024
14 points (100.0% liked)

NotAwfulTech

386 readers
4 users here now

a community for posting cool tech news you don’t want to sneer at

non-awfulness of tech is not required or else we wouldn’t have any posts

founded 1 year ago
MODERATORS
 

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.

you are viewing a single comment's thread
view the rest of the comments
[–] swlabr@awful.systems 4 points 3 weeks ago (1 children)

re: 2-2yeah 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 5 points 3 weeks ago (1 children)

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.

[–] sailor_sega_saturn@awful.systems 5 points 3 weeks ago* (last edited 3 weeks ago)

I am now less sleep deprived so can say how to do better somewhat sensibly, albeit I cannot completely escape from C++s verbosity:

2-2

  1. Don't worry about the sequences changing direction. Just call the check function both assuming it is increasing and assuming it is decreasing. This is cheap enough because the wrong branch will fail after 3 elements or so.
  2. When encountering an element that fails, you only need to consider removing the previous element, or the current element. If you can get to the next element removing one of those then you can continue on without any real backtracking.

Updated code:

2-2

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <iterator>

bool valid_pair(const std::vector<int> &arr, int i, int j, bool direction) {
  if (i < 0) return true;
  if (j == arr.size()) return true;
  return    !(arr[i] == arr[j])
         && (direction ? arr[i] < arr[j] : arr[j] < arr[i])
         && (std::abs(arr[j]-arr[i]) <= 3);
}

bool valid(const std::vector<int> &arr, bool direction) {
  int checks = 1;
  for (int i = 1; i < arr.size(); ++i) {
    if (valid_pair(arr, i-1, i, direction)) continue;
    if (checks == 0) return false;
    if (   valid_pair(arr, i-2,  i, direction)
        && valid_pair(arr, i,  i+1, direction)) {
      checks -= 1; i += 1;
    } else if (valid_pair(arr, i-1, i+1, direction)) {
      checks -= 1; i += 1;
    } else return false;
  }
  return true;
}

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>());
    safe += (valid(report, true) || valid(report, false));
  }
  std::cout << safe << std::endl;
}