AoC 2023 | Day 8 | Solutions & Spoilers

[round jetty]

by contradiction

assume sucha cycle exists

then at step 22 we are at the start location

but now, we are looking at the directions at index 2, rather than index 0

[potent ginkgo]

btw you definitely can't bruteforce today right?

[olive salmon]

yeah that's my point

[round jetty]

I'm saying that's not assumption

that's fundamentally guaranteed

by construction

[olive salmon]

[pure holly]

no

[round jetty]

it's not specific to the data

It's a proof that given the problem construction, any cycle on the graph will always be divisible by the number of steps

unless the steps array itself has cycles

sorry, direction array I should say

if the direction array is size 8, but it internally has a cycle of length 4 (i.e. it's just the same 4 directions repeated twice), then you can have cycles that are divisible by 4 instead of 8

if we exclude that though

then if the direction array is size 8, then all cycles must be divisible by 8: this isn't an artifact of the data

[tiny oasis]

I have reached the conclusion that: I successfully solved part 2 quickly by complete accident. My reading incomprehension paid off.

[round jetty]

just to emphasize; when we are writing cycles out here we assume that the cycles always traverse distinct nodes.
that's not actually necessarily the case and it's not the case for the input data either

[tiny oasis]

LCM occurred to me because I assume there were certain cycles... but looking closely, the cycles are more complicated than I expected

[round jetty]

In the actual data, you have cycles that look like this

A -> B -> C -> A -> D -> ...

in other words, you go through A multiple times in the cycle

but it's not a cycle yet, because each time you reached A, you were at a different index in the directions

[tiny oasis]

Here's what start/ends of the first cycle look like: ```py

start end startleft startright endleft endright
QKA QXZ QQD SSM SSM QQD
LBA GPZ XQJ PFH PFH XQJ
JMA VHZ CVR HFX HFX CVR
VMA MTZ DCG TDF TDF DCG
AAA ZZZ KPT QLD QLD KPT
RKA NDZ BGX BCX BCX BGX

[olive salmon]

we're discussing a different definition of cycle

[tiny oasis]

So, for start QKA, it ends on QXZ, and the next positions are inverted. Presumably the better solution here is to memo-ize the starts, repeat until I have a complete cycle.

[olive salmon]

i'm talking about just the first time you reach Z after stepping away from Z

if we account for the current position in the steps, then yes, it will still cycle

[round jetty]

it's not really a cycle then, because a cycle is something that repeats

but I understand what you're saying now

A better way to put it IMHO is that Z only shows up once per cycle

[fluid peak]

@lofty rose I forgot to thank you for your insight! Sorry I forgot

[round jetty]

which is also not a given

[olive salmon]

yeah, my definition of cycle might've been a bit off there sorry

[tiny oasis]

I'm not sure that's true, looking at my data... because the first "Z" doesn't lead to a cycle on the next element.

[round jetty]

I actually mentioned this assumption at the start, btw, but someone else took that to mean it was different Z's

and I got a bit misled

@trail vale

[olive salmon]

wdym doesn't lead to a cycle?

[round jetty]

I still think this is actually, correct, for what you need to do for every start; you have to find:

• the length of the cycle
• the offset of the end within the cycle (this is a big assumption; that there's exactly 1 end)
• the offset of the cycle from the start

so in 2 I mention that every cycle can only have one end

If Z => Z in a number of steps that was not a multiple of directions.len()

[tiny oasis]

I'm going to go do some graphviz later

[round jetty]

Which was your concern

then that would not be a cycle anymore, and in the process of completing a real cycle you'd have hit Z twice

it also happens to be the case, that in my bullets above, the first value is equal to the sum of the next two

the length of each cycle = offsend of the end + distance to cycle

because the RHS is just A => Z

(A to cycle start) + (cycle start to Z) = A to Z

[tiny oasis]

Oh nm, my data is confusing me. I was right the first time, my data does repeat to a cycle , just not for the reason I expected. Only one Z is visited for each cycle.

[olive salmon]

hitting Z multiple times is the annoying thing to code tbh
it means that over your CRTs, you have to consider multiple congruences because the time when you match Zs doesn't care which point you're at in the steps

whereas for the current situation, it's guaranteed you'll be at the start because of all the nice divisibility, so you can't have any intermediate Zs to hit

[round jetty]

yep

if A => Z != Z => Z then you have to use chinese remainder theorem

[misty flare]

interestingly there are starting nodes that do not cycle

[round jetty]

but if you hit Z's multiple times, then you have to use chinese remainder theorem with multiple possible remainders

so you have to do a search over "which" Z you're going to hit in every cycle, plug that into CRT, pop out the number

and get the minimum of all those

pretty nuts

[misty flare]

i've been going through my nodes and I got one here that doesn't to a cycle. stopped it at 13 million

so interesting

[round jetty]

it doesn't cycle to itself, sure

that' snot that surprising/interesting

but every node eventually goes into a cycle

[tiny oasis]

Not for me. I have 6 start nodes. All terminate.

[misty flare]

oh no not from the tast

[round jetty]

the phase space is finite so by the pidgeonhole principle you have to cycle

[misty flare]

just going through all notes and checking if they go back to that node with the instruction

[round jetty]

they may never return to the same node, sure

[misty flare]

with these instructions you just keep missing it

[round jetty]

you have to cycle, but the starting node doesn't have to be part of the cycle

A => B = > C => B

[olive salmon]

assuming that there is a solution and given the size of the input, i think it's fine to assume that the cycle will always contain the Z

[round jetty]

I guess, it's less that I'm against this style of AOC, so much as I just didn't expect it, to thi sdegree

I don't think I've ever done an AOC problem before that was this much "data exploration"

half of this problem is basically figuring out just how simplistic and engineered the data is

[tiny oasis]

Is this an anti-gpt feature?

[round jetty]

and half is actually programming the solution

no, they've already said gpt did not affect problem selection

anyhow, in a normal AoC it's like... 90% programming at least, and maye 10% verifying some basic assumptions about the data

[olive salmon]

2015 day 19 is kinda similar
tho even for that day you had people programming a general solution
for today it would be difficult to do that i think

if i were to approach it, i'd first find all the Z nodes that connect to A nodes, join up all the Z nodes into their respective cycles at that offset of A -> Z, find the cycle length and mark down every single Z's offset from the start Z in each cycle, and then do CRT on every offset across every cycle and find the minimum value

[round jetty]

I could be wrong but I don't think a genral solution is that bad

and yeah, it's what you said

[olive salmon]

it's not that bad, but it's a significant step up from "just take the lcm of the starting offsets"

[round jetty]

it's a cycle length + list of offsets for every start

and then search on CRT for every combination of offsets

yep

[olive salmon]

the main thing is the CRT with multiple congruences

[round jetty]

we had to do CRT for that bus problem a couple years ago didnm't we

so something like that could be suitable for a day 20+ problem

[olive salmon]

i don't know of any efficient algorithms for computing CRT across multiple moduli with multiple congruences
backtracking would be very helpful, but even then it'd take a lot

tho i guess it's reasonable to assume a reasonable input with few As and Zs if it were considering the general case

[misty flare]

interestingly there are 6 nodes that don't return to the start, 6 nodes that have numbers in the 5 digits and everything else is under 600.

[olive salmon]

i like https://brilliant.org/wiki/chinese-remainder-theorem/
you can skip the proof bit and just go to the "solving systems of congruences" bit, and i think that gives a pretty clear method on how to do it

[misty flare]

so they selected those inputs carefully

[tiny oasis]

Ugh. Now you're going to make me think.

[round jetty]

thank you, I appreciate it

[round jetty]

in many many more ways than that

[misty flare]

yes no doubt there

[round jetty]

that's a pretty small thing compared to some of the other things discussed here

like A=>Z == Z=>Z

[misty flare]

yeah i also found that with my test

[olive salmon]

assumptions:

• A -> Z == Z -> Z
• Z -> Z is a multiple of len(steps)
• each Z is contained within its own cycle (AZ can't reach BZ for example)
• A always reaches a Z (this one doesn't really count, since otherwise there would be no answer, so it's a valid assumption to make)
  i think that's all you need to get today's inputs

[hearty stratus]

I spent a long time trying to figure out how to account for all sorts of possible cycles only to find out here that the input was chosen to be simple 😄 So here is my solution, part1: 4.5ms, part2: 28ms
https://paste.pythondiscord.com/5OOQ

[misty flare]

is it normal to do an import in a function?

[olive salmon]

usually not

[hearty stratus]

no, I just keep solutions for part1 and 2 together so I don't get confused

[misty flare]

because I've never seen that before so I wondered

[hearty stratus]

if I were writing a normal script I would throw my imports up on top

[hearty stratus]

it's not a good practice 😄

but I'm only running this function once

[misty flare]

yes but it doesn't hurt for it to be up top so why go out of way to put it in the function?

[olive salmon]

it's probably going out of the way to put it at the top
usually if you're coding a function you're already there, and putting the import there is more convenient

[hearty stratus]

to put it on top I would have to scroll for half a second, too much work 😅

[misty flare]

is it bad practise to just import math instead of import math import lcm?

[warped briar]

Part 2 py o=open(0).readlines() f={x[:3]:(x[7:10],x[12:15])for x in o[2:]} a=[x for x in f if x[2]=="A"] r=[1]*len(a) for j,y in enumerate(a): t = __import__("itertools").cycle(o[0]) while(y:=f[y]["LR".index(next(t))])[2]!="Z":r[j]+=1 print(__import__("math").lcm(*r))

[nova ocean]

HEY , what do you think about my solution for today?
https://github.com/DownDev/advent-of-code/blob/main/2023/08-1.py

[misty flare]

404 - page not found

now it works

[olive salmon]

from math import lcm is arguably the worse of the two

not saying it's that bad, I do it as well

[warped briar]

lcm = __import__("math").lcm

[olive salmon]

but from a code readability standpoint it's less cluttering of the namespace

and you can see where things come from easier

[lusty wagon]

from numpy import*

[hearty stratus]

best version

[misty flare]

what does that do?

[warped briar]

It definitely depends. If it's something like pandas where it's mostly operations on the class instances, then import pandas as pd is desirable for less clutter. If it's something like manim where you will be spamming the module's functions and class, from manim import * is standard.

[hearty stratus]

takes every single function, class and global variable from numpy and puts it into your namespace

[steel rapids]

quick question, my code works for the test case. it's been running for like 2 minutes or so. How many steps did it take for you to reach the end ```py
import importlib.util

def importFromPath(path):
spec = importlib.util.spec_from_file_location("module.name", path)
module = importlib.util.module_from_spec(spec)
spec.loader.exec_module(module)
return module

myModule = importFromPath(r"D:\juliu\Python.py\adventOfCode\inputParser.py")

orders = [("(", ""), (")", ""), ("=", ","), (" ", "")]
for char, nchar in orders:
myModule.removingCharacters("challengeInput.txt", char, nchar)

def convertInstructions(string):
for element in string:
if element == "L":
yield 0
else:
yield 1

with open("challengeInput.txt", "r", encoding="utf-8") as file:
lines = file.readlines()

instructionSet, mapping, totalStep = lines[0].replace("\n", ""), {}, 0

for line in lines[2:]:
temp = line.replace("\n", "").split(",")
mapping[temp[0]] = temp[1:]

keyValues = list(mapping.keys())
key, endKey = keyValues[0], keyValues[-1]

while key != endKey:
for index in convertInstructions(instructionSet):
key = mapping[key][index]
totalStep += 1
if key == endKey:
break

[hearty stratus]

are you trying to simulate all of the steps? it would take years

[misty flare]

part 2 you can't bruteforce. 1 like a second

[hearty stratus]

my answer was in trillions of steps

[warped briar]

Maybe doable if you have a good graphics card and write shader code for it.

[hearty stratus]

I did try, but after coming back to my laptop after lunch I found it still working and decided to stop 😄

[lusty wagon]

this is part 1 again guys lol

start at literal "AAA" not keys[0]

[steel rapids]

how would i go about finding the steps? Im literally only following the steps provided in the first line

[tiny oasis]

Hey, what image paste utility do folks use around here?

I want to paste a graphviz image

[lusty wagon]

discord

[tiny oasis]

Too big

[misty flare]

put every node in a dict and use key = d.get(key)

then step += 1

[tiny oasis]

Oh, that's weird. It failed first try. This worked

[misty flare]

oh nice

[tiny oasis]

That's my input data.

[hearty stratus]

oh wow

[steel rapids]

im doing that?

but i have to decide to which node im going to go next based on the instruction (LR)

[misty flare]

how are your values structured?

[tropic ice]

oh ok that graph clears it up for me, why lcm works for this data

[misty flare]

l means you use the left one. r the right. convert l to 0 r to 1

[tiny oasis]

Yah, I didn't distinguish between L and R in that graph. But the point is, it doesn't matter.

[lusty wagon]

you're going from keys[0] to keys[-1] @steel rapids

in the full input those aren't in order but you still have to go from AAA to ZZZ

[olive salmon]

well you have to zoom in to see that every A path node matches with every Z path node

but yeah that makes it clearer why lcm works

[steel rapids]

i have my key : [leftKey, rightKey] based on the instruction i decide if i go with the left or the right key for my next node

[round jetty]

do we even need LCM

[hearty stratus]

I have just learned that itertools.cycle exists, nice

[round jetty]

or are the cycles / dir length mutually prime

[steel rapids]

Sorry but what do you mean?

[tiny oasis]

No, since they're all multiples of the "plan" length.

[hearty stratus]

my cycles were {20803, 17287, 23147, 13771, 19631, 17873}

[round jetty]

after division by that

[steel rapids]

is it possible to have an endless loop with nodes? So that you may never access the endnode`?

[round jetty]

it looks like they are in my input

lol

[tiny oasis]

Then there'd be no solution. The problem, as stated, assumes that there is a solution.

[lusty wagon]

you wrotepy key, endKey = keys[0], keys[-1]

this works for the example, where the dict starts at AAA and ends at ZZZ

but this may not be the case in the full input - you should write literally "AAA"

[olive salmon]

assuming there exists a solution is a valid assumption imo

[round jetty]

yeah

[steel rapids]

lol yeah this explains it

[misty flare]

you don't sort your keys. if you do it might just work

[round jetty]

I think the assumptions that are always fair game are basically:
a) a solution exists
b) when solutions involve integers, they will fit inside a 64 bit integer

[olive salmon]

!e print(2**64)

[empty otter]

@olive salmon :white_check_mark: Your 3.12 eval job has completed with return code 0.

18446744073709551616

[steel rapids]

well no need it finished like instantly

[round jetty]

there's probably very specific cases where b) doesn't hold, where it's almost being treated like a string but it's rare

[olive salmon]

yeah I'd agree with that

[round jetty]

if there were such a day though then python would suddenly have an enormous advantage 😛

[misty flare]

python has no upper limit? (practically?)

[round jetty]

I will say it's pretty annoying in some languages, like e.g. in Kotlin the pervasive default integer is 32 bits, and solutions that don't fit in 32 bits are not uncommon

so you have to use a 64 bit integer type everywhere basically, and there's no implicit conversions so there's a lot of casting. gets old fast

(but then it gets old in Rust too for differnt reasons)

[lusty wagon]

it checks for overflow and switches to an arbitrary precision type

[red vault]

Rust has been good so far about inferring other types based on, say, one annotation.

[tiny oasis]

quicknir, this is your input:

[hearty stratus]

pretty much, it can update the necessary size of the data type to make the number fit

[misty flare]

oh nice

[round jetty]

the inference is good but there's still a lot of places you have to cast, particularly if you care about performance and want to use smaller types when possible for packing

[lusty wagon]

what about concentric

[round jetty]

also in a lot of sitautions where you want to use signed integers, and rust has sadly used unsigned integers for indexing

[tiny oasis]

What?

[lusty wagon]

it would look nice if they were all concentric

[tiny oasis]

Oh, I'm not artistic 🙂 I just threw that into graphviz.

If I were more motivated, I'd animate the traversal

[hearty stratus]

someone on reddit bruteforced part2 lol

threw it into an rtx3090, gg ez

[misty flare]

well that works

[round jetty]

awesome

[warped briar]

I had to cheat a bit with rescaling to make them all fit, but here you go

[lusty wagon]

they do N steps at a time smh

[misty flare]

Nsteps?

[hearty stratus]

as you should when using a gpu 🤷‍♂️

[tropic ice]

link pls

[lusty wagon]

as in, they transform the original from a one step mapping to a N step permutation and then apply that repeatedly

which only works if it finishes at a multiple of N steps (which it does, but eg LCM algorithm isn't 'brute force')

[hearty stratus]

https://www.reddit.com/r/adventofcode/comments/18dry49/2023_day_8_part_2glsl_brute_forced_in_under_a/

[hearty stratus]

fair

[nova ocean]

Nice

[small trench]

Great! Perhaps we can use this map to escape the haunted wasteland.

[trail vale]

this is not possible if all paths cycle and the cycle lengths are relatively prime

[austere elk]

the term is 'pairwise coprime'

[trail vale]

both terms are the same

also mutually prime

or just a is prime to b

i did take number theory courses once long ago

[austere elk]

¬(a|b ∨ b|a)

wait actually that's not quite the same thing lol

[trail vale]

that's not guaranteed to work

but may work depending

o - o - o - o - o - z
o - z - o 

these cycles won't line up, but they will if both the z's are on the end (like in our input)

[austere elk]

Actually, the cycles don't have to be pairwise coprime, the constraint is slightly more relaxed than that - they just have to have the endpoint fall on the same step modulo their GCD

Like oooooz and ozoo have a GCD of 2, and the z occurs at 1 mod 2 in both cycles

[trail vale]

yep

[steel rapids]

i maybe on the wrong track but this code works for the test case. All my challenge Inputs seem to be closed loops without having a node that has the letter z in the end```py

import importlib.util

def importFromPath(path):
spec = importlib.util.spec_from_file_location("module.name", path)
module = importlib.util.module_from_spec(spec)
spec.loader.exec_module(module)
return module

myModule = importFromPath(r"D:\juliu\Python.py\adventOfCode\inputParser.py")

orders = [("(", ""), (")", ""), ("=", ","), (" ", "")]
for char, nchar in orders:
myModule.removingCharacters("challengeInput.txt", char, nchar)

def checkingForUnclosedLoop(start, end, mapping, instructions):
visited, stepCount, instructionCycle = set(), 0, 0
while start[-1] != end:
instructionCycle += 1
for instruction in instructions:
if start in visited:
return False
visited.add(start)
#print(f"{mapping[start]}{instruction} -> {mapping[start][instruction]}")
start = mapping[start][instruction]
stepCount += 1
if start[-1] == end:
break
return stepCount, instructionCycle

with open("challengeInput.txt", "r", encoding="utf-8") as file:
lines = file.readlines()

ordering, startPoints, instructionSet = {}, [], [0 if element == "L" else 1 for element in lines[0].replace("\n", "")]

for line in lines[2:]:
temp = line.replace("\n", "").split(",")
if temp[0][-1] == "A":
startPoints.append(temp[0])
ordering[temp[0]] = temp[1:]

steps, cycles = [], []
for startPoint in startPoints:
result = checkingForUnclosedLoop(start=startPoint, end="Z", mapping=ordering, instructions=instructionSet)
print(result)
if result:
result, cycle = result
cycles.append(cycle)
steps.append(result)

[tiny oasis]

Paste your data, if you like?

[steel rapids]

LR

11A,11B,XXX
11B,XXX,11Z
11Z,11B,XXX
22A,22B,XXX
22B,22C,22C
22C,22Z,22Z
22Z,22B,22B
XXX,XXX,XXX
``` here's the data i used from the test case

[narrow trout]

File "C:\Users\ducke\PycharmProjects\adventofcode\2023\day8.py", line 68, in goto_new_location
goto_new_location(current_location, direction_index, total_steps)
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

rip

[mighty rain]

kek

[mighty rain]

U can color code the left and right like #1182550042091991180 message

[modest frost]

circo?

[stuck inlet]

did you figure this out?

[warped briar]

@modest frost I didn't make them, I just used FireAlpaca (my art program of choice) to edit the existing images. Here's with that that colored one, again having to cheat with scaling to make everything fit.

[mighty rain]

Nice

I was going to make a custom layout but then got busy with other stuff 😔

[stuck inlet]

AHA

            if start in visited:
                return False

You might need to be able to visit a node twice though, once left, once right

I removed those 2 lines and your code produced the correct answer on my input.

[lofty rose]

I'm using obsidian with the excalidraw plugin

but I also have a drawing tablet so ymmv

[tiny oasis]

Paste over in the viz thread?

I’ve been playing around with animating it

[modest frost]

@velvet bough did ya bash

[velvet bough]

oui

wanna see

[modest frost]

sure

[velvet bough]

only a run.sh today 😩

[modest frost]

I mainly want to make sure you tag along 👀

[velvet bough]

😩

oh that's quite illegible

[modest frost]

I did split the scripts

[velvet bough]

https://paste.pythondiscord.com/66LA

[modest frost]

you know what exists to share code?

[velvet bough]

sh u.sh

[modest frost]

github

[velvet bough]

hmm, a splendid idea

have you tried it at work 😛

[modest frost]

😔

[velvet bough]

https://github.com/jonathan-d-zhang/aoc2023-roulette/blob/master/days/day08/run.sh

[modest frost]

well, we might actually be getting a new vcs frontend

but it's not a git-like one

https://github.com/martinvonz/jj

[velvet bough]

github changing the UI again 😒

[modest frost]

it's pretty neat ideas-wise, I'm using it for my aoc repo

[velvet bough]

The project is called "Jujutsu" because it matches "jj".
😩

[modest frost]

so I was even lazier with input parsing

[velvet bough]

oh?

wait i just realized i don't need to map the left and right into numbers lol

[modest frost]

or wait, you're doing something funky

with eval

eww

[velvet bough]

😎

[modest frost]

I did this

declare -A lookup
while read line; do
  s=( $line )
  lookup[${s[0]}L]=${s[1]}
  lookup[${s[0]}R]=${s[2]}
done < <(tr -d '=(,)' | tr -s ' ')

tr the crap away

dump into an array

and notably you need to do the < version, and not a pipe

because a pipe runs in a subshell 🤡

it took me a bit until I realized why I was getting empty lookups

[velvet bough]

not having $somethingthatdoesn'texist fail is understandable, but so so annoying

[modest frost]

so, my solution kinda accidentally depended on that fact that doing gcd from A->Z works

granted, I kinda don't like this problem in general because of the "lol, super specific special case"

why are you like this? 😔

printf "Part 2: %d\n" $p2

[velvet bough]

uh

lol i originally wanted p2 to be a function

[modest frost]

just echo "Part2: $p2" like normal people

[velvet bough]

yeah i kinda forgot you could do that

[modest frost]

so my solution is a bit shorter

40 lines

[velvet bough]

oh?

[modest frost]

https://github.com/algmyr/aoc-2023/blob/main/day08/main.sh

but as said, it ends up depending on the thing with the A-Z distances

[velvet bough]

oh that's nice. i coudn't figure out a way to avoid the duplication between p1 and p2

[modest frost]

right

that gcd is kinda neat/terrible

[velvet bough]

it's just the euclidean thing

[modest frost]

it is, but it's kinda symbol soup

https://github.com/algmyr/aoc-2023/blob/main/day08/main.sh#L29-L31

[empty otter]

day08/main.sh lines 29 to 31

function gcd() {
  ! (( $1 % $2 )) && echo $2 || gcd $2 $(( $1 % $2 ))
}```

[velvet bough]

oh your gcd. yeah

[modest frost]

overall not too bad looking solution given that it's bash

I'm kinda curious what metric Kat is using to rank languages though 🥴

[velvet bough]

good question...

[modest frost]

given that this was in week 2

[velvet bough]

also it looks like github syntax highlighting is mad at my code

[modest frost]

a bunch of the languages in week 1 is way safer than bash

especially performance-wise

[velvet bough]

well like, everything-wise

[modest frost]

also thank god we didn't need to do float computations

[velvet bough]

can prolog do floats?

[modest frost]

good question

[velvet bough]

meh, python is cheating

[modest frost]

much readable

[stuck inlet]

the first line is:

__import__('sys').setrecursionlimit(1_000_000)

it's cheating in a cheating language. 🙂

[modest frost]

let me a good citizen and make that screen shot a tad better

[stuck inlet]

the whole joke was the long screen shot. I long since posted the code as code.

[modest frost]

ah, you're mocking @velvet bough

please proceed

[velvet bough]

;-;

[stuck inlet]

with less pixels:

dirs, paths = open(aocinput).read().split('\n\n')
paths = {v[:3]:{'L':v[7:10],'R':v[12:15]} for v in paths.splitlines()}

def steps(s,c=0):
    return c if s[-1] == 'Z' else steps(paths[s][dirs[c%len(dirs)]], c+1 )

print('part1', steps('AAA'))
print('part2', lcm(*[steps(k) for k in paths if k.endswith('A')]))

[velvet bough]

lcm doesn't take an iterable?

[stuck inlet]

no 😦

[velvet bough]

maybe that's for the better. max/min are horrifying

though i would have preferred only iterable vs only *args

[modest frost]

basically do either iterator or args

not both

[stuck inlet]

I really do not enjoy the default= syntax of min/max. feels awkward

[modest frost]

I recall gcd being a two argument function for a while

which was then generalized

indeed

and lcm mirrors gcd when it was added at the same time

[velvet bough]

ah that makes sense then

[modest frost]

there are methods to the madness

not always good ones, but they exist

[velvet bough]

these are functions though

[modest frost]

I knew that risk

I foolishly thought you better than that

(I would have done it, but I'm a terrible person)

[velvet bough]

it's because the roulette fr

[modest frost]

in unrelated news I actually recieved my new phone

nice to actually see stuff again

[narrow trout]

is it true that part 2 has a very high number os is my code broken

[stuck inlet]

part1 19XXX
part2 13663968XXXXXX

[narrow trout]

ah so my 600k is not suprising

its still running

[stuck inlet]

600_000 ? when the answer is around 13_663_968_000_000
you might be here a while.

[stuck inlet]

You might even want to consider an alternative approach. The correct answer is foud in under a second. Bruteforce is not the way to go here.

[narrow trout]

is there some sort of trick?

[stuck inlet]

yes.

[potent ginkgo]

Ok finally finished code and tests

code

import dataclasses
import enum
import itertools
import math

import parse

START_ELEMENT = 'AAA'
END_ELEMENT = 'ZZZ'
START_NODES_LETTER = 'A'
END_NODES_LETTER = 'Z'


class Direction(enum.Enum):
    LEFT = 'L'
    RIGHT = 'R'


@dataclasses.dataclass(frozen=True)
class Node:
    left: str
    right: str


class Navigation:

    def __init__(self, nav_input):
        instrs, network = nav_input.split('\n\n')
        self.instrs = [Direction(dir_) for dir_ in instrs]
        self.network = {}
        for node in network.splitlines():
            parsed_node = parse.parse('{input_ele} = ({left_ele}, {right_ele})', node)
            self.network[parsed_node['input_ele']] = Node(parsed_node['left_ele'], parsed_node['right_ele'])

    @classmethod
    def read_file(cls):
        with open("input.txt") as f:
            return cls(f.read().strip())


def navigate(nav: Navigation, ele=START_ELEMENT, end=True):
    instr_map = {Direction.LEFT: 'left', Direction.RIGHT: 'right'}
    for step_no, instr in enumerate(itertools.cycle(nav.instrs), start=1):
        node = nav.network[ele]
        ele = getattr(node, instr_map[instr])
        yield ele
        if end and ele == END_ELEMENT:
            return step_no


def navigate_simultaneously(nav):
    """
    Navigate simultaneously only where paths follow a loop with no offset
    and only one end element is visited in the whole loop
    """
    start_eles = [ele for ele in nav.network if ele.endswith(START_NODES_LETTER)]
    end_ele_steps = []
    for start_ele in start_eles:
        nav_iter = navigate(nav, ele=start_ele, end=False)
        end_nodes = []
        for step in itertools.count(1):
            next_ele = next(nav_iter)
            if next_ele.endswith(END_NODES_LETTER):
                end_nodes.append((next_ele, step))
            if len(end_nodes) == 2:
                break
        end_node_1, end_node_2 = end_nodes
        if end_node_1[0] != end_node_2[0]:
            raise ValueError('More than one end element visited')
        if divmod(end_node_2[1], end_node_1[1]) != (2, 0):
            raise ValueError('Path to end element does not follow a loop with zero offset')
        end_ele_steps.append(end_node_1[1])
    return math.lcm(*end_ele_steps)


def main() -> None:
    nav = Navigation.read_file()
    nav_iter = navigate(nav)
    while True:
        try:
            next(nav_iter)
        except StopIteration as exc:
            steps = exc.value
            break
    print(
        f"Total number of steps required to reach {END_ELEMENT}:",
        steps,
    )
    print(
        f'Total number of steps required to end on a {END_NODES_LETTER} element '
        f'starting from a {START_NODES_LETTER} element simultaneously:',
        navigate_simultaneously(nav)
    )


if __name__ == "__main__":
    import timeit

    print(timeit.timeit(main, number=1))

tests

import pytest

from year_2023.day_08 import process


def test_navigation_no_cycle():
    nav_input = """\
RL

AAA = (BBB, CCC)
BBB = (DDD, EEE)
CCC = (ZZZ, GGG)
DDD = (DDD, DDD)
EEE = (EEE, EEE)
GGG = (GGG, GGG)
ZZZ = (ZZZ, ZZZ)"""
    nav = process.Navigation(nav_input)

    nav_iter = process.navigate(nav)
    assert next(nav_iter) == 'CCC'
    assert next(nav_iter) == 'ZZZ'

    try:
        next(nav_iter)
    except StopIteration as exc:
        steps = exc.value
    else:
        pytest.fail()

    assert steps == 2


def test_navigation_cycle():
    nav_input = """\
LLR

AAA = (BBB, BBB)
BBB = (AAA, ZZZ)
ZZZ = (ZZZ, ZZZ)"""
    nav = process.Navigation(nav_input)

    nav_iter = process.navigate(nav)
    exp_elements = ['BBB', 'AAA', 'BBB', 'AAA', 'BBB', 'ZZZ']
    for ele in exp_elements:
        assert next(nav_iter) == ele

    try:
        next(nav_iter)
    except StopIteration as exc:
        steps = exc.value
    else:
        pytest.fail()

    assert steps == 6


def test_navigate_simultaneously():
    nav_input = """\
LR

11A = (11B, XXX)
11B = (XXX, 11Z)
11Z = (11B, XXX)
22A = (22B, XXX)
22B = (22C, 22C)
22C = (22Z, 22Z)
22Z = (22B, 22B)
XXX = (XXX, XXX)"""
    nav = process.Navigation(nav_input)

    assert process.navigate_simultaneously(nav) == 6


def test_navigate_simultaneously_fails_if_more_than_one_end_element_visited():
    nav_input = """\
LR

11A = (11B, 11B)
11B = (XXX, 11Z)
11Z = (22B, XXX)
22B = (XXX, 22Z)
22Z = (11A, 11A)
XXX = (XXX, XXX)"""
    nav = process.Navigation(nav_input)

    with pytest.raises(ValueError, match='More than one end element visited'):
        process.navigate_simultaneously(nav)


def test_navigate_simultaneously_fails_if_path_to_one_end_element_does_not_follow_loop_with_no_offset():
    nav_input = """\
LR

11A = (11B, XXX)
11B = (XXX, 11Z)
11Z = (11C, XXX)
11C = (XXX, 11D)
11D = (11E, XXX)
11E = (XXX, 11A)
22A = (22B, XXX)
22B = (22C, 22C)
22C = (22Z, 22Z)
22Z = (22B, 22B)
XXX = (XXX, XXX)"""
    nav = process.Navigation(nav_input)

    with pytest.raises(ValueError, match='Path to end element does not follow a loop with zero offset'):
        process.navigate_simultaneously(nav)

[stuck inlet]

there's only 6 paths, consider finding out how long each of them takes to finish. and then think about how you could calulate when they would all finish at the same time.

[potent ginkgo]

I have error handling in my code

[stuck inlet]

Each of your tests is longer than my entire codebase.
I love it. 🙂

[potent ginkgo]

If it's given an input which has a path which isn't a strict loop, or has an offset from the loop, or visits more than one element ending with Z in a single path, it kills the process

[potent ginkgo]

XD

I love to write these as if they are production code that requires full test coverage

[velvet bough]

why aren't the links in your dataclass to other nodes?

[hearty stratus]

I do like reading your solutions

[stuck inlet]

Yeah it's a fnatasic approach and great interview fodder if you put it on a github.
"here, this is how I write code".

[potent ginkgo]

eh I have the elements as strings and then the nodes are just a collection of two elements

the links are just a dict

[potent ginkgo]

I'm also getting better with it too. I have a better sense of when to use classes vs when not to

[modest frost]

@velvet bough btw you should have seen my initial part 1, which re-read the file on every step

[narrow trout]

so what i need to do is find how many turns it takes for a path to reach a Z location and then i need to find if the other paths are on a Z location aswell on that turn?

[modest frost]

grep for correct start, parse out left/right

[velvet bough]

🥴

at least i learned a lot from today. i'll probably use bash more now

less python scripts

[marble nova]

Can you not just work out how long it takes for each start point to loop and then use that bus stop tehcnicque from before to work out when they intersect?

wait no, that wouldnt capture the end

[modest frost]

it's not that terrible, yeah

[stuck inlet]

something like that. like if you had 4 paths and they finished in 3,5,7, 9 turns. you could see that on turn 105 they're all at the finish together.

[potent ginkgo]

I thought that when I first learned bash and that turned out NOT to be the case lol

[modest frost]

learning bash arrays in particular is quite helpful

[velvet bough]

it just turns so quickly into trying to figure out how to do something in bash and not actually doing the thing

that's kind of a skill issue though

[narrow trout]

is 105 a random example or is there an equation i dont see

[modest frost]

working with arguments you want to pass? array

[stuck inlet]

most of my bash scripts turned into a find exec

[velvet bough]

xargs is based though

[potent ginkgo]

When it comes to file parsing at least, I use bash for simple stuff like head command (if that even counts as parsing) - and then anything more complex I immediately go to Python

[modest frost]

trade-offs

[stuck inlet]

it's the correct answer for 3,5,7,9
see if you can figure out a way to get the answer and if you can't I'll gladly spoil it for you.

[velvet bough]

oh wait i can grep and xargs to solve then reduce that with lcm

or rg 🦀

[modest frost]

bash - low barrier for working with cli, great at some stuff
python - more of a barrier, but much more flexible
c++/rust/whatever - big barrier - speeeeeed

[stuck inlet]

So which do we like more:

def steps(s):
    c = 0
    while s[-1] != 'Z':
        d = dirs[c%len(dirs)]
        s = paths[s][d]
        c += 1
    return c

vs for/count:

def steps(s):
    for c in count():
        if s[-1] == 'Z':
            return c
        s = paths[s][dirs[c%len(dirs)]]

vs recursive counting:

def steps(s,c=0):
    return c if s[-1] == 'Z' else steps(paths[s][dirs[c%len(dirs)]], c+1 )

cough ignoring: steps = lambda s,c=0: c if s[-1] == 'Z' else steps(paths[s][dirs[c%len(dirs)]], c+1 )

[narrow trout]

i have no clue

[modest frost]

counter-offer: enumerate(cycle(dirs))

[stuck inlet]

well one hint is 3*5*7 = 105

[stuck inlet]

that's not bad too.

[potent ginkgo]

I often wonder between the first two (never 3 though)

itertools.cycle() is convenient yet I don't like the idea of using for for an indefinite loop

[stuck inlet]

it occurs to me my example is bad, the 9 should have been a 15. 🙂

[potent ginkgo]

I went for convenience this time :)

[stuck inlet]

it does have a wrongness feel to it.

but i didn't like having a while loop with a counter, that's just a for loop with more steps

[modest frost]

I don't really see the wrongness

def steps(s):
    for c, d in enumerate(cycle(dirs)):
        if s[-1] == 'Z':
            return c
        s = paths[s][d]

[stuck inlet]

Yeah I like that. Very clean.

[modest frost]

when the abstractions hit just right

[narrow trout]

only thing i can think of is that 3 + 5+ 7 = 15

[potent ginkgo]

I've always felt that for should be for definite structures

but of course it doesn't necessarily have to be that way

[stuck inlet]

so: 4 paths, they finish in 3,5,7,15 amounts.

after 35 loops the '3' path reaches 105
after 21 loops the '5' path reaches 105
after 15 loops the '7' path reaches 105
after 7 loops the '15' path reaches 105

there's a simple mathematical way to find when they all reach the same path.

[narrow trout]

the path reaches loops * amount

[stuck inlet]

You could just do 3 * 5 * 7 * 15. But that would be too big. Even though they do all meet at that number as well.

so you want the least multiple of those numbers where they all meet at the same time.
how would you find the smallest multiple all these numbers have in common ?

[narrow trout]

its been a while since i had this at school lmao

[potent ginkgo]

AOC does use concepts I haven't seen for a long time

cough cough ||quadratic formula||

[modest frost]

so what would you do when you deal with infinite iterables?

[potent ginkgo]

I tend to while them tbh

[modest frost]

while with try except StopIteration?

[narrow trout]

would you make a function that keeps multiplying and then checks if all the numbers have that multiple?

[modest frost]

ok, if it's for sure infinite then I guess that's fine

the annoying case is possibly infinite

where you would need to except StopIteration

which is just...ugly

[stuck inlet]

That's one approach. here's another: https://en.wikipedia.org/wiki/Least_common_multiple

[modest frost]

tl;dr:

lcm(a, b) = a*b/gcd(a, b)
lcm(a, b, c, d) = lcm(a, lcm(b, lcm(c, d)))

I was about to do lcm(a, b, ..., y, z)

but couldn't figure out where to put the ...

[narrow trout]

my approach may be slower but i dont even know what a gcd is so that may be a hard task

[modest frost]

gcd is the answer to "all numbers have that multiple"

e.g. gcd of 12 and 30 is 6

i.e. 2*2*3 and 2*3*5 has 2*3 in common

[warped briar]

https://en.wikipedia.org/wiki/Greatest_common_divisor

[stuck inlet]

and once you understand the concept, you'll be pleased to know that from math import lcm exists.

!e print(import('math').lcm(3,5,7,15))

[empty otter]

@stuck inlet :white_check_mark: Your 3.12 eval job has completed with return code 0.

105

[narrow trout]

ah thats nice to know

but how will this work when my paths are all letters

[stuck inlet]

letters? you did part 1 right?

your path lengths should be a number

[narrow trout]

ah ye

ok so i basicly split each path, find the lengths from a -> z and then find the lcm of those paths?

[stuck inlet]

that's about the gist of it.

[stuck inlet]

someone brute forced part2 in rust. took them 6 hours.

[velvet bough]

🥴

did they thread it

[mighty rain]

#1182550042091991180 message

[stuck inlet]

I like the top comment: "Wow.. I understand this even less than LCM"

OP's explanation:

So, I wrote a GPU solution that goes through all of the possible solutions up until the correct one is found. To get parallelism for this seemingly purely serial task, I prepare tables that contain powers of the movement table: since the instructions loop on a cycle of the length of the direction instructions, one loop of the instructions is just a permutation. This permutation can be applied to itself to apply a square (and cube and so on) of the original single cycle permutation, so you can quickly get from 0 to iteration N and then brute force each step from there per thread.

that's great!

Now, we run a bunch of threads (around 200k) on the GPU. Each thread uses the precomputed lists to fast forward to a different position of the simulation really quickly, and then goes through a large number (some tens of thousands) of simulation steps and if it finds a solution, it marks it in global memory. After this, we check if any thread found a solution; if not, we nudge all indices forward to jump further in the simulation for each thread (this is what the "scanning from" prints in the output mean) to check again.
ha. still very fast. seems like a lot of work.

[red vault]

I was about to let my brute force method run, but then someone mentioned lcm and 💡, now it's about a millisecond

[steel rapids]

Nah took a break my code works for the test case

[steel rapids]

yeah, not the cleanest solution but doable i guess ```py
import importlib.util

def importFromPath(path):
spec = importlib.util.spec_from_file_location("module.name", path)
module = importlib.util.module_from_spec(spec)
spec.loader.exec_module(module)
return module

myModule = importFromPath(r"D:\juliu\Python.py\adventOfCode\inputParser.py")

orders = [("(", ""), (")", ""), ("=", ","), (" ", "")]
for char, nchar in orders:
myModule.removingCharacters("testCaseData.txt", char, nchar)

def findingStepCount(start, end, mapping, instructions):
stepCount = 0
while start[-1] != end:
for instruction in instructions:
#print(f"{mapping[start]}{instruction} -> {mapping[start][instruction]}")
start = mapping[start][instruction]
stepCount += 1
if start[-1] == end:
break
return stepCount

def greatestCommonDivisor(a, b):
while b != 0:
a, b = b, a % b
return a

def findingMinimumSteps(steps):
def leastCommonMultiple(a, b):
return a * b // greatestCommonDivisor(a, b)
result = steps[0]
for num in steps[1:]:
result = leastCommonMultiple(result, num)
return result

with open("challengeInput.txt", "r", encoding="utf-8") as file:
lines = file.readlines()

ordering, startPoints, instructionSet = {}, [], [0 if element == "L" else 1 for element in lines[0].replace("\n", "")]

for line in lines[2:]:
temp = line.replace("\n", "").split(",")
if temp[0][-1] == "A":
startPoints.append(temp[0])
ordering[temp[0]] = temp[1:]

steps = []
for startPoint in startPoints:
steps.append(findingStepCount(start=startPoint, end="Z", mapping=ordering, instructions=instructionSet))

print(findingMinimumSteps(steps))

[potent ginkgo]

Mind if I give a few comments?

[austere lily]

im not sure if I understand day-8 part2, can sm1 let me know if my brute force is towards the right direction

    instructions, network = aoc_input
    nodes = [node for node in network if node.endswith("A")]

    for i, instruction in enumerate(cycle(instructions)):
        if all(node.endswith("Z") for node in nodes):
            return i
        nodes = [network[node][instruction == "R"] for node in nodes]

basically, im gonna traverse all starting nodes until they all end with Z

[hearty stratus]

you cannot bruteforce this

[austere lily]

I know, but i wanna make sure that i understand the question before thinking of a different solution

the example for part2 wasnt clear enough for me

[potent ginkgo]

you can but you need a GPU lol

[hearty stratus]

and a clever way of handling inputs that I haven't gotten my head around 😄

[potent ginkgo]

honestly it's easier just to do it "correctly"

[hearty stratus]

at least my repo is now purged after rebuilding it twice and forgetting to include .gitignore :/

[hearty stratus]

The way I was thinking about part2 was that I needed to keep applying part1 cycling solution to each starting position until those positions meet. That kinda seems like what you're doing but I don't understand nodes = [network[node][instruction == "R"] for node in nodes]

(I'm just talking about the assignment not solution)

[austere lily]

thats just progressing all nodes to the next node, depending on the instruction (left or right)

hoping they all end with Z at some point

[hearty stratus]

oh cycle comes from itertools?

[austere lily]

yea

[hearty stratus]

ah okay, you have set up your nodes differently to what I did but I think you've got the right idea: take instruction, apply that instruction to each current node, check if all of the nodes are at the end, repeat for next instruction

[austere lily]

yea my nodes are pretty much like

{"AAA": ["BBB" ,"CCC"], ...}

[stuck inlet]

cool! well done!
looks like you went ahead and implemented lcm yourself. But you should know that there is an lcm function in the standard library. . After I removed yout 2 lines about if visited return false all I added to your code to make it work was:

from math import lcm
print(lcm(*steps))

[stuck inlet]

This'll work, but it might take a month to finish running. 🙂 Think of a better way to see how long each path takes to finish and then calculate when they would all finish at the same time if they kept looping.

[marble nova]

Huh, this was easier than expected

[pastel falcon]

@potent ginkgo i thought the cycles had an offset (being the first time an end node is reached) and went crazy trying to figure out an algo for computing LCM with offsets (my spaghetti code didn't help :P) ... so i gave up and looked at a solution

you have to be kidding me. i was one stupid assumption away. if i had persisted, i might have found that the offset of every cycle is equal to the cycle period itself (i.e. the time to reach an end node from a start node is equal to the time for that end node to reach itself). so there was in reality no offsets and the solution was to LCM all distances from start to end 😩

[potent ginkgo]

Yup 😂 This is why a bunch of people didn’t like this day lol

[pastel falcon]

i can't believe this. my assumptions were what most people came up with lmaooo

and i didn't trust it to the end

i doubted myself lmao

[potent ginkgo]

As for me I checked everything so I was good to go

I put error handling into my code to check if the assumption ended up not holding

[pastel falcon]

nice nice

time to clean up my spaghetti

and call day 8 completed with partial assistance :P

@potent ginkgo do you know if there's a "real" solution? i think i heard recursion thrown around

[potent ginkgo]

I think if there was an offset you could use CRT? Not entirely sure though

[olive salmon]

you could use CRT if the offset is also divisible by the length of the steps

[pastel falcon]

yeah, that's what i thought too, but i'm terrible at number theory and don't know what CRT actually means nor when to use it 😂

[olive salmon]

or well the smallest length of the steps that isn't itself just a cycle

i have a pseudocode outline of a general solution in my head, but it's not very efficient because of just how much variation a general case could have

someone did brute force this day iirc

[pastel falcon]

but by a "real" solution i meant one that doesn't make use of any janky assumptions, namely:

1. for every start node, traversal falls into a cycle, in which one unique corresponding end node is found once every period
2. the distance from the start node to the end node is equal to the distance from the end node to itself

[pastel falcon]

13_133_452_426_987 ... upwards of trillions of iterations ... madman?

[olive salmon]

if we assume that the cycle lengths are divisible by the length of the steps, then that's honestly all we need to make it tractable imo

[pastel falcon]

isn't that like 2 days straight of computation lol

[olive salmon]

GPU and parallelism go brrrr

[pastel falcon]

what do you mean the length of the steps?

[olive salmon]

length of the first line

ie how many LRs until the input cycles

[pastel falcon]

ahhhhh

[olive salmon]

if it's not divisible, then the cycle is far more complicated to figure out

[pastel falcon]

it's all complicated 🥴

[olive salmon]

because you have to consider multiple paths being taken since you'd end cycle at different positions in that instruction set

if it's divisible, then afaics all you need to do is run CRT over multiple congruences for every cycle containing at least one Z (one congruence per Z in cycle, moduli running over cycle lengths) and then find the least one that actually works

if the starting offsets aren't divisible, that might actually be fine now that I think about it

you'd just have to shift the input over, but that shouldn't affect much in the cycle if the cycle length is divisible

and by cycle length I mean number of steps until you return back to the node you started from, regardless of position in input

[austere lily]

I did it!

def traverse(
    instructions: str,
    network: dict[str, list[str]],
    *,
    start: str | None = None,
) -> int:
    node = (
        next(node for node in network if node.endswith(
            "A")) if start is None else start
    )
    for i, instruction in enumerate(cycle(instructions)):
        if node.endswith("Z"):
            return i
        node = network[node][instruction == "R"]
    return 0xFor paying_respect


def part1(aoc_input: tuple[str, dict[str, list[str]]]) -> int:
    return traverse(*aoc_input, start="AAA")


def part2(aoc_input: tuple[str, dict[str, list[str]]]) -> int:
    _, network = aoc_input
    nodes = [node for node in network if node.endswith("A")]
    return lcm(*(traverse(*aoc_input, start=node) for node in nodes))

[hearty stratus]

return 0xFor paying_respect O.o

[austere lily]

:D

[hearty stratus]

oh it's 0xF or paying_respect 😄 the missing space got me confused

I still don't know what that does

[austere lily]

saw it on esopy the other day

0xF evals to true so paying_respect is never executed

[hearty stratus]

so you can put in undefined variable? or am I missing something else

[austere lily]

yea

[hearty stratus]

wow

[pastel falcon]

.bm crazy number theory to read later 😩

[pastel falcon]

does anyone know of a "correct" algorithm for today? or is the hacky LCM solution the only way to go?

[tropic ice]

well

LCM isnt hacky

[pastel falcon]

# A hacky solution based on two major assumptions
# that happen to hold true for all puzzle inputs:
#
#    1. for every start node, traversal falls into
#       a cycle, in which there is one unique
#       corresponding end node every period;
#
#    2. the number of steps from a start node to its
#       corresponding end node is equal to that from
#       the end node to itself (offset = period).
#
# Then it is simply a matter of synchronizing large
# loops, i.e. using LCM.
```this is the comment i wrote at the top of my sol, i think it's pretty hacky \:P

what if the cycles encountered two or more end nodes

what if the offset was not equal to the period

what if end nodes were encountered before a cycle starts

what if some fall into dead-end cycles (i.e. no end nodes traversed in them)

what if some don't fall into cycles at all

[pastel falcon]

for this one, apparently some crazy number theory does the job (i think it's the chinese remainder theorem, no idea what that is lol)

but there's still all the other general cases i listed

that are not in any way forbidden by the problem statement

[stuck inlet]

AOC guarantees fair inputs.

Like. It is solvable in reasonable time with the inputs given.

So if the puzzle is. "Find when they meet" they will meet.

And no inputs like 3 42 pizza 17 🍕 73

[wary cypress]

Why can't I give math.lcm a list? I couldn't figure out how to get all the values from the list separated as integers so I just copy-pasted from a previous run into my code how am I supposed to do this if it doesn't take a list?

[hearty stratus]

lcm(*list)

[wary cypress]

ohhh unpacked list, thank you!

I never use unpackers in my day to day, good to know 👍

[pastel falcon]

true, but these inputs are under restrictions not described in the puzzle statement

[olive salmon]

having the starting offset be different to the cycle length would still be solvable in reasonable time

[olive salmon]

a cycle is basically guaranteed if there is an answer

[stuck inlet]

Yeah, I think that wouldhave been ok. But that's differnt than some of the paths having no conclusion

[olive salmon]

you have some edge case where they all meet up before cycling

but given the other assumptions they would have to fall into cycles

[fierce wagon]

They don't have to be guaranteed to cycle back to the beginning

[fierce wagon]

I'm upset about this too

[mighty moss]

Can someone here explain why the lcm works for part 2? I'm just not really sure how the lcm of the number of steps it takes each XXA node to traverse to XXZ somehow gives you the number of steps it would take if they happening simultaneously

I can see how this would work if XXZ was guaranteed to lead back to XXA when given the next instruction, but that is not mentioned anywhere.

[calm belfry]

it's been a criticism of this day in particular that that is an assumption you have to make/find and isn't mentioned in the text anywhere

[mighty moss]

Ahh, gotcha. I guess I could have tested for it, it just didn't even cross my mind when working on the solution. I guess I should have taken notice of how the pattern in the example prompt could transfer over. Thanks for the response!

[lofty rose]

that's sort of how it works: #1182550042091991180 message
Essentially, XXA and XXZ have to be on the same phase (i.e. they meet at one point after some number of steps)

[cold jewel]

They're all unique strings on the left, right?

yep, can confirm

[cold jewel]

is part 1 suppose to take long?

oh, I see the problem

ok, it still takes too long

[hearty stratus]

you cannot just walk the actual path one by one in a reasonable time

oh you're on part1

part1 shouldn't take very long

[cold jewel]

i looked up benchmark, and i think i'm doing something seriously wrong. i'll have to check tomorrow

[hearty stratus]

my part1 takes 3.6ms

[cold jewel]

Ok, I got part 1.

[cold jewel]

I see why my other code in other language didn't work: ```
Starting at AAA

I can't read

[cold jewel]

is the answer to part 2 greater than 1*e18?

[olive salmon]

it's very large, but not that large

at least for me

I had ~1e14

possible that you just had bigger values tho

so I wouldn't discount your answer based on magnitude

[cold jewel]

it doesn't look like it can fit in double 😦

p2_ans = 922657
p2_ans = 67353961
p2_ans = 3973883699
p2_ans = -91983485980753
p2_ans = 1.9135324588576046e+18

see that negative? it doesn't fit in double i think

let me test something

with the values I got with the language I'm using (G'MIC), and using math.lcm in Python, I got the right answer.

i tested with a smaller ranges of value, seems correct for 3973883699, but after lcm with using one more value breaks the double limitation

[cold jewel]

I think I know how to fit in a double. I looked for an alternative to (a*b)/gcd(a,b)

@pastel falcon as you asked for my solution: https://pastebin.com/rmYBZ3af . It's not in Python though. It works with the alternative way of finding LCM.

[icy snow]

doubles can precisely store all the integers from -2**53 to 2**53 (~9e15) but past that it just skips a few
they can go up to a bit above 1e308

[icy snow]

you could always try a / gcd(a, b) * b :D

[cold jewel]

that won't work. tested it. this is the only one that'll work for double case: ```
#include <bits/stdc++.h>
using namespace std;

// Function to return LCM of two numbers
int LCM(int a, int b)
{
int greater = max(a, b);
int smallest = min(a, b);
for (int i = greater; ; i += greater) {
if (i % smallest == 0)
return i;
}
}

// Driver program to test above function
int main()
{
int a = 10, b = 5;
cout << "LCM of " << a << " and "
<< b << " is " << LCM(a, b);
return 0;
}

[icy snow]

that's weird
a / gcd(a, b) is an integer so i'd assume we wouldn't lose anything to floating point shenanigans no?

[cold jewel]

yeah, that is a integer. but the language I use (G'MIC) only supports doubles in math evaluator.

there's functions with in it own types built-in behind the scenes though. there's no LCM() built-in

[hearty stratus]

I had 1.86E+13

[fast pike]

@potent ginkgo this is where I'm at: https://github.com/shenanigansd/scratchpad/commit/70477f4f8e309634d445f265a201bbb7f00150e1
Looks like bruteforcing p2 isn't going to work

[hearty stratus]

correct

[fast pike]

how fix??

[hearty stratus]

eeeeh well, how big of a hint would you like?

[fast pike]

I'll take all the hints I can get
I don't have any idea where to start here
I'm even reading the LCM stuff but I'm not understanding where the letters are getting converted to numbers.

[potent ginkgo]

Let’s say we just have AAA->AAZ and BBA->BBZ

[hearty stratus]

oh sorry I didn't see the mention 😦 I see AoV is responding

[potent ginkgo]

It’s fine if you want to continue! I need to go eat something anyway

[hearty stratus]

so the idea is that we have several starting positions. The simple case is that from all of those positions it takes the same number of steps to reach the ending position, which would mean your brute-force solution works here as you just take like 20k steps or whatever your solution to part 1 was and you're done. This is not the case so it takes different number of steps from each starting position to get to the end. Now what would be the next easiest solution? Probably a case where the cycle has no displacement from the start (cycle starts on the first step after starting position). So we can find the length of the cycle for each starting position and assume that they were chosen such that their phases will eventually cause them to meet (we assume there is a point where all of them reach the end of the cycle at the same time). What is the number of steps we need to take to reach that position? lcm(*cycle lengths)

[cold jewel]

You can treat each letters from the left as the value of their appearance. That's how I solved the problem breaking it down to only numbers.

So, in the input, NNN = 0. But you don't want to start from NNN because then you'll go into a forever loop.