Daily Challenge #73 - ATM Heist

A thief wants to steal from two ATMs at a very special casino.

While they mostly care about getting away with money, they are also interested in a unique fact about the ATMs at this particular casino; once a day, each ATM transfers one dollar to each other machine for each unit of distance away it is (e.g. in [0,1] both indices are 1 unit apart). Additionally, when emptied, each ATM will automatically refill with the exact same dollar amount as before, so it's possible to steal from the same ATM twice.

The thief is utlimately interested in is stealing from the two ATMs which have the highest combined total money inside, plus number of dollars each transferred to the other. Your function should return this value.

For example, if we have four ATMs: [2, 3, 4, 5], the ATM at index 0 will transfer a dollar to index 1, $2 to index 2, and $3 to index 3. Similarly, the ATM at index 2 will transfer $1 to indexes 1 and 3, and $2 to index 0.

Note that in the case above, our thief will either steal from the last ATM (index 3) twice, or steal from index 0 and index 3, because it nets her the maximum value of 10 ($5 + $5 + $0 transfer vs. $2 + $5 + $3 transfer). Either way, the answer is 10, returned as an integer.

Examples:

const atms = [3,1,3]
maximumThrill(atms) => 8 // $3 + $3 + $2 transferred between each (atms[0] and atms[2])

const atms = [2,3,4,5]
maximumThrill(atms) => 10 // $5 + $5 + $0 transferred (atms[3] and atms[3] again)

const atms = [10, 10, 11, 13, 7, 8, 9]
maximumThrill(atms) => 26 // $10 + $13 + $3 transfer between each (atms[0] and atms[3])

const atms = [2, 3, 4, 5, 10, 6, 7, 8, 9, 10, 11, 12, 4, 4, 2, 2, 12, 8]
maximumThrill(atms) => 34  // $10 + $12 + $12 transfer between each (atms[4] and atms[16])

Note: These are magic ATMs, so don't worry about accounting for whether an ATM has enough money to transfer.

Good luck!

---

This challenge comes from on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email [e-mail] with your suggestions!

Comments

[Oleksii Filonenko]

Rust:

use itertools::Itertools;

fn maximum_thrill(atms: &[i32]) -> i32 {
    atms.iter()
        .enumerate()
        .tuple_combinations()
        .map(|((i1, v1), (i2, v2))| v1 + v2 + (i1 as i32 - i2 as i32).abs())
        .chain(atms.iter().map(|atm| atm * 2))
        .max()
        .unwrap_or(0)
}

[Oleksii Filonenko]

Elixir:

defmodule Day73 do
  @spec maximum_thrill([non_neg_integer]) :: non_neg_integer
  def maximum_thrill(atms) do
    atms
    |> Enum.with_index()
    |> combinations(2)
    |> Enum.map(fn [{v1, i1}, {v2, i2}] -> v1 + v2 + abs(i1 - i2) end)
    |> Enum.concat(Enum.map(atms, &(&1 * 2)))
    |> Enum.max(fn -> 0 end)
  end

  @spec combinations(coll :: [any], size :: pos_integer) :: [[any]]
  defp combinations(_, 0), do: [[]]
  defp combinations([], _), do: []

  defp combinations([head | tail], size) do
    tail
    |> combinations(size - 1)
    |> Enum.map(&[head | &1])
    |> Enum.concat(combinations(tail, size))
  end
end