I approached solving Rush Hour puzzles using Solidity's core data structures and logic capabilities. Now, let's dive into a more experimental approach that leverages memory mapping for potential performance gains.
Memory Allocation based on Car Count
The core idea is to pre-allocate memory during board initialization. The total memory size is calculated based on the number of cars (cars) on the board. Here's the logic:
- Exponential Growth: We assume each car can have up to five different positions/orientations (considering up, down, left, right, and no movement).
- Total Cases: The total number of possible game states is calculated as cars raised to the power of cars (i.e., cars ^ cars). This represents the maximum number of memory slots that might be needed.
_createSnapMapMemorySpace() Function
The contract has a function named _createSnapMapMemorySpace responsible for allocating the memory space based on the calculated size.
https://github.com/JensonCollins/rush-hour-puzzle/blob/main/contracts/RushHourSolver.sol#L359
Optimizing Memory Usage (is3Len parameter)
To potentially reduce memory allocation size, we can introduce an optional parameter is3Len. This flag might indicate if any car on the board has a length of 3 units.
- Impact on Weight: Cars with a length of 3 can occupy more than one grid space simultaneously. This can affect the total number of possible game states, potentially reducing the required memory allocation compared to the cars ^ cars formula.
Step Count and Stack Overflow Protection
During the search process, a variable named stepNum might track the depth within the exploration tree (representing the number of moves made).
- Stack Overflow Risk: Solidity has limitations on stack usage. If the search goes too deep (i.e., stepNum becomes too large), a StackOverflow error might occur.
- Mitigating the Risk: To prevent this error, I declared a constant MAX_STACK_DEEP (e.g., set to 36) to limit the exploration depth.
Efficient Single Byte Storage with Assembly
Solidity v0.8 introduced the mstore8 assembly opcode. This allows setting a single byte in memory storage.
Saving Step Count: We can leverage mstore8 to store the stepNum value in just one byte within the allocated memory space.
mstore8
Conclusion
Memory mapping for Rush Hour in Solidity is an innovative concept with potential benefits. However, careful consideration of memory constraints and trade-offs is crucial before implementing it in real-world applications. For complex scenarios, alternative approaches like efficient data structures and heuristic search algorithms might be more practical.
Top comments (0)