458
\$\begingroup\$

What is the Sandbox?

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

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, 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. 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, replace the post here with a link to the challenge and delete it.

See the Sandbox FAQ for more information on how to use the Sandbox.

The Sandbox works best if you sort posts by "active".

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

To add an inline tag to a proposal use shortcut link syntax with a prefix: [tag:king-of-the-hill]

\$\endgroup\$
  • \$\begingroup\$ How are tags added to questions? \$\endgroup\$ – guest271314 Jan 9 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – DJMcMayhem Aug 29 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – JL2210 Sep 26 at 15:57
  • 1
    \$\begingroup\$ @JL2210 We now have a permanent info box that links to the Sandbox, so the featured tag isn't necessary \$\endgroup\$ – caird coinheringaahing Sep 29 at 13:43
  • \$\begingroup\$ I think the sentence 'replace the post here with a link to the challenge and delete it' may specify that the deletion should be done immediately . \$\endgroup\$ – AZTECCO Oct 5 at 19:39

2559 Answers 2559

0
\$\begingroup\$

Break out of the digital world!

Note: The tag is just something I knocked up quickly, if anyone has any better ideas please let me know.

Challenge

You must write a morse code to ASCII translator using an external device (such as a button or the spacebar on the keyboard).

Dots

A button press is a dot when it has been pressed for 0.5 seconds or longer and released.

Dashes

A button press is a dash when it has been pressed for 1 second or longer and released.

Exit

A button press is an exit when it has been pressed for 5 seconds or more. This should end the program and display the result.

Space

A space is when there has been no button input for 1 second. This should move on to the next letter.

Your code should support every character on the following:

http://zunkworks.com/images/bluetoothmorse/morsecode1.gif

Winning

The shortest code wins. You may write this in any language that allows input from an external source. For example, Arduino or Python (on a Raspberry Pi).

\$\endgroup\$
  • 4
    \$\begingroup\$ Does this actually have to be able take input from hardware? Can you allow feeding in simulating data? I think a standard format like a sequence of numbers measuring current/voltage every millisecond would make it more accessible. \$\endgroup\$ – xnor Nov 18 '14 at 1:35
  • \$\begingroup\$ While I do own an arduino, I see absolutely no reason why this challenge should be limited to using an external switch. Is there anything wrong with using the space bar or a mouse button? If it HAS to be an external switch, how about I rip open my mouse and connect an old doorbell push across one of the mouse button contacts? \$\endgroup\$ – Level River St Nov 27 '14 at 20:45
0
\$\begingroup\$

VSEPR Strikes Back!

(Note: I know that the VSEPR method fails sometimes, and that there are exceptional molecules. This is addressed in the scoring system, and otherwise the challenge is about the molecules which conform.)

