@bjorng did something similar.
adamu
lud
hauleth
Today was easy:
defmodule Buyer do
def hash(number, rounds \\ 2000) do
Enum.map_reduce(1..rounds//1, number, fn _, acc ->
r = do_round(acc)
{rem(r, 10), r}
end)
end
defp do_round(num) do
num = subround(num, num * 64)
num = subround(num, div(num, 32))
subround(num, num * 2048)
end
defp subround(a, b), do: rem(Bitwise.bxor(a, b), 16777216)
def sequences(prices) do
prices
|> Enum.chunk_every(5, 1, :discard)
|> Enum.reduce(%{}, fn seq, map ->
Map.put_new(map, diffs(seq), List.last(seq))
end)
end
def diffs(vals), do: vals |> Enum.chunk_every(2, 1, :discard) |> Enum.map(fn [a, b] -> b - a end)
end
# P1
inits
|> Enum.map(&elem(Buyer.hash(&1), 1))
|> Enum.sum()
# P2
seqs =
inits
|> Task.async_stream(
fn init ->
{prices, _} = Buyer.hash(init)
Buyer.sequences(prices)
end,
ordered: false
)
|> Enum.reduce(%{}, fn {:ok, a}, b -> Map.merge(a, b, fn _k, v, k -> v + k end) end)
Enum.max_by(seqs, &elem(&1, 1))
0
rvnash
bjorng
Erlang Core Team
I would expect atoms and small integers (fitting in 60 bits) to be fast when used as map keys.
0
rvnash
Just FYI. I tried for keys that maps sequences to bananas, unique Integers, Atoms, Tuples, and Strings as keys. Here are the times for the final bunch of merges that produce the answer.
# Integer 747ms
# Atom 670ms
# Tuple 1024ms
# String 2371ms
0
trenttobler
I wonder what optimizations could be made other than memoizing.
I ran brute force to get the solution, then optimized that. If you know when to stop adding bananas for a specific pricing sequence, you can skip a lot of computation.
Compute the min and max unit price for the pricing sequence; the most bananas you can get is max unit price * monkeys with that pricing sequence. You can track the maximum while computing a banana run to short circuit early.
Then if you order the pricings based on their expected average price, you can start short circuiting earlier using the more likely “best banana” price sequence results.
UPDATE: optimized even further - I no longer needed this strategy. Instead, I just loop through each pricing on each monkey, check to make sure it’s the first pricing seen, and add it to the total bananas in a pricing hash table of total bananas. Max on that table is the result.
Running now in about 400ms.
–
I just compute the total bananas and keep track of a pricing
In my code, it cut the number of pricing sequences additions I had to compute from brute force ~4.5M to ~118K.
For price sequence D1 - D4, the magic calculations were these:
int MinimumUnitPrice =>
Max(0, Max(0, Max(0, Max(0, 0 - D1) - D2) - D3) - D4)
+ D4 + D3 + D2 + D1;
int MaximumUnitPrice =>
Min(9, Min(9, Min(9, Min(9, 9 - D1) - D2) - D3) - D4)
+ D4 + D3 + D2 + D1;
1
adamu
In C#? This is the Elixir forum so sharing the Elixir running time would also be helpful. Elixir being immutable can be quite inefficient when doing things that involve many updates to data structures.
0
trenttobler
Yeah, it’s C#. I’m not as fluent with elixir, but here’s the immutable implementation of my latest strategy (using mostly linq query syntax – hopefully, the logic comes through):
var bananasByPricing =
from initialMonkeySecret in initialBuyerSecrets
let monkeySecrets = EvolveRep2001(initialMonkeySecret)
let bananaPricePoints =
from pricing in Pricings(monkeySecrets).DistinctBy(pricing => pricing.Key)
select (pricing.Key, bananas: pricing.Bananas)
from bananaPricePoint in bananaPricePoints
group bananaPricePoint.bananas by bananaPricePoint.Key
into pricePointBananas
select (totalBananas: pricePointBananas.Sum(), pricing: pricePointBananas.Key);
var answer = bananasByPricing.MaxBy(p => p.totalBananas);
Notes: “Pricing” key is a 4-tuple on price differences (D1-D4 values), and the “bananas” result for that price point, EvolveRep2001 generates a sequence of 2001 secrets from the initial secret. DistinctBy and MaxBy will choose the first qualifying element in the sequence.
Apologies if you wanted elixir directly - I posted more on the comment/question about possible further optimizations that might exist. My original idea was noting that the sum could potentially short circuit using an aggregation/reduce step, that could stop early rather than continuing to add more bananas once it was determined that there would not be enough remaining pricing results to exceed a current running maximum. You’re correct to point out that it could be a very different performance characteristic on elixir, and while I agree that there are some algorithms that may suffer due to pure functional immutability, I do not believe this is one of them.
0