Skip to content

Latest commit

 

History

History
718 lines (629 loc) · 34.9 KB

README.md

File metadata and controls

718 lines (629 loc) · 34.9 KB
Raw

header

Welcome to A December of Algorithms (2019). After the overwhelming response from last year, we present you with a new collection of algorithms to implement this December. Each Day, Each Algorithm ;) Finish them all to get prizes and certificate :)

Send a pull request only after completing all 31 algorithms.

Please submit all PRs on or before January 10th 11:59 PM IST.

What Do I Do?

We have a small collection of algorithms, one for every day of the month. Scroll down to take a look at them. All you need to do is fork this repository, implement all 31 algorithms and send a pull request over to us. Check out our FAQ for more information.

Index

Algorithms

December 1 - Sevenish Number

  • Problem
    • Let us now define what we mean by a sevenish number.
    • A "sevenish" number is a natural number which is either a power of 7, or the sum of unique powers of 7
    • The first 5 sevenish numbers are: 1, 7, 8, 49, 50.
    • Now, implement an algorithm to find the nth sevenish number.
  • Example 
    > sevenish_number(1)
  1
> sevenish_number(5)
  50
> sevenish_number(10)
  350
  • Optional Task
    • Create a Dynamic Programming solution to reduce the time complexity of your algorithm (if you used a brute-force approach before).
  • Resources

December 2 - Is this a valid credit card number?

  • Problem
    Are credit card numbers just a random combination of the digits from 0-9? NO!
    Credit card numbers are a systematic combination of numbers that can satisfy a single test. This test is created so that errors can be avoided while typing in credit card numbers as well as detect counterfeit cards!

    The algorithm is as follows:

    • Reverse the order of the digits in the number.
    • Take the first, third, ... and every other odd digit in the reversed digits and sum them to form the partial sum s1
    • Taking the second, fourth ... and every other even digit in the reversed digits:
      • Multiply each digit by two and sum the digits if the answer is greater than nine to form partial sums for the even digits
      • Sum the partial sums of the even digits to form s2
    • If s1 + s2 ends in zero then the original number is in the form of a valid credit card number as verified by the Luhn test.

    Reverse the digits:
61789372994
Sum the odd digits:
  6 + 7 + 9 + 7 + 9 + 4 = 42 = s1
The even digits:
    1,  8,  3,  2,  9
  Two times each even digit:
    2, 16,  6,  4, 18
  Sum the digits of each multiplication:
    2,  7,  6,  4,  9
  Sum the last:
    2 + 7 + 6 + 4 + 9 = 28 = s2

s1 + s2 = 70 which ends in zero which means that 49927398716 passes the Luhn test

    Your task is to implement to check if a given credit card number is valid or not using the above algorithm.

  • Example

    Input : 49927398716
Output: 49927398716 passes the test

  • Resources

December 3 - The Decimation

  • Problem
    • Well, this is day 3 so let's start with something easy. Perhaps an algorithm that might involve a list and the Marvel Supervillain Thanos!
    • While the list isn't sorted, snap half of all things (remove them from the list). Proceed until the list is sorted or only one item remains (which is sorted by default). This sorting algorithm may give varied results based on implementation.
    • The item removal (decimation) procedure is up to the implementation to decide, but the list should be half as long as before after one pass of the item removal procedure.
    • Your algorithm may commit to take away either the first half of the list, the last half of the list, all odd items, all even items, one at a time until the list is half as long, or any not specified above.
    • Decide for yourself: What would Thanos do if the universe carried an odd amount of living things? hello
    • The list is sorted if no elements are smaller than any previous item. Duplicates may exist in the input and may exist in the output.
  • Example 
    // A sorted list remains sorted
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
// A list with duplicates may keep duplicates in the result
[1, 2, 3, 4, 3] -> [1, 3, 3] // Removing every second item
[1, 2, 3, 4, 3] -> [3, 4, 3] -> [4, 3] -> [3] // Removing the first half
[1, 2, 3, 4, 3] -> [1, 2] // Removing the last half
  • Resources

