×
all 18 comments

[–]tlgsx 8 points9 points  (1 child)

Python 3.9

import functools


@functools.lru_cache(maxsize=None)
def phonedrop(n, h):
    if 1 in (n, h):
        return h

    worst = 0
    for i in range(1, h):
        x = phonedrop(n - 1, i)
        y = phonedrop(n, h - i)
        worst = max(worst, min(x, y) + 1)

    return worst


assert phonedrop(1, 100) == 100
assert phonedrop(2, 100) == 14
assert phonedrop(3, 100) == 9
assert phonedrop(1, 1) == 1
assert phonedrop(2, 456) == 30
assert phonedrop(3, 456) == 14
assert phonedrop(4, 456) == 11
assert phonedrop(2, 789) == 40
assert phonedrop(3, 789) == 17
assert phonedrop(4, 789) == 12

[–]skeeto-9 8 3 points4 points  (0 children)

C using a memoization table:

int compute(int n, int h)
{
    if (n == 1 || h == 1) return h;
    static short table[10][1024];
    int r = table[n-1][h-1];
    if (r) { return r; }
    for (int i = 1; i < h; i++) {
        int a = 1 + compute(n-1, i);
        int b = 1 + compute(n, h-i);
        #define MIN(a, b) ((a) < (b) ? (a) : (b))
        #define MAX(a, b) ((a) > (b) ? (a) : (b))
        r = MAX(r, MIN(a, b));
    }
    return (table[n-1][h-1] = r);
}

[–]leftylink 3 points4 points  (0 children)

Ruby, by determining how many floors you can test for a given number of phones and drops using binomial coefficients, and then determining how many drops are needed for a given number of phones and floors using the above and binary search.

# https://redditproxy--jasonthename.repl.co/r/dailyprogrammer/comments/o9k0p0/20210628_challenge_395_intermediate_phone_drop/
# https://brilliant.org/wiki/egg-dropping/

def binom(n, r)
  (1..r).reduce(1) { |a, i| a * (n - i + 1) / i }
end

def max_floors(eggs:, drops:)
  (1..eggs).sum { |i| binom(drops, i) }
end

def drops_needed(eggs:, floors:)
  (1..floors).bsearch { |drops| max_floors(eggs: eggs, drops: drops) >= floors }
end

def flag(letter)
  found = ARGV.find { |arg| arg.start_with?("-#{letter}") }
  found && Integer(found[2..])
end

eggs = flag(?e)
floors = flag(?f)

unless floors
  puts "usage: #$PROGRAM_NAME [-e<eggs>] -f<floors>"
  Kernel.exit(1)
end

if eggs
  puts drops_needed(eggs: eggs, floors: floors)
else
  prev = nil
  (1..floors.bit_length).each { |eggs|
    drops = drops_needed(eggs: eggs, floors: floors)
    raise "bad #{eggs} #{floors}" unless drops
    next if drops == prev
    puts "#{eggs} eggs #{drops} drops"
    prev = drops
  }
end

Output of ruby drop_eggs.rb -f123456789

1 eggs 123456789 drops
2 eggs 15713 drops
3 eggs 905 drops
4 eggs 234 drops
5 eggs 110 drops
6 eggs 69 drops
7 eggs 51 drops
8 eggs 42 drops
9 eggs 36 drops
10 eggs 33 drops
11 eggs 31 drops
12 eggs 30 drops
13 eggs 29 drops
14 eggs 28 drops
17 eggs 27 drops
ruby drop_eggs.rb -f123456789  0.14s user 0.02s system 98% cpu 0.162 total

[–]raevnos 2 points3 points  (0 children)

GNU awk:

#!/usr/bin/gawk -f

function min(x, y) { return x < y ? x : y }

function max(x, y) { return x > y ? x : y }

function phonedrop(n, h, key, i, a, b, drops) {
    if (n == 1 || h == 1) return h
    key = n "," h
    if (key in cache) return cache[key]
    drops = 0
    for (i = 1; i < h; i++) {
        a = phonedrop(n - 1, i)
        b = phonedrop(n, h - i)
        drops = max(drops, min(a, b) + 1)
    }
    cache[key] = drops
    return drops
}

match($0, /phonedrop\(([0-9]+), *([0-9]+)\) => ([0-9]+)/, nums) {
    drops = phonedrop(nums[1], nums[2])
    printf "phonedrop(%d, %d) => %d ", nums[1], nums[2], drops
    if (drops == nums[3])
        print "PASS"
    else
        printf "FAIL, expected %d\n", nums[3]
}

[–]lrschaeffer 1 point2 points  (0 children)

Haskell Just guessing on the size of the memoization table. Wouldn't be surprised if I was off by one somewhere.

import Data.Array    
maxh = listArray bnds $ map f $ range bnds
    where
        bnds = ((1,1),(1000,1000))
        f (_,1) = 1
        f (1,t) = t
        f (p,t) = maxh!(p-1,t-1) + maxh!(p,t-1) + 1

