What's going on?

Someone asked the moderators whether r/dailyprogrammer_ideas is still used. I can only speak for myself, but I'm the only one posting recently for what it's worth. But I know that other moderators care about different things than me.

The short answer is that I do read it for inspiration, but I rarely get ideas from there. The main reason is that I look for certain things in a challenge, and, partly due to my own laziness, it's hard to see how to work those ideas into what I consider a good challenge.

So what do I look for? It's different for Easy, Intermediate, and Hard, and also different if it's a standalone challenge, or a series of challenges that build on each other. Given the state of the subreddit, I'm currently focused on standalone Easy challenges, since Easy ones get by far the biggest response. So here's what I look for in a standalone Easy:

It should be expressed as a simple map from input to output (i.e. a function), dealing only with very simple data types (number, string, boolean, list). Anything like "build an app" or "parse this data set" or sound, graphics, web, etc., while interesting, is beyond the scope of Easy.

It should solve an interesting problem. Interesting can mean many things, such as a realistic problem that you might actually need to solve for a job or project, or some interesting mathematics you might see on Numberphile. But I try to avoid "exercises" where you have to solve artificial problems with no connection to any greater context. Here's a recent example where, IMHO, I failed this criterion and chose an uninteresting problem.

It should have multiple parts, and the easiest part should be very easy. If anyone posts that they don't even know how to get started, that's a failure on my part. But if it was just a very easy part, many people would get bored. So either the main challenge is very easy and there's an optional bonus, or there's a very easy warmup before the main challenge. Usually any problem can be adapted to be easier or harder, but sometimes it's more straightforward than others.

It should be fully explained. I would not post an Easy problem where the algorithm to solve it was unclear. Ideally it's clear enough that any non-coder could solve it by hand, and it's just a matter of converting that known algorithm into code. Any challenge can fit this criterion with enough explanation, but too much explanation makes the challenge unwieldy.

So that's it. I read through high-rated Easy challenges on r/dailyprogrammer_ideas and skip them for one of those reasons.

But I'm sure there's also a lack of imagination on my part. I'm sure that many ideas I skip could be made into what I'm looking for with a little work. If you have an Easy challenge you want posted, and you're willing to spend a couple hours working with me to get it ready, PM me the link and I'll take a look and tell you what I think it needs.

Description

Use either an Evolutionary or Genetic Algorithm to evolve a solution to the fitness functions provided!

Input description

The input string should be the target string you want to evolve the initial random solution into.

The target string (and therefore input) will be

'Hello, world!'

However, you want your program to initialize the process by randomly generating a string of the same length as the input. The only thing you want to use the input for is to determine the fitness of your function, so you don't want to just cheat by printing out the input string!

Output description The ideal output of the program will be the evolutions of the population until the program reaches 'Hello, world!' (if your algorithm works correctly). You want your algorithm to be able to turn the random string from the initial generation to the output phrase as quickly as possible!