December 4 - Dr. Bruce Banner's H-Index

  • Problem
    • Dr. Bruce Banner is a soft-spoken scientist and among Earth's most brilliant men. At this moment though, he needs your help to find his h-index.
    • In academia, the h-index is a metric used to calculate the impact of a researcher's papers. It is calculated as follows:
    • A researcher has index h if at least h of his N papers have h citations each. If there are multiple h satisfying this formula, the maximum is chosen.
    • For example, suppose N = 5, and the respective citations of each paper are [4, 3, 0, 1, 5]
    • Then the h-index would be 3, since the researcher has 3 papers with at least 3 citations.
    • Given a list of paper citations of Dr. Bruce Banner, calculate his h-index.
  • Example 
    > h_index(5, [4,3,0,1,5])
  3
> h_index(6, [4,5,2,0,6,4])
  4
  • Resources

December 5 - Convert CSV data to a HTML table

  • Problem
    • A comma-separated values (CSV) file is a delimited text file that uses a comma to separate values. A CSV file stores tabular data in plain text. Each line of the file is a data record. Each record consists of one or more fields, separated by commas.
    • Data in a CSV file is not very easy to understand. Your task is to read data from a CSV file and convert into a code for a HTML table and store it another file with a .html extension. Use the CSV file given in the resources to build your algorithm.
  • Example
    • CSV 
      column1,column2,column3
a,123,abc123
b,234,bcd234
c,345,cde345
    • HTML 
      <html>
    <body>
        <table>
            <tr><th>column1</th><th>column2</th><th>column3</th></tr>
            <tr><td>a</td><td>123</td><td>abc123</td></tr>
            <tr><td>b</td><td>234</td><td>bcd234</td></tr>
            <tr><td>c</td><td>345</td><td>cde345</td></tr>
        </table>
    </body>
</html>
  • Resources

December 6 - Fibonacci Prime Number Generation

  • Problem
    • Fibonacci Numbers are a series of numbers where each number is the sum of preceding 2 numbers.
    • Henry wants to generate prime numbers present in the Fibonacci Series. He needs your help to generate them.
      • For example, suppose N = 3
    • Then the series will have 3 Fibonacci prime numbers : 2,3,5
    • Given the count of prime numbers needed by Henry , compute the series for him.
  • Example 
      Enter the value for (n): 5
  
  Generated Fibonacci Prime Number Generation upto (5): 
  2, 3, 5, 13, 89
  • Resources
  • Fun Facts on Fibonacci
    • Every positive integer can be written in a unique way as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers. This is Zeckendorf Theorem.
    • Any three consecutive Fibonacci numbers, taken two at a time, are relatively prime.
    • No Fibonacci number greater than 8 is one greater or one less than any prime number.

December 7 - Queued up

  • Problem
    • A medical clinic assigns a token number to every patient who visits. The token number starts from 1 and it is given based on the order of arrival, to the n patients who arrive. But, the receptionist accepts bribe and lets a person k in first. The task is to print the token number and the patient's name in the order in which they see the doctor.
    • Implement the concept of Queues to solve this problem
  • Example
	Enter N: 5
	Enter (token no, id):
	(1, a)
	(2, b)
	(3, c)
	(4, d)
	(5, e)
	Enter k: c
	The order is:
	(3, c)
	(1, a)
	(2, b)
	(4, d)
	(5, e)

December 8 - Cheating Probability

  • Problem
    • Given an RxC Matrix in which each element represents the Department of a student seated in that row and column in an examination hall, write a code to calculate the probability of each student copying if a person from the same department sits:
      • In front of him = 0.3
      • Behind him = 0.2
      • To his left or right = 0.2
      • In any of his 4 closest diagonals = 0.025
  • Example
    • Input 
       CSE ECE CSE 
 ECE ECE CSE
    • Output 
      0.0 0.225 0.2
