Having played a nice amount of nonograms. I understand the general idea since its also similar Steps to when you do them yourself. But to put that process to code seems to be a nightmare
@Soverthe3 ай бұрын
Yeah it definitely was lol
@givrally76343 ай бұрын
"You might know Big O notation... I don't." 😂 Just a simple guess, but your new solver looks to be quadratic, and the old one exponential or factorial, thinking of factorial because of the combinatorics involved in a brute force search. I know my parabolas and this one's it.
@Soverthe3 ай бұрын
I'll take your word for it xd
@identityelement77293 ай бұрын
Nonogram is NP-Complete. That means your algorithm should not perform in worst case in polynomial time. Else you solved the P vs. NP Millenial problem and will become rich and famous among the mathematical society. I liked this video very much!
@Soverthe3 ай бұрын
@@identityelement7729 Aw thank you, I don't think I solved any mathematical problems though xd
@givrally76343 ай бұрын
@@identityelement7729 Oh, yeah, I forgot about that. Weird that it looks so much like a parabola though. Maybe it's on some kind of logarithmic scale ? Or, improbable but not impossible, it could actually be quadratic in the average case over a uniform nonogram distribution, but non-polynomial in the worst case. I remember reading about some kind of hamiltonian cycle algorithm that could run in polynomial average time over random graphs.
@steamline4322 ай бұрын
well well well looks like we got ourselves a smart guy
@Soverthe2 ай бұрын
smort
@ScyllaCephalopod3 ай бұрын
you could call them kilograms! wait...
@Soverthe3 ай бұрын
Invention of the metric system 1795 colorized:
@romajimamulo2 ай бұрын
This is pretty close to what I do, except with some memorization for single clue lines and a few assorted very full lines. Though, I tend to do single steps per line and just loop over the lines more frequently (especially switching between horizontal and vertical) since the new information is easier to process the impact it has on the perpendicular
@oiocha333 ай бұрын
Wow, it makes perfect sense (totally understood everything) thx!
@Soverthe3 ай бұрын
I'm totally happy about that (it's 100 awesome to hear the totalness of your understanding)
@Etrehumain1233 ай бұрын
I dont understand anything but I hear a lot of "If... Then..." so I guess I can imagine how it generally works
@Soverthe3 ай бұрын
Programming in a nutshell xd
@itryen76322 ай бұрын
You need to show this to Jerma.
@X-3K2 ай бұрын
pretty cool!
@ITR3 ай бұрын
Hmm, I have an idea that might simplify the logic a little by using a min and max for each min and max on the line (essentially saving both values from the first step). After that it could swap between doing the overlap check in step two (with an additional check for tilesnot inside anything) and propagating directionally on the min constraint or max constraint on the modified tiles and it should cover the different cases in your vid. Would probably be safe to do each row and column in parallel too.
@Soverthe3 ай бұрын
I'll be honest, I didn't really understand any part of this, if you'd like to you could try making that yourself but I'd advise against it since this is not the most fun thing to code Thank ya for the idea though and sorry about not understanding much, but at least judging by your last video you're gonna love my next one xd
@ITR3 ай бұрын
@@Soverthe Oo, are you doing bad apple in nonograms? No worries, already started programming it, but ended up on a sidequest to learn zig somehow. Now I'm fixing one hundred zigling programs one by one, but eventually I'll get back to making a PoC for it, lol
@Soverthe3 ай бұрын
@@ITR Maybe... xd Good luck btw!
@ITR3 ай бұрын
@@Soverthe Managed to write most of it, it solves most small ones fine, but still has some logical issues. Realized storing both the min and max for each end didn't make sense since they're always the clue length apart. But essentially what I ended up doing is: - Loop through line, and in that loop: -- Assign minimum possible clue position when you've passed (length of clue) and next one could be an X, then go to next clue -- Assign maximum possible clue position when you've passed a row of filled tile (counted separately). - Loop through line again, but in reverse, and do the reverse of the previous two points - Loop through clues and fill in "shared tiles" - Loop through pairs of clues and if: clue 1 ends before clue 2, mark all between with X. Else if clue 2 ends before clue 1, and the distance between them is equal to one of the clue, filled in the "shared" tiles of those two clues. Then just loop that until you no longer have anything to change. This manages to do most of the same "rules" you've programmed without checking for the rules specifically, which is pretty fun. Works somewhat fine, but I can't figure out how the last part should work, it essentially generates a contradiction on the hardest 25x25 on your website.
@Soverthe3 ай бұрын
@@ITR Good job! That's really impressive:3 And yeah it will probably always have stuff that it can't do, I solved most of it by comparing the new solver to the old one, but that might not be possible for you since you wrote it in another language (although you could make the old solver pretty easily and then just make random lines and randomly remove tiles from them and give them to both solvers and then you could see what they do differently, the main function for that in my code is massCompareNewAndOldSolver so feel free to take a look at that and the functions that it calls)
@ScoreStudios3 ай бұрын
Nice! It kinda makes sense to me too!
@Soverthe3 ай бұрын
Awesome :3
@TumbleGamerTK3 ай бұрын
1 and 3 function is what i do, woah I also do min and max positions and fill in any shared tiles
@Soverthe3 ай бұрын
Yeah that's the main logic in Nonograms and it's perfect for when you start with an empty line but once you have already filled tiles and Xs it gets really complex for a computer that doesn't just wanna check every possible option
@sirdumpybear3 ай бұрын
this is super cool!
@Soverthe3 ай бұрын
Aw thank you!
@Aterlone-iq9xx3 ай бұрын
Noice, I like it.
@Soverthe3 ай бұрын
Thank ya:3
@Aterlone-iq9xx3 ай бұрын
@@Soverthe Do ya have discord, I would love to have connections with someone who has genuine interests in their field(only if you feel comfortable.)
@Soverthe3 ай бұрын
@@Aterlone-iq9xx Oh yeah sure! My name's soverthe on there