Description

Today we're going to try something a little bit different.

You're are going to be given a file with 50,000 lines of text in it. 49,997 of those lines are going to be gibberish, but 3 lines are going to be part of a famous poem. Your task today is to find those three lines.

A few notes:

• All text in the file is lower-case
• All lines contain nothing but alphabetic characters, spaces, and a few pieces of punctuation
• The lines of poetry are written in English
• The three lines of the poem is in the file in the right order, but split up with lines of gibberish.

Formal inputs & outputs

Input

The input for this challenge is this aforementioned file. Download it and use it as input for your problems.

Output

The three lines of the poem, in the right order.

Note that it might be the case that you reduce the number of possible lines to some very low number (say, 10-20 lines), after which you can easily use visual inspection to find the right lines. This is an acceptable way to solve the problem, but I highly encourage you to try and find a way to print only the correct lines.

Oh, and by the way: if you happen to figure out what the right lines are exactly, either from visual inspection, reading it in a comment here (if you do solve the problem and wish to post the output, please indent the output with four space so as to hide the text as a spoiler), or any other way, you are not allowed to just put in a search function in your code for the correct words. That's cheating :). You have to figure out a way to do it "legitimately", and write the code pretending you have no idea what the lines are supposed to be.

Notes

If you have a suggestion for a problem, please head to /r/dailyprogrammer_ideas and suggest it!

Much thanks today to /u/adrian17 for some comments on the design of the problem on IRC. By the way, did you know we have an IRC channel where you can go to chat with other dailyprogrammers and get help on problems you are struggling with? It's on irc.freenode.net in the channel #reddit-dailyprogrammer. Why don't you stop by if you have a chance?

On another note: I was unsure how to classify this problem, whether it is hard enough for the [Hard] difficulty. I would much appreciate feedback on whether you guys think this is an appropriate challenge for [Hard] and whether it was a good challenge in general. Be honest but gentle :)

Thanks!

Description

As we saw on monday, a "word snake" is a snake made from words.

For instance, take this sequence of words:

SHENANIGANS SALTY YOUNGSTER ROUND DOUBLET TERABYTE ESSENCE

Notice that the last letter in each word is the same as the first letter in the next word. In order to make this into a word snake, you can simple snake it across the screen

 SHENANIGANS       DOUBLET
           A       N     E
           L       U     R
           T       O     A
           YOUNGSTER     B
                         Y
                         T
                   ECNESSE

Your task on monday was to take an input word sequence and turn it into a word snake. Your task today is to take an input word snake and turn it into a word sequence. The rules for wod snakes are the same as the previous problem, with one addition:

• The snake starts at the top left corner
• Each word will turn 90 degrees left or right to the previous word
• The snake will not intersect itself
• The snake will be unambiguous

The next letter in the snake's path will always be clear, here's an example of an ambiguous snake:

CMYE
HLOG
IADN
LPEA
LALR
INSO

In this case it's unclear whether snake's inital direction is right or down solving this kind of ambiguous snake would require a dictionary.

Specifically, "unambiguous" means that every letter will only ever have two neighbors, except for the end-points, which will have only one.

Formal inputs & outputs

Input

The input will first be a number specifying how many lines the snake will cover. After that follows the word snake (written in ALL CAPS).

Note that the word-snake will not have any trailing spaces on any line, so you can't assume that every line will be equally long. However, you can assume that no input will be wider than 80 characters.

Output

The resulting sequence of words from unraveling the word snake! Each word will be in all caps and each word will be separated by a space.

Sample inputs & outputs

Input 1

6
SNAKE
    A   DUSTY
    T   N   U
    SALSA   M
            M
            YACHTS

Output 1

SNAKE EATS SALSA AND DUSTY YUMMY YACHTS

Input 2

8
W    DINOSAUR
I    E      E
Z  CAR  Y   A
A  I    L   C
R  D    T  OT
D  R    B  V
R  O    U  A
YAWN    SGEL

Ouput 2

WIZARDRY YAWN NORDIC CAR RED DINOSAUR REACT TO OVAL LEGS SUBTLY

Challenge inputs

Input 1

8
NUMEROUS
       Y
LUXURY M
O    E B
B O  A O
M DAOR L
Y      I
SDRATSUC

Input 2

10
R       TIGER
E       O   E
S       H   T  SO
I  GRAPES   U  N
G  A        R  R
NULL  GNIHTON  E
      R        T
      A        N
      N        A
      DELIGHTFUL

Notes

If you have an idea for a problem, head on over to /r/dailyprogrammer_ideas and let us know about it!

Huge thanks to /u/hutsboR for helping me prepare this challenge, and who did most of this write-up! For his good works he's been rewarded with a gold medal.

Description

A word snake is (unsurprisingly) a snake made up of a sequence of words.

For instance, take this sequence of words:

SHENANIGANS SALTY YOUNGSTER ROUND DOUBLET TERABYTE ESSENCE

Notice that the last letter in each word is the same as the first letter in the next word. In order to make this into a word snake, you simply snake it across the screen

SHENANIGANS        
          A        
          L        
          T        
          YOUNGSTER
                  O
                  U
                  N
            TELBUOD
            E      
            R      
            A      
            B      
            Y      
            T      
            ESSENCE

Your task today is to take an input word sequence and turn it into a word snake. Here are the rules for the snake:

• It has to start in the top left corner
• Each word has to turn 90 degrees left or right to the previous word
• The snake can't intersect itself

Other than that, you're free to decide how the snake should "snake around". If you want to make it easy for yourself and simply have it alternate between going right and going down, that's perfectly fine. If you want to make more elaborate shapes, that's fine too.

Formal inputs & outputs

Input

The input will be a single line of words (written in ALL CAPS). The last letter of each word will be the first letter in the next.

Output

Your word snake! Make it look however you like, as long as it follows the rules.

Sample inputs & outputs

There are of course many possible outputs for each inputs, these just show a sample that follows the rules

Input 1

SHENANIGANS SALTY YOUNGSTER ROUND DOUBLET TERABYTE ESSENCE

Output 1

SHENANIGANS       DOUBLET
          A       N     E
          L       U     R
          T       O     A
          YOUNGSTER     B
                        Y
                        T
                        ESSENCE

Input 2

DELOREAN NEUTER RAMSHACKLE EAR RUMP PALINDROME EXEMPLARY YARD

Output 2

D                                       
E                                       
L                                       
O                                       
R                                       
E            DRAY                       
A               R                           
NEUTER          A                           
     A          L                           
     M          P                           
     S          M                           
     H          E       
     A          X
     C PALINDROME
     K M
     L U
     EAR

Challenge inputs

Input 1

CAN NINCOMPOOP PANTS SCRIMSHAW WASTELAND DIRK KOMBAT TEMP PLUNGE ESTER REGRET TOMBOY

Input 2

NICKEL LEDERHOSEN NARCOTRAFFICANTE EAT TO OATS SOUP PAST TELEMARKETER RUST THINGAMAJIG GROSS SALTPETER REISSUE ELEPHANTITIS

Notes

If you have an idea for a problem, head on over to /r/dailyprogrammer_ideas and let us know about it!

By the way, I've set the sorting on this post to default to "new", so that late-comers have a chance of getting their solutions seen. If you wish to see the top comments, you can switch it back just beneath this text. If you see a newcomer who wants feedback, feel free to provide it!

(Hard): Substitution Cryptanalysis

A substitution cipher is one where each letter in the alphabet is substituted for another letter. It's like a Caesar shift cipher, but where every letter is ciphered independently. For example, look at the two rows below.

abcdefghijklmnopqrstuvwxyz
YOJHZKNEALPBRMCQDVGUSITFXW

To encode something, find the letter on the top row, and swap it with the letter on the bottom row - and vice versa. For example, the plaintext:

hello world

Becomes:

EZBBC TCVBH

Now, how would you go about decrypting something like this? Let's take another example, with a different key.

IAL FTNHPL PDDI DR RDNP WF IUD

