SolveTaigaTrees.java

package lifting;

import com.seedfinding.mccore.rand.seed.StructureSeed;
import com.seedfinding.mccore.util.data.Pair;
import com.seedfinding.mccore.util.data.SeedIterator;
import com.seedfinding.mccore.util.data.Triplet;
import com.seedfinding.mccore.util.pos.BPos;
import com.seedfinding.mcseed.rand.JRand;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Function;

public class SolveTaigaTrees {
    public static void main(String[] args) {
        List<TaigaTreeData> data = new ArrayList<>();
//        data.add(new TaigaTreeData(76, 151, new Triplet<>(6, 1, 3), new Pair<>(0, 1)));
//        data.add(new TaigaTreeData(85, 149, new Triplet<>(8, 1, 3), new Pair<>(1, 0)));
//        data.add(new TaigaTreeData(76, 146, new Triplet<>(11, 8, 4)));
//        data.add(new TaigaTreeData(84, 143, new Triplet<>(9, 2, 3), new Pair<>(1, 0)));
//        data.add(new TaigaTreeData(79, 136, new Triplet<>(9, 7, 2)));
//        tryCrack(new SeedIterator(0, 1L << 48), data);

//        testData1();
//        testData2();
        test(17989135928469L,((151-8)>>4),((991-8)>>4));
    }


    public static void testData1() {
        List<TaigaTreeData> data = new ArrayList<>();
        // Test Data set ctr: 6469 seed: 265824877365960
        // Placed at /tp @p 161 86 969 , tree with characteristic (8,2,2) (0,1) (counter at 6477)
        // Placed at /tp @p 159 86 973 , tree with characteristic (7,2,3) (0,1) (counter at 6485)
        // Placed at /tp @p 157 89 969 , tree with characteristic (10,7,3) (counter at 6491)
        // Placed at /tp @p 165 85 974 , tree with characteristic (9,5,4) (counter at 6497)
        // Placed at /tp @p 160 87 977 , tree with characteristic (9,2,3) (1,2) (counter at 6505)
        // Placed at /tp @p 155 88 981 , tree with characteristic (10,6,1) (counter at 6517)
        // Placed at /tp @p 153 86 968 , tree with characteristic (7,3,2) (counter at 6523)
        data.add(new TaigaTreeData(161, 969, new Triplet<>(8, 2, 2), new Pair<>(0, 1)));
        data.add(new TaigaTreeData(159, 973, new Triplet<>(7, 2, 3), new Pair<>(0, 1)));
        data.add(new TaigaTreeData(157, 969, new Triplet<>(10, 7, 3)));
        data.add(new TaigaTreeData(165, 974, new Triplet<>(9, 5, 4)));
        data.add(new TaigaTreeData(160, 977, new Triplet<>(9, 2, 3), new Pair<>(1, 2)));
        data.add(new TaigaTreeData(155, 981, new Triplet<>(10, 6, 1)));
        data.add(new TaigaTreeData(153, 968, new Triplet<>(7, 3, 2)));
        long bound = 100_000L;
        long time = System.currentTimeMillis();
        tryCrack(new SeedIterator(265824877365960L - bound, 265824877365960L + bound), data,new WaterRestriction());
        long took = System.currentTimeMillis() - time;
        long expected = (1L << 47) / bound * took;
        System.out.printf("Took %d ms for %d seeds expected %d ms (%d hrs)\n", took, bound * 2, expected, expected / 1000 / 3600);
        /// should output [0, 1, 2, 3, 4, -1, -1, -1, -1, -1, -1]
    }

    public static void testData2() {
        List<TaigaTreeData> data = new ArrayList<>();
        // Test Data set ctr: 6558 seed: 17989135928469
        // Placed at /tp @p 151 84 991 , tree with characteristic (6,1,2) (1,2) (counter at 6566)
        // Placed at /tp @p 147 88 989 , tree with characteristic (11,7,1) (counter at 6578)
        // Placed at /tp @p 149 84 996 , tree with characteristic (7,2,3) (1,1) (counter at 6586)
        // Placed at /tp @p 138 85 990 , tree with characteristic (9,2,3) (0,0) (counter at 6612)
        // Placed at /tp @p 142 85 997 , tree with characteristic (7,2,2) (0,1) (counter at 6626)
        // missing
        data.add(new TaigaTreeData(151, 991, new Triplet<>(6, 1, 2), new Pair<>(1, 2)));

        // missing
        data.add(new TaigaTreeData(147, 989, new Triplet<>(11, 7, 1)));

        // missing
        data.add(new TaigaTreeData(138, 990, new Triplet<>(9, 2, 3), new Pair<>(0, 0)));

        data.add(new TaigaTreeData(149, 996, new Triplet<>(7, 2, 3), new Pair<>(1, 1)));
        data.add(new TaigaTreeData(142, 997, new Triplet<>(7, 2, 2), new Pair<>(0, 1)));
        WaterRestriction waterRestriction=new WaterRestriction();
        long bound = 1;
        long time = System.currentTimeMillis();
        tryCrack(new SeedIterator(17989135928469L - bound, 17989135928469L + bound), data,waterRestriction);
        long took = System.currentTimeMillis() - time;
        long expected = (1L << 47) / Math.max(bound, 1L) * took;
        System.out.printf("Took %d ms for %d seeds expected %d ms (%d hrs)\n", took, bound * 2, expected, expected / 1000 / 3600);
        /// should output [0, 1, 2, 3, 4, -1, -1, -1, -1, -1, -1]
    }

