Leetcode

Alternate characters from two strings

https://leetcode.com/problems/merge-strings-alternately/

category: array / string

level: easy

defmodule Merger do
  defp alternately([], word2, _, result), do: Enum.reverse(result) ++ word2

  defp alternately(word1, [], _, result), do: Enum.reverse(result) ++ word1

  defp alternately([pick | word1rest], word2, 1, result),
    do: alternately(word1rest, word2, 2, [pick | result])

  defp alternately(word1, [pick | word2rest], 2, result),
    do: alternately(word1, word2rest, 1, [pick | result])

  def merge_alternately(word1, word2) when is_binary(word1) and is_binary(word2),
    do: alternately(to_charlist(word1), to_charlist(word2), 1, []) |> to_string
end

"apbqcr" = Merger.merge_alternately("abc", "pqr")
"apbqrs" = Merger.merge_alternately("ab", "pqrs")
"apbqcd" = Merger.merge_alternately("abcd", "pq")

Greatest common divider of strings

https://leetcode.com/problems/greatest-common-divisor-of-strings/description/

category: array / string

level: easy

defmodule Divider do
  def gcd_of_strings(str1, str2) when is_binary(str1) and is_binary(str2) do
    maxlength = min(String.length(str1), String.length(str2))

    Enum.reduce_while(maxlength..1//-1, "", fn len, acc ->
      # are both str1 and str2 length divisable by len?
      if rem(String.length(str1), len) == 0 and rem(String.length(str2), len) == 0 do
        substr = String.slice(str1, 0..(len - 1)//1)
        # String.duplicate might not be memory efficient for long strings
        if String.starts_with?(str2, substr) and
             String.duplicate(substr, div(String.length(str2), len)) == str2 and
             String.duplicate(substr, div(String.length(str1), len)) == str1,
           do: {:halt, substr},
           else: {:cont, acc}
      else
        {:cont, acc}
      end
    end)
  end
end

"ABC" =
  Divider.gcd_of_strings(
    "ABCABC",
    "ABC"
  )

"AB" =
  Divider.gcd_of_strings(
    "ABABAB",
    "ABAB"
  )

"TAUXX" =
  Divider.gcd_of_strings(
    "TAUXXTAUXXTAUXXTAUXXTAUXX",
    "TAUXXTAUXXTAUXXTAUXXTAUXXTAUXXTAUXXTAUXXTAUXX"
  )

Helper: NumberPriorityQueue

A general purpose module named NumberPriorityQueue for some of the Leetcode assignments.

# Priority queue. Like heap_min/heap_max but implemented with list as queue.
# Init with new(), use push to add numbers, use pop_min to pop off the smallest number,
# and pop_max for the maximum number.
defmodule NumberPriorityQueue do
  defstruct min_value: nil,
            max_value: nil,
            queue: [],
            # maintain queue_length to avoid list traversals
            queue_length: 0

  def new(), do: %NumberPriorityQueue{}
  def length(%NumberPriorityQueue{} = state), do: state.queue_length
  def empty?(%NumberPriorityQueue{} = state), do: state.queue_length == 0

  def push(num, %NumberPriorityQueue{} = state) when is_number(num) do
    max_value =
      if state.queue_length > 0, do: max(state.max_value, num), else: num

    %NumberPriorityQueue{
      min_value: min(state.min_value, num),
      max_value: max_value,
      queue: [num | state.queue],
      queue_length: state.queue_length + 1
    }
  end

  defp min_max_and_length(num, {nil, nil, l}), do: {num, num, l + 1}
  defp min_max_and_length(num, {mi, ma, l}), do: {min(mi, num), max(ma, num), l + 1}

  def remove(nil, %NumberPriorityQueue{} = state), do: {nil, state}

  def remove(num, %NumberPriorityQueue{} = state) do
    new_list = List.delete(state.queue, num)
    {new_min, new_max, new_length} = Enum.reduce(new_list, {nil, nil, 0}, &min_max_and_length/2)

    {num,
     %NumberPriorityQueue{
       min_value: new_min,
       max_value: new_max,
       queue: new_list,
       queue_length: new_length
     }}
  end

  def pop_min(%NumberPriorityQueue{} = state), do: remove(state.min_value, state)
  def pop_max(%NumberPriorityQueue{} = state), do: remove(state.max_value, state)
  def peek_min(%NumberPriorityQueue{} = state), do: state.min_value
  def peek_max(%NumberPriorityQueue{} = state), do: state.max_value
end

:ok

Kth largest element

https://leetcode.com/problems/kth-largest-element-in-an-array/description

category: heap / priority queue

level: medium

# Keep the K largest numbers in the queue.
# The minimal value in the queue is the K-th largest element.
alias NumberPriorityQueue, as: PQ

defmodule KthLargestElement do
  def solve(number_list, k) do
    {start_list, rest} = Enum.split(number_list, k)
    initial_pq = Enum.reduce(start_list, PQ.new(), &PQ.push/2)

    Enum.reduce(rest, initial_pq, fn val, pq ->
      if val > PQ.peek_min(pq) do
        {_num, new_pq} = PQ.pop_min(pq)
        PQ.push(val, new_pq)
      else
        pq
      end
    end)
    |> PQ.peek_min()
  end
end

5 = KthLargestElement.solve([3, 2, 1, 5, 6, 4], 2)
4 = KthLargestElement.solve([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)

Find median from data stream

https://leetcode.com/problems/find-median-from-data-stream/description/

category: heap / priority queue

level: hard

# This median finder accepts all integer/float numbers, including negative numbers.
# It is not optimized for a particular range of integers.
# Assumed is that the median must be available after each change; 
# most of the work is done in the insert_num function.
# 
# This solution has O(n) time complexity and O(n) space complexity.
# All the numbers of the data stream are kept in memory, and this is needed for 
# solution to work if the numbers are not limited to a certain range and
# the stream size is not known in advance.
#
# Two lists are maintained; biggest and smallest numbers. The list sizes are kept
# in balance, so the median can be calculated by looking at the maximum of the 
# smallest numbers and the minimum of the biggest numbers.
#
# The first number will be put in the list of smallest numbers.

alias NumberPriorityQueue, as: PQ

# This structure holds all the state for the inserted numbers.

defmodule MedianState do
  defstruct smallest_numbers: PQ.new(),
            biggest_numbers: PQ.new()
end

defmodule MedianFinder do

  def new(), do: %MedianState{}
  
  # The function keeps two queue lengths in balance (same size ± 1);
  # to do that it can move one number from one queue to another.
  # The two queue lengths should differ at most 2 when this function is called.
  defp rebalance(state) do
    cond do
      PQ.length(state.biggest_numbers) > PQ.length(state.smallest_numbers) + 1 ->
        {min_of_biggest_numbers, new_pq} = PQ.pop_min(state.biggest_numbers)

        %MedianState{
          biggest_numbers: new_pq,
          smallest_numbers: PQ.push(min_of_biggest_numbers, state.smallest_numbers)
        }

      PQ.length(state.smallest_numbers) > PQ.length(state.biggest_numbers) + 1 ->
        {max_of_smallest_numbers, new_pq} = PQ.pop_max(state.smallest_numbers)

        %MedianState{
          smallest_numbers: new_pq,
          biggest_numbers: PQ.push(max_of_smallest_numbers, state.biggest_numbers)
        }

      true ->
        state
    end
  end

  def insert_num(%MedianState{} = state, num) do
    cond do
      num < PQ.peek_max(state.smallest_numbers) ->
        rebalance(%{
          state
          | smallest_numbers: PQ.push(num, state.smallest_numbers)
        })

      num > PQ.peek_min(state.biggest_numbers) ->
        rebalance(%{
          state
          | biggest_numbers: PQ.push(num, state.biggest_numbers)
        })

      PQ.length(state.biggest_numbers) >= PQ.length(state.smallest_numbers) ->
        %{
          state
          | smallest_numbers: PQ.push(num, state.smallest_numbers)
        }

      true ->
        %{
          state
          | biggest_numbers: PQ.push(num, state.biggest_numbers)
        }
    end
  end

  def get_median(%MedianState{} = state) do
    cond do
      PQ.empty?(state.smallest_numbers) ->
        nil

      PQ.length(state.biggest_numbers) == PQ.length(state.smallest_numbers) ->
        (PQ.peek_max(state.smallest_numbers) + PQ.peek_min(state.biggest_numbers)) / 2

      PQ.length(state.biggest_numbers) > PQ.length(state.smallest_numbers) ->
        PQ.peek_min(state.biggest_numbers) * 1.0

      true ->
        PQ.peek_max(state.smallest_numbers) * 1.0
    end
  end
end

:ok

# test the MedianFinder

# input
numbers = [6, 10, 2, 6, 5, 0, 6, 3, 1, 0, 0]

# expected output
medians = [6.0, 8.0, 6.0, 6.0, 6.0, 5.5, 6.0, 5.5, 5.0, 4.0, 3.0]

testdata = Enum.zip(numbers, medians)

initial_state = MedianFinder.new()

Enum.reduce(testdata, initial_state, fn {num, median}, state ->
  new_state = MedianFinder.insert_num(state, num)
  ^median = MedianFinder.get_median(new_state)
  new_state
end)

Container with most water

https://leetcode.com/problems/container-with-most-water/description/

category: two pointers

level: medium

defmodule WaterContainer do
  def solve(_heights, leftpos, rightpos, max, solution) when leftpos >= rightpos do
    {max, solution}
  end

  def solve(heights, leftpos, rightpos, max, solution) do
    leftheight = Enum.at(heights, leftpos)
    rightheight = Enum.at(heights, rightpos)
    area = (rightpos - leftpos) * min(leftheight, rightheight)

    solution =
      if area > max do
        {leftpos, rightpos}
      else
        solution
      end

    area_max = max(max, area)

    if leftheight < rightheight do
      solve(heights, leftpos + 1, rightpos, area_max, solution)
    else
      solve(heights, leftpos, rightpos - 1, area_max, solution)
    end
  end

  def max_area(heights) do
    {max, solution} = solve(heights, 0, length(heights) - 1, 0, nil)
    IO.inspect(solution, label: "Left and right position")
    max
  end
end

heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]

WaterContainer.max_area(heights)

Max number of vowels in substr

https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/

category: sliding window

level: medium

count_vowels = fn text ->
  Enum.filter(text, fn ch -> Enum.member?(~c"aeiou", ch) end) |> Enum.count()
end

k = 7
input = "weallloveyou"
4 = Enum.chunk_every(to_charlist(input), k, 1, :discard) |> Enum.map(count_vowels) |> Enum.max()

Helper: Bisect left/right

Some Python solutions use Bisect. The module below is used as replacement.

# Instead of bisect; it does not use binary search, but output is like bisect_left/right.
# Input must be a flatten sorted list.
# Search position in sorted list for a new value to be added in the sorted list.
# left_insert_pos: prefers left side for equal numbers
# right_insert_pos: prefers right side for equal numbers
defmodule SortPos do
  defp left([], _search, pos), do: pos
  defp left([key | _remain], search, pos) when key >= search, do: pos
  defp left([_key | remain], search, pos), do: left(remain, search, pos + 1)

  def left_insert_pos(nums, search), do: left(nums, search, 0)

  defp right([], _search, pos), do: pos
  defp right([key | _remain], search, pos) when key > search, do: pos
  defp right([_key | remain], search, pos), do: right(remain, search, pos + 1)

  def right_insert_pos(nums, search), do: right(nums, search, 0)
end

SortPos.right_insert_pos([1, 2, 2, 4], 2)

Longest increasing subsequence

https://leetcode.com/problems/longest-increasing-subsequence/description/

level: medium

category: dynamic programming

needed for some other leetcode problems

https://blog.finxter.com/5-best-ways-to-find-the-length-of-the-longest-increasing-subsequence-in-python/

Solution 1 - using recursion

Suboptimal solution but easier to understand and to adjust.

# Recursion without memoization.
# memoization could be done with key: {prev_num, cursor_pos} and passing and returning it in lis_util.
# Only solution length is printed, not the numbers, but this could also be added. 

defmodule LIS do
  def lis_util(_nums, _prev, [], _pos), do: 0

  def lis_util(nums, prev_num, [cursor_num | remaining], cursor_pos) do
    taken =
      if cursor_num <= prev_num,
        do: 0,
        else: 1 + lis_util(nums, cursor_num, remaining, cursor_pos + 1)

    not_taken = lis_util(nums, prev_num, remaining, cursor_pos + 1)
    max(taken, not_taken)
  end

  def length_of_lis(nums), do: lis_util(nums, -99999, nums, 0)
end

5 = LIS.length_of_lis([10, 9, 2, 101, 5, 105, 3, 103, 7, 109, 13, 111, 12])

Solution 2 - using a sorted list

from stackoverflow, translated from Python to Elixir.

https://stackoverflow.com/questions/3992697/longest-increasing-subsequence

#
# Multiple solutions are possible, but this algorithm finds at most one.
#
defmodule LongestIncreasingSubsequence do
  defp update_predecessor_map(predecessor, pos, _end_elements) when pos < 0, do: predecessor

  defp update_predecessor_map(predecessor, pos, end_elements) do
    Map.put(predecessor, pos, Enum.at(end_elements, pos))
  end

  # param is called nums, but it works for anything that can be ordered.
  defp solve(nums) do
    # end_elements is a sorted list of increasing elements.
    # predecessor is a map containing the longest sequence until now (keeps 1 solution at most).
    Enum.reduce(nums, {%{}, []}, fn num, {predecessor, end_elements} ->
      # instead of inserting the new num, the position j will be used for replacing.
      # end_elements will always be kept sorted.
      j = SortPos.left_insert_pos(end_elements, num)

      new_end_elements =
        if j == length(end_elements) do
          end_elements ++ [num]
        else
          List.replace_at(end_elements, j, num)
        end

      {update_predecessor_map(predecessor, j - 1, end_elements), new_end_elements}
    end)
  end

  def length_of_lis(nums) do
    {_predecessor, end_elements} = solve(nums)

    length(end_elements)
  end

  def lis(nums) do
    {predecessor, end_elements} = solve(nums)

    solution_length = length(end_elements)

    # add the last element to the solution
    sequence_map = update_predecessor_map(predecessor, solution_length - 1, end_elements)

    # convert map to list, with the values in the increasing order
    Enum.map(0..(solution_length - 1)//1, fn i -> sequence_map[i] end)
  end
end

["aa", "bb", "cc"] = LongestIncreasingSubsequence.lis(["aa", "dd", "bb", "cc"])

[2, 3, 7, 14, 16] =
  LongestIncreasingSubsequence.lis([9, 2, 101, 5, 105, 3, 103, 7, 109, 111, 15, 14, 16])

Russian doll envelopes

https://leetcode.com/problems/russian-doll-envelopes/description/

categorie: apply Longest Increasing Subsequence

level: hard

alias NumberPriorityQueue, as: PQ

envelopes = [[5, 4], [6, 4], [6, 5], [6, 7], [2, 3]]

# envelopes = [[2, 3],[2,4],[2,5]]
# first sort on width and descending on heigth
sorted_list =
  Enum.sort(envelopes, fn [w1, h1], [w2, h2] -> if w1 == w2, do: h1 > h2, else: w1 < w2 end)

heights = Enum.map(sorted_list, fn [_width, height] -> height end)

lis = LongestIncreasingSubsequence.lis(heights)

# print envelopes
Enum.reduce(sorted_list, lis, fn [width, height], lis ->
  case lis do
    [search_height | other_lis] when height == search_height ->
      IO.inspect([width, height], label: "Envelope")
      other_lis

    acc ->
      acc
  end
end)

length(lis)

Helper: divisor

Used to calculate greatest common divider and lowest common multiple.

# first some utilities
defmodule Divisor do
  def divisors(num) when num > 0 and is_integer(num) do
    until = trunc(:math.sqrt(num))

    Enum.reduce(1..until//1, [], fn test_divisor, divisor_list ->
      if rem(num, test_divisor) == 0 do
        other = div(num, test_divisor)

        if other == test_divisor do
          [test_divisor | divisor_list]
        else
          [test_divisor, other | divisor_list]
        end
      else
        divisor_list
      end
    end)
  end

  def common_divisor([]), do: []

  def common_divisor([1 | _]), do: [1]

  # it's more efficient if you put the smallest number first in the list of nums
  def common_divisors(nums) do
    [a_num | other_nums] = nums

    # search divisors of all nums. Result is sorted big to small
    Divisor.divisors(a_num)
    |> Enum.sort(:desc)
    |> Enum.filter(fn test_divisor ->
      Enum.all?(other_nums, fn num -> rem(num, test_divisor) == 0 end)
    end)
  end

  def greatest_common_divisor(sorted_nums) do
    Divisor.common_divisors(sorted_nums) |> List.first()
  end

  def lowest_common_multiple([num]), do: num
  def lowest_common_multiple([num, num]), do: num

  def lowest_common_multiple([num1, num2]) when num1 > num2,
    do: lowest_common_multiple([num2, num1])

  def lowest_common_multiple([num1, num2]) when num1 < num2 do
    div(num1 * num2, greatest_common_divisor([num1, num2]))
  end

  def lowest_common_multiple([num1, num2, num3 | other_nums]) do
    lowest_of_num1_and_num2 = lowest_common_multiple([num1, num2])
    lowest_of_other_nums = lowest_common_multiple([num3 | other_nums])
    lowest_common_multiple([lowest_of_num1_and_num2, lowest_of_other_nums])
  end
end

:ok

Coin change

https://leetcode.com/problems/coin-change/description/

category: dynamic programming

level: medium

This code is longer than most solutions, but it has several optimalisations. Most solutions on leetcode.com are limited to the code in the make_dp_map function below.

defmodule CoinChange do
  defp greedy_search_but_still_optimal(coins_sorted_desc, sum) when sum >= 0 do
    # The biggest coin determines the theoretic minimum of coins that are needed,
    # so every combination that match that, are the optimal solution.
    # This greedy aproach does not look further than the combination of 2 different coins.
    Enum.reduce_while(coins_sorted_desc, {nil, nil, sum}, fn coin,
                                                             {_, minimum_of_bigger_coin, _} ->
      remainder = rem(sum, coin)
      multiple = div(sum, coin)

      if remainder == 0 and multiple <= minimum_of_bigger_coin do
        {:halt, {coin, multiple, nil}}
      else
        # because of the remainder at least one more coin is needed
        if multiple + 1 > minimum_of_bigger_coin do
          # this might be not be the optimal solution.
          # coins are sorted from big to small, at some point there is no use to search further.
          search_further = if multiple > minimum_of_bigger_coin, do: :halt, else: :cont
          {search_further, {nil, minimum_of_bigger_coin, nil}}
        else
          # simple heuristic, assuming the remainder is 1 coin
          if Enum.member?(coins_sorted_desc, remainder) do
            {:halt, {coin, multiple, remainder}}
          else
            {:cont, {nil, multiple + 1, nil}}
          end
        end
      end
    end)
  end

  defp greedy_find_theoritic_minimum(sorted_coins, amount) do
    # look if we can fill the rest to the amount with one of the biggests coins.
    # If so, we have found an optimal solution and there is no need 
    # to calculate all the in-between values.
    coins_sorted_desc = Enum.reverse(sorted_coins)

    {fill_the_rest_coin, fill_times, remainder_coin} =
      greedy_search_but_still_optimal(coins_sorted_desc, amount)

    if is_nil(fill_the_rest_coin) do
      # return theoritic minimum
      {fill_times, nil}
    else
      # success
      if is_nil(remainder_coin) do
        {fill_times, %{fill_the_rest_coin => fill_times}}
      else
        {fill_times + 1, %{remainder_coin => 1, fill_the_rest_coin => fill_times}}
      end
    end
  end

  defp dp_increase_and_keep_the_best(dp_coin_acc, val, coin, calculated_for_value_minus_coin) do
    {coins_sofar, solution_sofar} = calculated_for_value_minus_coin
    current_best = dp_coin_acc[val]

    case current_best do
      nil ->
        Map.put(dp_coin_acc, val, {coins_sofar + 1, [coin | solution_sofar]})

      {current_best_minimum, _} ->
        # less coins is better
        if coins_sofar + 1 < current_best_minimum do
          Map.put(dp_coin_acc, val, {coins_sofar + 1, [coin | solution_sofar]})
        else
          dp_coin_acc
        end
    end
  end

  defp calc_new_dp_for_value(coins_sorted_desc, dp_acc, val) do
    Enum.reduce(coins_sorted_desc, dp_acc, fn coin, dp_coin_acc ->
      calculated_for_value_minus_coin = dp_acc[val - coin]

      if is_nil(calculated_for_value_minus_coin) do
        dp_coin_acc
      else
        dp_increase_and_keep_the_best(dp_coin_acc, val, coin, calculated_for_value_minus_coin)
      end
    end)
  end

  defp make_dp_map(sorted_coins, amount, step_size) do
    smallest_coin = List.first(sorted_coins)
    coins_sorted_desc = Enum.reverse(sorted_coins)

    Enum.reduce(smallest_coin..amount//step_size, %{0 => {0, []}}, fn val, dp_acc ->
      calc_new_dp_for_value(coins_sorted_desc, dp_acc, val)
    end)
  end

  defp change_sorted_coins([], _), do: {-1, %{}}

  defp change_sorted_coins(coins, amount) do
    sorted_coins =
      Enum.filter(coins, fn coin -> is_integer(coin) and coin <= amount and coin > 0 end)
      |> Enum.sort()

    common_divisor = Divisor.greatest_common_divisor(sorted_coins)
    IO.inspect(common_divisor, label: "Greatest common divisor")

    # test if it is even possible to make the amount with the given coins
    if rem(amount, common_divisor) == 0 do
      lcm = Divisor.lowest_common_multiple(sorted_coins)
      IO.inspect(lcm, label: "Lowest common multiple")
      remainder_amount = min(rem(amount, lcm) + lcm, amount)
      biggest_coin = List.last(sorted_coins)
      biggest_coin_extra = max(div(amount, lcm) - 1, 0) * div(lcm, biggest_coin)

      {theoretic_minimum, greedy_findings} =
        greedy_find_theoritic_minimum(sorted_coins, remainder_amount)

      IO.inspect(theoretic_minimum + biggest_coin_extra, label: "At least needed")

      {coin_count_subtotal, coin_frequency_subtotal} =
        if is_nil(greedy_findings) do
          IO.inspect(remainder_amount, label: "Calculate amounts until")
          dp = make_dp_map(sorted_coins, remainder_amount, common_divisor)
          IO.inspect(Enum.count(dp) - 1, label: "Calculated amounts")

          case dp[remainder_amount] do
            nil -> {-1, %{}}
            {len, coin_list} -> {len, Enum.frequencies(coin_list)}
          end
        else
          {theoretic_minimum, greedy_findings}
        end

      if biggest_coin_extra > 0 and coin_count_subtotal >= 0 do
        coin_frequencies =
          Map.put(
            coin_frequency_subtotal,
            biggest_coin,
            Map.get(coin_frequency_subtotal, biggest_coin, 0) + biggest_coin_extra
          )

        {coin_count_subtotal + biggest_coin_extra, coin_frequencies}
      else
        {coin_count_subtotal, coin_frequency_subtotal}
      end
    else
      {-1, %{}}
    end
  end

  def change([], _), do: {-1, %{}}

  def change(coins, amount) when is_integer(amount) and amount >= 0 do
    sorted_coins =
      Enum.filter(coins, fn coin -> is_integer(coin) and coin <= amount and coin > 0 end)
      |> Enum.sort()

    change_sorted_coins(sorted_coins, amount)
  end

  def coin_change(coins, amount) do
    {len, _coins} = change(coins, amount)
    len
  end
end

:ok

# test CoinChange
{len, coins} = CoinChange.change([200, 300, 700, 900], 214300)
IO.inspect(coins, label: "Solution with coin frequencies")
len

Maximum subarray

https://leetcode.com/problems/maximum-subarray/

categorie: Kadane’s Algorithm

level: medium

defmodule Kadane do
  def max_sub_array([first_num | tail_nums]) do
    init_acc = {first_num, [first_num], first_num, [first_num]}

    {_, _, found_max, found_seq} =
      Enum.reduce(tail_nums, init_acc, fn num, {local_max, local_seq, global_max, global_seq} ->
        new_local_max = max(num, local_max + num)
        new_local_seq = if new_local_max == num, do: [num], else: [num | local_seq]
        new_global_max = max(new_local_max, global_max)
        new_global_seq = if new_global_max == new_local_max, do: new_local_seq, else: global_seq
        {new_local_max, new_local_seq, new_global_max, new_global_seq}
      end)

    IO.inspect(Enum.reverse(found_seq), label: "Sequence")
    IO.inspect(found_max, label: "with max")
    found_max
  end
end

6 = Kadane.max_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, 4])
1 = Kadane.max_sub_array([1])
23 = Kadane.max_sub_array([5, 4, -1, 7, 8])

