SMFloris

SMFloris

Hackerrank optimizing euler problem #1

Hello everyone,

I spent my weekend optimising the first problem and learned allot in the process about Elixir. I got to 80 points, but still the third hidden test is timing out. Can anyone take a look at the code bellow and give me some pointers on how to improve the performance of the algorithm?

Problem is here

You can find the solution bellow; notice that I tried to parallelise as much as I could where it made sense (i.e. the solution is being computed as you input the numbers, in parallel). I don’t have allot of experience with Elixir so I would appreciate a helping hand.

defmodule Solution do

  def calculateFinalSum([{:ok, a}, {:ok, b}, {:ok, c}]) do
    a+b-c
  end

  def dividedSum(n, dividend) do
    p = div(n-1, dividend)
    div(dividend * p * (p+1), 2)
  end

  def solveOne(n) do
    {number, _} = Integer.parse(n)
    Task.async_stream([3,5,15], &(Solution.dividedSum(number, &1)))
    |> Enum.to_list
    |> Solution.calculateFinalSum
  end

  def solve() do
      IO.gets("")
      IO.stream(:stdio, :line)
        |> Task.async_stream(&(Solution.solveOne(&1)))
        |> Enum.each(fn {:ok, n} -> IO.puts(n) end)
  end
end

Solution.solve

Most Liked

idi527

idi527

:waving_hand:

Tasks seem unnecessary here. They probably cost more than the value they add over sequentially calling dividedSum/2.

AlchemistCamp

AlchemistCamp

Most Project Euler questions revolve around mathematical insight. This particular question has an O(1) solution!

A hint to point you in the right direction is to consider “triangle numbers”, or the 3rd line of Pascal’s triangle. The sum of all the numbers between 0 and 100 can be thought of as (0 + 100) + (1 + 99) + (2 + 98) + (3 + 97) … + (49 + 51) + 50. Using this sort of procedure, you can find the sum of any sequence of whole numbers from 0 to n by this equation:

(n^2)/2 + n/2, which is the same as n(n + 1) / 2

Can you think of a way to find the sum of all the numbers from 0 to n that are divisible by 3? Or the numbers divisible by 5? Or 15?

SMFloris

SMFloris

The current code, now passes all tests :smiley:

Where Next?

Popular in Challenges Top

sasajuric
Note by the Moderators: This topic is to talk about Day 5 of the Advent of Code. For general discussion about the Advent of Code 2018 an...
New
bjorng
Note: This topic is to talk about Day 4 of the Advent of Code 2019. There is a private leaderboard for elixirforum members. You can join...
New
bjorng
Note: This topic is to talk about Day 6 of the Advent of Code 2019. There is a private leaderboard for elixirforum members. You can join...
New
QuinnWilton
Note: This topic is to talk about Day 7 of the Advent of Code 2019 . There is a private leaderboard for elixirforum members. You can joi...
New
maennchen
Ok, that was a rough one today. I haven’t found a way to improve the algorithm further. Part 1 runs in .5 seconds, Part 2 in ~ 5 minutes...
New
Aetherus
The second part of today’s puzzle is very misleading. FYI, each of the ghosts has only one possible position that ends with a "Z" on its...
New
lud
Gosh this one took me sooo much time. At first I was trying to iterate each digit independently on the input A number to make digits cha...
New

Other popular topics Top

nobody
Hi! In PHP: $_SERVER[‘SERVER_ADDR’] - in Elixir? Searched the docs for ip address and the web, no good results. Thanks!
New
vertexbuffer
Hello, can anybody help here..? I have a list of players and I what to delete an element, but every for loop the list is reverting to ori...
New
dogweather
I wrote this comment on r/haskell, and it’s not popular there. :wink: But I think I’m on to something… Haskell reminds me of Java, and e...
New
sergio_101
I am VERY much an elixir newbie. I have taken one elixir course and one phoenix course on Udemy. During that course, I saw the instructor...
New
siddhant3030
Hi, I have to write a raw query for one of my project. But till now I have used ecto queries and don’t have much experience writing raw ...
New
senggen
Erlang/OTP 25 [erts-13.2.2] [source] [64-bit] [smp:8:8] [ds:8:8:10] [async-threads:1] 15:22:35.803 [error] gen_event {lager_file_backend...
New

We're in Beta

About us Mission Statement