    public static void tryCrack(SeedIterator seedIterator, List<TaigaTreeData> dataList, WaterRestriction waterRestriction) {
        seedIterator.asStream().forEach(seed -> {
            int[] matches = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
            crackOne(seed,seed,0,dataList,waterRestriction,matches,0);
        });
    }

    public static void crackOne(long originalSeed, long currentSeed, int currentIndex, List<TaigaTreeData> dataList, WaterRestriction waterRestriction,int[] matches,int nbMatches){
        JRand.Debugger rand = new JRand(currentSeed, false).asDebugger();
        for (int i = currentIndex; i < 11; i++) {
            int posX = rand.nextInt(16);
            int posZ = rand.nextInt(16);
            boolean isType1 = rand.nextInt(3) == 0;
            System.out.println(posX + " " + posZ + " " + isType1);
            if (isType1) {
                int fullTreeSize = rand.nextInt(5) + 7;
                int trunkSize = fullTreeSize - rand.nextInt(2) - 3;
                int treeGirth = 1 + rand.nextInt(fullTreeSize - trunkSize + 1);
                for (int dataIdx = 0; dataIdx < dataList.size(); dataIdx++) {
                    TaigaTreeData data = dataList.get(dataIdx);
                    if (data.getPosX() == posX && data.getPosZ() == posZ) {
                        if (data.isType1()) {
                            // this can only be accessed by at most one idx since posX and posZ are data point from real world where tree don't overlap
                            // TODO optimize on gpu for type2
                            if (data.getFullTreeSize() == fullTreeSize && data.getTrunkSize() == trunkSize && data.getTreeGirth() == treeGirth) {
                                matches[i] = dataIdx;
                                nbMatches++;
                            }
                        }
                    }
                }
            } else {
                int fullTreeSize = rand.nextInt(4) + 6;
                int trunkSize = 1 + rand.nextInt(2);
                int treeGirth = 2 + rand.nextInt(2);

                if (waterRestriction.contains(posX,posZ)){
                    // We have a water block so we stop generating one branch and go to the next iteration
                    crackOne(originalSeed,rand.getSeed(),i+1,dataList,waterRestriction,matches,nbMatches);
                }
                // We didn't have water so we keep going
                int topHatGirth = rand.nextInt(2);
                int topHatHeight = rand.nextInt(3);
                for (int dataIdx = 0; dataIdx < dataList.size(); dataIdx++) {
                    TaigaTreeData data = dataList.get(dataIdx);
                    if (data.getPosX() == posX && data.getPosZ() == posZ) {
                        if (data.isType1()) {
                            continue;
                        }
                        if (data.getFullTreeSize() == fullTreeSize && data.getTrunkSize() == trunkSize && data.getTreeGirth() == treeGirth) {
                            if (data.getTopHatHeight() == topHatHeight && data.getTopHatGirth() == topHatGirth) {
                                matches[i] = dataIdx;
                                nbMatches++;
                            }
                        }
                    }
                }
            }
            System.out.println(rand.getGlobalCounter() + 6558); System.out.println(Arrays.toString(matches));
        }
        if (nbMatches >= 5) {
            System.out.println(Arrays.toString(matches)+ " " +originalSeed);
        }
    }


    public static class WaterRestriction {
        public final List<BPos> positions = new ArrayList<>();

        WaterRestriction(BPos corner1, BPos corner2) {
            this.add(corner1,corner2);
        }

        WaterRestriction(BPos block) {
            this.add(block);
        }
        WaterRestriction(){

        }

        boolean contains(int posX,int posZ){
            return this.positions.contains(new BPos(posX,0,posZ));
        }

        void add(BPos block) {
            this.positions.add(block);
        }

        void add(BPos corner1, BPos corner2) {
            for (int x = Math.min(corner1.getX(),corner2.getX()); x < Math.max(corner1.getX(),corner2.getX()); x++) {
                for (int z = Math.min(corner1.getZ(),corner2.getZ()); z <Math.max(corner1.getZ(),corner2.getZ()); z++) {
                    this.add(new BPos(x,0,z));
                }
            }
        }

    }


    public static class TaigaTreeData {
        int posX;
        int posZ;
        Triplet<Integer, Integer, Integer> characteristics;
        Pair<Integer, Integer> topHat;

        TaigaTreeData(int posX, int posZ, Triplet<Integer, Integer, Integer> characteristics) {
            this(posX, posZ, characteristics, null);
        }

        TaigaTreeData(int posX, int posZ, Triplet<Integer, Integer, Integer> characteristics, Pair<Integer, Integer> topHat) {
            this.posX = posX;
            this.posZ = posZ;
            this.characteristics = characteristics;
            this.topHat = topHat;
        }

