Day 6: Tuning Trouble

#!/usr/bin/env pypy3

import sys

WINSIZ = 4

def main():
    data = sys.stdin.read().strip()
    nchars = next(i + WINSIZ for i in range(len(data) - WINSIZ)
                  if len(set(data[i:i + WINSIZ])) == WINSIZ)
    print(nchars)

if __name__ == '__main__':
    main()

#!/usr/bin/env pypy3

import sys

WINSIZ = 14

def main():
    data = sys.stdin.read().strip()
    nchars = next(i + WINSIZ for i in range(len(data) - WINSIZ)
                  if len(set(data[i:i + WINSIZ])) == WINSIZ)
    print(nchars)

if __name__ == '__main__':
    main()

(l > p
 | (windowed, X, 4)
 | (locate, X, all_unique)
 | first) + 4

from more_itertools import all_unique
from more_itertools import first
from more_itertools import locate
from more_itertools import windowed
from pipetools import X
from pipetools import pipe
import sys
p = pipe
for l in sys.stdin:
    l = l.rstrip('\n')
    output = (l > p | (windowed, X, 4) | (locate, X, all_unique) | first) + 4
    if output is not None:
        print(output)

(define (part-01 input)
  (for/first ([(a i) (in-indexed (in-string input))]
              [b (in-string (substring input 1))]
              [c (in-string (substring input 2))]
              [d (in-string (substring input 3))]
              #:when (= 4 (set-count (set a b c d))))
    (+ i 4)))

(define (part-02 input)
  (let search ([cs (string->list input)]
               [i 0])
    (cond [(= 14 (set-count (list->set (take cs 14))))
           (+ i 14)]
          [else (search (rest cs) (add1 i))])))

Attempt 1:

Part 1 ~75% elapsed time
Part 2 ~35% elapsed time

Attempt 2:
I wish I could remember that hash-count is a constant time count of keys.
Simply replace (= n (length (hash-keys cs)) with (= n (hash-count cs)) as the exit clause below gives
Part 1 ~50% elapsed time
Part 2 ~20% elapsed time

(define (package-start s n)
  (for/fold ([cs (counts (substring s 0 n))]
             [found? #f]
             #:result found?)
            ([i (in-naturals)]
             [start (in-string s)]
             [end (in-string (substring s n))]
             #:break found?)
    (if (= n (length (hash-keys cs)))
        (values cs (+ i n))
        (values (udpate-counts cs start end) found?))))

(define (udpate-counts counts removal addition)
  (define removed
    (if (<= (hash-ref counts removal 0) 1)
        (hash-remove counts removal)
        (hash-update counts removal sub1)))
  (hash-update removed addition add1 0))

(define (counts s)
  (for/fold ([cs (hasheqv)])
            ([c (in-string s)])
    (hash-update cs c add1 0)))

(define (part-01 input) (package-start input 4))
(define (part-02 input) (package-start input 14))

buffer = open("input.txt").read()


def device(length: int):
    for i in range(len(buffer) - length + 1):
        if len(set(buffer[i : i + length])) == length:
            return length + i


print(device(4))  # Part One: 1625
print(device(14))  # Part Two: 2250

Wasn't sure what to name the function tbh. It's not really giving the index.

defmodule AdventOfCode.Solution.Year2022.Day06 do
  def part1(input), do: index_of_marker(input, 4)
  def part2(input), do: index_of_marker(input, 14)

  defp index_of_marker(input, size) do
    input
    |> String.to_charlist()
    |> Stream.chunk_every(size, 1, :discard)
    |> Enum.find_index(&(MapSet.size(MapSet.new(&1)) == size))
    |> Kernel.+(size)
  end
end

I abuse it in my solutions (because it's fun), but the |> ("pipe") operator is basically just syntactic sugar.

Functions in Elixir, for the most part, are not tightly coupled with data types. As a counterexample, arrays in JS have array functions as "methods"—myArray.map(...). The method gets the "subject" array as an implicit first this argument. There are no methods in Elixir. Data and logic are more strictly separated. Instead, we have functions where you explicitly pass the "subject" as the first argument: Enum.map(my_list, ...).

|> exists mostly to make "chaining" possible. It takes the result of the previous expression, and passes it as the first argument of the next function call. The code runs the same, but it reads more like a pipeline of sequential operations than one giant messy one-liner.

One thing I really like about this approach is that, in referencing the module for each function call—e.g. String.*, Enum.*, MapSet.*—you can sort of annotate what type you're working with at each step. In a longer pipeline, it's often very easy to see the type transformations that are happening; something that you don't get with chained method calls in other languages.

numbers_str = "1 2 25 93 8"

sum = Enum.sum(Enum.map(String.split(numbers_str, " "), &String.to_integer/1))

# compiles to the exact same byte code as

sum =
  numbers_str
  # We're using a function from the String module, so the subject is currently a string
  |> String.split(" ")
  # We're using a function from the Enum module, so the subject is currently an enumerable (a list, specifically)
  |> Enum.map(&String.to_integer/1)
  # Still an enumerable
  |> Enum.sum()

This does both parts.. I'm still new to SCAN, though. :)

=ARRAYFORMULA(
  SCAN(,{4,14},
   LAMBDA(a,c, 
    QUERY(
     {SEQUENCE(LEN(A2),1,c),
      BYROW(SPLIT(REGEXREPLACE(MID(A2,SEQUENCE(LEN(A2)),c),"(.)","$1|"),"|"),
       LAMBDA(x,TRANSPOSE(UNIQUE(TRANSPOSE(x)))))},
     "select Col1
      where Col"&c+1&" is not null
      limit 1"))))

from collections import deque

with open('06.txt') as input_file:
	buffer = input_file.read().strip()

def find_marker(buffer):
	window = deque(maxlen=4)
	for i, c in enumerate(buffer):
		window.append(c)

		if len(window) == 4 and \
			window[0] not in (window[1], window[2], window[3]) and \
			window[1] not in (window[2], window[3]) and \
			window[2] != window[3]:
		   return i + 1, ''.join(window)

index, marker = find_marker(buffer)

print(marker)
print(index)

generalized it so that if I change the size parameter back to 4, it solves part 1 again

rather less efficient than it could be, because it constructs a set over and over again just to check for uniqueness. that could be improved by keeping track of characters as they both enter and leave the window, using that to maintain a dictionary of character counts, and checking those counts to see if we found the marker.

but, execution time on my desktop is ~20ms for both the example input and my real input, which is both fast enough and suggests that the long pole is the Python startup time and not my algorithm, so meh.

--- aoc06a.py   2022-12-05 23:55:26.426887947 -0800
+++ aoc06b.py   2022-12-05 23:53:52.512286534 -0800
@@ -3,18 +3,16 @@
 with open('06.txt') as input_file:
        buffer = input_file.read().strip()
 
-def find_marker(buffer):
-       window = deque(maxlen=4)
+def find_marker(buffer, size):
+       window = deque(maxlen=size)
        for i, c in enumerate(buffer):
                window.append(c)
+
+               charset = set(window)
+               if len(charset) == size:
+                       return i + 1, ''.join(window)
 
-               if len(window) == 4 and \
-                       window[0] not in (window[1], window[2], window[3]) and \
-                       window[1] not in (window[2], window[3]) and \
-                       window[2] != window[3]:
-                  return i + 1, ''.join(window)
-
-index, marker = find_marker(buffer)
+index, marker = find_marker(buffer, 14)

i = File.read("input.txt")

i.chars.each_cons(4) do |s|
  if s == s.uniq
    p i.index(s.join)+4
    break
  end
end

i = File.read("input.txt")

i.chars.each_cons(14) do |s|
  if s == s.uniq
    p i.index(s.join)+14
    break
  end
end

import queue


def checkRepeats(input):
    chars = []
    for item in input.queue:
        if item in chars:
            return False
        chars.append(item)
    return True


def part1(input):
    print(f"Part 1!")
    window = queue.Queue(4)
    for index,char in enumerate(input):
        if window.full():
            if checkRepeats(window):  
                break
            window.get() 
        window.put(char)
    print(f"Index: {index}")


def part2(input):
    print(f"Part 2!")
    window = queue.Queue(14)
    for index,char in enumerate(input):
        if window.full():
            if checkRepeats(window):  
                break
            window.get() 
        window.put(char)
    print(f"Index: {index}")


def openFile():
    return open("input.txt", "r").read()


def main():
    f = openFile()
    part1(f)
    part2(f)


if __name__ == '__main__':
    main()

use std::env;
use std::io::{self};
use std::collections::HashSet;

fn packet_start(s: &str) -> usize {
    const MARKER_SIZE: usize = 4;
    let mut start = MARKER_SIZE;
    for chs in s.chars().collect::<Vec<_>>().windows(MARKER_SIZE) {
        let (a,b,c,d) = (chs[0],chs[1],chs[2],chs[3]);
        if a != b && a != c && a != d && b != c && b != d && c != d { break }
        else { start += 1; }
    }
    start
}

fn message_start(s: &str) -> usize {
    const MARKER_SIZE: usize = 14;
    let mut start = MARKER_SIZE;
    'outer: for chs in s.chars().collect::<Vec<_>>().windows(MARKER_SIZE) {
        start += 1;
        let mut char_set: HashSet<char> = HashSet::new();
        for ch in chs {
            if char_set.contains(ch) { continue 'outer; }
            else { char_set.insert(*ch); }
        }
        break;
    }
    start - 1
}

fn solve(input: &str) -> io::Result<()> {
    // Input
    let input_str = std::fs::read_to_string(input).unwrap();
    let input_str = input_str.trim();

    // Output
    println!("Part 1: {}",packet_start(input_str)); // 1578
    println!("Part 2: {}",message_start(input_str)); // 2178

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}

import std/[sets, sequtils]

proc day06*() =
  let f = open("inputs/day06.in")
  defer: f.close()

  let chars = f.readLine().toSeq()
  var
    startOfPktIdx = -1
    startOfMsgIdx = -1
    curIdx = 0
    pktSet: HashSet[char]
    msgSet: HashSet[char]

  while startOfPktIdx == -1 or startOfMsgIdx == -1:
    # Part 1
    if startOfPktIdx == -1:
      pktSet = chars[curIdx .. curIdx + 3].toHashSet()
      if pktSet.len == 4:
        startOfPktIdx = curIdx + 4
    # Part 2
    if startOfMsgIdx == -1:
      msgSet = chars[curIdx .. curIdx + 13].toHashSet()
      if msgSet.len == 14:
        startOfMsgIdx = curIdx + 14
    curIdx += 1

  echo "Part 1: " & $startOfPktIdx
  echo "Part 2: " & $startOfMsgIdx

import { readFileSync } from "fs";

const input = readFileSync("input.txt", "utf8").toString().split("\n");
const MARKER_SIZE = 4;
// const MARKER_SIZE = 14;

const findMarker = (buffer) => {
  for (let i = 0; i < buffer.length; i++) {
    let s = new Set();
    let x = [...buffer.slice(i, i + MARKER_SIZE)];
    for (const i of x) {
      s.add(i);
    }
    if (s.size === MARKER_SIZE) return i + MARKER_SIZE;
  }
};

input.forEach((item, index) => {
  console.log(findMarker(item));
});

mod part1;
mod part2;
mod utilities;

fn main() {
    let _input = include_str!("./input.txt");

    println!("Part One");
    println!("Result: {}", part1::part1(_input));

    println!("Part Two");
    println!("Result: {}", part2::part2(_input));
}

pub fn find_dupes_stupid<T: PartialEq>(slice: &[T]) -> bool {
    for i in 1..slice.len() {
        if slice[i..].contains(&slice[i - 1]) {
            return true;
        }
    }
    false
}

use crate::utilities::*;

pub fn part1(input: &str) -> usize {
    input
        .as_bytes()
        .windows(4)
        .position(|x| !find_dupes_stupid(x))
        .unwrap()+4
}

use crate::utilities::*;

pub fn part2(input: &str) -> usize {
    input
        .as_bytes()
        .windows(14)
        .position(|x| !find_dupes_stupid(x))
        .unwrap()+14
}

#!/usr/bin/awk -f
BEGIN { FS = "" }
{
	for (i = 1; i <= NF; ++i) {
		a[$i] += 1

		if (i >= 4) {
			if (a[$i]*a[$(i-1)]*a[$(i-2)]*a[$(i-3)] == 1) {
				print(i)
				exit
			}

			a[$(i-3)] -= 1
		}
	}
}

#!/usr/bin/awk -f
BEGIN { FS = "" }
{
	for (i = 1; i <= NF; ++i) {
		a[$i] += 1

		if (i >= 14) {
			for (j in a)
				if (a[j] > 1)
					break

			if (a[j] < 2) {
				print(i)
				exit
			}

			a[$(i-13)] -= 1
		}
	}
}

use std::error::Error;
use std::fs::File;
use std::io::Read;

struct Buffer {
	inner: [(usize, char); 4],
}

impl Buffer {
	fn new() -> Buffer {
		Buffer { inner: [(0, '\n'); 4] }
	}

	fn add(&mut self, new_elem: (usize, char)) {
		let least_recent = self.inner.iter().enumerate().min_by(|x, y| x.1.0.cmp(&y.1.0)).unwrap();
		self.inner[least_recent.0] = new_elem;
	}

	fn unique(&self) -> bool {
		self.inner.iter().all(|e| e.1 != '\n' && self.inner.iter().filter(|e2| e.1 == e2.1).count() == 1)
	}
}

fn main() -> Result<(), Box<dyn Error>> {
	let mut file = File::open("input_6.txt")?;
	let mut contents = String::new();
	file.read_to_string(&mut contents)?;
	let mut recents: Buffer = Buffer::new();
	let pos = contents.chars().enumerate().take_while(|(idx, c)| {
		recents.add((idx + 1, *c));
		!recents.unique()
	}).count() + 1;
	println!("{pos}");
	Ok(())
}

use std::error::Error;
use std::fs::File;
use std::io::Read;

struct Buffer {
	inner: [(usize, char); 14],
}

impl Buffer {
	fn new() -> Buffer {
		Buffer { inner: [(0, '\n'); 14] }
	}

	fn add(&mut self, new_elem: (usize, char)) {
		let least_recent = self.inner.iter().enumerate().min_by(|x, y| x.1.0.cmp(&y.1.0)).unwrap();
		self.inner[least_recent.0] = new_elem;
	}

	fn unique(&self) -> bool {
		self.inner.iter().all(|e| e.1 != '\n' && self.inner.iter().filter(|e2| e.1 == e2.1).count() == 1)
	}
}

fn main() -> Result<(), Box<dyn Error>> {
	let mut file = File::open("input_6.txt")?;
	let mut contents = String::new();
	file.read_to_string(&mut contents)?;
	let mut recents: Buffer = Buffer::new();
	let pos = contents.chars().enumerate().take_while(|(idx, c)| {
		recents.add((idx + 1, *c));
		!recents.unique()
	}).count() + 1;
	println!("{pos}");
	Ok(())
}

#!/usr/bin/env bash

file=day6.dat
part=1

if [[ ${part} -eq 1 ]]; then
# /////////////////////////////////////////////////////////////////////////////
    #part 1 // 0.08s // 1300 dbpw
    searchWidth=4 #width of character subset to check
else
    #part 2 // 0.26s // 3986 lcfjqpdwznsbrh
    searchWidth=14 #width of character subset to check
fi

mapfile -t stream < $file
charLength=${#stream}
i=0 #counter for outer loop
while [[ $i -lt $charLength ]]; do

#   -- extract subset of letters from bit stream
    currentFour=${stream:i:searchWidth} 

    j=0 #counter for inner loop
    count=0 #number of unique letters in subset

#   -- extract one letter from our subset
#   -- delete matches of extracted letter
#   -- if only 1 letter is matched, look at the next letter, otherwise just start again
#   -- if we have four unique letters, print the spot and quit
    while [[ $j -lt $searchWidth ]]; do
        check=${currentFour:$j:1}
        removed=${currentFour//[$check]/}
        length=${#removed}
        if [[ length -eq $(($searchWidth - 1)) ]]; then
            ((count = count + 1))
            (( j = j + 1))
        else
            break
        fi
    done

#   -- quit searching after the first set of unique letters
    if [[ $count -eq $searchWidth ]]; then
        break 1
    fi
    (( i = i + 1))
done

echo Position of stream for part ${part}: $(($i + $searchWidth))
echo Unique letters: $currentFour

def find_packet_marker(message: str) -> int:
    end = 3 
    while end < len(message):
        if message[end - 3] in message[end - 2 : end + 1]: 
            end += 1
            continue

        if message[end - 2] in message[end - 1 : end + 1]: 
            end += 2
            continue

        if message[end - 1] == message[end]:
            end += 3
            continue

        return end + 1 

    return -1


def find_marker(message: str, marker_size: int) -> int:

    end = marker_size - 1 
    while end < len(message):
        for offset in range(marker_size - 1, 0, -1):
            if message[end - offset] in message[end - (offset - 1) : end + 1]: 
                end += marker_size - offset
                break
        else:
            return end + 1 

    return -1


def main(filepath: str) -> Tuple[int, int]:

    message = load_file.load_cleaned_lines(filepath)[0]
    return (find_marker(message, 4), find_marker(message, 14))

type InputData = string;

export function run(input: string): string[] {

  const findMarker = (stream: InputData, numberOfCharacters: number): number => {
    const previousLetters = [] as string[];
    for (let i = 0; i < stream.length; i++) {
      previousLetters.push(stream[i]);
      if (previousLetters.length <= numberOfCharacters) {
        continue;
      }
      previousLetters.shift();
      if (new Set(previousLetters).size === numberOfCharacters) {
        return i + 1;
      }
    }
    return -1;
  };

  return [`${findMarker(input, 4)}`, `${findMarker(input, 14)}`];
}