sprengerjo
Codewars - Twice Linear - Optimisation issue
Hi there,
i am new to elixir, so i solved some stuff on codewars.
i ran into this kata: Twice linear | Codewars
I tried to solve storing the u in a list, and learned linked list are not a good idea to solve that thing 
I could not get it working with tuples. I will push the solutions to github asap.
My fastest solution is based on a map cache, that is still to slow, i.e.
dotest(1000000, 54381286) # ~ 6-7 seconds
dotest(100000, 2911582) # ~ 300 ms
I get a timeout after 30 of 100 random tests…
def dbl_linear(n) do
{_, un} = Enum.reduce(
1..n,
{%{0 => 1}, 1},
fn (i, {u, un}) ->
x = Integer.floor_div((un - 1), 2)
y = Integer.floor_div((un - 1), 3)
xx = binary(x, u, 0, i - 1)
yy = binary(y, u, 0, i - 1)
un = 1 + Kernel.min(2 * xx, 3 * yy)
u = Map.put(
u,
i,
un
)
{
u,
un
}
end
)
un
end
defp binary(0, _, _, _), do: 1
defp binary(_, cache, lb, ub) when ub - lb <= 1 do
%{^ub => un} = cache
un
end
defp binary(un, cache, lb, ub) do
mid = lb + (
(ub - lb)
>>> 1)
%{^mid => mid_v} = cache
if mid_v > un do
binary(un, cache, lb, mid)
else
binary(un, cache, mid, ub)
end
end
Most Liked
peerreynders
Really?
Spoiler
defmodule Twice do
defp next_y(x),
do: 2 * x + 1
defp next_z(x),
do: 3 * x + 1
defp next(store, [], value, fun) do
[x | source] = :lists.reverse([value | store])
{[], source, fun.(x)}
end
defp next(store, [x | source], value, fun) do
{[value | store], source, fun.(x)}
end
defp helper(0, value, _, _, _, _, _, _) do
value
end
defp helper(index, _, y_store, y_source, y, z_store, z_source, z) when y < z do
{ny_store, ny_source, ny} = next(y_store, y_source, y, &next_y/1)
helper(index - 1, y, ny_store, ny_source, ny, [y | z_store], z_source, z)
end
defp helper(index, _, y_store, y_source, y, z_store, z_source, z) when y >= z do
{nz_store, nz_source, nz} = next(z_store, z_source, z, &next_z/1)
{ny_store, ny_source, ny} =
if y > z do
{[z | y_store], y_source, y}
else
next(y_store, y_source, y, &next_y/1)
end
helper(index - 1, z, ny_store, ny_source, ny, nz_store, nz_source, nz)
end
def dbl_linear(index),
do: helper(index, 1, [], [], 3, [], [], 4)
end
IO.inspect(:timer.tc(Twice, :dbl_linear, [100_000])) # {19802, 2911582}
IO.inspect(:timer.tc(Twice, :dbl_linear, [1_000_000])) # {212929, 54381286}
Refined version:
Spoiler
defmodule Twice do
defp next_y(x),
do: 2 * x + 1
defp next_z(x),
do: 3 * x + 1
defp next(store, [], fun) do
[x | seq] = :lists.reverse(store)
{[], seq, fun.(x), x}
end
defp next(store, [x | seq], fun) do
{store, seq, fun.(x), x}
end
# 1.) The current value goes into y_store
# regardless of where it came from (y or z)
# 2.) A value coming out of y_seq goes into z_store
defp helper(0, value, _, _, _, _, _, _) do
value
end
defp helper(index, _, y_store, y_seq, y, z_store, z_seq, z) when y < z do
{ny_store, ny_seq, ny, x} = next([y | y_store], y_seq, &next_y/1)
helper(index - 1, y, ny_store, ny_seq, ny, [x | z_store], z_seq, z)
end
defp helper(index, _, y_store, y_seq, y, z_store, z_seq, z) when y >= z do
yy_store = [z | y_store]
{ny_store, ny_seq, ny, zz_store} =
if y > z do
{yy_store, y_seq, y, z_store}
else
# skip over duplicate value
{n_store, n_seq, n, x} = next(yy_store, y_seq, &next_y/1)
{n_store, n_seq, n, [x | z_store]}
end
{nz_store, nz_seq, nz, _} = next(zz_store, z_seq, &next_z/1)
helper(index - 1, z, ny_store, ny_seq, ny, nz_store, nz_seq, nz)
end
def dbl_linear(index),
do: helper(index, 1, [], [], 3, [], [], 4)
end
IO.inspect(:timer.tc(Twice, :dbl_linear, [100_000])) # {16420, 2911582}
IO.inspect(:timer.tc(Twice, :dbl_linear, [1_000_000])) # {185478, 54381286}
3
Popular in Challenges
This topic is about Day 9 of the Advent of Code 2020 .
Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/le...
New
This is my second year doing AoC in Elixir and my first year doing it with Livebook.
When I was doing just plain Elixir I usually set up...
New
A frustrating one for me. I spent a long time trying to understand why some combinations resulted in fewer presses and struggled to keep ...
New
I spent 3 hours struggling in part 2, until I noticed a very basic mistake :joy:
Here’s my code:
https://github.com/Aetherus/advent-of-...
New
Anyone else think the prompt for this challenge is contradictory?
The rules for comparing packets include
If both values are lists, c...
New
Today’s challenge is quite interesting. I ended up using Zipper to solve this problem. Maybe I overengineered quite a bit.
The data stru...
New
Note: This topic is to talk about Day 9 of the Advent of Code 2019.
There is a private leaderboard for elixirforum members. You can join...
New
Finished Day 1 with Elixir :tada:
Here’s my code:
#!/usr/bin/env elixir
defmodule Combination do
@doc "Yields each combination of 2...
New
Trying to get more facility with dynamic programming concepts on Leetcode and having an issue I can’t find a way around. It’s a chutes an...
New
Thought I’d kick today’s thread off!
Parsing
Enum rocks, so most of my code was actually in parsing input.
▶ Preprocessing input
Part 1...
New
Other popular topics
Hello!
tl;dr Announcing Oban, an Ecto based job processing library with a focus on reliability and historical observability.
After spen...
New
As promised, the first release candidate of Phoenix 1.3.0 is out! This release focuses on code generators with improved project structure...
New
I believe there are people here who are dealing with CSV files import on the daily basis, and since Excel is a really popular tool there ...
New
I have a phoenix application from which a user can download multiple(5-6) files of size 1MB. I couldn’t find anything related to sending ...
New
Hello, I have map which I want to convert it to string like this:
the map:
%{last_name: "tavakkoli", name: "shahryar"}
the string I ne...
New
Surface is an experimental library built on top of Phoenix LiveView and its new LiveComponent API that aims to provide a more declarative...
New
I’ve read in another post that it may be possible with a router helper - but I couldn’t find an appropriate one, and tbh, I’m still just ...
New
Hi!
In PHP: $_SERVER[‘SERVER_ADDR’] - in Elixir?
Searched the docs for ip address and the web, no good results.
Thanks!
New
In the code below, if the create action is not set to accept “extra_key” as an input, it errors out with a message shown above. Is there ...
New
I want to highlight html closing tags when i click a html tag. That works in .html files but doesnt work for html.eex templates. How can...
New
Latest on Elixir Forum
Sponsor Spotlight
Catch errors, track performance, monitor hosts and more.
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #channels
- #elixirconf
- #exunit
- #discussion
- #code-sync
- #javascript
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixir-ls
- #phoenix_html
- #iex
- #blog-post
- #graphql
- #genstage
- #ai
- #websockets
- #supervisor
- #advent-of-code
- #elixirconf-us
- #distillery
- #processes
- #forms
- #api
- #metaprogramming
- #security
- #performance
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Error tracking for Elixir devs who love to ship. Start your free account.
Develop your skills with books, videos, and courses.
Producing high quality Elixir screencasts since 2017.
Enabling companies to succeed by building software people love.
The team behind Membrane, Popcorn, LiveDebugger. Available for hire.
Courses that'll move you from confusion to "Aha, now I get it!"