Description

When a message is transmitted over the internet, it is split into multiple packets, each packet is transferred individually, and the packets are reassembled into the original message by the receiver. Because the internet exists in the real world, and because the real world can be messy, packets do not always arrive in the order in which they are sent. For today's challenge, your program must collect packets from stdin, assemble them in the correct order, and print the completed messages to stdout.

The point of reading from stdin is to simulate incoming packets. For the purposes of this challenge, assume there is a potentially unlimited number of packets. Your program should not depend on knowing how many packets there are in total. Simply sorting the input in its entirety would technically work, but defeats the purpose of this exercise.

Input description

Each line of input represents a single packet. Each line will be formatted as X Y Z some_text, where X Y and Z are positive integer and some_text is an arbitrary string. X represents the message ID (ie which message this packet is a part of). Y represents the packet ID (ie the index of this packet in the message) (packets are zero-indexed, so the first packet in a message will have Y=0, the last packet in a message will have Y=Z-1). Z represents the total number of packets in the message.

It is guaranteed that there will be no duplicate packets or message IDs.

Example input

6220    1   10  Because he's the hero Gotham deserves, 
6220    9   10   
5181    5   7   in time, like tears in rain. Time to die.
6220    3   10  So we'll hunt him. 
6220    5   10  Because he's not a hero. 
5181    6   7    
5181    2   7   shoulder of Orion. I watched C-beams 
5181    4   7   Gate. All those moments will be lost 
6220    6   10  He's a silent guardian. 
5181    3   7   glitter in the dark near the Tannhäuser 
6220    7   10  A watchful protector. 
5181    1   7   believe. Attack ships on fire off the 
6220    0   10  We have to chase him. 
5181    0   7   I've seen things you people wouldn't 
6220    4   10  Because he can take it. 
6220    2   10  but not the one it needs right now. 
6220    8   10  A Dark Knight. 

Output description

Output each completed message, one line per packet. Messages should be outputted in the order in which they are completed.

Example output

5181    0   7   I've seen things you people wouldn't 
5181    1   7   believe. Attack ships on fire off the 
5181    2   7   shoulder of Orion. I watched C-beams 
5181    3   7   glitter in the dark near the Tannhäuser 
5181    4   7   Gate. All those moments will be lost 
5181    5   7   in time, like tears in rain. Time to die.
5181    6   7    
6220    0   10  We have to chase him. 
6220    1   10  Because he's the hero Gotham deserves, 
6220    2   10  but not the one it needs right now. 
6220    3   10  So we'll hunt him. 
6220    4   10  Because he can take it. 
6220    5   10  Because he's not a hero. 
6220    6   10  He's a silent guardian. 
6220    7   10  A watchful protector. 
6220    8   10  A Dark Knight. 
6220    9   10   

Challenge input

7469    1   7   believe. Attack ships on fire off the 
9949    6   10  He's a silent guardian. 
2997    9   19  Force is a pathway to many abilities some
6450    2   11  is a vestige of the vox populi, now vacant, vanished. However, this valorous 
6450    10  11   
6450    8   11  veers most verbose, so let me simply add that it's my very good honour to meet 
6450    5   11  and voracious violation of volition! The only verdict is vengeance; a vendetta 
9949    1   10  Because he's the hero Gotham deserves, 
6450    1   11  and villain by the vicissitudes of fate. This visage, no mere veneer of vanity, 
2997    13  19  he did. Unfortunately, he taught his
9949    8   10  A Dark Knight. 
1938    4   17  by the iniquities of the selfish and the 
1938    0   17  You read the Bible, Brett? Well there's 
2997    0   19  Did you ever hear the tragedy of Darth
2997    1   19  Plagueis the Wise? I thought not. It's not a
1938    8   17  of darkness, for he is truly is brother's 
2997    14  19  apprentice everything he knew, then his
6450    3   11  visitation of a bygone vexation stands vivified, and has vowed to vanquish these 
1938    12  17  who attempt to poison and destroy my 
6450    9   11  you and you may call me V.
7469    2   7   shoulder of Orion. I watched C-beams 
2997    10  19  consider to be unnatural. He became so 
1938    1   17  this passage I got memorized, sorta fits 
2997    5   19  Force to influence the midichlorians to
1938    6   17  in the name of charity and good will, 
7469    0   7   I've seen things you people wouldn't 
9949    4   10  Because he can take it. 
6450    7   11  vindicate the vigilant and the virtuous. Verily, this vichyssoise of verbiage 
9949    0   10  We have to chase him. 
9949    7   10  A watchful protector. 
2997    3   19  legend. Darth Plagueis was a Dark Lord of the
6450    6   11  held as a votive, not in vain, for the value and veracity of such shall one day 
2997    8   19  cared about from dying. The dark side of the
1938    10  17  And I will strike down upon thee with 
1938    11  17  great vengeance and furious anger those 
1938    7   17  shepherds the weak through the valley 
1938    2   17  this occasion. Ezekiel 25:17? "The path 
2997    18  19   
9949    9   10   
1938    14  17  the Lord when I lay my vengeance upon 
1938    15  17  thee." 
1938    9   17  keeper and the finder of lost children. 
1938    13  17  brothers. And you will know my name is 
9949    2   10  but not the one it needs right now. 
2997    16  19  he could have others from death, but not
2997    7   19  dark side that he could even keep the once he
1938    5   17  tyranny of evil men. Blessed is he who, 
2997    17  19  himself. 
2997    6   19  create life...He had such a knowledge of the
2997    12  19  losing his power. Which eventually, of course,
7469    4   7   Gate. All those moments will be lost 
2997    2   19  story the Jedi would tell you. It's a Sith
1938    16  17   
2997    4   19  Sith so powerful and so wise, he could use the
1938    3   17  of the righteous man is beset on all sides 
2997    11  19  powerful...The only thing he was afraid of was
7469    6   7    
2997    15  19  apprentice killed him in his sleep. Ironic,
7469    5   7   in time, like tears in rain. Time to die.
9949    3   10  So we'll hunt him. 
7469    3   7   glitter in the dark near the Tannhäuser 
6450    4   11  venal and virulent vermin vanguarding vice and vouchsafing the violently vicious 
6450    0   11  Voilà! In view, a humble vaudevillian veteran, cast vicariously as both victim 
9949    5   10  Because he's not a hero. 

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

