« first day (2248 days earlier)      last day (2925 days later) » 

16:00
    (2, 2),
    (0, 2),
    (3, 1),
    (0, 0)
would anyone mind helping diagnosing a bug that doesn't have an error?
with this starting position, which is essentially 4, 2, 4; I now get 31
though other starting position gives 33...
shit, BS.
my code seems to work up until around here, and then it never gives any result, it just keeps going and going without doing anything. when I use ctrl-c to stop the calculation, it quits in the middle of the relevant function, often in the line where matrices are multiplied.
that seriously cannot be right
Wish I had my laptop :( actually seems like a fun problem even if the text is super verbose
16:03
@MarcusS ain't fun
i just now added in a debugging line that prints "done" when a calculation has been completed, and it's in a loop, doing the same calculation over and over when it shouldn't be
oh, wait, i think i've got an idea
What issues you running into?
Grr, it has to be about formulating O(1) formula
16:04
I feel like there's no way the actual difficulty would have jumped up this fast, we're missing something that makes it simpler.
@davidism it did
Intended solution is likely bfs
look at the finishing times
@MarcusS I've iterated the whole solspace using DFS with memoization...
and I get 2 steps too many
I still am thinking there's something wrong with the puzzle :(:(
How the beans did that guy solve it in 8 minutes?!
If he wanted to force O(1) he would have used a lot more generators / chips / floors
16:06
ergh, i don't know why it's still not working
darn it infinite loops!
@MarcusS so 4**11 space is easily searchable on personal computer?
maybe I simply have some inherent perf issues...
4^11 is manageable, even less than that with pruning
@AnttiHaapala Can you make a simple input in line with your first DFS branch and walk through its counting procedure?
Might help inform the 2-error
16:26
it just adds +1 upon returning from recursion, (0,0),(0,0),(0,0),(n,n); floor 4 returns 0
aha now they say that 9 is possible for the example input
(not that much spoilers)
no, that is not possible :D
state 7 is illegal
Just to confirm, a floor is valid if it has no Gs, no Ms, or all Ms have Gs? I'm not missing a rule?
naturally a floor is valid if it has no gs no ms, as that 's the end condition
the mid-term rule is that iff there are G's on a floor, there mustn't be any M without corresponding G.
Meant only Gs or only Ms, but basically same thing. :-)
the rules are: you can move GG, MG, GM, M or G; you must always have at least one in the elevator to move around.
after one movement the floor mustn't have an unpaired M if it has G's.
16:40
... if there is yG where y != x :D
@MarcusS some guy tried to prove that the initial example can be solved in 9 steps... and failed
Dang I don't like edit mode on mobile here
@AnttiHaapala failed how? Allowed a chip to be exposed?
yes
most of the solutions allow a chip to be exposed
I see the 9 solution on reddit
Hm I don't actually see the error here: pastebin.com/SEqpVJUJ
me neither :D
so 9 is correct :P
so why in hell does my script count off by 2?!
I don't think the problem description claims 11 is miminal though
16:47
yeah, it doesn't
and that is shitty too
that it doesn't have the minimum input
unlike euler
state space search is not guaranteed to yield optimal result?
@ŁukaszRogalski it is
The example is only a solution, not the optimal solution.
but why do I get off by 2?!
but properly implemented search should yield 9, and my code yields 11
so, there's a bug somewhere?
I guess
16:50
:D
He probably should have either used the 9 solution and say it's minimal, or used the 11 and said it's not necessarily minimal (in the event that the 9 solution gives away a semi spoiler or optimization / pattern)
or a question is buggy and he wasnt aware of it
I'm hoping someone here can help me with something that sounds simple but is turning out not to be.

I want to animate a PNG across my laptop screen on keyboard press. I can create a program to listen to keys but I'm at a loss on how to create an image and put it "on" my laptop screen.

Note: I'm not talking about drawing an image inside an application window because this image must fly over all my currently open windows.