Most people who have taken an introductory chemistry course know about molecules, and (probably) the VSEPR theory of chemical bonding. Basically, the theory predicts the shape of a molecule given three main properties: the central atom A, the number of atoms bonded to the central atom X, and the number of lone electron pairs E on the central atom. Applying the VSEPR theory is simply a matter of finding the values of X and E (A always has an implied value of 1, as we'll see). This is called the AXE method. For example, a molecule which has 1 lone pair and 3 atoms bonded to the main atom is AX3E1, which is the trigonal pyramidal configuration.

The Challenge

Your job is, given a covalent chemical compound, to output the geometrical shape of the molecule inputted. But wait! exclaim the exasperated programmers, you can't expect us to input all of the molecular data for every element! Of course we can, but I'm not feeling particularly masochistic today, so born was the scoring system below.

The input is any molecule, such as CO2 or HgCl2, and the output should be the name of the shape and NOT the AXE form. Ions should have their charge put in parenthesis directly after the ion, such as CO3(2-) or NH4(1+). 1- and - (and 1+ and +) are all acceptable.

About the central atom A

In most cases, the central atom will be apparent. It usually has no subscript in the chemical formula: the C in CO2 is the central atom, for example. In a few cases, though, you might face compounds like ethelyne (C2O4), in which no clear atom is the central one. In this case, it is worth noting that such compounds are usually symmetrical, and considering any carbon to be the central atom will do.

Scoring System

The base score is the number of bytes the program takes.

  1. There is a minimum of 6 elements to be implemented for input; every 5 extra you add multiplies your score by 0.9.
  2. Multiply your score by 0.8 if you can make your code work for ions.
  3. Multiply your score by 0.9 if you can detect ionic compounds (VSEPR only works for covalent compounds) and reject them accordingly.
  4. Multiply your score by 0.8 if you also output the bond angles.
  5. There are certain classes of molecules which VSEPR fails to predict correctly, due to various reasons. (Check the first link in the post for the section on the exceptions.) Multiply your code by 0.9 per class if it returns those correctly.

Test Cases

The parts in brackets are optional bonuses from above.

CO2: CO2 -> linear [180*]
HgCl2: HgCl2 -> linear [180*]
H2O: H2O -> bent [104.5*]
[CO32-: CO3(2-) -> trigonal planar 120*]
BrF: BrF3 -> T-shaped [90*]
[NaCl: NaCl -> Ionic compound]
XeF4: XeF4 -> square planar [90*]

Notes:
- The bonding patterns are not valid when the central atom is a transition metal (so don't do that.).
- Standard loopholes apply.

\$\endgroup\$
0
\$\begingroup\$

One transparent colour sprite


Overview

This challenge will only involve a hex string as input and a hex string as output, but will be explained in terms of computer graphics.

Given a fixed size background image, a smaller fixed size sprite image and its location, place the sprite on the background image allowing the background to show through for one specified colour of the sprite image.


Details

  • The background image will always be 32 by 18 pixels.
  • The sprite image will always be 8 by 8 pixels.
  • The colours will always be in the range 0 to 3 inclusive.
  • There will always be exactly one transparent colour, from 0 to 3 inclusive.
  • The location (x, y) of the sprite may be outside or partially outside the background image.

Input

Since all inputs will always be the same size, there will be no separators, just a single string of hex digits.

To avoid having to define negative inputs, the top left pixel of the background image will be (128, 128), increasing left and down, and x and y will be defined by 2 hex digits each, giving a range of 0 to 255.

The input hex string will be made up of:

  • Background pixels, 2 per hex digit, a string of 32 * 18 * 0.5 = 288
  • Sprite pixels, 2 per hex digit, a string of 8 * 8 * 0.5 = 32
  • Transparent colour, a single hex digit (the most significant half of the hex digit is unused)
  • Sprite x and y, 2 hex digits each, a string of 2 * 2 = 4

The input will therefore be a string of 288 + 32 + 1 + 4 = 325 hex digits with no separators.

Output

The output is the finished 32 by 18 pixel image, as a string of 288 hex digits with no separators.

Format

Pixel order

Each image is ordered in English reading order, left to right then top to bottom. That is, the pixels are listed in rows. The first pixel listed will be the top left. This applies to both the background image and the sprite image.

Colour encoding

Pixel colours are encoded 2 per hex digit, most significant first.

For example, the hex digit B corresponds to binary 1011. This means the first pixel has value 10 = 2 and the second pixel has value 11 = 3.

Transparent colour

Since the single transparent colour is encoded in one hex digit, which normally holds 2 colours, the first 2 bits (most significant) are ignored and the last 2 bits (least significant) are used to represent the transparent colour.

For example, the hex digit D corresponds to binary 1101. The 11 is ignored and the 01 is used to indicate colour 1.

Although the first two binary digits are always ignored, you may not assume they are always 00. They may take any value and all hex inputs of the correct length should produce a valid output.

Coordinates

x and y are encoded as 2 hex digits each, most significant first.

For example, the hex string 2A corresponds to binary 00101010, and decimal 42

Case sensitivity

Your code may accept input as either upper case or lower case hex digits, or both. If it only accepts one or the other case, it must also output in the same case.

You may not choose an arbitrary 16 characters to represent hexadecimal. You must use either (or both) of the following as input:

0123456789abcdef

0123456789ABCDEF

You must choose one or other (not both/mixed) to use as output. That is, you may accept inconsistent inputs if you wish to, but the output must be either always lower case or always upper case.


Sandbox thoughts

  • I'm considering adding example inputs and outputs and maybe a snippet to verify the output of arbitrary inputs for testing.
\$\endgroup\$
0
\$\begingroup\$

Live Tennis Scoreboard

In this challenge, we're going to create a tennis scoreboard that could (theoretically) be used in an actual tennis match. The tennis scoreboard will display the score while listening on STDIN. As new results come in on STDIN, the tennis scoreboard will update itself accordingly.

Description of Input

When the scoreboard is first instantiated, it will be provided input for two strings -- these are the names of the competitors. This can be via command line arguments, user input functions, etc.

After that, the scoreboard will recieve input via STDIN. These correspond to events that the scoreboard should reflect in the score.

  • 0

    The first player has scored a point.

  • 1

    The second player has scored a point.

  • U

    Undo the previous point and revert to the previous state of the scoreboard.

The scoreboard must handle games, deuces, etc. as described in the next section.

Terse Description of Tennis Scoring System

This section here describes the exact rule set to use.

A match is between two players. To win a match, a player must win three sets. To win a set, a player must win at least six games and have a two-game lead over their opponent. To win a game, a player must win at least four points and have a two-point lead over their opponent.

The number of sets and games won are displayed as is. Points are displayed as follows in order of priority:

  • 1 point = 15
  • 2 points = 30
  • 3 points = 40
  • Number of points won are equal to the opponent = 40
  • Number of points won are one greater than the opponent = Ad

Tiebreaks are optional. Implementing tiebreaks grants you -40 to your score.

Scoreboard Format

During the first set and first game:

Name | x
Name | x

where x is the point display for each player.

During the first set:

Name a | x
Name a | x

where a is the number of games won by each player.

During the second set:

Name b a | x
Name b a | x

where b is the result of the first set.

During the third set:

Name c b a | x
Name c b a | x

where c is the result of the second set.

etc. for fourth and fifth sets.

Example:

Federer 5 6 6 3 2 | 0
Murray  7 4 4 6 2 | 15
\$\endgroup\$
  • \$\begingroup\$ A bit of a far stretch, but it would be cool if you could point the programs at URL which gave the scores for an actual tennis match \$\endgroup\$ – Beta Decay Jul 27 '15 at 8:04
0
\$\begingroup\$

Punch buggy?

As some of you might know, "punch buggy" is a children's(?) game that involves spotting Volkswagen Beetles and punishing other players. For reference, the car on the left is a punch buggy, while the car on the right is not:

punch-buggy-yellownot-punch-buggy

Your task is: given an image, determine whether there is a punch buggy shown in it. Entries will be scored by percent correct among all n (TBD) test images. If there is a tie, it will be broken by run time on my computer (specs will be posted on main).

Test images may contain just about anything, and come in various sizes. Most will be automobiles of various types, but I will make sure they have a maximum of one auto in them (so if you see a non-matching car, you don't need to look for more). I won't use toy cars or heavily modified cars to try to fool you. Images will be pulled from Google Image Search, and will be of varying quality (from ad-quality to candid in-the-yard).

This is not a Kolmogorov complexity challenge. The point is not to recognize specific image files, but to recognize a Beetle in any picture. If it looks like someone is cheating this, I will change to a different test set and re-score.

Spec

Input is the name of an image file in JPG or PNG format (should I restrict this to one?).

Output is Punch Buggy! if a punch buggy is present in the picture, and any other non-empty string if not.

Programs are run once per image. I will write a simple test controller for this using STDIO, so programs must be runnable from the command line, using a language that is freely available on Ubuntu.

You are allowed to read/write other files, but only in a folder with the relative path /yourProgramName. You are allowed to read files whose names are passed as input via STDIN.

Test Images

(will include link to collection when posted, probably about 100 total)

Sandbox

Yes, this seems a bit difficult to me, too. I don't see that as a problem. Is there anything that isn't clear about the task or spec? Other notes/questions/suggestions?

If it needs fluff (I'm not sure yet), it will probably be something like "help my robot become more human via children's games".

\$\endgroup\$
  • \$\begingroup\$ Personally, I don't think this is that hard. You just look for a large grouping of yellow pixels around the centre of the image. I think you should limit it to a PNG. \$\endgroup\$ – Beta Decay Jul 29 '15 at 13:21
  • 1
    \$\begingroup\$ @BetaDecay That would only work if all punch buggies are yellow and all other images/cars are not. The images shown here are only representative samples. The test cases will include various cars of various colors at various angles in various lighting conditions. \$\endgroup\$ – Geobits Jul 29 '15 at 13:27
  • \$\begingroup\$ Ohh I thought Punch Buggy was when you have a yellow car, not just a Beetle \$\endgroup\$ – Beta Decay Jul 29 '15 at 13:30
  • \$\begingroup\$ Ah. That's the Yellow Car Game. Similar, but yea, that would be a different difficulty level. \$\endgroup\$ – Geobits Jul 29 '15 at 13:32
  • 3
    \$\begingroup\$ I afraid even if you people try to recognize buggies their results will come from randomness and overlearning on the provided images. Recognizing a car at all would be a difficult task itself. \$\endgroup\$ – randomra Jul 30 '15 at 11:49
  • 1
    \$\begingroup\$ If you want to avoid this being a kolmorogov challenge, would it help to provide a much larger training set and test on a small subset of this that is not announced in advance? That does introduce a deadline excluding future submissions though. \$\endgroup\$ – trichoplax Aug 1 '15 at 18:30
  • \$\begingroup\$ @trichoplax Not necessarily, because you could always test the new submissions using the subset (which is still unannounced) \$\endgroup\$ – Beta Decay Aug 5 '15 at 11:48
  • \$\begingroup\$ @BetaDecay good point. That makes this sort of challenge seem much more promising. \$\endgroup\$ – trichoplax Aug 5 '15 at 12:27
  • \$\begingroup\$ @trichoplax Though it could still be a kolmogorov complexity because a program could be programmed to recognise all pictures in the album, and choosing a subset wouldn't stop that program from getting full marks \$\endgroup\$ – Beta Decay Aug 5 '15 at 12:37
0
\$\begingroup\$

Question about symmetry in ascii grid (temp title)

Synopsis: Given a grid of ASCII characters, determine if, and in what ways, the grid is symmetrical.

Some characters are symmetrical to others. For example:

  • d is symmetrical vertically to b
  • W is symmetrical horizontally to M
  • O is symmetrical both ways to O
  • ! is symmetrical horizontally to i (takes some imagination!)
  • ^ is symmetrical horizontally to v
  • b is rotationally symmetrical 180 degrees to q (that is, if you rotate the first character 180 degrees, you get the second character)
  • (space) is symmetrical vertically, horizontally, and rotationally to

In this challenge, there are only three types of symmetry that need to be considered: vertical, horizontal, and rotational by 180 degrees. You can find a full list of which characters are considered symmetrical at the bottom of this post.

If we arrange some characters into an n by m rectangle (where n and m are both even integers), then the rectangle may be symmetrical. Here is an example:

M^^^^MM^^M
OOOOOOOOOO
OOOOOOOOOO
WvvvvWWvvW

It is symmetrical horizontally.

Here's another example.

dddbbb
dddbbb
dddbbb
ddOObb

It is symmetrical vertically.

Here's one more example:

++++++
+p++q+
++++++
++++++
+b++d+
++++++

This one has three ways it is symmetrical -- horizontally, vertically, and rotationally.

Write a program which will, when given a rectangle of characters as input, output the number of ways that rectangle is symmetrical. For the three inputs I've shown above, the outputs would be 1, 1, and 3 respectively.

[Todo: list of characters]

Sandbox Questions

  1. One thing I've been considering is allowing entrants to access the list of which characters are symmetrical (in some sort of CSV format) in a file. This would mean that entrants wouldn't have to encode the symmetries themselves. On one hand, this probably saves some frustration at having to code in all the possible symmetries. On the other, this reduces the complexity of the challenge as the aspect of encoding the symmetries with minimal characters is removed. I'd like your thoughts on this.
\$\endgroup\$
  • \$\begingroup\$ Yet more symmetries: all of []{}() are vertically symmetric to themselves. | belongs in "Both". lower-case c belongs in vertical. Maybe also lower-case a depending on the font your going by (apparently not the one used on SE). Likewise t might belong in horizontal symmetry. We also forgot about digits: 08 both ways, 3 vertical. \$\endgroup\$ – Martin Ender Sep 1 '14 at 11:58
  • \$\begingroup\$ What do you think about adding rotational symmetry (by 180 degrees) to the mix? \$\endgroup\$ – Martin Ender Sep 1 '14 at 11:59
  • \$\begingroup\$ ​​​​​​​​​​​​​Like 6 and 9? I think rotational symmetry would do well as a seperate question actually. \$\endgroup\$ – absinthe Sep 1 '14 at 12:08
  • \$\begingroup\$ Yes, like 6 and 9. If a new question for that is based on the same concept, it would probably be too similar to not be a duplicate (at least the solution I have in mind would be rather easily adapted to do rotational symmetry, I think). Adding it here, might open some possibilities for interesting compression/golfing. \$\endgroup\$ – Martin Ender Sep 1 '14 at 12:11
  • \$\begingroup\$ You've convinced me. I'll edit in the rotational part when I have time. \$\endgroup\$ – absinthe Sep 1 '14 at 12:14
  • \$\begingroup\$ Since there will probably be combinations of all three symmetries on different characters, I'd recommend only having one list for each symmetry (with some pairs in multiple lists). Here are the rotational pairs I can think of: d/p, b/q, (/), [/], {/}, </>, %/%, ///, \/\, ,/,, S/S, s/s, z/z, Z/Z, W/M, !/i, ^/v, $/$, as well as all those which are symmetric both ways to themselves. \$\endgroup\$ – Martin Ender Sep 1 '14 at 12:22
  • \$\begingroup\$ Some of the characters are not visible (at least on my screen) so would benefit from being followed by a description. I think they are just spaces but markdown appears to fail to display them even in backticks. \$\endgroup\$ – trichoplax Sep 1 '14 at 14:09
  • 1
    \$\begingroup\$ Displaying a single space in an inline code tag has to be done with an actual <code> tag rather than with backticks. codegolf.stackexchange.com/questions/5194/… is a good starting point for rotational symmetries. Some digits also have linear symmetries. \$\endgroup\$ – Peter Taylor Sep 1 '14 at 14:39
  • \$\begingroup\$ Would you also consider J and L as symmetrical (also requires a little imagination...)? \$\endgroup\$ – WallyWest Sep 2 '14 at 22:41
0
\$\begingroup\$

Clarence the Fast? Typist

(Inspired by this excellent question on the original challenge.)

Introduction

Lawrence is a business manager who works at an Internet service provider. Recently, he has noticed that Clarence, the data entry clerk, has been typing a little slow lately. Since Clarence's job is entering the IP addresses manually into the database, Lawrence is starting to get worried. Especially that there is now a backlog of angry customers who are calling to ask why they are not connected to the Internet yet.

Lawrence, as you might expect from one who manages an ISP, has hit upon what he considers to be an excellent solution to the problem. He decides to optimise the layout of Clarence's keypad to make it faster for him to type in the IP addresses.

Clarence's keypad is normally laid out as follows:

123
456
789
.0E (E stands for "Enter")

The distance between the centres of each adjacent key is 1 centimetre. Clarence types using the "eagle search" system -- he uses one finger only and moves that finger from key to key to type in an address. For example, to input the number 7851, Clarence would start his finger on 7, move 1cm right to 8, move 1cm up to 5, then move √2cm to 1 -- a total of 3.41cm.

If we rearrange his keypad like this, we can get better results:

423
156
789
.0E

With this layout Clarence only needs to move his finger 3cm. This saves time!

Your task is to write a program that determines the most optimal keypad layout, given a list of IP addresses that Clarence must type in. Clarence needs to push the E after each IP address, so you also need to optimise the position of the E key.

Input Description

Input is a newline separated list of IP addresses. Each IP address is a string that will be in the form

().().().()

where each () is an integer in the range 0 - 999. I would also like to point out that addresses such as 0.42.42.42 or 999.999.999.999 in the input are still valid, despite the fact that they are invalid IP addresses. So you don't need to include any IP address verification code in your program.

Output Description

Output the layout of the keys such that the distance Clarence needs to move his finger to type them all in is as low as possible. If there are multiple layouts that are equally as low, output any one of them.

The format for the output looks like this:

123
456
789
.0E

[todo: example inputs and outputs]

\$\endgroup\$
  • 1
    \$\begingroup\$ Lose the intentional confusion of the names. The point of a specification is to be easily understood, not deliberately confusing. \$\endgroup\$ – Peter Taylor Aug 5 '15 at 10:51
  • \$\begingroup\$ I don't think it affects the challenge in any way, but 999.999.999.999 makes my eyes bleed. \$\endgroup\$ – Dennis Aug 8 '15 at 5:01
0
\$\begingroup\$

Is a picture worth a thousand words?

There is an old saying that goes "A picture is worth a thousand words". For us programmers, pictures and words are actually quantifiable in bytes. (A word is worth 8 bytes on a standard 64-bit system, a thousand words is worth 8000 bytes, and an image is worth the number of bytes needed to store it in the particular format it is in.)

Write a program or function that, given the path of an image as input, determines if it is or is not worth a thousand words. Print worth it if it is, and not worth it if it is not.

This is a challenge, so the shortest answer wins!

Problems:

Too simple, maybe have the programs perform a check on the environment to determine actual word length?

No test cases (Yet)

Question is sort of short

\$\endgroup\$
  • \$\begingroup\$ I love the title, but I'd agree the challenge is too simple. This is just os.path.getsize in Python, for instance. I'd suggest playing off the 'thousand words' part of the challenge more. \$\endgroup\$ – absinthe Aug 11 '15 at 22:30
  • \$\begingroup\$ @Pyrrha how would you suggest playing off of the 'thousand words' part? A thousand literal english words? Maybe have the program convert an image into words and words into images (Obviously not accurately, e.g. 'Blue' will not give a blue image, 'Blue' is just a symbol. 1000 symbols represent the image by dictionary lookup, or something. \$\endgroup\$ – rodolphito Aug 12 '15 at 2:29
  • \$\begingroup\$ If you have a good idea feel free to take over the challenge :) \$\endgroup\$ – rodolphito Aug 12 '15 at 2:30
  • 1
    \$\begingroup\$ Alternative: Find 1000 English words (i.e. letter sequences) in the image file’s source code. \$\endgroup\$ – Crissov Aug 12 '15 at 11:19
0
\$\begingroup\$

Write an Adblocker!

Introduction

You've gotten tired of reading text ads dispersed throughout your content. You've tried solving this problem using a simple find-and-replace solution, but the advertisers have wisened up! Every text ad now comes in slightly different variations to slip past your filter.

Challenge

Write an adblocker that, given a sample ad, removes all variations of it from the content. Your program must remove every sentence in the input for which 75% of its words are identical, and in the same location.

This is codegolf, shortest answer in bytes wins!

Example

Given an example sentence from an advertisement, such as

Buy my computer now with cheap free shipping.


Buy my laptop today with cheap free shipping.

is an ad because 6 out of 8 words (>= 75%) are identical and in the same locations.


The computer was expensive but shipping was free.

is not an ad because 0 out of 8 words (< 75%) are identical and in the same location. Note how computer, shipping, and free don't count as identical because they are in different positions in the sentence.

If a sentence is not the same length as the ad, it isn't an ad.

Bonus

After matching an ad, remember which words were used as replacements, and use them to match future ads.

For example, when Buy my laptop today with cheap free shipping. was matched to the given sample Buy my computer now with cheap free shipping., your program should remember that laptop and today are synonyms for computer and now, respectively.

If laptop or today are ever encountered in a future sentence, they should be matched with their synonyms in the ad.

Your program only needs to match synonyms in content that appears after the synonym was found.

So, if the sentence Purchase my laptop today with cheap free shipping. was encountered after your program found out about the aforementioned synonyms, it would match because 7 out of 8 words matched in the same location (>= 75%). Note that a program that doesn't claim the bonus would only match 5 out of 8 words (< 75%), and would not consider the sentence an ad.

Your program should then proceed to make note that Purchase is a synonym for Buy, and continue processing the content.

Programs claiming this bonus can claim a 35% reduction of their score, i.e. score_with_bonus = number_of_bytes * 0.65.

Input

Accept one sentence as a sample advertisement followed by a number of sentences of content. Only letters of the alphabet, spaces, and periods will appear in the input.

Input may be taken in any convenient format for your language. For example, accepting a string for the ad sentence and an array of strings for the content is acceptable.

Output

Output the content without the ad variations. The content must be in the same order.

The output may come in any reasonable format for your language. For example, printing to a file or stdout is acceptable. If your language makes it easier to output an array like ["Content 1", "Content 2", ...], or in a similar such format, this is acceptable.

Test Cases

Input

Two for one deal on lumber for a limited time only.

Make sure to pace yourself well when you run long distances.
You don't want to tire too quickly.
Three for one deal on tires for a limited time only.
Training is a must.
Two for one deal on lumber for a limited time only.
Three for one deal on tires for a short period only.

Output (with bonus)

Make sure to pace yourself well when you run long distances.
You don't want to tire too quickly.
Training is a must.

Output (no bonus)

Make sure to pace yourself well when you run long distances.
You don't want to tire too quickly.
Training is a must.
Three for one deal on tires for a short period only.

Notes

You may write a program or function.

More test cases to come!

This is my first challenge, so please give suggestions on how to improve!

In particular, comments on whether or not the bonus is appropriate would be appreciated. Also, it would be nice to know thoughts concerning the challenge as a whole (good, bad, too easy, too hard...?), so that I can better frame future ideas! Thanks!

\$\endgroup\$
  • \$\begingroup\$ So the input won't have any newlines? That is, the content will be a series of one or more sentences just separated by a period and a space? Could I write a function that accepts the ad as one parameter and the content as another? \$\endgroup\$ – Alex A. Aug 14 '15 at 4:07
  • \$\begingroup\$ You many accept the input in any reasonable format. (So yes, @AlexA., that would be fine) \$\endgroup\$ – jrich Aug 14 '15 at 4:07
  • \$\begingroup\$ But what about So buy my computer now, cheap with shipping? That's just 1 out of 8, when in reality it should be 7 out of 8... \$\endgroup\$ – Beta Decay Aug 14 '15 at 7:33
  • \$\begingroup\$ You mention that commas may be included in the input, but you don't say how they affect the matching. \$\endgroup\$ – Peter Taylor Aug 14 '15 at 7:43
  • \$\begingroup\$ @BetaDecay For the purposes of the challenge, we assume that the advertisers do not get more sophisticated than a simple replacement of words, not an addition, subtraction, or rearrangement of words. Obviously this wouldn't be a very effective adblocker, but I thought it would make for a reasonable challenge. \$\endgroup\$ – jrich Aug 14 '15 at 13:32
  • \$\begingroup\$ @PeterTaylor Commas may be ignored in the input. Periods only matter for separating sentences. For matching purposes, only letters of the alphabet matter. \$\endgroup\$ – jrich Aug 14 '15 at 13:33
  • \$\begingroup\$ If commas can be ignored, you might as well remove them entirely from the spec. ',- (in CJam) isn't really where the interest lies. \$\endgroup\$ – Peter Taylor Aug 14 '15 at 15:09
  • \$\begingroup\$ @PeterTaylor You're right, commas aren't where the interest lies. I'll remove them from the challenge. \$\endgroup\$ – jrich Aug 14 '15 at 15:35
0
\$\begingroup\$

Kolmorogov image complexity


The 512 by 512 pixel image below [ to be added when posting to main ] was produced using a combination of simple methods that, if known, would allow reproducing the image with a short program. It is therefore known to have low Kolmorogov complexity. However, the original methods used will not be revealed. Instead your challenge is to produce code that outputs this image by your own best method, pixel perfect, so that the hash of your image matches the hash of this image.

Blank image to show size 512 by 512 pixels

[ Hash ]

You may use any built ins and libraries that existed publicly before the challenge was posted, including graphical libraries.

Input and output

Input

  • Your code is not required to take input.
  • Your code must be able to produce the correct output without taking input.

Output

You may use any freely available image format (free and free) or display the image to screen. Your code is not responsible for converting the image to a format that can be hashed for validation.

Winning

A valid answer is one for which the output passes the validation test. The winner is the valid answer with the shortest code in bytes.

Validator

The following code takes a PNG image as input and outputs a hash of its pixel values, announcing whether this is valid.

[ Validator to be added later ]


Sandbox questions

  • I'm considering posting a few example images here in the sandbox so people can feedback on which one would make the best candidate for posting to main. Is this acceptable if I keep the time between posting example images and posting to main reasonably short (a day or two)?

  • Would it be better to approach this from the opposite direction and say the winner is the closest to the target image in 300 bytes? I think it can work as a question with insisting on an exact match though - I'm aiming to have several aspects to be golfed down, so even if not all are golfed well the total length should still be manageable. I prefer an exact match and open ended code length, as a byte limit has very different effects on different languages.

  • Is there any general advice on what to remember/avoid when preparing the target image? Obviously this cannot be very specific advice as the exact method will not be discussed before posting to main. However, I welcome any hints at things that would make for a good challenge and things that would be trivial or too difficult. I'm definitely going to follow Peter Taylor's advice and avoid any crypto or Mandelbrot zooms. The image should be fairly easy to identify, so the emphasis can be on golfing down the components rather than solving a mystery.

  • Would it be better to say "the original method will never be revealed" or "the original method will be revealed once an answer is posted that is shorter than it" or "the original method will be revealed after a set time period"? The last one is my least favourite. I like the idea of a challenge being open ended, so I would prefer to reveal at most only what is already beaten by existing answers.

  • I like the idea of using patterns that will be recognisable so people can say "I know that pattern from somewhere" and then look it up and tweak the parameters, rather than just presenting a random looking image that happens to have a simple description. Does this sound like an interesting challenge?

\$\endgroup\$
  • 1
    \$\begingroup\$ This basically looks like a single-robber cops-and-robbers. In particular, the by now well-known issues around use of crypto in robbers should be taken into account. Guess-the-Mandlebrot-parameters is also likely to be a waste of time. \$\endgroup\$ – Peter Taylor Aug 10 '15 at 18:43
  • \$\begingroup\$ Related: codegolf.stackexchange.com/questions/24909/kolmogorov-mania . This got very mixed votes at first. Note the edit made with the clue. I say pick an image and try it. Don't say the oiginal method will never be revealed, just give more hints until someone gets it. \$\endgroup\$ – Level River St Aug 17 '15 at 14:12
  • \$\begingroup\$ @steveverrill I definitely don't want something as obscured as that - I want the pattern to be perfectly visible so it's more about golfing than guessing. I like the idea of gradual hints, but if I get mine how I'm aiming to, it won't need hints, just golfing. \$\endgroup\$ – trichoplax Aug 17 '15 at 17:15
0
\$\begingroup\$

SETI (search for extraterrestrial life)

In this code golf challenge you will search for signs of life.

Specification:

Your program takes a sequence of exactly 225 characters, each either 0 or 1. You return as output a single bit, either 0 or 1.

The goal is to distinguish between two kinds of inputs:

0 (no extraterrestrial life): Each character is zero or one independently at random, and is one with probability exactly 15%.

1 (extraterrestrial life): First, each character is zero or one independently at random, and is one with probability exactly 28%. Then, 10 rounds of the original Conway's Game of Life are played from this configuration. The 225 characters are viewed as a 15 by 15 grid, and when we apply the rules, we treat the grid as wrapping around so that it has no borders. That is, column 1 wraps around and is adjacent to column 15, and row 1 also wraps around and is adjacent to row 15. The symbol '0' is associated with 'dead' and the symbol '1' is associated with alive. After the 10 rounds the string corresponding to the state of the game is the input.

Your program does not need to give any particular output for any particular input, however it should succeed on average in the following sense. If we flip a fair coin (either 0 or 1), and choose an input from the corresponding distribution, your program should output the correct answer with probability at least 90%.

Otherwise this is code golf as usual. Enjoy!

I/O:

Your program shall accept as input a sequence of 225 characters, each either 0 or 1. You may request in your answer that the characters are space-delimited, comma-delimited, or not delimited. You may request in your answer that the input is given on standard in, or, if your answer is a program which takes command-line arguments, you may assume that the characters are passed on the command-line so that each character is an argument (assuming your shell supports passing 225 arguments to a program), or, if your language supports the concept of "global variables / values", you may write your program under the assumption that a known global variable, of the simplest "character sequence" type that your language supports, contains the input.

Your answer shall output a single bit either zero or one. You shall do this either by printing the character 0 or 1 to standard out, or by returning an integer value 0 or 1 from a designated "main" function.

\$\endgroup\$
  • \$\begingroup\$ This question is going to need a fair number of test cases, soo that people can tell if their program works. Maybe a test case generator? \$\endgroup\$ – isaacg Aug 19 '15 at 14:01
  • \$\begingroup\$ I guess I assumed people would just write their own test case generator in their language of choice. I wrote one here in C++, that's what I used to pick the parameters hastebin.com/uguhapepat.avrasm \$\endgroup\$ – Chris Beck Aug 19 '15 at 14:04
  • \$\begingroup\$ added a license statement hastebin.com/sevimunolu.avrasm \$\endgroup\$ – Chris Beck Aug 19 '15 at 14:14
  • \$\begingroup\$ 8 rounds or 10 rounds? \$\endgroup\$ – Peter Taylor Aug 19 '15 at 16:19
  • \$\begingroup\$ Humm you know i'm open to suggestions, but I originally had 8 and then I made the board smaller and increased it to 10, I guess I left an 8 in there though. i'm going to edit to make it 10 everywhere \$\endgroup\$ – Chris Beck Aug 19 '15 at 16:20
  • \$\begingroup\$ So my goals for setting the parameters were like: (1) I thought there should still be some significant amount of noise in the life game, it shouldn't have enough time to entirely settle down into squares and flippers (2) I want you to have to do something more complex than "just count the number of 1's". If the same percentage is used for the random ones in both the "yes" and "no" instances, it leads to a large gap in density of ones because life tends to kill off many of the 1s after you start from random. so i made the board small and tuned the %s so that counting ones gives little info. \$\endgroup\$ – Chris Beck Aug 19 '15 at 16:27
0
\$\begingroup\$

Infinite monkeys and a broken keyboard

The infinite monkey theorem describes the probability of getting the desired result by just doing random stuff.

The task of this challenge is to calculate the minimum number of monkeys you need to get a given text on a broken keyboard. The situation is easy:

  • You have a keyboard (QWERTY-layout) that has lost some of its keys
  • Possible keys are: 1234567890abcdefghijklmnopqrstuvwxyz -=\[];',./
  • Only one button is pressed at a time and the other keys (enter, tab, numeric keypad, ...) will not be pressed/ are already lost
  • You have many many many monkeys which want to type on the keyboard!

Input

The input is a string which can only contain the possible chars. You may assume that only the characters that are in the given string aren't lost.

Task

You have to calculate how many monkeys are at least necessary to get the given input with a probability of over 50%. Afterwards just output that number.

Examples

input: aaaa
    1 key available -> P=100% to hit the right key
output: 1

input: abcd
    4 keys available -> P=25% to hit the right key
    Probability to get the desired string:
    P = 25%^4 = 0.00390625
    Number n of monkeys needed:
    (1-0.00390625)^n < 50%
    n = 178 (P=50.176%)
output: 178

Please tell me if you have ideas how to improve or clarify the question or how to optimize it.

\$\endgroup\$
  • \$\begingroup\$ Similar, but I think this is a better question than mine \$\endgroup\$ – Beta Decay Aug 20 '15 at 17:58
0
\$\begingroup\$

(Possible deadlines?)

The robber and the bank (Bank managers)

(Based off 'Two makes all the difference')

A group of robbers has decided to break into a bank, but one of the members leaked the information to the bank. To stop the robbers from getting any money, they have decided to change the combination on each vault to something more complicated.

Your task

As you are a bank manager, you must figure out a new combination of rotations for the wheel lock system of the vaults. The vaults take 7 turns each, represented in degrees. You must write a program that takes 10 integers (separated in any way you like) and outputs the processed integers which have been made from the originals. This is important, as you cannot use a randomizing function to make the new combination.

Sample input:

(Note: The numbers will all be multiples of 5. The output should also be this way.)

10, 50, -230, 110, 20, -5, 50, 80, 30, -50

Sample output:

30, 110, -110, 230, 50, 115, 110, 170, 70, 70

This result is obtained by the simple (Python 3) algorithm (deliberately non-golfed)

inputlist = input('list')
for i in len(inputlist):
    if inputlist(i) > 0:
        inputlist(i) *= 2
        inputlist(i) += 10
    else:
        inputlist(i) += 120

(Note the abscence of a condition for 0 degrees, as a wheel lock would not take such a value. Also note the fact that the algorithm is a full program, not just a function that would do the same.)

Winning conditions

The shortest uncracked algorithm wins. In case there are two algorithms that have the same length and are uncracked, the one with more votes will win.

The robber and the bank (Robbers)

Your group of robbers are breaking into a bank! However, one of your members seems to have leaked the information to the bank managers. Your team manages to hack the bank's system to retrieve the original password and part of the algorithm, but your connection was cut.

Your task

You will receive 10 integers and a snippet of code (need help deciding how much) from the algorithm used to change the lock's combination. You will need to deduce what the algorithm is and finally the new combination.

Sample information:

10, 50, -230, 110, 20, -5, 50, 80, 30, -50
Part of code

Sample answer:

30, 110, -110, 230, 50, 115, 110, 170, 70, 70
Code (optional)

Winning conditions

The robber with the most vaults (algorithms/combinations) cracked wins. In the case that there are two robbers with the same number of cracked vaults, the robber with more votes will win.

(Any way to separate who wants to be a robber and who wants to be a manager? Perhaps a separate system for answering?)

\$\endgroup\$
  • \$\begingroup\$ 1. It's quite confusing the way you keep talking about algorithms when you mean programs. 2. It's not at all clear what exactly the bank managers post. 3. It's not at all clear that the robbers can do anything except guess. \$\endgroup\$ – Peter Taylor Aug 24 '15 at 17:04
0
\$\begingroup\$

Buffalo buffalo buffallo buffalo buffallo buffallo buffallo parse buffalo buffalo buffallo buffalo buffallo buffallo buffallo

Write a program that can take a integer input N > 0 and then describes the syntax of a phrase in the style of "Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo" with N repetitions.

The wikipedia page has the parse tree and accepted syntax for phrases up to N = 8.

The sentence is unpunctuated and uses three different readings of the word "buffalo". In order of their first use, these are:

  • a. the city of Buffalo, New York, United States, which is used as a noun adjunct in the sentence and is followed by the animal;
  • n. the noun buffalo, an animal, in the plural (equivalent to "buffaloes" or "buffalos"), in order to avoid articles;
  • v. the verb "buffalo" meaning to outwit, confuse, deceive, or intimidate.

So for the first eight the output should be:

  1. Bully (meaning the imperative "[you] Buffalo!" - command someone to bully).
  2. NY bison (meaning a bison that hails from the town of Buffalo).
  3. NY bison bully (a bison from NY bullies).
  4. NY bison bully bison (NY Bison bully a bison)
  5. NY bison bully NY bison (NY bison bully NY bison)
  6. Buffalo buffalo buffallo buffalo buffallo buffallo (NY bison bully (TBC)
  7. Buffalo buffalo buffallo buffalo buffallo buffallo
  8. Buffalo buffalo buffallo buffalo buffallo buffallo buffallo

In the comments section, wikipedian Robin Johnson has it for 9 through 12 (NY stands for Buffalo, NY):

  1. (NY bison [which] bison bully) bully (bison [which] NY bison bully)
  2. (Bison) bully (NY bison [which] NY bison (NY bison bully) bully)
  3. (NY Bison) bully (NY bison [which] NY bison ([which] NY bison bully) bully)
  4. (bison [which] bison ([which] NY bison bully) bully) bully (NY bison [which] NY bison bully)

He added parenthesis for more phrase visibility, but that is not needed.

Your program should take the input and explain the gramatically correct phrase doing the following substitutions:

  • NY for the Buffalo, NY city.
  • Bison for the animal Buffalo.
  • Bully for the verb.

[code-golf] [kolmogorov-complexity]

\$\endgroup\$
  • \$\begingroup\$ Are we allowed to use NLTK? \$\endgroup\$ – Beta Decay Aug 27 '15 at 10:55
  • \$\begingroup\$ The name is a little obnoxious to be honest. I would recommend removing at least a few "buffalos" from either side of "parse." \$\endgroup\$ – Alex A. Sep 4 '15 at 17:42
  • \$\begingroup\$ @AlexA. that is a good suggestion, and I think the title as is is gramatically wrong too. \$\endgroup\$ – Mindwin Sep 4 '15 at 23:48
0
\$\begingroup\$

Get home by ONLY turning right

You're finally trying to get a drivers license. About halfway during the lesson, the instructor decides that you've sufficiently mastered telling the gas- and brake pedal apart. It's time to practice the next thing: turning right.

The challenge

Your program is provided an ASCII roadmap, with your starting position, direction and home marked. You should drive home in the minimum distance required.

Your program must output route instructions for reaching your destination. The following instructions must be printed by your program whenever appropriate.

Input

Items on the map will look like this. There are only horizontal and vertical roads. (I'm open for suggestions on this one.)

  • = – A horizontal road
  • | – A vertical road
  • # – A crossroad
  • > / < / ^ / v – A one-way street
  • H – Your home
  • N / E / S / W – Your starting point and direction (North, East etc. The map is oriented north-up.)

A road segment (a signle character) is connected to another segment when:

  1. It ends at an adjacent segment that has the same alignment. E.g.: == or
    |
    |
  2. It ends at a segment with a different alignment (horizontal vs vertical). E.g.: =|, |=,
    =
    |
    or
    |
    =
  3. It ends at a crossroad. E.g.:
     |
    =#=
     |
  4. It ends at a roundabout. E.g.:
 |
=O
 |

It is not connected in (for example) these instances:

  • |
     |
  • ||
  • | =

Moving one position up, down, left and right all count as traveling the same distance.

Output

  • Turn right
  • Go straight on
  • Take the {1st/2nd/3rd} exit (at a roundabout)

You take roundabouts clockwise. Because of this, taking any exit amounts to turning right.

Rules

  • Each instruction must be on its own line.
  • No other output is permitted.
  • Your program may take no longer than a minute to run on an average home user’s computer.

Standard loopholes are forbidden, unless specified otherwise.

This is code golf. The shortest answer wins.


This is an early draft. Input is welcome, especially on the feasibility of requiring the shortest possible route, if this should be code golf, how input should be generated (randomly but the same for all programs? A few predefined maps?) and any improvements for the challenge. Any constructive feedback is welcome, even if it's just about spelling and grammar errors.

\$\endgroup\$
  • \$\begingroup\$ Very related challenge \$\endgroup\$ – Sp3000 Aug 27 '15 at 11:50
  • \$\begingroup\$ @Sp3000 Not a duplicate though. \$\endgroup\$ – user2428118 Aug 27 '15 at 15:24
  • \$\begingroup\$ How are the roundabout exits numbered? \$\endgroup\$ – ASCIIThenANSI Aug 27 '15 at 17:51
  • \$\begingroup\$ @ASCIIThenANSI I've updated the text to say you take roundabouts clockwise. I hope it's sufficiently clear now. \$\endgroup\$ – user2428118 Aug 27 '15 at 18:33
0
\$\begingroup\$

Arranging Matrices

(doesn't actually require any matrix math)

While doing homework on matrix multiplication, I realized that I could avoid rewriting all of the matrices by arranging them intelligently on the page. If the problems were:

A * B = C
A * D = E
F * D = G

I could arrange the matrices like so:

 BD
ACE
 FG

This arrangement satisfies the requirement that each product (C E G) have the correct factors in the correct directions. For example, the A * D = E so E is to the right of A and below D.

The challenge is, given a list of multiplication problems (in the same format as above), output an arrangement of them that involves the fewest letters (the above solution has 7, the minimum).

\$\endgroup\$
  • \$\begingroup\$ Needs a test case for an input which has conflicts. The easiest one would probably be A * B = C B * A = D. \$\endgroup\$ – Peter Taylor Sep 1 '15 at 10:31
  • 1
    \$\begingroup\$ You might want to first explain how for a single matrix multiplication you usually arrange the matrices to do the computation. I don't think everyone is familiar with the technique this challenge is based on. \$\endgroup\$ – Martin Ender Sep 1 '15 at 11:09
0
\$\begingroup\$

Hello everyone! I've been lurking around for a couple of weeks now and I think this site is super interesting!

I've decided that I definitely want to contribute to this site as well and have composed a new challenge over the last few days, that I hope you'll find interesting too!
I've tried to do all the reading beforehand and hope that I've got everything right and that this kind of thing hasn't been done before.
Please let me know if you think something needs to be changed!

Anyways, here is my proposed challenge:


Programs With Taste

[probably will add some "flavor text" here]

The Task:

Write a program that takes an arbitrary group of pictures and ranks them after this program's "preference."

What that means is, you should come up with an algorithm that favors some attributes in pictures over others by comparing them in a specific way.

This is a popularity-contest, so what I want to see is interesting and creative methods of "pseudo-subjectively" ranking images.

As an example, one program could favor an overall more colorful image over a mostly gray one, or another could have a "favorite" color and ranks pictures which have it more, higher than others. You could even come up with an elaborate scoring system that combines a couple of criteria.

Details:

As input your program should accept any amount of images, which can be of any size.
It doesn't matter if your program requires them to be in a specific file format.

The output should be a ranked list from "favorite" image to "least favorite", with items that unmistakably represent each of the pictures (e.g. a list of file names or a list of the images itself).
If you want, you can also include the actual numbers (or score) that are compared in the output.

The program should definitely be deterministic, so that the same group of pictures will always result in the same order.

If you're entering, please also provide a short description of what your algorithm prefers in a picture and how it's calculated.

As a bonus task I think it would also be really interesting to see what "the perfect picture" for your algorithm would be, meaning that this image would theoretically always be ranked the highest by your program.

Example images:

Here are some groups of images you can use as examples:

[I'll create and/or find some images to put here]

You can download them all in a .zip here.

Good luck!

\$\endgroup\$
  • \$\begingroup\$ Whats stopping me from writing my program so that it prefers pictures with a filename closer to 0 in the ascii table (sorting)? \$\endgroup\$ – Blue Sep 3 '15 at 16:46
  • 1
    \$\begingroup\$ @muddyfish Nothing, really. I wouldn't expect it to do well in a popularity contest, though. It's not a golf, so the length of the program isn't really a concern. \$\endgroup\$ – Geobits Sep 3 '15 at 16:50
  • 1
    \$\begingroup\$ This is definitely "Too Broad". \$\endgroup\$ – Peter Taylor Sep 4 '15 at 13:54
  • \$\begingroup\$ @PeterTaylor Could you please elaborate? I don't really know much what you classify as broad on this site, but personally, I don't think it is, or at least not "definitely." I gave a specific and clear goal - to sort a set of images - while leaving enough freedom in the actual implementation to allow some creative submissions for an interesting popularity-contest. What do you think needs to be narrowed down? \$\endgroup\$ – Xrott Sep 4 '15 at 23:21
  • \$\begingroup\$ In essence your challenge is "Write any function you want from int[] to double". That isn't specific. I'm not sure that it can be narrowed down sufficiently without becoming a completely different question (e.g. a classifier which distinguishes representational vs abstract art with a reasonable degree of accuracy - and classification questions have their own problems). \$\endgroup\$ – Peter Taylor Sep 5 '15 at 8:12
0
\$\begingroup\$

Alternating Hamiltonian Chess Boards


Overview

Find a Hamiltonian cycle on a chess board that alternates between black and white squares. The catch is that the board does not have the colours arranged in the conventional way.


Detail

Consider a chess board, with each square having 4 neighbours (up, down, left, right), apart from the edge and corner squares which only have 3 or 2 neighbours respectively. A Hamiltonian cycle is a closed path (loop) that visits every square exactly once, moving from neighbour to neighbour (never diagonally).

On a chess board, it is easy to find a Hamiltonian cycle that alternates between black and white squares (in fact, any cycle will alternate between black and white squares). What if the black and white squares were not arranged so conveniently? Clearly there are arrangements for which there is no possible alternating Hamiltonian cycle, for example putting all the white squares in one half of the board.

The task of your code is to find any valid cycle, or indicate if there are none.

Input & output

Input

An 8 by 8 board of black and white squares.

This is in the form of a string of 64 characters each of which is either "0" or "1", terminated by a newline. This indicates the colours of the squares in English reading order.

Output

Any valid cycle if one exists, or a zero as an indication that no valid cycle exists.

A cycle is represented by a comma separated list of integers from 0 to 63 inclusive, indicating the order in which the squares are visited. Again the labelling is in English reading order.

Whether a list of a zero, the output is terminated with a newline.

Square numbering

The squares are labelled in English reading order (left to right then top to bottom). So for example, a 3 by 3 board would be labelled as follows:

0 1 2
3 4 5
6 7 8

Sandbox questions

  • Is this equivalent to another question already asked?
  • My first thought was , but I'm now preferring . There are a number of quick checks that can eliminate the possibility of there being a valid cycle, which will be competitive in fastest code. I'd rather see these than golfed brute force approaches.
  • I've chosen 8 by 8 simply because it's a familiar size due to chess. Would this be better with a different size board? For fastest code I'd want the time taken to be over a minute for at least some inputs, so that there is enough time to judge the difference between answers. Ideally for fastest code I'd choose inputs that take quite a bit longer than that to allow for solutions which are far more efficient than I expect.
  • How restrictive should I be with the input and output formats? For fastest code if the body of the problem takes a reasonably long time then input and output conversion should be negligible so I could insist on a single format for ease of measuring answers.
  • Is there any advantage to having a fixed board size, or would it be more interesting with the board size as an initial input N, followed by the board?
\$\endgroup\$
  • 1
    \$\begingroup\$ i think "fastest code" is most interesting b/c with code golf its just going to boil down to who can write the shortest exhaustive guess & check program. for fastest code I guess probably that there is some efficient algorithm for hamilton cycles on bipartite graphs? but i'm not actually sure, probably there would be alot of tricks to solve this quickly, and maybe exploit planarity somehow. \$\endgroup\$ – Chris Beck Aug 22 '15 at 17:55
  • \$\begingroup\$ @ChrisBeck the more I think about it the more I'm leaning towards fastest code too. In which case I'll include unsolvable boards in the input cases too. That will really separate the brute force solutions from those that have clever ways to fail fast. \$\endgroup\$ – trichoplax Aug 22 '15 at 18:05
  • \$\begingroup\$ @ChrisBeck and trichoplax - I'm intrigued but skeptical. Checking for Hamiltonian cycles is NP-Complete. If we think of the input as a graph with vertices representing the white squares and edges representing the black squares, this easily translates into many algorithms that ask about Hamiltonian paths. Presuming an even split between white and black squares, this results in a maximum of 32! different possible paths to brute force check, or, in the best Monte Carlo simulations, O(1.657^32). That's still 17+ minutes if your algorithm can check 10,000 possible paths per second. \$\endgroup\$ – AdmBorkBork Aug 27 '15 at 15:39
  • \$\begingroup\$ It might not be NP-complete when restricted to graphs like this though. I'm not sure, my hunch is no, maybe you see a reduction though? Regardless I'm quite sure that it will be at most like, exponential in the number of rows here, not like exponential in the number of grid squares. (Because, it can be translated to a SAT instance of bounded tree-width and there are known algorithms for those.) Making the graph bipartite is often a pretty severe restriction that dramatically reduces the complexity as well. \$\endgroup\$ – Chris Beck Aug 27 '15 at 15:47
  • \$\begingroup\$ @ChrisBeck Hence why I said I'm intrigued but skeptical. I haven't gone through anything rigorous - the "white squares as nodes and black squares as edges" was just something immediate that sprang to mind. It's certainly possible that there are enough restrictions on the input that can dramatically reduce complexity -- at the least, think of my ruminations as quantifying a maxima. \$\endgroup\$ – AdmBorkBork Aug 27 '15 at 15:55
  • \$\begingroup\$ @TimmyD If 17 minutes is the worst case brute force then I'll probably increase the size of the board. There are several methods of spotting certain classes of unsolvable boards almost instantly so I'm hoping for solutions that exit very early where possible, and are also optimised with a good heuristic for spotting the solutions that do exist. \$\endgroup\$ – trichoplax Aug 27 '15 at 18:46
  • \$\begingroup\$ I definitely want to give this plenty of thought before settling on a board size (or maximum test size if I settle on having board size as an input). \$\endgroup\$ – trichoplax Aug 27 '15 at 18:54
  • \$\begingroup\$ @TimmyD I'm interested in your O(1.657^32). Does that assume anything about the number of neighbours per square? \$\endgroup\$ – trichoplax Aug 27 '15 at 18:55
  • \$\begingroup\$ @TimmyD I'm fairly sure this case is simpler than the 32! you describe, as each black square has a maximum of 4 white squares to choose from, and some have less otherwise finding a cycle becomes trivial. \$\endgroup\$ – trichoplax Aug 27 '15 at 19:01
  • \$\begingroup\$ Brute-force checking an n-node graph for a Hamiltonian cycle is O(n!) - that's just straight math, regardless of any bounds on edge connectivity. Way too big to try. "Simple" algorithms exist to check in O(2^n) time, and have been known for years. I've not read the paper showing O(1.657^n) time, so I can't comment specifically, but I would imagine that the author tackles the general case, since they explicitly call out bipartite graphs as being solvable in O(1.414^n) ... I think that's the current best-case. My "17-minute" remark was for the O(1.657^n) time. \$\endgroup\$ – AdmBorkBork Aug 27 '15 at 19:28
  • \$\begingroup\$ That all said, I do believe that there are ways to shrink that O(1.657^32) time, given the constraints present (i.e., each vertex will have a maximum of 4 edges). I'd have to spend some more time thinking about this than I have to determine for sure. Additionally, all this is assuming that my mapping of "white squares as vertices, black squares as edges" is optimal, which I'm much too humble to think is the case, so there could be different ways of optimizing that, too. \$\endgroup\$ – AdmBorkBork Aug 27 '15 at 19:40
  • \$\begingroup\$ Related, in a general sense. Might be worthwhile to watch what happens with that one, just to see reaction and responses. \$\endgroup\$ – AdmBorkBork Aug 28 '15 at 20:49
  • \$\begingroup\$ @TimmyD Thanks - it will be interesting to see if the answers there turn out to be convertible to answers here. \$\endgroup\$ – trichoplax Aug 29 '15 at 16:03
  • 1
    \$\begingroup\$ I know that this is ancient history now, but I'm fairly positive you can't construct a Hamiltonian path if the squares aren't checkered. Simple proof: Assuming a standard checkerboard, and that you start on black, there's no way to get to another black without taking 2N steps, and white without taking 2N-1 steps. If you swap a black with a white, then you will never be able to step on the black square on a 2N step. \$\endgroup\$ – Nathan Merrill Mar 21 '16 at 2:29
  • \$\begingroup\$ @NathanMerrill thanks for the proof. It does seem that this challenge will only be possible if I allow diagonal steps in the path too. I should have started by making some test cases. I have some more thinking to do... \$\endgroup\$ – trichoplax Mar 23 '16 at 14:42
0
\$\begingroup\$

Oh dear, bad CSS! or How to Properly Format CSS™

Please give me any improvements/suggestions you may think of.

The goal is to write a short function to Properly Format CSS™; you must Properly Convert Spaces To Tabs™ and format the CSS nicely.

Bad CSS™

div> *
{
  padding: 10px;
     margin: 1em;
    -webkit-border-radius: 10px 2px 100%; border-radius:10px 2px 100%;
       border: 2px solid yellow;margin: 1rem;
-moz-border-radius:10px 2px 100%}

Proper CSS™

div > * {
--->border: 2px solid yellow;
--->-webkit-border-radius: 10px 2px 100%;
--->   -moz-border-radius: 10px 2px 100%;
--->        border-radius: 10px 2px 100%;
--->margin: 1em;
--->margin: 1rem;
--->padding: 10px;
}

A tab is represented by --->, as you can't embed tabs properly on StackExchange.

All the properties are sorted alphabetically, and nicely formatted (please also note that the order of the properties can be important, such as in the case of margin: 1em; ... margin: 1rem;. The selector is also nicely formatted.

Format

  • Format the selector with spaces around every token
  • A space; a left curly brace ({); a newline
  • One tab; optional spaces (see below); the property name; a colon; a space; the tokens, separated by single spaces how do I define token? (replace 0{unit} with 0); a semi-colon; a new line
  • A newline; a right curly brace (})

Property sorting

Sort the properties alphabetically, ignoring prefixes. Then list each prefix for the property specified in the original CSS, starting with the longest, down to the shortest (i.e., none), adding spaces before the property name to pad the shorter prefixes to the longest prefix.

The same property may appear more than once; keep each variant in the original order, as in the example.

Rules

  1. You may not use any built-in CSS parsers and/or formatters.
  2. Standard loopholes are disallowed.

Bonuses

  1. -100 bonus if the function can also format psuedo-classes and elements properly (e.g. p >a::before to p > a::before and p>a:visited to p > a:visited).
  2. -50 bonus if you change :after and :before to the new, two-colon syntax (::after and ::before).

The task is to provide a function to format (correct) some CSS (provided as a parameter) as specified above, not a fully-featured CSS parser – but you get a -1000 bonus if the code is a fully-featured, forwards-compatible CSS3 parser! :)

Input: function parameter or STDIN.
Output: function return value or STDOUT.
No output to STDERR.

\$\endgroup\$
0
\$\begingroup\$

With Rhyme and Reason

A budding poet (you) knows not his rhymes

Lines of code he can write deftly and quick

And those of prose he can write mostly fine

But the poems he creates make him sick

Through study of verse throughout all forms known

Our dear programmer shall learn the right way

But alas, all of his lyrical tomes

Would have him reading until he was gray

At once a brilliant epiphany struck

Thought he, "A program is just what I need!

It will look for me and rake through the muck

Songs and poems of all kinds it shall read

And give to me solely their rhyming scheme

With which I can write that of which I dream"


Your Task

Given an input, you are to output its rhyme scheme.

Rules

  1. You are to only compare the last words in each line when looking for rhymes. These will be referred to as "rhyme words."
  2. For each stanza (lines separated by single line breaks -- think something like a paragraph), you are to assign the first rhyme word the letter "A." If the next one rhymes with any other preceding rhyme word, it shall be assigned the letter of said word (in this case, "A"), and if not, the next letter in the alphabet (in this case, "B"). Once you reach two or more line breaks in a row, you treat whatever follows as separate stanza.
  3. You can code it in so that when you get past the letter "Z," your program wraps around and assigns rhyme words again to "A," but you should not expect that there will be that many rhymes in the stanzas provided. If your program errors instead, that is admissible.
  4. Sight rhymes do not count (you must find some sort of way to compare the words phonetically)
  5. Standard loopholes apply

Input

The input will be in the form of a file, unless your language cannot read files, in which case it will be through STDIN. It will consist of at least one stanza of written text.

Output

Your output will be either written to a file or the console (whichever is easier to read). Your output will consist of letters corresponding to the rhyme scheme as discussed in rule 2; you choose how they are formatted, but please format them in a readable fashion (especially for large inputs).

Scoring

Your score will be the amount of rhymes correctly identified over the total as a percentage. For example, if your program returns ABCA DDEE when the actual was ABBA CCDD, your score would be 3/4, or 75%, because it got AA, CC, and DD, but not BB.

I do not expect scores near 100%, due to the difficulty of this challenge, so if your score is low, don't worry about it.

Here is a link to my implementation of a scorer in Python.


Test Cases

Input: (Sonnets from the Portuguese #43)

How do I love thee? Let me count the ways.
I love thee to the depth and breadth and height
My soul can reach, when feeling out of sight
For the ends of Being and ideal Grace.
I love thee to the level of everyday's
Most quiet need, by sun and candle-light.
I love thee freely, as men strive for Right;
I love thee purely, as they turn from Praise.
I love thee with a passion put to use
In my old griefs, and with my childhood's faith.
I love thee with a love I seemed to lose
With my lost saints, --- I love thee with the breath,
Smiles, tears, of all my life! --- and, if God choose,
I shall but love thee better after death.

Output:

ABBA ABBA CDC DCD

Input:

A budding poet (you) knows not his rhymes
Lines of code he can write deftly and quick
And those of prose he can write mostly fine
But the poems he creates make him sick
Through study of verse throughout all forms known
Our dear programmer shall learn the right way
But alas, all of his lyrical tomes
Would have him reading until he was gray

At once a brilliant epiphany struck
Thought he, "A program is just what I need!
It will look for me and rake through the muck
Songs and poems of all kinds it shall read
And give to me solely their rhyming scheme
With which I can write that of which I dream"

Output:

ABAB CDCD 
ABAB CC

Input:

cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow
cow

Output:

Error.

or

ABCDEFGHIJKLMNOPQRSTUVWXYZA

What I'm looking for help with

  1. How can I figure out a way of easily scoring answers (this seems to be a programming puzzle in and of itself)? Maybe check to see if the characters used match I've made a scorer in Python, but I'm not 100% sure yet that it is completely accurate.
  2. Is this challenge too difficult; should I restrict it to only a certain few test cases?
  3. Regarding test cases, I plan on making a large one for purposes of scoring - how many lines of rhymes would be good?
  4. Would this maybe do better as a partially code golf challenge (factor in length with scoring) with the goal being to be able to give the scheme as accurately as possible for only a few test cases (although I believe that would make this come close to being a duplicate)?
  5. Anything else at all that you notice
\$\endgroup\$
  • 1
    \$\begingroup\$ IMO "you must find some sort of way to compare the words phonetically" is too broad. You should provide a clear specification of how words should be compared. I suggest requiring the use of CMUDICT (and allowing it to be preprocessed to remove comments and then read from a file named d), and specifying that words rhyme iff their phonetics as given in CMUDICT agree perfectly from the most stressed vowel to the end. And have test cases which cover words with more than one pronunciation in CMUDICT. \$\endgroup\$ – Peter Taylor Sep 21 '15 at 9:36
  • \$\begingroup\$ @PeterTaylor I think you're right, I'll look into CMUDICT, but judging from your comment it ought to be fine. If I allow it, I think I will then factor in length in the score. Thanks for the reply! \$\endgroup\$ – cole Sep 21 '15 at 15:05
0
\$\begingroup\$

Format the code

Given some source code in a C-like language, format (prettify) it using the following rules:

  • remove all leading/trailing whitespace on each line
  • collapse consecutive empty lines into one empty line
  • if the first line is empty, remove it; same with the last line
  • split lines after each occurrence of a semicolon (;) or left curly bracket ({); if it's the last character on the line, leave it as it is
  • split lines at each right curly bracket (}), so that the bracket is on a line by itself
  • remove all leading/trailing whitespace (if any) that appeared after splitting
  • if a left curly bracket is alone on a line, move it to the end of the previous non-empty line, preceded by one space; any preceding empty line should be removed
  • each line gets an indentation level: the initial level is 0, and is incremented after each left curly bracket and decremented before each right curly bracket; prefix each non-empty line with a number of tab characters given by its indentation level

The input consists of ASCII characters with codes 9, 10 and 32-126. The first non-whitespace character in the input is not a curly bracket. All curly brackets are balanced correctly. You don't need to do any special handling for strings, characters or comments. The output should end in exactly 1 newline character.

TODO: add examples, restrictions and more details
Oh, and it's

\$\endgroup\$
  • \$\begingroup\$ You might want to add a special case for for statements, because splitting for (init; test; inc) over three lines with the same indentation is rather idiosyncratic and hard to read. (I would also prefer special cases for semicolons and brackets in character and string literals). \$\endgroup\$ – Peter Taylor Sep 21 '15 at 9:05
  • \$\begingroup\$ @PeterTaylor oh, I hadn't thought about for statements, that's a good point. At the same time, I don't want to make the challenge too complicated/difficult. I'm considering removing the semicolon rule, but I'm not completely opposed to your suggestions (I'm just not convinced it's better that way) \$\endgroup\$ – aditsu Sep 21 '15 at 9:20
0
\$\begingroup\$

It's a small world!

A challenge inspired by small world networks. It is said that in such a network, starting at any point, you are able to reach any other node of the network in a specific amount of hops.

Your task will be determining the smallest number of hops necessary to reach any other node (maximum short-path length, aka graph diameter) and the average number of hops for the same purpose.

Input

Your program will recieve on its stdin some amount of lines, with space-separated numbers on it.

Line number N will list the line numbers of the nodes node N is connected to. Every node is linked mutually, there are no unidirectional eges.

2 3
1 4
1
2

Each line can be assumed to be sorted.

Output

Your program must compute the smallest number of hops necessary to depart from one node and land on any different node, and the average number of hops to traverse any node. Print it to stdout in any format desired. The average path length must be a decimal with at least 2 digits of precision.

The average path length is defined (for the purposes of this challenge) as the sum of the smallest number of hops between any 2 points divided by the amount of edges in the network (direct connections) plus the biggest short-path. The sum-of-short-paths includes the edges themselves (e.g. paths to neighbouring nodes), but not reversed paths (A to B and B to A).

sum(short_paths)/(edges+long)

Example

The network represented in this image:

visual representation of network

Will be input to your program as:

2 4
1 3 5
2 4
1 3
2

And the program must output something in the form of:

3
2.0

The average was calculated in this manner:

p12 = 1; p13 = 2; p14 = 1; p15 = 2; p23 = 1; p24 = 2; p25 = 1; p34 = 1; p35 = 2; p45=3
e = 5
A = sum(p) / (e+p45)
(5+8+3)/(5+3)

Rules

Basic rules, avoid standard loopholes


I can see an issue with the "average" part of the challenge, since it is ill-defined and I consider this challenge quite extensive without it already.

\$\endgroup\$
  • 1
    \$\begingroup\$ It took me awhile to understand your notation for the graphs. Maybe something along the lines of “line no. n lists the nodes node n is connected to” would be clearer. \$\endgroup\$ – xebtl Sep 23 '15 at 6:28
  • \$\begingroup\$ I'm also unsure if the calculation of the average should be part of the challenge, mainly because I defined it arbitrarily, and because the challenge should already be long enough without it. \$\endgroup\$ – Kroltan Sep 23 '15 at 12:40
  • 1
    \$\begingroup\$ The average path length is well defined provided that you specify that the graphs will be connected. The other parameter is more of a problem: you call it "maximum path length", but that sounds like the longest path, and what you seem to be describing is the graph diameter. We've had a couple of longest path questions already; we haven't had graph diameter or average path length, although arguably they're trivial variations on all-sources shortest path. I'm not sure offhand whether that's been done, or just single-source. \$\endgroup\$ – Peter Taylor Sep 23 '15 at 13:36
0
\$\begingroup\$

Find Your Stack Exchange Spirit Pokemon

It's a popular game on the internet to take some numbers related to someone (usually their birthday/age), multiply them, and divide until you get a number between 1 and 720. That number is the Pokedex number of your "spirit Pokemon".

We're going to play the same game, but since this is Stack Exchange, we'll be using our user IDs. And since this is PPCG, we'll be writing a program to tell us what our Stack Exchange-based spirit Pokemon is.

To find it, take any user, then multiply their user ID by the number of letters in their name. Take that number mod 720, then add 1 (so 0 will become 1 and 719 will become 720). That's the Pokedex number of their spirit Pokemon.

Input

A valid user ID greater than 0, and a valid name, in this format:
<ID> <name>

The site does not matter, and it won't be given.

You may accept input from either the command-line or STDIN (or your language's closest equivalent.)

Output

The name of the user's spirit Pokemon (as determined above.)

Additional Files

Since there's no way you can cram 720 names into one program, you'll be given a file with the names of all the Pokemon (in order). Here it is:

Bulbasaur
Ivysaur
Venusaur
Charmander
Charmeleon
Charizard
Squirtle
Wartortle
Blastoise
Caterpie
Metapod
Butterfree
Weedle
Kakuna
Beedrill
Pidgey
Pidgeotto
Pidgeot
Rattata
Raticate
Spearow
Fearow
Ekans
Arbok
Pikachu
Raichu
Sandshrew
Sandslash
Nidoran♀
Nidorina
Nidoqueen
Nidoran♂
Nidorino
Nidoking
Clefairy
Clefable
Vulpix
Ninetales
Jigglypuff
Wigglytuff
Zubat
Golbat
Oddish
Gloom
Vileplume
Paras
Parasect
Venonat
Venomoth
Diglett
Dugtrio
Meowth
Persian
Psyduck
Golduck
Mankey
Primeape
Growlithe
Arcanine
Poliwag
Poliwhirl
Poliwrath
Abra
Kadabra
Alakazam
Machop
Machoke
Machamp
Bellsprout
Weepinbell
Victreebel
Tentacool
Tentacruel
Geodude
Graveler
Golem
Ponyta
Rapidash
Slowpoke
Slowbro
Magnemite
Magneton
Farfetch'd
Doduo
Dodrio
Seel
Dewgong
Grimer
Muk
Shellder
Cloyster
Gastly
Haunter
Gengar
Onix
Drowzee
Hypno
Krabby
Kingler
Voltorb
Electrode
Exeggcute
Exeggutor
Cubone
Marowak
Hitmonlee
Hitmonchan
Lickitung
Koffing
Weezing
Rhyhorn
Rhydon
Chansey
Tangela
Kangaskhan
Horsea
Seadra
Goldeen
Seaking
Staryu
Starmie
Mr. Mime
Scyther
Jynx
Electabuzz
Magmar
Pinsir
Tauros
Magikarp
Gyarados
Lapras
Ditto
Eevee
Vaporeon
Jolteon
Flareon
Porygon
Omanyte
Omastar
Kabuto
Kabutops
Aerodactyl
Snorlax
Articuno
Zapdos
Moltres
Dratini
Dragonair
Dragonite
Mewtwo
Mew
Chikorita
Bayleef
Meganium
Cyndaquil
Quilava
Typhlosion
Totodile
Croconaw
Feraligatr
Sentret
Furret
Hoothoot
Noctowl
Ledyba
Ledian
Spinarak
Ariados
Crobat
Chinchou
Lanturn
Pichu
Cleffa
Igglybuff
Togepi
Togetic
Natu
Xatu
Mareep
Flaaffy
Ampharos
Bellossom
Marill
Azumarill
Sudowoodo
Politoed
Hoppip
Skiploom
Jumpluff
Aipom
Sunkern
Sunflora
Yanma
Wooper
Quagsire
Espeon
Umbreon
Murkrow
Slowking
Misdreavus
Unown
Wobbuffet
Girafarig
Pineco
Forretress
Dunsparce
Gligar
Steelix
Snubbull
Granbull
Qwilfish
Scizor
Shuckle
Heracross
Sneasel
Teddiursa
Ursaring
Slugma
Magcargo
Swinub
Piloswine
Corsola
Remoraid
Octillery
Delibird
Mantine
Skarmory
Houndour
Houndoom
Kingdra
Phanpy
Donphan
Porygon2
Stantler
Smeargle
Tyrogue
Hitmontop
Smoochum
Elekid
Magby
Miltank
Blissey
Raikou
Entei
Suicune
Larvitar
Pupitar
Tyranitar
Lugia
Ho-oh
Celebi
Treecko
Grovyle
Sceptile
Torchic
Combusken
Blaziken
Mudkip
Marshtomp
Swampert
Poochyena
Mightyena
Zigzagoon
Linoone
Wurmple
Silcoon
Beautifly
Cascoon
Dustox
Lotad
Lombre
Ludicolo
Seedot
Nuzleaf
Shiftry
Taillow
Swellow
Wingull
Pelipper
Ralts
Kirlia
Gardevoir
Surskit
Masquerain
Shroomish
Breloom
Slakoth
Vigoroth
Slaking
Nincada
Ninjask
Shedinja
Whismur
Loudred
Exploud
Makuhita
Hariyama
Azurill
Nosepass
Skitty
Delcatty
Sableye
Mawile
Aron
Lairon
Aggron
Meditite
Medicham
Electrike
Manectric
Plusle
Minun
Volbeat
Illumise
Roselia
Gulpin
Swalot
Carvanha
Sharpedo
Wailmer
Wailord
Numel
Camerupt
Torkoal
Spoink
Grumpig
Spinda
Trapinch
Vibrava
Flygon
Cacnea
Cacturne
Swablu
Altaria
Zangoose
Seviper
Lunatone
Solrock
Barboach
Whiscash
Corphish
Crawdaunt
Baltoy
Claydol
Lileep
Cradily
Anorith
Armaldo
Feebas
Milotic
Castform
Kecleon
Shuppet
Banette
Duskull
Dusclops
Tropius
Chimecho
Absol
Wynaut
Snorunt
Glalie
Spheal
Sealeo
Walrein
Clamperl
Huntail
Gorebyss
Relicanth
Luvdisc
Bagon
Shelgon
Salamence
Beldum
Metang
Metagross
Regirock
Regice
Registeel
Latias
Latios
Kyogre
Groudon
Rayquaza
Jirachi
Deoxys
Turtwig
Grotle
Torterra
Chimchar
Monferno
Infernape
Piplup
Prinplup
Empoleon
Starly
Staravia
Staraptor
Bidoof
Bibarel
Kricketot
Kricketune
Shinx
Luxio
Luxray
Budew
Roserade
Cranidos
Rampardos
Shieldon
Bastiodon
Burmy
Wormadam
Mothim
Combee
Vespiquen
Pachirisu
Buizel
Floatzel
Cherubi
Cherrim
Shellos
Gastrodon
Ambipom
Drifloon
Drifblim
Buneary
Lopunny
Mismagius
Honchkrow
Glameow
Purugly
Chingling
Stunky
Skuntank
Bronzor
Bronzong
Bonsly
Mime Jr.
Happiny
Chatot
Spiritomb
Gible
Gabite
Garchomp
Munchlax
Riolu
Lucario
Hippopotas
Hippowdon
Skorupi
Drapion
Croagunk
Toxicroak
Carnivine
Finneon
Lumineon
Mantyke
Snover
Abomasnow
Weavile
Magnezone
Lickilicky
Rhyperior
Tangrowth
Electivire
Magmortar
Togekiss
Yanmega
Leafeon
Glaceon
Gliscor
Mamoswine
Porygon-Z
Gallade
Probopass
Dusknoir
Froslass
Rotom
Uxie
Mesprit
Azelf
Dialga
Palkia
Heatran
Regigigas
Giratina
Cresselia
Phione
Manaphy
Darkrai
Shaymin
Arceus
Victini
Snivy
Servine
Serperior
Tepig
Pignite
Emboar
Oshawott
Dewott
Samurott
Patrat
Watchog
Lillipup
Herdier
Stoutland
Purrloin
Liepard
Pansage
Simisage
Pansear
Simisear
Panpour
Simipour
Munna
Musharna
Pidove
Tranquill
Unfezant
Blitzle
Zebstrika
Roggenrola
Boldore
Gigalith
Woobat
Swoobat
Drilbur
Excadrill
Audino
Timburr
Gurdurr
Conkeldurr
Tympole
Palpitoad
Seismitoad
Throh
Sawk
Sewaddle
Swadloon
Leavanny
Venipede
Whirlipede
Scolipede
Cottonee
Whimsicott
Petilil
Lilligant
Basculin
Sandile
Krokorok
Krookodile
Darumaka
Darmanitan
Maractus
Dwebble
Crustle
Scraggy
Scrafty
Sigilyph
Yamask
Cofagrigus
Tirtouga
Carracosta
Archen
Archeops
Trubbish
Garbodor
Zorua
Zoroark
Minccino
Cinccino
Gothita
Gothorita
Gothitelle
Solosis
Duosion
Reuniclus
Ducklett
Swanna
Vanillite
Vanillish
Vanilluxe
Deerling
Sawsbuck
Emolga
Karrablast
Escavalier
Foongus
Amoonguss
Frillish
Jellicent
Alomomola
Joltik
Galvantula
Ferroseed
Ferrothorn
Klink
Klang
Klinklang
Tynamo
Eelektrik
Eelektross
Elgyem
Beheeyem
Litwick
Lampent
Chandelure
Axew
Fraxure
Haxorus
Cubchoo
Beartic
Cryogonal
Shelmet
Accelgor
Stunfisk
Mienfoo
Mienshao
Druddigon
Golett
Golurk
Pawniard
Bisharp
Bouffalant
Rufflet
Braviary
Vullaby
Mandibuzz
Heatmor
Durant
Deino
Zweilous
Hydreigon
Larvesta
Volcarona
Cobalion
Terrakion
Virizion
Tornadus
Thundurus
Reshiram
Zekrom
Landorus
Kyurem
Keldeo
Meloetta
Genesect
Chespin
Quilladin
Chesnaught
Fennekin
Braixen
Delphox
Froakie
Frogadier
Greninja
Bunnelby
Diggersby
Fletchling
Fletchinder
Talonflame
Scatterbug
Spewpa
Vivillon
Litleo
Pyroar
Flabebe
Floette
Florges
Skiddo
Gogoat
Pancham
Pangoro
Furfrou
Espurr
Meowstic
Honedge
Doublade
Aegislash
Spritzee
Aromatisse
Swirlix
Slurpuff
Inkay
Malamar
Binacle
Barbaracle
Skrelp
Dragalge
Clauncher
Clawitzer
Helioptile
Heliolisk
Tyrunt
Tyrantrum
Amaura
Aurorus
Sylveon
Hawlucha
Dedenne
Carbink
Goomy
Sliggoo
Goodra
Klefki
Phantump
Trevenant
Pumpkaboo
Gourgeist
Bergmite
Avalugg
Noibat
Noivern
Xerneas
Yveltal
Zygarde
Diancie
Hoopa

Rules

  • The file containing all the Pokemon must be saved as "pokemonlist".
  • You may not open any files other than "pokemonlist".
  • The program must output the name of the Pokemon, not just the number.
  • Your program must work for any valid Stack Exhange user name and ID.

Bonuses

  • -50 points if you return "MissingNo." if the input -1 Community is entered.

Meta Questions

  • Are the rules clear?
  • Is the formula enough of a challenge?
  • I had a problem with the previous formula being too easy, so I've changed it. However, I'm not sure whether the problem was in the formula or the challenge itself. Will this challenge work, or is it too easy regardless of what formula I use?
\$\endgroup\$
  • \$\begingroup\$ I sincerely object to any formula where I end up a Palpitoad. \$\endgroup\$ – Geobits Sep 22 '15 at 18:50
  • 7
    \$\begingroup\$ On-topic: This is really just "print line X%720+1 from this file", right? \$\endgroup\$ – Geobits Sep 22 '15 at 18:52
  • \$\begingroup\$ @Geobits Yes. I'll probably have to rework the formula so it's not that simple. \$\endgroup\$ – ASCIIThenANSI Sep 22 '15 at 18:58
0
\$\begingroup\$

Prove Your Language's Turing Completeness

The goal is to show whether your language is or isn't Turing complete with the shortest program possible. This is different than "interpret BF" questions, since that's only one way to show the completeness of a language.

This question will maintain one for each programming language (using a snippet), so the goal is to have either the shortest Turing machine, or the shortest proof that your language isn't Turing complete.

Good luck with Malboge.

This is probably a weak question so far, and so it needs your suggestions!

  • Also, I'm not really sure how it'd work for non-Turing complete languages...
\$\endgroup\$
  • 1
    \$\begingroup\$ Also, are there any languages whose Turing completeness is undecidable? \$\endgroup\$ – mbomb007 Sep 24 '15 at 18:07
  • \$\begingroup\$ What do you mean by "the shortest Turing machine"? Are you planning to write a spec for an input format which describes the TM (according to a specified commonly-used definition) and its starting tape? \$\endgroup\$ – Peter Taylor Sep 25 '15 at 11:07
  • \$\begingroup\$ @PeterTaylor Not really. I could use some help with the wording. I really just want the user to show the Turing completeness of their language, which could involve implementing Rule 110, or interpreting BF, or several other things. Or are you saying a need a more specific definition of what it means to be Turing complete? \$\endgroup\$ – mbomb007 Sep 25 '15 at 16:46
  • \$\begingroup\$ I did actually start writing a comment asking what assumptions we could make about other systems being Turing complete, and then I saw that you talked specifically about having "the shortest Turing machine" and I rewrote the comment. If you generalise it then it becomes even more difficult: a proof that my language can implement all mu-recursive functions is really going to be a set of snippets showing how to handle each case, not a program. I think the approach which would cause least arguments would be to ask for implementations of a specific universal TM, and forget the non-TC langs. \$\endgroup\$ – Peter Taylor Sep 25 '15 at 21:35
  • \$\begingroup\$ @PeterTaylor Do you know of any good ones that haven't been done? Conway's Game of Life, Rule 110, Cyclic Tag System, Lambda Calculus, and BF have all been done. I was really hoping for a generic, "implement a TC" code-golf... \$\endgroup\$ – mbomb007 Sep 25 '15 at 21:53
  • \$\begingroup\$ I see the confusion: you're using "Turing machine" to mean "Turing-powerful system", whereas I was interpreting it to mean machines made of a tape and a finite state machine. sciencedirect.com/science/article/pii/S0304397596000771 includes the UTM which was used to prove that Magic: the Gathering is TC (2 states, 18 symbols): it seems as good as any for your purpose. \$\endgroup\$ – Peter Taylor Sep 26 '15 at 6:10
0
\$\begingroup\$

Hello, Loophole Abuse!

Assignment

Print the following string:

Hello, World!

Gimmick

you know the meta post "Loopholes that are forbidden by default"? Yeah, those don't apply here. In fact, you're actively encouraged to use as many as possible and combine them in weird ways. the more you use in a way that other users like, the more chance people will vote for you.

In addition, to prevent trivial answers getting all the glory, your program must also work in the event that the characters that make up the source code are reversed (this includes the separate characters of a string). This includes external sources, multi-character compiler and execution flags, file names and anything else that is essential for the execution of the software (like Metagolfscript IDs).

Scoring

This is .

\$\endgroup\$
  • 2
    \$\begingroup\$ See this comment thread \$\endgroup\$ – Peter Taylor Sep 26 '15 at 21:13
  • \$\begingroup\$ @PeterTaylor If we can figure out a way to make the subjective part, i.e. determining which loopholes are broken, more objective, would that fix the question? \$\endgroup\$ – Nzall Sep 26 '15 at 21:34
  • \$\begingroup\$ Relevant chat discussion: chat.stackexchange.com/transcript/message/24349167#24349167 \$\endgroup\$ – Nzall Sep 26 '15 at 21:47
  • 3
    \$\begingroup\$ To be perfectly honest, I think it's such a pointless idea that I don't want to spend much time thinking about hypothetical changes. \$\endgroup\$ – Peter Taylor Sep 27 '15 at 6:14
  • \$\begingroup\$ Characters reversed means reading the program from last to first character? \$\endgroup\$ – Paŭlo Ebermann Oct 11 '15 at 8:27
  • \$\begingroup\$ @PaŭloEbermann Yes. So that means that, for example, closing brackets will come before opening brackets, \$\endgroup\$ – Nzall Oct 11 '15 at 10:02
0
\$\begingroup\$

PPCG New Question Generator

Specification

Write a program that does the following, given a string s and an integer n (as a file, STDIN, or command line arguments):

  1. Determines the n most used characters in that quote. If there are two characters that are equally used, the character with the lower ASCII value takes priority.
  2. Returns the text and the character in the following format:

    Return the following text:
    
    >{string}
    
    But there's an ORIGINAL TWIST! You cannot use the characters {characters} in your answer. As this is code-golf, the answer with the least characters wins. Have fun!
    

Specifics:

  1. You need to display {string} in blockquotes using Markdown formatting, not HTML. So if the string spans multiple lines, you need to prepend each line with >.
  2. You also need to display {characters} using proper grammar and in order from most used to least used. For example, with "a", "b", and "c":

    You cannot use the characters "a", "b", or "c" in your answer.

Example

In this example, n is 4, and s is:

I have loved flowers that fade, 
Within whose magic tents 
Rich hues have marriage made 
With sweet unmemoried scents: 
A honeymoon delight,
A joy of love at sight, 
That ages in an hour
My song be like a flower!

The output is:

Return the following text:

>I have loved flowers that fade, 
>Within whose magic tents 
>Rich hues have marriage made 
>With sweet unmemoried scents: 
>A honeymoon delight,
>A joy of love at sight, 
>That ages in an hour
>My song be like a flower!

But there's an ORIGINAL TWIST! You cannot use the characters "e", "a", "h", or "o" in your answer. As this is code-golf, the answer with the least characters wins. Have fun!
\$\endgroup\$
0
\$\begingroup\$

Remove Pieces from Chess Position Notation

You should write a program or function which receives a string representing a chess position as input and outputs or returns the position with only the pawns and kings left.

The positions in the input and output are described by FEN notation:

Each rank is described, starting with rank 8 and ending with rank 1; within each rank, the contents of each square are described from file "a" through file "h". Each piece is identified by a single letter taken from the standard English names (pawn = "P", knight = "N", bishop = "B", rook = "R", queen = "Q" and king = "K").[1] White pieces are designated using upper-case letters ("PNBRQK") while black pieces use lowercase ("pnbrqk"). Empty squares are noted using digits 1 through 8 (the number of empty squares), and "/" separates ranks. (taken from Wikipedia)

For example

rnbqkbnr/pp1ppppp/8/2p5/4P3/2N5/PPPP1PPP/R1BQKBNR

describes the board

---------------
♜♞♝♛♚♝♞♜
♟♟  ♟♟♟♟♟

    ♟
        ♙
    ♘
♙♙♙♙  ♙♙♙
♖  ♗♕♔♗♘♖
---------------

With everything except kings and pawns removed it becomes

---------------
       ♚
♟♟  ♟♟♟♟♟

     ♟
       ♙

♙♙♙♙ ♙♙♙
       ♔
---------------

and expressed with the FEN string

4k3/pp1ppppp/8/2p5/4P3/8/PPPP1PPP/4K3    

Input

  • A FEN string consisting of the characters 12345678PNBRQKpnbrqk/.
  • The input describes a valid chess game position.

Output

  • A FEN string describing the position with knights, bishops, rooks, queens removed.
  • Output might not be a valid chess position in some extreme cases.

Examples

TODO

This is code golf so the shortest entry wins.

\$\endgroup\$
0
\$\begingroup\$

Pareto optimality challenge

Write a class that maintains a pareto optimal set. This class must have these three methods:

k(int n): Constructs the class. N is the array size that all of the other methods must use.

boolean k.p(int[] n): Adds n if there exists no entry m in k such that each single term of m is greater than each corresponding term in n. The method must also return true if n has been entered into k, or false otherwise. n can be assumed to be of the length specified by the constructor.

boolean k.s(int[] n): Returns true if n was previously entered by the above method and there exists no other term m in k such that each term of m is greater than each corresponding entry in n. Returns false otherwise.

This is code golf, so shortest entry wins. Yes, programming languages without classes may be used, but all the usual properties of classes must be satisfied by the three methods above.

\$\endgroup\$
0
\$\begingroup\$

ASCII Snake

NOTES

It was pointed out to me that we already have had at least 2 snake challenges before. However, seeing as they are from a couple years ago, I think another snake challenge would be nice. Below (from the description section to the end) I describe a "classic" snake challenge.

However, I want to differentiate this from the classic challenge. I am more than open to suggestions in the comments below. My idea is the following:

Make an "infinite" snake game. That is, every 10 points, the level changes and the snake is reset according to the following pattern:

--The nth level contains n obstacles in the form of the '#' character. These work the same as walls. They are randomly placed around the map, the difficulty is that they cannot create a situation where an ungettable 'x' exists. for example:

------------------------------
| #                          |  11
|                            |
|              oooooo        |
|              o    o        |
|              o    v        |
|              o             |
|                            |
|                            |
|    x                       |
|                            |
------------------------------

would be unacceptable because if an "x" were to spawn in the corner, it would be an automatic game over. Also, the barriers may not form a wall which closes off areas of the arena.

I can flesh out this idea more if you think it is any good.

Please Give Me Feedback On This Question

When I have a working question, I will begin work on a basic solution in C++.

Description

The goal of this challenge is to create a real time (non-buffered input) ASCII version of the popular game Snake .

The board is 10 newlines by 32 spaces. The boundary consists of the " | " and " - " characters.

The snake body is made of the "o" character.

The snake head is v,<,>,^ depending on direction of travel (intuitively)

The snake eats " x ".

For example a game board might look like:

------------------------------
|                            |  11
|                            |
|              oooooo        |
|              o    o        |
|              o    v        |
|              o             |
|                            |
|                            |
|    x                       |
|                            |
------------------------------

In the new game, the snake has three body segments and a head. It gains one body segment every time it eats an "x".

The score (the number of segments+head) should be displayed somewhere on the screen.

The starting position of the snake and the starting position of the "x" is left to the writer.

After an "x" is eaten, the snake gains a segment, and a new "x" must spawn. "x"s may not spawn in a set of predetermined coordinates. They must spawn "pseudo-randomly" in the loosest sense of the phrase. This means that they can spawn using a random number generator or their position may be simply a function of the snake's position or some such simple rule.

The snake moves according to nonbuffered user input according to one or both of the following layouts:

"W" - change direction up.

"A" - change direction left.

"D" - change direction right.

"S" - change direction down.

AND/OR

"UP" - change direction up.

"DOWN" - change direction left.

"LEFT" - change direction right.

"RIGHT" - change direction down.

Note that, as per the rules of snake, at a given instance of the game, only three options are available to the player:

-- Do nothing (and continue moving straight)

-- Turn 90 degrees

-- Turn -90 degrees

Therefore, at a given instance, two of the movement buttons should be unresponsive. E.g. in the above case, only right and left are responsive.

Snake movement follows the normal pattern. For those of you not familiar with it: Let segment zero, $$s_0$$ be the head and segment $$s_n$$ be the very end of the snake. In a given frame, the snake has 3 choices, go straight, go left, or go right (from the snake's reference frame). $$s_0$$ moves into one of these spaces based on user input. Then $$s_i$$ moves into the space taken by $$s_{i-1}$$ on the previous frame.

If an "x" is eaten, then on the next frame the new segment $$s_{n+1}$$ is placed where $$s_n$$ was on the previous frame.

The game ends when the snake head collides with the snake body or a with a wall.

Rules

1) Only languages which are available for free may be used. Libraries may be used (for i/o, etc), however the actual snake program must be written by you. (if library overuse is an issue, it will be determined by up/down votes)

2) The game must be playable (i.e. the framerate must be acceptable on most machines, as determined by readers)

3) The winner is the program using the smallest number of bytes that fits the above description.

4) If an online compiler is available, it is recommended that you link it with your code so that others may play your game.

\$\endgroup\$
  • \$\begingroup\$ FYI, we've had a couple snake-based challenges already (1 2). \$\endgroup\$ – Geobits Oct 5 '15 at 16:07
  • \$\begingroup\$ Thank you. I'll either delete this post or come up with a way to make it fundamentally different. Since those were three years ago hopefully I can come up with a refreshing twist \$\endgroup\$ – Liam Oct 5 '15 at 19:06
0
\$\begingroup\$

Machine Learning

If you give a downvote please say why! (otherwise how will I learn, thanks)

The task is to create a simple program that "learns"

-->The challenge is to create a program which:

(1) outputs 50 integers (1 at a time) and waits for input after each.

The input given will be 1 or 0 depending on whether the number is "good" or "bad" based on a predetermined pattern (see the pattern section for more information)

(2) The program will then output something to the effect of

<< Learning done. Ready for testing.

At which point it will wait for integer input.

(3) My script will then input 50 integers (1 at a time) and the program will read the integers and output 1 or 0 depending on whether it thinks the integer fits the pattern.

-->Types of Patterns

Patterns will be of the following types, in an unknown order

- is divisible by x (x no larger than 20)

- is greater/less than x (x no larger than 100)

- is a perfect square

- has exactly x prime divisors (x no larger than 3)

- is coprime to x (shares no common divisors with x except 1) (x no larger than 100 and not prime)

numbers above subject to change if a case is made in the comments

-->Scoring

Bots will be scored on correct answers to my script input. The score is equal to the total number of correct answers across all 5 tests. There is a max score of 250.

Since I do anticipate perfect scores, ties will be broken by golf score of the source.

Further ties will be broken by submission time.

-->Example of A Test

note: "in" is for my input. "out" is for machine output.

The rule is "even-good, odd-bad"

out<<  10
in>>   1
out<<  1901
in>>   0

... more lines like this ....

out<<  Learning Complete. Ready for Input.

in>>   12
out<<  1
in>>   87
out<<  0

... more lines like this ...

Say the machine got 47/50 correct on this test, then it currently has a score of 47. I would then proceed to test it with 4 different patterns. And sum its score on each test for its final score.

-->Rules

(1) you may not use external tables, i.e. have a library that contains table for all possible tests. However, your code may generate such tables.

(2) the bot may not exceed an average time of 2 seconds per output. This goes for both the learning and testing sections. I really don't want to have to spend over 15 minutes per test. The average is so that it can spend a bit of start-up time to generate tables if it needs to.

(3) Use of external libraries is permitted, although it should be clear that the bulk of the work is yours. (this will be determined by downvotes)

(4) Languages must have a free interpreter available. If they don't I won't be able to test them. This rules out MatLab, Mathematica, etc.

(5) other rules may be added as necessary.

\$\endgroup\$
  • \$\begingroup\$ As interesting as this challenge sounds, I think you'd need a lot more than 5 test cases and 20 inputs to be able to see any sort of meaningful result. \$\endgroup\$ – Sp3000 Oct 6 '15 at 4:44
  • \$\begingroup\$ Really? Why do you say that? Regardless, that shouldn't be a problem, I could write a script to test the bots. \$\endgroup\$ – Liam Oct 6 '15 at 4:45
  • \$\begingroup\$ Given only 5 * 20 = 100 inputs, I'd expect there to be only a difference of a few incorrect responses between the top answers, which is small enough to be caused by chance. Also, is there any limit on the size of the programs? \$\endgroup\$ – Sp3000 Oct 6 '15 at 4:50
  • \$\begingroup\$ Okay, I'll bump it up to 50 questions per test. I'll edit the scenario shortly. No, no size limit (should there be), although I think that I'll put in something to the effect of "bot must make decisions within 1 min at all steps" \$\endgroup\$ – Liam Oct 6 '15 at 4:52
  • \$\begingroup\$ Mathematica is free. \$\endgroup\$ – LegionMammal978 Oct 24 '15 at 23:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .