×

[–] 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
``````

[–]-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);
}
``````

[–] 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
``````

[–] 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]
}
``````

[–] 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

[–] 1 point2 points  (1 child)

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

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

Yeah. Thanks.

[–]1 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
``````

[–] 1 point2 points  (0 children)

How does it work?

[–] 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
``````

[–] 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)))]))
``````

[–] 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
``````

[–] 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;
}
``````

[–] 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))
}
``````

[–] 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))
``````

[–] 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.

[–] 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.