My thoughts are to find a python GUI lib, make a hidden "transparent" application window that I can draw on but this purpose isn't really supported in the major named li
and there is a discrepancy in text description
16:52
seriously, aoc creator is now in reddit telling everyone that "if you have problems with this, then wait until 25th day"
(hopefully that makes sense. I feel like people read "draw image" and assume an application window context, which is true 99% of the time. Sorry for disrupting current conversation. Ping me if you are intrigued)
Today's puzzle description also had a minor typo. This is becoming a pattern
Like they finish up the descriptions minutes before publishing them
@AndrewAllbright fullscreen window? or transparent?
Have author confirmed that 9 is a correct optimal solution?
@AndrewAllbright Assuming you're talking about Linux, it is possible to draw clipped windows, but I don't know what supports it. Probably some lower level call in Xlib or XCB.
16:55
@ŁukaszRogalski well, the point is that could it be less than 11
Wayland supposedly makes this much nicer, if not easier.
@AnttiHaapala I am interested if it was "yeah, that's correct, we shown convoluted example and it was out intention" or "ohh, I guess description was slightly ambiguous, yeah, this one is correct"
@AnttiHaapala Any solution is applicable, I'm open to ideas, as long if it meets these specs...

(1) The transparent application window is 100% height/width of my laptop's viewport
(2) The transparent application window always sits above all other application windows
(3) The transparent application window doesn't capture any events so I can use my laptop normally