Helper: grid conversion

Convert a list with lists, representing rows and colums and the cell value to a map with the x,y coördinates as key.

defmodule Grid do
  def listgrid_2_xymap(grid, offset \\ 0) when is_list(grid) do
    for {row, y} <- Enum.with_index(grid, offset),
        is_list(row),
        {val, x} <- Enum.with_index(row, offset) do
      {{x, y}, val}
    end
    |> Enum.into(%{})
  end

  def xymap_2_listgrid(%{} = grid, %Range{} = x_range, %Range{} = y_range) do
    for y <- y_range do
      for x <- x_range do
        grid[{x, y}]
      end
    end
  end
end

:ok

Cherry pickup

https://leetcode.com/problems/cherry-pickup/description/

category: dynamic programming

level: hard

# Solve the two paths at once, so we will know if a cherry is in both paths or not.
# Instead of a reverse path, both paths start in 0,0 and end in the right bottom corner.
# Since both paths are explored in the same pace and you cannot go back (up or left),
# One coördinate (x2) can be deduced from the others (x1,y1,y2).
# At each step the cherries are counted at a greater distance from point 0,0
# Accumulator contains the results sofar keyed by the x1,y1,y2 triplet.
defmodule CherryPickup do
  def count_cherries(grid, x1, y1, x2, y2) do
    # a thorn or outside the grid is about the same
    cherry_path1 = grid[{x1, y1}] || -1
    cherry_path2 = grid[{x2, y2}] || -1

    cond do
      cherry_path1 == -1 or cherry_path2 == -1 -> -1
      x1 == x2 and y1 == y2 -> cherry_path1
      true -> cherry_path1 + cherry_path2
    end
  end

  def update_acc_with_cherry_count(path_combination_acc, grid, prev, x1, y1, x2, y2)
      when y2 > y1 do
    # make sure y1 is equal or bigger than y2
    # IO.inspect({x1, y1, x2, y2}, label: "Crossing paths")

    path_combination_acc
    |> CherryPickup.update_acc_with_cherry_count(grid, prev, x2, y2, x1, y1)
  end

  def update_acc_with_cherry_count(path_combination_acc, grid, prev, x1, y1, x2, y2) do
    key = {x1, y1, y2}
    {prev_cherries, p1, p2} = prev

    max_sofar =
      case path_combination_acc[key] do
        nil -> nil
        {max_now, _, _} -> max_now
      end

    cherry_count = CherryPickup.count_cherries(grid, x1, y1, x2, y2)

    cond do
      cherry_count == -1 ->
        path_combination_acc

      is_nil(max_sofar) or cherry_count + prev_cherries > max_sofar ->
        Map.put(
          path_combination_acc,
          key,
          {cherry_count + prev_cherries, [{x1, y1} | p1], [{x2, y2} | p2]}
        )

      true ->
        path_combination_acc
    end
  end

  # thorn in the upper left position rules out any solution
  def most_cherries([[-1 | _t1] | _t2]), do: {0, [], []}

  def most_cherries(grid_list) when is_list(grid_list) do
    grid = Grid.listgrid_2_xymap(grid_list)
    max_y = length(grid_list) - 1
    [first_row | _] = grid_list
    max_x = length(first_row) - 1

    steps = max_x + max_y
    # number of cherries, path 1 & path 2
    cherry_at_startpos = {grid[{0, 0}], [{0, 0}], [{0, 0}]}

    bottom_right =
      Enum.reduce(1..steps//1, %{{0, 0, 0} => cherry_at_startpos}, fn _step, step_acc ->
        Enum.reduce(step_acc, %{}, fn {{x1, y1, y2}, prev}, path_combination_acc ->
          x2 = x1 + y1 - y2

          # calculate all combinations (down and right move) for both paths
          path_combination_acc
          |> CherryPickup.update_acc_with_cherry_count(grid, prev, x1, y1 + 1, x2, y2 + 1)
          |> CherryPickup.update_acc_with_cherry_count(grid, prev, x1, y1 + 1, x2 + 1, y2)
          |> CherryPickup.update_acc_with_cherry_count(grid, prev, x1 + 1, y1, x2, y2 + 1)
          |> CherryPickup.update_acc_with_cherry_count(grid, prev, x1 + 1, y1, x2 + 1, y2)
        end)
      end)

    {cherries, path1, path2} = Map.values(bottom_right) |> Enum.at(0) || {0, [], []}
    IO.inspect(cherries, label: "Cherries")

    if cherries > 0 do
      IO.inspect(Enum.reverse(path1), label: "Path       ")
      IO.inspect(path2, label: "Return path")
    end

    # Return just the number
    cherries || 0
  end
