Railbound Solver [Python Script] COMPLETE! Working on Interface... | Afterburn | Page 3

fervent tusk Mar 4, 2024, 1:28 AM

#

solution may be notable as the bottom switch isnt even needed

#

all the levels i tested worked in world 11

#

the only one i didnt do is 11-9b because i can already tell itll take forever

#

so ill leave that for my computer eventually when its done with world 10

#

onto world 12...

#

i cant believe im nearly done with this program

#

dont think the available tracks are supposed to be 5-1j

#

ah

#

solving boards isnt exactly an algebra equation

#

most of the world 12 levels are probably gonna have to go to my computer

#

theyre among the most complicated levels in the game

#

1 saved on 12-1A

#

very, VERY broken solution on 12-3

#

4 tracks saved

#

12-3a failed for some reason, gonna test other levels and come back to it

#

4 saved on 12-4a

#

3 saved on 12-5b

#

4 saved on 12-6b

fervent tusk Mar 4, 2024, 2:47 AM

#

ok, tested every level besides a select few from world 12 that will take a while

#

12-1B, 12-3A, 12-7A, 12-8A, 12-8B, and 12-10

#

12-3A can play the solution but cant find it ib_grumpy

#

thats gonna be the one last thing i think i need to do for this program

#

...tomorrow

fervent tusk Mar 4, 2024, 2:06 PM

#

concerning 8-6a and other lengthy levels im gonna do some server research to find the best solution people have found and then set that as the best tracks so the program runs faster

#

otherwise ill probably modify the program for certain levels to remove unnecessary mechanic checks that waste time

#

otherwise theyll have to wait for c++

fervent tusk Mar 4, 2024, 10:08 PM

#

10-1a is still going after 2 days

#

i think i didnt put enough things for semaphores

#

ah well

#

all thats left to do now is fix 12-3a and send the rest to my pc

#

the reason why 12-3a doesnt work is cause the decoy refuses to crash itself at the top of the board

fervent tusk Mar 4, 2024, 10:37 PM

#

sigh

#

the multiple path branching strikes again

#

when checking for same-tile crashes, cars check for the first generated car for every car's branch (cars generate multiple cars)

#

when decoys generate, they can make both generated cars that dont move and do move depending on whether they crash or not

#

the one that doesnt move is always the first generated car

#

ib_grumpy

#

theres no good way to go about this without making the program slower

#

what i could do is check the last generated car for every branch because then it would always check the car that moves, but then it doesnt account for the one that doesnt

#

i could also not go through with generations that have overlapping cars, but that wastes resources checking for that and also wastes resources going through with everything beforehand while generating when it shouldnt have

#

otherwise i have to make a 2nd list with the first generated car and then negate from the ones that dont move thatd crash

fervent tusk Mar 4, 2024, 11:12 PM

#

the last thing i could do is annihilate it on the turn after and then check if all the cars have different positions

#

but that wastes a looot of resources because its ideal if the invalid path is removed as soon as it gets generated

#

i think its the most viable solution for now though

#

hm

#

actually theres one thing i just realized i could do that would majorly speed up the program

#

right now i pass on 2 major values that are basically the root of all of branching which are: different cars and different tracks

#

i spend time adding those tracks to the lists with the usable tracks

#

but i think i can probably get the different cars to use by just using the list of usable tracks

#

ex. lets say theres a car at [0, 1, 1, 0] which means it is at x=0 and y=1, going right (x+1, y+0)

#

the new cars it could generate would be [1, 1, 1, 0], [1, 1, 0, 1], and [1, 1, 0, -1] and tracks would be 1, 6, 8

#

but i could get those cars by looking at the car positions, and then inputting the direction into the directions array that gives me the redirection

#

will see how much time it saves

#

11-7a can take as little as 2.9 seconds right now

fervent tusk Mar 5, 2024, 12:07 AM

#

ah actually it causes some troubles with tunnels

#

i could probably fix it later

fervent tusk Mar 5, 2024, 12:26 AM

#

i put in somewhat of a fix where it checks if cars have the same position before it proceeds with a branch

#

i can def make it faster but i need to verify it works

#

12-3a is solved now cause of it though (no extra tracks though gp_tongue )

#

yeah it works

#

it seems like its running fine so im gonna leave it

#

...so now theres just the extra levels to run

#

im gonna start trying to run the sandbox levels!!!

#

im not gonna call the program "finished" yet because theres still some of the longer levels to run but i think its done for the most part

#

Railbound Solver [Python Script] World 12/12

#

as for the sandbox levels im gonna try to solve them myself as best as i can, put that as the best tracks count, and then see if the program can do any better

#

#-1

fervent tusk Mar 5, 2024, 1:08 AM

#

the main problem with the sandbox levels is the lower the lowest remaining tracks is the longer its going to take because the program has too much to deal with

#

...well ive done all i can do for now

#

theres nothing to work on

#

i think the next step in truly "finishing" the solver is converting it to c++

#

im not familiar with c++ stuff sooo... i would appreciate it if @calm dawn could give me a good suggestion on what program to use if im doing this in c++ ib_icon

#

something like pycharm but for c++

#

besides that i have a few more things i have in mind for this project!

#

i wanna make visualizers for the program so its easier to see statistics and, well, visualizations of the program because i think thatd be super cool

#

for more of the visualization stuff ill probably use python as im more familiar with it and making visualization stuff seems more user friendly in python (i suppose that is what python is for however)

#

i also want to make a youtube video on the whole process and journey of making this, so thatll probably be the other 6 months of this 1-year project

#

and finally i want to make a github page and learn how to use github which @graceful raven can likely help me with

#

im also gonna make a google doc or something similar to the "least tracks guide" on steam so people can easily look at the stuff

#

i would love to use Snooj's document for all the solved stuff... but in case there's any features i cant edit because i wont be the document owner, im going to make my own... (sorry snooj!! gp_dead )

fervent tusk Mar 5, 2024, 1:26 AM

#

fervent tusk i wanna make visualizers for the program so its easier to see statistics and, we...

also, one of the cool things ive wanted to do since i started the project is make a video that represents what the program would look like in the game if it was done in real-time

calm dawn Mar 5, 2024, 1:45 AM

#

fervent tusk im not familiar with c++ stuff sooo... i would appreciate it if <@66970248083301...

Converting is a big project. C++ is fun though! Look into Visual Studio. Its free. https://visualstudio.microsoft.com/vs/features/cplusplus/

There is also Visual Studio Code, generally just called VSCode, but it isnt the same despite the similar name. I recommend Visual Studio instead.

fervent tusk Mar 5, 2024, 1:46 AM

#

is it really as simple as visual studio?

#

wow

calm dawn Mar 5, 2024, 1:47 AM

#

fervent tusk i would love to use Snooj's document for all the solved stuff... but in case the...

Hah no worries. Alternatively I can make you an owner. You should be ok to edit without ownership access though; pretty sure I have done that with Google Sheets API. It has been a while though.

fervent tusk Mar 5, 2024, 1:48 AM

#

Yeah if i have ownership access thatd be fair

calm dawn Mar 5, 2024, 1:49 AM

#

fervent tusk is it really as simple as visual studio?

Yep. Lots of people do use VSCode now instead but it takes a bit more tinkering with to set up. Visual Studio will just work.

fervent tusk Mar 5, 2024, 1:49 AM

#

yeah im downloading it right now

#

i have the 2019 version from messing with unity i think

#

i didnt know there was such a big difference

#

ahh actually for the document thing i just realized yours is more of a community-edit thing where anyone can edit it but i kinda want mine to just be a page for the solver's data

calm dawn Mar 5, 2024, 1:51 AM

#

Hm. Seems ownership cant be shared but I can give you edit access if you have an email you dont mind being public.

#

Ah, true, didnt even think of that lol. Yeah should have a second spreadsheet. Could have a link to both spreadsheets inside both though.

fervent tusk Mar 5, 2024, 1:53 AM

#

yup!

#

thanks for the effort tho

#

i will try to figure out visual studio once it downloads, converting to c++ is gonna be a massive hassle

#

making the entire project in python made me better at python so hopefully converting makes me a tiny bit better at c++...

#

will probably need help for specifics though

calm dawn Mar 5, 2024, 1:57 AM

#

Funny, I only used C++ once... to convert a project from another language. It was an interesting learning adventure.

#

I am definitely NOT a C++ pro but I can try to help lol. My husband is though so I may forward your specific questions to him. 🤣

fervent tusk Mar 5, 2024, 1:57 AM

#

i thought you did primarily c++? thats one of the things i remember when you first joined the thread and started talking about it

#

ah

calm dawn Mar 5, 2024, 1:59 AM

#

