The following is a set of problems that I organized with some friends at work in 2018.
This is an interesting one because the infinite sequence below converges to a number that relates to π. There are several ways to prove that although I like this one the most https://www.youtube.com/watch?v=d-o3eB9sfls.
1/1 + 1/4 + 1/9 + 1/16 + … = π / 6
Write a function mypi that takes a single argument n and returns the value of π.
There are a couple of ways to implement this function - most conventionally a for-loop if you are used to iterative programming style. Once you have the correct solution, try to implement it with functional programming techniques… perhaps you can do it with a single line of code!
An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. For example, the word “dog” can be rearranged into "god". Or for example, the word “binary” can be rearranged into "brainy".
Write a function that returns true if the provided two words are anagrams, or returns false otherwise. Don’t overthink this. Perhaps it can be written in a single line of code?
For example:
is_anagram(“iceman”, “cinema”) # true
is_anagram(“dog”, “cat”) # falseHere’s the extra credit. You gain an additional golden star if you complete this 2nd part.
A list of dictionary words can be downloaded here https://github.com/tk3369/words/raw/master/words.txt. Write a function download_words that downloads the file, lowercase everything, and returns the words as an array. Then, write a function find_anagrams that finds all related anagrams for a word e.g.
julia> find_anagrams("iceman", words)
3-element Array{String,1}:
"anemic"
"cinema"
"iceman"Monte Carlo simulation is a technique to solve numerical problem using random numbers. For example, we can find the area of the half-triange in a 1x1 square by "throwing random darts" to the square. Logically, if the random numbers come from a uniform distribution, then we should have approximately 50% of the darts landing in the triangle, and we can infer that the area of the triange is just 0.5 (half of the area of the 1x1 square.)
Let’s find the area under the curve between x = 0 and x = 1, given the following function:
f(x) = sin(pi * x)
Write a function sine_area that uses Monte Carlo simulation to find the area under the curve. The function should take a single argument for the number of simulations. What is the value of sine_area(10000)?
P.S. For those who love math, prove that your answer is correct by solving the same problem using Calculus.
Recursion is a fundamental computational technique that can make code beautiful and clean. Many mathematical functions can be expressed in a recursive manner naturally.
What to do:
- Write a recursive function
mygcd(x::Int, y::Int)that finds the greatest common divisor of two positive integers. - Benchmark your function against Julia and/or Python's built-in
gcdfunction using the example below.
Here's the logic –
The GCD of two positive numbers p and q is the same as the GCD of q and the remainder of p divided by q, for every p > q.
Example:
mygcd(102, 68) = 34
Test your code against these:
mygcd(20, 25) = 5
mygcd(4789084, 957196) = 388
The Collatz problem is defined as follow, for n ∈ 0, 1, 2, ...
a{n} = a{n-1} / 2 if a{n-1} is even
a{n} = 3 * a{n-1} + if a{n-1} is odd
So, starting with a number a{n-1}, we can find the next number a{n} using the formula above. Amazingly, for any positive starting number, the sequence will always return to 1. For example, the sequence starting with 7 is {7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1}, which takes 16 steps.
What to do:
- Write a function
find_collatz(s::Int)that returns the starting number a0 for which it takes exactlyssteps to reach the value of 1. Submit your answer withfind_collatz(500). - Benchmark your solution using BenchmarkTools and see how fast it runs.
It’s year 2099, the world is coming to an end. The aliens from the most distant galaxy GN-Z11 finally find a way to travel to our planet in a split second using “spooky action at a distance” technique. As the aliens have more advanced weapons, the civilization on earth is doomed…..
Fortunately, our world coalition leaders came to a meeting and negotiated a deal with the aliens. The aliens are craving computer algorithms and if we are able to write a fast enough algorithm to solve the following problem then they have agreed to leave and never come back again!
So what do we do? Let’s work together to save the world!
Write a function merge(x::Vector{Int}, y::Vector{Int}) that combines two sorted arrays into a single sorted array. An easy way to check if you have a fast enough program is when you are able to match or beat the built-in sort functions in Julia. Do your performance benchmark using BenchmarkTools.
For performance benchmarking, create your own input data of 1mm random positive integers as follows:
x = sort(rand(1:1_000_000, 1_000_000))
y = sort(rand(1:1_000_000, 1_000_000))
Bitcoin is going crazy these days and mining a new coin is becoming more and more difficult. Why chase after the hot stuff? We have something easier here!
Introducing the Julian Coin - it's easy to mine and it's based upon a common hashing algorithm called MD5. Each coin can be discovered from a secret. To start mining, concatenate the secret with a positive integer and run it through the MD5 hashing algorithm. You get the coin by finding the smallest number that gives you a hash code both starting and ending with 3 zeros. (You may use any MD5 library.)
For examples:
- Secret
hellorequires6144434to get the coin - Secret
juliarequires1436069to get the coin
Let's prove it from the Unix terminal:
$ echo -n "hello6144434" | md5sum
0006a1061ece946b7e95c2af73773000
$ echo -n "julia1436069" | md5sum
000d02cb0a523a25820ea72bb959d000
Can you mine the Julian Coin with secret "western"? Write a function mine_julian_coin(s::String) that returns the number and the corresponding hash code for the western Julian coin:
julia> mine_julian_coin("hello")
(key = 6144434, hash = "0006a1061ece946b7e95c2af73773000")Oh no! Mr. Bee took too much alcohol from the graduation party last night. When it got home, it suddenly limped along the beehive in all directions for several hours before it finally fell asleep at some unknown location. Now, it just wakes up and wants to find its way home but it doesn't even know how far his home is! Can you help?
The beehive is very big and it has no boundary. Luckily, the surveillance camera captured everything and logged every move Mr. Bee made along the way. The log can be found in:
Although Mr. Bee was quite drunk, its instinct only directed it 6 different ways from a hexagon:
- n - North
- s - South
- nw - North West
- ne - North East
- sw - South West
- se - South East
Let's assume that every adjacent cell is exactly 1 unit apart. Can you write a program that calculates how many units Mr. Bee is away from its home?
Due to elevated security concerns, we have decided to send all emails in an encrypted form! We will build a simple cipher to encode and decode messages with a passcode.
From an integer passcode, we can derive the shift variable n as follows:
𝑛 = (𝑝 mod 80) + 5
Here’s the task -
- Create a function
encode(s::String, passcode::Int)that encodes the stringsby shiftingnpositions forward using the ASCII table in the range 0x21 (exclamation mark) and 0x7E (tilda).
- If it the shifted position passes the last character in the range then it wraps around and starts from the beginning.
- If the character is originally out of range then do not do any translation and keep it the same.
- Create a function
decode(s::String, passcode::Int)that decodes the stringsby shiftingnpositions backward.
For examples:
encode("Hello", 9783) = "d#**-"
decode("d#**-", 9783) = "Hello"
Submit your code with the output of encode("Julia Rocks!") and decode the output to see if you get back the same thing.
Prime numbers were once considered boring (except for mathematicians) until public cryptography became popular in 1960's. Nowadays, people compete to find the largest prime number! The Sieve of Sundaram is a simple algorithm to find prime numbers up to a specific integer.
Write a function find_primes_sundaram(upto::Int) that returns an array of prime numbers up to the specified value. How many prime numbers are they that are less than 100,000?
If you start with $1 and, with each move, you can either double your money or add another $1, what is the smallest number of moves you have to make to get to a target amount?
Write a function grow(target::Int) that returns
- Minimum number of steps to reach the target
- A respective string that shows how to reach the target
- An illustrated path that shows the actual money growth to the target
For example, to get to a target of $10:
julia> grow(10)
(steps = 4, instructions = "+*+*", path = [1, 2, 4, 5, 10])What is the shortest path to reach a target of $123,456?