end

:ok

# tests
5 = CherryPickup.most_cherries([[0, 1, -1], [1, 0, -1], [1, 1, 1]])

0 = CherryPickup.most_cherries([[1,1,-1],[1,-1,1],[-1,1,1]])

4 = CherryPickup.most_cherries([[0, 1, -1], [1, 1, 1]])

regions_per_side = 3

for idx1 <- 1..9//1 do
    # combinations of 1, 4, 7
    regionRow = regions_per_side * div(idx1 - 1, regions_per_side) + 1;
    regionCol = regions_per_side * rem(idx1 - 1, regions_per_side) + 1;
  IO.inspect {regionCol,  regionRow}
end

x = 2..10
x.first

z = nil

z &amp;&amp; {z, 3}

Sudoku

https://leetcode.com/problems/sudoku-solver/description/

category: backtracking

level: hard

#
# Sudoku resolver for various sizes (like 4x4, 6x6, 9x9, 12x12, 16x16) till 36x36.
# Uses backtracking, but decides first in which order it is likely less work.
# In each iteration it picks the column/row/region with the most known values.
# Normally it is fast, unless there is no valid solution.
# 
# Many other solution techniques could be explored: https://sudopedia.org/wiki/Solving_Technique
# 
defmodule Sudoku do
  # General features of a Sudoku of a particular size
  defmodule Features do
    # defaults are for a 9x9 Sudoku
    defstruct cell_range: 0..8//1,
              value_range: 1..9//1,
              regions_in_topside: 3,
              region_width: 3,
              region_height: 3

    defp calc_region_with_and_height(%Range{} = cell_range, regions_in_topside) do
      width_and_height = cell_range.last + 1 - cell_range.first
      region_width = div(width_and_height, regions_in_topside)
      region_height = div(width_and_height, region_width)
      {region_width, region_height}
    end

    def new() do
      %Features{}
    end

    def new(columns, regions_in_topside) do
      # positions. zero-based index    
      cell_range = 0..(columns - 1)//1
      # for bigger than 9x9 sudoku's like 16x16: A=10 .. G=16, grid should contain 0-9 and A..G
      value_range = 1..columns//1
      {region_width, region_height} = calc_region_with_and_height(cell_range, regions_in_topside)

      %Features{
        cell_range: cell_range,
        value_range: value_range,
        regions_in_topside: regions_in_topside,
        region_width: region_width,
        region_height: region_height
      }
    end

    # end Features
  end

  defp count_value_in_col_row_region(%{} = xy_map, search_value, %Features{} = feat) do
    {column_counts, row_counts, region_counts} =
      for idx1 <- feat.cell_range, reduce: {[], [], []} do
        {column_list, row_list, region_list} ->
          # regionRow/regionCol are combinations of 0, 3, 6 in the range 0..8 with 3 sides
          # 0, 4, 8 in range 0..11
          region_start_row = feat.region_height * div(idx1, feat.regions_in_topside)
          region_start_col = feat.region_width * rem(idx1, feat.regions_in_topside)

          {column_counts, row_counts, region_counts} =
            for idx2 <- feat.cell_range, reduce: {0, 0, 0} do
              {col, row, reg} ->
                col_new = if xy_map[{idx1, idx2}] == search_value, do: col + 1, else: col
                row_new = if xy_map[{idx2, idx1}] == search_value, do: row + 1, else: row

                reg_x = region_start_col + rem(idx2, feat.region_width)
                reg_y = region_start_row + div(idx2, feat.region_width)
                reg_new = if xy_map[{reg_x, reg_y}] == search_value, do: reg + 1, else: reg

                {col_new, row_new, reg_new}
            end

          {[column_counts | column_list], [row_counts | row_list], [region_counts | region_list]}
      end

    {Enum.reverse(column_counts), Enum.reverse(row_counts), Enum.reverse(region_counts)}
  end

  defp find_value(_xy_map, _search_value, {nil, nil, nil}, _feat), do: nil

  defp find_value(xy_map, search_value, {column, _row, _region}, %Features{} = feat)
       when column != nil do
    y = Enum.find_index(feat.cell_range, fn row -> xy_map[{column, row}] == search_value end)
    y &amp;&amp; {column, y}
  end

  defp find_value(xy_map, search_value, {_column, row, _region}, %Features{} = feat)
       when row != nil do
    x = Enum.find_index(feat.cell_range, fn column -> xy_map[{column, row}] == search_value end)
    x &amp;&amp; {x, row}
  end

  defp find_value(xy_map, search_value, {_column, _row, region}, %Features{} = feat)
       when region != nil do
    region_start_row = feat.region_height * div(region, feat.regions_in_topside)
    region_start_col = feat.region_width * rem(region, feat.regions_in_topside)

    Enum.reduce_while(feat.cell_range, nil, fn idx, _acc ->
      reg_x = region_start_col + rem(idx, feat.region_width)
      reg_y = region_start_row + div(idx, feat.region_width)
      point = {reg_x, reg_y}

      if xy_map[point] == search_value do
        {:halt, point}
      else
        {:cont, nil}
      end
    end)
  end

  defp calc_region({x, y}, %Features{} = feat) do
    div(y, feat.region_height) * feat.regions_in_topside + div(x, feat.region_width)
  end

  defp decrease_counts(
         {x, y} = point,
         {column_counts, row_counts, region_counts},
         %Features{} = feat
       ) do
    region = calc_region(point, feat)
    column_count = Enum.at(column_counts, x)
    row_count = Enum.at(row_counts, y)
    region_count = Enum.at(region_counts, region)
    new_column_counts = List.replace_at(column_counts, x, column_count - 1)
    new_row_counts = List.replace_at(row_counts, y, row_count - 1)
    new_region_counts = List.replace_at(region_counts, region, region_count - 1)
    {new_column_counts, new_row_counts, new_region_counts}
  end

  defp find_candidate(
         xy_map,
         {column_counts, row_counts, region_counts},
         %Features{} = feat
       ) do
    solve_minimum =
      Enum.reduce(column_counts ++ row_counts ++ region_counts, 99, fn val, acc ->
        if val > 0 &amp;&amp; val < acc, do: val, else: acc
      end)

    search_fun = fn val -> val == solve_minimum end
    column = Enum.find_index(column_counts, search_fun)
    row = Enum.find_index(row_counts, search_fun)
    region = Enum.find_index(region_counts, search_fun)
    find_value(xy_map, ".", {column, row, region}, feat)
  end

  defp is_valid_number(xy_map, {x, y}, val, %Features{} = feat) do
    column = x
    row = y
    region = calc_region({x, y}, feat)

    find_value(xy_map, val, {column, nil, nil}, feat) == nil &amp;&amp;
      find_value(xy_map, val, {nil, row, nil}, feat) == nil &amp;&amp;
      find_value(xy_map, val, {nil, nil, region}, feat) == nil
  end

  defp int_to_value(int_val) do
    Integer.to_string(int_val, 36)
  end

  defp solve(xy_map, [], _feat), do: xy_map

  defp solve(xy_map, [point | points], %Features{} = feat) do
    # progress indicator
    IO.write(".")

    Enum.reduce_while(feat.value_range, nil, fn int_val, _acc ->
      val = int_to_value(int_val)

      if is_valid_number(xy_map, point, val, feat) do
        new_xy_map = %{xy_map | point => val}
        solved = solve(new_xy_map, points, feat)

        if solved == nil do
          # didn't work out, try next number
          {:cont, nil}
        else
          # found a solution
          {:halt, solved}
        end
      else
        # invalid number for this point, try next number
        {:cont, nil}
      end
    end)
  end

  defp determine_order(xy_map, counts, points, %Features{} = feat) do
    candidate =
      find_candidate(xy_map, counts, feat)

    if candidate == nil do
      # ready; no more points available
      Enum.reverse(points)
    else
      new_xy_map = %{xy_map | candidate => "X"}

      new_counts =
        decrease_counts(candidate, counts, feat)

      determine_order(new_xy_map, new_counts, [candidate | points], feat)
    end
  end

  defp start_solve(xy_map, %Features{} = feat) do
    counts = count_value_in_col_row_region(xy_map, ".", feat)

    # determine the order of the points to resolve the Sudoku
    points = determine_order(xy_map, counts, [], feat)

    solve(xy_map, points, feat)
  end

  # regions_in_topside is normally 3. 
  # A 16x16 sudoku has 4 regions in the topside.
  # A 4x4 or 6x6 sudoku has 2 regions in the topside
  def find_solution(board, regions_in_topside \\ 3) do
    rows = length(board)
    columns = length(List.first(board))
    true = rows == columns
    xy_map = Grid.listgrid_2_xymap(board)
    feat = Features.new(columns, regions_in_topside)
    solution = start_solve(xy_map, feat)
    IO.puts("")

    if solution == nil,
      do: nil,
      else: Grid.xymap_2_listgrid(solution, feat.cell_range, feat.cell_range)
  end
