#AoC 2022 | Day 6 | Solutions & Spoilers

1578 messages ยท Page 2 of 2 (latest)

edgy bramble
#

Or no wait iter gives you a .... &[u8]?

smoky flint
#

it extends Iterator, basically

edgy bramble
#

Yeah
That's going to take some getting used to
Never had crates extending other crates before

latent crown
ashen kindle
#

what in the ferrisBongoHyper are we talking about

silent forge
#

i feel like i would die if someone in real life walked up to me having a conversation and said "what in the ferrisBongoHyper are we talkling about?"

rustic crow
# 
def find_marker(sequence, num_characters):
    unique_characters = {}
    start_idx = 0
    end_idx = num_characters - 1

    for i in range(end_idx+1):
        unique_characters[sequence[i]] = unique_characters.get(sequence[i], 0) + 1

    while end_idx < len(sequence) and len(unique_characters.keys()) < num_characters:
        unique_characters[sequence[start_idx]] = unique_characters.get(sequence[start_idx], 0) - 1
        if unique_characters[sequence[start_idx]] == 0:
            unique_characters.pop(sequence[start_idx])

        start_idx += 1
        end_idx += 1

        unique_characters[sequence[end_idx]] = unique_characters.get(sequence[end_idx], 0) + 1

    return end_idx + 1

with open("problem_6_input", "r") as input_file:
    sequence = input_file.read()
    print(find_marker(sequence, 4))
    print(find_marker(sequence, 14))

Both parts solved in one

real goblet
#

my rust solution is hilarious looking

#

part one looks innocent enough

fn part1(input: &[u8]) -> AocResult<i32> {
  let mut count = [0u8; 256];
  let mut dupes = 0;
  

  let mut inc = |b: u8| {
    count[b as usize] += 1;
    if count[b as usize] == 2 {
      dupes += 1;
    }
  };

  inc(input[0]);
  inc(input[1]);
  inc(input[2]);
  inc(input[3]);

  let mut res = 4;
  for &[l, _, _, _, r] in input.array_windows() {
    count[l as usize] -= 1;
    if count[l as usize] == 1 {
      dupes -= 1;
    }
    count[r as usize] += 1;
    if count[r as usize] == 2 {
      dupes += 1;
    }
    res += 1;
    if dupes == 0 {
      break;
    }
  }
  Ok(res)
}
sonic coral
# 
[[print(min([b+a for b,c in enumerate(l[a:])if all([int(l[b:b+a].count(x))<2for x in l[b:b+a]])]))for l in open('day6_input')]for a in(4,14)]

any suggestions on how to further golf this?

real goblet
#

part 2 just looks dumb

fn part2(input: &[u8]) -> AocResult<i32> {
  let mut count = [0u8; 256];
  let mut dupes = 0;
  

  let mut inc = |b: u8| {
    count[b as usize] += 1;
    if count[b as usize] == 2 {
      dupes += 1;
    }
  };

  inc(input[0]);
  inc(input[1]);
  inc(input[2]);
  inc(input[3]);
  inc(input[4]);
  inc(input[5]);
  inc(input[6]);
  inc(input[7]);
  inc(input[8]);
  inc(input[9]);
  inc(input[10]);
  inc(input[11]);
  inc(input[12]);
  inc(input[13]);

  let mut res = 14;
  for &[l, _, _, _, _, _, _, _, _, _, _, _, _, _, r] in input.array_windows() {
    count[l as usize] -= 1;
    if count[l as usize] == 1 {
      dupes -= 1;
    }
    count[r as usize] += 1;
    if count[r as usize] == 2 {
      dupes += 1;
    }
    res += 1;
    if dupes == 0 {
      break;
    }
  }
  Ok(res)
}
#

same code, just wider

smoky flint
#

bruh what

real goblet
#

I'm also not sure whether array windows is cheap or not pithink

#

I hope it returns a sized view

smoky flint
#

it's a view, yeah

real goblet
#

actually, never mind, I unpack it ๐Ÿคก

#

I should not do that

#

I mean, the idea of my solution is easy enough, build the initial window and then move it along

analog portal
sonic coral
#

ik

real goblet
#

I don't think you can do it much cheaper than this

#

(other than me being dumb and unpacking)

smoky flint
#

why didn't you use a loop for...that part

real goblet
#

for the inc part?

smoky flint
#

mhm

real goblet
#

yeah, probably should have

#

but with vim macros it's so easy to just generate the other lines

#

yyp<c-a>

#

copy line, paste line, increment number

#

(yes, vim has commands to increment and decrement numbers)

#