0.225 0.5 0.3
  • Resources

December 9 - One to One?

  • Problem
    • In mathematics a one to one function is that which has a unique element in the range for every corresponding domain.
    • Let there be a function f: X->Y such that if a,b belong to X and if f(a)=f(b) then a=b. This proves the one to one property of a function. If there exists more than one "X's" for the same "Y's" then the function is not one to one.
    • Your task is to write a program that accepts two sets of numbers and the relationship between them and evaluate if they are indeed a one-one function.
  • Example 
    Set 1: {1,2,3,4}
Set 2: {1,4,9,16}
Function: x^2
Result: It is one-one.

    Set 1: {1,-1,2,-2,3,-3,4,-4}
Set 2: {1,4,9,16}
Function: x^2
Result: It is not one-one.
  • Optional
    • Prove that the function is onto and hence bijective.
  • Resources

December 10 - Count The Cookies

  • Problem

    • Tipsie, a cookie store sells cookies in jars. Each jar has one cookie in them. The store gives a free cookie if the customer returns enough cookie jars.
    • For example, if a customer Alex has n=15 to spend on jars of cookie that cost p=3 each. He can turn in c=2 cookie jars to receive another cookie.
    • Initially, he buys 5 cookies and has 5 jars after eating them. He turns in 4 of them, leaving him with 1, for 2 more cookies.
    • After eating those two, he has 3 cookie jars, turns in 2 leaving him with 1 cookie jar and his new cookie. 
    • Once he eats that one, he has 2 cookie jars and turns them in for another cookie. After eating that one, he only has 1 cookie, and his shopping ends. Overall, he has eaten 5+2+1+1=9 cookies.
    • The integers n, p and c represent money to spend, cost of a cookie, and the number of cookie jars he can turn in for a free cookie respectively.
    • Implement a function cookieCount(n, p, c) to count the number of cookies Alex could buy.

  • Example

    > cookieCount(10, 2, 5)
  6
> cookieCount(12, 4, 4)
  3

  • Resources

December 11 - Is This A Valid Email Address

  • Problem
    • While signing up for a website, you must have seen that when an invalid email address is entered, you get a warning. This is because the website validates the given email address according to some specification of a valid email address (check the resources section to know the format of a valid email address).
    • Now, for today's challenge implement your own email address verification algorithm.
    • For the sake of simplicity, assume that a valid email address has the following format:
      • local_part@domain
      • The local_part should contain only alphabets, numbers and the characters: _, ., -.
      • The domain should contain only alphabets followed by .com
  • Example 
    // Valid email addresses
[email protected]
[email protected]
  • Optional Problem
    • Implement an algorithm to verify an email address based on the complete syntax specification (given in the resources section).
  • Resources
  • Still stuck?

December 12 - Show JaSON the way

  • Problem
    • Jason is stranded in a desert.His phone's battery is going to die out and all he has left is a compass.
    • Parse the JaSON.json(in src/res) file and get the latitude and longitude values of the current and destination location.
    • Also find the distance between those two locations (refer resources for the link)
    • Return a Directions json file with your personalized message, distance and some direction.
  • Example
    • JaSON.json(src/res):
    {
 "markers": 
 [
 	{
 		"name": "start",
 		"location": [25.1212, 55.1535],
 	},
 	{
 		"name": "destination",
 		"location": [25.2285, 55.3273]
 	}
 ]
}
    • Sampl- Inpute Output:
    {
 "directions": 
 [
 	  {
 	    "message": "Meet at the destination point",
 	    "distance": 21.17,
 	    "direction": "N"
 	  }
 ]
}
  • Resources
  • Note
    JSON format can differ and values like message and direction are totally upto you.

