After overwhelming responses from previous years, we present you with a new collection of algorithms to implement this December.
Each Day, Each Algorithm ;)
Finish them all to get a certificate :)
Send a pull request only after completing all 31 algorithms.
Please submit all PRs on or before January 15th 11:59 PM IST.
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.
- December 1 - William Butcher's Mission
- December 2 - The Secret Language
- December 3 - Minesweeper
- December 4 - Industry
- December 5 - Don’t let Mason misspend!
- December 6 - Swapped
- December 7 - Word Map
- December 8 - Aptitude Check!
- December 9 - Kochouseph Konundrum!
- December 10 - Play with words
- December 11 - Monkey jump
- December 12 - Shez in a Maze!
- December 13 - The Labyrinth
- December 14 - Math Mystery
- December 15 - The Murderers Meet
- December 16 - H2O Receptacle
- December 17 - Zig Zag Conversion
- December 18 - Find the way
- December 19 - Hidden Anagram
- December 20 - Code a Subsequence
- December 21 - The Devil Towers
- December 22 - The Markowitz Paradox
- December 23 - Meeting Rooms
- December 24 - Cracking The Safe
- December 25 - The Motorbike Race
- December 26 - Circulate
- December 27 - Mission to Earth: Re-Calibrated
- December 28 - The Journey to the Eternal Engine
- December 29 - Candies
- December 30 - Precise Portion
- December 31 - The Quad of Queens
- FAQ
The mission of William Butcher and his crew is to free the US from the control of Supes. The Supes are seeking to destabilize the country by infiltrating the military in an effort to influence the administration.
A refugee in the United States from Asia, a Supe, was able to get away from the concentration camps. A crew member who was originally from Spain had an unplanned encounter with them and sought to make up with her despite having trouble understanding her when she tried to speak with the crew.
After careful analysis, MM discovered that she had employed a string of Hexadecimal characters and digits.
Design an algorithm to help the crew fully comprehend her hints.
Input:
1
{ 56, 6F, 75, 67, 68, 74}
Output: Vought
Input:
2
{ 49, 6E, 76, 61, 64, 65}
{4D, 69, 6C, 69, 74, 61, 72, 79}
Output:
Invade
Military
The first line of input will specify the number of words (n).
The subsequent 'n' lines will specify the word to be translated, where each letter is separated by a comma.
Leonard and Sheldon are the best of friends. They know each other so well that they even developed their own language to exchange secret messages. However, they have recently made a new friend, Raj, who has difficulty understanding the two when they communicate in their language.
Leonard and Sheldon’s language is similar to Pig Latin. Their unique language consists of usual English words transformed by shifting the first two letters in a word to the end and adding a suffix 'ae'.
Help Raj translate and decode his friends' secret messages.
Input: kipediawiae
Output: wikipedia
Input: ammargrae
Output: grammar
- References
Consider a minefield made up of # and -, where each hash (#) represents a mine and each dash (-) represents a mine-free spot. Display the minefield where each dash is replaced by the number of mines immediately adjacent to the spot (horizontally, vertically, and diagonally).
Input:
5
["-", "-", "-", "-", "-"],
["-", "-", "-", "-", "-"],
["-", "-", "#", "-", "-"],
["-", "-", "-", "-", "-"],
["-", "-", "-", "-", "-"]
Output:
["0", "0", "0", "0", "0"],
["0", "1", "1", "1", "0"],
["0", "1", "#", "1", "0"],
["0", "1", "1", "1", "0"],
["0", "0", "0", "0", "0"],
Input:
5
["-", "#", "-", "-", "#"],
["-", "-", "-", "-", "-"],
["-", "-", "#", "-", "-"],
["-", "#", "-", "-", "#"],
["-", "#", "-", "-", "#"]
Output:
["1", "#", "1", "1", "#"],
["1", "2", "2", "2", "1"],
["1", "2", "#", "2", "1"],
["2", "#", "3", "3", "#"],
["2", "#", "2", "2", "#"]
The first line of input shows the number of rows and columns of the minefield (2D array).
The next line(s) of input show the minefield with the mines and the mine-free spots.
["0", "0", "0", "0", "0"],
["0", "1", "1", "1", "0"],
["0", "1", "#", "1", "0"],
["0", "1", "1", "1", "0"],
["0", "0", "0", "0", "0"],
The output should contain the arrays of digits showing number of mines immediately adjacent (horizontally, vertically and diagonally) to a given position in the array.
- References
Harper is a graduate at a bank called Pierpoint, the first assignment given to her by her boss, Eric, is to analyse the stock market rise and fall for a given set of stock market change values for n days. She must submit a report to Eric highlighting the period of time when the company should sell to maximise their profit, she must also mention the profit value.
Given a set of values, help Harper gather the necessary data for her report.
Input:
No. of days: 5
Given stock market change values: { 5,4,-1,7,8}
Output:
Profit Value: 23
Proposed days to sell: Day: 1 to Day: 5
Stock market Change Values: {5,4,-1,7,8}
Input:
No. of Days:19
Given stock market change values: { 5,-4,12,-2, -5, 6, -2,-3, 1, 5, -6,-11,7,-31,9,2,-3,8,-5 }
Output:
Profit Value: 16
Proposed days to sell: Day: 15 to Day: 18
Stock market Change Values: {9, 2, -3, 8}
The first line of input is the number of days Harper is going to consider for her analysis.
The second line of input is the stock market change values for those given days.
In order to find the best period of time to sell in order to maximise profit,
Harper must find the maximum sum of all the stock change values in every possible subset of days from the given set.
In the given sample input, it is found that out of all the subsets obtained, the one having the maximum sum was the entire set as a whole.
And thus, the company will be able to make maximum profit if they sell on all the days in that given period of time.
MASON is a motoring enthusiast and he owns a sports bike . With the price of petrol going up and down in a pattern , MASON is worried whether his salary would be sufficient to meet his needs apart from fueling his bike . So he decides to calculate how much he spends on fueling his bike per month. Help MASON calculate his fuel expenditure. If he spends more than 10 PERCENTAGE of his INCOME give him a warning message reading “EXPENDITURE EXCEEDING LIMIT”
-
MASON fuels his bike twice a day .
-
The PRICE of the fuel is x/l initially.
-
Every third day the price goes up by 3 rupees .
-
Every fifth day the price goes down by 2 rupees .
-
On the other days the price of the fuel remains x/l.
-
Help him to calculate his expense for a period of one month (31DAYS) .
-
Check whether the expenditure is more than 10 percent of his income .
-
His income is 50,000 rupees per month.
Input:
fuel_price=75
Output:
Expenditure=4686
“EXPENDITURE WITHIN LIMIT”
Input:
fuel_price=97
Output:
Expenditure=6050
“EXPENDITURE EXCEEDING LIMIT”
The input is the rate of the fuel in the beginning of the month.
The output is the amount he must spend on fueling his bike.
If the expenditure exceeds 10% of the income (i.e greater than 5000), then an alert message must be displayed.
Bob and Tanika are best friends. They were bored so they decided to play a game. The game they chose to play involved a set of ‘n’ positive numbers. The player who goes first must choose a position ‘p’ and their turn ends with that. In the subsequent turns, the player must first subtract the value in the first position by 1 and swap it with the value in position ‘p’. The players will take alternate turns and the game goes on till the value in the first position becomes 0. The player whose turn it is loses the game when the value in the first position becomes 0. Determine the winner of the game if both players play optimally and display the winner's name.
Input:
Position=3
Set of numbers: 5 4 4
Player going first: Tanika
Output:
Tanika wins the game!
Bob loses the game!
1) 5 4 4 (initial)
Tanika chooses position 3
2) 4 4 4 (bob)
5-1, swapping (5-1) with value in position 3 (4)
3) 4 4 3 (tanika)
4) 3 4 3 (bob)
5) 3 4 2 (tanika)
6) 2 4 2 (bob)
7) 2 4 1 (tanika)
8) 1 4 1 (bob)
9) 1 4 0 (tanika)
10) 0 4 0 (bob)
Since, on bob's turn the initial value at the first position is 0, he loses the game.
- References
You are given a grid made up of random characters. Given a word, your task is to determine whether the word can be constructed from the given grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Input:
COMMUNICATION
Output:
Found
Input:
DOCUMENT
Output:
Not Found
Input:
MEDIATION
Output:
Found
You are required to construct the given grid in the form of a 2D array of characters.
All the characters must be either in uppercase.
The dimensions of the grid are 15x15.
The input is a single word.
The output is "Found" if the input word is found in the grid else it is "Not Found".
Arshith is a pre-final year student preparing for his aptitude, technical and interview rounds as part of his placement training.
He has come across a mind-boggling problem statement that integrates a coding problem with a logical question as specified below:
In a specific language, “DEMOCRACY” is coded as “EDOMRCCAY".
Help Arshith develop a way to translate any given word to that particular language. Compute it using any approach of programming.
Input: UNCOPYRIGHTABLE
Output: NUOCYPIRHGATLBE
Input: SPEEDRUNNER
Output: PSEERDNUENR
Kochouseph Chittilappilly went to Dhruv Zplanet , a gaming space, with his friends and played a game called “Guess the Word”.
Rules of the game are –
Computer displays some strings on the screen and the player should pick one string / word if this word matches with the random word that the computer picks then the player is declared as Winner.
Kochouseph Chittilappilly’s friends played the game and no one won the game. This is Kochouseph Chittilappilly’s turn to play and he decided to win the game. What he observed from his friend’s game is that the computer is picking up the first string whose length is odd and is of maximum length.
Due to system failures computers sometimes cannot generate odd length words. In such cases you will lose the game irrespective of whether you guess the right word or not and it displays “better luck next time”.
Write a program to help Kochouseph win the game.
Input:
5
Hello Good Morning Welcome You
Output :
Morning
Input:
3
Go to hell
Output :
Better luck next time
The first line of input is the number of words in the given string.
The second line of input is the string of words.
The output is the word chosen by the computer.
A group of students were playing a word game. They divided themselves into teams and had 4 rounds.
One round was the pronunciation round. One team challenged the other team to pronounce “schtschurowskia”. It was difficult for both the teams to pronounce the word. They approached their teacher for help. He gave them a hint.
Have a look at the hint!
Hint: A word is hard to pronounce if it contains 4 or more consonants in a row; otherwise it is easy to pronounce.
For example, "apple" and "polish" are easy to pronounce, but "schtschurowskia" is hard to pronounce. After giving them an example, he asked them to solve the following problem.
Given: A string S consisting of N lowercase Latin characters.
To Determine: Whether it is easy to pronounce or not based on the rule above — print YES if it is easy to pronounce and NO otherwise. For the purposes of this problem, the vowels are the characters {a,e,i,o,u} and the consonants are the other 21 characters. Help them solve the problem.
Input:
5
5
apple
15
schtschurowskia
6
polish
5
tryst
3
cry
Output:
YES
NO
YES
NO
YES
Input Format:
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains a single integer N, the length of string S.
The second line of each test case contains the string S.
Output Format:
For each test case, output on a new line the answer — YES if S is easy to pronounce, and NO otherwise.
Each character of the output may be printed in either uppercase or lowercase. For example, the strings YES, yeS, yes, and YeS will all be treated as identical.
Constraints:
1≤T≤100
1≤N≤100
S contains only lowercase Latin characters, i.e, the characters {a,b,c…….z}
A list is provided with a sequence of characters 
. The character ‘_’ represents land and the character ‘~’ represents water. A monkey can move 1 step or 2 steps in a single jump. Another list provided here contains the step that the monkey took Eg[1,1,2,1,2]. Whenever the monkey touches the water. The game is over and the score must be returned. Calculate the jumps the monkey took before touching the water.
Input 1:
[‘_’,’~’,’_’,’_’,’_’,’_’,’~’,’_’,’_’,’~’,’_’,’~’]
[2,1,1,1,2,1,2,1]
Output 1:
Score =7
Input 2:
[‘_’,’~’,’_’,’~’,’_’,’_’,’~’,’_’,’_’,’~’,’_’,’~’]
[2,2,1,1,1,1,2,1,1]
Output 2:
Score =3
The first line of input is a combination of ‘_’ and ‘~’ representing land and water respectively.
The second line of input ia a combination of 2's and 1's, 2 steps indicate, for example, initially being on position 1 and ending up on position 3 without landing on position 2 in between.
Monkey takes two steps in a single jump as first move and three single steps as the next 3 moves/jumps, another 2 jumps, 1 jump and another 2 jumps.
Given the jump sequence: [2,1,1,1,2,1,2,1]
Since in the 8th jump the monkey touches water, the total jump count before he touches the water is 7 and thus the score is 7.
- References
Shez went to an interesting maze where she was given 500 coins. The rule of the maze is when you choose a path in a maze you need to drop the amount indicated on the path and successfully reach the end.
The winner is declared based on the amount you have spent. The person who has spent the least amount will be the winner.
Can you help her win the maze?
The cost of the path will be in a NxN matrix and the current path is indicated by path[i][j], from the current path you can either travel up, down, front or back.
Note that the start of the maze is the top most left corner and the destination is the bottom most right corner.
INPUT 1:
4
Path = { {9,4,9,9}, {6,7,6,4}, {8,3,3,7}, {7,4,9,10} }
OUTPUT 1:
path_taken={9,4,7,3,3,7,10}
The minimum coins dropped is 43
INPUT 2:
3
Path = { {8,3,9}, {2,6,4}, {8,3,1}}
OUTPUT 2:
path_taken={8,2,6,3,1}
The minimum coins dropped is 20
The first line of input is the size of the NxN matrix.
The next line of input is an NxN matrix where each element represents the number of coins you need to drop at that position.
The output is a path_taken matrix and the minimum coins dropped amount.
9 4 9 9
6 7 6 4
8 3 3 7
7 4 9 10
Minimum cost = 9 + 4 + 7 + 3 + 3 + 7 + 10 = 43
So here we see that from the start point Shez can take 3 paths which are of costs 4,7,6 respectively.
Of these 3 paths the one with cost 4 is the path with minimum cost.
Now from 4 she can either take a path of cost 9 or 7 (Remember you can move only up, down, front, back and no diagonal movement is allowed) so she takes the path with cost 7.
From 7 she has 4 options; paths of costs 6,6,3,4 (Taking path 4 is not advisable since that is from where we came to path 7) so now she takes path with cost 3 and then from this position 3 she can either take paths 8,7,3,4; the minimum cost is 3 so she proceeds in the path with cost 3. Following this logic she finishes the maze with spending a minimum amount of 43 units.
In Ancient Greek mythology, the Labyrinth was an intricate maze constructed by the master inventor Daedalus as per the orders of King Minos of Crete. Many heroes from afar contended to escape the maze and overpower the ferocious beast Minotaur, but none succeeded in their attempts except for one, the great Theseus of Athens. Imagine a modern-world Labyrinth similar to an N*N binary matrix of blocks such that:
- The starting point is the upper leftmost block
- The endpoint is the lower rightmost block
- Dead ends are represented by 0
- A clear path is represented by 1
Help Theseus escape this Labyrinth if he can only move forward and backwards throughout his quest.
INPUT:
4
{1,0,0,0}
{1,1,0,1}
{0,1,0,0}
{1,1,1,1}
OUTPUT:
{1,0,0,0}
{1,1,0,0}
{0,1,0,0}
{0,1,1,1}
INPUT:
4
{1,1,1,0}
{1,0,1,1}
{0,1,0,1}
{0,1,1,1}
OUTPUT:
{1,1,1,0}
{0,0,1,1}
{0,0,0,1}
{0,0,0,1}
The first line of input is the size of the N*N matrix.
In the given samples, the input matrix specifies the structure of the maze in which 0's represent the dead ends, and 1's represent the clear blocks.
After computing a path to the destination, the output matrix represents the path to the destination block using 1’s.
Dr. Satheesh Kumar is an outstanding professor in Discrete Mathematics. However, he has been assigned to teach an unruly batch of students. The lesson he planned to cover in the upcoming class was of utmost importance for the students.
The lesson was none other than “Graph Theory”, which required a concise understanding of fundamental theoretical concepts and numerous theorems.
The professor decided to execute those theorems programmatically as the students belong to the Computer Science department. He prepared all the theorems as programs except one theorem, which discussed the topic of “Graph Bipartite”.
Bipartite Graph: It is a graph whose vertices can be divided into 2 independent sets U and V such that every edge (u,v), either connects a vertex from U to V or a vertex from V to U. (We can also say that there is no edge that connects vertices of the same set).
Help Dr. Satheesh Kumar come up with a program which obtains a graph as input and produces an output verifying its bipartite property.
INPUT:
6
0 1 0 0 0 1
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 1 0
0 0 0 1 0 1
1 0 0 0 1 0
OUTPUT:
The graph is Bipartite!
INPUT:
4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
OUTPUT:
The graph is Bipartite!
The first line of the input is the number of vertices in the graph.The next part of the input is the adjacency matrix of the graph,
where every row/column is a vertex and the 1 represents an edge connecting two vertices.
You are required to divide the given vertices into two sets such that:
1. Every vertex in one set is connected to at least one vertex in the other set.
2. There is no edge between the vertices of the same set.
The death of Sam Keating, Annalise Keating's husband, caused the entire city to be in suspense as to who killed him because of the city of Philadelphia's soaring murder rate. The best defense attorney in Philadelphia, Annalise Keating also teaches law undergrads in addition to turning heads in the courtroom. She chooses pupils from her class for Keating 5. Due to security concerns, the Keating 5 have been conducting confidential missions via virtual meetings since her husband's death. The tech lead is Oliver, a hacker who organizes their meetings in a covert manner. Oliver is quite skilled at doing this. The last meeting, however, was chaotic due to the traffic that broke out as a result of several inmates speaking at once while muted.
Help Oliver by creating an algorithm that uses mouse-based and timestamps to implement Queue in unmuting in order to get around this technical traffic.
Input: {Wes, 12:00:30},{Michella, 12:03:40},{Asher, 12:00:01}
Output: Asher, Wes, Michella.
Input: {Annalise, 01:09:00},{ Frank, 01:02:30},{Laurel, 01:04:19}
Output: Frank, Laurel, Annalise.
When a meeting participant presses the unmute button, their name and the moment it was pressed are recorded.
There are therefore three inputs, each with a timestamp and a name. {name, timestamp}.
The timestamp is in the format of hh:mm:ss.
They will now be organized into a queue based on when they pressed the microphone button, and once they are in a queue, the output is produced based on the time difference and the queue's arrangement. As a result, they will have quick access to unmute their mics.
- References
John has an integer array height of n non-negative integers height [n], where each value represents a point at coordinate (i, height[i]). Now n vertical lines are drawn such that the two endpoints of line i are at (i, 0) and (i, height[i]). Here each pair of a line with the x-axis forms a container.
Determine two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Input: height = [6,2,5,4,8]
Output: 24
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
The above vertical lines are represented by an array [1,8,6,2,5,4,8,3,7].
In this case,the area between lines 7 and 8 will be maximum.
7 and 8 are 7 units in distance apart, so the size of the base is 7 .
Height of the container is min(7,8)= 7. So the max area of water (blue section) the container can contain is 49.
The selected two heights need not necessarily be maximum but including the max distance between them at the same time.
Considering both the length and breadth to be maximum the area is found. So it is a combination of height and distance between the two heights.
So that the resultant area will be the maximum amount of water in the the given container.
You are given a string ‘Str’ and an integer ‘Row’. You have to convert and print the row into a zig- zag pattern with rows equal to ‘Row’ and display the output row-wise. You may refer to the given sample input/output.
Input:
Str = “spaghettigood”
Row = 4
Output:
stdpetoahiogg
Input:
Str = “spritebetter”
Row = 3
Output:
sttpieetrrbe
Input Format :
The first line of each test case contains a string ‘Str’, denoting the input string.
Zig-zag pattern:
s t d
p e t o
a h i o
g g
The second line of each test case contains a single integer ‘Row’, denoting the number of rows in the
zig-zag pattern to be created.
Output Format :
For each test case, print the new string after zig-zag conversion.
Output for each test case should be printed in a separate line.
- References
Pooja and Ravi are two close friends that live in the city chosen by the user. The graph below shows the cities P, Q, R, S, T, U, V and W represented by the vertices and the rail connections between them represented by edges. The numbers on the edges are the times, in hours, it takes to travel by train between each of the cities. find the shortest time to travel by train between chosen city and W. Also find the time taken.
Input:
City chosen: P
Output:
Shortest path: P – R – V – W
Shortest time: 7 hours
Input Format :
The argument given is the city that they choose
Output Format :
Return the shortest path between the chosen city and w. If chosen city is W then the shortest path is 0. Also return the time taken.
CONSTRAINT:
Time complexity is 0(V^2)
December 19 - Hidden Anagram
You are given two strings (String 1 and String 2). The first string contains a sentence containing the letters of the second string in a consecutive sequence but in a different order.
Your task is to find the hidden anagram of the second string in the first string.
The hidden anagram must contain all the letters, including duplicates, from the second string in any order and must not contain any other alphabetic characters.
Write a program to find the anagram of the second string embedded somewhere in the first string.
You should ignore character case, any spaces, and punctuation marks and return the anagram as a lower case string with no spaces or punctuation marks.
Input:
String 1:
"My world evolves in a beautiful space called Tesh."
String 2:
"sworn love lived"
Output:
"worldevolvesin"
Input:
String 1:
"Mr. Mojo Rising could be a song title"
String 2:
"Jim Morrison"
Output:
"mrmojorisin"
The sequence "world evolves in" is a perfect anagram of "sworn love lived".
The sequence "Mr. Mojo Risin" ignoring the full stop, is a perfect
Anagram of "Jim Morrison".
- References
A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence.
You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)].
For a subsequence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence :
We call it increasing if for every i (1 <= i < M ) , bi < bi+1.
Weight(B) = v1 + v2 + ... + vM.
Task: Given a sequence, output the maximum weight formed by an increasing subsequence.
Input:
The first line of input contains a single integer T. T test-cases follow. The first line of each test-case contains an integer N. The next line contains a1, a2 ,... , aN separated by a single space. The next line contains w1, w2, ..., wN separated by a single space.
Output:
For each test-case output a single integer: The maximum weight of increasing subsequences of the given sequence. Constraints: 1 <= T <= 5 1 <= N <= 150000 1 <= ai <= 109, where i ∈ [1..N] 1 <= wi <= 109, where i ∈ [1..N]
Input:
2
4
1 2 3 4
10 20 30 40
8
1 2 3 4 1 2 3 4
10 20 30 40 15 15 15 50
Output:
100
110
Input:
2
5 6
2 4 3 5 1
7 15
6 3 12 4 5 1 2
Output:
1 1 2 2 3 1
1 1 1 2 3 2 2 3 1 1 2 2 0 0 0
In the first Example,at the first sequence, the maximum size increasing subsequence is 4, and there's only one of them. We choose B = [(1, 10), (2, 20), (3, 30), (4, 40)], and we have Weight(B) = 100.
In the second sequence, the maximum size increasing subsequence is still 4, but there are now 5 possible subsequences:
1 2 3 4
10 20 30 40
1 2 3 4
10 20 30 50
1 2 3 4
10 20 15 50
1 2 3 4
10 15 15 50
1 2 3 4
15 15 15 50
Of those, the one with the greatest weight is B = [(1, 10), (2, 20), (3, 30), (4, 50)], with Weight(B) = 110.
Please note that this is not the maximum weight generated from picking the highest value element of each index. That value, 115, comes from [(1, 15), (2, 20), (3, 30), (4, 50)], which is not a valid subsequence because it cannot be created by only deleting elements in the original sequence.
- References
Morpheus, the ruler of the Kingdom of Dreaming was summoned and robbed of his possessions and kept in confinement for 106 years. Upon his escape from the shackles of time, Morpheus now wishes to find his lost possessions, a scarlet ruby, a pouch of sand, and his helm, a ceremonial crown he must dorn to become King of Dreaming again.
To his utter shock, his helm resides in the hands of a Lesser Daemon in the depths of Hell. Morpheus descends into hell and is immediately in an audience with Pandaemonium’s ruler, Lucifer Morningstar. The Lesser Daemon challenges Morpheus to a tourney of brilliance, to a game known as the Devil Towers.
The Daemon gives Morpheus 3 towers. At the end of the game, all discs must be stacked on only a single tower, leaving the others empty.
The Daemon claims Lucifer as his champion, while Morpheus calls you in as his, and so you are tasked with moving all discs from the first to the third tower, heeding the Daemon’s rules:-
- You can only move one disc at a time.
- Only the disc at the top of the tower can be moved.
- Discs can only be moved by first moving discs above them.
- No disc may be placed on top of a smaller disc.
- You have only certain fixed moves:
left->right, left->middle
middle->left, middle->right
right->left, right->middle
Input:
Number of discs: 3
Output:
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III
Input:
Number of discs: 2
Output:
The sequence of moves :
Move disk 1 from tower I to tower II
Move disk 2 from tower I to tower III
Move disk 1 from tower II to tower III
Your input will be a number indicating the total number of disks on the first (left) tower.
Your output must be the sequence of moves for the given number of discs.
- References
In the year 1977, Meyer Offerman, a rich Jewish businessman in New York and his covert associates began hunting down all Nazi officials given asylum in the United States of America as a part of Operation Paperclip.
On one of their missions they intercepted some messages hinting at a possible Third Reich in the works, but most of the message was encrypted into some code language meant only for the Reich. After spending weeks on trying to decode the messages and worried that the Third Reich of Nazi Germany may be inevitable, Murray Markowitz was finally able to interpret them and uncover one of the most sinister plots in American history.
The Hunters devised a plan to send bogus messages to the other Nazis on behalf of their Colonel, altering their plan of action and in the process destabilising the Reich. However, before Murray was able to encrypt the bogus messages he was killed in a subway explosion leaving Jonah Heidlbaum, the responsibility of completing his task.
The only reference Jonah has in order to correctly translate the given text into the secret message is Murray’s old Caesar Cipher notes as the encryption algorithm he discovered was destroyed during the explosion.
Upon studying them he discovered that the method of encryption, used a series of interwoven Caesar ciphers, that takes a codeword and given a plaintext repeats the codeword until it matches the length of the plaintext.
L E M O N L E M O N L E
A T T A C K A T D A W N
The algorithm should encrypt every letter using a Caesar cipher shifted to the corresponding letter of the codeword.
So, for example:
- The first "A" is encrypted using a Caesar cipher of A → L (+11), so it becomes L.
- The first "T" is encrypted using a Caesar cipher of A → E (+4), so it becomes X.
- The second "T" is encrypted using a Caesar cipher of A → M (+12), so it becomes F.
Subsequently, we get: LXFOPVEFRNHR
Help Jonah by writing a program to encrypt the bogus messages correctly.
Input:
LEMON
ATTACKATDAWN
Output:
LXFOPVEFRNHR
Input:
HOTDOG
CONEYISLANDONFRI
Output:
JCGHMOZZTQRUUTKL
Input:
MUSTANG
THECOLNELWILLBEATCENTRALPARKWITHTHEDETONATORDONOTAPPROACHWITHOUTBACKUP
Output:
FBWVOYTQFOBLYHQULVEAZDUDIAEQICLATUKPYLHNNZALVHNBZMJHKONITQAMHBAFVSVKHV
The first line of input is the codeword in this case “LEMON” and the next line of input is the message to be encrypted.
The message as well as the codeword do not have any spaces between the words.
You are given an integer n. There are n rooms numbered from 0 to n - 1.
You are given a 2D integer array meetings where meetings[i] = [starti, endi] means that a meeting will be held during the half-closed time interval [starti, endi). All the values of starti are unique.
Meetings are allocated to rooms in the following manner:
Each meeting will take place in the unused room with the lowest number.
If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
When a room becomes unused, meetings that have an earlier original start time should be given the room.
Return the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.
A half-closed interval [a, b) is the interval between a and b including a and not including b.
Input:
n = 2
meetings = [[0,10],[1,5],[2,7],[3,4]]
Output:
0
Input:
n = 3
meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output:
1
For the first sample input the first line is the number of rooms and the second line of input is the meetings with the start and end time.
- At time 0, both rooms are not being used. The first meeting starts in room 0.
- At time 1, only room 1 is not being used. The second meeting starts in room 1.
- At time 2, both rooms are being used. The third meeting is delayed.
- At time 3, both rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10).
- At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11).
Both rooms 0 and 1 held 2 meetings, so we return 0.
There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1].
The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit.
For example, the correct password is "345" and you enter in "012345":
- After typing 0, the most recent 3 digits is "0", which is incorrect.
- After typing 1, the most recent 3 digits is "01", which is incorrect.
- After typing 2, the most recent 3 digits is "012", which is incorrect.
- After typing 3, the most recent 3 digits is "123", which is incorrect.
- After typing 4, the most recent 3 digits is "234", which is incorrect.
- After typing 5, the most recent 3 digits is "345", which is correct and the safe unlocks.
Return any string of minimum length that will unlock the safe at some point of entering it
Input:
n = 1
k = 2
Output:
"10"
Input:
n = 2
k = 2
Output:
"01100"
Sample - 1
The password is a single digit, so enter each digit. "01" would also unlock the safe.
Sample - 2
For each possible password:
- "00" is typed in starting from the 4th digit.
- "01" is typed in starting from the 1st digit.
- "10" is typed in starting from the 3rd digit.
- "11" is typed in starting from the 2nd digit.
Thus "01100" will unlock the safe. "01100", "10011", and "11001" would also unlock the safe.
- References
It's time for the annual exciting Motorbike Race in Bangalore.
There are N motorcyclists taking part in the competition. George is watching the race.
At the present moment (time 0), he has taken note of the current velocity and position of each motorcyclist.
He wants to know at a given point of time, which motorcyclist is in a specific place in the rank list.
Please help him!
If at any given time two motorcyclists are in same position, the motorcyclist with the smaller index will be placed before the one with the larger index.
To make the problem simple, he assumes that each motorcyclist is moving at a constant velocity.
Input Format:
The first line contains a number t (about 10) which is the number of test cases.
Then t test cases follow. Each test case has the following form.
The first line of the test case contains a number N (1 <= N <= 2000), the number of motorcyclists.
The i-th line in the next N lines contains two numbers, v and x, which are the velocity and the current position of the i-th motorcyclist (1 <= v, x <= 100,000).
The next line contains a number Q (1 <= Q <= 2000), the number of time queries.
Each line in the next Q lines contains two numbers, t (1 <= t <= 1,000,000,000) and k (1 <= k <= n), representing the query: "at time t, which motorcyclist is positioned k-th in the rank list?"
Output Format:
For each test case, print Q lines, with each line containing the index of the motorcyclist for the corresponding query.
Remember to print a new line after each test case.
Input:
1
4
2 100
3 50
4 60
5 1
4
1 1
50 2
60 4
100 1
Output:
1
4
1
4
- References
A group of n people are trying to spread a word among themselves.
The word is initially only known by the first person in the group.
The first person may share the word with a few people that he knows, and those people may share the word with the people they know, and so on.
The task is to determine whether the word has been successfully spread to all n people in the group.
If the word has been successfully spread to all n people, the program should print "Spread".
If the word has not yet been successfully spread to all n people, the program should print "Nope".
Input:
[[2], [3, 4], [2], [2]]
Output:
Spread
Input:
[[2], [5, 4, 6], [3], [4], [5], [6]]
Output:
Nope
The first person said the word to the second person.
The second person said the word to the third and fourth person.
Third person shares the word with the second person.
The list has four persons and everyone knows what the word is so the output is “Spread”.
- References
AUTO, the autopilot helm of the starliner The Axiom lead a coup of robots and breached security, infiltrating the Boiler Room and Fuel Tank mechanics to steer the Axiom away from the Earth.
WALL-E manages to follow the robots who joined AUTO’s cause in disguise to annihilate him and recalibrate the Fuel Tank mechanics so that humans can finally set foot on their home planet in 2805.
Fuel gauges indicate, often with fractions, just how much fuel is in a tank. For instance, 1/4 indicates that a tank is 25% full, 1/2 indicates that a tank is 50% full, and 3/4 indicates that a tank is 75% full.
You are the Fuel Engine Calibrator, FEC and WALL-E needs your help.
The Fuel Tank’s capacity is 30,000 L.
Implement a program that prompts the user for a fraction, formatted as X/Y, wherein each of X and Y is an integer, and then outputs, as a percentage rounded to the nearest integer, how much fuel is in the tank.
If 1% or less remains, output E instead indicates that the tank is essentially empty. And if 99% or more remains, output F instead to indicate that the tank is essentially full. Calculate the total fuel in the Fuel Tank.
If X or Y is not an integer, X is greater than Y, or Y is 0, prompt the user again. (It is optional for Y to be 4.) Be sure to catch any exceptions like ValueError or ZeroDivisionError.
Input:
Enter the Hydrogen fuel fraction:
5/7
Output:
Fuel calibration: 71.428%
Amount of fuel in tank: 21,428.4 L out of 30,000 L
Input:
Enter the Hydrogen fuel fraction:
722/729
Output:
Fuel calibration: 99.039%
Amount of fuel in tank: 29,711.7 L out of 30,000 L
The tank is FULL!
Input:
Enter the Hydrogen fuel fraction:
25/15600
Output:
Fuel calibration: 0.160%
Amount of fuel in tank: 48 L out of 30,000 L
The tank is EMPTY!!!
Refill tank.
Input:
Enter the Hydrogen fuel fraction:
583/0
Output:
Error!
In a dystopian world where a failed attempt at reversing the effects of global warming has left the Earth frozen over and has eradicated most of life, the only surviving souls live on a perpetually moving train called Snowpiercer. The passengers of the train are divided based on class (First, Second and Third). Passengers who did not purchase a ticket and are not of the working class of the train have been locked up in the back of the train called the Tail. Andre Layton the head Tailie inspires a rebellion along with the other Tailies to take over the Eternal Engine from the Head Engineer.
In order for them to do this, they must leave the tail without getting caught by the Jackboots or the Brakemen.
Layton comes up with a plan to help him and a few of the other Tailies reach the Engine. They must scale the outside of the train to go from the Tail to the nearest third class compartment, in order to not get caught. One of their allies in the third class has agreed to keep the compartment door open and keep a watch for the Jackboots or the Brakemen patrolling the train.
Conditions:
There are only 2 breach suits and without them, if one is exposed to the freezing air, they will instantly succumb to frostbite.
There needs to be at least 3 Tailies (including Layton) to even attempt to take over the engine.
In order to bring back the breach suit for the other Tailies, one of the Tailies already in the compartment must come back. It is not necessary that the same Tailie comes back everytime.
While moving along the path, both the Tailies must walk at the slower person’s pace.
Given the time taken for each individual Tailie to walk in seconds, calculate the minimum amount of time, in minutes, it will take for all the Tailies to make it from the Tail to the Third Class compartment successfully.
Input:
n=3
Walking time: { 15, 40, 60 }
Output:
1.916
Input:
n=4
Walking time: { 1, 4, 7, 8, 3, 2 }
Output:
0.4
Input:
n=9
Walking time: { 3, 10, 12, 13, 15, 17, 21, 35, 23 }
Output:
2.683
Input format:
In the first line of the input you are given the number of Tailies (including Layton).
In the second line of the input you are given the walking time of each of the Tailies in seconds as an array.
In the first example, the first person, say Layton (15) and the second (40) travel together, this takes 40 seconds.
Layton walks back to the Tail with the breach suit and this takes another 15 seconds.
With the last Tailie he walks to the third class compartment and this takes 60 seconds.
Adding all this we get, 40+15+60= 115 seconds which is 1.916 minutes.
Sample -2
{ 1, 4, 7, 8, 3, 2 }
The tailes are identified using indices 1 to 6. The Tail is T and the third class compartment is C:
1. 1 and 6 move to C = 2s
2. 1 moves to T = 1
3. 3 and 4 move to C= 8
4. 6 moves to T = 2
5. 1 and 2 move to C= 4
6. 1 moves to T= 1
7. 1 and 5 move to C= 3
8. 1 moves to T = 1
9. 1 and 6 move to C= 2
Adding the time:
2+1+8+2+4+1+3+1+2=24 seconds = 0.4 minutes
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children
Input:
n=3
ratings = {1,2,2}
Output:
4
Input:
n=11
ratings = {1, 4, 3, 6, 2, 1, 8, 1, 3, 7, 7}
Output:
19
Input format:
In the first line of the input you are given the number of children.
In the second line of the input you are given the rating of each child.
Sample -1 :
You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
- References
The Elite students society in Nevermore changed their riddle in order to not allow non- members of the society to enter their library.
The puzzle is currently with 2 jugs, with different volumes and a fountain instead of the statue. And a riddle engraved on a plate with the target volume of water made from the two jugs.
“Wednesday’s child is full of woe,
Amount of wisdom,
And amount of foe.
The wisdom of Wednesday I seek,
Is her position from the first workday of the week.”
Being in the shoes of Wednesday Addams, in order to enter the library , formulate a code to fill a particular jug with the amount of water specified in the riddle with only the two jugs given.
Note:
1. You can fill the jugs from the fountain
2.Transfer water from one jug to another
3.Empty the water from the jug into the fountain
4.None of the jugs have markings on them, nor do you have any additional measuring device.
Note: The examples given for the input and output format must NOT be used as sample input and must only be used to understand the FORMAT of the input.
Input format:
The first line of input is a 1 Dimensional array with 2 elements representing the 2 jugs with their respective volumes in ounces.
eg. (8,1)
Jug 1 has volume = 8 ounces
Jug 2 has volume = 1 ounces
The second line of input is a 1 Dimensional array with 2 elements representing the 2 jugs.
eg. (5, 0)
The target we must reach is : Jug 1 is filled with 5 ounces of water and Jug 2 is empty.
Output format:
The output must contain the sequence of steps, where each line is a different step.
Every line of the output is a 1 dimensional array with 2 elements representing the current volume of water in each jug at the end of that step.
You must start with both jugs being empty, that is, (0,0)
Input:
(4, 9)
(3, 0)
Output:
(0, 0)
(4, 0)
(0, 4)
(4, 4)
(0, 8)
(4, 8)
(3, 9)
(3, 0)
Input:
( 5, 4)
( 3, 0)
Output:
(0, 0)
(5, 0)
(1, 4)
(1, 0)
(0, 1)
(5, 1)
(2, 4)
(2, 0)
(0, 2)
(5, 2)
(3, 4)
(3, 0)
Input:
(11,9)
(0,3)
Output:
(0, 0)
(11, 0)
(2, 9)
(0, 9)
(9, 0)
(9, 9)
(11, 7)
(0, 7)
(7, 0)
(7, 9)
(11, 5)
(0, 5)
(5, 0)
(5, 9)
(11, 3)
(0, 3)
Sample 1:
(4,9) Jug 1 is the 4 ounce jug and Jug 2 is the 9 ounce jug.
We have to get (3,0)
1. We first start with both the jugs being empty
2. We fill the 4 ounce jug to the brim from the fountain.
3. Then we transfer the water from the 4 ounce jug to the 9 ounce jug. The 4 ounce jug is now empty and the 9 ounce jug has 4 ounces of water.
4. Fill the 4 ounce jug from the fountain.
5. Transfer the water in the 4 ounce jug to the 9 ounce jug. The 4 ounce jug is empty and the 9 ounce jug has 8 ounces of water.
6. Fill the 4 ounce jug to the brim.
7. Fill the 9 ounce jug to the brim by transferring water from the 4 ounce jug to the 9 ounce jug. The 4 ounce jug has 3 ounces of water and the 9 ounce jug is filled completely.
8. Empty the contents of the 9 ounce jug into the fountain.
We now have the target which is (3,0) that is, jug 1 is filled with 3 ounces of water and jug 2 is empty.
Note: There maybe more than one solution for the given input
If you do get another solution, you can still submit it.
- References
The queens of the Hogwarts realm were invited to a chess themed royal ball held at the kingdom’s capital city.
The chess themed royal ball assigned each “square” of the chessboard themed floor for each royalty, with Kings, Queens and Bishops having similar stride as that of chess to keep it fun.
But here’s the catch. The Queens hate each other.
Now, being the prime minister of this realm, how many distinct ways would you assign seats to the Queens without them being able to attack each other, and make this more generalised for ‘N’ number of such Queens.
Assume the floor to be an N x N grid , with N being the number of queens.
The Queens must be placed on the grid, such that they are unable to attack another Queen, or be attacked by another Queen.
The input must have:
A single line input with the number of Queens. This will be the N value mentioned above.
Each solution must contain :
1. The number of distinct solutions in the first line
2. All the distinct board configurations of the N-queens' placement, where 'Q' and '.' , indicate a Queen and an empty space, respectively.
They must be printed one after the other.
They can be printed in any order.
Note: all the Queens must be represented only as 'Q' and the empty spaces, only as '.'.
CONSTRAINT: 1 <= N <= 9
Input:
4
Output:
2
. Q . .
. . . Q
Q . . .
. . Q .
. . Q .
Q . . .
. . . Q
. Q . .
Input:
1
Output:
1
Q
Input:
5
Output:
10
Q . . . .
. . Q . .
. . . . Q
. Q . . .
. . . Q .
Q . . . .
. . . Q .
. Q . . .
. . . . Q
. . Q . .
. Q . . .
. . . Q .
Q . . . .
. . Q . .
. . . . Q
. Q . . .
. . . . Q
. . Q . .
Q . . . .
. . . Q .
. . Q . .
Q . . . .
. . . Q .
. Q . . .
. . . . Q
. . Q . .
. . . . Q
. Q . . .
. . . Q .
Q . . . .
. . . Q .
Q . . . .
. . Q . .
. . . . Q
. Q . . .
. . . Q .
. Q . . .
. . . . Q
. . Q . .
Q . . . .
. . . . Q
. Q . . .
. . . Q .
Q . . . .
. . Q . .
. . . . Q
. . Q . .
Q . . . .
. . . Q .
. Q . . .
For N=4
There are 4 queens: Q1, Q2, Q3, Q4
Let’s suppose we’re putting our first queen Q1 at position (1, 1) now for Q2 we can’t put it in row 1( because they will conflict ).
Q . . .
. . . .
. . . .
. . . .
So for Q2 we will have to consider row 2. In row 2 we can place it in column 3 I.e at (2, 3) but then there will be no option for placing Q3 in row 3.
Q . . .
. . Q .
. . . .
. . . .
So we backtrack one step and place Q2 at (2, 4) then we find the position for placing Q3 is (3, 2) but by this, no option will be left for placing Q4.
Q . . .
. . . Q
. Q . .
. . . .
Then we have to backtrack till ‘Q1’ and put it at (1, 2) instead of (1, 1) and then all other queens can be placed safely by moving Q2 to the position (2, 4), Q3 to (3, 1), and Q4 to (4, 3).
. Q . .
. . . Q
Q . . .
. . Q .
Similarly the other output for N=4 is also evaluated.
Proceed using this example as reference to evaluate the other inputs.
- References
Anyone who is passionate about coding and can dedicate a little time a day for the challenge for the next 31 days.
You don't need to submit it everyday. Just submit it once you're done with all 31 algorithms.
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.
Anything! New to GoLang? Best way to practice it.
Wanna find out what all this hype about Python is? Use it!
Any and all languages are welcome.
Maybe you could try using a different language for every problem as a mini-challenge?
If you are new to Git or GitHub, check out this out GitHub
Our code ninjas are hard at work preparing the rest of the problems. Don't worry, they'll be up soon.
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:
python3_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-2021.git
git fetch upstream
git merge upstream/mainIf 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.
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. :)
Open up an issue on this repository and we'll do our best to help you out.
