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
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 && {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 && {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 && {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 && 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 &&
find_value(xy_map, val, {nil, row, nil}, feat) == nil &&
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