I use C++, there is no garbage collector. I found another way to sort. Using a temporary unordered_set is faster than std::sort. I didn’t think about the simple int comparison to check the goal.
I’ll try to preallocate my vectors, but first I want to try to avoid segments as cedricdd said.
Thank you.
1 Like
A small note: if you have x coord at the most significant bits, then you need to re-sort only if a box is moved left or right… but not if up or down
But I agree: pruning the number of iterations yields much more saving than cutting the computing time within an iteration.
PS. Maybe I am wrong, but if a c++ vector outgrows its current capacity, then double capacity is allocated and whole content is copied. That is lot of copying till the size grows from 8 to 100k items.
If you have an estimate of the maximum number of elements in the worst case, you can avoid this by preallocating with this amount using vector::reserve
1 Like
My ‘positions’ hash is just a visualization of the boxes positions.
There is no order or what.
The grid is linearized so that the whole grid can be vizualized like this: 000…000 and you put a 1 where the boxes are.
When you open a node, you check every neighboor of your player, if it’s empty you go there and if there’s a box (easy to check with the positions hash), you compute the new box position and check if there’s another box there (still with the positions hash) or a wall or if it’s a corner (corners can be precalculated easily).
Ok, now it’s done !
Actually there were 2 bugs in my code, the most important was on sorting boxes (using a temporary unordered_set wasn’t a good idea). Now i use std::sort the first time before my bfs, and a self-coded sorting function during the BFS to sort only the moved box.
I don’t use cedricdd’s segments, I don’t use Djoums’ idea about multi BFS, I don’t use gcc optims, I don’t use pre-allocated memory … and I pass all tests in less than 1s.
The longest one is Scoria 3 level 5 : 0.703568s, 312134 iterations.
Pardouin, I understand your bitboard, but I didn’t want to use a 128bit integer since all datas can be bitboarded in less than 64 bits. The container used in my BFS (unordered_set) needs a 64bits hash and I don’t know how to compute a 64bits hash with a 128bit integer in my datas.
Thank you all for your help. 
1 Like
In python you can in fact solve mith max time of 0.6s (case 25). Uses triks from @pardouin and a special bfs using sets instead of lists :
2 Likes