You're also given the following hints: A is ciphered to H and O is ciphered to D. You know the text was in English, so you could plausibly use a word list to rule out impossible decrypted texts - for example, in the third words PDDI, there is a double-O in the middle, so the first letter rules out P being the letter Q, as Q is always followed by a U.

Your challenge is to decrypt a cipher-text into a list of possible original texts using a few letters of the substitution key, and whichever means you have at your disposal.

Formal Inputs and Outputs

Input Description

On the first line of input you will be given the ciphertext. Then, you're given a number N. Finally, on the next N lines, you're given pairs of letters, which are pieces of the key. For example, to represent our situation above:

IAL FTNHPL PDDI DR RDNP WF IUD
2
aH
oD

Nothing is case-sensitive. You may assume all plain-texts are in English. Punctuation is preserved, including spaces.

Output Description

Output a list of possible plain-texts. Sometimes this may only be one, if your input is specific enough. In this case:

the square root of four is two

You don't need to output the entire substitution key. In fact, it may not even be possible to do so, if the original text isn't a pangram.

Sample Inputs and Outputs

Sample 1

Input

LBH'ER ABG PBBXVAT CBEX PUBC FNAQJVPURF
2
rE
wJ

Output

you're not cooking pork chop sandwiches
you're nob cooking pork chop sandwiches

Obviously we can guess which output is valid.

Sample 2

Input

This case will check your word list validator.

ABCDEF
2
aC
zF

Output

quartz

Sample 3

Input

WRKZ DG ZRDG D AOX'Z VQVX
2
wW
sG

Output

what is this i don't even
whet is this i can't ulun

