Advent of code 2022 day 6 , Dec 6-

gistfile1.txt

"""Problem at https://adventofcode.com/2022/day/6

SPOILER ALERT!

This is a problem that could easily be solved by "brute-force" and simply
creating a set for each 14-character window and checking its length.

I created a "counter of counters" that I think could hold
constant time for counting, and therefore, linear time to
find large un-repeated sequences in large (multi GB) datasets
"""

from collections import deque

class Counts:
    def __init__(self):
        self.keys = {}
        self.counts = {}
    def inc(self, key):
        x = self.keys[key] = self.keys.setdefault(key, 0) + 1
        if x not in self.counts:
            self.counts[x] = 1
        else:
            self.counts[x] += 1
        if x > 1:
            self.counts[x - 1] -= 1
            if self.counts[x-1] == 0:
                del self.counts[x-1]
    def dec(self, key):
        x = self.keys[key] = self.keys[key] - 1
        self.counts[x + 1] -= 1
        if x!= 0:
            if not x in self.counts:
                self.counts[x] = 1
            else:
                self.counts[x] += 1
        if self.counts[x+1] == 0:
            del self.counts[x+1]
    def valueset(self):
        # if there would be a large "M" number of keys and time would be  "M,N" due to that
        # this function could return a boolean, and check first the keys length,
        # and then their content (which shoud equal {1} )  instead. 
        return self.counts.keys()
    def __repr__(self):
        return repr(self.keys) + "\n" + repr(self.valueset())

class StateCounter():
    def __init__(self, window=14):
        self.counts = Counts()
        self.window = window
        self.queue = deque(maxlen=window + 1)
        self.processed = 0
        
    def feed(self, char):
        self.queue.append(char)
        self.counts.inc(char)
        v = None
        if len(self.queue) > self.window:
            v = self.queue.popleft()
        self.processed += 1
        if v:
            self.counts.dec(v)
            if self.counts.valueset() == {1}:
                raise BaseException(f"value found at index {self.processed} - 1")