The idea being: I only want to animate an image across my screen when I press a very convoluted key combination.
It's not fair, you expect to use example as your "unit" test and then you learn that this test does not test if your space search works correctly :\
Use a BFS with depth 9 and see how many valid solutions it finds along the way
17:00
(Honestly, a trouble I'm facing is finding the vocabulary to describe this domain. I feel like I should read up on GNOME or other OS "draw to laptop screen" literature.)
@AndrewAllbright did you miss my post above?
It's not GNOME, it's X that draws geometry to the screen.
@davidism No, I was just about to respond to it. I have that window open and am going to read to see if there's anything there :)
@MarcusS umm...aren't microchips and generators swapped in the above example? cc @Antti
my solution brute-force checks every possible path, and it finds 11 for the example
incidentally, part 1 real input has been running for half an hour:D
and going
I suspect it will end in T_{universe}/2
also, intermittent cabbage
@AndrasDeak and it is off by 2 :D
and I can't explain why
I'm not sure I agree/understand that
17:05
the minimum is 9
how do you know that?
because someone did it in 9 moves here
what Marcus linked has a different initial state than the official example; there's G<->M swap in the input
@AnttiHaapala they did it wrong?
did they take into account that the elevator can't contain an M+G pair of different kinds? (might not be a constraint)
after switching M and G my code also yields 9
you're right of course
shit :D
17:09
of course I am
:P
so the puzzle is broken
?????
but whyyy yam it?
my correct answer was broken all the time
my initial state is
The first floor contains a thulium generator, a thulium-compatible microchip, a plutonium generator, and a strontium generator.
The second floor contains a plutonium-compatible microchip and a strontium-compatible microchip.
The third floor contains a promethium generator, a promethium-compatible microchip, a ruthenium generator, and a ruthenium-compatible microchip.
The fourth floor contains nothing relevant.
what do you get for this?
17:10
my similar one is still running:D
it will end in finite time, but that's all I can say
@AndrasDeak I'm in same place, it won't complete IMHO
@AnttiHaapala but mine looks very similar
it's the same input
so, @MartijnPieters answer is also broken, since it does not account for item types but only for count of items on each floor?
The first floor contains a polonium generator, a thulium generator, a thulium-compatible microchip, a promethium generator, a ruthenium generator, a ruthenium-compatible microchip, a cobalt generator, and a cobalt-compatible microchip.
The second floor contains a polonium-compatible microchip and a promethium-compatible microchip.
The third floor contains nothing relevant.
The fourth floor contains nothing relevant.
mine (for reference)
Martijn's got 2 stars, so I expect his to work fine:P
Have you seen his code?
17:12
nope, I don't look at the code of others until I've finished with mine
@AndrasDeak no...
martijn didn't code anything
he just wrote a formula for the "solution"
like a boss
@ŁukaszRogalski but you're using cannibals too, right?
17:13
@AnttiHaapala yeah, I based model on M*C
my state space is 4**11 for 10 items position and elevator position
and (unless I do not cache enough it check too much) I feel like naive BFS is designed to fail (timeout)
@ŁukaszRogalski did you finish it yet?
@AnttiHaapala code? sure. It won't complete in reasonable time
So Antti where's your solution from for two stars? Do you have code that should not work?
@AndrasDeak I don't have a solution for 2 stars
you have 2 stars
17:16
I have a solution that counts +2 compared to everyone elses solution
I wanted to see if the pattern matches for the 2nd part too..
honestly, fuck stars, i want to solve it just for satisfaction
... it does
... and now someone said that 9 stars is the correct solution for the starting example.
it isn't.
it isn't.
what is stars?
17:17
however what is even stranger is that I found a ruby solution that parses input, gives 11 for that example, exact solution for my 2 parts
Stars from AoC leaderboard
so why is mine off by 2 except for the example
@AnttiHaapala try bfs instead of dfs perhaps
if has to be BFS for optimal solution, right?
I'm suprised DFS does not yield enormous solution
17:23
You can use DFS but it's not well suited to problems like these and requires extra handling that usually leads to tricky bugs
Suppose I have a list [[1,2],[2,3],[3,9],[4,7],[5,10]] can I sort this list according to second element in the list of list using sorted() ?
@johnsmith key keyword argument
tons of questions on SO
and its mentioned in docs
you need to step up your google game :)
@johnsmith google "python sort list by second element".
Alrgiht guys, I wanna link my math.se question
17:30
@MarcusS perhaps someone else does that
I want to have different algorithms
How would you prune BFS in this case?
Normalize input states
explore only those that minimize error?
What matters is the relative location of chips to generators, so you can relabel each state to minimize the amount of memoization needed
For example SG SM floor 1, PG PM floor 2, same state as PG PM floor 1, SG SM floor 2
17:34
So consider using numeric labels for the elements and relabel each time
ok, thanks for the example
thank you very much!
@MarcusS wikipedia said that the cannibals and missionaries problem has the same lower limit...
so you can just have Gs and Ms, and ensure that there are n(M) <= n(G) if n(G) > 0
Lower limit for what?
minimal steps of solution
bound for minimal number of travels
17:35
and it still shoots above :D
Oh, sure
I am more and more inclined to think that the answers are calculated incorrectly
@MarcusS my algorithm also solves the 3-3 standard jealous husbands correctly, giving 11 moves :/
Would some sort of heuristic be helpful, like scoring a state based on the distance of everything to the top? Could at least inform what paths to look at first, since I assume it's always better to move upwards.
@davidism prefer moving 2 items upwards, 1 item downwards
@davidism yes -- if minimal heuristic + current state exceeds known minimum so far, don't bother checking it
17:44
@davidism if you think your code is right, stop and commit it pls!
geez, I feel so uneducated when I hear you guys talk
@ŁukaszRogalski pfft
@AnttiHaapala haven't solved it yet, mostly just thinking right now. Thinking about how much I want to play The Last Guardian, mostly.
I mean: please keep intermediate states, do not just change it until it magically spits out the "correct solution"
I still have a hard time to put my finger on how to refine search comparing to naive BFS...
18:28
All right, lets dump BFS and do A* :P
18:50
I got 53 with A* and it's too high, I guess heuristics needs to be tweaked
Decorating our Christmas tree, I'm reminded of this:
wat, java doesn't have type inference?
even C++ has it
sheeeeet, I added properly the 2 up/1 down heuristic, and my code started popping out finite answers
who knew algorithm design is important?
@ŁukaszRogalski 53?
19:02
@ŁukaszRogalski keep the code!!!
give me the input, let me try it
The first floor contains a polonium generator, a thulium generator, a thulium-compatible microchip, a promethium generator, a ruthenium generator, a ruthenium-compatible microchip, a cobalt generator, and a cobalt-compatible microchip.
The second floor contains a polonium-compatible microchip and a promethium-compatible microchip.
The third floor contains nothing relevant.
The fourth floor contains nothing relevant.
I also found another code using A* that gives my solution
@AnttiHaapala well, I wrote it :P (but in fact I just mimicked pseudocode from wikipedia) but hey, it works
lol, I got 85 (and 119 for part2)
strange
85 for my input?
19:06
yes :d
:
for your code or this random web code you mentioned?
(5, 3), (0, 2), (0, 0), (0, 0)
my code
which isn't correct at all :D
I wonder what should be correct heuristic_cost_estimate for A*
aha mhm...
this ruby code gives a better number
not gonna spoil it yet :D
but I really don't get what's wrong with my code :D
yep, I'm too close to give this one up :\
part2 has even longer state vector?
19:11
yes
I think.. dfs probably wasn't the best thing to do.
When I read more about space search, it felt so obvious to use some form of smart search
BFS is good enough only for example
yay
51@
51!
51 is also too high :(
yea
this is just wr0ng
Heuristic needs to be aware of generators and microchips, it cannot be just a naive distance from all-zero-vec
ofc not, but ... the solution that I got from a ruby program that I don't understand matches the naive-distance...
go figure
hmm
this one astar* agrees with that, hmhm.
something fishy with my code
@ŁukaszRogalski you can ask me what's your correct answer :D
or rather, "is my answer correct"
@AnttiHaapala Martijns spoiled that is should be :P
well, in range 45-50
19:24
yea
but you can't use binary search any more
I don't care about stars
just want to have it working
its first AoC task where I actually learned something
I am not sure I have learnt anything.
except being annoyed at this
:P
state space search, A* - this is all new to me
wow
got good answet
answer*
I think my dfs still sucks
yeah. my dfs is at fault here :D
I still don't get it, Antti. You have 2 stars, so you submitted a number that was accepted. Is your issue that you don't believe that that was the correct answer, and you're trying to verify it with a program?
19:40
@AndrasDeak I don't get it, you do AoC just for the stars*?
no, but stars for Antti == he submitted numbers that were accepted, so he has some sort of solution for the problem
DSM
DSM
Hmmph. Can someone hint what I'm missing on part 2?
well, and yes, what else?:P
@AnttiHaapala what is the estimated run time for this ruby solution you have?
they all run sub-second
19:41
should I let it run for a few minutes?
ouch
@AndrasDeak Isubmitted numbers from martijns answer
because I wanted to see if they were the same...
sub-second:D
DSM
DSM
What's the initial state? Are all the objects except the new ones on the top? Where is the elevator?
19:42
I pulled the plug on my original (working) solution after a few hours
i am now doing bfs
@DSM first floor, elevator is also on first floor
state vector has 4 new entries, that's the only difference
DSM
DSM
Wait, so after moving all the objects to the top we moved them back down?
or 'elements' I'm not quite sure what is a formal english nomenclature
@DSM you haven't started moving those items yet
reread description :)
DSM
DSM
I have, and it's still confusing to me what state I'm starting with. At first I assumed it was the end state of part 1 (including elevator on top floor) except that I noticed four extra items on the first floor. But I'm on the first floor, so the elevator must have come with me, and we know the elevator can't have travelled alone ("the elevator will only function if it contains at least one RTG or microchip.") So I'm just confused.
19:48
maybe you've given it more thought than the dungeon master?
You make some notes of the locations of each component of interest (your puzzle input). Before you don a hazmat suit and start moving things around, you'd like to have an idea of what you need to do.
and...
You step into the cleanroom separating the lobby from the isolated area and put on the hazmat suit.

