1
// SPDX-License-Identifier: Unlicensed
2
pragma solidity ^0.8.17;
3

4
import "../interfaces/IPuzzle.sol";
5

6
/// @title what are buckets?
7
/// @author waldenyan.eth
8
contract WhatAreBuckets is IPuzzle {
9
    uint256 public constant PRIMES = 0x20305070b0d1113171d1f25292b2f353b;
10
    uint256 public constant numPrimes = 17;
11

12
    /// @inheritdoc IPuzzle
13
    function name() external pure returns (string memory) {
14
        return unicode"what are buckets?";
15
    }
16

17
    function work(uint256 state, uint8 op) internal pure returns (uint256) {
18
        if (op >> 2 == 0) {
19
            if ((op & 2) == 2) {
20
                state <<= 8;
21
            }
22
            state &= 0xffffff00ff;
23
            if ((op & 1) == 1) {
24
                state |= (state >> 16) & 0xff00;
25
            }
26
            if ((op & 2) == 2) {
27
                state >>= 8;
28
            }
29
        } else if ((op & 5) == 4) {
30
            if ((op & 2) == 2) {
31
                state = (state & 0xff00ff00) >> 8 | (state & 0x00ff00ff) << 8;
32
            }
33
            uint256 flow0 = (state >> 8) & 0xff;
34
            uint256 flow1 = ((state >> 16) & 0xff) - (state & 0xff);
35
            uint256 flow = flow0 > flow1 ? flow1 : flow0;
36
            state -= flow << 8;
37
            state += flow;
38
            if ((op & 2) == 2) {
39
                state = (state & 0xff00ff00) >> 8 | (state & 0x00ff00ff) << 8;
40
            }
41
        }
42
        return state;
43
    }
44

45
    function workAll(uint256 state, uint256 commands) internal pure returns (uint256) {
46
        for (uint256 i = 0; i < 85; i++) {
47
            state = work(state, uint8(commands >> (i * 3)) & 7);
48
        }
49
        return state;
50
    }
51

52
    /// @inheritdoc IPuzzle
53
    function generate(address _seed) external pure returns (uint256) {
54
        uint256 seed = uint256(keccak256(abi.encodePacked(_seed)));
55
        uint256 tmp = seed;
56

57
        uint256 numPairs = numPrimes * (numPrimes - 1);
58
        while (tmp > 0) {
59
            uint256 v = tmp % numPairs;
60
            tmp /= numPairs;
61
            uint256 a = v % numPrimes;
62
            uint256 b = v / numPrimes;
63
            if (b >= a) b += 1;
64
            uint256 prime1 = (PRIMES >> (a << 3)) & 0xff;
65
            uint256 prime2 = (PRIMES >> (b << 3)) & 0xff;
66
            if (
67
                (prime1 + 1) % prime2 == 0 || (prime2 + 1) % prime1 == 0
68
                    || (prime1 - 1) % prime2 == 0 || (prime2 - 1) % prime1 == 0
69
            ) {
70
                continue;
71
            }
72
            return workAll((prime1 << 24) | (prime2 << 16), seed);
73
        }
74

75
        // It's your lucky day!
76
        return 1;
77
    }
78

79
    /// @inheritdoc IPuzzle
80
    function verify(uint256 _start, uint256 _solution) external pure returns (bool) {
81
        return
82
            workAll(_start, _solution ^ uint256(keccak256(abi.encodePacked(_start)))) & 0xffff == 1;
83
    }
84
}
85