December 13 - Toggling Switches

  • Problem

    • There are n switches labeled from 1 to n,to turn on/off n bulbs.
    • At start all the bulbs are switched off
    • At first round, every bulb is turned on
    • At second round, every second switch is turned off
    • At third round, every third switch is toggled on/off (on->off and off->on)
    • This goes on and during nth round, every nth switch is toggled on/off.
    • The task is to write O(n) and constant time functions to find how many switches are in the on state (two separate functions).
    • [optional] Find the switch nos. that are in the 'on' state after n such iterations.

  • Example

Enter no of switches: 5
     
Iteration 0: 1->off  2->off  3->off  4->off  5->off
Iteration 1: 1->on   2->on   3->on   4->on   5->on
Iteration 2: 1->on   2->off  3->on   4->off  5->on
Iteration 3: 1->on   2->off  3->off  4->off  5->on
Iteration 4: 1->on   2->off  3->off  4->on   5->on
Iteration 5: 1->on   2->off  3->off  4->on   5->off

No of switches in the 'on' state at the end: 2

December 14 - A Wordplay with Vowels and Consonants

  • Problem
    • There are two players A and B. Initially, they are given the same string s.
    • They have to make substrings with letters in 's'.
    • A makes substrings starting with a vowel(a,e,i,o,u) and B makes substrings starting with consonants.
    • For each occurence of their substring in 's', the players get 1 point.
    • The task is to find who has the maximum score and what's the winner's score for a string 's'.
  • Example 
    String: london
A's score:7 (o,on,ond,ondo,ondon)
B's score:14 (l,lo,lon,lond,londo,london,n,nd,ndo,ndon,d,do,don) 
The winner is B with 14 points
  • Format 
    Enter string: monkey
The winner is B with 14 pts
  • Resources

December 15 - Intruder Alert

  • Problem
    • Rick Sanchez just discovered that someone from another planet has been intruding into his private planet use its resources.
    • In order to lure that person in to humiliate him, Rick decides to send a dish as a gift. This dish has been cooked with a balance between its main ingredients: Animal A and Liquid B.
    • If for every 1g of A 1ml of B has to be added, write a code that uses Backtracking to print the number of ways the ingredients can be added when the quantity of A needed is provided.
  • Example 
    Quantity of A(in grams): 2
Combinations: [AABB, ABAB]
Quantity of A(in grams): 3
Combinations: [AAABBB, AABABB,AABBAB,ABAABB,ABABAB]
  • Resources

December 16 - Casino Royale

  • Problem
    • In poker, players form sets of five playing cards, called hands, according to the rules of the game. Each hand has a rank, which is compared against the ranks of other hands of all those in the game and the highest hand wins all the money that everybody puts in.
    • A poker hand is specified as a space separated list of five playing cards:
    • Each input card has two characters indicating face and suit. For example: 2d (two of diamonds).
      • Faces are: a, 2, 3, 4, 5, 6, 7, 8, 9, 10, j, q, k
      • Suits are: h ♥️ (hearts), d ♦️ (diamonds), c ♣️ (clubs), and s ♠️ (spades)
    • Create a program to parse a single five card poker hand and specify the poker hand ranking and produce one of the following outputs.
     straight-flush
 four-of-a-kind
 full-house
 flush
 straight
 three-of-a-kind
 two-pair
 one-pair
 high-card
 invalid
  • Example 
     2h  2h  2h  kc  qd:  three-of-a-kind
 2h  5h  7d  8c  9s:  high-card
 ah  2d  3c  4c  5d:  straight
 2h  3h  2d  3c  3d:  full-house
 2h  7h  2d  3c  3d:  two-pair
 2h  7h  7d  7c  7s:  four-of-a-kind 
 10h jh  qh  kh  ah:  straight-flush
 4h  4s  ks  5d  10s: one-pair
 qc  10c 7c  6c  4c:  flush
  • Resources