Gen: 1  | Fitness: 219 | JAmYv'&L_Cov1
Gen: 2  | Fitness: 150 | Vlrrd:VnuBc
Gen: 4  | Fitness: 130 | JPmbj6ljThT
Gen: 5  | Fitness: 105 | :^mYv'&oj\jb(
Gen: 6  | Fitness: 100 | Ilrrf,(sluBc
Gen: 7  | Fitness: 68  | Iilsj6lrsgd
Gen: 9  | Fitness: 52  | Iildq-(slusc
Gen: 10 | Fitness: 41  | Iildq-(vnuob
Gen: 11 | Fitness: 38  | Iilmh'&wmsjb
Gen: 12 | Fitness: 33  | Iilmh'&wmunb!
Gen: 13 | Fitness: 27  | Iildq-wmsjd#
Gen: 14 | Fitness: 25  | Ihnlr,(wnunb!
Gen: 15 | Fitness: 22  | Iilmj-wnsjb!
Gen: 16 | Fitness: 21  | Iillq-&wmsjd#
Gen: 17 | Fitness: 16  | Iillq,wmsjd!
Gen: 19 | Fitness: 14  | Igllq,wmsjd!
Gen: 20 | Fitness: 12  | Igllq,wmsjd!
Gen: 22 | Fitness: 11  | Igllq,wnsld#
Gen: 23 | Fitness: 10  | Igllq,wmsld!
Gen: 24 | Fitness: 8   | Igllq,wnsld!
Gen: 27 | Fitness: 7   | Igllq,!wosld!
Gen: 30 | Fitness: 6   | Igllo,!wnsld!
Gen: 32 | Fitness: 5   | Hglln,!wosld!
Gen: 34 | Fitness: 4   | Igllo,world!
Gen: 36 | Fitness: 3   | Hgllo,world!
Gen: 37 | Fitness: 2   | Iello,!world!
Gen: 40 | Fitness: 1   | Hello,!world!
Gen: 77 | Fitness: 0   | Hello, world!
Elapsed time is 0.069605 seconds.

Notes/Hints

One of the hardest parts of making an evolutionary or genetic algorithm is deciding what a decent fitness function is, or the way we go about evaluating how good each individual (or potential solution) really is.

One possible fitness function is The Hamming Distance

Bonus

As a bonus make your algorithm able to accept any input string and still evaluate the function efficiently (the longer the string you input the lower your mutation rate you'll have to use, so consider using scaling mutation rates, but don't cheat and scale the rate of mutation with fitness instead scale it to size of the input string!)

Bonus EXTRA HARD MODE

Using the principles you learned from the hello world problem, write an algorithm to find the maximum of the much harder multivariable function:

f(x,y) = (e^{-x2 - y^2}+sqrt(5) sin² (x³ )+2 cos² (2x+3 y))/(1 + x² + y² )

where -3<=x<=3 and -3<=y<=3

or you can check out the function On Wolfram Here

My solution in Matlab can be found in my Github Repository

Hint: By representing the solutions (or genomes) in binary instead of cartesian (x,y) coordinates you will be able to perform the evolutionary and genetic operations on the genomes more easily!

Finally

Have a good challenge idea? Consider submitting it to /r/dailyprogrammer_ideas

There's a gold rush for each new post in /r/dailyprogrammer to be the first to solve the puzzle(s), or to be the first one in for a given language, or even just to be done before the next challenge arrives in 2 days' time. Those who aren't so worried about beating the crowd still face a tight turnaround, especially on [hard] problems. This is in keeping with most of our experience - we're all in competition with coworkers, other companies, markets, deadlines, etc., but it - like those things - rules out the other side, the more academic end of the equation.

I do realize how off it sounds to say that a place where strangers gather to write code to solve challenges just for the fun of it isn't academic - we're certainly in some top percentile :) - but it would be nice to show off and discuss solutions played at for longer periods of time, say, a week or two, or even a few months if something hooked our interest. I rarely come up with the best algorithm right away, and have to dabble in the domain space for a week or more before I see a smarter, more interesting solution. However, 2 weeks later, the forty-niners have moved on, and there's nowhere but a ghost town in which to post such interesting results.

Maybe I'm alone in this, but I'd like to see a weekly post - Saturdays, or some other low-volume day (it could even be posted automatically by a bot) - calling for any cool updates on things worked at for longer than the usual day or two. This would allow people to take an idea and run with it for a bit, knowing there'd be a place to share it when they had something cool. It would also keep alive past challenges, so not everything would be so disposable. The "make a little game" [hard] posts especially are ripe for this treatment. These posts would also be interesting, as they'd be aggregates of random, past postings, so you wouldn't know what you'd find posted to each, e.g. "I decided to turn 'Challenge #nnn [Hard] - Title' into a full game using FRP!" or "I realized that 'Challenge #nnn [Intermediate] - FooBar' was a subclass of x" or "I thought it would be cool to combine challenges #mmm and #nnn into a single, [surprisingly useful] utility."

Anyway, just a thought.

Description

There is a crisis unfolding in reddit. For many years, redditors have continued to evolve shitposting to new highs, but it seems progress has slowed in recent times. Your mission, should you choose to accept it, is to create a state of the art rektangular shitpost generator and bring shitposting into the 21st century.

Given a word, a width and a length, you must print a rektangle with the word of the given dimensions.

Formal Inputs & Outputs

Input description

The input is a string word, a width and a height

Output description

Quality rektangles. See examples. Any orientation of the rektangle is acceptable

Examples

• Input: "REKT", width=1, height=1

  Output:

   R E K T
   E     K
   K     E
   T K E R

• Input: "REKT", width=2, height=2

  Output:

    T K E R E K T
    K     E     K          
    E     K     E
    R E K T K E R
    E     K     E
    K     E     K
    T K E R E K T

Notes/Hints

None

Bonus

Many fun bonuses possible - the more ways you can squeeze REKT into different shapes, the better.

• Print rektangles rotated by 45 degrees.

• Print words in other shapes (? surprise me)

• Creatively colored output? Rainbow rektangles would be glorious.

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

Write a program that accepts a string, an integer, and optionally a second string. Return a string with total length given by the integer, left padded with the specified string. In the default case, padding should be done using spaces.

This should be helpful to the programming community at large and help avoid future problems.

Intermediate: Path to Philosophy

Clicking on the first link in the main text of a Wikipedia article not in parentheses, and then repeating the process for subsequent articles, usually eventually gets you to the Philosophy article. As of May 26, 2011, 94.52% of all articles in Wikipedia lead eventually to the article Philosophy. The rest lead to an article with no wikilinks or with links to pages that do not exist, or get stuck in loops. Here's a youtube video demonstrating this phenomenon.

Your goal is to write a program that will find the path from a given article to the Philosophy article by following the first link (not in parentheses) in the main text of the given article.

Formal Inputs & Outputs

Input Description:

The program should take in a string containing a valid title of a Wikipedia article.

Output Description

Your program must print out each article in the path from the given article to Philosophy.

Sample Inputs & Outputs

Input

Molecule

Output

Molecule 
Atom 
Matter 
Invariant mass 
Energy 
Kinetic energy 
Physics 
Natural philosophy 
Philosophy 

Challenge Input

Telephone

Solution to challenge input

Telephone
Telecommunication
Transmission (telecommunications)
Analog signal
Continuous function
Mathematics
Quantity
Property (philosophy)
Logic
Reason
Consciousness
Subjectivity
Subject (philosophy)
Philosophy

Just thought I let you all know about a great site for these kinds of programming challenges: Advent of Code This year's starts up on December 1st, but you can still look back at previous years.

Implement the weasel program, a simple genetic algorithm. The program should display its progress over time.

Description

According to Wikipedia, Roman numerals are:

The numeric system represented by Roman numerals originated in ancient Rome and remained the usual way of writing numbers throughout Europe well into the Late Middle Ages. Numbers in this system are represented by combinations of letters from the Latin alphabet. Roman numerals, as used today, are based on seven symbols.

Those seven symbols are the following:

Convert an integer to Roman numerals, or Roman numerals to an integer (depending on the input).

Formal Inputs & Outputs

Input description

A list of integers and Roman numerals, line by line.

Challenge input:

XLV
MMXV
3333
X
888
1776
1344
DVI
1998
444
CCCXXXIII
MMMCMXCIX
45
CDXLIV
1998
3999
CII

Output description

The converted Roman numerals or integers.

Challenge output

45
2015
MMMCCCXXXIII
10
DCCCLXXXVIII
MDCCLXXVI
MCCCXLIV
506
MCMXCVIII
CDXLIV
333
3999
XLV
444
MCMXCVIII
MMMCMXCIX
102

Notes/Hints

How can you tell the difference in a Roman numeral string between V and IV? or IV and I?

There are only a few different character combinations in Roman numerals, the max length is 2.

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

Who doesn't want to speak like doge? Wow. Such programming learned.

Anyway, I decided that I was way too lazy to type out a doge-ified Reddit comment, so I wrote a little script to do it for me. Here's some sample output:

                                                                                wow

such learned                                                                    very talked to

                                        many teach
        how play game?
   hash tag wow                                                 kolej hard

                                                               wow

[Finished in 0.0s]

Formal input would be comma-separated words, like so:

'such learned, many teach, very talked to, wow, how play game?, kolej hard, hash tag wow'

And output would be a randomized Doge-ified comment. I used Markdown, so each line begins with at least 4 spaces. Some lines can have 2 items, others will only have one. Spacing is semi-random.

For more challenge, you can have it try to doge-ify someone else's comment (or a bot!) without using pre-doged phrases.

If anyone's interested, I have a sample Ruby script I whipped up for this purpose. Enjoy!

                                          wow
                    how do?


                                                                       such not simple
                                                                         many idea
                                             wow
                      so program

      redit commenting
                                                                        hax

Just wanted to see if this subredddit and its parent are still considered active or if the cadence has changed?
It appears that there is now one challenge a month. Is that intentional or just a result of the activity?

Great subreddit and I really appreciate the wealth of challenges that have come up here.

I know this is against the rules, but like what happened to the Subreddit (dailyprogrammer), they haven't posted in like 15 days what is happening?

Description

I can mash up the words ONE and rags to get OraNgEs. Observe that I didn't change the order of letters in either word; I just interleaved them together.

Given words w1, w2, and target, determine whether you can mash the words w1 and w2 to make target.

Example Inputs & Outputs

merges("cool", "shed", "schooled") = True
merges("cia", "cad", "cicada") = True
merges("pet", "piet", "pipette") = False
merges("aababbabba", "abaaaaabaab",
 "aabaaabaabbaabbaabaab") = True

Bonus

Using an English dictionary file, what's the longest word merge in English you can find, scoring by the minimum length of the two merged words? Exclude examples where you just concatenate the words, e.g. "fire"+"truck"="firetruck". You will need an efficient algorithm, because triply or even doubly looping over the entire English language would take a very long time.

Finally

Have a good challenge idea? Consider submitting it to /r/dailyprogrammer_ideas.

Description

Make a calculator that lets the user add, subtract, multiply and divide integers. It should allow exponents too. The user can only enter integers and must expect the result to be integers.

The twist is that YOU, the programmer, can only let the program calculate expressions using addition. Only addition.

The user can enter 3*2 however you cannot calculate it using multiplication. For integers, multiplication is basically addition.

Basically, the programmer is not allowed to multiply, divide and subtract using the operations provided by a programming language. Only addition is directly accessible to the programmer.

Please note that

• You are not allowed to use any functions (other than user-defined functions) to work with exponents.

• You are not allowed to use any functions (other than user-defined functions) to work with exponents.

• You can use logical operators.

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

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

• No bitwise operations are allowed.

Input description

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

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

Output description

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

Challenge Inputs

3+5
9*3
9*-3                               
2-5
12/2
9^2 
2/7
124^0
1^1

Note that 9*-3 means 9*(-3). Since you are working with two numbers, there is no need for brackets.

Challenge Outputs

8 
27 
-27 
-3 
6
81
NON-INTEGRAL ANSWER
1
1

Bonus

Allow the user to enter expressions with multiple terms and evaluate them. Let the user use brackets. Again, remember, the only operation directly accessible to the programmer is addition.

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

Description

Your task is to from a string user input, to recreate that string in the style of the opening credits from the movie Birdman, in which the words are slowly revealed to the viewer by having all the letters appear in alphabetical order. You can see a demonstration of this from this clip here.

Formal Inputs & Outputs

Input description

The program should expect an alphanumerical string as an input.

Output description

The program should in total only output a single line, but the line should update gradually in an interval of your choosing.

For instance an input of "Aadvark" would produce the following. "Aa a " "Aad a " "Aad a k" "Aad ark" "Aadvark"

However each line would overwrite the previous line.

Notes/Hints

Watch the demonstration linked above if you want a visualisation of the idea taking place.

Bonus

Try and have the interval in which the new letters are displayed have random intervals, in order to emulate the opening credits more faithfully.

Finally

This is my first submission, I've tried my best to imitate other submissions but feedback is appreciated if I've done something unusual :)

I see lots of people posting C solutions in which they complain about how reading input from a file is most of the effort. In languages where it's not just a matter of stuff = map(int, read_stdin()), it can be annoying (and maybe even discouraging -- in C, reading input from a file without introducing bugs can actually be harder than an Easy problem!) to have to write the same boilerplate to read data from standard input each time and convert it from strings to numbers/tuples/whatever.

Maybe we should encourage hard-coding the test cases as an alternative to reading them from a file in places where that makes sense. It's necessary to enforce an exact input/output format when you're writing a problem for something like SPOJ, but it seems rather unnecessary to be so strict on /r/dailyprogrammer. I feel like it should be enough to just write a function that implements the relevant logic.

Of course, sometimes reading input from text files has its merits: it allows users to write their own test cases and share them with everyone else. Standardization is nice, so suggesting a format isn't necessarily a bad idea -- it just shouldn't be a requirement, I think.

What do you all think?

Description

In Brazil, vehicle's license plates are a set of three letters and four numbers (eg. ETR-7741). So whenever I'm stuck in the traffic jam, I keep my mind busy trying to build equations with plate's numbers.

For example: the above numbers 7741 can be solved with 7/7=sqrt(4)-1

As a hacker, I want to automate this puzzle :)

Rules are:

• Every one of the four digits must be used in the equation in the position they are presented.

• No other number can be added.

• Numbers CAN be concatenated to build two-digit numbers (or three digit).

• The equals sign (=) can be put in any position.

• Feel free to put parenthesis anywhere too.

• Try to keep it in the integers field (remember that it's originally a mental puzzle, so only ints here).

Allowed operations are:

• Addition (+)

• Substraction (-)

• Multiplication (*)

• Division (/)

• Exponentiation (⁾

• Square (²)

• Square root (√)

• Factorial (!)

(square is the only operation that can be used without taking a literal "2". Any other exp can only be used if both the base and exponent are present)

So, summing up:
Given 4 digits, print every possible equation using them.

Examples:

1123 => 1*1+2=3
2491 => 2=4-sqrt(9)+1
3327 => 3^3=27

Challenge input

7994
7697
8080
2222
0158

Extra

Allow inputs of any length

Description#

We offer you to catch circles with a rectangular lasso.

We have a list of circles of the plan, represented by triplets (x, y, r) of real ((x,y) is the center, r the radius) of positive radius.

Write a program which determines the vertices of the minimum rectangle with sides parallel to the axes and that surrounds completely all the circles.

Lasso

Input

Centers and radii of the circles will be given in a string separated by commas.

Example with 4 circles:

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

Output

The coordinates of the vertices of the rectangle will be given in the form:

[-3,-5],[6,-5],[6,3],[-3,3]

Bonus

Let v = (v1, v2) a direction, a vector that is not null.

Write a program which determines the vertices of the minimum rectangle which at least one of the sides is parallel to the direction of vector v and that surrounds completely all the circles.

Example

Input

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

And v=[1,1]

Output

[-1,-5.828427128],[6.621320348,1.792893220], [2.792893221,5.621320347],[-4.828427127,-2.000000001]

Lasso with direction

Notes/Hints

For the bonus:

If a vector u=(a,b) is 1-norm then the rotation matrix that rotate (1,0) to u is

[ a -b ]

[ b a ]

And the inverse matrix is:

[ a b ]

[ -b a ]

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

I often get stuck working on a dailyprog problem, and instead of going to learnprogramming and posting the whole challenge and my soution to ask for help, it would be nice to have the same group that did solve (or tried to solve) the problem look at my code and give helpful hints.

Also, it'll be just like the dailyprogrammer subreddit, where every post is necessarily about a particular problem and nothing else, no other problems, just to keep it clean. So we could even limit (just like dailyprogrammer) who can post (only mods). And then the rest of us can just add comments, so it'll look just like the dailyprogrammer page, except each post has only discussions etc.

Problem description

Fizz Buzz is a simple kids' game revolving around counting. The basic rules involve counting from 1 to 100, and replacing any multiples of 3 with the word "fizz", any multiples of 5 with the word "buzz", and any multiples of both with both words ("fizz buzz").

It is not only useful for teaching kids about division, but is also used as a litmus test for basic programming skills in job interviews. What they're usually looking for is some code like this (C99):

#include <stdio.h>

int main() {
  int mod3, mod5;
  for (int i=1; i<101; i++) {
    mod3 = i % 3;
    mod5 = i % 5;
    if (!mod3 && !mod5) printf("fizz buzz\n");
    else if (!mod3) printf("fizz\n");
    else if (!mod5) printf("buzz\n");
    else printf("%d\n", i);
  }
}

Resulting in output like this:

1
2
fizz
4
buzz
fizz
7
8
fizz
buzz
11
fizz
13
14
fizz buzz
16
[...]

That's simple, though. Today, let's look at a more interesting problem: reversing the Fizz Buzz process to find out what the divisors for a particular "fizz buzz" sequence (in this case, 3 and 5) were. Better, let's do it from an input that has no numbers; only words.

Input

The input starts by specifying two numbers:

• the number of different words; for example, if we are using the words "fizz", "buzz" and "qazz", it would be 3

• a number N >= 1

These inputs will be followed by a series of lines containing the Fizz Buzz words (no numbers) corresponding to playing Fizz Buzz from 1 to N (which was specified above).

Given the number of words, and the sample "play" of Fizz Buzz, your program must figure out the divisors corresponding to each word.

Output

The output must contain each word used, associated with a divisor that makes the sequence work.

Sample 1

Input

2 20
fizz
buzz
fizz
fizz
buzz
fizz
fizz buzz
fizz
buzz

The intended solution uses "fizz" and "buzz" as words, with 3 and 5 as the respective divisors. The pattern (ranging 1..20) with the numbers not excluded would have been: 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizz buzz, 16, 17, fizz, 19, buzz

Output

fizz 3
buzz 5

The program figured out that "fizz" must correspond to 3, and "buzz" must correspond to 5.

Sample 2

Input

3 30
red
red blue
red
yellow
red blue
red
red blue
red yellow
red blue
red
red blue
yellow
red
red blue
red
red blue yellow
red

Output

red 2
blue 4
yellow 7

Notes

You can find a script for generating inputs for this problem here:

https://github.com/fsufitch/dailyprogrammer/blob/master/ideas/reverse_fizzbuzz/fizzbuzz_inputgen.py

The popular video games Fallout 3 and Fallout: New Vegas have a computer "hacking" minigame where the player must correctly guess the correct password from a list of same-length words. Your challenge is to implement this game yourself.

The game operates similarly to the classic board game [Mastermind](http://en.wikipedia.org/wiki/Mastermind_(board_game)). The player has only 4 guesses and on each incorrect guess the computer will indicate how many letter positions are correct.

For example, if the password is MIND and the player guesses MEND, the game will indicate that 3 out of 4 positions are correct (M_ND). If the password is COMPUTE and the player guesses PLAYFUL, the game will report 0/7. While some of the letters match, they're in the wrong position.

Ask the player for a difficulty (very easy, easy, average, hard, very hard), then present the player with 5 to 15 words of the same length. The length can be 4 to 15 letters. More words and letters make for a harder puzzle. The player then has 4 guesses, and on each incorrect guess indicate the number of correct positions.

Here's an example game:

Difficulty (1-5)? 3
SCORPION
FLOGGING
CROPPERS
MIGRAINE
FOOTNOTE
REFINERY
VAULTING
VICARAGE
PROTRACT
DESCENTS
Guess (4 left)? migraine
0/8 correct
Guess (3 left)? protract
2/8 correct
Guess (2 left)? croppers
8/8 correct
You win!

You can draw words from our favorite dictionary file: enable1.txt. Your program should completely ignore case when making the position checks.

There may be ways to increase the difficulty of the game, perhaps even making it impossible to guarantee a solution, based on your particular selection of words. For example, your program could words that have little letter position overlap so that guesses reveal as little information to the player as possible.

Possible followup challenge

Write a program that solves the hacking game in as few guesses as possible. Use it to beat the game you wrote in the previous challenge.

As an example of being optimal, when making a guess, choose a word that's likely to give the most information if it's wrong.

this one's been on my mind since i read about it in Bollobas' book on graph theory, and also when helping my wife build acceptable rooming assignments for her class trips. turns out it's an interesting math problem!

Title Stable Marriage Problem

Difficulty Hard

Description

For a set of men {A,B,...,Z} and a set of women {a,b,...,z} they have a preference table - A would prefer to marry b, but will be satisfied to marry c; c would prefer to marry B, will be OK to marry C, etc. Matches are considered unstable if there exists a pair who likes each other more than their spouses. The challenge is then to construct a stable set of marriages given the preferences.

The Gale-Shapely Theorem tells us that a stable marriage is always possible, and found in O( n^2 ) time.

Formal Input Description

You'll be given the individual (uppercase for men, lowercase for women) identifier first, then the identifiers for their preferences for each member of the set of men (uppercase letters) and women (given by lowercase letters).

Formal Output Description

You'll emit the list of pairs that satisfy the constraints.

Sample Input

A, b, c, a
B, b, a, c
C, c, a, b
a, C, B, A
b, A, C, B
c, A, C, B

Sample Output

(A; b)
(B; c)
(C; a)

Challenge Input

A, b, d, g, h, c, j, a, f, i, e
B, f, b, i, g, a, j, h, e, c, d
C, b, i, j, g, h, d, e, f, c, a
D, f, a, e, i, c, j, b, g, d, h
E, f, d, a, e, i, b, c, g, j, h
F, d, f, a, c, j, e, i, b, g, h
G, e, g, c, b, f, d, a, i, j, h
H, f, i, b, c, e, a, h, g, d, j
I, i, a, j, f, c, e, b, g, h, d
J, h, f, c, e, b, a, j, g, d, i
a, J, C, E, I, B, F, D, G, A, H
b, I, H, J, C, D, A, E, B, G, F
c, C, B, I, F, H, A, D, J, G, E
d, F, G, J, D, C, E, I, H, B, A
e, D, G, J, C, A, H, I, E, B, F
f, E, H, C, J, B, F, D, A, G, I
g, J, F, G, E, I, A, H, B, D, C
h, E, C, B, H, I, A, G, D, F, J
i, J, A, F, G, E, D, H, B, I, C
j, E, A, B, C, J, I, G, D, H, F

Challenge Input Solution (not visible by default)

(A; h)
(B; j
(C; b)
(D; e)
(F; d)
(G; g)
(H; i)
(I; a)

Note (optional)

While real marriages are far more complex than this, this wording is a common way to express the math problem. Please don't think I'm a sexist jerk for this!

Edited 22 Feb to make it a 10x10 matrix, updating challenge and solution.

The Problem

Determine all the tiles that are visible to the hero (@) in the given map.

Line of sight can be established between two tiles if you can draw a straight line from any part of tile A into any part of tile B so that the line doesn't intersect with any walls.

Input Description

The first line of input contains the number of columns, number of rows and vision range (in tiles) separated by spaces.

The following lines contain the dungeon map with the given dimensions where

• . is empty floor

• # is a wall

• @ is the hero

Each input is guaranteed to contain a single hero.

Output Description

The program should print the dungeon map as it is in the input, but so that all tiles that are not visible to the hero are replaced with spaces.

The vision range given in the input further restricts visibility so that the following must hold for each visible tile: (column delta)² + (row delta)² <= (vision range)²

Input/Output Samples

Input 1

The trivial case.

9 9 6
#########
#.......#
#.......#
#.......#
#...@...#
#.......#
#.......#
#.......#
#########

Output 1

Each wall segment around the hero should be visible.

#########
#.......#
#.......#
#.......#
#...@...#
#.......#
#.......#
#.......#
#########

Input 2

Limited vision range

9 9 4
#########
#.......#
#.......#
#.......#
#...@...#
#.......#
#.......#
#.......#
#########

Output 2

Only the walls at 90 degree angles should be visible.

    #
  .....
 .......
 .......
#...@...#
 .......
 .......
  .....
    #

Input 3

Back against the wall

9 9 5
#########
#.......#
#.......#
#....#..#
#....#.@#
#....#..#
#.......#
#.......#
#########

Output 3

The closest wall should be fully visible, including the corners.

    #####
    ....#
     ...#
     #..#
     #.@#
     #..#
     ...#
    ....#
    #####

Input 4

Peeking a corner

9 9 7
#########
#.......#
####....#
#...@...#
#.......#
#...#...#
#...#...#
#...#...#
#########

Output 4

First tile behind the top wall is visible. The vertical wall directly below is hidden.

   ######
   .....#
####....#
#...@...#
#.......#
#...#...#
#... ...#
#..   ..#
###   ###