Sandbox for Proposed Challenges

Question

This "sandbox" is a place where Code Golf users can get feedback on prospective challenges they wish to post to main. This is useful because writing a clear and fully specified challenge on your first try can be difficult, and there is a much better chance of your challenge being well received if you post it in the sandbox first.

Sandbox FAQ

Posting

To post to the sandbox, scroll to the bottom of this page and click "Answer This Question". Click "OK" when it asks if you really want to add another answer.

Write your challenge just as you would when actually posting it, though you can optionally add a title at the top. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it.

When you think your challenge is ready for the public, go ahead and post it, and replace the post here with a link to the challenge and delete the sandbox post.

Discussion

The purpose of the sandbox is to give and receive feedback on posts. If you want to, feel free to give feedback to any posts you see here. Important things to comment about can include:

• Parts of the challenge you found unclear
• Comments addressing specific points mentioned in the proposal
• Problems that could make the challenge uninteresting or unfit for the site

You don't need any qualifications to review sandbox posts. The target audience of most of these challenges is code golfers like you, so anything you find unclear will probably be unclear to others.

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

It is recommended to leave your posts in the sandbox for at least several days, and until it receives upvotes and any feedback has been addressed.

Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

To add an inline tag to a proposal, use shortcut link syntax with a prefix: [tag:king-of-the-hill]. To search for posts with a certain tag, include the name in quotes: "king-of-the-hill".

Answer 1

Generate random seeds for strings

Consider the following pseudocode:

function randomString(long input) {
    accumulator = "";
    random = random.seededWith(input);
    while(true) {
        x = random.nextInteger(27); # generate integer 0-26
        if(x == 0) break;
        accumulator += x + 'a'; # add lowercase letter from a-z for values 1-26
    }
    return accumulator;
}

In other words, this generates a random lowercase string based on a random number seed.

Your job is not to write this behavior.

For this golf, your job is to REVERSE this process. Receive a String as input, and return the random seed that would generate this string, using whatever pseudorandom algorithm is included by default in your language - so different languages will have different numbers returned for the same string.

However, the algorithm used to regenerate the strings should be the same for all languages.

Fine print

You may write a program or function, which returns the output as an integer or long (whatever's appropriate for your language) or printing it to STDOUT (or closest alternative). You may optionally include a single trailing newline in the output.

If the String cannot be generated in this method, your program should throw an exception and/or print an error message of some sort.

Additionally, standard loopholes which are no longer funny are banned. You may not use external libraries unless your language doesn't support seeded random number generation by default. If that is the case, then you may use the library for random number generation that is most commonly used by that language's community.

Citations

This question has been brought to you by: Why does this code using random strings print hello world?

Answer 2

Structural Damage Simulation

popularity-contest grid (either ascii-art or image-processing, haven't decided yet)

Introduction

In this challenge, you are given a two-dimensional map or a brick structure. Each brick is glued to its four neighbors, and is guaranteed to be connected to the ground, that is, the bottom edge of the input grid, via adjacent bricks. This structure is affected by gravity, which may cause some of the bricks to break, depending on their durability. Your task is to predict whether this happens, and where.

Spec

The input is given as a grid of the ASCII characters . and # that represent empty space and square bricks OR a black-and-white image with the black pixels representing bricks. You are also given a nonnegative number that represents the durability of the bricks; you can choose the valid type (integer or float) and range of this parameter and how it affects the computation. Your output is a grid in the same format as the input, but with some of the bricks replaced by Xs (or gray/red pixels); they represent bricks that have broken under the strain caused by the weight of the structure.

Example

Suppose we have the following input grid (replace with an image if that's chosen as the input format)

................
..######...####.
..######...####.
..########.####.
...###...#.####.
.....#...######.
.....#.....####.
.....#......#...
.....#.######...
.....#####......
.....#######....
.....#######....

The narrow parts of the structure are likely to break, especially the vertical ones, but the solid parts may very well hold themselves together. A possible output would be

................
..######...####.
..######...####.
..######XX.####.
...###...X.####.
.....#...X#####.
.....X.....####.
.....X......X...
.....X.#XXXXX...
.....####X......
.....#######....
.....#######....

TODO: add more test cases.

Scoring

This is a popularity contest, meaning that the answer with the highest vote tally wins. Voters are encouraged to take the following criteria into account:

• Simplicity. Simple and elegant algorithms are favored over complex and over-engineered ones. Elegance includes reasonable speed, so very slow algorithms are discouraged.
• Realism. The outputs should be close to the physical intuition of most people.
• Flexibility. Solutions should preferably handle complicated structures and extreme values of durability.

Answer 3

Cops 'n' Robbers - Hide a keyword in each answer answer-chaining

This is an idea I'm still working on, but I want some feedback on whether or not it could pan out well.

Cops

The robbers are here! They've found our files! We, need to encrypt them! We need a certain key, something special that clearly shows what the real program is. We need to keep writing our new files, but we must keep encoding them. When a robber cracks a key, we find the key they cracked and write a new file off of that key! For example, we will hide the encryption key for file #2 in file #1, then file #2 hides a key for file #3, and so on. The files are safe if they go uncracked for 5 days, in which we win! But if the robbers crack all 100 of our files, we lose!

Robbers

We found the cops' files! Not only that, we cracked their encryption scheme! In file #1, they hide a key for file #2, which hides a key for file #3, and so on. Our goal is to hack all 100 files. The only catch? We'll lose our connection if we don't crack a file within 5 days.

In English, Please?

Basically, the cops will upload an answer with a program when the robbers crack the previous answer. The clue to the next answer is hidden in this one, encoded with the clue from the last answer. If a robber guesses wrong, that robber can not guess again on the same answer. If a answer remains uncracked for 5 days, cops win. If robbers guess all 100 answers, the robbers win.

Winners

The winner for the cops is whoever made the uncrackable file. For the robbers, it's whoever cracked the most files (in event of a tie, later answers are better than old ones.)

Answer 4

Astrometric Tiling

A common problem in astronomy is the stitching together of astronomical images to create a mosaic of the entire imaging survey. This can't be done by naively putting the images next to each other in a grid - they might have slightly different dimensions, and certainly have different positions & orientations, which might overlap.

The solution is to calculate the positions of the objects (usually stars) in each image in celestial coordinates, a process known as Astrometry. (This is not the challenge, as it's far too difficult for a codegolf, but if you're interested in that process, take a look at astrometry.net.) Once an astrometric solution for a given image is found, every star's position on the sky can be calculated based on its position on the image.

The Challenge

Write a program to accept lists of coordinates for some number N>=2 of astronomical images, and output a transformation matrix for each image to create the mosaic.

Input

You may accept either a list of coordinate lists, or a list of filenames containing coordinate lists, whichever is more convenient. The coordinate list (length >= 10) for a given image is made up of 4 coordinates per star: x,y in whole number pixel coordinates on the image, and a,d in float (requiring precision to at least 10^-5) celestial coordinates. Assume that every star's coordinates are exact, and that the same celestial coordinates in two different lists refer to the same star.

Output

Your program should output a 3x3 affine transformation matrix for x,y in each image (alternatively, you can output a matrix for each image after the first, if you would like to use the first as a reference), which can be used to tile the images in such a way as to align the celestial coordinates in adjacent & overlapping images.

Scoring

This is a (admittedly quite challenging) code golf, so shortest in bytes wins.

I'll need to produce a test case, which I will do before posting.

Answer 5

Create a program or function that, given a postfix expression, converts it to the simplest equivalent expression. The expression may contain real numbers, floating variables denoted a to z, and the basic arithmetic operators +-*/^.

Two expressions are equivalent if they produce the same result for all possible integer values of the variables. "Simplest" means you should return the equivalent expression with the least number of operators. If there are multiple expressions with the same number of operators, pick the shortest.

Example

Consider the expression (8+4*y)/2+x*2. In postfix notation, this would be

8,4,y,*,+,2,/,x,2,*,+

This should yield the output

2,2,y,+,x,+,*

which corresponds to (2+y+x)*2.

Question:

this challenge is irrelevant of code length , so i want to ask , any scoring methods i can use in this defiance

i propose : picked up nine variant expressions with different polynomial degrees , which im free to choose , tested as input for all concurrent codes , then validate the lowest sum = (number_of_operations)^2+length(output_string)

Answer 6

Detect limit points in (possibly) oscilating sequence

Popularity Contest, Algorithms

Given an (infinite) sequence of numbers, your task is to find an algorithm (and write a corresponding program) that takes the sequence as input and determines

• Whether the sequence converges to a cyclic behaviour. That means the sequence will oscillate throu one or more values, that means whether it has one or more limit points. In this case it should output the limit points.

• diverges (does not end up in one or more limit point). In this case it should output a message that says so.

• No defined behaviour for sequences that do not have acyclic limit points.

A limit point is a value such that for every neighbourhood of that value an infinite number of sequence elements are within that neighbourhood.

Of course you can only use a finite part of the sequence, so you the task is ambiguous, but the larger the given sample the better your algorithm should be able to dectect the cycles. As this is difficult to achieve for arbitrary sequences, you are allowed to use 'fine tuing parameters' that can be changed manually in order for your algorithm to work best for the given set of sequences. Please document what those parameters do.

In this case here, you can assume that the sequence will converge to a behaviour where it cycles throu all the n limit points without gaps (intermediate values that are not limit points) and always in the same order.

Motivation

You perhaps have already see this diagram (the bifurcation diagram of the logistic map)

In order to generate this diagram, you have to compute a sequence for every r and compute the limit points x of each of those sequences (which in this case are cyclic). Then you plot those x against r. The sequence is generated by the recursive function (logistic map) with a starting value 0< x(0) < 1 (usually something like 0.5)

x(n+1) := r * x(n) * (1 - x(n))

The sequences generated this way are nice examples of the sequences that your algorithm should be able to detect.

Your submission

should consist of

• a function/program that executes your algorithm on a given sequence (input in any way you like),
• a description of how your algorithm works,
• and a program that uses your function for generating the bifurcation diagram above.

Examples

Following sequence is generated by 1+(-1)^n*(10+n)/n This sequence does not converge in the usual sence of sequences but it has limit points at 0 and 2. The sequence looks like this, so the

This is from the example above (logistic map with r=3.5), here we have 4 limit points:

The following sequence is bounded (and therefore has at least one limit point) but does not converge and does not seem to have a cyclic behaviour. (It is generated by x(n) = [pi*n^3 (mod e)]/e)

META:

I'm happy to hear from you what you think. So far I did not find any sources that described algorithms that do exactly this task, but there may very well exist such algorithms. If you can improve the text please do so! Any suggestions are welcome.

Answer 7

Quaternion calculator

Quaternions are extensions of the complex number system that are used in 3d graphics and some other applications. In addition to i, there is also j and k. j^2 and k^2 are both -1, however, ij=k, jk=i, ki=j, ji=-k, kj=-i, and ik=-j. Write a calculator that can calculate addition, subtraction, multiplication, division, and exponents. This is a code golf challenge, shortest answer wins.

EDIT: sample input: (2+4i+3j)*i^(j+2k)/(5j-i)+1

Answer 8

Kaos Pendulum and Einstein's Revenge

The Double Pendulum system is a relatively simple system with quite complex behavior that's highly sensitive to initial conditions (i.e., "chaotic").

Doctor Kaos has designed a particularly fiendish double pendulum, using his diabolical machine "Einstein's Revenge". Einstein's Revenge is a device which couples matter and energy, causing the mass of the first pendulum (connected to the anchor point) to be a function of the energy of the second: m1 = sqrt(PE2**2 + KE2**2), with the potential energy measured from the rest position of the pendulum.

For this challenge, you must write a program or function to simulate a basic Kaos Pendulum, where the second pendulum has unit mass and both pendulums are unit length. It must accept the starting position of the Pendulum - two real numbers, theta1 and theta2 - as input or command-line arguments, and one positive integer equal to the number of seconds the pendulum will be active.

Your program must output the value of theta1 and theta2 for each second, either printing to stdout or returning as a list, or something similar.

Notes

I don't know if this should be a golf, a popularity contest, or if there should be some scoring method for some other type of challenge.

Answer 9

Blind (deterministic) Jenga

The idea for this came up in the chat room, under the broader topic of how to make a human dexterity game into a software KotH challenge. Here's the basic idea, which I don't think works, but I'd love to get feedback to make it better.

The jenga tower has three blocks per layer. Layers alternate between N/S aligned blocks and E/W aligned blocks.

There may be just two players, or more than two.

Each turn a player selects a block location to probe. If there's no block there, the player gets to go again. If there's a block there, it is removed from the stack. If this causes the tower to fall, the player loses. Otherwise, the block is placed in the next safe position at the top of the tower, unless all available positions are unsafe in which case the player loses. If the player has not lost, it is now the next player's turn. Continue until some player loses.

I think this won't work well because it will boil down to a relatively random competition between bots that start with edge pieces and bots that start with center pieces. I don't want to run the contest just to find out that that's the case. Maybe putting four blocks per layer would make that a non-issue. I'm open to other suggestions on how to make this challenge work.

Answer 10

A king-of-the-hill idea. Maybe I'll do it a long time later...

You have these options each turn (they need better names and a plausible background):

• Meet k If the bot k also did meet you, and nobody injects, both of your scores are increased by 1. Otherwise nothing happens. But if k is yourself, this is invalid and will be just like doing nothing.
• Invite k The bot k gets a notification that you are doing this, and in the next round, your output is ignored and you must do Meet k.
• Inspect k You will get these informations at the beginning of next round:
  • What the bot k was doing.
  • The score change of bot k.
  • Who was inviting bot k.
  • Who was trying to meet bot k. (This is not known by bot k if not inspecting himself and his score is not changed.)
  • Who was inspecting bot k. (This is not known by bot k if not inspecting himself.)
  • Who was injecting bot k (and another bot). (This is not known by bot k if not inspecting himself and his score is not changed.)
• Inject j k If j is meeting k and k is meeting j, your score is increased by 10 and their scores are both decreased by 1 instead. If one of them is pretending doing that, and the other is pretending or really doing that, your score doesn't change. Otherwise, your score is decreased by 10. They'll not know who is injecting unless they are inspecting you or self-inspecting instead.
• DoNothing Nothing happens.

Possible other options:

• Pretend action: action is any action other than Pretend. It's the same as doing nothing, but inspectors will be told that you are doing that action. The score change that the inspectors will see is calculated as if you really did that.
• Multiply: For each turn until the next time you meet some bot each other, the points you, the other bot and all the bots injecting you get are doubled (or incremented, I'm not sure).

Everybody can see only their own score, bots inviting them and the result from Inspect.

Answer 11

Is this a red-black tree?

A red-black tree is a binary search tree where each node has an additional 'colour' property, which can be black or red. The root and leaf nodes must be black, each red node must have black children, and the path from any node to any child leaves must have the same number of black nodes. For instance:

2B
|  \
1R  3B
|   |
~   ~

Is invalid because of a black violation (the path from the root to each leaf has a different number of blacks).

Your task is to determine whether a given tree is a valid Red-Black tree.

Input

The input will be a string matching [ a-zA-Z]. A space represents a leaf, a lowercase character a black node, and an uppercase character a red node. The value of a node is the position in the alphabet: a is 0, b is 1, C is 2, and so on. The children of the node in position n are in positions 2n+1 and 2n+2. If the string ends before the position you're looking for, that node is a leaf. For instance, baD cf E corresponds to:

       1,B

     /     \

 0,B         3,R

           /     \

       2,B         5,B

                 /

             4,R

Output

Your program should output something other than whitespace on STDOUT if and only if the input represents a valid tree.

Simple test cases

True      False
" "       ""        (Root black violation)
"a"       "A"       (Root black violation)
"cAD"     "cAB"     (Order violation)
"dBeac"   "dBea"    (Black violation)
          "dAE B"   (Red violation)  

Answer 12

Question about extrapolating data from an incomplete tennis scoreboard

code-golf

Introduction

It is a fine day at the Stack Exchange tennis club. The players have just finished playing a grand tennis tournament in a round robin style (every player plays every other player once). The final results were about to be announced when suddenly, the scoreboard explodes! It is a total disaster - now nobody knows what the final scores were! Luckily, a piece of the scoreboard is still intact. Can you write a program to figure out the rest of the scoreboard from only a small part of it?

If there are k players, our scoreboard would have had k*3 entries, indicating each player's wins, losses, and draws. It is presented in a list of space separated comma separated tuples. For instance, in a game with 4 players here is a possible final scoreboard:

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

In this example the first player did not win anything, lost twice, and drew once; the second player won all three of their matches; the third player won once, lost once, and drew once; and the fourth player won once and lost twice.

Input Description

As input, you are given a scoreboard similar to the one above, except some of the numbers have been replaced by ?. The ? indicate the numbers that were unrecoverable after the explosion. For instance:

?,?,1 0,?,0 ?,?,?

Output Description

Output the scoreboard, with the ?s replaced with the actual scores. The input scoreboard will always have enough information for you to deduce the final scoreboard.

For example, consider the above input. We know that the second player has 0 wins and 0 draws, therefore, they must have lost both of their games. The first player has a single draw, and since we know the first player beat the second player, that draw must be with the third player. Thus the output is:

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

Sample inputs and outputs

TODO: Sample inputs and outputs of higher k

Sandbox Questions

• I have an alternate formulation for this question where instead of an incomplete scoreboard, the complete scoreboard is given and the program has to generate a table of which player beat which player. Which challenge do you think would be more interesting?

Answer 13

Sudoku Swapping Shenanigans

code-golf? fastest-code?

Honestly, there's not many shenanigans in this challenge but I wanted that sweet tautogram title.

Introduction

Imagine you're on a train, and there is a Sudoku grid that's already been entirely filled in left on the seat. We'll represent this grid as a series of 81 comma separated integers from 1-9 on a single line. Each cell in the grid can be numbered as follows:

As with all Sudoku grids, there will be exactly 9 of each number present in the input.

The Sudoku grid will not be completed correctly. It will have the right number of each number, but they will be positioned wrong. Your program's task is to swap these numbers to solve the Sudoku puzzle correctly.

(Since your stop is next, you want to make this program solve the Sudoku puzzle as fast as possible.)

or:

(Since you're writing this program on a napkin, you want to make it use as little bytes as possible.)

Input Description

Input consists of 81 positive integers that are comma separated. Some of them will be prefixed with an X which means those are the ones that are already placed and you can't swap them.

Example input goes here.

Output Description

Output the swaps required to solve the grid in the fewest number of swaps. You should have a line for each swap, consisting of two numbers in the form:

a,b

where a and b are both different and in the range 0-80.

Here's an example output (and I haven't actually written the example input yet!)

80,0
8,9
14,15

So that would mean that to solve the grid we need to swap the number in position 80 with the number in position 0, the number in position 8 with the number in position 9, etc.

Sandbox Questions

• Not sure if it should be code-golf or fastest-code. Suggestions appreciated.

Answer 14

Code golf challenge: Write a program or a function that solves the following problem. Normal code-golf rules apply.

Given a set of subnets, give the smallest possible network these can belong to. You should consider the network- and broadcast addresses in your calculations.

Example input:

128.208.0.0/18
128.208.128.0/17
128.208.96.0/19

Example output:

128.208.0.0/16

You might want to read up on IP prefixes before trying this.

Answer 15

Flash Cards Viewer

code-golf

In this challenge, your goal is to produce a flash card viewer. Since this is a Code Golf challenge, it won't be a particularly featureful flash card viewer - in fact, it'll be the bare minimum a flash card viewer can be. We'll implement the following features:

1. Reading a list of flash cards from a file;
2. Quizzing the user on either "side" of the flash cards;
3. Reporting to the user which ones they got incorrect.

Input Description

As feature number 1 suggests, for this challenge you must read input from a file (unfortunately, your language cannot participate if it does not support reading from a file). The file shall be called cards.txt and will be formatted as a simple list of values separated by a pipe character |. For instance, a "Family Names in Chinese" flash card deck might look like this:

Mother|妈妈
Father|爸爸
Elder Sister|姐姐
Younger Sister|妹妹
Older Brother|哥哥
Younger Brother|弟弟

Output Description

First, your program should ask the user which side of the cards they want to revise, using a user input function such as prompt() or raw_input(). An input of 0 indicates the user wants to revise the left side of the cards, and an input of 1 indicates the user wants to revise the right side of the cards. Use the message "Choose side:" when asking the user.

After that, the program will pick out random entries from the opposite side of the user's selection, and prompt the user to type in the entry's corresponding value. After the user has gone through the entire list, output the pairs that he or she got incorrect.

Here is an example of what a possible session might look like. What the user inputted in this example is signified with >.

Choose side:
>0
妹妹
>Younger Sister
妈妈
>Mother
爸爸
>Father
哥哥
>Younger Brother
弟弟
>Older Brother
Older Brother|哥哥
Younger Brother|弟弟

Answer 16

Fibonacci Box Packing Factory

code-golf fibonacci

Introduction

The Electronic Goods Company is a company that produces electronic item of various sizes. They need to package their items in boxes so that they can be shipped off to the store. There are some restrictions regarding what item can be stored in what box:

1. Each box can only contain a single item, and each item can only be contained in one box;
2. The volume of the item cannot exceed the volume of the box;
3. If the volume of the item is exactly the volume of the box, the item can be placed in the box without any padding material required;
4. If the volume of the item is less than the volume of the box, then padding material equal to the difference of volumes must be placed in the box to prevent the item breaking.

For example, an item that had a volume of 2m³ could be placed in a box of volume 2m³ without any extra padding material, but if the same item was placed in a box of volume 5m³, we'd need to add padding material of 3m³.

The supplier company is called the Fibonacci Box Company, which supplies The Electronics Goods Company with N boxes and P metres squared of filling material. Each box's volume is determined by the Fibonacci sequence (so the first box's volume is 1, the second is also 1, the third is 2, the fourth is 3, the fifth is 5, etc.).

Your program goal is to figure out the minimum amount of padding material required to pack all of the electronic items.

Input Description

Input is a space separated list of integers that indicate the volume in square metres of the electronic items.

//TODO: Example inputs and outputs

Output Description

Output the minimum value of P required to fill all the boxes.

//TODO: Example inputs and outputs

Answer 17

NP Cops and Robbers

This is an idea I've had for a while, and I really want to get it to work, but there are some large hurdles.

Hurdle 1: I need to pick a puzzle, preferably one that is NP-Complete. I think lots of Nikoli puzzles are good candidates, and I am leaning towards Light Up

Cops:

Cops will write a program to generate a puzzle. The puzzle has a maximum size of WxH. The cops must be able to generate the puzzle in under 1 second. Puzzles must be deterministic, but randomness is allowed as long as I can set the seed. The puzzles generated must have only 1 solution. The cop will post a sample puzzle in his post (for the robbers to use)

Your score is the shortest time any of the robbers solved your puzzle. Highest score wins.

Robbers:

Robbers write programs to solve the puzzles. Robbers are not allowed to target the specific puzzles, but are allowed to target the specific algorithms used to generate the puzzle. If the cop were to change the sample puzzle posted, the robber should still be able to solve the new puzzle in a similar amount of time.

If you solve a puzzle faster than any other robber, your score increases by the time taken to solve that puzzle. Highest score wins.

Hurdle 2: How to measure time taken. I don't want to run all of the cops/robbers, especially if this becomes popular. I also don't want to use the GOLF framework, as that would take a really long time to run. So, possible I could have the person run som CPU-intesive algorithm on their computer, measure how long it takes, and scale all of their answers according to that time.

Answer 18

Create a basic spell checker

code-golf In this challenge, you have to implement a basic spell checker. Your program will use the first input as a source.

Specifications

• You will receive two inputs, one is a sentence/paragraph you use as a source for your spell checker, and the other includes wrong words (they can be correct too) which you have to correct using the first input.
• Possible mistakes: Missing one letter (e.g. helo), one extra letter (e.g. heello), substitution of one character (e.g. hilp instead of help), transposition of two adjacent characters (e.g. hlep instead of help).
• In other words, the mistake and the original word have to have a Damerau–Levenshtein distance of one.
• You can separate the inputs in any reasonable format. For example, instead of using a newline, you can use a pipe sign to separate them. (|) However, watch out so you don't use something like letters because they are used in the 1st input.
• It's possible for a word to have neither an identical word nor a word with 1 distance from the first input. You will have to leave them unchanged.
• You don't need to do anything with punctuation. That is, I won't test words that are followed by a punctuation. (E.g. From the first example, I won't ask the correction of 'blod')
• Challenge is case insensitive, both the input and output. Meaning that if 'The' is used in the 1st input and the 2nd input is 'teh' you can change it to 'The', 'teh', 'teH', and similar cases.
• If a word is in the first input, but also has a distance of 1 with one of the other words, do not correct it.
• If there are two words with the same distance, you can output either of them. (E.g. 'en' can change into 'on' and 'in' if the words are both in the first input.) You can also output both of them, but you'll have to use a slash between them. (E.g. 'en' can be corrected into 'in/on')
• You can assume words are just sequences of letters separated by spaces.
• You can use STDIN or the closest alternative in your language.
• Standard loophole rules apply.
• This is code-golf, so the shortest code wins.

Examples

Input:

A criminal strain ran in his blood, which, instead of being modified, was increased and rendered infinitely more dangerous by his extraordinary mental powers. 

increasd mnetal

Output:

increased mental

Input:

The fact is that upon his entrance I had instantly recognized the extreme personal danger in which I lay.

I recognizi dnger en

Output:

I recognize danger in    

Answer 19

Multiply with restricted operations: Best lower bound

fastest-code

Multiply with restricted operations is a challenge to multiply two variables using as few as possible of four allowed operations: addition, reciprocal, negation, and variable assignment. The current best is 22 operations.

Your goal is to prove a lower bound L, a number for which you demonstrate that there are no solutions with fewer that L operations. The highest L wins.

You must explain why your code demonstrates the lower bound, and I must be able verify your code by running it. There is a time limit of 30 minutes. The natural approach is to search the space of possible solutions, perhaps shrinking it via mathematical arguments, but any method is allowed. Purely mathematical proofs without code are also valid.

Your code is limited to 30 minutes and 3GB of memory on my machine (Windows 7 with a Intel Core i5-460M processor). I may be satisfied with someone else running your code to confirm with a conservative adjustment for different machine speeds.

Your code needs to run on easily-available free software. Please include instructions on how to run your code.

The winner will be the highest lower-bound proven by [date]. Tiebreak is fastest runtime on my computer. I will give a bounty of 500 rep to the winner.

If your lower bound matches a solution, narrowing down the optimum to a single value, I will award you an additional bounty of 300 rep.

---

For Sandbox:

• I haven't done a fastest code before. Anything I'm missing? Any machine specs I should add?
• When to have deadline?

Answer 20

Date-A-List!

code-golf graphs

Introduction

The year is 20XX. Lists of integers are now members of society with a full set of rights. Like humans, lists like to have dates and get married. In this challenge, we'll produce a program "Date-A-List!" that will get as many lists as possible on happy and compatible dates. Lists tend to prefer using programs that use as little bytes as possible, so this program will be golfed.

Lists are compatible (that is, you can assign them to a date together) if they share 2 or more integers in the same order. For instance, the lists (1 2 3) and (2 3 5) would be compatible. The lists (1 2 3) and (3 2 5) would not be compatible because they do not share 2 or more integers that are in the same order.

Lists are also always monogamous -- they will never go on a date with more than one list. For instance, consider the lists (1 2 3), (2 3 5) and (5 1 2) -- although the first list is compatible with both of the others, it may only date one of them.

Input Description

Input is a list of lists in brackets, space separated:

(1 2 3) (2 3 5) (5 1 2)

That input would indicate three lists to be assigned to dates: [1, 2, 3], [2, 3, 5], and [5, 1, 2].

Output Description

If n is the maximum number of dates possible, output n lines, each line consisting of two space separated lists which are to be matched up. For instance, on the example input there are two possible outputs:

(1 2 3) (2 3 5)

or:

(1 2 3) (5 1 2)

[TODO: More complex inputs and outputs]

Answer 21

5-a-side Toroidal Bot Soccer

king-of-the-hill

Randomised teams

This is a team game. Rather than being assigned permanently to one team or the other, each bot will play in a number of games, each for a different randomly composed team of 5 players ("5-a-side"), and score a point for each game in which its team wins. This means every game requires team work, but there is still a single overall winner after all games are played.

Rules

There are no rules for the players (no referee, no penalties, no off-side rule). The movement of the ball defines the score and the players can do as they see fit.

Scoring

There are no goal posts. If the ball moves off the right hand edge of the field, it reappears at the left hand edge of the field and team 1 scores a goal. Similarly team 2 score if it moves off the left hand edge and reappears at the right. The score will be represented by a single integer, that is increased by one when team 1 scores, and decreased by one when team 2 scores. At the end of a game, team 1 wins if the score is positive, team 2 wins if the score is negative, and a zero score is a draw/tie.

Movement over the top and bottom edges has no effect on the score.

The game lasts for 2000 time steps (each bot provides 2000 moves). If there is no winner by the end of the game it is extended by up to a further 1000 moves, with the game ending if either team scores.

Physics

Physics is the main obstacle to real world toroidal soccer, and will not be respected in this game. The physics have been simplified as much as possible to hopefully allow games to be viewed live.

This is a non-contact sport. Bots pass straight through other bots (of either team) with no interaction. Each bot can only interact with the ball.

The playing field is a continuous rectangle of width 100 and height 50. The bots and the ball have radius 1. Bots and ball can move freely in any direction without meeting a boundary - the edges of the field wrap. The ball will rebound from any bot if their circumferences overlap.

Turning and acceleration

Due to the use of simplified physics this is quick to explain:

A bot has a facing angle and a velocity. A constant acceleration applies in the direction specified by the facing angle. Drag is a deceleration proportional to the velocity (an acceleration in the opposite direction to the velocity, proportional to the size of the velocity). This means a bot that does not turn will accelerate to a maximum velocity where the drag matches the acceleration.

A bot can turn any angle instantaneously, but the velocity (and hence direction) will only change gradually. For example, a bot changing direction by 180 degrees will continue travelling backwards while it slows down to zero velocity, and then accelerate in its new direction.

The ball has no acceleration of its own, so other than collisions, its only change in velocity is due to drag. There is no spin.

Collisions

Only the ball can be involved in a collision with a bot - bots pass straight through each other.

Although the radius of both bots and ball will be displayed visually as 1, I believe the results are the same if collision calculations are based on the bots having radius 2 and the ball being a point.

To keep calculation simple, the ball will be tested for collision with each bot by considering the bot to be a circle moving with constant velocity and the ball to be a point moving with constant velocity (that is, the acceleration will occur at instants, rather than continuously over time). Since this is also how the motion will be modelled generally, the collisions should be consistent with the motion of objects in the game.

This allows the exact point of collision to be calculated so the rebound can occur with no overlap.

Communication

There is no communication between bots. Each bot communicates solely with the controller.

The communication method will depend on the controller type (language agnostic/specific). Players will either be functions/objects in a specific language, or separate programs that communicate through STDIN/STDOUT.

Each step all bots will be supplied with the same information, and will provide a facing angle which will be a float in the range [0, 360).

The information supplied to bots will be as follows.

• Team direction (1 for team 1 or -1 for team 2)
• Current score (positive if team 1 is winning, negative if team 2 is winning)
• Facing angle and velocity of itself
• Facing angle and velocity of 4 team mates
• Facing angle and velocity of 5 opponents

Facing angle will be given as a float. Velocity will be given as x and y components, so two floats.

The information will therefore be received as two integers followed by 15 floats.

---

Sandbox questions

• Are any terms not familiar that would be worth linking or further explaining?
• Are there any further simplifications that could be made, without detracting from the game?
• Are any of the simplifications too much? Am I overlooking some way in which the game could become trivial?
• Is it correct to model the bots as radius 2 and the ball as a point? Does this give identical results to modelling the bots as radius 1 and the ball as radius 1?
• Are there any problems likely to arise from basing collision detection on constant velocity bots and ball? (Acceleration being applied instantaneously each step, rather than spread out over continuous time.)

Answer 22

Build a Rorschach Generator

2 possible challenges:

1.

Help a poor struggling game dev write some code to quickly and efficiently generate a Rorschach inkblot.

Using your language of choice, generate a Rorschach inkblot. You may use any method of generating a random seed.

The generated image must be in black and white and reflect down the middle of the image. This is a code golf so the shortest submission will win.

code-golf popularity-contest image-processing

OR

2.

Help a poor struggling game dev write some code to quickly and efficiently generate a Rorschach inkblot.

Given 2 input images (a source image and an image of a template inkblot), convert the first into the Rorschach inkblot of the second without changing the colours of the image.

You may assume that the images are the same size, however you may not display the original image unaltered. Anywhere in the template where the RGB values of the pixel are (255,255,255), you may not display the original image. The produced image must be vertically mirrored, so you will have 2 copies of the source image distorted and reflected in the result.

code-golf popularity-contest image-processing

Then I'd provide source images some of which would probably be shamelessly stolen from either the Voroni Map or the Mona Lisa Colour Palette questions because those questions are awesome.

My thoughts:

I'm essentially hoping to get the source image in a twisted demented fragmented form, similar to if you gave a small child red cordial then the source image and a blur tool and said go nuts. I feel like my second challenge has potential, but I feel like I need to improve the challenge description and detail exactly what I want to be produced, but I'm not sure how to do that without a wall of text and without unnecessarily restricting the challenge.

Answer 23

[Insert] Nerd Sniping Pattern (Series)

Having learned from Prime Nerd Sniping Pattern that hoping an optimal solution will not be spotted too quickly is not a good idea, I'd like to judge how much interest there is in a series of similar contests that have been demonstrated to not have an achievable optimal solution, allowing long term open ended competition.

Each one would need work to demonstrate this lack of an achievable optimal solution, and I'll put that work in if there is suffficient interest here.

For example, there could be a Fibonacci Nerd Sniping Pattern, Factorial Nerd Sniping Pattern, and so on. Each one would need to have a different method of defining the scoring pattern, so that different optimisation techniques and algorithms would be required for each one. This is what would ensure they are distinguished from each other as separate challenges in a series, rather than near duplicates.

What I've learned from my mistake with the primes

The prime scoring pattern had a checkerboard optimal solution because all of the scoring pixels were on opposite coloured checkerboard squares to the pixel being scored. I need to avoid this in any future scoring patterns, and more generally avoid any pattern that divides the image into two regions for scoring (where all of one region are scored by combinations of pixels from the other). Intuitively, there should be plenty of mixing.

As I think about it more, I'll add ideas here on things to rule out and things to ensure I have before considering a pattern scoring rule ready for posting.

Answer 24

Build a Mahjong AI

Mahjong is a traditional Chinese gambling game played throughout Asia in which four players draw and discard tiles in order to try to complete a hand of 14 tiles.

In this problem, a specification for a simplified version of Mahjong called "PPCG Mahjong" was given. Your task in this problem is to build a program that will play a version defined here called "Full PPCG Mahjong" (hereafter known as the FPM rules).

Your program will be an online program, taking input as it plays the game. (that does not necessarily mean it needs networking capabilities, but it means that it will output in reaction to ongoing input, not just all input at once.)

Tiles

There are 34 types of tiles in FPM.

1. The “bǐng”/“pin” (餅) tiles, also known as the circle tiles / dot tiles. These will be represented in text with a number from 1 to 9 and then the letter b, as in 1b, 2b, up to 9b.

2. The “suǒ”/“sou” (索) tiles, also known as the bamboo tiles. These will be represented in text with a number from 1 to 9 and then the letter s, as in 1s, 2s, up to 9s.

3. The “wàn”/“man” (萬) tiles, also known as the character tiles. These will be represented in text with a number from 1 to 9 and then the letter w, as in 1w, 2w, up to 9w.

The three tile types totalling 27 tiles above are called the number tiles.

4. The “fēng”/”fuu” (風) tiles, also known as the wind tiles. There is one wind tile for each cardinal direction. These will be represented in text with the letter of the wind's cardinal direction in capitals, repeated twice, as in: EE, SS, WW, or NN.

5. The “yuán”/“gen” (元) tiles, also known as the dragon tiles. There is one red, one green, and one white dragon, represented as ZZ (for zhōng 中/center), FF (for fā 發/fortune), and BB (for bái 白/white) respectively.

The two tile types above are called the honour tiles. There are four of each type of tile, for a total of 136 tiles.

Objective

The goal of Mahjong is to form a complete hand, which consists of four sets and a pair.

A set is one of:

• A sequence of number tiles. (e.g. 5w 6w 7w or 3s 4s 5s)

• A triplet of any tile (number or honour tile). (e.g. 3b 3b 3b or EE EE EE)

• A quadruplet of any tile. (e.g. 3b 3b 3b 3b or EE EE EE EE)

A complete hand will have 14 tiles if there are no quadruplets present; each quadruplet adds one tile to the hand's size, up to a possible 18.

Gameplay

Mahjong is a game played in several hands (局, jú).

At the beginning of each hand, each player receives a text input of START [Wind] [Round number]. Each player is then given an input of 13 tiles, represented as a set of 13 space-separated strings (e.g. 1b 9s BB 3w 6w 4b ZZ 3w 5w 2s 6b NN NN) and assigned a different seat wind depending on where they "sit" at the virtual table (given as a single letter out of NESW).

Starting with the player at position East and moving clockwise around the compass, each player takes a turn in which:

• The player whose turn it is will be given a tile (自摸牌, zìmōpái) from the "wall" (the collection of tiles that have not been drawn or dealt yet) as a two-character input.

• The player can take actions during the standby phase:

  • If the player has four of the same tile in his hand, it can call kong (槓, gàng) and draw an extra tile. Those tiles must stay as a quadruplet from then on and cannot be used for anything else. The program does this by outputting kong [quadruplet tile] as text.

  • If the player previously called pung on a triplet and has a fourth of the tile, it can call kong as well.

  • If the player's hand is complete with this drawn tile, it may declare hu in which case the hand ends.

• The player will then produce an output of whatever tile it decides to discard. The tile that was discarded will be propagated as output to the other players in the form [seat] [discarded tile] (e.g. E 8w). The players can then call that tile if it will complete a set:

  • The player immediately after the discarding player may call chi (吃, chī) by outputting chi as text during the call phase, to complete a sequence.

  • Any other player can call pung (碰, pèng) to complete a triplet, similarly by outputting pung as text. Pung overrides chi when it happens.

  • Any player can also call kong (槓, gàng) to complete a quadruplet, also by outputting text, in which case they are given an extra tile as text input.

  • Any player can also call hu (胡, hú) to complete their hand regardless of whether they are completing a sequence, triplet, or pair. Hu overrides both pung/kong and chi.

  • If a player does not want to call tiles, it must output pass.

The turn immediately goes to the player who called the tile, and they skip their draw phase, discarding another tile immediately. If nobody called a tile, the next player draws one. At any point if a player calls, the other three players will receive an input indicating that the player in that seat made a call and what was called.

• For chi, the input will be in the form of [seat] chi [other two tiles] (e.g. S chi 6w 7w).

• For pung and kong, the input will be in the form of [seat] pung/kong. This is because all the tiles are identical to the called tile anyway.

• For hu, the input will be in the form of [seat] hu [all other tiles in hand].

In the above three cases, the tile being called is always the previously discarded tile.

• For a kong during the standby phase, the input will be in the form of [seat] kong [kong tile], because the kong tile is not implied to be the previously discarded tile.

• For a hu during the standby phase, the input will be in the form of [seat] hu [tile drawn]

Once a tile is called, the set that it makes is locked in place and cannot change for the rest of the hand. So if two tiles would make use of a tile in a called set, they may not use that tile.

A hand ends when either somebody calls hu validly or there are no more tiles to draw. (There is no dead wall in this game.) At that point, all players will receive an input of END to signal that the round has ended, and a summary of their points.

If somebody other than the dealer won, then the deal rotates. If the dealer or nobody won, then the deal stays the same. After four deal rotations, the prevailing wind also rotates.

A game of FPM consists of 16 such deal-rotations (rounds), such that each player gets to play one round with each combination of seat wind and table wind. Each player starts with a bank of 500 points. At the end of 16 rounds, the player with the most points is the winner of the game.

Example gameplay interaction

> START HAND EAST 1
> 1b 4b 6b 2s 9s 3w 3w 5w 6w NN NN ZZ BB
> E       // The player is East (dealer)
> NN      // East drew the north-wind first.
BB        // East decides to discard the white-dragon.
> S 3w    // Nobody called it, and South discards a 3-character.
pung      // East wants to pung the 3w tile.
ZZ        // East discards the red-dragon
> S pung  // South pungs the red-dragon.
> S 6w    // South discards a 6-character instead.
pass      // East has no use for this tile, so it passes.
> W kong 2s    // West declares a standby kong on 2-bamboo.
> W 3b    // West discards a 3-circle.
pass      // East passes again.
> N chi 2b 4b  // North chi-s it with a 2b and 4b.
> N 7s    // North discards a 7-bamboo.
pass
> 2w      // East's hand: 1b 4b 6b 2s 9s 2w 5w 6w NN NN NN -- 3w 3w 3w
2w        // East doesn't need the 2w, so he discards it.
> S hu 2b 3b 4b 7s 8s 9s 2w 6w 7w 8w ZZ ZZ ZZ 
          // South wins on that tile. The 2w completed his pair.
> END
> 496 506 499 499  // Their current point counts. South's hand was worth
                   // 2 points, so East pays 4 while the others pay 1.
> START EAST 2
> [13 more tiles]
> N       // The deal rotated, and this player is now North.

Brackets

Your program can participate in one of three levels of gameplay:

• Level 1, where every hand is worth exactly 8 points, and the only thing that matters is completing hands.

• Level 2, where every hand is worth the number of points in the points table section below, but any hand can still win.

• Level 3, where every hand is worth the number of points in the points table, but a hand must have at least 8 points total with that system to win.

Points

(TBD)

Penalties

The following are invalid moves:

• Failing to produce an output when required.

• Discarding a tile that is not in your hand, or when it is not your turn.

• Calling chi on any player other than the one immediately before you, or calling any tile that does not actually complete a set in your hand.

• Calling hu when your hand is not complete, or when your hand value does not meet the minimum point requirement in level 3 gameplay.

If your program makes an invalid move, the move will be rejected, your program will pay 20 points to each of the three other players, and for the rest of that round, it will be a "forced tsumogiri" player, which automatically discards every tile it draws and never calls anything.

Special Rules

There are no special rules such as dora or furiten in FPM. Any person may complete a hand at any time as long as it is a valid complete hand.

Answer 25

Team Gun Battle

king-of-the-hill

---

This is an individual competition, where the goal is to be the last player surviving. Fighting always takes place between two teams. At the beginning, every player is randomly assigned to one of two teams and placed randomly on the board.*

Each turn, a player can move north, south, east or west or stay. In addition to moving, they can also shoot a bullet north, south, east, or west. Note that players won't know about other players' movements when they move, but the shoot() method is called after all moving has taken place. The player can choose to shoot a light bullet, which travels 4 squares per frame and does 1 damage, or a heavy bullet, which travels 2 squares per frame and does 3 damage. The bullets do move on the same step they were shot in, so if a target is less than 4 units away, you can shoot a light bullet without any chance of the target dodging.

Every player has a starting health of 30 and 30 bullets to shoot.

After 1000** or so steps, the round will end. Whichever team has more players alive will be considered the winners. Ties will be broken by whichever team has the highest total health.*** Every player not on the winning team will die, and the winning team will be split up into two new teams. This means that half of those who were originally on your side are now your enemies. Another 1000 steps are executed and another winning team is chosen. This process repeats until there is only one player left.

This has some interesting strategic consequences. For example, if your team is winning, it is in your interest to start shooting players on your own team because they may not expect it and you will have to fight them eventually. Similarly, you don't want to waste all of your bullets on the first few rounds because your bullets and your health is not replenished after each round. I like trichoplax's suggestion where ammunition and health could be slightly restored after each round. You want to get your teammates to do as much work as possible before killing them.

The controller almost ready. This is the spec:

public class Player1 extends Player {
  public Direction move(World w, int stepsLeft) {
    // stepsLeft = # of steps left in round
    // List of players: w.getPlayers()
    // List of bullets: w.getBullets()
    Player p1 = w.getPlayers().get(0);
    // Check health: p1.getHealth()
    // Check # of bullets left: p1.getBullets()
    // Check team: p1.isOnSameTeam(this)
    // Check position: p1.getPosition()
    return Direction.NORTH; // always move north
  }
  public Bullet shoot(World w, int stepsLeft) {
    // similar to above
    return new Bullet(Direction.NORTH, true); // heavy bullet shot north
  }
}

*I think the board should be a square with side length 3*(# of players). Hopefully this would make to not too sparsely populated.

**Exact number to be determined. It may be based on the number of players (higher # of players = more steps until the end of the round). 1000 seems like a good number.

*** I'm working on a system that's somewhat more fair. Currently, if there was originally an odd number of players, they were split with one random team getting an extra player. Obviously, that team has a significant advantage under this system. Perhaps it could be percentage of surviving players?

Answer 26

A few minutes ago, I posted this question as a popularity-contest which was quickly put on hold as too broad. Specifically, the "there are no restrictions on what the programs/functions do" was apparently not quite right. A commenter also suggested that an empty program would be a possible answer which I knew, but didn't necessarily want to restrict as I think the popularity contest would have taken care of that. I'd be interested in any suggestions people have to make the question more appropriate for PPCG.

Also, I plan on asking with the tags popularity-contest and restricted-source. Does that seem right?

Here is the question:

Inspired by the bonus in this question

Write some code that can be run in multiple directions. In each direction, the code must be a complete program or a function. The code must be written in one language (so for example, you cannot have a python program that is also a whitespace program when run backwards).

Explanation of "multiple directions"

If your code is

abcd efgh
 ijklm
nop

Then backwards is

hgfe dcba
mlkji 
pon

And sideways is

a n
bio
cjp
dk
 l
em
f
g
h

Trivial example

Brainfuck

 .
.+++++++++
 +++++++++
 +++++++++
 +++++++++
 +++++++++
 +++++++++
 +++++++++
 +++++++++
 +++++++++.
         .

Notes

• there are no restrictions on what the functions/programs do
• your code must be able to run in at least two directions, but more is better
• abuse of comments is frowned upon but allowed

Answer 27

Allongiator code-golf

---

There are a lot of acronyms on the internet -- ROTFL, RTFM, NSA, laser, taser, and so on. Your job is to write code that, given an acronym, can figure out what that acronym might stand for. You'll be given an alphabetically-sorted list of words that you can use, to be provided in the format of your choice.

Note that if you're given an actual acronym, you don't have to provide what it really stands for. As an example, given ROTFL, you could output "rolling on the floor laughing", or you could output "rearrange orange thrice free language".

Input

1. A dictionary of all of the words you're allowed to use. This is guaranteed to have at least one word for each letter; your program is allowed to do anything it wants if it encounters a letter that it can't find a word for.
   • Not necessarily in alphabetical order
   • All in lowercase
2. A string of lowercase letters, with no whitespace, punctuation, or non-letter characters.

They can be given in any format you want. For example, the acronym could be the first command line argument and the dictionary the rest of them, or they could be arguments to a function, or given via standard input, or whatever.

The dictionary contents can be found [here].

Output

1. A string containing a space-delimited list of words that form the acronym given as input, from the dictionary given.
   • No trailing whitespace except for a single optional newline
   • The words must be chosen (pseudo-)randomly from the dictionary -- that is, if I run it twice with identical inputs, I should get different outputs¹.
   • It doesn't have to make sense or be plausible or grammatically correct. Any words that start with the right letters will do; however, bonus points² to anyone who manages that.

Since this is code-golf, the shortest answer wins.

All the standard prohibitions apply here, though with the note that accessing the dictionary from the web is acceptable, so long as it's the unmodified dictionary and nothing else.

^{1: Barring practically impossible situations.
2: That is, a browser cookie}

---

Sandbox (foot)notes:

This may very well be a duplicate. I looked around as much as I could, but I don't even know what this is called, so I didn't find much. Apologies if it is.

Would they be acronyms or initialisms? I'm not sure.

I'll add the actual dictionary once I've found a nice one that isn't massive.

Answer 28

Gimme your best shot

code-golf internet

Introduction

You're fed up. You've tried to sell your car but failed, not knowing whether your price is too high, too low or people are just too picky. Then a programmer decides to take a look at your car and makes you an offer using a program that he had written for judging a car's worth.

Challenge

Given a car's make, model and mileage, you have to find how much a car is worth using the method below. The shortest program to do so wins.

If the make or model of the car is incorrect, you must output "Error: [input make/model] is invalid".

Method

First of all, you should scrape all of the prices and mileages of all of the listings on AutoTrader.com of the specified car. Next, plot these on a graph (this graph is not needed to be shown) of mileage against prices.

On the graph you should draw a line of best fit. Now you can read the price on the line of best fit for the specified mileage of the car. Now output this with a dollar sign before the price.

Example

None of these prices are correct output

Ford Fiesta, 200 miles

Input: ford, fiesta, 200
Output: $15000

Subaru Outback, 0 miles

Input: subaru, outback, 0
Output: $27000

Example script

Here's my example test script in Python 2.7 (uses autotrader.co.uk though, not .com):

from BeautifulSoup import BeautifulSoup
import urllib2, sys, re, pylab

model, make, mileage, postcode = sys.argv[1:]
mileage = int(mileage)

page = urllib2.urlopen("http://www.autotrader.co.uk/search/used/cars/%s/%s/postcode/%s/"%(model.replace(" ","%20"), make.replace(" ","%20"), postcode)).read()
soup = BeautifulSoup(page)

results = soup.findAll("div", {"class":"search-result__content"})

cars = []

for j in results:
    pricetag = j.findAll(text=re.compile(r"£.*"))
    price = int(pricetag[0].replace(',','').replace('£',''))

    mileages = j.findAll(text=re.compile(r".+ miles"))
    mileagecar = int(mileages[1].replace(" miles","").replace(",",""))

    cars.append([mileagecar, price])

x = [k[0] for k in cars]
y = [i[1] for i in cars]

poly = pylab.polyfit(x, y, 2)

print("£"+str(int(pylab.poly1d(poly)(mileage)+0.5)))

Answer 29

Meta-Manufactoria

Manufactoria is a pretty great programming game. However, instead of writing machines to solve the problems, your goal is to write a program that creates the machines for you. If you are already familiar with Manufactoria, then for the next section, you only need to read the italicized phrases.

The Rules of Manufactoria

In this version of Manufactoria, you are placed in a 9x9 world. The input generator is in the center top square (4, 0), and the output acceptor is in the center bottom square (4, 8). When input is generated, it moves immediately down.

Input is represented by a robot that has a queue of colors. Output will be the same robot, but the queue may contain a different sequence of colors. Robots must always eventually end up in the output square. There are 2 colors available, Red and Blue.

Each tick, the robot moves 1 square. The direction the robot moves, and any modifications to the queue is determined by the square it is on. There are 3 types of squares:

1. Movement square. This square either moves the robot North, East, South, or West and does not affect the queue. You cannot have two movement squares on the same tile

2. Choice square. This square moves the robot based on the top color in the queue. The general Choice square moves the robot east if red, west if blue, south if empty, and never north. This square can be rotated or reflected to change the directions traveled.

3. Writer square. This square writes a color to the back of the queue, and moves the robot in a given direction.

STDIO and Scoring

Your program will be passed two lists of the same length, one containing the inputs, and the other containing the outputs. Each item of each list contains only the R and B characters, representing the input queue.

Your output is the board that solves the Manufactoria puzzle. Each square is represented by two characters. The first character represents the square type, the second represents the direction. The square types can be:

• Movement
• Choice
• Red writer
• Blue writer.
• .. Empty square
• II Input
• OO Output

The directions are: - North - East - South - West.

The direction listed for a choice tile represents the direction traveled if the queue is empty. If the direction is lowercase, the tile is reflected (which swaps the colors).

The program which solves more puzzles than any other program wins. In the event of a tie, the tiebreaker is the program that produces the most efficient solutions. Efficiency is measured by the number of times the robot moves across all of the solutions.

Your program should be a general solver. I may add puzzles to the ones listed below at any time.

Sample Puzzles

The solutions given below don't necessarily have to do what the title indicates. Your program's solution also doesn't have to match the ones listed below. It only needs to solve the inputs given. The format below is

[Inputs] [Outputs]
Solution Map

Example 1: Don't do anything

["","R","B","RRBR","BRRBRB"] ["","R","B","RRBR","BRRBRB"]

........II........
........MS........
........MS........
........MS........
........MS........
........MS........
........MS........
........MS........
........OO........

Example 2: Print second R and anything after:

["","R","B","RR","BRB","RBRBBB"] ["","","","R","","RBBB"]

........II........
..MSCSMWCSMW......
..RSMEMEMS........
BECsMEMEMS........
........MS........
........MS........
........MS........
........MS........
........OO........

Example 3: Reverse String (This doesn't reverse any string, it only works for the examples listed)

["","BBR","B","RRB","BRRRB","BBRB"] ["","RBB","B","BRR","BRRRB","BRBB"]

........IICsMERS..
......CECSCEMSBS..
......RSMSCEMSMW..
......REMSCEMS....
........MSRSMS....
........MSRSMS....
........MSRSMS....
........MSBWMW....
........OO........

Example 4: Only include Rs

["R","","BBR","BRR","B","RBRBRBBR","BBBBBBRRR","RBBBRBRBBB","RRRR"] ["R","","R","RR","","RRRR","RRR","RRR","RRRR"]

........II........
........MEMEMEMS..
MSCSMWCSMWCSMWCSMW
REREMERERSMW..MS..
........MSMWMWMW..
........MS........
........MS........
........MS........
........OO........

Answer 30

(Need a title.)

Write two programs (or functions) in the same language for these two tasks:

1. Given a list of integers, split at every non-negative integer. If there are two or more consecutive non-negative integers, your program should preserve the empty list between them.
2. Given a list of lists of negative integers, concatenate the lists and insert non-negative integers between them. The inserted integer after the nth list (zero-based) should be n.

Alternatively, you can increment every integer by one for both tasks. So you split at positive integers, accept non-positive integers in task 2 and the inserted integers start at 1.

The input for task 1 and the output for task 2 should have the same format, with the exception that one can be the string representation of the other in your programming language. The same goes for the output for task 1 and the input for task 2.

Your score is the total length of your two programs times (30 + their Levenshtein distance). Lowest score wins.

Example for task 1

Input:  [-5 7 8 -5 2 -6 -3 -3 8]
Output: [[-5] [] [-5] [-6 -3 -3] []]

Example for task 2

Input:  [[-5] [] [-5] [-6 -3 -3] []]
Output: [-5 0 1 -5 2 -6 -3 -3 3]