end

:ok

board = [
  ["5", "3", ".", ".", "7", ".", ".", ".", "."],
  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
  [".", "9", "8", ".", ".", ".", ".", "6", "."],
  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
  [".", "6", ".", ".", ".", ".", "2", "8", "."],
  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
  [".", ".", ".", ".", "8", ".", ".", "7", "9"]
]

expected = [
  ["5", "3", "4", "6", "7", "8", "9", "1", "2"],
  ["6", "7", "2", "1", "9", "5", "3", "4", "8"],
  ["1", "9", "8", "3", "4", "2", "5", "6", "7"],
  ["8", "5", "9", "7", "6", "1", "4", "2", "3"],
  ["4", "2", "6", "8", "5", "3", "7", "9", "1"],
  ["7", "1", "3", "9", "2", "4", "8", "5", "6"],
  ["9", "6", "1", "5", "3", "7", "2", "8", "4"],
  ["2", "8", "7", "4", "1", "9", "6", "3", "5"],
  ["3", "4", "5", "2", "8", "6", "1", "7", "9"]
]

solution = Sudoku.find_solution(board)
solution == expected

# 12x12 board. Width of each region is 4, height = 3
board = [
  ["7", ".", "B", "4", ".", "8", "1", "C", ".", ".", ".", "."],
  [".", ".", "1", "8", ".", ".", "9", ".", ".", ".", ".", "5"],
  ["6", "9", "C", ".", "5", "A", "3", "4", "1", "8", "7", "B"],
  ["3", ".", ".", ".", "8", ".", "7", ".", "4", "A", "B", "1"],
  ["1", "4", "8", ".", "A", ".", ".", ".", "5", "7", "2", "9"],
  [".", ".", "5", "7", "4", ".", ".", ".", ".", "C", "3", "8"],
  ["2", "1", "4", ".", "9", "B", "6", ".", "7", "3", "8", "C"],
  [".", "B", ".", "A", "3", "5", ".", ".", "9", ".", "6", "."],
  ["8", "6", ".", "3", "7", "4", "C", ".", ".", "5", ".", "A"],
  [".", "2", "6", ".", "C", ".", "A", "B", "8", "4", ".", "7"],
  ["5", ".", "A", ".", "1", "7", "4", "6", ".", "B", ".", "3"],
  ["4", ".", ".", "B", ".", "9", "5", ".", ".", ".", "C", "6"]
]