Upon entering the isolated containment area, however, you notice some extra parts on the first floor that weren't listed on the record outside:
ok solved
fairly clear to me
part 1 is a Gedankenexperiment, right?
19:49
@AnttiHaapala gz
mine has some serious perf issues, likely due to bad heuristic func
DSM
DSM
@ŁukaszRogalski: possibly I'm an idiot, but just repeating text I've already read and clearly misunderstood isn't likely to help that situation.
and wat:?
a sec
If I understand the description correctly, you notice the additional four objects before you actually start moving stuff
19:52
@DSM I'm sorry, I didn't mean to disrespect or anything. My understanding is: 'before running all of that stuff you have to do a simulation based on some notes on the desk; when you're ready, it's revealed that notes are incomplete and you have to take into consideration 4 additional objects;
hopefully I made myself clear
wat?
wat wat wat? :D
but I don't want to implement A* :(
DSM
DSM
Ah, that's better, thanks @Andras, @vaultah, @ŁukaszRogalski. You were all right about what I was missing, I missed that part 1 was virtual, not actual.
wat??!
and now again the "fries" function is not needed:?
@AnttiHaapala your solution is based on A* or DFS?
19:55
no, simple M*C BFS with deque and visited-set
care to share code? I had that before A* and I am curious why perf in my code was so bad
a sec, I will clean up
@AnttiHaapala awesome, thanks!
did anyone else do day 9 recursively?
@idjaw yep, my part2 was recursive

« first day (2248 days earlier)      last day (2925 days later) »