package com.java;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class EggsFloorsSecondAttempt {
    private static class EggDrops {
        private int eggs;
        private int drops;

        public EggDrops(int eggs, int drops) {
            this.eggs = eggs;
            this.drops = drops;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            EggsFloorsSecondAttempt.EggDrops eggDrops = (EggsFloorsSecondAttempt.EggDrops) o;
            return eggs == eggDrops.eggs &&
                    drops == eggDrops.drops;
        }

        @Override
        public int hashCode() {
            return Objects.hash(eggs, drops);
        }
    }


    private static Map<EggsFloorsSecondAttempt.EggDrops, Integer> floorCache = new HashMap<>();

    public static int getNumberFloors(int eggs, int drops) {
        if(eggs <= 0 || drops <= 0) {
            return 0;
        }
        if(eggs == 1) {
            return drops;
        }
        if(drops == 1) {
            return 1;
        }

        EggsFloorsSecondAttempt.EggDrops eggDrops = new EggsFloorsSecondAttempt.EggDrops(eggs, drops);
        if(floorCache.containsKey(eggDrops)) {
            return floorCache.get(eggDrops);
        }

        int result = getNumberFloors(eggs - 1, drops - 1) + 1 + getNumberFloors(eggs, drops - 1);
        floorCache.put(eggDrops, result);
        return result;
    }

    public static int getMinimumEggDrops(int eggs, int floors) {
        for(int i = 1; i <= floors; ++i) {
            if (getNumberFloors(eggs, i) >= floors) return i;
        }
        throw new RuntimeException("Something is wrong here!");
    }


     public static int getFirstDroppingFloor(int eggs, int floors) {
        int lo = 1;
        int hi = floors;
        int s;
        int s_min = 0;
        int wc = Integer.MAX_VALUE;
        while(lo < hi){
            s = (lo + hi) / 2;
            int b = getMinimumEggDrops(eggs - 1, s - 1);
            int nb = getMinimumEggDrops(eggs, floors - s);


            int wc1 = 1 + Math.max(b, nb);
            if(wc1 < wc) {
                wc = wc1;
                s_min = s;
            }
            if(b == nb) break;
            else if(b > nb) {
                hi = s - 1;
            }
            else {
                lo = s + 1;
            }
        }
        return s_min;
    }

    public static void main(String[] args) {
        System.out.println(getMinimumEggDrops(2, 100)); // prints 14 correct
        System.out.println(getMinimumEggDrops(3, 100)); // prints 9 correct
        System.out.println(getFirstDroppingFloor(2, 36)); // prints 9 wrong should  be 8 or 14
        System.out.println(getFirstDroppingFloor(3, 100)); // prints 25

    }
}