December 17 - Subway Surfer

  • Problem

    • Many metro train systems across the world have multiple lines. These lines often meet each other at few stations called interchanges. Commuters often change lines at interchanges based on their destination.

    • In the above diagram we can observe that if we want to travel between Greenwich station and the Airport we have to travel for 10 stations in the red line : GREENWICH -> SUNTECH -> MARINA -> CENTRAL -> CITY HALL -> BAY -> MUSEUM -> RIVERFRONT -> DOWNTOWN -> AIRPORT

    • However if the passengers switch trains to the blue line in CENTRAL station they can save time and reach their destination faster: GREENWICH -> SUNTECH ->MARINA -> CENTRAL -> ZOO -> ESTATE ->AIRPORT

    • Write a program that accepts two ordered arrays of railway lines and calculates the fastest route possible between two stations.

  • Example 
    Enter Train Lines, Start and Endpoint:
Line 1: Park, Central, Beach, Mylapore, Kilpauk
Line 2: Central, T.Nagar, Washerampet, MKB Nagar.
Start: Park
End: T.Nagar

    Fastest Path: Park ->Central -> T.nagar
  • Resources

December 18 - Your Password is too WEAK

  • Problem
    • Brute Force Attack is the simplest password cracking method. This attack simply tries to use every possible ASCII printable characters (character code 32-126) combination as a password. Brute Forcing takes time but the chances of getting it right is certain.
    • The problem is to calculate the time taken to find the password given that you know the length of the password string using Brute Force and Multithreading. Note: Brute Forcing doesn't work in real life.
  • Example
Enter Password: T!Kk@
Time Taken: 6723.45 seconds

December 19 - Periphery of a lake

  • Problem
    • Reshwin wants to experience the scenic view of the kolleru lake from the periphery of the lake.
    • Given a set of random points (which also contains the points which lie in the periphery of the lake), Reshwin has to find the points which lie in the periphery of a lake to traverse the outer limits of the lake.
    • Develop an algorithm to help Reshwin
  • Example
{{0, 3}, {2, 2}, {1, 1}, {2, 1}, {1, 2},{3, 0}, {0, 0}, {3, 3}}

The outer limits are - {{0, 3}, {0, 0}, {3, 0}, {3, 3}}

December 20 - 100 days of summer

  • Problem
    • Nitya wants to visit a number of cities in her summer vacation.
    • Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.
    • The input is in the form of a matrix where the indices represent the city number and the value in the matrix represents the distance between the two cities
    • The output is the least distance
  • Example
    For four cities A,B,C,D the input will be in the following format (Note: The matrix is symmetric since the distance from A->B is the distance from B->A)
    • Input
    	A	B	C	D
 A	0km	40km	10km	30km			

 B	40km	0km	20km	10km	

 C	10km	20km	0km	50km		

 D	30km	10km	50km	0km
    • Output
    The shortest distance is 70km
  • Resources

December 21 - Marching Partners

  • Problem
    • Nikhil wants to organise a procession with his students.
    • In this procession, two students will walk side-by-side in each row.
    • Nikhil expects that the height difference of the two students who walk in each row should not exceed a certain threshold. That is, two students can be paired as long as their height difference does not exceed d.
    • If there are n students in the class in which the ith student is H[i] units tall, pair the maximum number of students corresponding to the above condition.
    • Note: A student cannot be part of more than one pair.
    • Implement a function marching_partners(n, H, d) that prints the maximum number of pairs that can be formed.
  • Example 
    > marching_partners(5, [147,149,149,155,150], 2)
  2
  • Explanation
    • The 5 students have heights 147, 149, 149, 155 and 150 respectively. The maximum allowed difference in the heights of two students forming a pair is at most 2. It is clear that the 4th student (height 155) cannot be paired with any other student. The remaining 4 students can be paired as (1st and 3rd) and (2nd and 5th) to form 2 pairs.
  • Resources