expected = [
  ["7", "5", "B", "4", "6", "8", "1", "C", "3", "9", "A", "2"],
  ["A", "3", "1", "8", "B", "2", "9", "7", "C", "6", "4", "5"],
  ["6", "9", "C", "2", "5", "A", "3", "4", "1", "8", "7", "B"],
  ["3", "C", "2", "9", "8", "6", "7", "5", "4", "A", "B", "1"],
  ["1", "4", "8", "6", "A", "C", "B", "3", "5", "7", "2", "9"],
  ["B", "A", "5", "7", "4", "1", "2", "9", "6", "C", "3", "8"],
  ["2", "1", "4", "5", "9", "B", "6", "A", "7", "3", "8", "C"],
  ["C", "B", "7", "A", "3", "5", "8", "1", "9", "2", "6", "4"],
  ["8", "6", "9", "3", "7", "4", "C", "2", "B", "5", "1", "A"],
  ["9", "2", "6", "1", "C", "3", "A", "B", "8", "4", "5", "7"],
  ["5", "8", "A", "C", "1", "7", "4", "6", "2", "B", "9", "3"],
  ["4", "7", "3", "B", "2", "9", "5", "8", "A", "1", "C", "6"]
]

solution = Sudoku.find_solution(board, 3)
solution == expected

# 4x4 sudoku
board = [
  [".", ".", ".", "."],
  ["1", "4", ".", "."],
  [".", ".", "1", "3"],
  [".", ".", ".", "."]
]

expected = [
  ["2", "3", "4", "1"],
  ["1", "4", "3", "2"],
  ["4", "2", "1", "3"],
  ["3", "1", "2", "4"]
]

solution = Sudoku.find_solution(board, 2)
solution == expected

# if one of these 9's in the board is changed to another number, there will be no solution,
# and finding the non-existing solution will eat all systems memory.
board = [
  ["9", ".", ".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", "9", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", "9", ".", "."],
  [".", "9", ".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", "9", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", "9", "."],
  [".", ".", "9", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", "9", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", ".", "9"]
]

Sudoku.find_solution(board)

Top 75 / 150 Leetcode questions

https://www.designgurus.io/blind75

https://leetcode.com/studyplan/leetcode-75/

https://leetcode.com/studyplan/top-interview-150/