        boolean isType1() {
            return this.topHat == null;
        }

        public int getPosX() {
            return (this.posX - 8) & 15;
        }

        public int getPosZ() {
            return (this.posZ - 8) & 15;
        }

        public int getFullTreeSize() {
            return this.characteristics.getFirst();
        }

        public int getTrunkSize() {
            return this.characteristics.getSecond();
        }

        public int getTreeGirth() {
            return this.characteristics.getThird();
        }

        public int getTopHatGirth() {
            return this.topHat.getFirst();
        }

        public int getTopHatHeight() {
            return this.topHat.getSecond();
        }

        Pair<Integer, Integer> getFirstCall() {
            if (isType1()) {
                return new Pair<>(5, this.characteristics.getFirst() - 7);
            } else {
                return new Pair<>(4, this.characteristics.getFirst() - 6);
            }
        }

        Pair<Integer, Integer> getSecondCall() {
            if (isType1()) {
                return new Pair<>(2, this.characteristics.getFirst() - this.characteristics.getSecond() - 3);
            } else {
                return new Pair<>(2, this.characteristics.getSecond() - 1);
            }
        }

        Pair<Integer, Integer> getThirdCall() {
            if (isType1()) {
                return new Pair<>(this.characteristics.getFirst() - this.characteristics.getSecond() + 1, this.characteristics.getThird() - 1);
            } else {
                return new Pair<>(2, this.characteristics.getSecond() - 2);
            }
        }

        @Override
        protected Object clone() throws CloneNotSupportedException {
            return super.clone();
        }
    }

    public static void test(long seed,int chunkX,int chunkZ) {
        JRand rand = new JRand(seed, false);
        for (int i = 0; i < 11; i++) {
            System.out.println(generateTree(rand,chunkX,chunkZ));
        }
    }

    public static Pair<BPos, TreeCharacteristic> generateTree(JRand rand,int chunkX,int chunkZ) {
        int offsetX = rand.nextInt(16);
        int offsetZ = rand.nextInt(16);
        BPos pos = new BPos(offsetX+chunkX*16 +8, 0, offsetZ+chunkZ*16 +8);
        TreeCharacteristic treeCharacteristic = rand.nextInt(3) == 0 ? TreeType.TYPE1.apply(rand) : TreeType.TYPE2.apply(rand);
        return new Pair<>(pos, treeCharacteristic);
    }


    public static TreeCharacteristic generateTree1(JRand rand) {
        int fullTreeSize = rand.nextInt(5) + 7;
        int trunkSize = fullTreeSize - rand.nextInt(2) - 3;
        int treeGirth = 1 + rand.nextInt(fullTreeSize - trunkSize + 1);
        return new TreeCharacteristic(fullTreeSize, trunkSize, treeGirth, new Triplet<>(fullTreeSize - 7, fullTreeSize - trunkSize - 3, treeGirth - 1));
    }

    public static TreeCharacteristic generateTree2(JRand rand) {
        int fullTreeSize = rand.nextInt(4) + 6;
        int trunkSize = 1 + rand.nextInt(2);
        int treeGirth = 2 + rand.nextInt(2);
        int topHatGirth = rand.nextInt(2);
        int topHatHeight = rand.nextInt(3);
        return new TreeCharacteristic(fullTreeSize, trunkSize, treeGirth, topHatGirth, topHatHeight, new Triplet<>(fullTreeSize - 6, trunkSize - 1, treeGirth - 2));
    }

    public static class TreeCharacteristic {
        int fullTreeSize, trunkSize, treeGirth;
        Integer topHatGirth, topHatHeight;
        Triplet<Integer, Integer, Integer> numbers;

        public TreeCharacteristic(int fullTreeSize, int trunkSize, int treeGirth, Triplet<Integer, Integer, Integer> numbers) {
            this(fullTreeSize, trunkSize, treeGirth, null, null, numbers);
        }

        public TreeCharacteristic(int fullTreeSize, int trunkSize, int treeGirth, Integer topHatGirth, Integer topHatHeight, Triplet<Integer, Integer, Integer> numbers) {
            this.fullTreeSize = fullTreeSize;
            this.trunkSize = trunkSize;
            this.treeGirth = treeGirth;
            this.topHatGirth = topHatGirth;
            this.topHatHeight = topHatHeight;
            this.numbers = numbers;
        }

        @Override
        public String toString() {
            return String.format("(%d,%d,%d) (%d,%d)", this.fullTreeSize, this.trunkSize, this.treeGirth, this.topHatHeight, this.topHatGirth);
        }
    }

    public enum TreeType {
        TYPE1(SolveTaigaTrees::generateTree1),
        TYPE2(SolveTaigaTrees::generateTree2);
        final Function<JRand, TreeCharacteristic> function;

        TreeType(Function<JRand, TreeCharacteristic> function) {
            this.function = function;
        }

        TreeCharacteristic apply(JRand rand) {
            return this.function.apply(rand);
        }
    }
}