December 22 - Alternating Balls

  • Problem
    • There are N balls arranged in a row. They are either red or blue in colour.
    • A sub-row is said to be alternating if any two adjacent balls are of different colours.
    • For each ball located at position x (from 1 to N), compute the length of the longest alternating sub-row that starts at x.
    • Implement a function alt_balls(N,arr) that outputs the length of the longest alternating sub-row for each x from 1 to N.
  • Example 
    > alt_balls(4, [B,B,B,B])
  1 1 1 1
> alt_balls(4, [B,R,B,R])
  4 3 2 1
> alt_balls(6, [B,B,B,R,B,B])
  1 1 3 2 1 1
  • Explanation
    • Case 1: No two balls have different colours, so any alternating sub-row may only consist of a single ball.
    • Case 2: Every sub-row is alternating.
    • Case 3: The only alternating sub-row of length 3 is from position 3 to 5.
  • Resources

December 23 - Finding the centroid of a polygon

  • Problem
    • Given a set of vertices, write a function to find the centroid of a closed polygon.
    • Centroid of a polygon is its geometric centre.
    • It can be determined by referencing the Shoelace Formula.
  • Example 
    Vertices={{3,4},{5,2},{6,7}}
Centroid={4.66,4.33}

Vertices={{0,4},{0,0},{4,0},{4,4}}
Centroid={2,2}

Vertices={{0,0},{0,40},{80,40},{80,90},{0,90},{0,120},{120,120}}
Centroid={66.9,65}

    Case 1: 
Centroid is calculated using centroid of a triangle formula.

Case 2:
Centroid for a square is point of intersection of its diagnols.

Case 3:
Centroid is calculated for irregular polygons by calculating seperate summation of areas and 
dividing them for x and y coordinates.

Maintainers

FAQ:

Who can join the Challenge?

Anyone who is passionate about coding and can dedicate a little time a day for the challenge for the next 31 days.

When should I submit the pull request?

You don't need to submit it everyday. Just submit it once you're done with all 31 algorithms.

What if I'm not able to code every day?

Not a problem. While coding every day is nice, we understand that other commitments might interfere with it. Plus its holiday season. So you don't have to solve one problem every day. Go at your own pace. One per day or 7 a week or even all 30 in a day.

What language should I use to code?

Anything! New to C? Best way to practice it. Wanna find out what all this hype about Python is? Use it! Any and all languages are welcomed. Maybe you could try using a different language for every problem as a mini-challenge?

Fork? Pull request? What is all that? I don't know how to use GitHub!

If you are new to Git or GitHub, check out this small tutorial from our team and GitHub

Where are the rest of the problems?

Our code ninjas are hard at work preparing the rest of the problems. Don't worry, they'll be up soon.

How should I complete these programs?

We have a folder for each day of the month. Simply complete your code and move the file into that folder. Be sure to rename your file to the following format: language_username or language_username_problemname Some examples: python_exampleUser.py c_exampleUser.c Please do not modify any existing files in the repository.

I forked the repository but some problems were added only after that. How do I access those problems?

Not to worry! Open your nearest terminal or command prompt and navigate over to your forked repository. Enter these commands:

git remote add upstream https://github.com/SVCE-ACM/A-December-of-Algorithms-2019.git
git fetch upstream
git merge upstream/master

If you're curious, the commands simply add a new remote called upstream that is linked to this repository. Then it 'fetches' or retrieves the contents of the repository and attempts to merge it with your progress. Note that if you've already added the upstream repository, you don't need to re-add it in the future while fetching the newer questions.

I received a merge error. What do I do?

This shouldn't happen unless you modify an existing file in the repository. There's a lot of potential troubleshooting that might be needed, but the simplest thing to do is to make a copy of your code outside the repository and then clone it once again. Now repeat the steps from the answer above. Merge it and then add your code. Now proceed as usual. :)

I'm facing difficulties with/need help understanding a particular question.

Open up an issue on this repository and we'll do our best to help you out.

[Back to Top]

wave