Oh, nope. These days I do mostly Apex (it is Salesforce's version of Java basically), and TypeScript/JavaScript.

fervent tusk Mar 5, 2024, 1:59 AM

#

neato

calm dawn Mar 5, 2024, 2:01 AM

#

You will like C++. It forces you to understand memory allocation of data.

fervent tusk Mar 6, 2024, 12:27 AM

#

re-solving nearly every level in the game to gather some data for the stuff im making... 5-6 apparently doesnt work any more

#

it can play the solution

fervent tusk Mar 6, 2024, 1:40 AM

#

cars above 1 dont stall for 2 frames and instead only stall for 1

#

oh yeah

#

i keep forgetting that when i make list copies they're only 1 list depth of copy

#

so since i updated the station_stalled list to have 2 layers for worlds 11 and 12 it no longer updates correctly

#

so my switch queue variable is also incorrect

fervent tusk Mar 6, 2024, 2:59 AM

#

one thing i just realized for semaphores is that when stations get used up their index on the interactibles board vanishes, meaning a semaphore could then get placed on a station which cant happen

#

so im gonna set them to 26 (deactivated semaphore) indices when theyre used so semaphores cant be placed on them

fervent tusk Mar 6, 2024, 3:17 AM

#

also, 10-1A finished generating and it took 2 days but it got an incorrect solution

#

for 1 it says it has 0 tracks remaining when the solution it gives has 1 remaining, and the solution it gives isnt even viable

#

so im gonna have to rerun it...

#

its still in the process of running other levels though so i guess ill let it finish

#

it did find a lot of cool solutions on world 10 this far though

#

not sure why 10-1A was broken but the others did fine

#

the one its been stuck on for a little less than 2 days now is 10-5A

#

but it has said "Found a new minimum solution!" 5 times so im expecting a massive level break on it which will be cool when it finishes

#

im gonna work on debugging 10-1A after i finish adding some data to my sheet

#

but the program is still chugging through world 10 nonetheless

#

10-1A seems to be the only outlier

#

i think these 2 are pretty funny

#

10-2A can be done with 2 spares AND doesnt even need the semaphores
10-2B ignores using the middle switch-rail entirely and has 4 spares

#

man i love my solver so much

fervent tusk Mar 6, 2024, 4:34 AM

#

re-ran 8-3a and it actually gave me a better solution than before

#

i think im going to redo the world 8 levels

#

i need to finish 8-6A anyways...

#

i remember seeing someone do 8-6A with 11 or 9 remaining tracks so ill just set that as the minimum for that level to speed things up and it should hopefully solve stuff

#

all thats left for the program is just solving all the big levels now

#

originally i wanted to make the program in c++ so i could do the big levels, but im not sure its worth all the effort

#

ive accomplished making a solver and i think that's good enough for me

#

converting to c++ would be a massive hassle

fervent tusk Mar 7, 2024, 2:06 PM

#

program crashed last night

#

wooooo

#

gonna try and make semaphores faster probably and fix up 10-1A before i regenerate world 10

fervent tusk Mar 7, 2024, 10:26 PM

#

generating world 12 in the mean time right now, gonna try figuring out what's wrong with 10-1A and then regenerate it

#

before i actually regenerate it im probably gonna try and figure out if i can make semaphores any faster

#

because i feel like thats one of the newer factors that could be optimized

#

also heres 10-1A before my pc crashed

#

took 163138 seconds, or 1 day, 21 hours, 18 minutes and 58 seconds to generate

#

which is by FAR the longest that has actually finished

#

and 12,103,535,244 iterations

#

12.1 BILLION is insane

#

there has to be something i can do to make that more reasonable

#

if i had to guess what the problem is for 10-1A id say its probably something with the lists not properly copying for some variables

#

yeah it doesnt run the faulty solution it gave me

#

im gonna make the stuff properly copy first

#

might have to do a bit of code rearranging because variable types might change or how theyre organized

fervent tusk Mar 8, 2024, 1:31 AM

#

im not sure what i can do to make semaphores faster tbh

#

i made the variables copy correctly now so 10-1A should hopefully be fine if nothing else goes wrong

#

i dont wanna have to wait 3 hours per test though

#

i guess ill let world 12 finish up and then do other lengthy levels before coming back to it

#

other than that, the script im writing for the video im gonna make on this project is about a third of the way done i think!

#

im gonna have to look at about every message in this thread so its gonna take a while for the script to even be written before i start making the video, but it should be fun

#

12-1B 1 saved

#

511 million iterations...

#

12-7A 1 saved

#

only took 1:57 minutes surprisingly so im not sure why i marked it as a longer level

#

probably didnt want to spend the time running it

#

remaining world 12 levels are: 12-8A, 12-8B and 12-10

#

i actually havent fully tested world 10 so im doing the levels past the lengthy 2 (10-1A and 10-5A) and 10-7 failed

#

the level is input exactly correctly so im assuming its something to do with the decoy being right behind the first car

#

it also fails on the decoys turn

#

...and the program only lasts for a single turn

#

...its because i set the same-tile crashing to do the last car generated which is always the one that places a semaphore, which would make the car in front of the decoy stop and kill the program

#

yaaaay

#

i can never find a compromise

#

i think what ill do when checking for crashes is always check for the last generated car (the one that places a semaphore IF there are any) and then if the position is the same as the car started with (it didnt move so it placed a semaphore) i can just remove that generated car

#

simple

fervent tusk Mar 8, 2024, 2:49 AM

#

i think i added it in but it takes 3 times longer and it has roughly 100k more iterations on 10-7 out of 4.5M

#

sigh

#

ill fix it some other day

#

the only remaining levels that need to be solved are: 8-6A, 10-1A, 10-5A, 11-9B, 12-8A, 12-8B, and 12-10

#

only 7 levels out of 233 are left.

#

the game is 97% solved

#

...i still have a tiny bit of work to do but its coming together nicely

fervent tusk Mar 8, 2024, 1:55 PM

#

ughhhh

#

it solved 12-8A last night but when i tried to open it up the program crashed

#

it had a 7 tracks saved solution though which is absolute wack

#

im gonna rerun it

#

i hope it wasnt faulty

fervent tusk Mar 8, 2024, 9:58 PM

#

#

5h31m

#

1 billion iterations

#

but 7 tracks remaining

#

oh my god it actually works

#

gp_lol gp_lol gp_lol

#

wow

#

7 entire tracks

#

world 12 might be even more broken than world 8

fervent tusk Mar 9, 2024, 4:07 AM

#

im not sure how i didnt realize this earlier but

#

i cleared up some of my pc storage and did everything i possibly could to optimize pycharm

#

so hopefully it should crash less and it runs much faster (i think)

fervent tusk Mar 9, 2024, 5:24 AM

#

the video script has now reached 17 pages and i am starting on world 7!

#

it should hopefully be done soon, but im gonna have to revise it quite a few times to shorten it

#

my goal is to make the video 20-40 minutes so it's watchable, but honestly with everything i've done in this project its kinda hard to fit in into that

#

its quite fun to look back on how far ive come though

fervent tusk Mar 10, 2024, 4:40 AM

#

finished writing the rough draft of the script today, 21 pages long 🥲

fervent tusk Mar 12, 2024, 2:52 AM

#

pycharm crashes on 12-8B too i guess

#

the furthest it got was 5 statements of "new minimum solution found" so im going to rerun it with a best tracks of 4

#

12-10 also crashed

#

sigh

#

...and 10-5A

#

ill do some more program optimizations before i rerun them i guess

#

the only feasible thing i can think to do from this point is literally analyze each generation the program does and see if theres anything to improve on

jovial heath Mar 15, 2024, 1:53 AM

#

Hey there, I just arrived on the server, I'd be interested in taking a look if you've shared your code anywhere, see if I can find any ways to prevent crashing out, or at least make it resumable when it does?

fervent tusk Mar 15, 2024, 1:53 AM

#

yeah i dont see why not

#

im a bit busy making the video for it so im focusing less on it now haha

#

i might come back to it eventually to fix it because i have some ideas but i can share it

#

i have yet to make a github page because i want @graceful raven to hopefully help me with it so i can just send it here

#

ill send it in a moment

#

do whatever you want

📎 v5.1.txt 📎 reference.txt 📎 levels_cars.txt

#

the crashing is probably some limitation with my pc or pycharm

#

the levels that it crashes on are: 8-6A, 10-1A, 10-5A, 11-9B, 12-8B, 12-10

#

kinda wish it was in c++ so it was faster but i dont wanna spend time converting it 😅

jovial heath Mar 15, 2024, 2:07 AM

#

I can't see why I would, but I'm interested I'm on my phone now, so just PyDroid, but tomorrow I'll try it on my pc

#

Ah, I see, it's numpy, but I'm not seeing why straight away

fervent tusk Mar 15, 2024, 2:10 AM

#

it would take a hot 30 minutes for me to explain the program and im afraid i dont really feel like it right now but you can scroll through this thread and look at stuff if you want for some insight

jovial heath Mar 15, 2024, 2:10 AM

#

I'm good, I used to write python professionally, I'll figure it out

#

I might be tempted to use a trampoline to prevent such deep recursion, although it'll likely slow things down

fervent tusk Mar 15, 2024, 2:12 AM

#

I don't code professionally so apologies if I don't understand anything you say or the code is messy

#

...though i hope to get to that point ib_choose

jovial heath Mar 15, 2024, 2:14 AM

#

It's all good, I'm going to leave looking deeper until I'm on my PC, but I think I can give some pointers

#

Trampoline is a method of tail call optimisation to prevent blowing the call stack, rather than using sys to increase the stack limit

fervent tusk Mar 15, 2024, 2:16 AM

#

jovial heath Trampoline is a method of tail call optimisation to prevent blowing the call sta...

the what the what now gp_dead

jovial heath Mar 15, 2024, 2:20 AM

#

Ok, so when you call a function the computer enters a new scope, which is stored along with the current executing line in a data structure called a stack - that's referred to as a stack frame

#

When you return from a function, it pops the top frame off the stack so it knows where to return to

#

Roughly and slightly inaccurately, Tail Call Optimisation is a type of optimisation whereby if the tail of your function, i.e the last thing it does before it returns, is a recursive call, then instead of calling then returning, which increases the stack depth, it returns but tells its caller to call the function, which therefore maintains stack depth

#

You get that built into some languages (mostly functional languages like LISPs, Haskell, that sort of thing), but a trampoline is a way of implementing it in a language without native support

#

I kinda assumed knowledge, because what you've made is a big undertaking even if you know a fair amount

#

So like, it's a compliment I guess?

fervent tusk Mar 15, 2024, 2:28 AM

#

jovial heath You get that built into some languages (mostly functional languages like LISPs, ...

makes... sense now

fervent tusk Mar 15, 2024, 2:28 AM

#

jovial heath So like, it's a compliment I guess?

im a sophomore in high school gp_smile

jovial heath Mar 15, 2024, 2:29 AM

#

That's second year?

fervent tusk Mar 15, 2024, 2:29 AM

#

yup

jovial heath Mar 15, 2024, 2:29 AM

#

Sorry, I'm British, trying to figure out what's equivalent, I'm guessing you're about 17, 18?

fervent tusk Mar 15, 2024, 2:30 AM

#

15

jovial heath Mar 15, 2024, 2:30 AM

#

Oh wow

fervent tusk Mar 15, 2024, 2:30 AM

#

my brother codes for his job so he showed me a cool thing python has where you can check the time each function takes which i used to debug some stuff a while back

#

should probably use it again

jovial heath Mar 15, 2024, 2:30 AM

#

At your age I could barely crank out Blackjack on my graphing calculator

#

Yeah, I was assuming you knew terms I didn't come across until I got to my degree course

#

My bad

fervent tusk Mar 15, 2024, 2:32 AM

#

youre good

jovial heath Mar 15, 2024, 2:34 AM

#

Right, I should get some sleep and then take another look in the morning (it's gone 02:30 here)

fervent tusk Mar 15, 2024, 2:35 AM

#

ok! let me know what you see tomorrow

#

i still kinda wanna maintain some degree of me making it cause im proud of making it solve this far so sorry if i get a bit pushy sometimes

#

i have school tomorrow so i probably wont be able to talk by the time you go to bed but im free on the weekends... i hope

jovial heath Mar 15, 2024, 2:37 AM

#

Not at all, I might kinda fork my own version if you don't mind, so I can show you some stuff, but you're free to take or leave any advice, and I'm not going to show my ideas anywhere else?

fervent tusk Mar 15, 2024, 2:38 AM

#

sounds fair

fervent tusk Mar 15, 2024, 3:53 AM

#

rerunning 10-5a starting with 4 spares because of the 5 "new min found" lines from before, hopefully it finishes unlike all the other levels

jovial heath Mar 15, 2024, 12:55 PM

#

Ok so I've got it running,

fervent tusk Mar 15, 2024, 12:58 PM

#

fervent tusk rerunning 10-5a starting with 4 spares because of the 5 "new min found" lines fr...

crashed again when i checked it this morning

#

starting to think its something with the program cause it happens much earlier than b4

#

one thing to note is on task manager python.exe is always separated from pycharm when i check it (later) on the crash levels

#

like not under the tree

#

shrug

jovial heath Mar 15, 2024, 1:04 PM

#

I'm also noticing that it's only using at most 10% CPU and about 50MB RAM on my system, so something is slowing things down artificially

jovial heath Mar 15, 2024, 1:23 PM

#

Urgh, I used to run PyCharm Professional which has a built in profiler, but the version I have a license for only supports python versions up to 3.9, which means after looking around PyCharm CE for it for ages before realising it's not there, I'm looking at other tools

#

OK so for 8-1 cProfile spits out

         7007668 function calls (6812568 primitive calls) in 9.493 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    433/1    0.003    0.000    9.493    9.493 {built-in method builtins.exec}
        1    0.000    0.000    9.493    9.493 main.py:1(<module>)
 188380/1    7.906    0.000    9.088    9.088 main.py:81(generate_tracks)
       68    0.001    0.000    0.936    0.014 __init__.py:1(<module>)
   942015    0.449    0.000    0.449    0.000 {built-in method numpy.array}
    520/4    0.003    0.000    0.404    0.101 <frozen importlib._bootstrap>:1349(_find_and_load)
    520/4    0.002    0.000    0.404    0.101 <frozen importlib._bootstrap>:1304(_find_and_load_unlocked)
3573902/3573644    0.403    0.000    0.403    0.000 {built-in method builtins.len}
...

Which doesn't tell us much yet because so much of the code is in generate_tracks, so I'm going to split out some functions for the body of that

#

(to get this then all you do is instead of running python main.py you run python -m cProfile main.py)

jovial heath Mar 15, 2024, 2:09 PM

#

still whittling down the generate_tracks function, but I solved the recursion issue less invasively than using a trampoline - it's now a generator that yields the arguments for further calls, and you call it like so:

    argslist = [
        (list(cars + decoys + ncars), np.array(board), np.array(interactions), maxTracks,
                    np.zeros((len(cars + decoys + ncars), 4, *boardDims)), [[-1] * len(cars), [-1] * len(ncars)],
                    [False] * len(cars + decoys + ncars), np.full((len(cars + decoys + ncars), 2), -1),
                    [False] * len(cars + ncars), np.full((len(decoys), 2), -1), 0, semaphores)
    ]
    while argslist:
        args = argslist.pop()
        new_args = list(
            generate_tracks(*args)
        )
        argslist.extend(reversed(new_args))

#

that means you longer need to recurse, and it shaves about 1s off 8-1 just because its not managing a ridiculously deep stack

#

there's more optimisations that could be made with that technique, especially if the order of calls doesn't matter, but this is probably plenty, and premature optimisation is the root of needless complexity

#

I'm probably going to leave it there for a bit, maybe the rest of the day (I have a fatigue condition which is why I don't work any more, and if I overdo it one day I'll get far less done over the course of a week)

fervent tusk Mar 15, 2024, 2:40 PM

#

neat

fervent tusk Mar 15, 2024, 2:41 PM

#

jovial heath that means you longer need to recurse, and it shaves about 1s off 8-1 just becau...

how long did 8-1 take when you ran it before?

#

like how much of a % save is 1s for how fast you ran it

jovial heath Mar 15, 2024, 2:41 PM

#

9.4, now it's down to 8.4, so it's something like a 9% saving

#

Uh, 11%

#

Don't mind my mental arithmetic, there's a reason I get computers to do it for me 😅

#

I'm trying to run 10-5a and it has been going a few minutes already, but it's now using 12-18% CPU and only 16.4MB of RAM, so stack management was a pretty large overhead

#

My PC is nothing special, it's an R5 7600

#

Latest output:
Found a new minimum solution! (2052.1963s)

jovial heath Mar 15, 2024, 3:30 PM

#

Found a new minimum solution! (1906.0791s)

#

iirc you said it produced 5 of those eventually and then crashed?

jovial heath Mar 15, 2024, 4:14 PM

#

Found a new minimum solution! (3009.2724s) Found a new minimum solution! (2.7329s)

fervent tusk Mar 15, 2024, 4:28 PM

#

yeah

#

if it solves send a pic of the full output

#

so i can analyze the solution (and for record keeping!!)

#

tysm

#

i cant believe you can run 8-1 at 11s... mine does it in around 130 i think

jovial heath Mar 15, 2024, 4:31 PM

#

oh wow, that's quite a difference, what hardware are you running on?

fervent tusk Mar 15, 2024, 4:31 PM

#

7 year old pc 😁

#

couldnt tell you the specs off the top of my head but it cant upgrade to windows 11 cuz its that bad

#

i tried running it on my laptop which is from a tech dump at an engineering company and my pc was still 1.5x faster than ut

jovial heath Mar 15, 2024, 4:33 PM

#

ah, yeah, I just upgraded, I know the pain, my old rig was an i5 4690k with ddr3 running at 1666MT/s and the upgrade has been night and day, I only justified it as getting out ahead of Windows 10 EOL next year so I'm still running a GTX 1060

fervent tusk Mar 15, 2024, 4:33 PM

#

my pc has a nvidia 1060t which i think is the only thing going for it at this point

#

the storage is literally 128gb 🥲

jovial heath Mar 15, 2024, 4:34 PM

#

like, I'm running this stuff in the background while I run heavily modded XCom2 because I know I have the spare horsepower

jovial heath Mar 15, 2024, 4:34 PM

#

fervent tusk my pc has a nvidia 1060t which i think is the only thing going for it at this po...

Please tell me it's at least the 6GB version?

fervent tusk Mar 15, 2024, 4:34 PM

#

not sure

#

i remember i just got it so i could play vr on my pc and you needed a gpu for it

#

so probably 6 or 8

#

im so glad your pc can run something like 8-1 in 10s

jovial heath Mar 15, 2024, 4:35 PM

#

ah yeah, there's no way you're on the lower tier version if it can handle VR, 6GB is the highest that card goes

fervent tusk Mar 15, 2024, 4:36 PM

#

ill finally be able to run the crash levels and then rb will be fully solved

jovial heath Mar 15, 2024, 4:37 PM

#

I might not want to run it all without seeing if we can improve the algorithm, as it would be running up quite the electricity bill if it wasn't just a background task while I game

fervent tusk Mar 15, 2024, 4:38 PM

#

true

jovial heath Mar 15, 2024, 4:38 PM

#

Found a new minimum solution! (1775.857s)

#

that's the 5th, so let's see if it gets further

fervent tusk Mar 15, 2024, 4:38 PM

#

theres a couple things i remember are wrong with it that i have yet to fix but it works for basically everything

jovial heath Mar 15, 2024, 4:39 PM

#

oh exciting, a 6th

#

here's the full output so far

[[ 0  0  1  0  0  9  1  0]
 [ 1  1  0  0  0  0  0  0]
 [ 0  0  0 20  0  0  0  0]
 [ 0  4  4  0  0  0  4  0]
 [ 0  0  1  0  0  0  0  2]
 [ 0  2  0  0  0  0  0  0]
 [ 0 13  0  0  0 15  1  3]
 [ 0  0  0  0  0  0  0  0]
 [ 0  0  1  0  0 17  0  0]]
Generating...
Found a new minimum solution! (2052.1963s)
Found a new minimum solution! (1906.0791s)
Found a new minimum solution! (3009.2724s)
Found a new minimum solution! (2.7329s)
Found a new minimum solution! (1775.857s)
Found a new minimum solution! (23.3531s)```

fervent tusk Mar 15, 2024, 4:40 PM

#

im curious, do you already know what some of the board numbers mean and how the cars are made?

jovial heath Mar 15, 2024, 4:40 PM

#

so I know how to look up the numbers

#

but I've not got the simulation quite down

fervent tusk Mar 15, 2024, 4:41 PM

#

jovial heath so I know how to look up the numbers

have you looked at the reference file

jovial heath Mar 15, 2024, 4:41 PM

#

yeah

fervent tusk Mar 15, 2024, 4:41 PM

#

okay thats good

jovial heath Mar 15, 2024, 4:42 PM

#

I'm tempted to make some Enums to make things a bit easier to grok, but I'm wary of changing too much

#

My first instinct for how to understand it all is to rewrite everything, but that wouldn't really be doing justice to the hard work you've put in

#

so I'm just poking at the edges

fervent tusk Mar 15, 2024, 4:43 PM

#

the bulk of how generation works is it iterates over every car, looks at where it is, then gives it every track it can place, tests for crashes with other cars, and then tests every track it can place to see if its not useless

jovial heath Mar 15, 2024, 4:44 PM

#

are you doing anything to check you're not recalculating old work?

fervent tusk Mar 15, 2024, 4:44 PM

#

then it does that for each car and creates like 27 different branches of each possible track combo

fervent tusk Mar 15, 2024, 4:44 PM

#

jovial heath are you doing anything to check you're not recalculating old work?

wdym

jovial heath Mar 15, 2024, 4:45 PM

#

so something I think might help is to have a calculation you run over the current state to make a number, which you store in a set, and then you know that if the number is already in the set, you don't need to branch from there again, because you've already done that work

fervent tusk Mar 15, 2024, 4:46 PM

#

no i dont think so

#

other cars can create paths that must be considered for when placing

#

the idea itself sounds very good though

#

i could probably improve the car riding over tracks that are already placed though

#

the car always places a track no matter what each frame (unless its a decoy crashing)

#

so if its riding over pre-placed tracks it still calculates placing the track, but it just doesnt remove 1 from available_tracks

#

it still has to think about making 3 ways though but ive done stuff for that too

jovial heath Mar 15, 2024, 5:03 PM

#

cool, then that gives me a hint to look at how you're putting together the state to see if I can roll a hashable datastructure for it, it'll possibly help catch things like infinite loops a lot earlier, and hopefully take you from what looks like exponential complexity to something more like quadratic

jovial heath Mar 15, 2024, 6:20 PM

#

Still running, if it's still going in an hour then I'll be putting my PC to sleep, and might not have a chance to boot back up until Sunday

fervent tusk Mar 15, 2024, 6:43 PM

#

fair

fervent tusk Mar 17, 2024, 1:58 AM

#

gonna look at the program periodically as i work on the video

#

the biggest save at this point would be fixing heatmap limits so its not just a static 10 on levels with swapping tracks

#

8-6A is one of the crashing levels that takes forever because it has a bunch of tracks and a big board for 1, but it also has a heatmap limit of 10 because of the 1 singular swapping track before the end

#

which i guarantee makes the program take at least twice as long

#

i need to find a way to figure out when to raise the heatmap limit for certain tiles when a swapping track is crossed

#

like how to raise it

#

...actually i think its simpler than im making it

#

now that i think about it

#

i can have a 2nd copy of the entire heatmap list for cars that indicates the limit for each tile, and then if a swapping track is crossed it just raises the limit for all previously visited tiles by 1

#

im not sure if its perfect but it sounds... sound to me right now

#

will use 4-9 for reference right now, it can currently do it ~0.9s with 28,284 iterations

fervent tusk Mar 17, 2024, 2:22 AM

#

the hardest part is figuring out which tiles have tracks placed on them though

#

because a newly placed track will have a heatmap limit of 1, as will an empty tile

#

it needs to be efficient too because iterating over the heatmaps to figure out where something is placed and where something isnt is awful

#

i think ill just start with a blank 0 heatmap limit sheet and then when a track gets placed for the first time it gets raised to 1

#

impractical but its fine

jovial heath Mar 17, 2024, 2:09 PM

#

Ok so I killed the process after it had about 17 hours of runtime (over a 45 hour period, which is why the stats look janky) and it was still going, despite having generated 6 solutions in the first 2½ hours, and then no more, so I think it might have fallen into an infinite loop? I had to kill the process to install updates

#

https://gist.github.com/alistair-broomhead/31c073c55edc21c8579c0035528e75df

Gist

solver.out

GitHub Gist: instantly share code, notes, and snippets.

#

Obviously with recursion an infinite loop would eventually blow the stack which is probably why it crashed before

#

Whereas having unwrapped to an iterative solution, it'll just run forever

#

A stop-gap might be to print the solution as soon as a new fastest solution is found

#

Because then you should get something

#

Even if it's not definitively the fastest

fervent tusk Mar 17, 2024, 2:54 PM

#

ye i thought about that

#

im convinced with the infinite loop thing but at the same time the program has to generate everything it can before it quits

#

and the heatmap limit of 10 doesnt helpt that

jovial heath Mar 17, 2024, 3:12 PM

#

Yeah, just 17 hours is a long time

fervent tusk Mar 17, 2024, 3:12 PM

#

fervent tusk the biggest save at this point would be fixing heatmap limits so its not just a ...

eeeeexactly

jovial heath Mar 17, 2024, 3:22 PM

#

Like, statistically it seems unlikely that the top 6 fastest solutions are found in less than ⅙ of the run

#

But I'll give you that it's not impossible

fervent tusk Mar 17, 2024, 3:23 PM

#

i feel like semaphores would be the other big problem because theyve been implemented very recently and are complicated

#

+they basically double generation since semaphores are a 4th placing option...

#

4th 5th and 6th actually

#

so yeah

#

not bueno

jovial heath Mar 17, 2024, 4:05 PM

#

Just to check, a semaphore in this context is the barrier that opens when something passes its intersection?

fervent tusk Mar 17, 2024, 4:05 PM

#

mhm

fervent tusk Mar 17, 2024, 6:06 PM

#

jovial heath https://gist.github.com/alistair-broomhead/31c073c55edc21c8579c0035528e75df

thanks for sending this! i've never actually looked at the cprofile for something as long as this so its a lot more helpful seeing the time it takes for stuff

#

like flatten takes 1600 seconds...

#

no matter what percent its still time saved on lengthy stuff

#

30 minutes is 30 minutes

jovial heath Mar 17, 2024, 6:07 PM

#

Bear in mind that cumtime is meaningless when the PC slept at various points

fervent tusk Mar 17, 2024, 6:07 PM

#

it is?

jovial heath Mar 17, 2024, 6:08 PM

#

Yeah because of you start something that takes a second, but suspend for a minute half way through, it'll read as 61 seconds

#

*if

fervent tusk Mar 17, 2024, 6:08 PM

#

ah

#

helpful nonetheless considering its that long of a cprofile

jovial heath Mar 17, 2024, 6:09 PM

#

Yeah

#

I just wanted to warn against taking the numbers at face value

fervent tusk Mar 17, 2024, 6:15 PM

#

ive wanted to make a github page for the solver too, so... since barciu wont respond could you show me how to do that

jovial heath Mar 17, 2024, 6:53 PM

#

Do you have an account?

graceful raven Mar 17, 2024, 8:28 PM

#

I’m still here and I’ll be happy to help with GitHub.

jovial heath Mar 17, 2024, 9:14 PM

#

I guess I should ask first whether you know how to use git

fervent tusk Mar 17, 2024, 11:08 PM

#

Nope

jovial heath Mar 17, 2024, 11:17 PM

#

Ok so you'll probably want to make an account on GitHub, and, what OS do you run? Assuming it's Windows, because games, grab GitHub for Windows and log onto that with your new account. You seem plenty smart enough to work that out and then use the gui to create a repository from your project.

#

Lemme know if you run into any problems

fervent tusk Mar 17, 2024, 11:20 PM

#

yeah

#

ok thanks

#

ill probably add it in once i do the heatmap limit thing

#

simpler than i thought i guess!

#

github just seems intimidating to me lol

jovial heath Mar 17, 2024, 11:26 PM

#

Eh, it's not that hard, once you turn the project folder into a repository pycharm should notice and let you do stuff from there

#

You'll likely want to create a file in there called .gitignore and add a line to it with the text .idea so it ignores your pycharm project files

#

Then you can add that file and the three python files to a commit, and give it a message like "Initial commit" or something

#

Then GitHub for Windows should let you push the repo to a new project on GitHub

fervent tusk Mar 17, 2024, 11:29 PM

#

alr

#

thanks

#

ib_hi

jovial heath Mar 17, 2024, 11:32 PM

#

Then every time you do more stuff on the project then you can add the files you've changed to a new commit, add a message saying what you've done, and commit, then push that commit to GitHub

#

You can do that either in pycharm or the GitHub for Windows app

fervent tusk Mar 17, 2024, 11:33 PM

#

is that like how releases work

jovial heath Mar 17, 2024, 11:33 PM

#

No, but it's related?

fervent tusk Mar 17, 2024, 11:33 PM

#

ah

jovial heath Mar 17, 2024, 11:35 PM

#

You can find a load of articles about what makes a good git commit message, but basically you're just creating snapshots of your codebase that you can view, and roll back to at any time, like a complicated undo buffer

#

There's way more to it than that

#

Git is a pretty powerful and complicated tool, but you don't need to know much to use it at a basic level

jovial heath Mar 18, 2024, 2:07 PM

#

Not necessarily useful but I was playing with using cProfile through a context manager so I could still attach a debugger, and thought I'd check out the run to run variance:

https://gist.github.com/alistair-broomhead/f4ae8add2c4192174e5746288098c195

Gist

solver-variance.out

GitHub Gist: instantly share code, notes, and snippets.

#

also I had it spit out each solution as it found it

#

I think I am going to have to work through my own version of this before I can give deeper insight into what you might need to change to get things solved a bit quicker

jovial heath Mar 18, 2024, 2:53 PM

#

I feel like I'm missing a step reading

# directions contains instructions on which axis to move a car if it's on the given track in (x, y) format
# the instruction for each direction is listed by index shown by xyToIndex (0=left, 1=right, 2=down, 3=up)
# directions are shown in form of "car is going (left, right, down, up)"
# e.g. car going down onto a vertical track will be 0-1-2nd index. 2nd index of vertical track instructs to go down 1.
# (2, 2) indicates a crash, (3, 3) for empty and (4, 4) for ending might be used later
directions = np.asarray((
    ((2, 2), (2, 2), (2, 2), (2, 2), (0, 0)),  # 0 Empty
    ... snip ...
    ((0, 0), (2, 2), (2, 2,), (2, 2), (0, 0))  # 22 Numeral Car Ending Track (Left Side)
))

Like, the direction is already a shorthand for a 2d transformation so assuming the top left is the (0, 0) and on a 10x10 board the bottom left is (9, 9) then left is (-1, 0), right is (1, 0), up is (0, -1), down is (0, 1), so for a direction instruction to be an array of pairs of transforms is kinda confusing me. Like I could understand if it was an array of 4 transforms based on which direction you were already moving in, but I'm kinda scratching my head

fervent tusk Mar 18, 2024, 3:35 PM

#

depending on the track it can redirect in multiple directions based on one

#

if the car is going down it can go left right or down and you cant instantly determine that because it varies from track to track

#

i feel like im only understanding half of what youre saying

fervent tusk Mar 18, 2024, 3:36 PM

#

jovial heath I feel like I'm missing a step reading ```python # directions contains instruct...

also, bottom right not bottom left i assume?

#

are you saying i should just put in 6 (no mvmt and crash) directions as numbers instead of (#, #)?

#

like use 1 and 2 in place of right (1, 0) and up (0, -1)

jovial heath Mar 18, 2024, 4:27 PM

#

fervent tusk if the car is going down it can go left right or down and you cant instantly det...

I'm pretty sure the three tracks are deterministic, right? So if you have a vertical track with a fork to the left, you choose when you draw the track whether that's a fork to the left when moving up or moving down, and in the other direction it's a straight on?

jovial heath Mar 18, 2024, 4:29 PM

#

fervent tusk are you saying i should just put in 6 (no mvmt and crash) directions as numbers ...

If the pairs are (direction, status) that makes more sense, but I'm not sure how that makes sense?

#

Like, how does (2, 2) indicate a crash?

#

I'm sure there's some logic there, I just can't follow it

fervent tusk Mar 18, 2024, 4:38 PM

#

all of the directions are meant to be where the car moves so (0, 0) makes sense for something like an end track because it doesnt move after it reaches it, and itd mess the program up because if it was (1, 0) the car would crash into the wall and say it wouldnt work

#

i use (2, 2) as a substitute the program can read for crashes because its not as clean when you have something like "0" for crashing among sets of transformations

fervent tusk Mar 18, 2024, 4:44 PM

#

jovial heath I'm pretty sure the three tracks are deterministic, right? So if you have a vert...

as for this part im afraid i still dont understand
if a car is riding over a 3-way that it isnt instantly placing, it still needs to know what route to take
also, cars dont determine what velocity they take for the next branch. they determine what track they pick, and that track gives them the new velocity

#

are you saying i should use transforms for branching instead of tracks?

fervent tusk Mar 18, 2024, 4:48 PM

#

fervent tusk i use (2, 2) as a substitute the program can read for crashes because its not as...

also, (2, 2) is a lot easier to differentiate because you can just check if the x velocity in the transform is 2, and if it is then it's a crash

fervent tusk Mar 18, 2024, 4:54 PM

#

fervent tusk are you saying i should use transforms for branching instead of tracks?

if i did this i would still need a chart because theres multiple tracks that make a car go down, it doesnt make sense to just say which one in every instance rather than having an organized chart to refer to

jovial heath Mar 18, 2024, 5:04 PM

#

I think we each have a very different mental model of the problem, lemme think about this a while and see whether I can figure out precisely what you mean

jovial heath Mar 18, 2024, 6:47 PM

#

I updated https://gist.github.com/alistair-broomhead/31c073c55edc21c8579c0035528e75df with new output having told it to print each best board as it is found

Gist

solver.out

GitHub Gist: instantly share code, notes, and snippets.

fervent tusk Mar 18, 2024, 7:19 PM

#

thanks, ill look at it

#

super helpful idk why i didnt do it before

jovial heath Mar 18, 2024, 7:32 PM

#

If you pass me a link to your project on GitHub I'll make a pull request with the changes

fervent tusk Mar 18, 2024, 7:37 PM

#

isnt all you changed reporting found solutions and the recursion depth?

jovial heath Mar 18, 2024, 7:45 PM

#

Yeah, well I also moved the globals into a namespace object to make it easier to move things about, but I've not done anything with that yet

fervent tusk Mar 18, 2024, 10:52 PM

#

the solution takes literally forever even with max speed but

#

it works

#

pretty nifty

jovial heath Mar 18, 2024, 11:26 PM

#

Just tried running it myself, I've come up with solutions by hand that take longer, while being nowhere near as efficient 😂

fervent tusk Mar 18, 2024, 11:26 PM

#

lmao

#

thats the longest solution ive seen in the entire game

fervent tusk Mar 20, 2024, 12:13 AM

#

gonna switch from 4-9 to 4-3A because 4-9 can still get a solution with a heatmap limit of 1

#

so 4-3A with a heatmap limit of 10 takes 958 iterations

#

(before)

fervent tusk Mar 20, 2024, 12:39 AM

#

pretty sure i added it in, it can now do it in 805 iterations

#

only slightly less because its less open

#

im gonna try it on a bigger level

#

ok, 4-7B takes 23443 iterations

#

with the old method

#

...and with the new one it only takes 5098

#

pretty sweet

#

5-4b with the old one has 2,915,395 iterations whereas the new heatmap limit has 288,738

#

137s to 11s.

#

pretty good change if you ask me

#

levels still take a bit but its good that its much faster now

#

i wanna add it to github now but im not really figuring it out

#

still is confusing...

#

do i make a github project from pycharm or from github for windows?

fervent tusk Mar 20, 2024, 1:40 AM

#

i tried doing it from github for windows earlier and the files are still confusing, like i dont understand where the project goes and if it saves and if itll still maintain on the website and all that

#

10-1 didnt work, so theres still some stuff to be done

#

ah, if it's stalled on a swapping track it keeps adding to the limit

jovial heath Mar 20, 2024, 8:36 AM

#

fervent tusk i wanna add it to github now but im not really figuring it out

Where did you get up to?

fervent tusk Mar 20, 2024, 11:14 AM

#

i have the purple github icon app on my pc at the basic "clone, make, or create a repository" and nothing for pycharm

jovial heath Mar 20, 2024, 11:26 AM

#

Ok, you'll want to create a repository

#

https://docs.github.com/en/desktop/overview/creating-your-first-repository-using-github-desktop#part-2-creating-a-new-repository

GitHub Docs

Creating your first repository using GitHub Desktop - GitHub Docs

#

Or you can create the repository in pycharm from your project, and then add that repository in GitHub Desktop (looks like they changed the name)

#

The former will mean you have to move your files in, but you just need to follow one tutorial, while the latter let's you leave them in place but you'll need to come bits of this one https://www.jetbrains.com/help/pycharm/set-up-a-git-repository.html#put-existing-project-under-Git

PyCharm Help

Set up a Git repository | PyCharm

#

Tell it to ignore the pycharm project files

fervent tusk Mar 20, 2024, 10:32 PM

#

alright, fully set up a github page (i hope) for the project
https://github.com/FoxtrotOnce/RailboundSolver.git

GitHub

GitHub - FoxtrotOnce/RailboundSolver: A solver for levels in Railbo...

A solver for levels in Railbound. Contribute to FoxtrotOnce/RailboundSolver development by creating an account on GitHub.

jovial heath Mar 20, 2024, 11:27 PM

#

Looks good

jovial heath Mar 21, 2024, 11:50 AM

#

I've submitted https://github.com/FoxtrotOnce/RailboundSolver/pull/2 which is all my changes that I think you'll definitely want, but I'm happy to remove anything you're unhappy with

GitHub

Enhancements to fix blown stacks and make it easier to progress imp...

#

I also noticed that the code you submitted doesn't run for 10-7 (I've not checked other levels) but I'll check that later

fervent tusk Mar 21, 2024, 12:00 PM

#

yeah ive already noted that

#

its a very specific semaphore problem i have to find a faster patch for

#

if u look at the github program i commented out a fix for it because it slows it way down

jovial heath Mar 21, 2024, 12:02 PM

#

I wasn't sure when you'd be around so I tried to explain some of what I was doing assuming you know nothing, so that you could ignore what you do already know

#

Like I only realised a couple of days ago that implementing the TCO as a decorator would be way cleaner than making the place that calls it worry about it, but also I didn't know whether you're familiar with decorator syntax

fervent tusk Mar 21, 2024, 12:05 PM

#

whats tco?

jovial heath Mar 21, 2024, 12:05 PM

#

The PR is probably easier to read one commit at a tim rather than all at once

#

Tail Call Optimisation

fervent tusk Mar 21, 2024, 12:05 PM

#

ah

jovial heath Mar 21, 2024, 12:08 PM

#

See everyone was a beginner once and there's no shame in it, but as somewhat of an expert, it's a bit like https://xkcd.com/2501/ . Keep asking questions, it's the only way to learn and the only way I'm going to shake assumptions

xkcd: Average Familiarity

fervent tusk Mar 21, 2024, 12:10 PM

#

also what is decorator syntax and PR

jovial heath Mar 21, 2024, 12:22 PM

#

PR is Pull Request

fervent tusk Mar 21, 2024, 12:23 PM

#

just saw the thing on decorator syntax

jovial heath Mar 21, 2024, 12:23 PM

#

Does it make sense, or would you like the tutorial link I just dug up?

#

I'll send the link before I lose it and you can always ignore it if it's unnecessary: https://pythonbasics.org/decorators/

fervent tusk Mar 21, 2024, 12:27 PM

#

i somewhat understand the changes but for the most part they all use code blocks(?) ive never even seen

jovial heath Mar 21, 2024, 12:28 PM

#

Fair enough, so I think as well as decorators I introduced context managers, classes, and type hints?

fervent tusk Mar 21, 2024, 12:28 PM

#

ya

#

classes and objects are one of the most basic things i havent really looked into which i feel kinda guilty about

#

guess i never found an applicable use or thought of onw

jovial heath Mar 21, 2024, 12:31 PM

#

There's plenty in that codebase which would be cleaned up using classes: https://pythonbasics.org/class/

But it's also easy to go overboard with object oriented programming

#

An object is basically a bundle of state (variables) with some functions which act on said state

#

And a class is a recipe for making an object

jovial heath Mar 21, 2024, 12:36 PM

#

fervent tusk classes and objects are one of the most basic things i havent really looked into...

To be fair it's a big topic, there's a lot you have looked at and only so much personal time? I'd recommend looking into it to save yourself work, but I'm not one to put negative moral value on what you have and haven't learned in your spare time

#

I'm trying to find simpler stuff explaining context managers, but for now this is the best I've found: https://realpython.com/python-with-statement/

Context Managers and Python's with Statement – Real Python

In this step-by-step tutorial, you'll learn what the Python with statement is and how to use it with existing context managers. You'll also learn how to create your own context managers.

#

Similar for type hints, but I wouldn't really worry about understanding them, just think of them as a comment that the IDE understands. But here's a tutorial if you're really interested

#

If you have questions on the PR, it's probably easier if you put the questions there so I can more easily point to the code and annotate it in place

#

But classes are probably the first thing to understand before the rest

fervent tusk Mar 21, 2024, 10:17 PM

#

i think one of the next steps for solving is figuring out 10-1a because it had a faulty solution

fervent tusk Mar 21, 2024, 10:18 PM

#

fervent tusk

looking back at this it took about 3 hours to generate the solution

#

with the new stuff it should likely take somewhere between 1-3 hours

#

so im going to do that and then analyze it since it's faulty

fervent tusk Mar 21, 2024, 11:43 PM

#

only took 49 minutes.

#

i love how much the heatmap limit thing sped it up, though i still have to look into al's stuff and add in the tail recursion (i wish there was someway i could partially merge because i want that but not the cprofile stuff, and itd be weird if i merged that and removed it or just added in the code without merging)

#

oh

#

it didnt get the solution

#

...but it works

fervent tusk Mar 21, 2024, 11:47 PM

#

fervent tusk i love how much the heatmap limit thing sped it up, though i still have to look ...

i will... run it further once if i could get some info on this?

#

i wanna properly only merge the tail recursion because deleting or adding in code manually i feel would make it look strange

#

otherwise i suppose i could just add a comment for the manual addition.

jovial heath Mar 21, 2024, 11:57 PM

#

fervent tusk i love how much the heatmap limit thing sped it up, though i still have to look ...

I can pull that commit out

fervent tusk Mar 22, 2024, 12:00 AM

#

actually i just realized its positioned where i could just do up to the 3rd commit and not do it because its the 4th

#

...i still only want the tail call recursion though and not any of the .gitignore or requirements.txt

#

should i just do a manual addition and make a comment or would that not do justice (i feel like it wouldnt)

jovial heath Mar 22, 2024, 12:03 AM

#

Ah, in that case you could just cherry pick the commit, but I'm not sure why you wouldn't want the requirements file or the gitignore

fervent tusk Mar 22, 2024, 12:04 AM

#

the changes dont seem that big imo and i want the program to be as close to mine as possible

#

id prefer having big change edits instead of smaller things that dont do as much and arent made by me

#

also wdym by "cherry pick" the commit?

#

can you just like only do changes on one specific commit

jovial heath Mar 22, 2024, 12:06 AM

#

git cherry-pick {commit_hash}

#

You should be able to open a shell/console from GitHub Desktop and run that where {commit_hash} is 5ab213b525c685c50b5a7dc04d4ee56354fc3606

#

You might need to add my fork as a remote

#

git remote add alistair-broomhead https://github.com/alistair-broomhead/RailboundSolver git fetch

#

It's generally considered better to make small atomic commits precisely so it's easier to cherry-pick what you want and reject what you don't, rather than having a commit with hundreds of lines where you only want a few of them

fervent tusk Mar 22, 2024, 12:19 AM

#

oh wait you said the remote thing

#

nope

#

i did the git remote, then git fetch, and then tried the cherry-pick command and it didnt work

jovial heath Mar 22, 2024, 1:12 AM

#

Hmm I can think of things to try from your end, but it's probably simplest if when I boot my PC tomorrow I remove the other commits from the PR

fervent tusk Mar 22, 2024, 4:35 PM

#

do you know if there's a way i could make it something like this where you can show the solution in a collapsible print?

fervent tusk Mar 22, 2024, 5:09 PM

#

gonna see if i can modify positions you cant access into another board overlay instead of having to use 3 different variables to determine it (gen_cars, stalled_cars, crashed_decoys)

#

makes things way simpler, might still have to keep gen_cars but itd remove the need for stalled and crashed cuz i can easily put them into one variable that doesnt need to be iterated over or "added" to (just changed)

jovial heath Mar 22, 2024, 5:43 PM

#

fervent tusk do you know if there's a way i could make it something like this where you can s...

Not easily, essentially instead of just printing stuff, you'd need to create an interface which you interact with at runtime. It would be easier to do as a web site than to do in the terminal, but even that might be a bit much

#

What you could perhaps do is to dump extra info to a file (say level_{level_name}_solution_{spare_tracks + spare_semaphores}.out), and print the path to that file?

fervent tusk Mar 22, 2024, 8:43 PM

#

eh thats writing to a bunch of files when unnecessary

#

what i mean is having something be collapsible would be convenient because it doesnt load the output with text that you might not care for but if you want to see it then it can show it

fervent tusk Mar 22, 2024, 10:54 PM

#

actually the file would be smart for the big levels because even if pycharm crashes i get the solution if there ever was one

#

nvm

fervent tusk Mar 25, 2024, 9:55 PM

#

fervent tusk gonna see if i can modify positions you cant access into another board overlay i...

just realized that this isnt really worth it because theres a reason i had crashed decoys and stalled cars in 2 different lists.

#

stalled cars gets reset every game movement but crashed decoys dont

#

which doesnt really work when you combine them into 1 list

#

im gonna look for other optimizations in the program, the heatmap thing helped so much which im really happy about though

#

i also finally merged the tail optimization

fervent tusk Mar 30, 2024, 4:30 PM

#

going over a little bit of the program for fun, just testing various lines in the code i think might take time and making some improvements depending on what i find

#

ex. rn im changing cars that use unpacking to just doing every index because it was faster when i tested it

#

so instead of *car[:4] im now doing car[0], car[1], car[2], car[3] cuz its faster

jovial heath Mar 30, 2024, 4:43 PM

#

Huh, may be because of needing to call into numpy to unpack the array?

fervent tusk Mar 30, 2024, 4:43 PM

#

no this is the same for all lines that use *car[:4]

#

just changing all of them to that

#

its probably because im slicing the car and then unpacking it (or the other way around)

#

i remember doing something similar like this doing every index way earlier when i was doing the program too

jovial heath Mar 30, 2024, 4:45 PM

#

Yeah, but if car was a python list / tuple slicing should be cheap, but I believe car is a numpy.array

fervent tusk Mar 30, 2024, 4:45 PM

#

its a list

jovial heath Mar 30, 2024, 4:46 PM

#

Huh, it shouldn't be a noticeable performance impact then

fervent tusk Mar 30, 2024, 4:46 PM

#

i could probably change some of the variable types to be faster which ill do too depending whether list and np.array are faster to do things on and copy during frames

fervent tusk Mar 30, 2024, 4:46 PM

#

jovial heath Huh, it shouldn't be a noticeable performance impact then

still makes it faster nonetheless, fun to code on it

#

i remember when i was still making the program i used copy.deepcopy(list) to copy stuff and when i changed it to list(list) and np.array(array) it became so much faster lol

#

idk if theres a faster copying method i could use now though

jovial heath Mar 30, 2024, 4:48 PM

#

I would advise leaving choices of what sort of ordered collection to use until I'd seen whether the algorithm could be improved more, as you may find advantages in switching to something else entirely

#

Generally list[:] is fine for copying a list, but all of those other than deepcopy are shallow copies, so if anything there is mutable you need to be aware you're sharing a reference

#

I'd be tempted to use tuple unless mutability is advantageous

#

Then you don't need to copy

#

Micro-optimisations are fun and satisfying, but often make it harder to see where you can make bigger more important algorithmic optimisations

fervent tusk Mar 30, 2024, 4:56 PM

#

jovial heath Generally list[:] is fine for copying a list, but all of those other than deepco...

yeaaaa i figured that out the hard way

#

the shallow part

jovial heath Mar 30, 2024, 4:58 PM

#

My general preference is to use immutable data structures where possible because then you don't need to keep track of where might change them, and make copies everywhere, and they tend to be cheaper to construct when you need to make new ones

#

But that's also kinda part of a functional programming approach

fervent tusk Mar 30, 2024, 5:01 PM

#

i know tuples are faster and i kinda wanna use them

#

have to change a lot tho

jovial heath Mar 30, 2024, 5:02 PM

#

I might be tempted to recommend trying collections.namedtuple

fervent tusk Mar 30, 2024, 5:02 PM

#

the what

jovial heath Mar 30, 2024, 5:02 PM

#

Because having descriptive field names rather than just indices would make the code a lot clearer

#

It's part of the standard library

#

https://docs.python.org/3/library/collections.html#collections.namedtuple

Python documentation

collections — Container datatypes

Source code: Lib/collections/init.py This module implements specialized container datatypes providing alternatives to Python’s general purpose built-in containers, dict, list, set, and tuple.,,...

#

It's kind of a compromise between a dataclass and a tuple

#

Although they were introduced way earlier than dataclasses

#

You could possibly subclass it to add a method, but that might incur extra runtime costs

fervent tusk Mar 30, 2024, 5:06 PM

#

sounds complicated

jovial heath Mar 30, 2024, 5:08 PM

#

Just ignore that last message

#

But named tuples are pretty simple

graceful raven Apr 16, 2024, 5:36 PM

#

Are you going to make a YouTube video about the solver?

fervent tusk Apr 16, 2024, 6:09 PM

#

ive thought about it but itd take a ton of effort

#

the video would be 30+ minutes so a few months of editing and idk when id have the motivation to work on it that long

#

ive made about 1 minute of footage for it though

graceful raven Apr 17, 2024, 3:50 AM

#

How about a blog post with a description of how the solver works, and new clever solutions that it found?

fervent tusk Apr 17, 2024, 3:51 AM

#

where would i put a blog post?

#

also i feel like a blog wouldnt carry the true energy that i put into this

graceful raven Apr 25, 2024, 9:36 AM

#

A post on Medium would be nice.

jovial heath Apr 25, 2024, 10:11 AM

#

Foxtrot doesn't need to do a bunch of extra work just because you'll like to see the output. You could always go through and gather everything from this thread and present what you'd like them to publish

harsh cipher Apr 30, 2024, 6:43 AM

#

My intention wasn't to put any more work on Foxtrot. I just think that the work done here is so cool that more people should see it, and it's a waste that it's just Al and me who were able to find it among Discord threads. Foxtrot already put in months of their time to create a solver. Perhaps extra couple of days wouldn't make such a huge difference. But it's their choice of course and I won't complain whatever the decision is.

delicate nymph Jun 16, 2024, 12:45 PM

#

Hey, I just started playing this game and I'm really enjoying it. I'm trying to figure out how to solve it by writing code. Did you use brute force to solve it?

fervent tusk Jun 23, 2024, 2:58 AM

#

If you want to learn how I solved it I have the github page with the code here -> https://github.com/FoxtrotOnce/RailboundSolver

GitHub

GitHub - FoxtrotOnce/RailboundSolver: A solver for levels in Railbo...

A solver for levels in Railbound. Contribute to FoxtrotOnce/RailboundSolver development by creating an account on GitHub.

#

the method of solving uses recursive generation to solve the board

#

basically it looks at every car, generates all the possible tracks that car can place, then moves the car and does that over and over until it finds a solution that reaches the end without any failures

#

it uses a bunch of logic to shorten the branches like checking if cars will crash on the next frame, valid semaphore placement, valid switches, if placing a track will crash the car regardless so it doesnt place it, etc

#

its not fully finished technically but almost the entire game is solved

#

i think 3 or 4 levels havent been solved yet and i havent gotten commited to fixing the solver

delicate nymph Jul 30, 2024, 4:31 PM

#

fervent tusk If you want to learn how I solved it I have the github page with the code here -...

I done some work for the game loop, it a little slow but can accept. Now I try to solve it now xD

fervent tusk Jul 30, 2024, 4:33 PM

#

nice

#

i like the little gif showing the animation its cool

delicate nymph Jul 30, 2024, 4:34 PM

#

I draw it by hand pc_boop

delicate nymph Jul 31, 2024, 3:08 AM

#

I got deeped in polishing everything 😦 can't even get to the backtracking algorithm

fervent tusk Jul 31, 2024, 3:09 AM

#

it looks super clean

delicate nymph Jul 31, 2024, 4:47 AM

#

So, this is my first attempt. I precompute all the possibilities for the cell, then randomly pick a tile and update the possibilities of the neighbors. The idea comes from the Wave Collapse Algorithm. I think I'm just going to go with all combinations since the map is quite small, then run the cart simulation for all.

delicate nymph Jul 31, 2024, 10:18 AM

#

It's fun xD

tranquil sinew Jul 31, 2024, 10:24 AM

#

love the art on the rocks

delicate nymph Aug 11, 2024, 8:52 AM

#

I can solve all of level 1 now, but I'm stuck at level 1-13A. It takes too much time to check all the possibilities.

My current track list for placement looks like this:

tiles.append(curve_tile)
tiles.append(curve_tile.rotate(1))
tiles.append(curve_tile.rotate(2))
tiles.append(curve_tile.rotate(3))
tiles.append(straight_tile)
tiles.append(straight_tile.rotate(1))
tiles.append(t_turn_tile)
tiles.append(t_turn_tile.rotate(1))
tiles.append(t_turn_tile.rotate(2))
tiles.append(t_turn_tile.rotate(3))
tiles.append(t_turn_tile.flip())
tiles.append(t_turn_tile.flip().rotate(1))
tiles.append(t_turn_tile.flip().rotate(2))
tiles.append(t_turn_tile.flip().rotate(3))

This gives me 14 possible tracks. If I try to place 10 tiles, that results in ~14^10 possibilities. I think I can reduce this by removing the T-turn tile, leaving me with only 6 tracks to consider, which would be ~6^10 possibilities. This would make the problem 4000 times smaller. Then, I can add the T-turn back in when necessary.

fervent tusk Aug 11, 2024, 10:15 AM

#

i think the main issue is that your program generates 3-ways whenever it wants

#

usually on any given tile there are 3 tracks to place based on what direction its going

#

for example, if a car is going right it can only place a horizontal track, a turn going up, and a turn going down

#

by allowing it to generate 3-ways whenever it wants it stretches this amount to 9 which is why it takes forever

#

the way i solved this with my program is as follows:
a 3-way can only be generated if a car intersects with a track, OR if a car rides a track for the 2nd time

#

of course this brings looping solutions and many other problems but it greatly simplifies the process

#

the reason it works is because for a 3-way to be useful, it needs to be accessed from all 3 directions. if it isn't, theres no point in having a 3-way

#

when a car rides over a track it already gets accessed from 2 directions (entering and exiting), so intersecting the track or riding over it a 2nd time and then turning a horizontal/vertical into a 3-way guarantees the 3rd side gets used

#

on a side note, I really like how your program shows the real-time generation...
ive been wanting to make a visualizer for mine since i started it but i couldnt figure out where to start, and i wanted it to look like the real game but seeing yours makes me think it cant be too hard and it doesnt need to be realistic 😄

delicate nymph Aug 11, 2024, 1:58 PM

#

I'll definitely try that, thanks for your help pc_yipee

delicate nymph Aug 12, 2024, 7:00 AM

#

Yay, from forever to~12 seconds 😄

#

your tips is very useful pc_yipee

fervent tusk Aug 12, 2024, 3:38 PM

#

i just looked at pillow for the first time about generating images and it doesnt seem too difficult to use so i might start working on a visualizer for mine

fervent tusk Aug 13, 2024, 3:27 AM

#

how did you make the little preview window that shows the visualizer? im using pillows and it just downloads an image and shows me it, unlike the little window you have that shows it live

#

actually i just found a way to make a gif using the images, its not live but it works

delicate nymph Aug 13, 2024, 4:00 AM

#

Im using pillow to create image then use numpy to convert to right format and send to cv2 to render

fervent tusk Aug 13, 2024, 4:01 AM

#

cv2?

#

whats that

delicate nymph Aug 13, 2024, 4:01 AM

#

It some machine learning package i think https://opencv.org/get-started/

OpenCV

Get Started

Installation Select your preferences and run the install command. Operating System: Linux macOS Windows Building From Source: Yes No Language: Python C++ Java Android iOS JavaScript Run this Command: Default Result: pip3 install opencv-python Verification To ensure that OpenCV is installed correctly, we can run the following example to show how ...

fervent tusk Aug 13, 2024, 4:02 AM

#

ah

#

to me it just seems like another opener for images, i feel like i could just save the file and open it from explorer using Image.show() instead of having cv make an extra window for it

#

i suppose it would actually show the image in real time though rather than having to wait for the program to finish

#

so i see the purpose now

#

regardless, how did you make it show the animation? did you just send it images of every frame

delicate nymph Aug 13, 2024, 4:06 AM

#

Yeah, after some iteration, or if a solution founded i send it to the window

fervent tusk Aug 13, 2024, 4:06 AM

#

i see

delicate nymph Aug 13, 2024, 4:07 AM

#

Rendering every frame can slow things down, so setting an interval should be good enough.

fervent tusk Aug 13, 2024, 4:07 AM

#

yeah

#

for the tiles im thinking of turning all the track images into arrays and then splicing the data together to make an image, is that what youre doing?

#

im not sure how im going to overlay a car onto it though

delicate nymph Aug 13, 2024, 4:09 AM

#

https://github.com/Th1nhNg0/railbound-solver

GitHub

GitHub - Th1nhNg0/railbound-solver: A Python-based puzzle solver fo...

A Python-based puzzle solver for Railbound, the track-bending puzzle game. Features a graphical editor and automated solving algorithm. - Th1nhNg0/railbound-solver

#

You can check my source code here

#

Im using class so it may simpler

#

Im mapping the predefine class to the 2d grid

#

So at first I tried to make the solver in JavaScript so it could run in a browser, but doing it in Python might be easier. My goal is to be able to run the visualization live on a browser, but for now I'm working on the algorithm in Python first so I can translate it easily later.

fervent tusk Aug 13, 2024, 4:10 AM

#

ah

#

i know nothing about interfaces

#

i already have a basically complete solver and you wanna make an interface for it so i mean

#

i think itd be cool if mine had an interface with the capabilities that youre mentioning like people being able to edit it and stuff and make custom ones

#

because mine can technically do that but theres no interface and idk how to do that yet

#

the problem is though youre making your own version of the code and for me to help you complete it i'd have to give you ALL of the info i used for mine to make it faster because i doubt youll manage to make it faster that mine (maybe you can? idk yet your program is still in the beginning stage at world 1)

#

and if i gave you mine youd have to learn how it works and change some of it which could mess it up to make it possible to work with an interface

#

but if any of that worked id be willing to work with you to make my solver have an interface that sounds super nice

delicate nymph Aug 13, 2024, 4:19 AM

#

That's cool, my solver isn't getting out of level 1 yet. Since I want to visualize it, I have to break everything down into smaller functions and make sure that when I add something new, nothing breaks. So I need OOP almost everywhere. I'm still working on the structure of this. So have a help maybe make it faster pc_yipee

fervent tusk Aug 13, 2024, 4:21 AM

#

your program uses oop but mine doesnt 🤔

#

thatd be annoying to convert between

fervent tusk Aug 13, 2024, 4:21 AM

#

fervent tusk but if any of that worked id be willing to work with you to make my solver have ...

anyways, thats my proposal.

delicate nymph Aug 13, 2024, 4:21 AM

#

The oop is good for visual

#

But the algorithm may not need it

#

The class object may reduce the time to process, the simpler numpy or list is good

fervent tusk Aug 13, 2024, 4:25 AM

#

do you want to:
help me make an interface
get my advice to make yours better
or we both code our own? i think i could probably still figure out how to make an interface after some time

#

if i made my own interface id have to learn how using multiple languages together works and also learn javascript and html more to make a functional website but that sounds kinda fun

delicate nymph Aug 13, 2024, 4:27 AM

#

Sure, working together will improve our code quality. But I think I will first read your code to check if my idea is close to yours. If it matches, then we can work on the same source code. But if the algorithm is different, I can only help you with the interface.

fervent tusk Aug 13, 2024, 4:28 AM

#

alright

#

But if the algorithm is different
not sure what you mean here

#

i think my algorithm is already fully completed because my program can solve (almost) all of the levels in the game, im just looking for an interface so...

delicate nymph Aug 13, 2024, 4:32 AM

#

My algorithm uses backtracking to find the solution.
At each iteration, I simulate the cart movement, and if any cart goes to an empty tile, I add that position to a list. Then I generate all the possible tiles that can be placed on these positions and continue the iteration until all carts reach their destinations. So there are going to be two loops, one for looping through all the grid states and one for simulating the cart on that grid.

fervent tusk Aug 13, 2024, 4:33 AM

#

yours is the exact same as mine (i think?)

#

i just call it recursive generation though

delicate nymph Aug 13, 2024, 4:34 AM

#

So I don't need to make my own algorithm. We can just refactor some code and add an interface. pc_yipee

fervent tusk Aug 13, 2024, 4:34 AM

#

yup

#

the only issue is my program is 600-700 lines, and the complexity comes from all the different mechanics

#

so it would be a field day trying to explain how it works lol but i think you would have to learn regardless, because every mechanic needs to be covered

#

Alistair managed to figure out how some of my code works so i cant imagine its that difficult... it might be a bit messy though

#

i think itd be better to start with mine as a base instead of creating a new project and using mine as reference though, i can try to help you convert it to oop

delicate nymph Aug 13, 2024, 4:40 AM

#

Sure, so to get started, I may need you to provide steps in your flow, like in one grid state, what you check first, cart crash cart goes through the tunnel....

fervent tusk Aug 13, 2024, 4:42 AM

#

these are all the parameters i use every "frame"

delicate nymph Aug 13, 2024, 4:43 AM

#

I already have the map editor, so we can use it to create some maps to debug. Since your base code is working well, I may set up some test cases to automatically test our work when something changes so it doesn't break.

#

And one more thing is what repo should we work on

fervent tusk Aug 13, 2024, 4:44 AM

#

im kinda new to github and "professional coding" so bear with me if i dont know anything lol

#

wdym by repo

fervent tusk Aug 13, 2024, 4:45 AM

#

delicate nymph I already have the map editor, so we can use it to create some maps to debug. Si...

also concerning your map editor i already made some track art for when it gets finished, i can make it for everything so it looks as much like the game as possible

#

oh i see are you asking whether we should work on my project or yours on github

delicate nymph Aug 13, 2024, 4:46 AM

#

The repository on github

fervent tusk Aug 13, 2024, 4:46 AM

#

ah

#

probably mine then if we're using it as a base

delicate nymph Aug 13, 2024, 4:46 AM

#

By the way, I don't know if our work is going to violate any terms of service of the game. Maybe we need an admin to authorize it first? XD

fervent tusk Aug 13, 2024, 4:47 AM

#

luke has seen my project since the very beginning im sure hes fine with it lol

#

he should see this new development too so if he needs us to stop thats fine

#

hes keeping in touch

delicate nymph Aug 13, 2024, 4:48 AM

#

Okay, can you add me to your repository. Here is my link: https://github.com/Th1nhNg0

GitHub

Th1nhNg0 - Overview

Hello :D. Th1nhNg0 has 27 repositories available. Follow their code on GitHub.

fervent tusk Aug 13, 2024, 4:48 AM

#

how do i add you to my repository?

delicate nymph Aug 13, 2024, 4:49 AM

#

In the setting, collaborators

#

I guess that's all for now, I gotta go now so I'll be back with a plan pc_yipee

fervent tusk Aug 13, 2024, 4:50 AM

#

alright

#

i added you

fervent tusk Aug 13, 2024, 4:50 AM

#

fervent tusk these are all the parameters i use every "frame"

i believe i never explained how my generation works so:

delicate nymph Aug 13, 2024, 4:51 AM

#

You can write a short doc, im gonna read it later

fervent tusk Aug 13, 2024, 4:51 AM

#

its currently 11:49pm for me lol

#

i think we're on opposite sides of the globe

delicate nymph Aug 13, 2024, 4:51 AM

#

Haha😂

fervent tusk Aug 13, 2024, 4:51 AM

#

are you gmt+7?

delicate nymph Aug 13, 2024, 4:51 AM

#

It 11:51 am for me

#

Yea

fervent tusk Aug 13, 2024, 4:51 AM

#

oh wow

#

ok yeah

#

i can start explaining my entire code thing in depth in a doc

#

i can maybe pump it out tomorrow but it might be a little while

delicate nymph Aug 13, 2024, 4:52 AM

#

Sure, see ya later

fervent tusk Aug 13, 2024, 4:52 AM

#

ib_bye

#

even though youre gonna be working on the interface im gonna start on adding some code for mine too because i kinda wanna learn more about how pillow works and i already fully understand my code so i can start on it

#

Railbound Solver [Python Script] COMPLETE! Working on Interface...

fervent tusk Aug 13, 2024, 6:35 AM

#

oh and by the way before i start on the doc heres a basic explanation if you didnt see it

delicate nymph Aug 13, 2024, 7:34 AM

#

I've created a new branch for refactoring. The plan is to reorganize the project structure and add new features:

Code Reorganization:
- Move existing code to an algo folder
- Create images and editor folders
Editor Modifications:
- Update the editor to ensure level data compatibility with the algorithm
- Add more tile to it, the editor only have tile on level 1

Level Structure:

Implement a new levels folder with the following structure:

levels/
├── 1/
│   ├── 1-1.json
│   ├── 1-2.json
│   ├── 1-11A.json
│   └── ...
├── 2/
├── 3/
├── 4/
└── ...

Testing:
- Add a test folder for automated algorithm testing
- Ensure new features and changes don't break existing functionality
Visualization:
- Create a visual folder for basic visualization code

fervent tusk Aug 13, 2024, 7:59 AM

#

finally finished my visualizer

#

it only works for world 1 levels right now and it doesnt show cars but this is 1-11B

#

the gif plays a bit slower than it actually solved it idrk how to make it more accurate and its 3am so i should probably go to bed

delicate nymph Aug 13, 2024, 8:00 AM

#

bravo, remember to push your code to github so i can follow pc_yipee

fervent tusk Aug 13, 2024, 8:00 AM

#

should be up now

#

have fun

delicate nymph Aug 13, 2024, 8:50 AM

#

I have push the refactor code. Is you happy with it you can merge it to the main

delicate nymph Aug 13, 2024, 11:20 AM

#

delicate nymph Aug 13, 2024, 12:28 PM

#

the editor only work for level 1 for now.
I think i gonna setup some basic automation test.
Can you make the algorithm as a function like:

from algo import solve

level_data = ....
result = solve(level_data, return_multiple_solutions=False)

fervent tusk Aug 13, 2024, 3:12 PM

#

delicate nymph

on the level select menu for the editor i think itd be nicer if all the levels were ordered correctly

fervent tusk Aug 13, 2024, 3:16 PM

#

delicate nymph the editor only work for level 1 for now. I think i gonna setup some basic autom...

im not really sure what you mean by this, but the "level_data" for every level in the game is stored in levels_cars so you can just fetch it from there if you havent been

#

and the result would be a variable called bestBoard thats used at the very end of the program after the first generation function is called

#

you should understand more of it once i make the doc

fervent tusk Aug 13, 2024, 3:40 PM

#

ill just leave some comments on the commits

fervent tusk Aug 13, 2024, 5:02 PM

#

heres the program solving 1-13A in real time lol

#

last frame with solution didnt show up because i had to speed it up by 967500%

#

its super neat how fast it can do calculations

#

watching how it solves is also helpful because i can figure out what to add to generation to make it faster

#

the program doesnt seem to connect to the train very often, so if i could somehow make a rule that it must connect to the train im sure that would speed the program up a lot

fervent tusk Aug 13, 2024, 7:15 PM

#

here is the doc explaining the code, i hope its formatted well for you to read
https://docs.google.com/document/d/1ZBsVyqjR1_9rYbyv-k1ANv-jgJNqy2Pt1q3K6jeQy4U/edit?usp=sharing

Google Docs

Foxtrot's Guide to Railbound Solving

NOTES BEFORE READING In numpy arrays, grid data would be accessed as array[y, x] because the “y” arrays come first. Whenever vectors or positions are mentioned in the code they are formatted as (x, y) which may cause confusion, Because the position is swapped to access the board array. If a car w...

#

im slowly working on it

#

lmk if you need any further explanation

#

the comments inside the main generation should provide basic information on how it all works but i can go further in depth if you ask me to

fervent tusk Aug 13, 2024, 10:22 PM

#

added more sprites

#

gonna add cars and interaction stuff next

#

down and up tunnels are swapped oops

fervent tusk Aug 13, 2024, 10:47 PM

#

if we can figure out how to add a palette that'd be super nice too

#

heres the cars and i changed the fence to be flat

#

seeing numbers above 4 is kinda cursed

#

delicate nymph Aug 14, 2024, 2:28 AM

#

How many tile there are, in the levels i see a tile with id 20

fervent tusk Aug 14, 2024, 2:28 AM

#

look at reference.py

#

it lists all the tile indices and interaction indices

delicate nymph Aug 14, 2024, 2:34 AM

#

Look good

#

I already have a images folder

#

Check the uppercase letter

fervent tusk Aug 14, 2024, 2:35 AM

#

when i tried to push the project with the new folders onto my pycharm some of the data didnt for some reason and that images folder was one of them

#

yesh

#

i didnt know until i uploaded it

delicate nymph Aug 14, 2024, 2:36 AM

#

Use git

#

You pull then push :v

fervent tusk Aug 14, 2024, 2:36 AM

#

apologies

delicate nymph Aug 14, 2024, 2:37 AM

#

Btw you can use this helper to calc the time so you can know what part take most time

#

class TimingManager:
    def __init__(self, enabled=True):
        self.execution_times = defaultdict(list)
        self.current_operations = []
        self.enabled = enabled

    @contextmanager
    def measure_time(self, operation_name):
        if not self.enabled:
            yield
            return

        full_operation_name = "/".join(self.current_operations +
                                       [operation_name])
        self.current_operations.append(operation_name)
        start_time = time.perf_counter()
        try:
            yield
        finally:
            if self.enabled:
                end_time = time.perf_counter()
                self.execution_times[full_operation_name].append(
                    end_time - start_time)
                self.current_operations.pop()

    def print_averages(self):
        if not self.enabled:
            return

        print('\n' + '=' * 80)
        print("{:^80}".format("Average Execution Times"))
        print('=' * 80)
        print("{:<50} {:>15} {:>15}".format(
            "Operation", "Avg Time (s)", "Total Time (s)"))
        print('-' * 80)

        for operation, times in sorted(self.execution_times.items()):
            avg_time = mean(times)
            total_time = sum(times)
            indent = "  " * (operation.count("/"))
            operation_name = operation.split('/')[-1]
            print("{:<50} {:>15.6f} {:>15.6f}".format(
                f"{indent}{operation_name}", avg_time, total_time))

        print('=' * 80 + '\n')

    def enable(self):
        self.enabled = True

    def disable(self):
        self.enabled = False

    def reset(self):
        self.execution_times = defaultdict(list)

fervent tusk Aug 14, 2024, 2:38 AM

#

i already used the built in thing to look at process time

#

i did that a long time ago

delicate nymph Aug 14, 2024, 2:38 AM

#

Here a example how to use it:

import time
from collections import defaultdict
from contextlib import contextmanager
from statistics import mean

# Assuming the TimingManager class is defined here

# Create an instance of TimingManager
timing_manager = TimingManager()

# Function to simulate some work
def simulate_work(duration):
    time.sleep(duration)

# Example usage of TimingManager to measure time of different operations
def perform_operations():
    with timing_manager.measure_time("Operation A"):
        simulate_work(1)  # Simulate work for 1 second
    
    with timing_manager.measure_time("Operation B"):
        simulate_work(2)  # Simulate work for 2 seconds
        
        with timing_manager.measure_time("Operation B/Sub-operation B1"):
            simulate_work(0.5)  # Simulate work for 0.5 seconds

    with timing_manager.measure_time("Operation C"):
        simulate_work(1.5)  # Simulate work for 1.5 seconds

# Perform the operations
perform_operations()

# Print the average execution times
timing_manager.print_averages()

#

Nice

#

I'm gonna finish the editor soon then go to the visual

fervent tusk Aug 14, 2024, 2:39 AM

#

Ok

#

when i tried running the editor on mine it didnt work fsr

delicate nymph Aug 14, 2024, 2:41 AM

#

I'm on macOS, so maybe I need to check for other OS too

fervent tusk Aug 14, 2024, 2:41 AM

#

im using windows

#

whats the end plan for the interface?

#

do you want to make a website with nice ui where you can edit and solve a board, an executable, just the window, or what?

delicate nymph Aug 14, 2024, 2:48 AM

#

For now maybe stick to python

#

To make the web, we must convert all the code to javascript or typescript

fervent tusk Aug 14, 2024, 2:49 AM

#

all????

#

surely theres some other way you can use python for the backend

delicate nymph Aug 14, 2024, 2:49 AM

#

But with the web I can make the UI faster and more beautiful, the UI in python are hard

fervent tusk Aug 14, 2024, 2:50 AM

#

converting to javascript would be hell and im not sure how fast it runs compared to python

delicate nymph Aug 14, 2024, 2:50 AM

#

We can keep the algo in python but then we must setup a backend server thing to communicate between backend and frontend

fervent tusk Aug 14, 2024, 2:51 AM

#

thats fine

#

not sure how using servers works but i hope its not horrible

delicate nymph Aug 14, 2024, 2:54 AM

#

delicate nymph the editor only work for level 1 for now. I think i gonna setup some basic autom...

It's like the function i mention early

#

We must made every as a function so it take input and return output

#

Input may come from the frontend then the server send the output back

fervent tusk Aug 14, 2024, 2:54 AM

#

hm

#

for the level_data part my generation function currently sends 12 different parameters that originate from levels_cars (the data for every level) so thats possible

#

but my generation function doesn't "return" a solution and that might be problematic

#

the generation function yields itself at the end to generate new combinations

delicate nymph Aug 14, 2024, 2:58 AM

#

I can convert it to a simple queue is it too conplex

fervent tusk Aug 14, 2024, 2:58 AM

#

idk how yield works compared to return

delicate nymph Aug 14, 2024, 3:03 AM

#

I think we should use queue so it more simpler

fervent tusk Aug 14, 2024, 3:03 AM

#

elaborate

delicate nymph Aug 14, 2024, 3:05 AM

#

So instead of yield for a new state, we create a tuple of param then push to a queue

fervent tusk Aug 14, 2024, 3:06 AM

#

when would the queue get called

#

to be generated again

delicate nymph Aug 14, 2024, 3:08 AM

#

Here is an example

# Approach 1: Using deque for DFS

from collections import deque

def dfs_with_deque(graph, start):
    stack = deque([start])
    visited = set()

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            print(f"Visiting node: {vertex}")
            visited.add(vertex)
            stack.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)

# Approach 2: Using tail call optimization for DFS

import functools
import typing

def tail_call_gen(func: typing.Callable[[...], typing.Generator]):
    @functools.wraps(func)
    def facilitator(*args):
        argslist = [args]
        while argslist:
            args = [*func(*argslist.pop())]
            argslist.extend(reversed(args))
    return facilitator

@tail_call_gen
def dfs_with_tail_call(graph, node, visited=None):
    if visited is None:
        visited = set()
    
    if node not in visited:
        print(f"Visiting node: {node}")
        visited.add(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                yield graph, neighbor, visited
    
    yield  # This empty yield is necessary to make it a generator function

# Example graph for testing
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("DFS using deque:")
dfs_with_deque(graph, 'A')

print("\nDFS using tail call optimization:")
dfs_with_tail_call(graph, 'A')

fervent tusk Aug 14, 2024, 3:09 AM

#

ah my program uses tail call optimization

delicate nymph Aug 14, 2024, 3:11 AM

#

With the queue, we will have more control over it

fervent tusk Aug 14, 2024, 3:12 AM

#

i dont fully understand what you mean but if you can add it that works

#

sorry im not that great at coding lol

delicate nymph Aug 14, 2024, 3:12 AM

#

It's okay

#

So now we agree to use web frontend and backend for this project right?

fervent tusk Aug 14, 2024, 3:14 AM

#

yeah

#

if python is backend i suppose

#

unless youre super good at converting python to javascript

delicate nymph Aug 14, 2024, 3:15 AM

#

So I will try to convert your algorithm to the queue things first then get back to the editor

fervent tusk Aug 14, 2024, 3:15 AM

#

alright

#

let me know if you need help understanding anything

delicate nymph Aug 14, 2024, 3:15 AM

#

Sure

fervent tusk Aug 14, 2024, 3:54 AM

#

i made it so the cars appear during generation and since it has the new tunnel sprites i ran the visualizer on the longest level to generate in world 2 (2-3B)

#

still looks super cool

#

i love watching the program on a video like this its so cool

#

once i add interaction sprites i wanna try running it on a longer world 5 level i feel like thatd be fun to watch

#

a world 7 level would also look pretty funny

delicate nymph Aug 14, 2024, 4:20 AM

#

fervent tusk i made it so the cars appear during generation and since it has the new tunnel s...

Wait until I set up the website. I am very confident in my web development skills pc_yipee

fervent tusk Aug 14, 2024, 4:21 AM

#

Yeah i know youll do a super good job

#

Im just trying to make my own so i can learn more about pillow and so i can see the program solve right now

#

its just a basic version were not gonna use it for the final product

delicate nymph Aug 14, 2024, 4:22 AM

#

It easy to debug when you know what is happening in the code xD

fervent tusk Aug 14, 2024, 4:22 AM

#

its easy to debug when you look at the same 700 lines for 7 months pc_tired

delicate nymph Aug 14, 2024, 4:29 AM

#

pc_gasp pc_gasp pc_gasp

#

It easier now pc_yipee

delicate nymph Aug 14, 2024, 8:05 AM

#

it hard than I imagine ps_sweat

#

I think we should apply OOP and do refactor the algorithm

#

I see you use cars_to_use=list(cars + decoys + ncars) but later in the generate_tracks function you use the variable cars, decoys and ncars again. Then the cars_to_use is duplicate and pass many reference or variable may confuse and slow the program

#

and inside a function it shouldn't use the variables outside it. 2 to 3 global variables and constant variables is ok, but you reference too many variables outside it

#

This is the step in the generate tracks right?:

Initial Setup
- Process any crashed decoy cars
- Handle switch interactions and gate operations
- Update heatmaps for car positions
Car Generation Loop
- For each car:
  - Handle special cases (stations, gates, tunnels)
  - Determine possible tracks to place
  - Check for crashes and solve conditions
  - Generate possible new positions for the car
Track Combination Generation
- Create all possible combinations of generated car positions and tracks
Branch Creation and Recursion
- For each combination:
  - Update the board state
  - Check for solution conditions
  - Recursively call generate_tracks with the new state
Solution Checking and Updating
- If a solution is found, update the best solution if it's better than the current best
Termination
- End when all combinations have been explored or a perfect solution is found

#

so i recommended create 3 class:

Grid: hold the 2d array list of the map. number of track have been place... hold some function that made the map change like: gates, place tile, change tile...
Tile: hold the data of a tile like: semaphorePass,directions ... and function to check if 2 tile can connect, etc...
Cart: hold position and direction of the cart. is the cart crash, type of the cart, the order of the cart... and function to move it,

#

I already made some of it but my algorithm is not good at you. so maybe we start from this and migrate your algorithm to OOP?
https://github.com/Th1nhNg0/railbound-solver/blob/master/src/solve.py

#

If you could adapt your algorithm into a single function that takes an input and returns all the frames or the complete solution, that would be preferable for me. While I'm more comfortable with object-oriented programming, a functional approach like this would work well too.

jovial heath Aug 14, 2024, 9:12 AM

#

I definitely agree that encapsulating all the state into a few classes is a good approach - I know when I was giving input earlier this year I was wary of changing too much so it was still Foxtrot's project, and I didn't want to overwhelm them - happy to contribute more too if larger changes are welcome, and I can probably help a bit with desktop UI

#

As for OO versus functional, my temptation would be to learn towards functional with something this algorithmic, and have the state set up so methods return a new object rather than mutating the existing one, because then immutable data can have shared references, rather than copying all the state any time you want to branch. That way we could potentially move towards branches running in parallel without having to worry about side effects

delicate nymph Aug 14, 2024, 9:21 AM

#

I don't know if we should refactor Foxtrot's code or create new code using Foxtrot's idea.

jovial heath Aug 14, 2024, 9:22 AM

#

I feel like either works. I guess if we create a new version we could have a converter spit out the same data format for a level, and use the data generated by Foxtrot's version for a test suite

#

That way we can at least tell we're getting the right output

delicate nymph Aug 14, 2024, 9:28 AM

#

That mean i will continue my work xD

#

I just want collaboration, working alone may not be fun.

fervent tusk Aug 14, 2024, 1:31 PM

#

delicate nymph I see you use `cars_to_use=list(cars + decoys + ncars)` but later in the `genera...

cars decoys and ncars arent even global variables im pretty sure the reason i used them is because i can check the starting position of the cars and the amount of cars in that type

#

the steps is correct

fervent tusk Aug 14, 2024, 1:38 PM

#

delicate nymph If you could adapt your algorithm into a single function that takes an input and...

if it were possible to add a return after the yield statement that would return bestBoard? thatd work because itd only be run once the first yield is finished, meaning the generation is finished

fervent tusk Aug 14, 2024, 2:04 PM

#

jovial heath I definitely agree that encapsulating all the state into a few classes is a good...

can you further explain this? i have a vague understanding of classes and oop but if it makes my code more organized i may change it

#

by how thinh describes it it just seems like a capsule to put variables in

delicate nymph Aug 14, 2024, 2:23 PM

#

fervent tusk if it were possible to add a return after the yield statement that would return ...

You can yield the solution instead of return so the code not gonna change much but the problem if i dont know is anything gonna break if we change the flow @@

fervent tusk Aug 14, 2024, 2:24 PM

#

uhh yielding something other than the function would break it id think

#

i can just try adding a return after and seeing if it works i looked up yields and it can maybe run the code following it(?)

delicate nymph Aug 14, 2024, 2:25 PM

#

Yield "123" is return the result
You can use yield from create_tracks(... to make it like recursive callback

fervent tusk Aug 14, 2024, 2:26 PM

#

actually

#

couldnt i just make a new function that sets a variable bestBoard, gives the generate_tracks function the level_data, runs generate_tracks fully, and then the function returns bestBoard?

#

its not exactly organized or fancy but its simple

delicate nymph Aug 14, 2024, 2:28 PM

#

Yea

fervent tusk Aug 14, 2024, 2:29 PM

#

Then your preference is met

jovial heath Aug 14, 2024, 3:03 PM

#

So what I would do is to have a State class which holds a Grid object, and the number of each type of piece still to be placed. A function could then take an initial State object, and call a method on it which yields or returns all the State objects that result from placing one piece according to your existing algorithm, and as @delicate nymph suggests, shove the results in a deque. Then create a process pool with as many workers as there are CPU cores, and until the queue is empty and all the workers have finished, get the workers to call our function on that State object, and get all the next versions of the State from them. You might, when creating the Grid objects, want to check if they're a solution, and then when you get back to the main process you can store the solved State objects in a list.

If you make your Grid objects hashable then you can put all the Grid objects in a set in the main thread when you submit them to the worker pool. That way you can avoid resubmitting any that are identical to a Grid you've already processed

#

The Grid should probably have a dict keyed by a tuple of the coordinates and the value would be a Tile, as well as the Cart object

#

Or the Cart object could be on the State

#

That way if you don't place any tiles on a move then the next State object can get a reference to the existing Grid object without having to create a new one, because you're already going to need to create a new State

#

The function can probably be a method on State, but you need to avoid mutations, and only ever yield/return new State objects, so you don't have to worry about things like atomic operations etc

#

I probably wouldn't do the ProcessPool stuff until we know we're generating good solutions, etc because parallelism is a bugger to debug

#

You could instead of a single deque have a dict of deques keyed by the number of pieces left to place, and always prefer to submit State objects with the maximum number of spare pieces left. Then when you get a solution, stop submitting any State objects with fewer remaining pieces, and therefore you should only ever get the shortest solutions, and possibly any that place one extra piece, but obviously that depends whether you're interested in seeing the shortest solutions, or all solutions

#

If you're not running things in parallel you'd be guaranteed only to generate the shortest solutions

#

That's an optimisation I wouldn't add though until a few of the shorter levels with each feature in are generating all the right solutions

#

Because again: it adds complication, which makes things harder to debug

fervent tusk Aug 14, 2024, 3:32 PM

#

can you link some articles so i understand what youre saying

delicate nymph Aug 14, 2024, 3:34 PM

#

jovial heath I probably wouldn't do the ProcessPool stuff until we know we're generating good...

I was trying doing that before but it become a mess and everything broken pc_tired

jovial heath Aug 14, 2024, 3:39 PM

#

fervent tusk can you link some articles so i understand what youre saying

Which bits?

fervent tusk Aug 14, 2024, 3:39 PM

#

all of it

#

pc_tired

jovial heath Aug 14, 2024, 3:39 PM

#

Heh

#

So a ProcessPool has just been multiprocessing.Pool since early python 3, woops

#

But don't worry about that for now

#

All the complicated bits are things we can do later if we adopt a structure designed to accommodate them

delicate nymph Aug 14, 2024, 3:43 PM

#

I think I'm gonna write a blog post for this problem

fervent tusk Aug 14, 2024, 3:45 PM

#

im gonna read up on classes and oop on w3schools and see if i can or should change anything

#

al is most of what you said for making the program organized, making it faster, or making it more compatible with thinh's needs

jovial heath Aug 14, 2024, 3:46 PM

#

Maybe avoid w3schools

#

They're notoriously bad

fervent tusk Aug 14, 2024, 3:46 PM

#

?

#

i use it to learn the basics for most languages including python

#

i havent found a good equivalent, but geeksforgeeks gives good advice for more specific stuff

jovial heath Aug 14, 2024, 3:48 PM

#

https://docs.python.org/3/tutorial/classes.html is decent and accurate

Python documentation

9. Classes

Classes provide a means of bundling data and functionality together. Creating a new class creates a new type of object, allowing new instances of that type to be made. Each class instance can have ...

#

The problem is that w3schools is frequently inaccurate or out of date, which can lead to a lot of frustration

#

Like, for web stuff I recommend Mozilla, for python stuff the official docs are pretty good

delicate nymph Aug 14, 2024, 3:49 PM

#

btw we should choose a python version to work with

#

the new version is very not stable xD

jovial heath Aug 14, 2024, 3:51 PM

#

I think the last time I ran it I was using 3.11

fervent tusk Aug 14, 2024, 3:52 PM

#

fervent tusk al is most of what you said for making the program organized, making it faster, ...

al pc_points

jovial heath Aug 14, 2024, 3:52 PM

#

jovial heath There's plenty in that codebase which would be cleaned up using classes: https:/...

Looks like I recommended this as a more beginner-friendly tutorial

jovial heath Aug 14, 2024, 3:53 PM

#

fervent tusk al <:pc_points:1243206541943767081>

Yes?

#

Primarily to make it more organised

#

But by doing so, we can make it easier to achieve the other two

fervent tusk Aug 14, 2024, 3:54 PM

#

i see

fervent tusk Aug 14, 2024, 4:19 PM

#

i think i have the basics down now but what you said is still super confusing

jovial heath Aug 14, 2024, 4:21 PM

#

Is it the part about State being hashable?

#

Or all the optimisations?

#

Or something more fundamental?

fervent tusk Aug 14, 2024, 4:22 PM

#

no i think the only part i understand is the first sentence

#

im gonna try to figure out what deques and tail call optimizations are and what every line means

jovial heath Aug 14, 2024, 4:24 PM

#

Tail call optimisation is the thing where you were recursing really deep and that was causing performance problems and crashes, so instead of recursing we return what to do next, and do that from the caller

delicate nymph Aug 14, 2024, 4:25 PM

#

I think you should learn about DFS and BFS first

jovial heath Aug 14, 2024, 4:25 PM

#

Deques are Double Ended Queues, where you can add to either end just as easily, or pop from either end just as easily

delicate nymph Aug 14, 2024, 4:25 PM

#

BTW I'm writing the blog how I solve the level 1 now, so maybe when i published it may easy to understand what I mean

fervent tusk Aug 14, 2024, 4:26 PM

#

jovial heath Tail call optimisation is the thing where you were recursing *really* deep and t...

it still crashes on 3 levels i thought that was supposed to fix it running out of memory

jovial heath Aug 14, 2024, 4:26 PM

#

To be fair we don't really need a deque, any old queue should work, but deques are built in so we may as well

delicate nymph Aug 14, 2024, 4:27 PM

#

jovial heath To be fair we don't really need a deque, any old queue should work, but deques a...

deque is a linked list so you can switch between DFS and BFS with no cost and change in code

jovial heath Aug 14, 2024, 4:27 PM

#

fervent tusk it still crashes on 3 levels i thought that was supposed to fix it running out o...

Are you able to post the output from where it crashes?

jovial heath Aug 14, 2024, 4:28 PM

#

delicate nymph deque is a linked list so you can switch between DFS and BFS with no cost and ch...

Sure, it's just that in our use case we're not using that

fervent tusk Aug 14, 2024, 4:28 PM

#

no, the last time i ran all 3 i ran them for 2 days and then when i checked my pc pycharm just closed

delicate nymph Aug 14, 2024, 4:28 PM

#

when I run the first level, some level solve faster when using BFS and some faster when go with DFS

fervent tusk Aug 14, 2024, 4:28 PM

#

when i checked task manager with a running pycharm it always had pycharm and like 3 or 4 other processes under it and python was one of them

#

when i checked task manager after pycharm crashed and closed python would still be there though despite pycharm having "closed"

jovial heath Aug 14, 2024, 4:29 PM

#

Hmm

fervent tusk Aug 14, 2024, 4:29 PM

#

so i presume python is still running the program after pycharm crashes but its useless because i wouldnt be able to see the result

jovial heath Aug 14, 2024, 4:30 PM

#

Yeah, I don't know what's going on there

#

It would help to be logging to a file as well as the terminal, as then you can see whether the file still grows

#

You could also try running outside of pycharm

#

IDK why pycharm would be crashing, whether it's trying to keep the terminal output in memory or something

#

But what I suspect is that you're hitting some sort of infinite loop

#

But with the code in the current structure it's hard to tell, and even harder to prevent

#

Whereas if your State is hashable you can avoid repeating work

#

You'd need to make sure the hash accurately reflects whether two State objects are equal though

#

Which means making Grid hashable, by making Tile Hashable, etc

fervent tusk Aug 14, 2024, 4:36 PM

#

you lost me at hashable im looking up the term

#

doesnt it mean something that you can iterate over?

delicate nymph Aug 14, 2024, 4:36 PM

#

for simple, you make a set then add a string to it

#

if the string already in the set that mean you already process that state so skip it

fervent tusk Aug 14, 2024, 4:49 PM

#

so are you trying to say that if there were a queue of generations to run, every time you ran one youd add it to a list and then check before every generation if it's already been generated (there's a copy in the list)?

jovial heath Aug 14, 2024, 4:50 PM

#

Basically

fervent tusk Aug 14, 2024, 4:51 PM

#

im not sure how thatd work because the amount of data to create a "state" of a board is abysmal so recording that much information, checking it, and then saving every single one would slow the program waaaay down with little improvement

jovial heath Aug 14, 2024, 4:52 PM

#

Hashable means that you can generate a number from it which will be the same for two equal objects, but different for different objects, which means you can use data structures that are a constant lookup rather than the cost of checking increasing as you add items

fervent tusk Aug 14, 2024, 4:52 PM

#

so like an animal ear tag or something?

#

oh i think im starting to understand

jovial heath Aug 14, 2024, 4:53 PM

#

Sure, I guess

#

https://stackoverflow.com/questions/14535730/what-does-hashable-mean-in-python#14535739

Stack Overflow

What does "hashable" mean in Python?

What exactly does it mean to say that an object in Python code is hashable?

fervent tusk Aug 14, 2024, 4:53 PM

#

youre saying that you would look at all the data in the board, put it through some function to give it an id, and then save that id as used

#

i literally have that open already lol

jovial heath Aug 14, 2024, 4:54 PM

#

Heh

#

Yeah basically.

fervent tusk Aug 14, 2024, 4:54 PM

#

that could work actually thats pretty smart

#

the only issue is the length of numbers would still be ridiculous

fervent tusk Aug 14, 2024, 4:55 PM

#

fervent tusk

look at this

jovial heath Aug 14, 2024, 4:55 PM

#

For small levels it would probably add more overhead than it saves, but for large levels it would be a huge optimisation

fervent tusk Aug 14, 2024, 4:56 PM

#

you would need maybe 300 million ids if not more according to that image

jovial heath Aug 14, 2024, 4:56 PM

#

So you could use a Bloom Filter

#

But also not all of those will be unique

#

And even if they were, if it takes 2 bytes to store a number (let's assume the numbers will be big) then that's still only 600MB

#

I assume you have more RAM than that

fervent tusk Aug 14, 2024, 4:58 PM

#

isnt 2 bytes 16 bits

#

which would be 512

#

no 65536

#

if theres over 300 million unique combinations id need more than 2 bytes

#

assuming every single number got used

jovial heath Aug 14, 2024, 4:59 PM

#

True, let's say 4 bytes, which holds some huge numbers, still only 1.2GB

fervent tusk Aug 14, 2024, 5:00 PM

#

i suppose

jovial heath Aug 14, 2024, 5:00 PM

#

I mean sure, that's more memory than my first computer had, but it's still reasonable

fervent tusk Aug 14, 2024, 5:00 PM

#

youd need a list with 300m items and have to check all 300m of those every time you want to generate something though

jovial heath Aug 14, 2024, 5:00 PM

#

No, you use a set, or a Bloom Filter

fervent tusk Aug 14, 2024, 5:01 PM

#

i feel like the optimization here would be a bell curve depending on the level size

#

bloom filter?

jovial heath Aug 14, 2024, 5:01 PM

#

It's a collection that you can't retrieve stuff from, but it can tell you whether a specific item is in there

fervent tusk Aug 14, 2024, 5:01 PM

#

oh so exactly like a set

jovial heath Aug 14, 2024, 5:01 PM

#

But a set of likely fine

#

A bloom filter has less overhead but it's less useful

fervent tusk Aug 14, 2024, 5:02 PM

#

even if it were a set wouldnt you still need to check every item? im not fully sure how sets work so maybe it just checks if the memory address is used or not in there

#

if it does the 2nd option then thats extremely fast and viable

jovial heath Aug 14, 2024, 5:02 PM

#

Yeah set lookup is O(1)

fervent tusk Aug 14, 2024, 5:03 PM

#

?

jovial heath Aug 14, 2024, 5:03 PM

#

Whereas for a list of would be O(n)

#

Order of magnitude

#

O(1) means it's constant

#

O(n) means it scales linearly with the size of the data

fervent tusk Aug 14, 2024, 5:04 PM

#

thatd work

#

i could also check if theres any duplicate states if its inside of the set (which should never happen)

#

theres probably some duplicates on the level i showed judging by the size and arrangement but for levels like 8-6 there could still be millions of combinations

#

how would you add data to the set? iirc they cant be edited

#

conversion into different data types each time would also slow it wouldnt it

jovial heath Aug 14, 2024, 5:10 PM

#

Sure they can, .add()

fervent tusk Aug 14, 2024, 5:10 PM

#

oho

#

oops

#

pc_boop

#

im gonna start implementing this system then i really like the sound of all of this and it can help me debug duplicate states

jovial heath Aug 14, 2024, 5:11 PM

#

So I would calculate the hash on object creation, and if the Grid has a hash, and isn't being recreated needlessly, then the State doesn't need to calculate that much

fervent tusk Aug 14, 2024, 5:12 PM

#

im not worrying about oop yet

jovial heath Aug 14, 2024, 5:12 PM

#

Ah

fervent tusk Aug 14, 2024, 5:12 PM

#

the first thing i need to figure out is how to give every state a unique id because there are maaaaaany of them and even though 4 bytes is 4 billion i should use every one shouldnt i

jovial heath Aug 14, 2024, 5:12 PM

#

That's going to make it harder

fervent tusk Aug 14, 2024, 5:12 PM

#

mmmm how hard would it be to convert to oop then youve got me hyped up for hashing right now

jovial heath Aug 14, 2024, 5:13 PM

#

Start with your tiles and work outward

fervent tusk Aug 14, 2024, 5:13 PM

#

can you reexplain what all 3 classes should be in laymans terms so i can understand

#

sorry

delicate nymph Aug 14, 2024, 5:14 PM

#

Hashing is super cool, wait till you find out how chess and go is solved using AI

#

And hash

jovial heath Aug 14, 2024, 5:26 PM

#

So a tile object would just need to store what's on a given tile, i.e what track, semaphore, etc

fervent tusk Aug 14, 2024, 5:28 PM

#

so youd want like 25 different objects just with 2 numbers or do you want more than a track and semaphore on it

#

because there can currently only be 3 things on a tile at any given moment

#

a car, track, or interactable

#

on a sidenote i should rename interactables to modifiers i feel like that makes more sense ib_think

jovial heath Aug 14, 2024, 5:37 PM

#

Yeah I think a Tile object is just

class Tile:
    track: Track
    modifier: Optional[Modifier]

where Track and Modifier could just be integers but I'd prefer they were Enum values because it makes the code much easier to reason about.

fervent tusk Aug 14, 2024, 5:39 PM

#

the modifier should probably just be 0 instead of optional because it could break some of the code otherwise but i like it (i could also just change it)

jovial heath Aug 14, 2024, 5:39 PM

#

I can give an implementation for Tile.__hash__ and __init__ or I can leave that as an exercise for the reader

fervent tusk Aug 14, 2024, 5:40 PM

#

let me do it i need to learn classes in practice too anyways

#

this whole project is just me learning python anyways pc_happy

#

what are enum values?

#

if its a value i dont see how you can enumerate a single value

jovial heath Aug 14, 2024, 5:41 PM

#

I think I tried to submit an implementation in a PR, 1 sec

#

Looks like no

#Railbound Solver [Python Script] COMPLETE! Working on Interface...