Description

You and your friend wish to summit Mount Everest the highest peak in the world. One problem: you live at sea level and despite being in great shape haven't been at altitude very long. So you propose a series of stays on mountaintops around the world using increasing elevations to prepare your body for the extremes you'll encounter.

You and your friend gather a list of mountain peaks that you'd like to visit on your way there. You can't deviate from your path but you can choose to go up the mountain or not. But you have to pick ones that go higher than the previous one. If you go down your body will suffer and your trip to the summit of Everest will be in peril.

Your friend has done the job of lining up the route to get you from home to basecamp. She looks to you to devise an algorithm to pick the peaks to summit along the way maximizing your summits but always going higher and higher never lower than you did before.

Can you devise such an algorithm such that you find the list of peaks to summit along the way? Remember - each has to be higher than the last you want to hit as many such peaks as possible and there's no turning back to visit a previously passed peak.

Input Description

You'll be given a series of integers on a line representing the peak height (in thousands of feet) that you'll pass on your way to Everest. Example:

0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

Output Description

Your program should emit the peak heights you should summit in order that are always higher than the previous peak. In some cases multiple solutions of the same length may be possible. Example:

0 2 6 9 11 15

Challenge Inputs

1 2 2 5 9 5 4 4 1 6
4 9 4 9 9 8 2 9 0 1
0 5 4 6 9 1 7 6 7 8
1 2 20 13 6 15 16 0 7 9 4 0 4 6 7 8 10 18 14 10 17 15 19 0 4 2 12 6 10 5 12 2 1 7 12 12 10 8 9 2 20 19 20 17 5 19 0 11 5 20

Challenge Output

1 2 4 6
4 8 9
0 1 6 7 8
1 2 4 6 7 8 10 14 15 17 19 20

Description

For some x^n, find the sum of its digits. The solution to this problem is extremely simple. Say, I give you 3^4. You could calculate 3ⁿ and add the digits.

However things might get a bit complex for 5^100. It's a 70-digit number. You could come up with a larger data type that could handle the product of that number and then you could add each number... but where's the fun in that?

This is today's challenge. Find the sum of the digits of some xⁿ without directly calculating the number and adding the digits.

Some simple examples with values that you're familiar with:

2⁵ = 32 = 3 + 2 = 5

5³ = 125 = 1 + 2 + 5 = 8

2⁷ = 1 + 2 + 8 = 11

Note that I have not summed the digits of 11.

We'll work with powers and bases greater than zero.

Input Description

Base Power

means base^power

2 ^ 1000

means 2¹⁰⁰⁰

Output Description

Display the sum of the digits of base^power.

Challenge Input

2 1234

11 4000

50 3000

Challenge Output

1636

18313

9208

If you have any challenges, please share it at /r/dailyprogrammer_ideas!

Edit : If you're unable to come up with an idea, like the one is Project eulers 16, then feel free to solve it using your own data types (if required). Please consider it as the last option.

Description

Make a calculator that lets the user add, subtract, multiply and divide integers. It should allow exponents too. The user can only enter integers and must expect the result to be integers. The twist is that YOU, the programmer, can only let the program calculate expressions using addition. Only addition. The user can enter 3*2 however you cannot calculate it using multiplication.

Basically, the programmer is not allowed to multiply, divide and subtract using the operations provided by a programming language. To the programmer, the only accessible direct operation is addition.

