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

:wave:

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:

SMFloris

SMFloris

Hello,

@AlchemistCamp, This is exactly what I am using here, its a bit hidden by the optimizations I tried to make. If you read carefully, I do: 3*(1+2+…+n/3)+5*(1+2+…+n/5)-15*(1+2+…+n/15), where 1+2+…+n/3 and the other series are calculated using the formula Sn = n*(n+1)/2.

@idi527, Indeed, you were correct. Getting rid of the tasks solved my issues. This was the winning solution:

defmodule Solution do

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

  def solveOne(n) do
    Solution.dividedSum(n, 3)+Solution.dividedSum(n, 5)-Solution.dividedSum(n, 15)
  end

  def solve() do
      {lines, _ }= IO.gets("") |> Integer.parse
      for _ <- 1..lines do
        {number, _} = IO.gets("") |> Integer.parse
        number
        |> Solution.solveOne
        |> IO.puts
      end
  end
end

Solution.solve

Thanks for the help! In the end, I overcomplicated things.

Where Next?

Popular in Challenges Top

sasajuric
Note: This topic is to talk about Day 12 of the Advent of Code. For general discussion about the Advent of Code 2018 and links to topics...
New
Aetherus
This topic is about Day 3 of the Advent of Code 2020 . Thanks to @egze, we have a private leaderboard: https://adventofcode.com/2020/le...
New
bjorng
Note: This topic is to talk about Day 25 of the Advent of Code 2019. There is a private leaderboard for elixirforum members. You can joi...
New
bjorng
This topic is about Day 5 of the Advent of Code 2021. We have a private leaderboard (shared with users of Erlang Forums ): https://adve...
New
Aetherus
This topic is about Day 7 of the Advent of Code 2020 . Thanks to @egze, we have a private leaderboard: https://adventofcode.com/2020/le...
New
stevensonmt
Anyone else think the prompt for this challenge is contradictory? The rules for comparing packets include If both values are lists, c...
New
bjorng
My solution finishes both parts in 5 seconds on my computer. That time should be possible to reduce by optimizing my rather naive tilt/2 ...
New
rugyoga
Fairly straightforward Dijkstra’s algorithm import AOC aoc 2023, 17 do def compute(input, candidates) do {{max_row, max_col}, ite...
New
code-shoily
Just did part 1. Part 2 seems to be demanding too much of my reading time so will get to that after I am done with some chores. Oh here ...
New
christhekeele
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 Top

JDanielMartinez
Hi! May someone helps me, please! I have two apps into an umbrella project: the first one is Database, which manages queries, and the se...
New
peerreynders
Manning 2016 Halloween weekend sale via Deal of the Day Friday, October 28 - Half off all MEAPs - code WM102816LT Saturday, October 29 ...
326 29600 154
New
William
I would like to know that is there any online source for learning Phoenix Framework for building E-Commerce Store? Any advantage on build...
New
fireproofsocks
I’m working on defining a simple Ecto schema for a table (in PostGres), but I don’t see where I can define a column as NOT NULL. Conside...
New
script
If I have a string “1000 cfu/ml” . I want to remove the characters and / and space . So the string is like this "1000" What is the ...
New
freewebwithme
Using vs code and installed ElixirLS: support and debugger. And I got an error popped up on start up says Failed to run ‘elixir’ comma...
New
myronmarston
The Elixir Typespec docs show the following syntax for keyword lists in typespecs: # ... | [key: type] # keyword lis...
New
electic
Hi, I am new to Elixir. I am trying to use the DateTime component to insert a date into MySQL however the there seems to be no way to fo...
New
Patoshizzle
After calling mix ecto.create I get this error: 17:00:32.162 [error] GenServer #PID&lt;0.412.0&gt; terminating ** (Postgrex.Error) FATAL...
New
vrod
I am using the Starship cross-shell prompt – it seems pretty nice, but I get some errors: [WARN] - (starship::utils): Executing command ...
New

We're in Beta

About us Mission Statement