Timeline for Shortest universal maze exit string
Current License: CC BY-SA 3.0
45 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 5, 2019 at 20:38 | comment | added | Sopel |
This code can be further sped up by halving move values and not doing the division by 2. Though I haven't measured precisly, the speedup was noticable at least on my pc. godbolt.org/z/iLml-3 The version with bt was slower, at least on my nehalem enum { N = -4, W = -1, E = 1, S = 4 }; int do_move(uint32_t walls, int pos, int halfmove) { int idx = pos + halfmove; return walls & (1ull << idx) ? pos + halfmove + halfmove : pos; } Also it's trivial to parallelize. pastebin.com/tv1vnPcA There's num_threads variable.
|
|
| Aug 2, 2017 at 20:12 | comment | added | tuskiomi | Has anyone thought about porting the do_Move function to OpenCL or CUDA? | |
| Oct 23, 2016 at 23:47 | vote | accept | trichoplax is on Codidact now | ||
| Oct 23, 2016 at 23:44 | comment | added | trichoplax is on Codidact now | I hope you don't mind my edit - I wanted to include the most up to date score found using your code ready for posting an open ended bounty for an improvement. | |
| Oct 23, 2016 at 23:42 | history | edited | trichoplax is on Codidact now | CC BY-SA 3.0 |
Edit in length 79 based on comment in chat http://chat.stackexchange.com/transcript/message/23311942#23311942
|
| Aug 9, 2015 at 19:04 | history | bounty ended | Sp3000 | ||
| Aug 7, 2015 at 18:16 | comment | added | trichoplax is on Codidact now | That was quick... | |
| Aug 7, 2015 at 14:14 | comment | added | orlp | @trichoplax 81 :) | |
| Aug 7, 2015 at 14:14 | history | edited | orlp | CC BY-SA 3.0 |
added 19 characters in body
|
| Aug 7, 2015 at 12:48 | comment | added | trichoplax is on Codidact now | Ah... Well I'll be waiting until the end of the 24 hour grace period before awarding the bounty, so there are over 25 hours still available. Good luck :) | |
| Aug 7, 2015 at 12:37 | comment | added | orlp | @trichoplax Well, I woke up today to check the terminal, but it seems that my computer BSOD'd overnight. So, the only answer is 'perhaps'. | |
| Aug 7, 2015 at 11:23 | comment | added | trichoplax is on Codidact now | @orlp did the improvements lead to shorter strings? 24 hours left to get lower than 82 for the bounty... | |
| Aug 4, 2015 at 21:26 | comment | added | trichoplax is on Codidact now |
@orlp Great! I was only swapping with i - 1 and saw a marginal speed up - I didn't think to use i / 2.
|
|
| Aug 4, 2015 at 19:51 | comment | added | orlp | @trichoplax From my measurements it seems to be 2x faster! | |
| Aug 4, 2015 at 19:39 | history | edited | orlp | CC BY-SA 3.0 |
added 313 characters in body
|
| Aug 4, 2015 at 19:38 | comment | added | orlp |
@trichoplax And from my measurements, effective too! All I do is if I detect that the maze at index i caused the failure, I swap it with the maze at position i / 2. This (really) often reduces 10000+ mazes being checked to <50.
|
|
| Aug 4, 2015 at 19:30 | comment | added | orlp | @trichoplax That's a cool idea! | |
| Aug 4, 2015 at 18:59 | comment | added | trichoplax is on Codidact now | I got a little bit of a speed up by sorting the vector of mazes - each time a string fails for a maze, that maze is moved one step closer to the start of the vector, so that after a while invalid strings are failing earlier on average. Not sure if that will conflict with some of the other improvements you've made since then though... | |
| Aug 4, 2015 at 18:51 | history | edited | orlp | CC BY-SA 3.0 |
added 19 characters in body
|
| Aug 4, 2015 at 16:41 | history | edited | orlp | CC BY-SA 3.0 |
added 17 characters in body
|
| Aug 4, 2015 at 9:24 | comment | added | orlp |
@AlexReinking Done. do_move is now insanely fast.
|
|
| Aug 4, 2015 at 9:23 | history | edited | orlp | CC BY-SA 3.0 |
deleted 157 characters in body
|
| Aug 4, 2015 at 5:18 | comment | added | orlp | @AlexReinking Initially I thought of using 2-bit integers to represent the strings, but then I found out memory usage is no problem, so the enum still stems from that version. In my next version I can do that, yes. | |
| Aug 4, 2015 at 5:09 | comment | added | Alex Reinking | could you save a little bit by defining the enum constants to be the offsets you compute and then make the rarely-called string translation a bit more complicated? | |
| Aug 4, 2015 at 4:38 | comment | added | orlp | @AlexReinking I updated my answer with said implementation. If you look at the disassembly you'll see it's only a dozen of instructions without any branch or load: coliru.stacked-crooked.com/a/3b09d36db85ce793 . | |
| Aug 4, 2015 at 4:37 | history | edited | orlp | CC BY-SA 3.0 |
added 95 characters in body
|
| Aug 4, 2015 at 4:17 | comment | added | Alex Reinking | Would love to see what that looks like. | |
| Aug 4, 2015 at 4:09 | comment | added | orlp |
@AlexReinking Not needed, you can change the position numbers such that they'll never go negative, and then encode the wall such that the ith bit of it contains either a 0 or a 1 for a wall at that position, and every other bit is a 0. Then you can just mask directly without the need of any lookup table or branch.
|
|
| Aug 4, 2015 at 4:06 | comment | added | Alex Reinking | @orlp I had an idea for moving that doesn't require branching and uses a small lookup table (less than the size of a cache line). How fast do you think it is? | |
| Aug 4, 2015 at 3:38 | comment | added | orlp | @AlexReinking No, iterating over a contiguous chunk of memory in a linear fashion is perfect for the prefetcher and cache. Either way, that iteration can not be avoided. | |
| Aug 4, 2015 at 3:36 | comment | added | Alex Reinking | Aren't you already hitting L3 cache when you iterate over the vector of Mazes? No memory lookups would be best, yeah. | |
| Aug 4, 2015 at 3:32 | comment | added | orlp | @AlexReinking That would be significantly slower. Since the table is around ~1 megabyte you'll expect to hit L3 cache. L3 cache is ~40 cycles per access. The best way to speed this up is to precompute the masks into the walls variable, and to not do memory lookups at all. | |
| Aug 4, 2015 at 3:29 | comment | added | Alex Reinking |
Actually, if you created that table within each Maze struct, you would only use two memory loads to compute a move, rather than one memory load and a bunch of arithmetic (and a branch!).
|
|
| Aug 4, 2015 at 3:27 | comment | added | Alex Reinking |
You could make this even faster by just preprocessing a table of walls, positions, and directions. It'd be less than a megabyte in size, and do_move would just become table[walls][pos][move]
|
|
| Jul 29, 2015 at 15:39 | comment | added | orlp | @trichoplax I told you it was fun :) | |
| Jul 29, 2015 at 15:37 | comment | added | trichoplax is on Codidact now | I finally got round to installing gcc and running this for myself. It is hypnotic watching the strings mutating and slowly shrinking... | |
| Jul 18, 2015 at 8:07 | history | edited | orlp | CC BY-SA 3.0 |
deleted 222 characters in body
|
| Jul 18, 2015 at 6:42 | history | edited | orlp | CC BY-SA 3.0 |
added 15 characters in body
|
| Jul 17, 2015 at 22:09 | history | edited | orlp | CC BY-SA 3.0 |
added 15 characters in body
|
| Jul 17, 2015 at 21:41 | history | edited | Alex A. | CC BY-SA 3.0 |
Added syntax highlighting
|
| Jul 17, 2015 at 21:34 | history | edited | orlp | CC BY-SA 3.0 |
added 506 characters in body
|
| Jul 17, 2015 at 20:45 | comment | added | trichoplax is on Codidact now | Confirmed valid. I'm impressed - I didn't expect to see strings this short. | |
| Jul 17, 2015 at 20:41 | history | edited | orlp | CC BY-SA 3.0 |
added 18 characters in body
|
| Jul 17, 2015 at 19:19 | history | edited | orlp | CC BY-SA 3.0 |
added 242 characters in body
|
| Jul 17, 2015 at 19:11 | history | answered | orlp | CC BY-SA 3.0 |