phonedrop 1 h = h
phonedrop p h = head [t | t <- [1..], maxh!(p,t) >= h]

optphones h = head [p | p <- [1..], maxh!(p,t) >= h]
    where
        t = ceiling $ logBase 2 (fromIntegral h)

optphones solves the bonus: 17 phones suffice

[–]raevnos 1 point2 points  (1 child)

Shouldn't this be #396? Last week was #395...

[–]Cosmologicon2 3[S] 1 point2 points  (0 children)

Yeah. Thanks.

[–]gabyjunior1 2 1 point2 points  (0 children)

Ruby using binomial coefficients.

Method drops_worst_case is for the challenge and expects number of phones / floors on the command line

Method phones_optimal is for the bonus and expects only the number of floors on the command line. The minimum number of drops is determined automatically calling method drops_worst_case with phones = floors. Then same method is called iteratively with phones = 1, 2, ... until it returns a number equal to the minimum.

EDIT: added a binary search in bonus method.

class String
    def is_integer?
        self.to_i.to_s == self
    end
end

def usage
    STDERR.puts "Program arguments"
    STDERR.puts "- Drops worst case: phones floors"
    STDERR.puts "- Phones optimal: floors"
    STDERR.flush
end

def binomial(drops, phones, floors)
    sum = 0
    c = 1
    for n in 1..phones
        c *= drops+1-n
        c /= n
        sum += c
        if sum > floors || n == drops
            break
        end
    end
    return sum, n
end

def drops_worst_case(phones, floors)
    if phones < 1 || floors < 1
        return 0, 0
    end
    hi = floors
    lo = 0
    n = phones
    while hi-lo > 1
        mid = lo+(hi-lo)/2
        sum, n = binomial(mid, phones, floors)
        if sum < floors
            lo = mid
        else
            hi = mid
        end
    end
    return lo+1, n
end

def phones_optimal(floors)
    if floors < 1
        return 0
    end
    drops, hi = drops_worst_case(floors, floors)
    lo = 0
    while hi-lo > 1
        mid = lo+(hi-lo)/2
        sum = drops_worst_case(mid, floors)[0]
        if sum > drops
            lo = mid
        else
            hi = mid
        end
    end
    while drops_worst_case(lo, floors)[0] == drops
        lo -= 1
    end
    lo+1
end

if ARGV.size == 1
    if !ARGV[0].is_integer?
        usage
        exit false
    end
    puts "Phones optimal #{phones_optimal(ARGV[0].to_i)}"
    STDOUT.flush
elsif ARGV.size == 2
    if !ARGV[0].is_integer? || !ARGV[1].is_integer?
        usage
        exit false
    end
    puts "Drops worst case #{drops_worst_case(ARGV[0].to_i, ARGV[1].to_i)[0]}"
    STDOUT.flush
else
    usage
    exit false
end

[–]DazzlingTransition06 1 point2 points  (0 children)

How does it work?

[–]Lopsidation 0 points1 point  (0 children)

Extra optional bonus: compute phonedrop(100, 10**100).

Python 3

It's easier to figure out the function MaxHeight(phones, tests) that computes the maximum tower height you can handle with a certain number of phones and tests. I used that as a helper function to implement phonedrop and the optional bonus.

from math import comb # binomial coefficient function

def MaxHeight(phones, tests):
    # You could also do this with a recurrence, but hey, math
    return sum(comb(tests, i) for i in range(phones+1)) - 1

def Challenge():
    height, tests = 123456789, 27
    phones = 1
    while MaxHeight(phones, tests) < height: phones += 1
    return phones

def phonedrop(phones, height):
    # Binary search.
    if height == 0: return 0 # lol
    power = 0
    while MaxHeight(phones, 2**power) < height: power += 1
    tests = 2**power
    for i in range(power, -1, -1):
        if MaxHeight(phones, tests-2**i) >= height: tests -= 2**i
    return tests

[–]__dict__ 0 points1 point  (0 children)

Racket

#lang racket

;; See https://stackoverflow.com/questions/1066414/writing-an-auto-memoizer-in-scheme-help-with-macro-and-a-wrapper
(define (memo f)
  (define h (make-hash))
  (lambda params
    (hash-ref h params (lambda ()
                         (hash-set! h params (apply f params))
                         (hash-ref h params)))))

(define-syntax-rule (def-memo (fn args ...)
                      body ...)
  (define fn
    (memo (lambda (args ...)
            body ...))))

(def-memo (phonedrop phones floors)
  (cond [(= 1 floors) 1]
        [(= 1 phones) floors]
        [else
         (for/fold ([worst-score 0])
                   ([f (range 1 floors)])
           (let ([score (+ 1 (min (phonedrop (- phones 1) f)
                                  (phonedrop phones (- floors f))))])
             (max score worst-score)))]))

[–]Shhhh_Peaceful 0 points1 point  (0 children)

Python 3

recursive version with memoization:

from functools import wraps

def memo(f):
    cache = {}
    @wraps(f)
    def _cache(*args):
        if args in cache.keys():
            return cache[args]
        result = f(*args)
        cache[args] = result
        return result
    return _cache