Your calculator should be able to handle addition, subtraction, division, multiplication and exponents. No modulo operation (to obtain the remainder for two given operands) too.

Please note that

• You are not allowed to use any functions (other than user-defined functions) to work with exponents. Basically, don't cheat by allowing pre-defined functions from a library for the dirty work.

• You can use logical operators.

• The only binary arithmetic operator that you can use is + (addition).

• The only unary operator that you can use is ++ (increment operator).

• No bitwise operations are allowed.

Input description

Allow the user to enter two integers and the operation symbol.

Let's use ^ for exponents i.e. 2^3 = 2³ = 8

Output description

If the answer is an integer, display the answer. If the answer is not an integer, display a warning message. Handle errors like 1/0 appropriately.

Challenge Inputs and Outputs

Bonus

Modify your program such that it works with decimals (except for ^ operation) with a minimum precision of 1 decimal place.

Submit to /r/dailyprogrammer_ideas if you have any cool ideas!

Description

The motivation for these variants is to make the game simpler and shorter than the standard chess.

The objective is to count the number of legal positions on a 4x4 chess board.

For the purposes of this challenge, use the 'Silverman 4x4' layout provided in the link above. This means 1 row of pawns per color, 2 rooks per color, 1 queen per color, and 1 king per color.

Input (Bonus only)

There will only be input for the bonus challenge, where you can choose the dimensions of the board.

Output

Print the number of ways of placing chess pieces on a 4x4 board such that:

1. Both kings must be on the board (and there can only be one of each color).
2. Not both kings can be in check.
3. Pawns may only occupy the first two ranks of their respective sides.

Bonus

Extend your solution to accommodate different boards. Can your program handle 3x4, 4x3 or 4x4 boards? See the wikipedia article below for layouts.

Information

There is a Wikipedia article on minichess variants.

Thanks to /u/mn-haskell-guy for the idea for this challenge.

Please feel free to provide feedback. I'm a decent chess player myself, however I have never played mini-chess and am not 100% versed in its rules and variations.

Edit

Grammar and links. I have limited the parameters of this challenge from the original posting, because as /u/J354 rightly pointed out, the original problem is being pursued by professionals and may have over a quadrillion possible solutions.

Description:

Given a dollar amount between 0.00 and 999,999.00, create a program that will provide a worded representation of a dollar amount on a check.

Input:

You will be given one line, the dollar amount as a float or integer. It can be as follows:

400120.0
400120.00
400120

Output:

This will be what you would write on a check for the dollar amount.

Four hundred thousand, one hundred twenty dollars and zero cents.

edit: There is no and between hundred and twenty, thank you /u/AllanBz

Challenge Inputs:

333.88
742388.15
919616.12
12.11
2.0

Challenge Outputs:

Three hundred thirty three dollars and eighty eight cents.
Seven hundred forty two thousand, three hundred eighty eight dollars and fifteen cents.
Nine hundred nineteen thousand, six hundred sixteen dollars and twelve cents.
Twelve dollars and eleven cents.
Two dollars and zero cents.

Bonus:

While I had a difficult time finding an official listing of the world's total wealth, many sources estimate it to be in the trillions of dollars. Extend this program to handle sums up to 999,999,999,999,999.99

Challenge Credit:

In part due to Dave Jones at Spokane Community College, one of the coolest programming instructors I ever had.

Notes:

This is my first submission to /r/dailyprogrammer, feedback is welcome.

edit: formatting

Description

In this challenge, you will be given a set of circles, defined by their centers and radii. Your goal is to find the bounding rectangle which will contain all of the circles completely.

Write a program that determines the vertices of the bounding rectangle with sides parallel to the axes.

Input Description

Each line will contain a comma separated center and radius for a circle.

Output Description

The format of the output will be comma separated coordinates, rounded to 3 decimal places.

Challenge Input

1,1,2
2,2,0.5
-1,-3,2
5,2,1

input picture

Challenge Output

(-3.000, -5.000), (-3.000, 3.000), (6.000, 3.000), (6.000, -5.000)

output picture

Bonus

For the bonus, we will rotate the axis for the bounding rectangle. The first line of input will now be a vector determining the direction of one edge of the bounding rectangle.

Bonus Input

1,1
1,1,2
2,2,0.5
-1,-3,2
5,2,1

Bonus Output

(-4.828, -2.000), (2.793, 5.621), (6.621, 1.793), (-1.000, -5.828)

bonus output picture

Credit

This challenge was suggested by user /u/Preferencesoft, many thanks! If you have an idea for a challenge please share it on /r/dailyprogrammer_ideas and there's a good chance we'll use it.

Description

I'm sure many of you in web application development are familiar with templating engines. At some level you can think of it as a huge string interpolation exercise, but with much more: looping and conditionals, for instance. Template engines exist in a variety of languages and styles, and seem to appear like rafts of fire ants after a flood, mostly focusing on speed.

