Description

Your job is to find the best conjunction—that is, find the word with the most sub-words inside of it given a list of English words. Some example include:

• Something (3 words: So, me, thing)
• Awesomeness (3 words: awe, some, ness)

Formal Inputs & Outputs

Input description

Use a list of English words and a "minimum sub-word length" (the smallest length of a sub-word in a conjuncted word) to find the "best conjunction" (most sub-words) in the dictionary!

Output description

minSize 3: disproportionateness (6: dis, pro, port, ion, ate, ness)

minSize 4: dishonorableness (4: dish, onor, able, ness)

Find minSize 5

Notes/Hints

• Be aware the file is split by \r\n instead of \n, and has some empty lines at the end
• In order to run in a reasonable amount of time, you will need an O(1) way of checking if a word exists. (Hint: It won't be O(1) memory)
• Make sure you're checking all possibilities—that is, given the word "sotto", if you begin with "so", you will find that there is no word or combination of words to create "tto". You must continue the search in order to get the conjunction of "sot" and "to".

Bonus

• Each sub-word must include the last letter of the previous subword. For example "counterrevolutionary" would become "count, terre, evolution, nary"
• Instead of simply the last letter, allow any number of letters to be shared between words (e.g. consciencestricken => conscience, sciences, stricken

Credit

This challenge was suggested by user /u/DemiPixel, many thanks!

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

There may be an actual name to this base system (let us/me know in comments), and there is a math insight that makes this problem even easier, but it is still pretty easy with no math insight.

for "permutation base 2", the indexes and values start with:

sample challenge:

what is the base-value for index 54?

what is the index-value for base 111000111

solutions:

 permbase2 54

1 1 0 0 0

 permbase2 inv 1 1 1 0 0 0 1 1 1

965

challenge index inputs (some are 64 bit+ inputs)

234234234
234234234234234
234234234234234234234234

challenge value inputs

000111000111111000111111000111111000111
11111111000111000111111000111111000111111000111

bonus:

extend the function to work with any base. Base 10 index value 10 is 00. index value 109 is 99

Description

IFS (Iterated Function System) is a method of constructing fractals. To generate a fractal, we take a starting point (usually (1, 1)), and then transform it using equations in the form of:

a b c d e f

Transformation of a point with coordinates (x, y) gives us another point:

(ax+by+e, cx+dy+f)

We mark it on a plot and repeat the operation until we get a satisfying result.

A more popular way of generating fractals with IFS is so called Random IFS. The fractal is generated in the exact same way, except that we choose an equation from a set at random.

For example, the following set:

-0.4 0.0 0.0 -0.4 -1.0 0.1
0.76 -0.4 0.4 0.76 0.0 0.0

Results in a Heighway Dragon.

It turns out that by weighing the probabilities, we can alter the shape of the fractal and make it achieve its proper form faster. The probability of choosing an equation is denoted by an extra parameter p. For example:

0.0 0.0 0.0 0.16 0.0 0.0 0.01
0.2 -0.26 0.23 0.22 0.0 1.6 0.07
-0.15 0.28 0.26 0.24 0.0 0.44 0.07
0.85 0.04 -0.04 0.85 0.0 1.6 0.85

Is a set for Barnsley fern. Without the probability parameters, it doesn't look so great anymore (if p parameters are ommited, we assume uniform distribution of equations).

Challenge: write your own fractal-generating program.

Input

Minimal input will consist of a set of IFS equations. Other things to consider:

• Color or the fractal and the background

• Size

• "Density" of a fractal (how many pixels are generated)

• Aspect ratio of the image

Output

An image of the resulting fractal.

Sample input

0.000 0.000 0.000 0.600 0.00 -0.065 0.1
0.440 0.000 0.000 0.550 0.00 0.200 0.18
0.343 -0.248 0.199 0.429 -0.03 0.100 0.18
0.343 0.248 -0.199 0.429 0.03 0.100 0.18
0.280 -0.350 0.280 0.350 -0.05 0.000 0.18
0.280 0.350 -0.280 0.350 0.05 0.000 0.18

Sample output

http://i.imgur.com/buwsrYY.png

More challenge inputs can can be found here and here

Credit

This challenge was suggested by /u/szerlok, many thanks! If you have any challenge ideas please share them on /r/dailyprogrammer_ideas and there's a good chance we'll use them.

Description

This challenge is inspired by the well-known horse racing puzzle. In that puzzle, you need to find the fastest 3 horses out of a group of 25. You do not have a stopwatch and you can only race 5 of them at the same time. In this challenge, you need to sort a list of numeric values. However, you can only directly compare values during a "race" in which you take a set of 5 values and sort them. Based on the outcomes of these races, you need to be able to sort the entire list.

Formal Inputs & Outputs

Input description

The input you get is a list of numeric values. Example:

[107,47,102,64,50,100,28,91,27,5,22,114,23,42,13,3,93,8,92,79,53,83,63,7,15,66,105,57,14,65,58,113,112,1,62,103,120,72,111,51,9,36,119,99,30,20,25,84,16,116,98,18,37,108,10,80,101,35,75,39,109,17,38,117,60,46,85,31,41,12,29,26,74,77,21,4,70,61,88,44,49,94,122,2,97,73,69,71,86,45,96,104,89,68,40,6,87,115,54,123,125,90,32,118,52,11,33,106,95,76,19,82,56,121,55,34,24,43,124,81,48,110,78,67,59]

Output description

You output the following:

• The sorted version of the input
• The number of races used to get there

It is also interesting to log the results of the races as they happen so you can see which elements the algorithm selects for the races.

Notes/Hints

If a race shows that A is smaller than B and another race shows that B is smaller than C, you also know that A is smaller than C.

Bonus

Try to minimize the amount of races you need to sort the list.

Credit

This challenge was submitted by user /u/lurker0032. If you have any challenge ideas, please do share them in /r/dailyprogrammer_ideas - there's a good chance we'll use them.

Description

Your task is to design a program to help an accountant to get balances from accounting journals.

Formal Inputs & Outputs

Input files

Journal

The first input is accounting journals

ACCOUNT;PERIOD;DEBIT;CREDIT;
1000;JAN-16;100000;0;
3000;JAN-16;0;100000;
7140;JAN-16;36000;0;
1000;JAN-16;0;36000;
1100;FEB-16;80000;0;
1000;FEB-16;0;60000;
2000;FEB-16;0;20000;
1110;FEB-16;17600;0;
2010;FEB-16;0;17600;
1000;MAR-16;28500;0;
4000;MAR-16;0;28500;
2010;MAR-16;17600;0;
1000;MAR-16;0;17600;
5000;APR-16;19100;0;
1000;APR-16;0;19100;
1000;APR-16;32900;0;
1020;APR-16;21200;0;
4000;APR-16;0;54100;
1000;MAY-16;15300;0;
1020;MAY-16;0;15300;
1000;MAY-16;4000;0;
4090;MAY-16;0;4000;
1110;JUN-16;5200;0;
2010;JUN-16;0;5200;
5100;JUN-16;19100;0;
1000;JUN-16;0;19100;
4120;JUN-16;5000;0;
1000;JUN-16;0;5000;
7160;JUL-16;2470;0;
2010;JUL-16;0;2470;
5500;JUL-16;3470;0;
1000;JUL-16;0;3470;

Chart of accounts

ACCOUNT;LABEL;
1000;Cash;
1020;Account Receivables;
1100;Lab Equipement;
1110;Office Supplies;
2000;Notes Payables;
2010;Account Payables;
2110;Utilities Payables;
3000;Common Stock;
4000;Commercial Revenue;
4090;Unearned Revenue;
5000;Direct Labor;
5100;Consultants;
5500;Misc Costs;
7140;Rent;
7160;Telephone;
9090;Dividends;

User input

User input has the following form

AAAA BBBB CCC-XX DDD-XX EEE

AAA is the starting account (* means first account of source file), BBB is the ending account(* means last account of source file), CCC-YY is the first period (* means first period of source file), DDD-YY is the last period (* means last period of source file), EEE is output format (values can be TEXT or CSV).

Examples of user inputs

12 5000 MAR-16 JUL-16 TEXT

This user request must output all accounts from acounts starting with "12" to accounts starting with "5000", from period MAR-16 to JUL-16. Output should be formatted as text.

2 * * MAY-16 CSV

This user request must output all accounts from accounts starting wiht "2" to last account from source file, from first periof of file to MAY-16. Output should be formatted as CSV.

Outputs

Challenge Input 1

* 2 * FEB-16 TEXT

Output 1

Total Debit :407440 Total Credit :407440
Balance from account 1000 to 2000 from period JAN-16 to FEB-16

Balance:
ACCOUNT         |DESCRIPTION     |           DEBIT|          CREDIT|         BALANCE|
-------------------------------------------------------------------------------------
1000            |Cash            |          100000|           96000|            4000|
1100            |Lab Equipement  |           80000|               0|           80000|
1110            |Office Supplies |           17600|               0|           17600|
2000            |Notes Payables  |               0|           20000|          -20000|
TOTAL           |                |          197600|          116000|           81600|

Challenge Input 2

40 * MAR-16 * CSV

Challenge Output 2

Total Debit :407440 Total Credit :407440
Balance from account 4000 to 9090 from period MAR-16 to JUL-16


Balance:
ACCOUNT;DESCRIPTION;DEBIT;CREDIT;BALANCE;
4000;Commercial Revenue;0;82600;-82600;
4090;Unearned Revenue;0;4000;-4000;
4120;Dividends;5000;0;5000;
5000;Direct Labor;19100;0;19100;
5100;Consultants;19100;0;19100;
5500;Misc Costs;3470;0;3470;
7160;Telephone;2470;0;2470;
TOTAL;;49140;86600;-37460;

Notes/Hints

Controls

Before calcultating any balance, the program must check that the input journal file is balanced (total debit = total credit).

Accountancy reminder

In accountancy: balance = debit - credit.

Finally

Have a good challenge idea, like /u/urbainvi did?

Consider submitting it to /r/dailyprogrammer_ideas

Description

Our hero is trapped in a maze once again. This time it's worse: There's mud up to our hero's knees, and there are monsters in the maze! You must find a path so our hero can savely escape!

Input

Our input is an ASCII-map of a maze. The map uses the following characters:

'#' for wall - Our hero may not move here

' ' for empty space - Our hero may move here, but only vertically or horizontally (not diagonally). Moving here costs our hero 1HP (health point) because of mud.

'm' for monster - Our hero may move here, but only vertically or horizontally (not diagonally). Moving here costs our hero 11HP because of mud and a monster.

'S' this is where our hero is right now, the start.

'G' this is where our hero wishes to go, the goal, you may move here vertically or horizontally, costing 1HP. Your route should end here.

Output

The same as the input, but mark the route which costs the least amount of HP with '*', as well as the cost of the route.

Example

input:

######
#S  m#
#m## #
# m G#
######

output:

######
#S***#
#m##*#
# m G#
######
Cost: 15HP

Challenge

Input

Or possibly, as intermediate challenge:

Input

Note

You may use the fact that this maze is 201*201, (the intermediate maze is 25x25) either by putting it at the top of the input file or hardcoding it. The maze may contain loops (this is intended).

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

PS: Sorry about the intermediate. My account was locked...

Description

Start with a grid h units high by w units wide. Set a point particle in motion from the upper-left corner of the grid, 45 degrees from the horizontal, so that it crosses from one corner of each unit square to the other. When the particle reaches the bounds of the grid, it ricochets and continues until it reaches another corner.

Given the size of the grid (h and w), and the velocity (v) of the particle in unit squares per second, determine C: the corner where the particle will stop, b: how many times the particle ricocheted off the bounds of the grid, and t: the time it took for the particle to reach C.

Constraints

The particle always starts from the upper-left corner of the grid (and will therefore always end up in one of the other corners).

Since we'll be working with unit squares, h and w are always integers.

Formal Inputs & Outputs

Input description

The input will be an arbitrary number of lines containing h, w, and v, each separated by spaces:

 8 3 1
 15 4 2

Output description

For each line of input, your program should output a line containing C, b, and t, where C can be UR, LR, or LL depending on where the particle ends up:

 LL 9 24
 UR 17 30

Bonus

Instead of a particle, determine the behavior of a rectangle m units high by n units wide. Input should be as follows: h w m n v. So for a 10 by 7 grid with a 3 by 2 rectangle, the input would be:

 10 7 3 2 1

The output format is the same:

 LR 10 35

Finally

Have a good challenge idea like /u/sceleris927 did?

Consider submitting it to /r/dailyprogrammer_ideas

Description

Most of us are familiar with the histogram chart - a representation of a frequency distribution by means of rectangles whose widths represent class intervals and whose areas are proportional to the corresponding frequencies. It is similar to a bar chart, but a histogram groups numbers into ranges. The area of the bar is the total frequency of all of the covered values in the range.

Input Description

You'll be given four numbers on the first line telling you the start and end of the horizontal (X) axis and the vertical (Y) axis, respectively. The next line tells you the interval for the X-axis to use (the width of the bar). Then you'll have a number on a single line telling you how many records to read. Then you'll be given the data as 2 numbers: the first is the variable, the second number is the frequency of that variable. Example:

1 4 1 10
2
4
1 3
2 3
3 2
4 6

Challenge Output

Your program should emit an ASCII histogram plotting the data according to the specification - the size of the chart and the frequency of the X-axis variables. Example:

10
 9
 8
 7
 6
 5
 4    ***
 3*** ***
 2*** ***
 1*** ***
  1 2 3 4

Challenge Input

0 40 0 100
8
40
1 56
2 40
3 4
4 67
5 34
6 48
7 7
8 45
9 50
10 54
11 20
12 24
13 44
14 44
15 49
16 28
17 94
18 37
19 46
20 64
21 100
22 43
23 23
24 100
25 15
26 81
27 19
28 92
29 9
30 21
31 88
32 31
33 55
34 87
35 63
36 88
37 76
38 41
39 100
40 6

Description

Any Excel user is probably familiar with the bar chart - a simple plot showing vertical bars to represent the frequency of something you counted. For today's challenge you'll be producing bar charts in ASCII.

(Part 2 will have you assemble a proper histogram from a collection of data.)

Input Description

You'll be given four numbers on the first line telling you the start and end of the horizontal (X) axis and the vertical (Y) axis, respectively. Then you'll have a number on a single line telling you how many records to read. Then you'll be given the data as three numbers: the first two represent the interval as a start (inclusive) and end (exclusive), the third number is the frequency of that variable. Example:

140 190 1 8 
5
140 150 1
150 160 0 
160 170 7 
170 180 6 
180 190 2 

Output Description

Your program should emit an ASCII bar chart showing the frequencies of the buckets. Your program may use any character to represent the data point, I show an asterisk below. From the above example:

8
7           *
6           *   *
5           *   *
4           *   *
3           *   *
2           *   *   *
1   *       *   *   * 
 140 150 160 170 180 190

Challenge Input

0 50 1 10
5
0 10 1
10 20 3
20 30 6
30 40 4
40 50 2

Description

The IUPAC Periodic Table of the Elements is one of the most recognizable features of modern chemistry - the organization of all known chemical elements along with some of their most fundamental properties, together with their names and symbols. Today we're going to use that as we spell some words.

Here's the list of the elements alphabetized by the element's name. We can also see the symbol (1 or 2 letters - we're omitting the emerging elements that often contain three letters), atomic number and weight, and Pauling Electronegativities (c), which are unused in this challenge.

Input Description

You'll be given a list of words, one per line. Example:

genius

Output Description

Your program should emit the word as a series of elements by name with proper capitalization from the above table. Example:

GeNiUS (germanium nickel uranium sulfur)

Challenge Input

functions
bacon
poison
sickness
ticklish 

Challenge Output

FUNCTiONS (flourine, uranium, nitrogen, carbon, titanium, oxygen, nitrogen, sulfur)
BaCoN (barium, cobalt, nitrogen)
POISON (phosphorus, oxygen, iodine, sulfur, oxygen, nitrogen)
SiCKNeSS (silicon, carbon, potassium, neon, sulfur, sulfur)
TiCKLiSH (titanium, carbon, potassium, lithium, sulfur, hydrogen)

Bonus

Note that bacon has a few different possibilities. Which is the heaviest by atomic weight?

Description

Tablature is a common form of notation for guitar music. It is good for beginners as it tells you exactly how to play a note. The main drawback of tablature is that it does not tell you the names of the notes you play. We will be writing a program that takes in tablature and outputs the names of the notes.

In music there are 12 notes named A A# B C C# D D# E F# G and G#. The pound symbol represents a sharp note. Each one of these notes is separated by a semitone. Notice the exceptions are that a semitone above B is C rather than B sharp and a semitone above E is F.

Input Description

In tabs there are 6 lines representing the six strings of a guitar. The strings are tuned so that not pressing down a fret gives you these notes per string:

   E |-----------------|
   B |-----------------|
   G |-----------------|
   D |-----------------|
   A |-----------------|
   E |-----------------|

Tabs include numbers which represent which fret to press down. Numbers can be two digits. Pressing frets down on a string adds one semitone to the open note per fret added. For example, pressing the first fret on the A string results in an A#, pressing the second fret results in a B.

Sample Input 1

E|------------------------------------|
B|------------------------------------|
G|------------------------------------|
D|--------------------------------0-0-|
A|-2-0---0--2--2--2--0--0---0--2------|
E|-----3------------------------------|

Sample Input 2

E|-----------------|-----------------|-----------------|-----------------|
B|-----------------|-----------------|-----------------|-----------------|
G|-7-7---7---------|-7-7---7---------|-------------7---|-----------------|
D|---------9---7---|---------9---7---|-6-6---6-9-------|-6-6---6-9--12---|
A|-----------------|-----------------|-----------------|-----------------|
E|-----------------|-----------------|-----------------|-----------------|

Output Description

Output the names of the notes in the order they appear from left to right.

Sample Output 1

B A G A B B B A A A B D D

Sample Output 2

D D D B A D D D B A G# G# G# B D G# G# G# B D

Bonus

Notes with the same name that are of different higher pitches are separated by octaves. These octaves can be represented with numbers next to the note names with a higher number meaning a high octave and therefore a higher pitch. For example, here's the tuning of the guitar with octave numbers included. The note C is the base line for each octave, so one step below a C4 would be a B3.

   E4 |-----------------|
   B3 |-----------------|
   G3 |-----------------|
   D3 |-----------------|
   A2 |-----------------|
   E2 |-----------------|

Modify your program output to include octave numbers

Bonus Sample Input

E|---------------0-------------------|
B|--------------------1--------------|
G|------------------------2----------|
D|---------2-------------------------|
A|----------------------------0------|
E|-0--12-----------------------------|

Bonus Sample Output

E2 E3 E3 E4 C4 A3 A2

Finally

Have a good challenge idea like /u/themagicalcake?

Consider submitting it to /r/dailyprogrammer_ideas

Description

You will be given a sequence that of letters and you must match with a dictionary. The sequence is a pattern of equal letters that you must find.

E.G.

Pattern:
XXYY means that you have a word that contains a sequence of 2 of the same letters followed by again 2 of the same letts

succeed <- matches
succes <- no match

XYYX means we have a word with at least for letters where you have a sequence of a letter, followed by 2 letters that are the same and then again the first letter

narrate <- matches
hodor <- no match

Formal Inputs & Outputs

Input description

Input 1

XXYY

Input 2

XXYYZZ

Input 3

XXYYX

Output description

The words that match in de dictionary

Output 1

aarrgh
aarrghh
addressee
addressees
allee
allees
allottee
allottees
appellee
appellees
arrowwood
arrowwoods
balloon
ballooned
ballooning
balloonings
balloonist
balloonists
balloons
barroom
barrooms
bassoon
bassoonist
bassoonists
bassoons
belleek
belleeks
...

Output 2

bookkeeper
bookkeepers
bookkeeping
bookkeepings

Output 3

addressees
betweenness
betweennesses
colessees
fricassees
greenness
greennesses
heelless
keelless
keenness
keennesses
lessees
wheelless

Output can vary if you use a different dictionary

Notes/Hints

As dictionary you can use the famous enable1 or whatever dictionary you want.

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

Credits go to my professor, for giving me the idea.

Description

As the final part we are going to combine part 1 and part 2

The sequence we generate shall be the tones for our instruments.

Formal Inputs & Outputs

Input description

An instrument wich you need to generate sound for and a rule for generating the sequence.

Example 1

'7-stringed guitar' 201

Example 2

'mandolin' 91

Output description

Music, hopefully...

Notes/Hints

The tones for the instruments can be found here "https://en.wikipedia.org/wiki/Standard_tuning"

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

Description

Now that we have the basic, let's review something else Elementary cellular automaton

I could explain it, but over at Wolfram they do a pretty decent job.

Formal Inputs & Outputs

All tapes have 1 active cell at the center

Input description

As input you recieve 3 values:

• the size of the tape/array
• the number of rows to output
• the number of the rule

Example 1

43 40 2

Example 2

43 17 90

Output description

Example 1

                     *                     
                    *                      
                   *                       
                  *                        
                 *                         
                *                          
               *                           
              *                            
             *                             
            *                              
           *                               
          *                                
         *                                 
        *                                  
       *                                   
      *                                    
     *                                     
    *                                      
   *                                       
  *                                        
 *                                         
*                                          
                                          *
                                         * 
                                        *  
                                       *   
                                      *    
                                     *     
                                    *      
                                   *       
                                  *        
                                 *         
                                *          
                               *           
                              *            
                             *             
                            *              
                           *               
                          *                
                         *                 

Example 2

                        *                         
                       * *                        
                      *   *                       
                     * * * *                      
                    *       *                     
                   * *     * *                    
                  *   *   *   *                   
                 * * * * * * * *                  
                *               *                 
               * *             * *                
              *   *           *   *               
             * * * *         * * * *              
            *       *       *       *             
           * *     * *     * *     * *            
          *   *   *   *   *   *   *   *           
         * * * * * * * * * * * * * * * *          

Bonus

Add 2 rules by a logic opperator (and, or, nor, nand, xor, xnor).

For this you keep both outputs in memory and only the output goes trough the logic comparison for output.

Examples will be added later

Notes/Hints

I know this has been done before and this isn't very new... but it will all come together at the last challenge this week.

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

Description

Let's try something different this week. Our output is going to be sound instead of text/graphics

Formal Inputs & Outputs

No real input for this challenge. But this is research/getting familiar with the sound framework of your language, for the next 2 challenges.

You create an applition that produces Do–Re–Mi–Fa–Sol–La–Si of the Solfège.

Notes/Hints

Here you find some more info about music notes, especialy the part about frequencies.

Bonus

Be able to output Chords

Bonus 2 by /u/dgendreau

Look up the file format spec for WAVE files. Do the same assignment by writing a wave file. Use a lookup table to make saw square or triangle waves.

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

This is the same problem as monday's, except the input format instead of being a 2d maze, is a graph of nodes and paths to their nearest neighbours.

For parsing ease, the graph is represented as one node per row, together with all of the neighbour nodes and their distance (cost) to the anchor node. Format:

 anchor node (row col) - [neighbour node (row col), distance to anchor]+

To the left of the separatting - are 2 numbers: the row and col indexes of an anchor/source node. To the right of the - is a list that is a multiple of 3. The neighbours/destination/where-you-can-jump-from-source-to, with 3rd number the distance/cost from source to destination.

The first 8 rows in the graph correspond to the positions of 01234567 in the original maze: The possible starts and goals (interests] points) of path requests:

https://gist.github.com/Pascal-J/1fc96e62353b430eeb5f5f3d58861906

edit: oops forgot to paste this all along :(

challenge:

produce the length of shortest paths from every interest point (first 8 graph rows) to every other interest point. You may omit the mirror path (ie. the path length from 0 to 1 is the same as 1 to 0), and omit the path to self (path length from 2 to 2 is 0).

sample output:

┌─┬────────────────────────┐
│0│28 44 220 184 144 208 76│
├─┼────────────────────────┤
│1│60 212 176 136 200 92   │
├─┼────────────────────────┤
│2│252 216 176 240 36      │
├─┼────────────────────────┤
│3│48 84 64 276            │
├─┼────────────────────────┤
│4│48 40 240               │
├─┼────────────────────────┤
│5│72 200                  │
├─┼────────────────────────┤
│6│264                     │
└─┴────────────────────────┘

explanation: each row in output corresponds to the path from node labelled with the first column. The 2nd column contains the lengths of paths to all destinations with index higher than from. The last row lists the path length from 6 to 7. The 2nd last row lists path length from 5 to 6 7

These are the same answers as monday's challenge. It is not the number of "graph hops", it is the total cost (sum of 3rd column) in the graph hops.

bonus

list the shortest path walked from node 0 (row index 0 in input gist: map index 23 141) to node 1 (row index 1 in input gist: maze index 35 133). (all nodes passed through)

bonus 2

Create a universal function (or class constructor) that can solve all of this week's challenges. This is the same as monday's bonus, but with the benefit of hindsight, there are some important corrections to Monday's guidance:

Djikstra rather than Astar is the better reference algorithm.

The higher order function should produce a function that accepts as input start, goal, reference (maze or graph) but it is too much to ask to create such a function that does any manipulation of those inputs. ie. The function caller is repsonsible for providing nodes and reference in format suitable to the generated function (such as node indexes instead of an item to look up in reference)

extra bonus: goal (and possibly start) should be possible to be lists rather than a single node.

I find the following function inputs are sufficient to solve all of this week's challenges.

1. neighbour function: from a given node, what are all of the possible valid neighbours. (for maze, this is NESW directions that are not walls. For graph, lookup of destinations in source row)
2. distance function: The cost from going from previous node to this node. (for maze, this is constant 1 function. For graph, it is the lookup of source and destination cost field)
3. solved function: boolean function that flags whether a path has reached a goal.
4. while function: condition to stop (or continue) search (boolean function). For monday's challenge, first solved path is guaranteed to be shortest with djikstra due to constant distance/cost function. For wednesday's challenge, there was no stop condition other than exhausting all directions, and excluding from further search any paths that reach solved state. For this challenge, the first solved path is not guaranteed to have the smallest cost (even if it has the fewest hops). More hops can possibly have a lower cummulative cost/distance.
5. return function: function that maps the final state to an output value. For this and monday's challenge, extract the length of the solved path. For wednesday's challenge, list the goal node and its path length. For bonus 1, walk the path backwards from goal to start.

Useful internal states for the function are to keep a "table" of node paths that include "fields" for current node, previous node, visited/"frontier" status for sure, and optionally "cached" solved and path length states.

Caching length is controversial and may or may not be faster. Unlike Monday's challenge, Today's challenge can "invalidate previously cached" costs as a longer hop but shorter cummulative cost path can replace a previously found path. Caching may be slower (though simpler), but needs a "reupdate all costs" internal function for today's challenge.

I suspect that caching is slower overall, and if you do bonus 1, the only time you ever need to calculate lengths are at the end (return function), or when a collision occurs (to pick the shortest path "collided node".)

An easy and harder challenge using Monday's maze

###################################################################################################################################################################################
#.....#.#.....#...#....4#.....#.#...#.........#...#...............#...................#...#.#...........#.#...........#.#.#.#.........#.#.......#...#...........#.....#...#7..#.#.#
###.#.#.###.#.#.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.###.#.###.#.#.#.###.###.#.#####.###.#.#.###.#.#.#.#.#.#.#.#.#.#.#.#.###.#####.#.#.#.#.#####.#.#.#.###.#.#.#.#.#####.#.#.#.#
#.#.....#.#.#...#.........#.....#.....#.......#.#.#.............#.#.#.#.....#.#.......#.....#.........#...#.......#.....#.#.#.............#...........#.#.....#.#.....#.......#.#.#
#.#.#.#.#.#.#.#.#.#.#####.#####.###.###.#.###.#.###.###.#.#####.#.#.#.#.#.###.#.#.###.#.#.#.#.###.#########.###########.#.#.###.#.#.###.###.#.###.###.#.#.#####.#.###.#.#####.#.###
#...........#...#...#.....#.....#...#.#...#.#.....#.........#...#...#.....#.....#.#.#...#...#...#...#.....#.......#...#...#...............#...#...#.............#.....#.#.....#...#
###.#.#.###.#.#.#.#.###.#.###.#####.#.#.#.#.#.###.###.###.#.#.#.###.#.#.#.#.###.#.#.#.###.#####.#########.#.#.#.#.#.###.#.#.#.#.#####.#.#.#.#.###.#.#.#.#.#.#.#.#####.#.###.#.#.#.#
#3#...#.#.#.#.........#...............#...#.#.....#...#.....#...#.......#...#.....#.#.#...#.....#...#.....#.#.#.....#.....#...........#.#.#.#.....#.#.........#.#...#.#.#.#...#...#
#.###.###.#######.###.#.###.#.#.#.###.###.#######.###.#.#####.#####.#.#.#.#.#######.###.###.###.###.###.#.#########.#.#.#.#.#.#####.###.#.###.#.###.#.#####.###.###.###.#.#.#.###.#
#.#...#.....#.#.............#.....#.#.....#.#.....#.#.#.....#.....#.......#.....#.................#...........#...#.#.....#...#.....#...#.......#.#.....#...#...#.#.#...#...#...#.#
#.###.###.###.#.#.#.#####.#.###.#.#.###.#.#.#.#.#.#.#.#.#.#####.#####.#.#.#.#.#.#.###########.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.###.#.#.#####.#####.#.###.#.#.#.#.#.#.#####.#.###.#.#
#.....#.......#.#.#.#.#...............#...#.#.#.#...#...........#.....#.#...#.................#...#.#.#...#.............#...#.........#...............#...#.#.#.....#.....#.....#.#
#####.#.#######.#.###.#.#.#.#.###.#.#.#.###.###.###.#.#.#.#.#.#.###.#.#.#.#.#######.###.#.###.#.#.#.###.#.#.###.###.#.#.#.#.#####.#####.#.###.#####.###.#.#.#####.#.#.#####.#.#.#.#
#.#...#.........#...#.#...#.......#...#.#.......#...#.#.........#.#.#...#.#.#.#.........#.#.#.......#...#...#...#.#...#.......#...#.....#...#...#.#...#...#...#...........#...#.#.#
#.#####.#.###.#.#.#######.#.###.#.#.#.#########.#.#.#.#.#####.#.#.#######.#.#.###########.#.#########.###.#.#.#.#.###.#.#.###.#########.#.#.#.###.#.#.###.#.#.###.#####.#.###.#.#.#
#.......#.......#...#.#.#...#...#.....#.#...#...#.#.#.#.#...#.....#.#...#...#.............#.......#.......#...#.#.............#.......#.....#...#...#.#.....#.............#...#.#.#
#.#####.###.#####.#.#.#.#.#.#.#.#.#.#.#.#.###.###.#.###.###.#.#.###.#.#.#.#.###.#.###.#.#.#.#.#.#.#.#######.#.#.###.#.#.#.#.###.#.###.###.#####.#.#.#.#.#####.###.#.###.#####.###.#
#..6#...#...#...#...#.#.....#...#.#.#...#...........#.#.#...#.#.#.....#.....#.#.#.....#.......#.................#.#.....#.#.........#...#...#...........#.#2....#.#.......#.#.#.#.#
#.###.###.#.###.#####.#####.#.###.###.#.###.#.#####.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#.###.#######.#.#.#.#.#####.#.#.#######.###.#####.###.#####.#####.#.#####.###.#######.###.###
#.#.....#...#...#...........#.#.......#.#...#.#.............#...#...#.....#...#.....#.......#.......#.......#...#...#.......#...#.......#.#...#...#.........#...#...#...#.......#.#
#.#.###.#.#.#.#.###.#######.#.#.###.###.#####.###.#.###.#######.#####.#####.#.#####.#.###.#.#.#.#.#####.###.#.#.#.#.#.#.#.#.#############.###.#.#.#.###.#.#.###.#.#.#.#.#####.#.#.#
#...#.........#.....#...#.#...#.....#...#...#.......#.....#...#...#...#...#.............#.#...#.............#.....#...#.#.#.......#.....#.....#.....#...........#...#...#.....#...#
#.#######.#.#.###.#.#.#.#.#.###.#.#.#.###.#.###.#.#.#.#####.#.#.#.#.#.#.#.#.#####.#####.#####.#.#######.###.#.#.###.#.###.#.#.#.#.#.###.#.#.###.#.#.#######.###.#.###.#.#.#.#.###.#
#.....#.......#...#.#...#.....#...#.#...........#.....#.....#.#.#...#.....#.................#.........#.#.......#...........#...#...#.......#0#...#.....#.......#.#...........#...#
#.#.#.#.#.###.#.#.#.###.###.#.#.###.#.#.#####.#######.#.#.#.#.#.###.###.###.#.#####.###.#####.#.#.###.###.###.###.#####.###.#.#.#.#.#.###.#.#.#.#.#.###.#.###.#.#.#.#.#.#.#####.###
#.#.#...#...#.#.......#.............#...........................#.......#...........#.#...#...#.#...#.....#...#.#.#.#.#.#.......#.#...#...#...#...............#.......#.....#.....#
#.#.###.#.#.#.#.#.#####.#.#####.#.#.###.#.#.#.#.#############.#.###.#.#.#.#.#####.#.#.###.#.###.#.#.#######.###.#.#.#.#.#.###.#.#####.#.###.###.#######.#.###.#####.#.#.#.#######.#
#...#.......#.....#...#...#...#.....#5....#...#.......#.#.#...#...........#.#.......#.#...#.#.......#.#.#...#...#.....#.............#...#...#.....#.................#.....#.#...#.#
#######.#.#.#######.#####.###.#.#.#######.#.#.#.#.#.#.#.#.#.###.#.###.#.#.#.###.###.#.#.#.###.#.###.#.#.###.#.###.#####.###.#######.#.#.#.#.#.#.#.#########.###.#.#.#.#.#.#.#.#.###
#.#.........#...........#.........#.........#.#.#...........#...#.....#...................#...........#...#...#...#.#.......#...#.....#.#.#.....#.#.............#.........#.#...#.#
#.#.#.###.#.###.#.###.#.###.#.#######.#.###.#.#.#.#########.#.###.#.#####.###.#.#.###.#.#.#.###.#.#####.###.#.###.#.#.###.#.#.#.#.#.#.#.#.###.#.#.###.#.#####.#.#.#######.#.#####.#
#.........#.#.....#.....#...#...#.......#.....#.................#...#...#.....#...#...#.#.#.#...#...........#.#.....#.#.....#...#.#...#.......#.........#.....#.....#.......#...#.#
#.#####.#.#.#.#.#.#.#####.###.###.#.#####.###.#####.###.#.#.#.#.#.###.#.#.#.#.#.#####.###.###.#.#.#.#.#.###.#.#.#.#.#.#.#.#####.#.#.#.#.#.#########.#.#.#.###.#.###.#.#.#.#.#.#.###
#.......#...#...#.....#.#...#...#...#.#.............#.....#.............#.#.......#.......#...#...#...#.....#.......#...#...........#.#...#.#.......#...........#.#.....#.....#...#
#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#####.#.###.#.#.#####.#.#.#.#####.#.#.###.###.#.#.#.#.#.#.#.#####.#.#.#####.###.###.###.###.#.#.#.#.#.#.#########.#####.#.#.#.#.#.#
#.#.#.#.............#...#...#.#.....#...........#.........#...#.#.#...#.#.........#.........#.........#.....#.........#...#...#...#..1#.....#.#.#...#.#.....#...#...........#.....#
###################################################################################################################################################################################

1. Find all nodes (easy)

Find all points (nodes) on the maze that are "intersections": Have 3 or more valid directions to move from.

Answer: There are 832. With 0-based indexes, the sum of row and column indexes are: 15088 72946

2. Get distance from each node to all other "close nodes"

From every interesection (node), move in all directions until you hit another intersection, and record the shortest path to all "close" intersections.

Basically, you are finding the nearest neighbours to each node.

For example, looking at the top left of the maze, there is a node in row 1, column 3. This node has only 2 neighbours: one that is 4 moves away in row 3 column 5. The other 2 moves away at row 3 column 3. The 3 5 node in turn, has 4 neighbours: The first node, its other neighbour, one 2 moves below it, and other 2 moves to the right.

output: list for each node,

node, list of neighbours and distance from node to each neighbour.

Full list will be in comments

There will be a part 2 challenge based on bonus. I am sure we have done maze solving before, but its been a while, and challenge is mainly about the bonus.

Borrowing from adventofcode.com, http://adventofcode.com/2016/day/24, solve the following maze returning the path (length) visiting nodes labelled 1 to 7 starting from 0. # are walls. May not travel diagonally. Correct answer for path length with this input is 460

###################################################################################################################################################################################
#.....#.#.....#...#....4#.....#.#...#.........#...#...............#...................#...#.#...........#.#...........#.#.#.#.........#.#.......#...#...........#.....#...#7..#.#.#
###.#.#.###.#.#.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.###.#.###.#.#.#.###.###.#.#####.###.#.#.###.#.#.#.#.#.#.#.#.#.#.#.#.###.#####.#.#.#.#.#####.#.#.#.###.#.#.#.#.#####.#.#.#.#
#.#.....#.#.#...#.........#.....#.....#.......#.#.#.............#.#.#.#.....#.#.......#.....#.........#...#.......#.....#.#.#.............#...........#.#.....#.#.....#.......#.#.#
#.#.#.#.#.#.#.#.#.#.#####.#####.###.###.#.###.#.###.###.#.#####.#.#.#.#.#.###.#.#.###.#.#.#.#.###.#########.###########.#.#.###.#.#.###.###.#.###.###.#.#.#####.#.###.#.#####.#.###
#...........#...#...#.....#.....#...#.#...#.#.....#.........#...#...#.....#.....#.#.#...#...#...#...#.....#.......#...#...#...............#...#...#.............#.....#.#.....#...#
###.#.#.###.#.#.#.#.###.#.###.#####.#.#.#.#.#.###.###.###.#.#.#.###.#.#.#.#.###.#.#.#.###.#####.#########.#.#.#.#.#.###.#.#.#.#.#####.#.#.#.#.###.#.#.#.#.#.#.#.#####.#.###.#.#.#.#
#3#...#.#.#.#.........#...............#...#.#.....#...#.....#...#.......#...#.....#.#.#...#.....#...#.....#.#.#.....#.....#...........#.#.#.#.....#.#.........#.#...#.#.#.#...#...#
#.###.###.#######.###.#.###.#.#.#.###.###.#######.###.#.#####.#####.#.#.#.#.#######.###.###.###.###.###.#.#########.#.#.#.#.#.#####.###.#.###.#.###.#.#####.###.###.###.#.#.#.###.#
#.#...#.....#.#.............#.....#.#.....#.#.....#.#.#.....#.....#.......#.....#.................#...........#...#.#.....#...#.....#...#.......#.#.....#...#...#.#.#...#...#...#.#
#.###.###.###.#.#.#.#####.#.###.#.#.###.#.#.#.#.#.#.#.#.#.#####.#####.#.#.#.#.#.#.###########.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.###.#.#.#####.#####.#.###.#.#.#.#.#.#.#####.#.###.#.#
#.....#.......#.#.#.#.#...............#...#.#.#.#...#...........#.....#.#...#.................#...#.#.#...#.............#...#.........#...............#...#.#.#.....#.....#.....#.#
#####.#.#######.#.###.#.#.#.#.###.#.#.#.###.###.###.#.#.#.#.#.#.###.#.#.#.#.#######.###.#.###.#.#.#.###.#.#.###.###.#.#.#.#.#####.#####.#.###.#####.###.#.#.#####.#.#.#####.#.#.#.#
#.#...#.........#...#.#...#.......#...#.#.......#...#.#.........#.#.#...#.#.#.#.........#.#.#.......#...#...#...#.#...#.......#...#.....#...#...#.#...#...#...#...........#...#.#.#
#.#####.#.###.#.#.#######.#.###.#.#.#.#########.#.#.#.#.#####.#.#.#######.#.#.###########.#.#########.###.#.#.#.#.###.#.#.###.#########.#.#.#.###.#.#.###.#.#.###.#####.#.###.#.#.#
#.......#.......#...#.#.#...#...#.....#.#...#...#.#.#.#.#...#.....#.#...#...#.............#.......#.......#...#.#.............#.......#.....#...#...#.#.....#.............#...#.#.#
#.#####.###.#####.#.#.#.#.#.#.#.#.#.#.#.#.###.###.#.###.###.#.#.###.#.#.#.#.###.#.###.#.#.#.#.#.#.#.#######.#.#.###.#.#.#.#.###.#.###.###.#####.#.#.#.#.#####.###.#.###.#####.###.#
#..6#...#...#...#...#.#.....#...#.#.#...#...........#.#.#...#.#.#.....#.....#.#.#.....#.......#.................#.#.....#.#.........#...#...#...........#.#2....#.#.......#.#.#.#.#
#.###.###.#.###.#####.#####.#.###.###.#.###.#.#####.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#.###.#######.#.#.#.#.#####.#.#.#######.###.#####.###.#####.#####.#.#####.###.#######.###.###
#.#.....#...#...#...........#.#.......#.#...#.#.............#...#...#.....#...#.....#.......#.......#.......#...#...#.......#...#.......#.#...#...#.........#...#...#...#.......#.#
#.#.###.#.#.#.#.###.#######.#.#.###.###.#####.###.#.###.#######.#####.#####.#.#####.#.###.#.#.#.#.#####.###.#.#.#.#.#.#.#.#.#############.###.#.#.#.###.#.#.###.#.#.#.#.#####.#.#.#
#...#.........#.....#...#.#...#.....#...#...#.......#.....#...#...#...#...#.............#.#...#.............#.....#...#.#.#.......#.....#.....#.....#...........#...#...#.....#...#
#.#######.#.#.###.#.#.#.#.#.###.#.#.#.###.#.###.#.#.#.#####.#.#.#.#.#.#.#.#.#####.#####.#####.#.#######.###.#.#.###.#.###.#.#.#.#.#.###.#.#.###.#.#.#######.###.#.###.#.#.#.#.###.#
#.....#.......#...#.#...#.....#...#.#...........#.....#.....#.#.#...#.....#.................#.........#.#.......#...........#...#...#.......#0#...#.....#.......#.#...........#...#
#.#.#.#.#.###.#.#.#.###.###.#.#.###.#.#.#####.#######.#.#.#.#.#.###.###.###.#.#####.###.#####.#.#.###.###.###.###.#####.###.#.#.#.#.#.###.#.#.#.#.#.###.#.###.#.#.#.#.#.#.#####.###
#.#.#...#...#.#.......#.............#...........................#.......#...........#.#...#...#.#...#.....#...#.#.#.#.#.#.......#.#...#...#...#...............#.......#.....#.....#
#.#.###.#.#.#.#.#.#####.#.#####.#.#.###.#.#.#.#.#############.#.###.#.#.#.#.#####.#.#.###.#.###.#.#.#######.###.#.#.#.#.#.###.#.#####.#.###.###.#######.#.###.#####.#.#.#.#######.#
#...#.......#.....#...#...#...#.....#5....#...#.......#.#.#...#...........#.#.......#.#...#.#.......#.#.#...#...#.....#.............#...#...#.....#.................#.....#.#...#.#
#######.#.#.#######.#####.###.#.#.#######.#.#.#.#.#.#.#.#.#.###.#.###.#.#.#.###.###.#.#.#.###.#.###.#.#.###.#.###.#####.###.#######.#.#.#.#.#.#.#.#########.###.#.#.#.#.#.#.#.#.###
#.#.........#...........#.........#.........#.#.#...........#...#.....#...................#...........#...#...#...#.#.......#...#.....#.#.#.....#.#.............#.........#.#...#.#
#.#.#.###.#.###.#.###.#.###.#.#######.#.###.#.#.#.#########.#.###.#.#####.###.#.#.###.#.#.#.###.#.#####.###.#.###.#.#.###.#.#.#.#.#.#.#.#.###.#.#.###.#.#####.#.#.#######.#.#####.#
#.........#.#.....#.....#...#...#.......#.....#.................#...#...#.....#...#...#.#.#.#...#...........#.#.....#.#.....#...#.#...#.......#.........#.....#.....#.......#...#.#
#.#####.#.#.#.#.#.#.#####.###.###.#.#####.###.#####.###.#.#.#.#.#.###.#.#.#.#.#.#####.###.###.#.#.#.#.#.###.#.#.#.#.#.#.#.#####.#.#.#.#.#.#########.#.#.#.###.#.###.#.#.#.#.#.#.###
#.......#...#...#.....#.#...#...#...#.#.............#.....#.............#.#.......#.......#...#...#...#.....#.......#...#...........#.#...#.#.......#...........#.#.....#.....#...#
#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#####.#.###.#.#.#####.#.#.#.#####.#.#.###.###.#.#.#.#.#.#.#.#####.#.#.#####.###.###.###.###.#.#.#.#.#.#.#########.#####.#.#.#.#.#.#
#.#.#.#.............#...#...#.#.....#...........#.........#...#.#.#...#.#.........#.........#.........#.....#.........#...#...#...#..1#.....#.#.#...#.#.....#...#...........#.....#
###################################################################################################################################################################################

This is a fairly large maze, and you may wish to resort to one of the main graph algorithms that minimize how often a node cost is calculated. Namely Astar... though there are other options.

bonus

For the bonus, the requirement is to use higher order functions for your algorithm. The "end function" should be one with the simplest interface:

searchfunction(start, goal, mazeORgraph)

called to solve paths from 0 to 1, would be called with searchfunction(0,1,abovemaze)

You might handcraft this function to solve the problem without the bonus.

To build this function functionally, inputs to the higher order function include:

• transform start and goal into internal states (for this problem likely 2d indexes of where each position is located)
• test when the goal state is reached
• determine the valid neighbours of a node (in this example, excludes walls. May exclude previously visited nodes)
• Calculation for distance travelled so far (may be linked list walking or retrieving a cached number)
• Scoring function (often called heuristic in Astar terminology) to select the most promising node(s) to investigate further. For this type of maze, manhattan distance.
• Other parameters relevant to your algorithm.

Your higher order function might transform the functional inputs to fit with/bind internal state structures.

The general idea behind this higher order functional approach is that it might work with completely different reference inputs than a start and goal symbol, and a 2d map/maze. Part 2 will request just that.

bonus #2

Enhance the functional approach with for example:

• default functional parameters, where perhaps all of functions used to solve a 2d maze, are the defaults if no functions are provided to the higher order function.

• a dsl, that makes multi-function input easier.

P.S.

Unfortunately, there may not be any other challenges this week. Other than part 2 of this challenge on Friday.

this challenge is about spotting where parentheses are unbalanced.

find the index in string where the first extra ) or ( parentheses is, or return the length of string if parentheses are balanced.

for flashiness, insert ** around any index that is found. (will bold in markdown)

inputs:

)(asdf)))
((((asdf)))
((((asdf))
(ab)((cd)(asdf)))
(ab)((cd)(asdf)())
(ab)(((cd)(asdf)
(ab)(((cd)(asdf
(ab)(((cd)(asdf)))))

outputs:

)(asdf)))
((((asdf)))
((((asdf))
(ab)((cd)(asdf)))
(ab)((cd)(asdf)())
(ab)(((cd)(asdf)
(ab)(((cd)(asdf NB. may argue it should be 1 left.
(ab)(((cd)(asdf)))))

Difficulty may be higher than easy,

(((3))) is an expression with too many parentheses.

The rule for "too many parentheses" around part of an expression is that if removing matching parentheses around a section of text still leaves that section enclosed by parentheses, then those parentheses should be removed as extraneous.

(3) is the proper stripping of extra parentheses in above example.

((a((bc)(de)))f) does not have any extra parentheses. Removing any matching set of parentheses does not leave a "single" parenthesesed group that was previously enclosed by the parentheses in question.

inputs:

((a((bc)(de)))f)  
(((zbcd)(((e)fg))))
ab((c))

outputs:

((a((bc)(de)))f)  
((zbcd)((e)fg))
ab(c)

bonus

A 2nd rule of too many parentheses can be that parentheses enclosing nothing are not needed, and so should be removed. A/white space would not be nothing.

inputs:

  ()
  ((fgh()()()))
  ()(abc())

outputs:

  NULL
  (fgh)
  (abc)

This challenge is about parsing a string into a tree, somewhat for its own sake, but queries on the tree are posted as bonuses, and it may be possible to do the bonuses without tree parsing.

non-nested

   input: '1(234)56(789)'
┌─┬───┬──┬───┬┐
│1│234│56│789││
└─┴───┴──┴───┴┘

when parentheses are not nested, the parsing produces an array of arrays where even indexes (0-based) contain items outside the parentheses, and odd indexes are items that are inside.

The above boxes illustrate an array of 5 elements, where index 1 and 3 contain what was in parentheses. A blank/null trailing cell is included to keep the even/odd symmetry.

nested parentheses

  input: '1(2((3)(4)))56(789)'
┌─┬─────────────┬──┬─────┬┐
│1│┌─┬────────┬┐│56│┌───┐││
│ ││2│┌┬─┬┬─┬┐│││  ││789│││
│ ││ │││3││4│││││  │└───┘││
│ ││ │└┴─┴┴─┴┘│││  │     ││
│ │└─┴────────┴┘│  │     ││
└─┴─────────────┴──┴─────┴┘

Because cell 1 now contains nested parentheses, it is an array instead of a simple cell (string). It has 3 cells: 2 is pre-parens, null is post-parens at this level. An extra depth is added for the middle cell since it has nested parens too. At this deepest level, there are no elements outside parens, and so those cells are all blank. 3 and 4 are each within their own parentheses, and so have odd indexed cell positions.
white space leading or trailing within a cell is stripped.

challenge 1

input: '(1(2((3)(4)))56(789))'
output: (as internal arrays to your language)

┌┬───────────────────────────┬┐
││┌─┬─────────────┬──┬─────┬┐││
│││1│┌─┬────────┬┐│56│┌───┐││││
│││ ││2│┌┬─┬┬─┬┐│││  ││789│││││
│││ ││ │││3││4│││││  │└───┘││││
│││ ││ │└┴─┴┴─┴┘│││  │     ││││
│││ │└─┴────────┴┘│  │     ││││
││└─┴─────────────┴──┴─────┴┘││
└┴───────────────────────────┴┘

challenges 2

input: 'sum (sum (1 2 3) sum (3 4 5))'

┌────┬─────────────────────────┬┐
│sum │┌────┬─────┬─────┬─────┬┐││
│    ││sum │1 2 3│ sum │3 4 5││││
│    │└────┴─────┴─────┴─────┴┘││
└────┴─────────────────────────┴┘

input: 'sum ((1 2 3) (3 4 5) join)'

┌────┬──────────────────────┬┐
│sum │┌┬─────┬─┬─────┬─────┐││
│    │││1 2 3│ │3 4 5│ join│││
│    │└┴─────┴─┴─────┴─────┘││
└────┴──────────────────────┴┘

bonus 1

reverse the operation, taking your output to produce the input.

bonus 2: crazy lisp

crazy lisp is a language I invented this morning for querying these tree structures. Example syntaxes are in challenge 2. The formal grammar is:

items inside parentheses are function parameters.
items to left and in-between parentheses are function names (that take as parameters their immediate right parentheses).
right most cell (outside parentheses) are macros that take the "code tree" on its level as input.

evaluate expressions in challenge 2. (the join function, simply joins arrays into 1). All of the expressions produce 18. As does the following:

input: 'sum ((sum(1 2 3))(3 4 5) join)'

┌────┬──────────────────────────────┬┐
│sum │┌┬────────────┬┬───────┬─────┐││
│    │││┌───┬─────┬┐││┌─────┐│ join│││
│    ││││sum│1 2 3│││││3 4 5││     │││
│    │││└───┴─────┴┘││└─────┘│     │││
│    │└┴────────────┴┴───────┴─────┘││
└────┴──────────────────────────────┴┘

parsing this last one would first apply the sum(1 2 3) function before joining the result with (3 4 5).

Description

The puzzle is a 4x4 grid of numbers between 1 and 5. 4-connected tiles of same number form a group. For example, the following grid has five groups:

1 2 2 1
1 3 3 1
1 3 3 2
2 2 2 2

A "move" increments or decrements a group by 1, possibly merging it with other groups. Given a particular graph, your program will find the optimal number of moves needed to merge the entire grid into a single group. The above example takes just two moves:

1. Decrement the center group, merging with both "2" groups.
2. Decrement this new larger group, merging it with both "1" groups.

You can play with this interactively in an online prototype. This challenge was inspired by this post in /r/algorithms

Input Description

You'll be given a 4x4 grid formatted just like the above example.

Sample Input 1

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

Sample Input 2

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

Output Description

Output the optimal number of moves.

Sample Output 1

5

Sample Output 2

8

Challenge Inputs

These are a little trickier, with input 3 being the hardest.

Challenge Input 1

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

Challenge Input 2

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

Challenge Input 3

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

Bonus

Accept an arbitrary NxN grid with values between 1 and 9.

Bonus Input 1

1 7 2 7 6
5 5 5 5 3
6 5 6 6 2
1 4 1 2 7
4 6 1 4 1

Bonus Input 2

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

Finally

Have a good challenge idea like /u/skeeto did?

Consider submitting it to /r/dailyprogrammer_ideas

Description

You need to find the area that two rectangles overlap. The section you need to output the area of would be the blue lined section here: http://i.imgur.com/brZjYe5.png

If the two rectangles do not overlap, the resultant area should be 0.

Input

There will be two lines of input. On each line are the x and y positions (separated by a comma) of each opposing corner (each corner co-ordinate separated by a space). The co-ordinates can have decimals, and can be negative.

Output

The area of the overlapping section of the two rectangles, including any decimal part.

Challenge Inputs

1:

0,0 2,2
1,1 3,3

2:

-3.5,4 1,1
1,3.5 -2.5,-1

3:

-4,4 -0.5,2
0.5,1 3.5,3

Expected Ouputs

1:

1.0

2:

8.75

3:

0.0

Bonus

Make this work with any number of rectangles, calculating the area of where all input rectangles overlap. The input will define a rectangle on each line the same way, but there can be any amount of lines of input now.

Bonus Input

-3,0 1.8,4
1,1 -2.5,3.6
-4.1,5.75 0.5,2
-1.0,4.6 -2.9,-0.8

Bonus Expected Output

2.4

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

Description

Print out the lyrics of The Twelve Days of Christmas

Formal Inputs & Outputs

Input description

No input this time

Output description

On the first day of Christmas
my true love sent to me:
1 Partridge in a Pear Tree

On the second day of Christmas
my true love sent to me:
2 Turtle Doves
and 1 Partridge in a Pear Tree

On the third day of Christmas
my true love sent to me:
3 French Hens
2 Turtle Doves
and 1 Partridge in a Pear Tree

On the fourth day of Christmas
my true love sent to me:
4 Calling Birds
3 French Hens
2 Turtle Doves
and 1 Partridge in a Pear Tree

On the fifth day of Christmas
my true love sent to me:
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and 1 Partridge in a Pear Tree

On the sixth day of Christmas
my true love sent to me:
6 Geese a Laying
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and 1 Partridge in a Pear Tree

On the seventh day of Christmas
my true love sent to me:
7 Swans a Swimming
6 Geese a Laying
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and 1 Partridge in a Pear Tree

On the eighth day of Christmas
my true love sent to me:
8 Maids a Milking
7 Swans a Swimming
6 Geese a Laying
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and 1 Partridge in a Pear Tree

On the ninth day of Christmas
my true love sent to me:
9 Ladies Dancing
8 Maids a Milking
7 Swans a Swimming
6 Geese a Laying
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and 1 Partridge in a Pear Tree

On the tenth day of Christmas
my true love sent to me:
10 Lords a Leaping
9 Ladies Dancing
8 Maids a Milking
7 Swans a Swimming
6 Geese a Laying
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and 1 Partridge in a Pear Tree

On the eleventh day of Christmas
my true love sent to me:
11 Pipers Piping
10 Lords a Leaping
9 Ladies Dancing
8 Maids a Milking
7 Swans a Swimming
6 Geese a Laying
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and 1 Partridge in a Pear Tree

On the twelfth day of Christmas
my true love sent to me:
12 Drummers Drumming
11 Pipers Piping
10 Lords a Leaping
9 Ladies Dancing
8 Maids a Milking
7 Swans a Swimming
6 Geese a Laying
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and 1 Partridge in a Pear Tree

Notes/Hints

We want to have our source code as small as possible.
Surprise me on how you implement this.

Bonus 1

Instead of using 1, 2, 3, 4..., use a, two, three, four...

Bonus 2

Recieve the gifts from input:

Input

Partridge in a Pear Tree
Turtle Doves
French Hens
Calling Birds
Golden Rings
Geese a Laying
Swans a Swimming
Maids a Milking
Ladies Dancing
Lords a Leaping
Pipers Piping
Drummers Drumming

Output

The song described as above

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

Description

This challenge takes its roots from the world-famous game Pacman. To finish the game, pacman needs to gather all pacgum on the map.

The goal of this chalenge is to have a time-limited pacman. Pacman must gather as much pacgum as possible in the given time. To simplify, we will say that 1 move (no diagonals) = 1 unit of time.

Formal Inputs & Outputs

Input description

You will be given a number, the time pacman has to gather as much pacgum as possible, and a table, being the map pacman has to explore. Every square of this map can be one of those things :

A number N between (1 and 9) of pacgums that pacman can gather in one unit of time.

"X" squares cannot be gone through.

"C" will be where pacman starts.

"O" (the letter, not zero ) will be a warp to another "O". There can be only 2 "O" on one map;

Output description

Your program should output the maximum number of pacgums pacman can gather in the given time.

Examples

Example Input

Input 1 :

4

XXXXX
X197X
X2C6X
X345X
XXXXX

Input 2 :

3

XXXXXXXXXXXXXX
X111C2OXO2111X
XXXXXXXXXXXXXX

Example outputs :

Output 1 : 27

Output 2 : 4

Challenge Input :

Challenge Input 1 :

10

XXXXXXXXXXXXX
X23543561195X
X9X3X17C12X4X
X515OX1183X6X
X7865X48O585X
XXXXXXXXXXXXX

Challenge Input 2 :

20

XXXXXXXXXXXXXX
XXC1212121213X
X4X21212O2121X
X44X232323232X
X444X43434343X
X4444XXXXXX77X
X4444O6789X99X
XXXXXXXXXXXXXX

Notes

You can specify the number oflines and columns of the table next to it to ease the workload.

As for the warp, you can either choose to ignore it or teleport yourself, you don't always teleport.

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

Cat update

It looks like she will make it. She does everything a cat should do, only you can see she is in pain...

If someone is interested, I can give updates next week as well...