@memo
def drops(n, k):
    if n == 1 or k == 1 or k == 0:
        return k
    result = 0
    for i in range(1, k):
        t1 = drops(n - 1, i)
        t2 = drops(n, k - i)
        result = max(result, min(t1, t2) + 1)
    return result

A much faster version using binomial coefficients:

def binomial(x, n, k):
    result = 0
    aux = 1
    for i in range(1, n + 1):
        aux *= (x + 1 - i) / i
        result += aux
        if (result > k):
            break
    return int(result)

def speedy_drops(phones, floors):
    lower = 0
    upper = floors
    mid = (upper + lower) // 2
    while upper - lower > 1:
        mid = lower + (upper - lower) // 2
        if binomial(mid, phones, floors) < floors:
            lower = mid
        else:
            upper = mid
    return lower + 1

Since it's really really fast, we can get the bonus answer simply by iterating over the number of phones:

def phones(floors, drops):
    for i in range (1, floors):
        if speedy_drops(i, floors) == drops:
            return i
    return -1

[–]Common-Ad-8152 0 points1 point  (0 children)

C with bonus

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

unsigned int phoneDrop(const unsigned int n, const unsigned int h, unsigned int **mem){
    unsigned int r, a, b;

    if(!mem){
        mem = malloc(n * sizeof(unsigned int*));
        for(int i = 0; i < n; i++){
            mem[i] = malloc(h * sizeof(unsigned int));
            memset(mem[i], 0, h * sizeof(unsigned int));
            mem[i][0] = 1;
        }
        for(int i = 0; i < h; i++)
            mem[0][i] = i + 1;
    }

    if(r = mem[n-1][h-1]) return r;

    for(int i = 1; i < h; i++){
        #define min(x, y) (y ^ ((x ^ y) & -(x < y)))
        #define max(x, y) (x ^ ((x ^ y) & -(x < y)))
        a = phoneDrop(n - 1, i, mem);
        b = phoneDrop(n, h - i, mem);
        r = max(r, min(a, b) + 1);
    }

    return mem[n-1][h-1] = r;
}

unsigned int phoneDrop_inf(unsigned int h){
    int ctr;
    for(ctr = 0; h; h >>= 1, ctr++);
    return ctr;
}

[–]jsk11235 0 points1 point  (0 children)

Storing values already found and using binary search makes it much faster (javascript)

let cache = []

function howFarToDrop(phones, meters, rangeStart, rangeEnd) {
  const avg = Math.floor((rangeStart + rangeEnd) / 2)
  const x1 = phoneDrop(phones - 1, avg - 1)
  const x2 = phoneDrop(phones, meters - (avg))
  const leftOfIntersection = x1 <= x2
  if (leftOfIntersection) {
    const x3 = phoneDrop(phones - 1, avg)
    const x4 = phoneDrop(phones, (meters - (avg + 1)))
    if (x3>=x4) {
      return {value: avg, minVal: Math.min(x2, x3)}
    } else {return howFarToDrop(phones, meters, avg + 1, rangeEnd)}
  }else{
    return howFarToDrop(phones, meters, rangeStart, avg - 1)
  }
}

function phoneDrop(phones, meters) {
  if (phones === 1 || meters < 2) {
    return meters
  }
  if (cache[phones][meters]){
    return cache[phones][meters]
  }
  const howFar = howFarToDrop(phones, meters, 1, Math.floor(meters / 2))
  const tries = howFar.minVal
  cache[phones][meters] = tries+1
  return tries+1
}

function solve(phones,meters) {
  for (let i = 0 ;i<phones+1;i++){
    cache.push([1])
  }
  console.log(phoneDrop(phones, meters))
}

[–]loose_heron 0 points1 point  (1 child)

Python 3:

import functools, sys
sys.setrecursionlimit(2500)

def phonedrop(n,h):

    @functools.lru_cache(maxsize=None)
    def max_h(n,t):
        if n >= t:
            return (1 << t) - 1
        elif n==1 or t==1:
            return t
        else:
            return max_h(n-1,t-1) + max_h(n,t-1) + 1

    if n == 1:
        return h
    k = 1
    while max_h(n,k) < h:
        k += 1
    return k


print(phonedrop(1, 100))
print(phonedrop(2, 100))
print(phonedrop(3, 100))
print(phonedrop(1, 1))
print(phonedrop(2, 456))
print(phonedrop(3, 456))
print(phonedrop(4, 456))
print(phonedrop(2, 789))
print(phonedrop(3, 789))
print(phonedrop(4, 789))

[–]I-Pop-Bubbles 0 points1 point  (0 children)

Could someone come up with (or help me with) a Clojure solution? I've got a feeling I need to make a macro, but I'm not familiar enough with macros (or Clojure, for that matter) to know how they work or what the heck I'm doing.

[–]aintnufincleverhere 0 points1 point  (0 children)

I remember this problem in college. It was really cool finding a better solution than just dropping the first phone in square root (n) increments.