(it's very useful)

smoky flint
#

ya, but like...๐Ÿ˜”

real goblet
#

but I get the point, I should be able to just unify the functions

analog portal
real goblet
#

with some const generics

sonic coral
analog portal
#

weird

sonic coral
#

i assume the first part is right

analog portal
smoky flint
#

i'm guessing you're running in a repl

real goblet
#

it's amusing to me that adding inc here is an error

image.png
devout rain
real goblet
#

because mutable borrows

sonic coral
#

ive looked at it, i want to stay in one line tho

real goblet
#

but the other loop is fine

image.png
sonic coral
#

thx

real goblet
#

actually, can some rust person explain why that is?

devout rain
sonic coral
#

๐Ÿ˜ญ

real goblet
#

why is it an error in the first loop I posted?

#

oh, it complains about dupes being borrowed?

smoky flint
#

i think

real goblet
#

dupes and count are mutably borrowed

analog portal
median python
#

I feel like day 6 was suspiciously easy, day 7 is gonna be the 2022 equivalent to the lanternfish problem

smoky flint
real goblet
# 
fn part1(input: &[u8]) -> AocResult<i32> {
  let mut count = [0u8; 256];
  let mut dupes = 0;
  

  let mut inc = |b: u8| {
    count[b as usize] += 1;
    if count[b as usize] == 2 {
      dupes += 1;
    }
  };

  for i in 0..4 {
    inc(input[i]);
  }

  let mut res = 4;
  for &[l, _, _, _, r] in input.array_windows() {
    count[l as usize] -= 1;
    if count[l as usize] == 1 {
      dupes -= 1;
    }
    inc(r); // if the function is inlined, this works
    res += 1;
    if dupes == 0 {
      break;
    }
  }
  Ok(res)
}
analog portal
sonic coral
#

everythong is 1 line if you exec(bytes)

real goblet
#

I feel this is rust's borrow checker being too dumb to understand what's doing on pithink

devout rain
dreamy panther
#

late but I will share my code

# 
import numpy as np
found = False
index = 0

with open("inp.txt", "r") as f:
    for line in f:
        q = []
        line = line.replace("\n", "")
        for i in range(len(line)):
            q.append(line[i])
            if(len(q) == 14): #PART ONE JUST WRITE 4
                if np.unique(q).size == len(q):
                    index += i+1
                    found = True
                else:
                    q.pop(0)
            if found:
                found = False
                break
print(index)
smoky flint
#

hm

analog portal
analog portal
sonic coral
analog portal
#

going to be pretty much impossible to go below 69 today

dreamy panther
#

does someone know if set had method unique or sth like that to know if set has unique elements?

pseudo nova
#

a set by definition only has unique elements

smoky flint
#

if you passed those references, it would work, probably

real goblet
dreamy panther
real goblet
#

I don't see how count or dupes are borrowed by things in the loop

#

(other than inc)

smoky flint
real goblet
#

what's the lifetime of that borrow?

#

I would have assumed it was taken and immediately released after the expression

#

but apparently not

smoky flint
#

hm. actually, idk

smoky flint
real goblet
#

I know lambdas with mutable captures have issues in general...

#

because they don't annotate lifetimes properly

analog portal
real goblet
#

returning references from a lambda

#

but this case here seems far more mundane

#

also, wtf const generics

image.png
#

can I really not do this?

#

that's...not great

#

yeah, this kind of generics is very much a weak point of rust

#

even without looking at variadic generics

smoky flint
#

so since you mutably borrow it a second time between the creation of the closure and using the closure, you get an error

real goblet
#

sometimes I hate rust...

fn solve<const N: usize>(input: &[u8]) -> AocResult<i32> {
  let mut count = [0u8; 256];
  let mut dupes = 0;
  

  let mut inc = |b: u8| {
    count[b as usize] += 1;
    if count[b as usize] == 2 {
      dupes += 1;
    }
  };

  for i in 0..N-1 {
    inc(input[i]);
  }

  let mut res = (N-1) as i32;
  for window in input.array_windows::<N>() {
    let l = window[0];
    count[l as usize] -= 1;
    if count[l as usize] == 1 {
      dupes -= 1;
    }
    let r = window[N-1];
    count[r as usize] += 1;
    if count[r as usize] == 2 {
      dupes += 1;
    }
    res += 1;
    if dupes == 0 {
      break;
    }
  }
  Ok(res)
}

fn part1(input: &[u8]) -> AocResult<i32> {
  solve::<{4+1}>(input)
}

fn part2(input: &[u8]) -> AocResult<i32> {
  solve::<{14+1}>(input)
}
smoky flint
#

that thread does give a solution it seems. and you're already using nightly with array_windows

real goblet
#

yes, I could try using the nightly feature, but it's just an annoying restriction

smoky flint
#

yeah, definitely

real goblet
#

I guess the concept of constexpr is very immature in rust

edgy bramble
smoky flint
#

also, if you did

  let inc = |b: u8, c: &mut [u8; 256], d: &mut i32| {
    c[b as usize] += 1;
    if c[b as usize] == 2 {
      *d += 1;
    }
  };
``` you could use it in the loop, but it's pretty much just as annoying
real goblet
#

which is...a bad workaround

edgy bramble
#

I meant - ...
My entire Rust function is 9 lines

real goblet
edgy bramble
real goblet
edgy bramble
vast oliveBOT
#

events/advent_of_code/2022/6/rust/src/main.rs lines 3 to 12

fn find_unique_window(text: &str, length: usize) -> usize {
    let windows = text.as_bytes().windows(length);

    for (index, window) in windows.enumerate() {
        if window.iter().unique().count() == length {
            return length + index;
        }
    }
    panic!("did not find")
}```
real goblet
#

oh, it's O(N*K)

#

not O(N)

#

sad

smoky flint
#

you can easily get an O(N) sol without resorting to shenanigans though

real goblet
#

you think my thing is shenanigans? it's just counting but with a sliding window

#

(actually making use of the fact that it's a sliding window)

edgy bramble
smoky flint
#

fairly clearly. unique() needs to iterate over the window each time

real goblet
#

at these tiny input sizes it's hard to measure things

edgy bramble
smoky flint
real goblet
#

ignoring reading the string I get 5us for the actual logic

#

I really hope that array_windows is O(n) overall...

smoky flint
#

well, it's shenanigans due to rust, not the solution itself

edgy bramble
#

Fenix do you have a job?

real goblet
#

I do

edgy bramble
#

Do you actually have to build for time complexity?

#

Would my solution be thrown out just because it was "too slow"?*

real goblet
#

it depends, I do work a bunch with data processing pipelines, so I need to keep performance in mind there

#

granted, with distributed data pipelines there are bigger issues than just how long it takes to process stuff

smoky flint
# 
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.num == 0 {
            return None;
        }
        // SAFETY:
        // This is safe because it's indexing into a slice guaranteed to be length > N.
        let ret = unsafe { &*self.slice_head.cast::<[T; N]>() };
        // SAFETY: Guaranteed that there are at least 1 item remaining otherwise
        // earlier branch would've been hit
        self.slice_head = unsafe { self.slice_head.add(1) };

        self.num -= 1;
        Some(ret)
    }
```i think this is O(n)
edgy bramble
#

#[inline]
That's a new one for me

smoky flint
#

hints to the compiler to inline

real goblet
#

this is the source for array_windows?

smoky flint
#

yeah the next method for the struct it returns

#

oh, this is important too,

pub struct ArrayWindows<'a, T: 'a, const N: usize> {
    slice_head: *const T,
    num: usize,
    marker: PhantomData<&'a [T; N]>,
}
real goblet
#

PhantomData pithink

smoky flint
#

fantomdata fenix

real goblet
#

fiery fantom fenix

#

would have been decent for halloween

smoky flint
#

damn, yeah. why didn't we think of that

real goblet
#

but yeah, it looks like it should be O(n)

smoky flint
#

the pointer cast is constant, so yeah

#

actually does it take any time? surely that's done at compile time

hoary raft
real goblet
#

it should compile away to nothing

smoky flint
#

yeah. what's the time complexity of that ๐Ÿค” still constant ig?

real goblet
#

idk if it's worth talking about time complexity at that point ๐Ÿ˜›

smoky flint
#

ok but, do the c have to be non-zero?

real goblet
#

notably 0 is in O(1) but 1 is not in O(0)

#

0/1 tends to a constant as the (irrelevant) parameter grows large

#

1/0...doesn't feel so well

smoky flint
#

do you have a typo in that message

real goblet
#

oh

#

fixed

smoky flint
#

ok, back to writing essays ๐Ÿ˜”

real goblet
#

so wrt inc, it works fine if I call inc a bunch before doing any other mutable borrow

#

so the borrow checker is not that smart wrt to lambdas and lifetimes

#

unfortunate

#

if I were using C++ I would totally write small helper lambdas like this to not repeat code

#

(and make the overall logic more readable)

#

something akin to

  for i in 0..N-1 {
    inc(input[i]);
  }

  let mut res = (N-1) as i32;
  for window in input.array_windows::<N>() {
    dec(window[0]);
    inc(window[N-1]);

    res += 1;
    if dupes == 0 {
      break;
    }
  }
smoky flint
real goblet
#

maybe with better names

real goblet
#

it would be sensible if it borrowed for the call, but seems that's not the semantics of rust lambdas

#

I know it likely wouldn't be implemented like that, but the borrowing semantics that makes sense to me would be to grab ownership during the call

#

but I guess rust doesn't have a way of expressing that

#

(other than explicitly passing the arguments)

smoky flint
#

it has to have the mutable borrow when you define the closure, which makes more sense if you're passing the closure into things, i think

real goblet
#

it does, but it feels like there are several flavors of lambdas at play here

#

some absolutely need to capture state and hold it, some could really capture as needed

#

but you can't express the latter in rust

#

(other than passing args explicitly)

smoky flint
#

yeah, i think you're right ๐Ÿค”

real goblet
#

I could encapsulate the counter in a struct I guess

#

and expose two methods

#

I guess this is clean enough

struct DupCounter {
  count: [u8; 256],
  dupes: i32,
}

impl DupCounter {
  fn new() -> Self{
    DupCounter { count: [0; 256], dupes: 0 }
  }
  fn add(&mut self, b: u8) {
    self.count[b as usize] += 1; 
    if self.count[b as usize] == 2 {
      self.dupes += 1;
    }
  }
  fn remove(&mut self, b: u8) {
    self.count[b as usize] -= 1; 
    if self.count[b as usize] == 1 {
      self.dupes -= 1;
    }
  }
}

fn solve<const N: usize>(input: &[u8]) -> AocResult<i32> {
  let mut counter = DupCounter::new();

  for i in 0..N-1 {
    counter.add(input[i]);
  }

  let mut res = (N-1) as i32;
  for window in input.array_windows::<N>() {
    counter.remove(window[0]);
    counter.add(window[N-1]);

    res += 1;
    if counter.dupes == 0 {
      break;
    }
  }
  Ok(res)
}
#

(modulo the N that is offset from what I want it to be)

#

maybe I should just use that nightly feature

smoky flint
#

just use windows instead of array_windows

real goblet
#

err...

image.png
#

but without array_windows the bounds checks probably won't be elided ๐Ÿ˜ญ

#

(I could go unsafe...)

#

but yeah, maybe I should ditch the idea that felt correct in favor of the solution that the current state of rust likes

#

unsatisfying, but what can you do?

#

one of these days will actually cross the 1ms threshold

image.png
#

wasn't lanternfish day 6 last year?

#

(granted, the intended solution to lanternfish was cheap)

edgy bramble
real goblet
#

nothing fancy

dense oracle
real goblet
#

just something that uses std::time::Instant::now

#

and runs the program N times and takes the average (after throwing out a fraction of outliers)

#

I hope Instant::now is fine for use for this pithink

#

Instants are always guaranteed, barring platform bugs, to be no less than any previously measured instant when created, and are often useful for tasks such as measuring benchmarks or timing how long an operation takes.
ok, seems like a sensible thing to use

cerulean cedar
#

Pretty happy i managed to get the answer in one line:

with open('day6\input.txt', 'r') as f:
    input = f.read()


ans = [num for num, char in enumerate(input[14:], 14) if len(set([input[i] for i in range(num-14, num)])) == 14][0]```
real goblet
#

more dumb shell solutions

solve() { perl -pe "s/(.)(?=(.{$(($1-1))}))/\1\2\n/g" | nl -v$1 | grep -vP "([a-z]).{0,$(($1-2))}\1" | head -n1; }
# 
$ solve 4 < inputs/06input 
  1578    bdjq
$ solve 14 < inputs/06input 
  2178    mdcbnwqgshpvfj
dense oracle
#

Are you sure that's not a perl solution?

real goblet
#

part of it is perl

#

it also uses three other programs

cunning nest
sonic coral
#

you should be able to do the entire program at compile time with rust

#

i would think

#

with procmacros

smoky flint
#

well yeah. you can run arbitrary code during compile time

#

also build scripts exists, so before compile time lol

cerulean cedar
# cunning nest I like this solution! Also note that `len(set([input[i] for i in range(num-14, n...

Thanks! Yeah I noticed that earlier when I was looking at other peoples solutions, however when I try to implement it into my code it outputs IndexError: list index out of range, I have no idea why because also when I copied your replacement it worked, but when I hand type it doesn't, idk I'm very confused, this is my hand typed code

with open('day6\input.txt', 'r') as f:
    input = f.read()


ans = [num for num, char in enumerate(input[14:], 14) if len(set([input[num-14:num]])) == 14][0]
halcyon urchin
cerulean cedar
#

Yeah I don't, that still doesn't fix my issue index error issue tho

smoky flint
#

it probably does

cerulean cedar
#

It doesn't I just tried it

#

I mean I don't even need the set() part, I can just contain input[num-14:num] with {}

smoky flint
#

that would make a set with a single string in it, not a set with each of the elements in input[num-14:num]

halcyon urchin
cerulean cedar
#

wat

#

how

#

HEH

#

NOW IT WORKS?

#

I literally swear I did that earlier

#

Im so confused

halcyon urchin
cerulean cedar
#

So why doesn't this work

ans = [num for num, char in enumerate(input[14:], 14) if len({input[num-14:num]}) == 14][0]
#

wait

#

thats not what I meant to paste

#

one sec

#

fixed

smoky flint
#

that would make a set with a single string in it, not a set with each of the elements in input[num-14:num]

halcyon urchin
cerulean cedar
#

wth

halcyon urchin
# cerulean cedar wth 
set(...) # takes an iterable
{...} # takes individual values
# a string is both an iterable and an individual value
cerulean cedar
halcyon urchin
# 
>>> stringy = "the elves keep asking me to help!"
>>> list(stringy)
['t', 'h', 'e', ' ', 'e', 'l', 'v', 'e', 's', ' ', 'k', 'e', 'e', 'p', ' ', 'a', 's', 'k', 'i', 'n', 'g', ' ', 'm', 'e', ' ', 't', 'o', ' ', 'h', 'e', 'l', 'p', '!']
>>> [stringy]
['the elves keep asking me to help!']
>>> set(stringy)
{'t', 'e', 'p', '!', 'l', 'h', 'n', ' ', 's', 'a', 'm', 'k', 'o', 'v', 'g', 'i'}
>>> {stringy}
{'the elves keep asking me to help!'}
cerulean cedar
#

Right, so in my code

ans = [num for num, char in enumerate(input[14:], 14) if len(set([input[num-14:num]])) == 14][0]

I made a list with one element in it, and then made a set out of that list, so the set had one element in it, thus a length of one, I see, my only remaining question is why did it give a type error then?

#

Wait... Don't tell me it's because of the [0] at the end

halcyon urchin
#

IndexError: Because the list comp came out empty (i.e. [][0])

smoky flint
#

because your set will always have one element, so your list comp will have nothing in it, so it errors

cerulean cedar
#

Bruhhhhhh I thought it was something to do with the num-14:num, this is the disadvantages of trying to code everything in one line :/

prisma spade
#

what disadvantages? seems pretty good for reducing char counts

#

also have we still not gone lower than 69?

cerulean cedar
#

No clue, not to my knowledge but I haven't really been keeping up with golf

cerulean cedar
cerulean cedar
prisma spade
cerulean cedar
#

๐Ÿง 

prisma spade
#

just set breakpoints anywhere

#

instead of being restricted to lines

cerulean cedar
#

wdym

prisma spade
#

if you're the interpreter, then you can run the code however you like

#

can inspect each variable and stop execution whenever

halcyon urchin
#

Reject CPython - Return to ๐Ÿง ๐Ÿ

prisma spade
#

just look at the assembly and emulate x86

#

not that hard

devout rain
mighty oyster
#

!e print("test"[-3:3])

vast oliveBOT
#

@mighty oyster :white_check_mark: Your 3.11 eval job has completed with return code 0.

es
cerulean cedar
#

As in the program starts checking at index 14, and also the enumerate counter starts at 14

#

idek why it's there, my code went through so many iterations during writing and I probably just forgot it was there

#

because I originally i was confused and doing != 14 at the end, which would just return 0 all the time, so I did that ^ but then I corrected it to == and forgot to change the rest of the code

devout rain
devout rain
cerulean cedar
devout rain
#

You still have the [3:] there which you do not need.

#

You have to remove both parts, not just the ,num part

#

!e

for i in range(6):
    print('thisisatest'[i-4:i])
vast oliveBOT
#

@devout rain :white_check_mark: Your 3.11 eval job has completed with return code 0.

001 | 
002 | 
003 | 
004 | 
005 | this
006 | hisi
cerulean cedar
devout rain
cerulean cedar
devout rain
#

and if you next again you get the next, etc

cerulean cedar
#

ah, so is it just a different way of doing [0] at the end?

devout rain
#

better than building the collection entirely and taking [0] from it. here you just get 1 and you're done.

cerulean cedar
devout rain
#

right.

cerulean cedar
#

Yeah that would be more efficient, interesting

halcyon urchin
# 
>>> my_generator = (i**2 for i in range(100))
>>> next(my_generator)
0
>>> next(my_generator)
1
>>> next(my_generator)
4
>>> next(my_generator)
9
>>> next(my_generator)
16
>>> next(my_generator)
25
devout rain
#

yeah, so there are 4096 chars in the input, with a list you have to look at all of them, with a generator is only goes as afar as it needs to.

cerulean cedar
cerulean cedar
#

I should look into generator's more later, I'll write that down

devout rain
cerulean cedar
#

I mean clearly it doesn't because when I run it without that, it just outputs exactly the same thing

#

Shouldn't that raise a index error?

# 
ans = [num for num, _ in enumerate(input) if len(set(input[num-14:num])) == 14]
halcyon urchin
#

Slices don't care if the index is out of range, and backwards slices just stop before they start (i.e. empty string). Remember that negative indexes count from the end of the string (-1 is last, -2 is second last, etc.)

>>> "abcdefghijklmnopqrstuvwxyz"[0-14:0]
''
>>> "abcdefghijklmnopqrstuvwxyz"[20-14:20]
'ghijklmnopqrst'
>>> "abcdefghijklmnopqrstuvwxyz"[30-14:30]
'qrstuvwxyz'
>>> "abcdefghijklmnopqrstuvwxyz"[40-14:40]
''
>>> "abcdefghijklmnopqrstuvwxyz"[-20:20] # If you loop back far enough you can get a valid range
'ghijklmnopqrst'
cerulean cedar
#

oh

#

one question, why does that last line return 'ghijklmnopqrst'?
Shouldn't it just return the first 20 letters?

devout rain
#

fun with negative indexes and slices. ๐Ÿ™‚

halcyon urchin
devout rain
cerulean cedar
#

ahhh I see, that hurts my brain lmao

devout rain
#

but fir our example, the len of the listr is 4096, so there's no way that num-14:num will ever overlap.

halcyon urchin
#

I can't really imagine where [-20:20] would be useful, but [1:-1] is useful for stripping one leading and one trailing char (e.g. "<123>"[1:-1] is "123")

devout rain
#

but [i-14:14] was on the other hand, quite useful last night.

halcyon urchin
#

*:i

cerulean cedar
#

or rather, this code:

set(input[num-14:num])```
#

Because [num-14:num] when num = 10 is equivalent to [-4:10]

halcyon urchin
#

Not quite - it starts at the 4th-last char and moves until it is at or past the 10th char. It's already past the 10th char so the string is empty

cerulean cedar
devout rain
cerulean cedar
#

oh nvm

devout rain
cerulean cedar
#

like 4093-4096

devout rain
#

no.

#

start at 4092, end at 10, there is no wrapping so it's just an empty string. 4096 is already > 10 so it just stops.

#

think of it like this:

start = 4092
end = 10
while start < end:
   yield data[start]
   start += 1
cerulean cedar
#

thanks both of you for helping me with everything I appreciate it :D

devout rain
sacred smelt
# 
with open("06_input.txt") as file:
    data = file.read().splitlines()

message = data[0]
count = 14
while len(set(message[count - 14 : count])) != 14:
    count += 1

print(count)
halcyon urchin
dawn talon
dull vessel
#

what approaches for unique character count did people use besides just len(set(buffer_list))?

queen perch
# 
import re

def solve_regex(amt: int) -> None:
    c = []
    f: str = ""

    for i in range(1, amt+1):
        c.append(f"\{i}")
        f += "(.)(?!" + "|".join(c) + ")"
    print(re.search(f, open("input.txt").read().strip()).end())
    
solve_regex(4)
solve_regex(14)```

I am being silly, but cannot see how the `solve_regex(14)` is giving none, but the `solve_regex(4)` gives the correct answer
hollow nest
#

pandas: rick and roll

eternal wyvern
#

You could always use named patterns (?P<{i}>) and \k<{i}>

#

Also you should be using raw strings

#

(I think rf is a thing)

#

(it is)

image.png
queen perch
#

KK. Will try that and see. Just messing around
Thanks for the feedback

granite veldt
#

got the time to get around to six ๐ŸŽ‰

#

this took me a good bit less time than 5

#

the solutions for part 1 and part 2 were both pretty similar as well

# 
def part_1(raw_input: str) -> int:
    return (
        raw_input.index(
            "".join([i for i in windowed(raw_input, 4) if len(set(i)) == 4][0])
        )
        + 4
    )


def part_2(raw_input: str) -> int:
    return (
        raw_input.index(
            "".join([i for i in windowed(raw_input, 14) if len(set(i)) == 14][0])
        )
        + 14
    )
prisma spade
# 
s=input();i=0
for j in 4,14:
 while len({*s[i-j:i]})<j:i+=1
 print(i)```
elder holly
prisma spade
#

i like the problems that take longer

#

because i rank higher

#

5 min mistake on a 1 min problem vs 5 min mistake on a 10 min problem

queen perch
#

Basically are the same, just with a different window size. Can make it into a single function also.

Loved that puzzle

queen perch
prisma spade
#

i usually choke

#

it's just that my chokes have less impact on longer problems

karmic cape
# 
    for i in range(1, amt+1):
        c.append(f"\{i}")
        f += "(.)(?!" + "|".join(c) + ")"```
wouldnt this make more sense
```python
    for i in range(1, amt+1):
        f += "(.)(?!" + "|".join([f"\{i}"]*i) + ")"```
or i guess this even but thats unrelated
```python
    for i in range(amt):
        f += f"(.)(?!\{i}" + f"|\{i}"*i + ")"```
real goblet
#

lol, I went for the leaderboards for part of my first AoC year

#

I don't think I ever will again

prisma spade
#

nice

real goblet
#

unless I move to some other time zone

prisma spade
#

i think i have a good shot as long as i don't choke

real goblet
#

I started doing AoC in unfamiliar languages instead

prisma spade
#

sounds fun

real goblet
#

I learned rust last year and wrote pretty fast programs overall

#

(not fast to write, but fast to run)

devout rain
eternal wyvern
real goblet
#

(I would like to imagine my rust code isn't terrible)

edgy bramble
prisma spade
#

everything was 1 line and ternary operators were sprinkled everywhere

real goblet
#

my goal last year was for my total time to be <1s

#

which I made with some margin

#

~400ms, maybe a bit less

eternal wyvern
real goblet
#

250 of which is for one single problem ๐Ÿ˜›

prisma spade
#

now try less than 0.5s for this year

eternal wyvern
real goblet
#

day 23

prisma spade
#

probably a brute force graph problem

real goblet
#

not graph

#

but a puzzle moving pieces around

prisma spade
#

oh

eternal wyvern
#

Oh god that one

real goblet
#

my next slowest one was ~50ms, I would imagine that was the beacon one

#

oh it wasn't

prisma spade
#

ok but 23 can be solved using a graph

real goblet
#

I mean, it is a graph

#

but it's not much of a graph problem

prisma spade
#

ic what you mean

real goblet
#

not on the graph of the board at least

#

I think I did Dijkstra, but the "nodes" were states of the board

#

I probably added an heuristic to get A* to squeeze some extra time out

#

oh beacons was as early as day 19?

#

I liked beacons, it completely stumped me for a bit

#

so far in 2022 I'm way below 1ms in total

#

~170us

prisma spade
#

looks interesting

real goblet
#

beacons?

#

it was hard to even come up with a good way to approach it at first

prisma spade
#

if i were going for leaderboard, i could probably naively approach this

real goblet
#

what's even the naive approach?

prisma spade
#

take the first beacon to have absolute coords, then try every orientation while translating some point in a beacon to the bottom left point in beacon 0; you can sliding window possible groups of 12 points

#

it would take a while to run, but that's probably the naive approach

real goblet
devout rain
eternal wyvern
#

Nice

real goblet
#

I jumped between C++ and python when I did interviews

#

I even asked the interviewer which one they would prefer in one interview ๐Ÿ˜›

prisma spade
#

how long was the day 19 golf lol

real goblet
#

no clue

#

I think with some linalg libraries you can probably get it down a lot

prisma spade
#

true

real goblet
#

or other kinds of solvers

devout rain
#

The beacon one? I have a short (ish) solution somewhere, but not golfed.

real goblet
#

but yeah, the approach is basically to try different rotations of one beacon point and match it to another and build up a graph of beacons

prisma spade
#

yeah

#

oh wait so the naive approach is the actual approach

real goblet
#

kinda

prisma spade
#

here i was thinking i could optimize it somehow ๐Ÿ˜”

real goblet
#

you can avoid actually testing the 24 rotations for most beacons by computing all internal distances and seeing how big fraction matches the other beacon

#

and only if distances match, actually do the rotations

prisma spade
#

oh yeah that works

real goblet
#

which saves a lot of time

#

I think my solution is at like 5ms

prisma spade
#

oh wow

real goblet
#

down from probably 120 ish

devout rain
#

I can't find the short one. but this is ~30 lines:

from itertools import combinations,product

def find_rotation(scan,rebased0):
    for rot,rot_scan in rotations(scan).items():
        rebased = {p1: {psub(p1,p2) for p2 in rot_scan} for p1 in rot_scan}
        for p1,p2 in product(rebased0,rebased):
            if len(rebased0[p1]&rebased[p2])>11: return p1,p2,rot

def make_absolute(scanners):
    absolute,*task_list = scanners
    scanner_locs = {(0,0,0)}
    while task_list:
        scan = task_list.pop(0)
        rebased0 = {p1: {psub(p1,p2) for p2 in absolute} for p1 in absolute}
        result = find_rotation(scan,rebased0)
        if result is None:
            task_list.append(scan)
        else:
            p1,p2,rot = result
            absolute |= {padd(rotate(s,*rot), psub(p1,p2)) for s in scan}
            scanner_locs.add(padd((0,0,0), psub(p1,p2)))
    return len(absolute), scanner_locs

def psub(p1,p2): return p1[0]-p2[0],p1[1]-p2[1],p1[2]-p2[2]
def padd(p1,p2): return p1[0]+p2[0],p1[1]+p2[1],p1[2]+p2[2]
def rotate(s,a,b,c,i,j,k): return (a*s[i],b*s[j],c*s[k])
def rotations(scan): return {r: {rotate(s,*r) for s in scan} for r in orientations}
def mhd(a,b): return abs(a[0]-b[0])+abs(a[1]-b[1])+abs(a[2]-b[2])

scanners = [{eval(line) for line in scanner.splitlines() if '--' not in line}
            for scanner in open(filename).read().split('\n\n')]
beacons, scanner_locs = make_absolute(scanners)

print('part1:', beacons)
print('part2:', max(mhd(a,b) for a,b in combinations(scanner_locs,2)))
real goblet
#

basically what I did was build an MST of things that should connect based on the distances, then rotate them in place

#

def rotate(s,a,b,c,i,j,k): is one hell of a signature

prisma spade
#

ig aoc isn't like lc, sometimes the bruteforcey solution is the actual solution

devout rain
#

yeah, coding in a rush... ๐Ÿ™‚

real goblet
#

that's...24 lines of my code

devout rain
real goblet
#

just saying the actual code it a bit longer with that included ๐Ÿ˜›

devout rain
#

I went through different iterations of auto generating it vs just using the generated version.

real goblet
#

I just wrote them out, it's not so hard if you know how to not create left handed systems

devout rain
#

lol @ the beacons problem done in Dyalog:

โŽ•IOโ†0
pโ†โ†‘ยจโŽยจยจ'-'โŽ•R'ยฏ'ยจยจ1โ†“ยจ{โตโŠ†โจร—โ‰ขยจโต}โŠƒโŽ•NGET'p19.txt'1
mโ†โ†‘{โˆชโต,,({โต(1โŒฝ1โŠ–โต)}3 3โด1 0 0 0 0 1 0 ยฏ1 0)โˆ˜.(+.ร—)โต}โฃโ‰ก,โŠ‚โˆ˜.=โจโณ3
qโ†0
aโ†(โŠƒp){0=โ‰ขโต:โบ โ‹„ i jโ†โŠƒโธ12โ‰คโŠข/zโ†โ†‘โบโˆ˜{{{โตโŒทโจrโณโŒˆ/rโ†โŠข/โต}{โบ(โ‰ขโต)}โŒธโต}โค2,[1 2]โต-โค1โค1 2โŠขโบ}ยจmโˆ˜(+.ร—โค2 1โค2 2)ยจโต โ‹„ (โˆชโบโช((jโŒทm)+.ร—โค2 1โค2 2โŠขiโŠƒโต)-โค1โŠขdโŠฃqโŒˆโ†+/|dโ†(โŠ‚i j 0)โŠƒz)โˆ‡โต/โจiโ‰ โณโ‰ขโต}1โ†“p
โ‰ขa โ part 1
q โ part 2

that language is crazy

prisma spade
#

holy hell

devout rain
# real goblet where is orientations defined?

ah here we go, I had another paragraph about how I generated it:

orientations = [(1,1,1,0,1,2),(1,1,1,1,2,0),(1,1,1,2,0,1),(1,1,-1,2,1,0),(1,1,-1,1,0,2),(1,1,-1,0,2,1),(1,-1,-1,0,1,2),(1,-1,-1,1,2,0),(1,-1,-1,2,0,1),(1,-1,1,2,1,0),(1,-1,1,1,0,2),(1,-1,1,0,2,1),(-1,1,-1,0,1,2),(-1,1,-1,1,2,0),(-1,1,-1,2,0,1),(-1,1,1,2,1,0),(-1,1,1,1,0,2),(-1,1,1,0,2,1),(-1,-1,1,0,1,2),(-1,-1,1,1,2,0),(-1,-1,1,2,0,1),(-1,-1,-1,2,1,0),(-1,-1,-1,1,0,2),(-1,-1,-1,0,2,1)]
#

generated from::

views, faces  = [(-1,-1,1),(-1,1,-1),(1,-1,-1),(1,1,1)],[(0,1,2),(1,2,0),(2,0,1)]
orientations  = [v+f for v,f in product(views,faces)]
orientations += [(-a,-b,-c,k,j,i) for a,b,c,i,j,k in orientations]
prisma spade
#

what do the numbers mean mioderp

real goblet
#

here it my thing

  let mappings: [fn(Point) -> Point; 24] = [
    |Point { x, y, z }| Point::new(x, y, z),
    |Point { x, y, z }| Point::new(-x, -y, z),
    |Point { x, y, z }| Point::new(-x, y, -z),
    |Point { x, y, z }| Point::new(x, -y, -z),
    |Point { x, y, z }| Point::new(y, z, x),
    |Point { x, y, z }| Point::new(-y, -z, x),
    |Point { x, y, z }| Point::new(-y, z, -x),
    |Point { x, y, z }| Point::new(y, -z, -x),
    |Point { x, y, z }| Point::new(z, x, y),
    |Point { x, y, z }| Point::new(-z, -x, y),
    |Point { x, y, z }| Point::new(-z, x, -y),
    |Point { x, y, z }| Point::new(z, -x, -y),
    |Point { x, y, z }| Point::new(y, x, -z),
    |Point { x, y, z }| Point::new(-y, -x, -z),
    |Point { x, y, z }| Point::new(-y, x, z),
    |Point { x, y, z }| Point::new(y, -x, z),
    |Point { x, y, z }| Point::new(z, y, -x),
    |Point { x, y, z }| Point::new(-z, -y, -x),
    |Point { x, y, z }| Point::new(-z, y, x),
    |Point { x, y, z }| Point::new(z, -y, x),
    |Point { x, y, z }| Point::new(x, z, -y),
    |Point { x, y, z }| Point::new(-x, -z, -y),
    |Point { x, y, z }| Point::new(-x, z, y),
    |Point { x, y, z }| Point::new(x, -z, y),
  ];
prisma spade
#

just represent orientation as a quaternion frfr

earnest spoke
devout rain
#

those are the a,b,c,i,j,k used in rotations, they represent the various orientations

real goblet
#

there are only so many valid rotations

prisma spade
#

i forgot i'm supposed to underengineer these solutions

#

nvm don't use quaternions

eternal wyvern
real goblet
#

no p.x p.y p.z noise

eternal wyvern
#

No but like
Point { x: z, y: x, z: y }

devout rain
#

the short version is: the first scanner is in real space, and then for every other scanner rotate it until it maps on to that base space, and then update the base space, and if a scanner doesn't match yet, put it at the back of the queue and keep going.

#

I enjoyed the beacons problem.

real goblet
#

it was nice

#

I like problems that stump me for a bit

#

it's pretty rare for AoC

devout rain
#

I liked beacons more than the rotating puzzle find the seamonster puzzle.

real goblet
#

usually I have a pretty good idea what to do immediately

prisma spade
#

same

real goblet
#

oh right, that was a thing

#

the fun part is the second one

#

Finally, a deck worthy of shuffling!

image.png
eternal wyvern
#

Lemme go look at that one again lmao

real goblet
#

you'll want some basic number theory knowledge, like modular inverses

eternal wyvern
#

Oh lovely this is before I used aoc_helper lmao my code is such a mess

real goblet
#

I was lazy and realized it would just be some linear recurrence

#

and there is this magic algo to reconstruct linear recurrences from samples

eternal wyvern
#

That's kinda cool but I don't have the energy to understand it and there's no simple.wikipedia for it

#

Can you TL;DR?

real goblet
#

(magic)

eternal wyvern
#

Understandable

real goblet
#

iirc it's not that bad to understand if you actually sit down and look at it

#

but it's fun to use as a black box

#

simulate a bunch of steps, try finding the recurrence, extrapolate the recurrence

#

???

#

profit

prisma spade
real goblet
#

yes, exactly

prisma spade
#

seems freelo to me

real goblet
#

you want to simulate?

prisma spade
#

the shuffling? hell no

#

just keep track of where 2019 is at each step

real goblet
#

and then?

prisma spade
#

that's literally part 1

#

idk what part 2 is yet

real goblet
#

oh, part 1 is easy

#

that one you can simulate

prisma spade
#

thought so kekw

#

what's part 2

#

i don't feel like coding part 1

real goblet
prisma spade
#

you could probably brute-force to find a cycle

real goblet
#

cycle among 119315717514047 cards?

prisma spade
#

if you didn't feel like mathing

prisma spade
#

i did not read that

#

reading comprehension diff

real goblet
#

(fwiw that number is prime, which is actually helpful)

#

(because number theory reasons)

prisma spade
#

i haven't taken number theory ๐Ÿ˜”

#

but there should be a way to compose the shuffles into something predictable, unless i'm completely wrong

real goblet
#

well, it follows a linear recurrence

#

and not a particularly complicated one either

prisma spade
#

yeah

#

i haven't even looked at the different shuffles possible

#

but with numbers of this size, that has to be the case

real goblet
#

"deal into new stack" = reverse
"cut N cards" = rotate N steps (as in a cyclic shift)
"deal with increment N" = this is the weirder one

#

basically deal first card at index 0, the next at N the next at 2N, ... (and wrap around the deck as needed)

#

(or in math terms ||multiply by N modulo length of the deck||)

prisma spade
#

yep

real goblet
#

crucially, you can only invert that step (in general) if the modulo is prime

prisma spade
#

this just seems like modular arithmetic

real goblet
#

it is

prisma spade
#

tbh not too difficult if you've seen modular math before

real goblet
#

well, you can't even simulate it without the math, and simulation doesn't get you anywhere anyway

#

well, it gets you somewhere, but not far

prisma spade
#

any sane person knows that this is a math problem after they see those numbers

real goblet
#

I think you could write a program to take the instructions given in the input and simplify it

#

and then you just need to extrapolate it

#

"just"

prisma spade
#

or you could run a few cycles of simulation to see what the pattern is

real goblet
#

which requires some trick like exponentiation by squaring

#

so it's two things combined, some basic modular math knowledge to deal with the deck size, and some fast way of extrapolating to deal with the number of shuffles

prisma spade
#

yeah

real goblet
#

let's say most people weren't too happy about the difficulty of this one ๐Ÿ˜›

prisma spade
#

lol

#

i'm not allowed to say skill issue anymore

#

so uh

#

rip them

eternal wyvern
#

Puzzle issue ๐Ÿ™ƒ

#

I'm kidding I like the 'rethink the approach'-type puzzle

#

Just not that one

#

Or the trains one

prisma spade
#

i should probably catch up on past aoc problems

eternal wyvern
#

I like 'rethink this in a way that doesn't require extensive googling but isn't simple'-type puzzles the best

#

And/or intcode

#

I really liked intcode

real goblet
#

intcode was manageable if you had enough foresight to actually implement something that could easily be extended ๐Ÿ˜›

#

otherwise I imagine it would be painful

uncut plaza
#

what's intcode?

eternal wyvern
eternal wyvern
real goblet
prisma spade
#

now i'm curious

real goblet
#

intcode was building a virtual machine

prisma spade
#

oh fun

real goblet
#

it was basically every two days for the whole month

#

building on top of the previous one

prisma spade
#

which was the first?

uncut plaza
#

i see

uncut plaza
real goblet
#

day 2

#

5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25

#

so 2, 5 and every odd day after that

#

basically your intcode vm was used later on as a part of other puzzles

#

so if you had a bug or couldn't easily modify stuff as needed, sucks to be you

#

day 13 was amazing

#

when you realize what's going on and what they want you to do

eternal wyvern
#

I'll be honest I just rewrote it on day (I think 8 but I can check the git history) because I realised it would be used again lol

eternal wyvern
mellow bone
#

intcode killed my motivation in 2019. Was new to coding, so whatever I did was not expandable at all and I had to rewrite each time]

eternal wyvern
#

I'm sorry to hear that

#

I liked it though

mellow bone
#

Would love to go do it now since I'm not brand new anymore. Pretty sure I'd enjoy it now xD

vapid oar
#

did they really link all of the signal puzzles in AoC here

image.png
dense oracle
#

Well it is significant

timid blade
#

can someone explain how this (the example) is 5 ? ```
bvwbjplbgvbhsrlpgdmjqwftvncz

#

or share your thought process? i'm not sure how the answer is 5

granite veldt
# timid blade can someone explain how this (the example) is 5 ? ``` bvwbjplbgvbhsrlpgdmjqwftvn...

so, you're essentially trying to find the number of characters it takes to get to the start of this stream of text to the point at which you can find a sequence of four characters, all of which are unique. with bvwbjplbgvbhsrlpgdmjqwftvncz, the first character is b, the first four are bvwb. This doesn't match the criteria, since b is repeated. We try again, this time starting at v. We go down, and four characters later end up with vwbj, all of which are unique. The j here is the fifth character in the text, which means we need to go down five characters to get to the point where we have had a sequence of four, unique, characters.

timid blade
#

thanks for the clarification

hot grove
#

this is so easy lmao ```py

aoc problem 6

from collections import deque

def start_marker_i(buffer, length):
queue = deque(buffer[:length], length)
for i, c in enumerate(buffer[length:], length):
queue_chars = set(queue)
if len(queue_chars) == length:
return i
queue.append(c)

def main():
with open('6.txt') as f:
cont = f.read()
print(start_marker_i(cont, 4)) # part 1
print(start_marker_i(cont, 14)) # part 2

if name == 'main':
main()

half iron
# 
with open('day6.in', 'r') as file:
    stringa = file.read()

print(stringa)

consecutive = 0
caratteri_diversi = ""
count = 0

for carattere in stringa:
    count += 1
    if carattere not in caratteri_diversi:
        caratteri_diversi += carattere
        consecutive += 1
    else:
        consecutive = 0
        caratteri_diversi = ""
    if consecutive == 14:
        break


print(count)