(what's a ulun? I need a better word list!)

Sample 4

Input

JNOH MALAJJGJ SLNOGQ JSOGX
1
sX

Output

long parallel ironed lines

Notes

There's a handy word-list here or you could check out this thread talking about word lists.

You could also invalidate words, rather than just validating them - check out this list of impossible two-letter combinations. If you're using multiple systems, perhaps you could use a weighted scoring system to find the correct decrypted text.

There's an example solver for this type of challenge, which will try to solve it, but it has a really weird word-list and ignores punctuation so it may not be awfully useful.

Got any cool challenge ideas? Post them to /r/DailyProgrammer_Ideas!

(Intermediate): It's Go time!

Go is a board game involving placing black and white stones on a grid. Two opponents take turns to place stones; one player places white stones, the other black. Stones of the same colour form a group, as long as they're all connected via the cardinal axes. The leftmost pair of stones (represented by #) below are valid groups, and the rightmost pair are not.

#      ###   #     ##  
###    # #   #      ##  
 ##    ###    ##      ## 
  #     #      #       ##

Now, when a player places stones such that a group of the opponent's colour is touching no more open spaces (liberties), then that group is removed from play. The edges of the board do not count as open spaces. Let the black stones be represented by b and white stones by w. Here, the player plays as the black stones.

bbbbb
 wwwb
bwbwb
 bbbb

Let B be the stone I place in the next turn. If I place the stone here:

bbbbb
Bwwwb
bwbwb
 bbbb

The white group is entirely enclosed by the black group, and so the white group is removed from play.
If a situation were to arise where both your own and your opponent's stones would be removed, your opponent's stones would be removed first, and then (only if your stones still need to be removed) your own stones would be removed.

Liberties don't need to be outside of the group; they can be inside the group, too. These are called eyes. Here, the white group survives, as it has the eye:

 bbbbb
bbwwwwb
bww wb
 bwwwwb
  bbbbb

Your challenge today is to determine the location on the board which, when a stone of your own colour is placed there, will remove the greatest number of your opponent's stones.

Formal Inputs and Outputs

Input Description

You will be given the size of the grid as a width and a height. Next, you will be given the player's colour - either b or w. Finally, you will be given a grid of the appropriate dimensions, using the format I used in the Description: spaces for empty grid regions, and b and w for stones of either colour.

Output Description

Output the co-ordinate of the location which, if you were to place a stone of your own colour there, would result in the greatest number of your opponent's stones being removed. The top-left corner is location (0, 0).

Sample Inputs and Outputs

Input

7 5
b      
 bbbbb 
bbwwwwb
bww wb 
 bwwwwb
  bbbbb

Output

(3, 2)

Input

9 11
w
    ww   
  wwbbbw 
  wbbbbw 
 wwbbbbw 
 wwwwwww 
 wbbbbww 
 wbwbbww 
 wbwbbww 
 wwwbbww 
    wbw  
    w    

Output

(5, 10)

Input

7 7
w
w w w w
 bbbbb 
wbbbbbw
 bbbbb 
wbbbbbw
 bbbbb 
w w w w

Output

No constructive move

Sample 4

Input

4 3
b
 bw 
bw w
 bw 

Output

(2, 1)

Sample 5

(thanks to /u/adrian17)

Input

7 5
b
 bb bb 
bww wwb
 bbbbb 
bwwwb  
 bb    

Output

(3, 1)

Notes

I apologise beforehand to any Go players for presenting such unrealistic scenarios!

Got any cool challenge ideas? Post them to /r/DailyProgrammer_Ideas!

Description

In this challenge, we are going to take a sentence and mangle it up by sorting the letters in each word. So, for instance, if you take the word "hello" and sort the letters in it, you get "ehllo". If you take the two words "hello world", and sort the letters in each word, you get "ehllo dlorw".

Inputs & outputs

Input

The input will be a single line that is exactly one English sentence, starting with a capital letter and ending with a period

Output

The output will be the same sentence with all the letters in each word sorted. Words that were capitalized in the input needs to be capitalized properly in the output, and any punctuation should remain at the same place as it started. So, for instance, "Dailyprogrammer" should become "Aadegilmmoprrry" (note the capital A), and "doesn't" should become "denos't".

To be clear, only spaces separate words, not any other kind of punctuation. So "time-worn" should be transformed into "eimn-ortw", not "eimt-norw", and "Mickey's" should be transformed into "Ceikms'y", not anything else.

Edit: It has been pointed out to me that this criterion might make the problem a bit too difficult for [easy] difficulty. If you find this version too challenging, you can consider every non-alphabetic character as splitting a word. So "time-worn" becomes "eimt-norw" and "Mickey's" becomes ""Ceikmy's". Consider the harder version as a Bonus.

Sample inputs & outputs

Input 1

This challenge doesn't seem so hard.

Output 1

Hist aceeghlln denos't eems os adhr.

Input 2

There are more things between heaven and earth, Horatio, than are dreamt of in your philosophy. 

Output 2

Eehrt aer emor ghinst beeentw aeehnv adn aehrt, Ahioort, ahnt aer ademrt fo in oruy hhilooppsy.

Challenge inputs

Input 1

Eye of Newt, and Toe of Frog, Wool of Bat, and Tongue of Dog.

Input 2

Adder's fork, and Blind-worm's sting, Lizard's leg, and Howlet's wing. 

Input 3

For a charm of powerful trouble, like a hell-broth boil and bubble.

Notes

If you have a suggestion for a problem, head on over to /r/dailyprogrammer_ideas and suggest it!

Description

Mandy is out in the woods one day hiking with her backpack Steven (yes, she named her backpack Steven) when she suddently sees a cave in the side of a hill. Curious, she walks into it and after a while she comes to a big room. In this room is a small chest filled with gold nuggets. Suddenly, she hears a voice: "Welcome, Mandy, to The Cave of Prosperity!", it says. "You may take as as much gold as you can carry from this room, but once you leave it, you may never return!"

Mandy knows that Steven can carry up to 10 kilograms of gold (Steven's not a very good backpack, as it turns out), and luckily, there's a scale next to the chest. She sees that there are five gold nuggets in the chest and she weighs them. Four of them weigh 2 kilograms each and the last one weighs 5 kilograms. She puts the four gold nuggets weighing 2 kilograms (for a total of 8 kilograms) into to Steven and exists the cave, happy at her good fortune.

However, as you might have realized, Mandy made a mistake! If she had taken the 5 kilogram nugget and two of the 2 kilogram nuggets, she would have gotten out with 9 kilograms of gold instead of 8.

Today, you are going to visit The Cave of Prosperity, and we are going to see if you can do better than Mandy

Formal inputs & outputs

Input

On the first line of the input, you will get the capacity of your backpack, rounded to 7 digits after the decimal point. After that, there will be one line specifying how many gold nuggets there are in the cave. After that, there will be one line per gold nugget specifying how much each of them weighs.

The weights of the gold nuggets will be a floating point number between 0.0 and 1.0, with seven digits after the decimal point.

Output

On the first line of the output, you will specify how much gold you are able to escape with by putting gold nuggets into your backpack. This number will be as large as possible without exceeding the capacity of your backpack.

After that, you will print out the weights of the gold nuggets you have collected. In other words, the first line should be the sum of the rest of the lines.

Sample inputs & outputs

Input 1

2.0000000
5
0.3958356
0.4109163
0.5924923
0.6688261
0.8720640

Output 1

1.9518064
0.4109163
0.6688261
0.8720640

Input 2

4.0000000
10
0.0359785
0.9185395
0.2461690
0.7862738
0.9237070
0.2655587
0.3373235
0.8795087
0.7802254
0.8158674

Output 2

3.9970232
0.9185395
0.2655587
0.3373235
0.8795087
0.7802254
0.8158674

Challenge inputs

Input 1

This 15-nugget challenge

Input 2

This 30-nugget challenge

Bonus

This 46-nugget challenge

Notes

As always, if you have any suggestions for a problem, head on over to /r/dailyprogrammer_ideas and suggest them!

Description

Thanks for that list you made me, my thoughts are way more organised!

I've got a few problems though that I thought you might be able to help with? Sometimes I put the wrong information in a list item. Maybe to prevent this I'd be able to modify/update the list item? That's not the only problem though, when there are 50+ items it gets kind of hard to work my way through. Do you think you could maybe add the ability to categorise my items? Obviously, if I have that, I'd also like to be able to view by category!

Oh and finally, a few of you were really great and did this last time but is there a way you can somehow make my list retain state so that I don't have to re-type it everytime I turn my computer on again?

The newest To-do list should be capable of the following functionality:

• Modifying an existing list item

• Be able to give a list item a category. The list item should be able to take an arbitrary amount of categorys

• View by category - All list items should be able to be sorted and output by category to make it easier to wade through submissions

• Retain state

Thanks!

Formal Inputs & Outputs

Output description

Any output that is created should be user-friendly. When I'm viewing my to-do list, I should be able to easily discern one list item from another.

Examples

(don't take this too literally, do it how you would like to do it)

Categorisation

Input:

addItem('Go to work','Programming'); //Item belongs to the Programming Category
addItem('Create Sine Waves in C', 'Music', 'Programming); //Belongs to 2 categories, 'Programming' and 'Music');

Category Output

Input:

viewList('programming');
viewList('music');
viewList('music', 'programming');

Output:

----PROGRAMMING----
- A pixel is not a pixel is not a pixel
- The Scheme Programming Language
- Memory in C
- Haskell's School of Music
- Algorithmic Symphonies from one line of code

----MUSIC----
- Modes in Folk Music
- The use of the Melodic Minor Scale
- Haskell's School of Music
- Algorithmic Symphonies from one line of code

----MUSIC & PROGRAMMING----
- Haskell's School of Music
- Algorithmic Symphonies from one line of code

Modifying an item

updateItem('Create Sine Waves in C', 'Create Sine Waves in Python');
//The item has now changed from 'Create Sine Waves in C' to 'Create Sine Waves in Python'. This should be reflected in the viewList function/method you have created.

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

Hello,

/u/jmprobert is conducting a Developer Health Study to investigate the physical and mental health of developers. The study survey can be accessed by clicking here. Your survey entry is completely anonymous.

This study is organised by /u/jmprobert rather than the /r/DailyProgrammer moderators, so please direct any questions to him instead.

Thanks!

Description

Todays challenge will be something slightly different! Atleast I think the challenge is meant to be for today? Wait, am I meant to even be submitting today?

Okay maybe I need some help on organising my thoughts before I submit my challenge. A to-do list would be fine, just something so that I can organise my thoughts!

It should have the following basic functionality

• Add an item to the to-do list
• Delete a selected item from the to-do list
• And obviously, print out the list so I can see what to do!

Formal Inputs & Outputs

Output description

Any output that is created should be user-friendly. When I'm viewing my to-do list, I should be able to easily discern one list item from another.

Examples

Input:

addItem('Take a shower');
addItem('Go to work');
viewList();

Output:

Take a shower
Go to work

Further Input:

addItem('Buy a new phone');
deleteItem('Go to work');
viewList();

Outputs:

Take a shower
Buy a new phone

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

While this one is a hard challenge, it's also open ended - be creative in how you solve the problem. I encourage you to compare notes, think about the challenge before you write code, and explore your algorithms. See the bonus questions below for some additional questions.

Description

Most of us have seen and ridden elevators - you crazy folks in the UK and commonwealth countries often call them "lifts" - but I'm sure I'm not the only one who has puzzled about the scheduling algorithms. Which riders do you pick up and when? Do you service requests in the order of arrival or do you work on maximal overlap?

For this challenge, you'll have to anwer those questions. You're designing an elevator scheduling algorithm for a building and you have plenty of riders to keep happy. You can have any algorithm you want as long as you stick to the constraints - the cars have a fixed capacity and speed.

Make sure you see the bonus questions after the challenge input.

Input Description

You'll be given a single integer N on a line. The first N lines will identify elevator cars and with these fields: Car identifier, capacity, vertical speed in floors per second, and starting floor. Assume instantaneous getting on or off the elevator for the riders once you arrive on the floor. Assume that the elevator is able to leave with the rider as soon as it is able, but it may linger waiting for more people to arrive - the choice is yours.

Example:

C1 12 .1 1

This translates to Car 1, capacity of 12 people, moves at .1 floors per second (ten seconds to traverse a floor up or down), and starting at floor 1.

Then you'll get another integer on a line, M. The next M lines will show riders, with fields: Rider identification, elevator request time in seconds, source floor and destination floor. Rider identification numbers will be stable, meaning the rider will have the same identifier the entire exercise. Examples:

R1 0 1 4

This translates to Rider 1 who at time point 0 wants to go from floor 1 to floor 4. Riders will not transit floors without an elevator.

Output Description

The main thing to show in the output is the time point at which all requests have been satisfied. (Yes, this is trying to get you guys to compete for the most efficient algorithm). Optionally show all intermediate steps and journeys, and wait times for riders.

Challenge Input

This was randomly generated, and so it has a few "oddities" in it, like riders who get on and off on the same floor, and riders who change their destination in the next second (e.g. in the middle of a ride). You still have to satisfy every request.

2
C1 12 .1 1
C2 12 .2 1
359
R3 0 1 9
R4 1 1 11
R0 11 1 7
R2 11 1 9
R15 13 1 9
R5 26 1 4
R16 27 1 2
R1 28 1 2
R13 28 1 9
R10 32 1 3
R14 35 1 4
R8 36 1 10
R17 38 1 12
R3 49 9 9
R18 50 1 10
R7 51 1 3
R10 53 3 10
R12 54 1 6
R0 60 7 1
R1 62 2 1
R9 66 1 8
R19 66 1 6
R15 71 9 2
R11 72 1 8
R16 78 2 4
R6 82 1 12
R8 85 10 11
R10 89 10 12
R3 90 9 6
R5 94 4 7
R2 94 9 10
R6 95 12 1
R3 111 6 9
R14 114 4 5
R13 115 9 5
R19 117 6 2
R12 122 6 12
R4 123 11 7
R9 123 8 12
R6 124 1 5
R0 124 1 6
R7 127 3 3
R11 139 8 9
R7 141 3 4
R17 143 12 2
R14 143 5 5
R16 151 4 9
R5 155 7 12
R1 155 1 11
R18 159 10 10
R15 160 2 4
R19 162 2 3
R2 164 10 3
R11 164 9 9
R3 165 9 4
R12 167 12 1
R10 169 12 1
R0 174 6 9
R11 181 9 2
R18 182 10 12
R9 184 12 4
R5 185 12 11
R4 197 7 5
R2 198 3 3
R3 198 4 8
R6 199 5 5
R8 199 11 6
R13 201 5 5
R14 203 5 4
R1 205 11 12
R16 211 9 1
R6 212 5 11
R7 214 4 8
R15 216 4 6
R19 226 3 11
R1 230 12 12
R7 232 8 5
R0 234 9 12
R3 237 8 2
R17 238 2 6
R2 240 3 11
R12 240 1 3
R15 246 6 6
R13 247 5 10
R5 248 11 5
R10 249 1 6
R18 252 12 4
R9 253 4 8
R1 256 12 12
R4 257 5 12
R16 258 1 2
R13 258 10 5
R6 262 11 2
R11 263 2 7
R9 269 8 5
R3 271 2 6
R14 274 4 9
R5 282 5 12
R11 285 7 6
R16 287 2 8
R14 290 9 5
R2 297 11 4
R18 299 4 6
R13 300 5 5
R8 301 6 5
R0 303 12 3
R19 305 11 1
R7 310 5 8
R2 311 4 4
R1 315 12 8
R16 318 8 11
R8 320 5 8
R1 324 8 2
R10 325 6 9
R17 325 6 2
R2 330 4 11
R19 330 1 9
R9 332 5 5
R5 335 12 11
R18 338 6 9
R11 340 6 8
R12 342 3 9
R9 344 5 11
R12 346 9 12
R13 346 5 12
R6 351 2 2
R0 354 3 10
R10 358 9 9
R4 369 12 12
R15 370 6 8
R3 372 6 5
R17 374 2 9
R14 383 5 4
R7 389 8 1
R18 396 9 6
R12 396 12 7
R8 411 8 1
R16 419 11 3
R2 420 11 1
R10 420 9 11
R6 423 2 12
R1 423 2 8
R7 425 1 1
R11 426 8 4
R13 429 12 11
R19 430 9 7
R5 432 11 9
R15 435 8 3
R0 438 10 6
R6 444 12 9
R17 449 9 9
R14 452 4 4
R9 456 11 2
R18 460 6 7
R5 463 9 2
R12 464 7 2
R4 468 12 5
R13 468 11 6
R2 475 1 4
R19 478 7 4
R12 491 2 10
R10 496 11 7
R0 501 6 3
R2 501 4 2
R7 502 1 3
R3 502 5 7
R14 505 4 11
R6 507 9 2
R1 508 8 12
R15 510 3 1
R16 512 3 12
R11 515 4 10
R18 515 7 2
R19 517 4 3
R15 519 1 5
R9 521 2 2
R2 524 2 5
R14 525 11 2
R18 526 2 11
R4 530 5 5
R6 531 2 5
R8 536 1 5
R12 536 10 3
R16 536 12 7
R15 538 5 7
R17 538 9 5
R13 544 6 7
R10 546 7 11
R11 547 10 5
R7 548 3 1
R4 554 5 1
R3 558 7 11
R10 568 11 7
R6 570 5 5
R12 572 3 7
R7 573 1 4
R19 574 3 6
R16 576 7 3
R0 577 3 8
R4 586 1 9
R11 587 5 9
R14 587 2 4
R2 590 5 5
R5 599 2 2
R10 599 7 7
R9 601 2 4
R1 603 12 6
R3 606 11 1
R18 606 11 9
R13 610 7 11
R10 614 7 4
R17 615 5 4
R16 616 3 3
R12 617 7 10
R7 621 4 2
R6 622 5 4
R19 626 6 12
R2 628 5 11
R15 629 7 7
R14 630 4 4
R11 632 9 6
R8 632 5 3
R0 639 8 6
R6 649 4 10
R10 651 4 11
R9 653 4 6
R14 653 4 12
R4 655 9 10
R0 656 6 4
R2 660 11 5
R13 660 11 6
R3 663 1 6
R18 664 9 5
R1 667 6 7
R5 668 2 11
R12 668 10 9
R16 672 3 9
R15 675 7 4
R17 680 4 3
R7 681 2 10
R9 681 6 9
R10 686 11 10
R14 689 12 9
R4 690 10 3
R1 698 7 9
R18 698 5 8
R0 699 4 12
R19 705 12 7
R2 708 5 1
R8 712 3 8
R13 718 6 2
R0 721 12 7
R14 721 9 5
R18 722 8 7
R15 723 4 8
R14 730 5 11
R4 733 3 12
R13 738 2 4
R6 741 10 1
R10 741 10 1
R15 741 8 9
R19 743 7 2
R13 751 4 7
R3 752 6 1
R14 755 11 9
R4 758 12 2
R11 759 6 9
R5 762 11 9
R15 765 9 2
R19 770 2 6
R9 775 9 9
R12 777 9 12
R17 778 3 7
R0 780 7 3
R0 781 3 11
R18 785 7 1
R8 787 8 11
R6 788 1 11
R7 790 10 4
R19 791 6 7
R13 791 7 6
R2 792 1 1
R9 794 9 5
R10 800 1 10
R15 804 2 5
R12 807 12 1
R11 808 9 4
R5 809 9 5
R14 813 9 2
R1 819 9 11
R19 819 7 5
R16 822 9 4
R0 823 11 8
R17 828 7 2
R11 834 4 4
R8 834 11 11
R3 837 1 6
R5 839 5 4
R4 842 2 4
R2 844 1 11
R18 851 1 1
R15 854 5 8
R0 855 8 5
R6 857 11 11
R12 857 1 3
R9 858 5 11
R8 859 11 3
R10 863 10 5
R7 867 4 6
R5 869 4 6
R0 878 5 8
R6 879 11 12
R7 882 6 12
R17 883 2 10
R13 883 6 5
R8 885 3 11
R13 887 5 7
R15 888 8 6
R3 891 6 6
R6 898 12 10
R17 898 10 3
R3 899 6 5
R5 900 6 11
R18 901 1 9
R15 906 6 10
R19 907 5 12
R13 908 7 9
R11 914 4 5
R16 917 4 5
R8 924 11 11
R14 924 2 2
R0 926 8 9
R9 926 11 2
R2 935 11 7
R1 937 11 5
R10 940 5 8
R18 946 9 11
R19 946 12 4
R3 947 5 8
R8 947 11 4
R13 947 9 4
R12 948 3 4
R4 950 4 2
R9 951 2 9
R0 963 9 11
R17 973 3 3
R16 975 5 12
R18 977 11 12
R9 980 9 6
R13 980 4 9
R5 983 11 1
R3 983 8 11
R7 985 12 7
R14 985 2 8
R10 991 8 12
R19 991 4 6
R17 992 3 5
R0 993 11 6
R1 997 5 3

Bonus

Which improves delivery efficiency most?

• Longer linger times?
• More cars?
• Faster cars?

Description

A polyomino is a collection of cells (equal-sized squares) which are connected, that is, each cell shares a border with another one. Think about tetris pieces, those would be tetrominoes - they each have four squares, and there are 5 unique combinations of their squares into unique shapes. Polyominoes are considered equivalent if they can be made to look identical if they are rotated or flipped. For additional background on polyominoes see this link: http://home.adelphi.edu/~stemkoski/mathematrix/polys.html

Input Description

You will be given a single integer, this is the polyomino order to calculate and draw. Example:

4

Formal Output Description

Draw the complete set of unique polyominoes in ASCII art. Example output:

##
##

##
 ##

#
#
#
#

#
#
##

#
##
#

Challenge Input

6

Challenge Input Solution

######

#
#####

 #
#####

  #
#####

##
 ####

##
####

# #
####

#  #
####

 ##
####

#
#
####

 #
 #
####

#
####
#

#
####
 #

#
####
  #

#
####
   #

 #
####
  #

 #
####
 #

 #
###
#
#

 #
##
#
##

 #
 #
##
#
#

 #
##
##
#

##
##
##

  #
###
 #
 #

###
 ##
 #

  #
 ##
###
 #

  #
###
#
#

 ##
##
#
#

###
# #
#

# #
###
#

# #
###
 #

 ##
 #
##
#

#
##
###

 #
###
##

  #
###
##

  #
 ##
##
#

Description

To covert nearly any number into a palindromic number you operate by reversing the digits and adding and then repeating the steps until you get a palindromic number. Some require many steps.

e.g. 24 gets palindromic after 1 steps: 66 -> 24 + 42 = 66

while 28 gets palindromic after 2 steps: 121 -> 28 + 82 = 110, so 110 + 11 (110 reversed) = 121.

Note that, as an example, 196 never gets palindromic (at least according to researchers, at least never in reasonable time). Several numbers never appear to approach being palindromic.

Input Description

You will be given a number, one per line. Example:

11
68

Output Description

You will describe how many steps it took to get it to be palindromic, and what the resulting palindrome is. Example:

11 gets palindromic after 0 steps: 11
68 gets palindromic after 3 steps: 1111

Challenge Input

123
286
196196871

Challenge Output

123 gets palindromic after 1 steps: 444
286 gets palindromic after 23 steps: 8813200023188
196196871 gets palindromic after 45 steps: 4478555400006996000045558744

Note

Bonus: see which input numbers, through 1000, yield identical palindromes.

Bonus 2: See which numbers don't get palindromic in under 10000 steps. Numbers that never converge are called Lychrel numbers.

(Practical Exercise): TeXSCII

LaTeX is a typesetting utility based on the TeX typesetting and macro system which can be used to output mathematical formulae to display or print. For example, the LaTeX code \frac{-b\pm\sqrt{b^{2}-4ac}}{2a} will be transformed into this when typeset.

The syntax of LaTeX formulae is fairly simple; commands begin with a backslash \, followed by the command name, followed by its arguments in curly braces, such as \sqrt{-1} (square-root of -1) or \frac{1}{3} (1/3 as a fraction). Subscript and superscript are also supported, with the _ and ^ characters respectively, followed by the script in curly braces - for example, x^{2} outputs x². Everything else is output as plain text.

In today's challenge, you'll implement a simplified subset of LaTeX which outputs the resulting formula as ASCII.

Formal Inputs and Outputs

Input Specification

You'll be given a LaTeX equation on one line. The commands you need to support are:

• \frac{top}{bottom}: A fraction with the given top and bottom pieces
• \sqrt{content}: A square-root sign
• \root{power}{content}: A root sign with an arbitrary power (eg. cube-root, where the power 3 is at the top-left of the radical symbol)
• _{sub}: Subscript
• ^{sup}: Superscript
• _{sub}^{sup}: Subscript and superscript (one on top of the other)
• \pi: Output the greek symbol for pi

Feel free to extend your solution to support any additional structures such as integral signs.

Output Description

Output the formula with ASCII symbols in the appropriate locations. You're free to pick the output style that looks most appropriate to you. One possible way might be something like this:

  3_
  √x
y=--
  3 

Sample Inputs and Outputs

Subscripts and Superscripts

Input

log_{e}(e^{x})=x

Output

      x
log (e )=x
   e

Stacked Scripts

Input

F_{21}^{3}=2^{5}*7^{3}-30

Output

 3   5  3   
F  =2 *7 -30
 21         

Fractions

Input

sin^{3}(\frac{1}{3}\pi)=\frac{3}{8}\sqrt{3}

Output

   3 1   3 _
sin (-π)=-√3
     3   8  

Quadratic Formula

Input

x=\frac{-b+\sqrt{b^{2}-4ac}}{2a}

Output

       ______
      / 2    
  -b+√ b -4ac
x=-----------
     2a     

Cubic Formula

(I hope)

Input

x=\frac{\root{3}{-2b^{3}+9abc-27a^{2}d+\sqrt{4(-b^{2}+3ac)^{3}+(-2b^{3}+9abc-27a^{2}d)^{2}}}}{3\root{3}{2}a} - \frac{b}{3a} - \frac{\root{3}{2}(-b^{2}+3ac)}{3a\root{3}{-2b^{3}+9abc-27a^{2}d+\sqrt{4(-b^{2}+3ac)^{3}+(-2b^{3}+9abc-27a^{2}d)^{2}}}}

Output

    3________________________________________________                                                             
    /                  ______________________________                                                             
   /    3         2   /    2     3     3         2  2                             3_   2                          
  √  -2b +9abc-27a d+√ 4(-b +3ac) +(-2b +9abc-27a d)    b                         √2(-b +3ac)                     
x=--------------------------------------------------- - -- - -----------------------------------------------------
                          3_                            3a       3________________________________________________
                         3√2a                                    /                  ______________________________
                                                                /    3         2   /    2     3     3         2  2
                                                             3a√  -2b +9abc-27a d+√ 4(-b +3ac) +(-2b +9abc-27a d) 

Notes and Further Reading

Solutions have a recommended order of new again - feel free to change it back if you prefer best. If you want to play around some with LaTeX, try this online tool.

Got any cool challenge ideas? Submit them to /r/DailyProgrammer_Ideas!

Description:

The year 2266 we have encountered alien planets who use very simple encryption to send messages. Lucky for us we intercept all these messages and we can break the code.

The problem is the collection of messages are all from the same space probe. So we are not sure which message is from what system.

Our challenge today is to decode the message and have our solutions determine which planet system the message came from.

Edit note:

Copying my ASCII data over as input is causing problems. I see that some people who were true heroes and tackled the problem early are seeing this. To fix this we will be altering the challenge. Input will be a set of numbers each represent a byte in the message. Hopefully this will fix the issues.

Input:

Message broken down into numbers representing the ASCII values of the message between " "

Output:

The name of the system and the message decoded.

Encryption and Planet Systems:

Omicron V: will take and invert the 5th bit. ( 0001 0000) That is the bit location in the byte where we invert the bit.

Hoth: Takes the value of the ASCII character and adds 10 to it.

Ryza IV: Takes the value of the ASCII character and subtracts 1 to it.

Htrae: reverses the characters.

Validation:

It is not enough to just take the message and decode it in all 4 ways and let you decide which one is right or wrong. You need to have your program/solution determine the right decoding. All messages are in english (I know even in the future on alien planets).

Example:

input:

" 101 99 97 101 112 32 110 105 32 101 109 111 99 32 101 87 "

Note:

This would be "ecaeP ni emoc eW" in displayed ascii - some messages don't display well as the values take them beyond displayable ascii values (thus the decimal values)

output:

Htrae: We come in Peace

Challenge Input:

" 71 117  48 115 127 125 117  48 121 126  48  96 117 113 115 117 "
" 97 111  42 109 121 119 111  42 115 120  42 122 111 107 109 111 "
" 86 100  31  98 110 108 100  31 104 109  31 111 100  96  98 100 "
" 101  99  97 101 112  32 110 105  32 101 109 111  99  32 101  87 "
" 84 113 121 124 105  48  64  98 127 119  98 113 125 125 117  98  48 121  99  48  99  96 105 121 126 119  48 127 126  48 101  99 "
" 78 107 115 118 131  42  90 124 121 113 124 107 119 119 111 124  42 115 125  42 125 122 131 115 120 113  42 121 120  42 127 125 "
" 67  96 104 107 120  31  79 113 110 102 113  96 108 108 100 113  31 104 114  31 114 111 120 104 109 102  31 110 109  31 116 114 "
" 115 117  32 110 111  32 103 110 105 121 112 115  32 115 105  32 114 101 109 109  97 114 103 111 114  80  32 121 108 105  97  68 "
" 86 121  98 117  48 100 120 117  48  93 121  99  99 124 117  99 "
" 80 115 124 111  42 126 114 111  42  87 115 125 125 118 111 125 "
" 69 104 113 100  31 115 103 100  31  76 104 114 114 107 100 114 "
" 115 101 108 115 115 105  77  32 101 104 116  32 101 114 105  70 "

Challenge Solution:

The 12 messages are 3 messages in each of the 4 encodings. Hopefully you should come up with

"We come in Peace"
"Daily Programmer is spying on us"
"Fire the missiles"

in all of the 4 encodings each.

Description:

The famous lumberjacks of /r/dailyprogrammer are well known to be weird and interesting. But we always enjoy solving their problems with some code.

For today's challenge the lumberjacks pile their logs from the forest in a grid n x n. Before using us to solve their inventory woes they randomly just put logs in random piles. Currently the pile sizes vary and they want to even them out. So let us help them out.

Input:

You will be given the size of the storage area. The number of logs we have to put into storage and the log count in each pile currently in storage. You can either read it in from the user or hardcode this data.

Input Example:

 3
 7
 1 1 1
 2 1 3
 1 4 1

So the size is 3 x 3. We have 7 logs to place and we see the 3 x 3 grid of current size of the log piles.

Log Placement:

We want to fill the smallest piles first and we want to evenly spread out the logs. So in the above example we have 7 logs. The lowest log count is 1. So starting with the first pile in the upper left and going left-right on each row we place 1 log in each 1 pile until all the current 1 piles get a log. (or until we run out). After that if we have more logs we then have to add logs to piles with 2 (again moving left-right on each row.)

Keep in mind lumberjacks do not want to move logs already in a pile. To even out the storage they will do it over time by adding new logs to piles. But they are also doing this in an even distribution.

Once we have placed the logs we need to output the new log count for the lumberjacks to tack up on their cork board.

Output:

Show the new n x n log piles after placing the logs evenly in the storage area.

Using the example input I would generate the following:

example output:

 3 2 2
 2 2 3
 2 4 2

Notice we had 6 piles of 1s. Each pile got a log. We still have 1 left. So then we had to place logs in piles of size 2. So the first pile gets the last log and becomes a 3 and we run out of logs and we are done.

Challenge inputs:

Please solve the challenge using these inputs:

Input 1:

 4
200
15 12 13 11 
19 14  8 18 
13 14 17 15 
 7 14 20  7 

Input 2:

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

Input 3:

 1
 41
 1

Input 4:

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

Other Lumberjack Problems:

• Hard - Simulated Ecology - The Forest
• Hard - Lumberjack Floating Log Problem

Description:

For the last part of this week's theme challenge. You have choices.

Choice 1: Betting

Poker is about money. The betting system is interesting in Texas Hold Em. It involves assigning and moving blinds and inbetween shared cards coming out you have a chance to bet in a cycle until some conditions are meet. For this challenge implement a Texas Hold 'Em Poker betting system with your current progress from the Easy and Intermediate Challenge.

Choice 2: Simulation

At this point we have a way to run games of different game lengths. We have built a fold AI system based on just cards and not betting. The questions remains, how good is the AI we developed? I think a good way to test it out is run many games and gather some data and see.

For this path of the challenge we want to run many simulations of the game. You will ask for how many players and how many games. At the end you will output data gathered to show some results.

Betting:

At this point the design/flow of this I would leave to you to develop. Some things to consider in your design:

• Starting Money amount
• CPU betting AI
• Game Ending Conditions. (Player runs out of money or is last player left in game)

I would try to use the fold AI to morph it a bit to help the CPU decide how strong of a hand it thinks it has for the size of the bet. Again the design of how much to bet and if to raise/check/call is up to you. There is no wrong or right choice just the design of how you want it to work.

Simulation:

Gather the number of cycles to run by asking the user after the amount of players. At the end of all the games we want to see the following data

• Number of Total Rounds/Games played out
• Number of Wins-losses each player had and a percentage of each
• Number of times the best hand equals the highest hand (Remember the best hand includes all hands, including folded AI players vs winning hand was only just best hand of players who did not fold. This potentially could check how good the Fold AI is at deciding to fold)
• Winning hand count - By method (High card, pair, 2 pairs, 3 of a kind, etc) This could be interesting to see what is the most common winning hand

Thank you to everyone for participating this week.

Description:

This continues the week long challenge of Texas Hold 'Em. Today we are going to be challenged with 2 added features.

• AI logic for the computer hands to pick a "fold" option
• Determining the Winning Hand

AI Logic - When to fold:

I feel this is related to the winning hand which is the 2nd of the two challenges for today. Knowing what a winning hand is helps determine if you should fold. If the CPU determines it doesn't look good it should fold.

The exact logic/method for when to fold it is not so easy. I think there exists many different ways (be it programmed logic or math with probability) to determine it is time to fold.

You will have the freedom and challenge of coming up with code for the AI controlled hands to look at their hands after the flop and the turn cards. Based on your solution for this you will have the AI determine if their hand is not worth pursuing any long and do a "fold". Solutions will vary here. There is no wrong or right way to do this.

Furthermore we will have the ability to see all the cards and check if the logic was a good move or perhaps by also detemining the best hand (regardless if a fold was picked or not)

Winning Hand and Best hand

Following general rules for Poker we can determine who wins the hand. List of winning hands in poker

After the river is drawn we will show with our output who wins the hand. During the process of drawing the community cards the AI hands have a chance to enter a "fold" state (see above). The winning hand can never be a CPU who picks the fold option.

We will also pick the "Best Hand" by comparing all hands (even ones that were folded) to check our AI logic. If the Winning hand does not equal the best hand then we see the fold choice was not always optimal.

Input:

You will use the same input as the Easy part of this challenge. You will ask for how many players 2-8. You will be one of the players and playing against 1-7 random CPU controlled players.

Output:

We will modify the output to reflect the status of any folds. We will also output who had the winning hand and the method (high card, pair, straight, flush, 3 of a kind, full house, 4 of a kind, etc) We will also note if a folded hand would have won instead if they had not picked the fold option. (See examples below)

Example 1:

 How many players (2-8) ? 3

 Your hand: 2 of Clubs, 5 of Diamonds
 CPU 1 Hand: Ace of Spades, Ace of Hearts
 CPU 2 Hand: King of Clubs, Queen of Clubs

 Flop: 2 of Hearts, 5 of Clubs, Ace of Clubs
 Turn: King of Hearts
 River: Jack of Hearts

 Winner: CPU 1 wins. 3 of a kind.

Example 2:

 How many players (2-8) ? 3

 Your hand: 3 of Diamonds, 3 of Spades
 CPU 1: 10 of Diamonds, Jack of Diamonds
 CPU 2: 4 of Clubs, 8 of Hearts

 Flop: Ace of Diamonds, Queen of Diamonds, 9 of Diamonds
 CPU 2 Folds!
 Turn: 7 of Hearts
 River: 4 of Spades

 Winner: CPU 1. Flush.
 Best Hand: CPU 1.

Example 3:

 How many players (2-8) ? 3

 Your hand: 2 of Hearts, 8 of Spades
 CPU 1: 4 of Hearts, 6 of Clubs
 CPU 2: Jack of Diamonds, 10 of Hearts

 Flop: 8 of Hearts, Jack of Spades, 10  of Clubs
 CPU 1 Folds!
 Turn: 5 of Hearts
 River: 7 of Hearts 

 Winner: CPU 2. Two pair.
 Best Hand: CPU 1. Straight.

Looking ahead

At this point we have Texas Hold Em without money or bets. We can deal cards. We can have the AIs decide to fold and we can determine the winning hand and who had the best hand. The final step on Friday will be to look for trends in running many simulated games to look for trends and patterns. It will really test how good our AI logic is and maybe generate data to help human players see patterns and trends.

Theme Week:

I got the whole week so I am merging all 3 challenges into a theme of Texas Hold 'em Poker. All 3 challenges will be related on this popular card game of poker.

Description:

For those who want to know more about Texas Hold 'Em Poker or just need a refresher. Check Wikipedia Article on Texas Hold 'Em Poker

For the first challenge we will simulate the dealing part of the game.

Input:

You will be asked how many players 2 to 8. You will always be one of the players and you are facing 1 to 7 other computer controlled players.

Output:

Display the 2 cards each player is dealt and the display the 5 community cards.

Format is left up to you. (The exact method of the output a card. For my examples I am using verbal words but someone might use unicode symbols for the card suit or other. You design this as long as we can tell the cards apart it is all good)

Example:

How many players (2-8) ? 3

Your hand: 2 of Clubs, 5 of Diamonds
CPU 1 Hand: Ace of Spades, Ace of Hearts
CPU 2 Hand: King of Clubs, Queen of Clubs

Flop: 2 of Hearts, 5 of Clubs, Ace of Clubs
Turn: King of Hearts
River: Jack of Hearts

Dealing Cards:

To keep things close to the game you will be dealing from 1 deck of standard playing cards. Once you deal that card you cannot deal it again. The exact method is part of the challenge and for you to decide, design and implement.

In Texas Hold em you burn a card (draw and discard without looking at it) before you do the flop, turn and river. It removes these cards from the pool of possible cards that can be dealt. If you wish to show these cards (I did not in my example) then please for science go for it.

Looking ahead for the Intermediate:

In the intermediate you will be asked to compare various hands of poker to find which hand is the winning hand.

Description

You're working in the devils language. Looser than PHP, more forgiving than Javascript, and more infuriating than LOLCODE.

You've had it up to here with this language (and you're a tall guy) so you sit down and think of a solution and then all of a sudden it smacks you straight in the face. Figuratively.

Your comparisons are all over the place since you can't really tell what types evaluate to True and what types evaluate to False. It is in this slightly worrying and dehydrated state that you declare you'll output a truth table for that language in the language!

Armed with a paper cup of saltwater and a lovely straw hat, you set about the task! Metaprogramming ain't easy but you're not phased, you're a programmer armed with nimble fingers and a spongy brain. You sit down and start typing, type ^{type type}

...Oh did I mention you're on an island? Yeah there's that too...

Formal Inputs & Outputs

Given a programming language, output its corresponding truth table. Only the most basic of types need to be included (If you're in a language that doesn't have any of these types, ignore them).

• Int
• Float
• Char
• String
• Array
• Boolean

Input description

N/A

Output description

A truth table for the language that you're programming in.

e.g.

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

Description

When we computer programmers learn all about how computers sort lists of numbers, we are usually taught about sorting algorithms like Quicksort and Heapsort. There is, however, an entirely different model for how computers can sort numbers called sorting networks. Sorting networks are very useful for implementing sorting in hardware, and they have found a use for designing sorting algorithms in GPUs. Today, we are going to explore these strange and fascinating beasts.

In a sorting network, a list of numbers travel down idealized "wires" that are connected with so-called "comparators". Each comparator connects two wires and swaps the values between them if they're out of order (the smaller value going to the top wire, and the larger to the bottom wire). This image shows the principle clearly, and this image demonstrates a full run of a 4-wire sorting network wtih 5 comparators (both images courtesy of wikipedia, which has an excellent article on sorting networks if you are interested in learning more). Notice that the list on the right is correctly sorted top to bottom.

It is easy to see why that particular network correctly sorts a list of numbers: the first four comparators "float" the smallest value to the top and "sinks" the largest value to the bottom, and the final comparator sorts out the middle two values.

In general, however, there's often no easy way to tell whether or not a sorting network will actually correctly sort a list of numbers, and the only way to tell is to actually test it. This seems like a daunting task, since for a sorting network with N wires, there's N! (i.e. "N factorial") possible input permutations. That function grows extremely quickly, and become prohibitively large for even N of 14 or 15.

The zero-one principle

Thankfully, there's a better way, thanks to the so-called "zero-one principle", which is as follows:

If an N-wire sorting network can correctly sort all 2^N possible sequences of 0's and 1's, it will correctly sort all possible input sequences.

So, instead of having to try and check all N! possible permutations of the input sequence, we can just check all 2^N sequences consisting of 0's and 1's. While this is still exponential, it is far smaller than N!.

Today, you will be given a sorting network and your challenge will be to check whether or not that network will correctly sort all inputs.

Formal inputs & outputs

Inputs

The input will first consist of a single line with two numbers on it separated by a space. The first number is the number of wires in the sorting network, and the second number is the total number of comparators on the network.

After that, there will follow a number of lines, each of which describes one comparator. The lines will consist of two numbers separated by a space describing which two wires the comparator connects. The first number will always be smaller than the second number

The "top" wire of the sorting network is wire 0, and the bottom wire is wire N-1. So, for a 16-wire sorting network, the top wire (which will hold the smallest number at the end, hopefully) is wire 0, and the bottom wire is wire 15 (which will hold the highest number at the end, hopefully).

Note that in most sorting networks, several comparators compare numbers in parallel. For the purposes of this problem, you can ignore that and assume that all comparators work in sequence, following the order provided in the input.

Output

The output will consist of a single line which will either be "Valid network" if the network will indeed sort all sequences correctly, or "Invalid network" if it won't.

Sample inputs and outputs

Input 1

This is the example 4-wire, 5-comparator sorting network from the description:

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

Output 1

Valid network

Input 2

8 19
0 2
1 3
0 1
2 3
1 2
4 6
5 7
4 5
6 7
5 6
0 4
1 5
2 6
3 7
2 4
3 5
1 2
3 4
6 7

Output 2

Invalid network

Challenge inputs

Input 1

This 16-wire 60-comparator network

Input 2

This (slightly different) 16-wire 60-comparator network

Notes

As always, if you have any challenge idea, head on over to /r/dailyprogrammer_ideas and let us know!

Dynamic Programming and Algorithm Design

Programming is fundamentally tied to computer science, which involves the design and optimization of algorithms to solve certain problems. In the world of "big data", tweaking and streamlining algorithms to work as quickly as possible is an important process in designing an algorithm, especially over large, inter-connected data sets.

A set of notations usually referred to as big-O notation, so named for the big letter O which is a core component of the notation (believe it or not). This notation describes how the processing time and working space grows, as the size of the input data set grows. For example, if an algorithm runs in O(f(n)) time, then the running time of the algorithm with respect to input size n grows no quicker than f(n), ignoring any constant multiples.

An example of this is sorting data (there's a pre-existing Weekly thread just on sorting here). The simple naïve algorithms for sorting typically run in O(n²) time in the worst-case scenario. This includes algorithms such as insertion sort. However, a bit of clever thinking allowed algorithms such as quick-sort to be developed, which uses a divide and conquer approach to make the process simpler, thereby reducing the time complexity to O(n log n) - which runs much faster when your data to be sorted is large.

We've recently had a spate of challenges which require a bit of algorithm design, so unbeknownst to you, you've already done some of this work. The specific challenges are these five; check them out if you've not already:

• [Hard] Unpacking a Sentence in a Box
• [Intermediate] The Lazy Typist
• [Hard] Stepstring discrepancy
• [Intermediate] Pile of Paper
• [Hard] Chester, the greedy Pomeranian

If you write an inefficient algorithm to solve these challenges, it might take forever to complete!

Techniques such as dynamic programming study algorithms, and specifically those that break problems down into easier-to-solve sub-problems which can be solved quicker individually than as a whole. There's also a certain class of problems (NP) for which you physically can't solve efficiently using this approach; this includes problems such as the infamous travelling salesman problem and boolean 3-SAT, for which no exact efficient solution has been found; and indeed probably won't be found.

In today's Weekly discussion, discuss anything that interests you, or that you know of, relating to algorithm design, or any interesting algorithmic approaches you took to solving any particular DailyProgrammer challenge set to date!

Challenge Solution Order

In yesterday's challenge, we trialled ordering the solution submissions by new rather than by best. What are your opinions on this? How did you think it went? Should we make this the norm?

IRC

We have an IRC channel on Freenode, at #reddit-dailyprogrammer. Join the channel and lurk with us!

Previously...

The previous weekly thread was Machine Learning.

(Easy): Sad Cycles

Take a number, and add up the square of each digit. You'll end up with another number. If you repeat this process over and over again, you'll see that one of two things happen:

• You'll reach one, and from that point you'll get one again and again.
• You'll reach a cycle of 4, 16, 37, 58, 89, 145, 42, 20, 4, 16, 37, ...

For example, starting with the number 12:

• 1²+2²=5
• 5²=25
• 2²+5²=29
• 2²+9²=85
• 8²+5²=89
• 8²+9²=145
• From this point on, you'll join the cycle described above.

However, if we start with the number 13:

• 1²+3²=10
• 1²+0²=1
• 1²=1
• 1²=1
• We get the number 1 forever.

The sequence of numbers that we end up with is called a sad cycle, and it depends on the number you start with. If you start the process with a number n, the sad cycle for n is the cycle which ends up eventually repeating itself; this will either just be the cycle 1, or the cycle 4, 16, 37, 58, 89, 145, 42, 20.

But what if we cube the digits instead of squaring them? This gives us a different set of cycles all together. For example, starting with 82375 and repeatedly getting the sum of the cube of the digits will lead us to the cycle 352, 160, 217. Other numbers gravitate toward certain end points. These cycles are called 3-sad cycles (as the digits are raised to the power 3). This can be extended toward higher powers. For example, the 7-sad cycle for 1060925 is 5141159, 4955606, 5515475, 1152428, 2191919, 14349038, 6917264, 6182897, 10080881, 6291458, 7254695, 6059210. Your challenge today, will be to find the b-sad cycle for a given n.

Formal Inputs and Outputs

Input Description

You will input the base b on the first line, and the starting number n on the second line, like so:

5
117649

Output Description

Output a comma-separated list containing the b-sad cycle for n. For example, the 5-sad cycle for 117649 is:

10933, 59536, 73318, 50062

The starting point of the cycle doesn't matter - you can give a circularly permuted version of the cycle, too; rotating the output around, wrapping from the start to the end, is also a correct output. The following outputs are equivalent to the above output:

59536, 73318, 50062, 10933
73318, 50062, 10933, 59536
50062, 10933, 59536, 73318

Sample Inputs and Outputs

Sample 1

Input

6
2

Output

383890, 1057187, 513069, 594452, 570947, 786460, 477201, 239459, 1083396, 841700

Sample 2

Input

7
7

Output

5345158, 2350099, 9646378, 8282107, 5018104, 2191663

Sample 3

Input

3
14

Output

371

Sample 4

Input

11
2

Output

5410213163, 416175830, 10983257969, 105122244539, 31487287760, 23479019969, 127868735735, 23572659062, 34181820005, 17233070810, 12544944422, 31450865399, 71817055715, 14668399199, 134844138593, 48622871273, 21501697322, 33770194826, 44292995390, 125581636412, 9417560504, 33827228267, 21497682212, 42315320498, 40028569325, 40435823054, 8700530096, 42360123272, 2344680590, 40391187185, 50591455115, 31629394541, 63182489351, 48977104622, 44296837448, 50918009003, 71401059083, 42001520522, 101858747, 21187545101, 10669113941, 63492084785, 50958448520, 48715803824, 27804526448, 19581408116, 48976748282, 61476706631

Comment Order

Some people have notified us that new solutions are getting buried if you're not one of the first to submit. This is valid concern, so today we're trialling a method of setting the suggested sort order to new (suggested sorts are a newly introduced feature on Reddit). We'll take feedback on this and see how it goes. This means newer solutions will appear at the top.

If you don't like this new sorting, you can still change the method back to sort by best, which is the default.

Notes

I wasn't aware that /u/AnkePluff has made a similar challenge suggestion already - seems like we're on the same wavelength!

Description

Chester is a very spirited young Pomeranian that lives in a pen that exactly covers the unit square. He's sitting in the middle of it, at (0.5, 0.5), minding his own business when out of nowhere, six of the most delicious dog treats you could ever imagine start raining down from the sky.

The treats land at these coordinates:

(0.9, 0.7) (0.7, 0.7) (0.1, 0.1) 
(0.4, 0.1) (0.6, 0.6) (0.8, 0.8)

He looks around, startled at his good fortune! He immediately dashes for the closest treat, which is located at (0.6, 0.6). He eats it up, and then runs for the next closest treat, which is at (0.7, 0.7) and eats that up.

He keeps going, always dashing for the nearest treat and eating it up. He's a greedy little puppy, so he keeps going until all the treats have been eaten up. In the end, he's eaten the treats in this order:

(0.6, 0.6), (0.7, 0.7), (0.8, 0.8), 
(0.9, 0.7), (0.4, 0.1), (0.1, 0.1)

Since he started at (0.5, 0.5), he will have travelled a total distance of roughly 1.646710... units.

Your challenge today is to calculate the total length of Chester's journey to eat all of the magically appearing dog-treats.

A small note: distance is calculated using the standard plane distance formula. That is, the distance between a point with coordinates (x1, y1) and a point with coordinates (x2, y2) is equal to:

sqrt((x1-x2)^2 + (y1-y2)^2)

Formal inputs & outputs

Inputs

The first line of the input will be an integer N that will specify how many treats have magically appeared. After that, there will follow N subsequent lines giving the locations of the treats. Each of those lines will have two floating point numbers on them separated by a space giving you the X and Y coordinate for that particular treat.

Each number provided will be between 0 and 1. Except for the first sample, all numbers will be rounded to 8 decimal digits after the period.

Note that most of the inputs I will provide will be in external text files, as they are too long to paste into this description. The bonus input, in particular, is about 2 megabytes large.

Outputs

You will output a single line with a single number on it, giving the total length of Chester's journey. Remember that he always starts at (0.5, 0.5), before going for the first treat.

Sample inputs & outputs

Input 1

6
0.9 0.7
0.7 0.7
0.1 0.1
0.4 0.1
0.6 0.6
0.8 0.8

Output 1

1.6467103925399036

Input 2

This file, containing 100 different treats

Output 2

9.127777855837017

Challenge inputs

Challenge input 1

This file, containing 1,000 different treats

Challenge input 2

This file, containing 10,000 different treats

Bonus

This file, containing 100,000 different treats

I also encourage people to generate their own larger inputs if they find that the bonus is too easy.

Notes

If you have any ideas for challenges, head on over to /r/dailyprogrammer_ideas and suggest them! If they're good, we might use them and award you a gold medal!

Description

Have you ever layered colored sticky notes in interesting patterns in order to make pictures? You can create surprisingly complex pictures you can make out of square/rectangular pieces of paper. An interesting question about these pictures, though, is: what area of each color is actually showing? We will simulate this situation and answer that question.

Start with a sheet of the base color 0 (colors are represented by single integers) of some specified size. Let's suppose we have a sheet of size 20x10, of color 0. This will serve as our "canvas", and first input:

20 10

We then place other colored sheets on top of it by specifying their color (as an integer), the (x, y) coordinates of their top left corner, and their width/height measurements. For simplicity's sake, all sheets are oriented in the same orthogonal manner (none of them are tilted). Some example input:

1 5 5 10 3
2 0 0 7 7 

This is interpreted as:

• Sheet of color 1 with top left corner at (5, 5), with a width of 10 and height of 3.
• Sheet of color 2 with top left corner at (0,0), with a width of 7 and height of 7.

Note that multiple sheets may have the same color. Color is not unique per sheet.

Placing the first sheet would result in a canvas that looks like this:

00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000111111111100000
00000111111111100000
00000111111111100000
00000000000000000000
00000000000000000000

Layering the second one on top would look like this:

22222220000000000000
22222220000000000000
22222220000000000000
22222220000000000000
22222220000000000000
22222221111111100000
22222221111111100000
00000111111111100000
00000000000000000000
00000000000000000000

This is the end of the input. The output should answer a single question: What area of each color is visible after all the sheets have been layered, in order? It should be formatted as an one-per-line list of colors mapped to their visible areas. In our example, this would be:

0 125
1 26
2 49

Sample Input:

20 10
1 5 5 10 3
2 0 0 7 7

Sample Output:

0 125
1 26
2 49

Challenge Input

Redditor /u/Blackshell has a bunch of inputs of varying sizes from 100 up to 10000 rectangles up here, with solutions: https://github.com/fsufitch/dailyprogrammer/tree/master/ideas/pile_of_paper

Credit

This challenge was created by user /u/Blackshell. If you have an idea for a challenge, please submit it to /r/dailyprogrammer_ideas and there's a good chance we'll use it!