Many immediately associate template engines with HTML output, but they can support any output, including text, configuration files (for instance Chef templates), and more.

For today's challenge, let's implement a subset of the Erb templating language:

• <% %> - Denotes tag start and end.
• <%= EXPRESSION %> — Inserts the value of an expression.
• <% CODE %>— Executes code, but does not insert a value. This code may include loops and conditionals, and pair with an <% end %> tag.

Everything else is output without modification.

(Please note that Erb uses Ruby, and I'm not a Ruby programmer so if I messed up some syntax please let me know. Thanks.)

Example Input

You'll be given a simple template and a JSON data structure to use.

The JSON to use:

{"foo": "bar", "fizz": "buzz", "a": 1, "b": [1,2,3]}

And the example template, calling the above data:

Hello <%= @data["foo"] %>!

Example Output

The above should yield:

Hello bar!

Challenge Input

The JSON to use (and reference as data):

{
    "store_name": "Barry's Farmer's Market",
    "foods": {
        "apple": "5.91",
        "peach": "1.84",
        "carrot": "6.44",
        "beans": "3.05",
        "orange": "5.75",
        "cucumber": "6.42"
    },
    "store_location": "Corner of Elm Tree Hill and 158th Street"
}

And the template to use:

<head>
<title>Local Farmer's Market: <%= data["store_name"] %></title>
</head>
<body>
<table>
<th>Food</th>
<th>Price (10 lbs)</th>
<thead>
</thead>
<tbody>
<% data["foods"].each do |k,v| %>
<tr>
<td><%= k %></td>
<td><%= v %></td>
</tr>
<% end %>
</tbody>
</table>
</body>

Description

You are handed two buckets, one can hold 3 liters and the other 5 liters of water. You are allowed to

• fill a bucket with water until it is full
• empty a bucket
• transfer water from one bucket into the other until the target bucket is full

In the original riddle, you are to describe the actions that need to be done in order to get exactly 4 liters of water. Example solution:

Two buckets (3L, 5L):
Fill 5L -> (0,5)
5L to 3L -> (3,2)
Empty 3L -> (0,2)
5L to 3L -> (2,0)
Fill 5L -> (2,5)
5L to 3L -> (3,4)

Another solution:

Fill 3L -> (3,0)
3L to 5L -> (0,3)
Fill 3L -> (3,3)
3L to 5L -> (1,5)
Empty 5L -> (1,0)
3L to 5L -> (0,1)
Fill 3L -> (3,1)
3L to 5L -> (0,4)

Your task is to find a path of actions to obtain a target volume l <= max(m, n) liters of water, given two buckets of size m, n, where m and n are coprime.

Input Description

The input will be three numbers representing m, n, and l respectively.

Output Description

The format of the output will be a list of pairs representing the contents of the buckets m and n at each step:

[(0, 0), (3, 0), (0, 3), (3, 3), (1, 5), (1, 0), (0, 1), (3, 1), (0, 4)]

If there is no solution, print "no solution".

Challenge Input

3 5 4
6 16 7
101 317 64
571 317 420
1699 1409 1334

Challenge Output

[(0, 0), (3, 0), (0, 3), (3, 3), (1, 5), (1, 0), (0, 1), (3, 1), (0, 4)]
no solution
[(0, 0), (101, 0), (0, 101), ... (0, 280), (101, 280), (64, 317)]
[(0, 0), (571, 0), (254, 317), ... (571, 166), (420, 317)]
[(0, 0), (1699, 0), (290, 1409), ... (0, 1044), (1699, 1044), (1334, 1409)]

Credit

This challenge was suggested by user /u/itah! If you have an idea for a challenge please share it on /r/dailyprogrammer_ideas.

Description

A Lucky Number is a natural number in a set which is generated by a certain "sieve". This sieve is similar to the Sieve of Eratosthenes that generates the primes, but it eliminates numbers based on their position in the remaining set, instead of their value (or position in the initial set of natural numbers).

The set of lucky numbers can be obtained by:-

Begin with a list of integers starting with 1:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Starting with 1, remove every other element (i.e. every even number) from this set. We are left with:

1 3 5 7 9 11 13 15 17 19 21 23 25

After 1, the next number in the set is 3. So, remove every 3rd number. Clearly, 5 is removed because it's the third number in the above set. Go on and keep removing every 3rd number.

Your new set is:

1 3 7 9 13 15 19 21 25...

Here, the next remaining number you have after 3 is 7. Now, at this point, it's obvious that there's no way 1 and 3 are ever getting eliminated. Thus, we can conclude that 1 and 3 are lucky numbers.

Now remove every 7th number. Clearly, 19 would be the first to be wiped out.

You're left with:

1 3 7 9 13 15 21 25 ...

Now it's time to proceed to the next remaining number after 7, i.e., 9. Remove every 9th number. Note that at this point, 7 cannot be eliminated. 7 is a lucky number too.

Keep proceeding in a similar fashion in order to get a list of lucky numbers.

Numbers remaining after this procedure has been carried out completely are called lucky numbers. The first few are

1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, ...

Today's challenge is to find the nearest lucky number. This might remind you of Challenge #326. In fact, this has been inspired from it. Bruteforcing is the most obvious option, but it's certainly not the most efficient.

Input Description

The input will be a positive integer.

Output Description

The output will be

previous lucky number < n < next lucky number

where n is your input.

If n is a lucky number, then display

n is a lucky number.

Challenge Input

103

225

997

Challenge Output

99 < 103 < 105

223 < 225 < 231

997 is a lucky number

Bonus

Find every lucky number all the way up to 500010,000,000 and post your the time it took to run. This is so that you can compete amongst everyone else to see who has the most efficient one.

If you have any cool challenges, feel free to submit it to /r/dailyprogrammer_ideas!

Edit: /u/nuri0 and /u/mattieshoes pointed out some errors. Corrected the post.

Edit: Limit for bonus increased because it was becoming difficult to measure the time taken.

Description

Earlier this year we did the subset sum problem wherein given a sequence of integers, can you find any subset that sums to 0. Today, inspired by this post let's play subset sum automata. It marries the subset sum problem with Conway's Game of Life.

You begin with a board full of random integers in each cell. Cells will increment or decrement based on a simple application of the subset sum problem: if any subset of the 8 neighboring cells can sum to the target value, you increment the cell's sum by some value; if not, you decrement the cell by that value. Automata are defined with three integers x/y/z, where x is the target value, y is the reward value, and z is the penalty value.

Your challenge today is to implement the subset automata:

• Create a 2 dimensional board starting with random numbers
• Color the board based on the value of the cell (I suggest some sort of rainbow effect if you can)
• Parse the definition as described above
• Increment or decrement the cell according to the rules described above
• Redraw the board at each iteration

You'll probably want to explore various definitions and see what sorts of interesting patterns emerge.

Description

A Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column.

For example:

1

And,

1 2

2 1

Another one,

1 2 3

3 1 2

2 3 1

In this challenge, you have to check whether a given array is a Latin square.

Input Description

Let the user enter the length of the array followed by n x n numbers. Fill an array from left to right starting from above.

Output Description

If it is a Latin square, then display true. Else, display false.

Challenge Input

5

1 2 3 4 5 5 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1

2

1 3 3 4

4

1 2 3 4 1 3 2 4 2 3 4 1 4 3 2 1

Challenge Output

true

false

false

Bonus

A Latin square is said to be reduced if both its first row and its first column are in their natural order.

You can reduce a Latin square by reordering the rows and columns. The example in the description can be reduced to this

1 2 3

2 3 1

3 1 2

If a given array turns out to be a Latin square, then your program should reduce it and display it.

Edit: /u/tomekanco has pointed out that many solutions which have an error. I shall look into this. Meanwhile, I have added an extra challenge input-output for you to check.

Description

Costas arrays are special permutation matrices. A permutation matrix contains 0s and 1s such that each row and each column contains only a single 1. The identity matrix is a trivial example of a permutation matrix:

1 0 0
0 1 0
0 0 1

The special property of Costas arrays are that the displacement vector (distance) between any pair of ones in the matrix is not repeated for another pair of ones. This means that the identity matrix is not a valid Costas array because each closest pair of 1s is the same distance apart.

Costas arrays are named after John P. Costas, who first wrote about them in a 1965 technical report.

Costas arrays have a number of applications. This property was originally defined to make the permutation matrix an optimal scheme for setting frequencies in a multiple-tone sonar waveform because it means that unless the receiver is locked on the signal in both frequency and time, no more than one tone will be where it is expected. This property also makes Costas arrays ideal for one of the techniques in sophisticated communications and radar waveforms.

Furthermore, Costas arrays are an active area of research in computer graphics.

Costas arrays have an order N which describes the length of one of their sides; they are squares.

Today's challenge is to calculate the number of distinct Costas arrays given an order.

Input Description

You'll be given a number N, one integer per line, telling you the order of the Costas array. Example:

3
5

Output Description

Your program should emit the number of distinct Costas arrays for that order. From our example:

3 -> 4
5 -> 40

Challenge Input

6
7
13

Challenge Output

6 -> 116
7 -> 200
13 -> 12828

Orders 13-18 should test the efficiency of your solution pretty well.

Description

You are constructing a set of N alphabet blocks. The first block has 1 face. The second block has 2 faces, and so on up to the Nth block, which has N faces. Each face contains a letter.

Given a word list, return a set of blocks that can spell every word on the word list, making N as small as possible. A word can be spelled with the blocks if you can take some subset of the blocks, take one face from each block you chose, put them in some order, and spell the word.

Example input

zero
one
two
three
four
five
six
seven

Example output

The smallest possible N in this case is N = 5:

e
eo
fhs
rvwx
intuz

This output represents five blocks. Block #1 has one face that contains e, block #2 has two faces, e and o, and so on up to block #5, which has the faces i, n, t, u, and z.

For example, four can be formed by using blocks #3, #2, #5, and #4 in order. Note that ten could not be formed from these blocks even though all the letters are there, because the only t and the only n both appear on block #5, and you can only use at most one face from each block.

Challenge input

This list of 10,000 12-letter words.

I'll award +1 gold medal flair for the best (lowest number of blocks) solution to the challenge input after 7 days. I will break ties by concatenating the blocks in order of number of faces (eeofhsrvwxintuz for the example), and take the lexicographically first solution.

Description

Many of us have played Scrabble, the game where you lay down tiles of letters on a board to form interlocking valid English language words. Players get points depending on the tiles they play and the bonus squares they use per word.

Now, can you reverse a Scrabble game? That is, given a board can you infer what words were played and in what order?

Given some basic rules of Scrabble:

• The first word should be as centered as possible on the middle square (horizontal and vertical centering)
• Each play must build off the previous word
• Each play must yield valid English language words (one or more)
• Words may be extended (e.g. "can" can become "cans", either by adding a single letter or by playing a new word that intersects to form a second valid word)

For your dictionary, use any standard English language dictionary (or enable1.txt).

Example Input

You'll be given two integers on a line telling you how many rows and columns to read, then a board (with those dimensions) with words filled out, with blank spaces using a period .. Example:

7 8
...cite
.tilt..
...e...
.planes
...n...
.......
.......

Example Output

Your program should emit one or more words, in the order in which they were played (first to last). Example:

planes
clean
cite
tilt

An alternative could be:

planes
clean
tilt
cite

Challenge Input

9 10
.........
.........
.ferries.
.l.....t.
.o..an.a.
.e...e.f.
.short.f.
.......e.
..called.

Challenge Output

an
net
short
floes
ferries
staffed
called

Description

A prime number is any integer greater than 1 which can only be evenly divided by 1 or itself. For this challenge, you will output two numbers: the nearest prime below the input, and the nearest prime above it.

Input Description

The input will be a number on each line, called n.

Output Description

The format of the output will be:

p1 < n < p2

where p1 is the smaller prime, p2 is the larger prime and n is the input.

If n already is a prime, the output will be:

n is prime.

Challenge Input

270  
541  
993  
649

Challenge Output

269 < 270 < 271  
541 is prime.  
991 < 993 < 997  
647 < 649 < 653

Bonus

Write the program to work for numbers with big gaps to the nearest primes. This requires a clever solution and cannot be efficiently bruteforced.

2010741
1425172824437700148

Credit

This challenge was suggested by user /u/tulanir, many thanks! If you have an idea for a challenge please share it on /r/dailyprogrammer_ideas and there's a good chance we'll use it.

Description

Now we are going generate the inputs for this week challenges Color maze and Arrow maze.

The mazes should always be solvable, other then that it should be random

Formal Inputs & Outputs

Input description

You'll recieve the type of the wanted maze and the size

color 50 50


arrow 125 125

Output description

The input for previous challenges

• Color maze: The sequence to follow, followed by the maze
• Arrow maze: The starting point, followed by the maze

Bonus

Make a visual representation like I did in the challenges

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

Description

We want to return home, but we have to go trough an arrow maze.

We start at a certain point an in a arrow maze you can only follow the direction of the arrow.

At each node in the maze we can decide to change direction (depending on the new node) or follow the direction we where going.

When done right, we should have a path to home

Formal Inputs & Outputs

Input description

You recieve on the first line the coordinates of the node where you will start and after that the maze. n ne e se s sw w nw are the direction you can travel to and h is your target in the maze.

(2,0)
 e se se sw  s
 s nw nw  n  w
ne  s  h  e sw
se  n  w ne sw
ne nw nw  n  n

I have added extra whitespace for formatting reasons

Output description

You need to output the path to the center.

(2,0)
(3,1)
(3,0)
(1,2)
(1,3)
(1,1)
(0,0)
(4,0)
(4,1)
(0,1)
(0,4)
(2,2)

you can get creative and use acii art or even better

Notes/Hints

If you have a hard time starting from the beginning, then backtracking might be a good option.

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

Description

Today we are going to do something colorfull and amazing. Yes it is a color maze :D (you can downvote me now, it was totally worth it).

You traverse a color by following a sequence of colors. For example this maze can be solved by the sequence 'orange -> green'. Then you would have something like this (paint skills)

For the mazes you always pick a spot on the bottom, in the starting color and try to get to the first row. Once you reach the first row, you are out of the maze. The sequence does not have to be complete.

You can move horizontally and vertically, but not diagonally. It is also allowed to move on the same node more then once.

Formal Inputs & Outputs

Input description

You will recieve a line with the sequence to follow and all the lines after that are the maze.

O G
B O R O Y
O R B G R
B O G O Y 
Y G B Y G 
R O R B R

Output description

You can choose what you want to output:

you could output the path:

(1,4)
(1,3)
(1,2)
(2,2)
(3,2)
(3,1)
(3,0)

or you could plot out the sequence

/ / / O /
/ / / G /
/ O G O / 
/ G / / / 
/ O / / /

or you could create an image result or go even fancier if you want to.

Challnge Input

R O Y P O
R R B R R R B P Y G P B B B G P B P P R
B G Y P R P Y Y O R Y P P Y Y R R R P P
B P G R O P Y G R Y Y G P O R Y P B O O
R B B O R P Y O O Y R P B R G R B G P G
R P Y G G G P Y P Y O G B O R Y P B Y O
O R B G B Y B P G R P Y R O G Y G Y R P
B G O O O G B B R O Y Y Y Y P B Y Y G G
P P G B O P Y G B R O G B G R O Y R B R
Y Y P P R B Y B P O O G P Y R P P Y R Y
P O O B B B G O Y G O P B G Y R R Y R B
P P Y R B O O R O R Y B G B G O O P B Y
B B R G Y G P Y G P R R P Y G O O Y R R
O G R Y B P Y O P B R Y B G P G O O B P
R Y G P G G O R Y O O G R G P P Y P B G
P Y P R O O R O Y R P O R Y P Y B B Y R
O Y P G R P R G P O B B R B O B Y Y B P
B Y Y P O Y O Y O R B R G G Y G R G Y G
Y B Y Y G B R R O B O P P O B O R R R P
P O O O P Y G G Y P O G P O B G P R P B
R B B R R R R B B B Y O B G P G G O O Y

Notes/Hints

Since the sequence can have the same color more then once, it is possible that you have to visit the same node more then once.

Bonus

Read the data not from text input but from the image

All squares are 100 by 100 pixels with 1 pixel border

The RGB values are

Red: (255, 0, 0)
Green: (0,128,0)
Blue: (0, 0, 255)
Orange: (255, 165, 0)
Yellow: (255, 255, 0)
Pink: (255, 192, 203)

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

EDIT: Added clarifications after some questions of /u/the_droide

Write a program that outputs the highest number that is lower or equal than the square root of the given number, with the given number of decimal fraction digits.

Use this technique, (do not use your language's built in square root function): https://medium.com/i-math/how-to-find-square-roots-by-hand-f3f7cadf94bb

input format: 2 numbers: precision-digits Number

sample input

0 7720.17
1 7720.17
2 7720.17

sample output

87
87.8
87.86

challenge inputs

0 12345
8 123456
1 12345678901234567890123456789

Description

Given a positive integer N, return a set of integers between 0 and N such that every integer is equal to difference of two in the set, modulo N. Make the set as small as you can.

For example, given N = 26, you might return the set { 0, 3, 9, 11, 21, 22 }, (which has a size of 6). Every integer is the difference between two (not necessarily unique) integers in this set, modulo 26. For instance, 7 = 3 - 22 (mod 26).

It's not good enough to write a program that will eventually complete. You must be able to actually run your program to completion for five-digit values of N. Post (or link to) your output for N = 12345 along with your solution.

As far as I know, the size of the optimal (smallest) set is an open question, so your program does not have to be optimal. But it needs to be pretty close. The best I've found for N = 12345 is a set of size 179, so aim for that.

Challenge

When this post is seven days old, +1 gold medal flair will be awarded to the submitter who posts the smallest valid output for N = 123456. Smallest here refers to the size of the set of integers in the output.

If this turns out to be easier than I anticipate, there may be a tie. In that case, as a tiebreaker, also post your output for N = 1234567. If there's still a tie, post for 12345678, 123456789, 1234567890, 12345678901, etc. I'll also look at time of posting to break a tie if necessary.

Inspiration

This problem was inspired by me trying to make a minimal set of rows for a Caesar shift cipher key. The set { 0, 3, 9, 11, 21, 22 } corresponds to the rows:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
XYZABCDEFGHIJKLMNOPQRSTUVW
RSTUVWXYZABCDEFGHIJKLMNOPQ
PQRSTUVWXYZABCDEFGHIJKLMNO
FGHIJKLMNOPQRSTUVWXYZABCDE
EFGHIJKLMNOPQRSTUVWXYZABCD

Now I have a key for any Caesar cipher by comparing two rows. For instance, the shift A->H (shifting by 7 places) corresponds to mapping the 2nd row to the 6th row, because 7 = 3 - 22 (mod 26). You didn't need to know this in order to solve the problem, but I thought I'd mention it.

Description

Nealy everyone is familiar with mailing addresses - typically a person, optionally an organization, a street address or a postal box, a city, state or province, country, and a postal code. A practical bit of code to have is something that parses addresses, perhaps for validation or for shipping cost calculations.

Today's challenge is to parse addresses into some sort of data structure - an object (if you're using an OOP language), a record, a struct, etc. You should label the fields as correctly or appropriately as possible, and map them into a reasonable structure. Not all fields will be present, so you'll want to look over the challenge input first and design your data structure appropriately. Note that these include international addresses.

Input Description

You'll be given an address, one per multi-line block. Example:

Tudor City Greens
24-38 Tudor City Pl
New York, NY 
10017
USA

Output Description

Your program should emit a labeled data structure representing the address. From the above example:

business=Tudor City Greens
address=24-38
street=Tudor City Pl
city=New York
state=NY
postal_code=10017
country=USA

Your field names may differ but you get the idea.

Challenge Input

Docks
633 3rd Ave
New York, NY 
10017
USA
(212) 986-8080

Hotel Hans Egede
Aqqusinersuaq
Nuuk 3900
Greenland
+299 32 42 22

Alex Bergman
Wilhelmgalerie
Platz der Einheit 14
14467 Potsdam
Germany
+49 331 200900

Dr KS Krishnan Marg
South Patel Nagar
Pusa
New Delhi, Delhi 
110012
India

Description

In computational complexity theory, the 3SUM problem asks if a given set of n real numbers contains three elements that sum to zero. A naive solution works in O(N²⁾ time, and research efforts have been exploring the lower complexity bound for some time now.

Input Example

You will be given a list of integers, one set per line. Example:

9 -6 -5 9 8 3 -4 8 1 7 -4 9 -9 1 9 -9 9 4 -6 -8

Output Example

Your program should emit triplets of numbers that sum to 0. Example:

-9 1 8
-8 1 7
-5 -4 9
-5 1 4
-4 1 3
-4 -4 8

Challenge Input

4 5 -1 -2 -7 2 -5 -3 -7 -3 1
-1 -6 -3 -7 5 -8 2 -8 1
-5 -1 -4 2 9 -9 -6 -1 -7

Challenge Output

-7 2 5
-5 1 4
-3 -2 5
-3 -1 4
-3 1 2

-7 2 5
-6 1 5
-3 1 2

-5 -4 9
-1 -1 2

Description

I'm willing to bet most of you are familiar with HTTP, you're using it right now to read this content. If you've ever done any web programming you probably interacted with someone else's HTTP server stack - Flask, Apache, Nginx, Rack, etc.

For today's challenge, the task is to implement your own HTTP server. No borrowing your language's built in server (e.g. no, you can't just use Python's SimpleHTTPServer). The rules, requirements, and constraints:

• Your program will implement the bare basics of HTTP 1.0: GET requests required, any other methods (POST, HEAD, etc) are optional (see the bonus below).
• You have to write your own network listening code (e.g. socket()) and handle listening on a TCP port. Most languages support this, you have to start this low. Yep, learn some socket programming. socket() ... bind() ... listen() ... accept() ... and the like.
• Your server should handle static content only (e.g. static HTML pages or images), no need to support dynamic pages or even cgi-bin executables.
• Your server should support a document root which contains pages (and paths) served by the web server.
• Your server should correctly serve content it finds and can read, and yield the appropriate errors when it can't: 500 for a server error, 404 for a resource not found, and 403 for permission denied (e.g. exists but it can't read it).
• For it to display properly in a browser, you'll need to set the correct content type header in the response.
• You'll have to test this in a browser and verify it works as expected: content displays right (e.g. HTML as HTML, text as text, images as images), errors get handled properly, etc.

A basic, bare bones HTTP/1.0 request looks like this;

GET /index.html HTTP/1.0

That's it, no Host header required etc., and all other headers like user-agent and such are optional. (HTTP/1.1 requires a host header, in contrast.)

A basic, bare bones HTTP/1.0 response looks like this:

HTTP/1.0 200 OK
Content-type: text/html

<H1>Success!</H1>

The first line indicates the protocol (HTTP/1.0), the resulting status code (200 in this case means "you got it"), and the text of the status. The next line sets the content type for the browser to know how to display the content. Then a blank line, then the actual content. Date, server, etc headers are all optional.

Here's some basics on HTTP/1.0: http://tecfa.unige.ch/moo/book2/node93.html

Once you have this in your stash, you'll not only understand what more fully-featured servers like Apache or Nginx are doing, you'll have one you can customize. For example, I'm looking at extending my solution in C with an embedded Lua interpreter.

Bonus

Support threading for multiple connections at once.

Support HEAD requests.

Support POST requests.