464
\$\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 '19 at 7:51
  • \$\begingroup\$ @guest271314 You can use this markup to create a tag in a draft: [tag:code-golf] \$\endgroup\$ – DJMcMayhem Aug 29 '19 at 15:19
  • \$\begingroup\$ Why no featured anymore? Can't we have it auto-added or something? \$\endgroup\$ – S.S. Anne Sep 26 '19 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 '19 at 13:43
  • \$\begingroup\$ $y=mx+c+abcdef$ \$\endgroup\$ – Rebecca J. Stones Jan 4 at 3:14

2661 Answers 2661

3
\$\begingroup\$

Hi, first time golf questioner, hopefully I'm doing it right!

Maths Trade Calculator

A maths trade (or "math" trade if you prefer) is a way of calculating complex trades of arbitrary items in a circle of participants where not all participants want all items.

X participants have an item they would like to trade. Each participant is assigned a unique number, and provides a list of (numbers identifying) the items they would willingly trade their item for. They may provide an empty list (i.e. they would rather not trade).

Input

X lines, one for each participant, comprising a unique number identifying them, followed by a colon, then a comma-separated-list of numbers identifying other items that they would trade for. e.g.:

1:2,3,4
2:
3:1,4
4:2

The numbers identifying the participants will not necessary be in order, nor will they necessarily be 1 to X. You may assume that they will be numeric.

This string can be in STDIN, or an argument to a function, or similar and can be followed by a new-line or not, whatever the coder prefers.

Output

One or more trade loops in which all participants are making trades they're happy with. Each loop should be on a new line and comprise a participant number, followed by "->", followed by the participant they should give their item to, then another "->", and another participant number etc, until the loop is closed and the last participant number matches the first one. Another line is added with the number of completed trades. e.g.:

1->3->1
2

Participants for which no valid trade is possible are omitted.

Output can be via STDOUT, or returned as a string, or something else, with an optional final new-line.

Trade rules

  1. A participant may not be involved in more than one trade
  2. A participant may not receive an item that they didn't want
  3. All loops must be closed
  4. Maximum number of possible trades should be completed (i.e. no submitting a zero-trade output and claiming it's valid). If there are multiple permutations, pick whichever you prefer.

This is a code golf challenge, so shortest working code wins.

Some more example inputs and possible outputs

1

1:2,3,4,5
2:3,5,7,9
3:1,2,5,6,10
4:
5:1,2,3,4,10
6:5,7,9
7:3,6,9,10
8:1,2,4,10
9:1
10:9

1->9->10->3->1
7->2->5->6->7
8

For instance, in this trade: 9 stated that he would accept 1's item in a trade, 10 stated that he would accept 9's item, 3 would accept 10's and 1 would accept 3's. In the second loop, 2 receives 7's item, 5 receives 2's, 6 receives 5 and 7 receives 6's. (Other outputs are possible from this input.)

2

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

0

3

1:5,9
5:1
9:1

1->5->1
2

1->9->1 is also valid in this case, but both cannot be completed. Either is acceptable.

Thanks for reading guys! Let me know if there are any improvements I can make.

\$\endgroup\$
  • \$\begingroup\$ "can be followed by a new-line or not, whatever the coder prefers." How flexible is this? For instance, can I use trailing commas, like 1:2,4,7, if it makes my code shorter? \$\endgroup\$ – Martin Ender May 2 '14 at 17:28
  • 2
    \$\begingroup\$ Will the participants always be numbered 1 to n and their input lines provided in order? If so, state it. If not, include a test case which fails if an implementation decides to ignore everything before the : in each input line. \$\endgroup\$ – Peter Taylor May 5 '14 at 10:02
  • \$\begingroup\$ @m.buettner I would say a trailing comma is not acceptable, on the end of any line, or the end of the input/output. \$\endgroup\$ – Johno May 6 '14 at 8:55
  • \$\begingroup\$ @PeterTaylor Good tip. I'll correct the question to state that you can't assume that the numbers will be 1 to n, in order. \$\endgroup\$ – Johno May 6 '14 at 8:57
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 16:39
3
\$\begingroup\$

Design and Solve a Maze

(this question on hold while the details are ironed out)


Your task is to play the roles of both characters in this scene from Inception. In it, Cobb gives Ariadne a challenge:

You have two minutes to design a maze that takes one minute to solve.

Some liberties will be taken on that description. Most importantly, this challenge is not time-based, rather scores are based on the effectiveness of your mazes and maze-solvers.

I apologize for the many edits to this challenge as we iterate towards an easy and fair format..

Part I: Maze format

All mazes are square. A cell in the maze is represented as a zero-indexed tuple row column.

Walls are represented by two binary strings: one for horizontal walls (which block movement between rows) and vertical walls (vice versa). On an NxN maze, there are Nx(N-1) possible walls of each type. Let's take a 3x3 example where the cells are labelled:

A   B | C
   ---
D | E   F
   ---
G   H | I

all possible vertical walls are: AB BC DE EF GH HI. Translated into a string, the walls shown are 011001 for vertical walls and 010010 for horizontal walls. Also, by "binary string" I mean "the characters '0' and '1'".

The full maze format is a string which contains, in this order:

  • width
  • start cell tuple
  • end cell tuple
  • horizontal walls
  • vertical walls

For example, this maze:

   0 1 2 3 4
   _________
0 | |  E|  _|
1 |  _|_|_  |
2 |_ _ _  | |
3 |  _ _  | |
4 |____S|___|
start:(4,2)
end:(0,2)

is formatted to this:

5
4 2
0 2
00001011101110001100
10100110000100010010

Part II: The Architect

The Architect program creates the maze. It must play by the rules and provide a valid maze (one where a solution exists, and the end is not on top of the start).

input via stdin: Two positive integers:

size [random seed]

Where size will be in [15, 50]. You are encouraged to make use of the random seed so that matches can be replayed, although it is not required.

output to stdout: A valid size x size (square) maze using the format described in Part I. "valid" means that a solution exists, and the start cell is not equal to the end cell.

The score of an Architect on a given maze is

   # steps taken to solve
------------------------------
max(dist(start,end),(# walls))

So architects are rewarded for complex mazes, but penalized for each wall built (this is a substitute for Ariadne's time restriction). The dist() function ensures that a maze with no walls does not get an infinite score. The outside borders of the maze do not contribute to the wall count.

Part III: The Solver

The Solver attempts to solve mazes generated by others' architects. There is a sort of fog-of-war: only walls adjacent to visited cells are included (all others are replaced with '?')

input via stdin: the same maze format, but with '?' where walls are unknown, an extra line for the current location, and a comma-separated list of valid choices from this location. (This is a big edit that is meant to make it simpler to write a maze-parsing function)

example (same as the above 5x5 maze after taking one step left)

5
4 2
0 2
???????????????011??
????????????????001?
4 1
4 0,4 2

Which corresponds something like this, where ? is fog:

   0 1 2 3 4
   _________
0 |????E????|
1 |?????????|
2 |?????????|
3 | ?_?_????|
4 |__C_S|_?_|

output to stdout: One of the tuples from the list of valid choices

Each Solver's score is the inverse of the Architect's score.

Part IV: King of the Hill

Architects and Solvers are given separate scores, so there could potentially be two winners.

Each pair of architects and solvers will have many chances to outwit each other. Scores will be averaged over all tests and opponents. Contrary to code golf conventions, highest average score wins!

I intend for this to be ongoing, but I can't guarantee continued testing forever! Let's say for now that a winner will be declared in one week.

Part V: Testing

I have written a Python testing kit which includes a Maze class for parsing and writing in the proper formats, as well as an example architect/solver pair: Daedalus and the Minotaur

Available on both Dropbox and GitHub

Part VI: Submitting

  • I maintain veto power over all submissions - cleverness is encouraged, but not if it breaks the competition or my computer! (If I can't tell what your code does, I will probably veto it)
  • Come up with a name for your Architect/Solver pair. Post your code along with instructions on how to run it.
\$\endgroup\$
  • \$\begingroup\$ I suppose input is via STDIN? You might want to mention that explicitly, because at least the architect could just as well take the input via command-line arguments. \$\endgroup\$ – Martin Ender May 15 '14 at 15:34
  • \$\begingroup\$ updated. I have a driver/referee program which will handle I/O; I'll update it to use stdin/stdout since that will no doubt be the easiest standard. \$\endgroup\$ – wrongu May 15 '14 at 16:04
  • \$\begingroup\$ @m.buettner before de-sandboxing this, would you be willing to try the test kit? \$\endgroup\$ – wrongu May 15 '14 at 18:20
  • \$\begingroup\$ I'd love to, but I'm afraid I'm too busy this week. Try ask for help in the chatroom. \$\endgroup\$ – Martin Ender May 15 '14 at 18:35
  • \$\begingroup\$ Possible architect issue: With this scoring method (steps/walls), you can get a minimum score of 3 by simply putting the start/finish right next to each other with a single wall between. It takes three steps to go around. Most actual mazes I've seen have too many walls to make a score of 3 likely, much less guaranteed. \$\endgroup\$ – Geobits May 16 '14 at 13:51
  • \$\begingroup\$ Thats a problem. What if the dist function was shortest path? Then only mazes which cause detours could get a score > 1 \$\endgroup\$ – wrongu May 16 '14 at 15:09
  • \$\begingroup\$ That would probably be better. That way it's scored on best vs actual. It would take away the incentive to figure out how to build hard mazes with few walls, though, which was interesting itself. \$\endgroup\$ – Geobits May 17 '14 at 3:01
  • \$\begingroup\$ Hey rangu... not sure if you're still planning to do this thing, but overactor just said something in chat which reminded me of your challenge and might be a neat way to avoid the combined score: split this up into two code-challenges, one for maze generation and one for maze solving. Each code-challenge's benchmark set (to determine the scores) would be the outputs of the other challenge's participants. Then you could just pick a best solver and a best generator independently. \$\endgroup\$ – Martin Ender Aug 1 '14 at 11:18
3
\$\begingroup\$

Author note: I was thinking about new genres today, and I had an idea. What if there could be a challenge that encourages people to write good code, instead of the code-golf gibberish we all know? Here's a challenge that attempts to do that. (This could even possibly be a , which would be great because it would bring in a greater high quality question volume to the site, but I'm terrible at coming up with names. Feel free to suggest something in the comments.)


Build your own image editor

(?)

For this challenge, you will create the best GUI image editor that can perform the most tasks that you possibly can... from scratch.

Tasks and scoring

Here are the features / tasks used to score your program. Each task is worth a certain amount of points, which is specified in brackets before the task description. For convenience, each task will also be prefixed by an ID string so that you can refer to them when describing your program.

  • [1 A] Brush tool: Simple, click and drag the mouse to draw freestyle doodles. Must draw a contiguous path.
    • [1 A1] Ability to change the brush size.
  • {TODO: etc., add more}

Requirements

Your editor must conform to the following requirements:

  • Must accept input via the mouse. Tools (brush, flood fill, etc.) can be switched and configured with keyboard shortcuts, by clicking icons with the mouse, through a menu, or however you would like.
  • You may not use a single built-in function to accomplish one or more of the tasks. For example, if your language has a built-in image flood fill function, you may not use it and must build your flood fill from scratch.

Final score and voting

This is the syntax you should use to describe your score in your answer:

# {language}, {your score} score
<sup>(features implemented: {A, A1, ...})</sup>

    {your code here}

{description, comments, other notes, etc. here}

The amount of votes your post has (upvotes minus downvotes) will be multiplied by {TODO: figure out a good number} and added to your score. (Do not add this to the score in your post, since votes change constantly; I will add them manually.) Voters, please vote according to the following criteria:

  • elegance and readability of the source code
  • ease of use of the image editor and how powerful it is
  • remember to sort by "active" so that you're voting for new answers too, and not just the top voted ones!
\$\endgroup\$
  • 3
    \$\begingroup\$ Your questions should be reasonably scoped. If you can imagine an entire book that answers your question, you’re asking too much. A really good answer to this would run into millions of lines of code. \$\endgroup\$ – Peter Taylor Jun 4 '14 at 15:52
  • \$\begingroup\$ @PeterTaylor Yes, I was a little worried about that, but if it's not broad enough, it will be easy to just implement all the features. Any suggestions for fixing this? I was thinking of adding a "brevity" criterion in the voting section, but that doesn't seem like an ideal solution. \$\endgroup\$ – Doorknob Jun 4 '14 at 16:00
  • 3
    \$\begingroup\$ To be honest, the site for good code is Code Review. They already have a monthly challenge, for which they post snippets for review. I don't see a need to copy them. \$\endgroup\$ – Peter Taylor Jun 4 '14 at 16:12
  • \$\begingroup\$ @PeterTaylor Wait, isn't Code Review for questions and answers, not challenges and contests? In any case, is there any reason for that to prevent us from posting challenges like we always have? \$\endgroup\$ – Doorknob Jun 4 '14 at 16:17
  • \$\begingroup\$ meta.codereview.stackexchange.com/questions/tagged/… . Surprised you don't know about it, given how dedicated you are to spying on them ;) In general, if a question is on topic for multiple stacks then there's no obligation to do the sensible thing and post it on the one which it best fits, but you should expect people to ask why you're not doing the sensible thing. I think you're going to have to work hard to turn this into a question which fits this site, whereas it's already a good fit for CR's challenge programme. \$\endgroup\$ – Peter Taylor Jun 4 '14 at 16:31
  • \$\begingroup\$ @PeterTaylor Hmm, that's strange. Wouldn't that be more on-topic here? (And I only occasionally pop in to their chat/meta to see what they're up to. :-P) \$\endgroup\$ – Doorknob Jun 4 '14 at 16:32
3
\$\begingroup\$

Help Joe Bloggs with his password hash

Joe was confidently using "password1" as his main password to all his accounts until one day he received an e-mail from fBay. His account has been compromised and he must change his password immediately. Yet worse, the attacker had access to all Joe's accounts. Being an engineer, Joe thought: What if I could hash somehow my password using a keyword? I wouldn't need to remember any passwords and I would have a different one for each account.

Joe then creates an algorithm - he takes the domain name as a key and creates the password for each of his account consisting of:

1. (<consonants><vowels>)(alternating case: lower, capital, lower...)
2. <number of consonants><number of vowels>
3. <sum of consonants and vowels numbers converted to a character on US Qwerty Keyboard>

Joe then opens an account on SO to create a new code golf challenge. He uses stackoverflow as a key to generate password:

1. sTcKvRfLwAoEo - consonants and vowels in alternating case
2. 94 - 9 consonants, 4 vowels
3. 9+4=13, 1+3=4, Shift+4=$

Therefore, Joe's password for stackoverflow is: sTcKvRfLwAoEo94$

Challenge

Create a shortest function to generate a password given the rules above. The code should accept a string type parameter d and return/display the generated password.

Rules

  1. Only Latin letters from the input should be used. Any other characters should be ignored.
  2. Minimum input length is 1 letter. (guys at q.com need passwords as well!)
  3. Assume Y is a vowel
  4. If vowels or consonants are missing, use 0 accordingly. E.g. input a would result in a01!
  5. Shortest code wins

List of vowels and consonants

US qwerty keyboard

\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback @m.buettner. I meant to say, without using any libraries. The problem is, that people become lazy to think sometimes and just dive straight away to use Linq where a bit of thought will do \$\endgroup\$ – mai May 28 '14 at 13:14
  • \$\begingroup\$ Well actually you can, I'm just checking now. You can do a lot of manipulations on strings without libraries. \$\endgroup\$ – mai May 28 '14 at 13:18
  • \$\begingroup\$ Looping over string characters, concatenation work perfectly. Nevertheless, I've updated the challenge. If a function to depend on a library, it must be included in the character count. \$\endgroup\$ – mai May 28 '14 at 13:21
  • 3
    \$\begingroup\$ 1. Strictly speaking, in .Net you don't have strings without libraries. The string keyword is syntactic sugar for a class in mscorlib. 2. As things currently stand, your rule 1 strictly prohibits something and then says what to do if you ignore that prohibition. This is illogical. It's also unclear what "that" in "please inlcude that in characters count" means. Does it mean that each submission should be a program as opposed to a code snippet? If so, state it explicitly. \$\endgroup\$ – Peter Taylor May 28 '14 at 13:32
  • \$\begingroup\$ Hmm.. I don't know how to write it the best way. mscorlib is included by default so that is permissible. I don't want the code to use other libraries as Linq as it's less fun. \$\endgroup\$ – mai May 28 '14 at 13:47
  • \$\begingroup\$ @m.buettner I agree with you. Nevertheless, there will solutions provided in other languages as well (there always are). And I would like the authors of those solutions to think about the best approach in their language of choice without depending on libraries like Linq. \$\endgroup\$ – mai May 28 '14 at 14:00
  • \$\begingroup\$ Does Rule 2 mean ONLY vowels/consonants to be used from input? What about symbols *@#$ etc. Depending on that answer, potentially clarify Rule 5 regarding symbol input. As for Step 3 in the hash, should that progress further, similar to my Appended Numbers game so 103 consonants and 5 vowels would follow as 103+5 = 108, 1+0+8/10+8, etc.? \$\endgroup\$ – Matt Jun 4 '14 at 2:35
  • 1
    \$\begingroup\$ @Matt, clarified - only Latin letters are used from the input. If consonants or vowels are missing, use 0 instead. The sum should progress, until it's <=9. E.g. 103 consonants, 5 vowels: 103+5=108, 1+0+8=9. Then, Shift+9='(' \$\endgroup\$ – mai Jun 18 '14 at 10:36
3
\$\begingroup\$

Diplomacy

Note for Sandbox: I have not finished (or really started) the control program for this game, because I wanted to see if there was interest in it before I dedicated too much time to the project. that means that the rule are still up to be tweaked, so please leave a comment if you have a suggestion, and comment or vote if you are interested in seeing this happen.

Diplomacy is a complex strategy game, with a very entertaining combat system. This challenge will be to write a bot to compete in a simplified version of diplomacy combat.

Rules

Rounds

Countries (bots) will begin the game with 10 health, representing their remaining will to fight. The goal is to eliminate all other Nations by attacking them until they have 0 health.

The game will consist of several rounds. On the first round, all bots will receive 2 numbers as command line arguments: The first will be the total number of countries fighting, and the second will be their number in the list. Each following round, bots will receive a command line arguments containing the actions taken by each player last round and a list of all bots and their remaining health separated by commas, like so

 1:A2,2:S3,3:A4,4:A3 1:10,2:7,3:7,4:1

Each bot must then output a desired action, which is one two commands

  1. Attack a player. This is done by printing the letter A followed by the number of the player you with to attack. For instance, A3
  2. Support a player. This will give the player you support a boosted attack.

Resolving combat

After player have sent in their moves, attack scores will be calculated thus:

  1. All players start with a strength of 1, and one point is added for every player supporting them. For instance, if the moves are 1:A3,2:S1,3:A2,4:S2 then bot 1 has strength 2, bot 2 has strength 2, bot three has strength 1, and bot 4 has strength 1.
  2. After strength has been calculated, bots will deal damage based on their strength. The formula for damage is (Attacker's strength + 1) - (Defender's Strength) In the above situation, player 3 would take 2 damage and player 2 would take 0 damage. Note that, unlike regular diplomacy, attacking a supporter does not cut support.
  3. All attack take place simultaneously and independently. This means that if player 1 and 2 both attack player 4, then they each deal 1 damage. If player 3 were to support player 4, then player 4 would take no damage.

Round Ends

After combat has been resolved, countries that have 0 health will no longer be able to attack or support. However, they still will be listed in the input with an health of 0. When a bot is eliminated, all remaining bots will receive a single point.

Ending the game

The game ends when either 100 turns have elapsed or only 2 or less players remain. At this point, the player with the highest remaining health is the winner and receives 1 point. In case of ties, all tied bots will revive 1 point. If all bots die on the same turn, this is not a tied victory, but mutually assured destruction, and all bots will receive 0 points.

Scoring

The control program will run 100 rounds of the game. The winner will be the country with the most points at the end of 100 rounds.

Code

You may write in any language I can reasonably compile. I will make an effort to compile odd languages, but make no promises as to my ability to do so. Please provide your source code, an explanation, and a command line command to run your program.

Notes
  • You are allowed to write to a file. In fact, you are encouraged to do so.
  • Because this is a game where cooperation is paramount, you are allowed to write bots that work together, with the following restriction:

    • Only two bots can be written by a single player to work together at a time.
  • Standard Loopholes apply. You are not allowed to change the way the control program runs. If you provide invalid input to the control program, the program will just skip your turn. However, you are allowed to spy on other countries files, and all bot programs will be in the same folder at runtime. This is war, after all!

  • I reserve the right to disqualify any country that takes more than about a second to run, or that tries a loophole not mention within. That being said, if it is sufficiently clever I will probably let it go.

I will have source code up soon for a sample country that will be competing, and will post the control program when I finish it.

\$\endgroup\$
  • \$\begingroup\$ "In case of ties, all tied bots will revive 1 point". Is that supposed to say "receive"? "If all bots die on the same turn, ... all bots will receive 0 points." If there are two bots left, each of which has received 1 point from the earlier death of a third bot, and the two bots destroy each other on the same turn, what's the final score for the round? I'm not sure whether it's 0-0-0 or 1-1-0. "You are allowed to write bots that work together": but how can they identify each other? Do they have to use their moves as a covert channel? \$\endgroup\$ – Peter Taylor Aug 29 '14 at 14:28
  • \$\begingroup\$ "Support a player. This will give the player you support a boosted attack." Or defence. Might be clearer to say "boost that player's strength for the turn". Should also state whether or not it's possible to support yourself. \$\endgroup\$ – Peter Taylor Aug 29 '14 at 14:29
3
\$\begingroup\$

Check GenericScript source code for compiler errors

Given the source code for a GenericScript program as input, parse the source code to check that it conforms to the syntax rules for the language. The syntax definition for GenericScript is below. If a part of the source code is found to be invalid, the program should output "Invalid syntax", otherwise it should output "Valid syntax".

Win Criteria

This is code golf. Shortest code wins.

Syntax

Source code will be considered to be valid if it matches the rule for "Program" below.

Program             = Sequence
Sequence            = Statement [Sequence]
Statement           = SequenceBlock | Assignment | If | While | Output
SequenceBlock       = "{" Sequence "}"
Assignment          = Identifier "=" (String | Bool); 
If                  = "if(" Bool ")" Statement ["else" Statement]
While               = "while(" Bool ")" Statement
Output              = "print(" String ");"
Identifier          = {Any sequence of alphanumeric characters prefixed with "var" }
Bool                = StringEquals | Identifier
StringEquals        = String "==" String
String              = StringConstant | OperatorConcat | Input | Identifier
StringConstant      = "'"StringContent"'"
StringContent       = Character [StringContent]
Character           = {Any character except for "'"}
OperatorConcat      = String "&" String
Input               = "read()"

Whitespace is defined as any sequence of the ascii characters 9, 10, 13 and 32. Whitespace characters are allowed between tokens but are not required.

Rules

  1. The answer should be a complete program
  2. Standard input/output allowed
  3. Standard loopholes apply
  4. Universally testable answers only

Test Input

Valid syntax:

print('What is your name?');
varInput = read();
print('Hello ' & varInput);

Invalid syntax:

if(read() == 'DoTask1')
  print('Executing you'r command');
\$\endgroup\$
3
\$\begingroup\$

Text Adventure Game

Objective

Your goal is to develop a complete text-based adventure game with the shortest code possible. The player navigates in a dungeon composed of rooms. The game objectives are to find the treasure, slain the dragon and rescue the princess.

Rules

A room description is as follows:

You are in <description>.
You can go <exits>
You see <object>      (optional)
  • exits can be "north", "east", "west", "south".
  • description can be "a adjective cavern", "a adjective room", "a adjective corridor", "a adjective hall", "a cell", "the dragon's lair".
  • adjective can be "dark", "murky", "small", "large", "narrow", "gloomy", "huge", "strange", "tiny", "broad", "old".
  • object can be "the princess", "the dragon", "a troll", "a goblin", "a sword", "gold", "a key", "a trunk".

Exit list must be comma-separated and end with "and". If there is no object in the room, the last line is omitted.

Example of valid description:

You are in a murky room.
You can go north, east and south.
You see a goblin.

The game accepts the following commands (case is ignored) :

  • GO direction : direction can be NORTH, EAST, WEST, SOUTH
  • TAKE item : item can be SWORD, GOLD, KEY
  • KILL monster : monster can be DRAGON, TROLL, GOBLIN. The DRAGON and the TROLL can be killed only if the user has the SWORD. If he hasn't, he loses the game. The weak GOBLIN can be killed with bare hands. When a monster dies, he disappears from the room. When the GOBLIN dies, he drops a SWORD. When the TROLL dies, he drops a KEY.
  • KISS person : person can be PRINCESS, DRAGON, TROLL, GOBLIN. Kissing the princess validates one of the objective of the game, and the princess disappears from the room. Kissing a monster results in player death.
  • OPEN object : object can be TRUNK. If the player has the KEY, the TRUNK object disappears and is replaced with GOLD.

OBJECTS
The player can perform an action on an object only if the object is in current room. A room can contain only one object ; a given object can be found in only one room. At the beginning of the game, only the following objects are placed in the map : PRINCESS, DRAGON, TROLL, GOBLIN, TRUNK. Other objects are not yet created.

ACTIONS

  • If an action cannot be performed (e.g. GO NORTH where there is no exit to the north, or TAKE DRAGON, or DANCE GANGNAM STYLE), the message "Sorry, I can't do that" must be displayed.
  • If an action can be performed, the message "OK" and the current room description should be displayed.
  • You can read game commands from console or as a program parameter, as you wish.

MAP
The dungeon should have at least 30 rooms. The dungeon should not contains a series of more than 5 exits in the same direction. The exits between rooms must be consistent, e.g. if you go north from room #1 to room #2, there must a south exit in room #2 leading back to room #1. Every room name should be unique. There must be at least one room of each kind (hall, cavern, corridor...)

  • A hall has at least 3 exits.
  • A corridor can have only 2 exits.
  • The cell has only one exit.
  • There is only one dragon's lair and only one cell, containing respectively the dragon and the princess.

GAME END
The game ends when the player has been killed, or when he has taken the gold, slain the dragon and kissed the princess.

  • If the player dies, the message "You have been killed by X !" is displayed, with X being the name of the monster.
  • If the player wins, the message "Well done adventurer ! you've conquered the dungeon." is displayed.

Player should not be able to win the game in less than 40 turns.

Example

You are in a murky room.
You can go north, east and south.
You see a goblin.
> KILL GOBLIN
Ok.
You are in a murky room.
You can go north, east and south.
You see a sword.
> TAKE SWORD
Ok.
You are in a murky room.
You can go north, east and south.
> GO NORTH
Ok.
You are in a narrow corridor.
You can go south and east.  

Scoring

The shortest code wins.

\$\endgroup\$
  • \$\begingroup\$ @Martin Thanks for your comments! I've updated the question. \$\endgroup\$ – Arnaud Aug 21 '14 at 7:59
  • \$\begingroup\$ Provided the player ignores the troll and goblin (i.e. doesn't try to kiss or kill them), they don't do anything? \$\endgroup\$ – Peter Taylor Aug 21 '14 at 8:30
  • \$\begingroup\$ @Peter you're right. Maybe the player should kill (with bare hands) the goblin in order to get the sword, and then kill the troll (with the sword) to get the key. \$\endgroup\$ – Arnaud Aug 21 '14 at 8:50
  • \$\begingroup\$ "The map must be spatially coherent" still doesn't disallow always going left without ending up in the same room twice, unless you specify that the rooms are all meant to be square (which is what I think you had in mind). Also, I still think that "at least" 30 rooms is unnecessary. Who would implement 8 additional rooms if they don't have to. It will definitely be shorter if I omit the two longest adjectives and just use all available combinations of the remaining ones (giving 30 unique rooms). So you can omit two adjectives and the "at least" right away, I'd say. \$\endgroup\$ – Martin Ender Aug 21 '14 at 9:19
  • \$\begingroup\$ I think it's fine to keep "at least" there for flavour, same with additional adjectives. Also, someone might figure out a way to make the code shorter with a longer adjective (for that reason, having a few more adjectives might be nice) \$\endgroup\$ – FireFly Aug 21 '14 at 9:38
  • \$\begingroup\$ @Martin I've added a criteria "Player should not be able to win in less than 30 turns", to force the golfer to implement more rooms. \$\endgroup\$ – Arnaud Aug 21 '14 at 9:39
  • \$\begingroup\$ @SuperChafouin That doesn't force it though. I just need to place the goblin at the end, troll at the beginning, trunk at the end, so that you need to traverse the map 3 times. \$\endgroup\$ – Martin Ender Aug 21 '14 at 9:51
  • \$\begingroup\$ @Martin It's also here to prevent the dungeon to be too straightforward to solve, e.g. if all the objects are in 5 adjacent rooms near the player start location. \$\endgroup\$ – Arnaud Aug 21 '14 at 10:51
  • \$\begingroup\$ +1 for golfing in Inform 7. \$\endgroup\$ – Lopsy Sep 20 '14 at 2:56
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 16:58
  • \$\begingroup\$ @programmer5000 Yes no problem :-) \$\endgroup\$ – Arnaud Jun 10 '17 at 1:07
3
\$\begingroup\$

Simulate a Quantum Circuit

Work-in-progress until I can make sure I know what I am doing and can finish the spec. or maybe


Quantum computers are the way of the future! Why wait, when you can simulate one now?

Your mission is to determine the output of a quantum circuit given its input and a diagram of logic gates.

Details

You will simulate a single quantum register and apply a series of quantum logic gates to it. A quantum register is a group of qubits. The state of a register is described by a vector of 2^N complex numbers, where N is the number of qubits in the register.

a|000>
b|001>
c|010>
d|011>
e|100>
f|101>
g|110>
h|111>

Above is a representation of a 3-qubit register. Each letter (a b c etc.) represents a complex number. There is an addition restriction that:

|a|^2 + |b|^2 + |c|^2 + |d|^2 + |e|^2 + |f|^2 + |g|^2 + |h|^2 = 1

Quantum gates

Gates are represented by a 2^N x 2^N square unitary matrix, where N is the number of input qubits. All quantum gates have the same number of outputs and inputs, since they neither create nor destroy qubits, they modify them.

A common quantum gate is called the Hadamard gate and acts on a single qubit. The matrix [H] looks like this:

1/Sqrt(2)  1/Sqrt(2)
1/Sqrt(2)  -1/Sqrt(2)

If we let [R] represent the following 1-qubit register:

0.6|0>
O.8|1>

Then the application of the gate is represented by [H][R] and gives the following result:

7*Sqrt(2)/10|0>
 -Sqrt(2)/10|1>

It is still true that the sum of the squares of the absolute values is equal to 1.

(TODO: explain how to apply gates to larger registers)

Measurement

Measurement collapses the state of the quantum register.

(Todo: Explain how measurement works)

Input

Output

\$\endgroup\$
3
\$\begingroup\$

BS

The goal of this challenge is to implement an AI for the game of BS, also known as Bull Shit, Cheat, Bluff, and numerous other names.

The game is outlined in this wikipedia article.

The Rules of the Game

For the purposes of this challenge, the game will work like this:

  1. A standard 52-card deck is dealt out to the players
  2. The current rank is set to Ace
  3. The play order is randomized
  4. The player holding the Ace of Hearts goes first
  5. On each player's turn:
    1. The current player plays some number of cards
    2. The current player states how many of what rank they played
    3. Other players may declare 'BS'.
    4. If any player declares 'BS':
      1. All players are notified of which players declared 'BS'.
      2. The played cards are revealed to all players.
      3. If the played cards are inconsistent with the current player's statement:
        • The current player adds the played cards and all cards in the pile to their hand
      4. If the played cards are consistant with the current player's statement:
        • The last player to declare 'BS' that round adds the played cards and pile to their hand.
    5. If no player declares 'BS':
      1. The played cards are added to the pile, without revealing them.
      2. If the played cards were inconsistant with the current player's statement, the current player may declare 'Peanut Butter'.
    6. If the current player has no cards in their hand, the current player wins.
    7. The current rank is incremented. (If the current rank is King, it becomes Ace.)

The Messaging Protocol

Play will be conducted via messages passed to the standard input and received from the standard output of each program. Each message will be terminated with a single newline character.

Cards

Card ranks are represented as one of A, 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, or K. Card suits will be represented as one of S, C, H, or D. Cards are represented as the rank, followed immediately by a suit. For instance, the Ten of Clubs would be represented by TC, and the Three of Hearts would be represented by 3H.

A hand of cards will be represented as a space-delimited sequence of cards. For instance, a hand containing the Queen of Spades and the Six of Diamonds could be represented as QS 6D or 6D QS.

Player Identification

A player will be represented by their nickname, followed by a number from 0 to 32768, in parenthesis, formatted as an integer. This number is guaranteed to be unique within a particular game. A player's nickname must have at least one character, can have up to 32 characters, and may only include letters, numbers, and underscores. For instance, a player with nickname ExampleAI and ID number 16480 would be identified in the game as ExampleAI(16480).

When the game begins, each program will recieve a message containing their unique ID:

Unique ID: uniqueID

Each player will reply with their desired nickname:

Nickname: name

Names may contain only alphanumeric characters and underscores.

After all players have responded with their nickname, the standard play sequence begins.

Standard Play Sequence

When a player's turn begins, each player will receive a be given a list of the players and their card counts, in order of play:

Players: player[count], player[count], ... player[count]

Each player will be informed of the contents of their hands:

Hand: initial_hand

The current the player will then receive this message:

Your turn: current_rank 

The current player will reply with a space-separated list of of cards:

Play: list_of_cards

Once they have submitted their play, all players will receive the number of cards, formatted as an integer, along with the current rank:

Player player plays: nunber_of_cards x current_rank

Each other player may then declare BS on that play by sending any message up to 32 characters, containing the capital letters B and S, and otherwise only contains lowercase letters and spaces. So any of Bull Shit, Bananna Split or Bacon Sandwich would be acceptable.

During this period, the current player may declare Peanut Butter by sending any message up to 32 characters, as long as it contains the capital letters P and B, and otherwise only contains lowercase letters and spaces. So any of Peanut Butter, Pancake Batter or Polish Bacon would be acceptable.

In order to allow the game to move faster, if a player does not wish to declare either of these things, they must instead send:

Pass

After all players have responded, all players will receive a list of players who called BS, in the order they called it:

Called BS: player, player ... player

If no player called BS, this message will still be sent --- it just won't have any players listed. If any player did call BS, then all players will recieve:

Player player had played: list_of_cards

If they were bluffing, all players recieve:

Player player was bluffing.

And the current player receives:

Your bluff was called: list_of_cards_recieved

If they were not bluffing, all players recieve:

Player player was not bluffing.
Player last_player receives the pile.

The last player who called BS recieves this message:

You misjudged: list_of_cards_received

The list of cards received will contain, in reverse chronological order, the contents of each play since the last call. (Separate plays will not be delimited in the list.)

If no player declared BS, and the current player was bluffing and declared Peanut Butter, then all players recieve the message:

Player player was bluffing.

If the current player has no cards left in their hand, all players receive this message, and the game terminates:

Player player won!

Otherwise, the next player's turn begins.


Example Game

The following might be considered a typical (abbreviated) message transcript:

Unique ID: 16481
> Nickname: Alice
Players: Alice(16481)[18], Bob(16479)[17], Charlie(16480)[17]
Hand: 2D 7S AS TC 5S JS JC 3C 8H 9D 5D AH 7C 6C 4D KC KH KS
Your turn: A
> Play: AS 2D AH
Player Alice(16481) plays: 3 x A
> PB
Called BS:
Player Alice(16481) was bluffing.
Players: Bob(16479)[17], Charlie(16480)[17], Alice(16481)[15]
Hand: 7S TC 5S JS JC 3C 8H 9D 5D 7C 6C 4D KC KH KS
Player Bob(16479) plays: 2 x 2
> BS
Called BS: Alice(16481)
Player Bob(16479) had played: 2H 2C
Player Bob(16479) was not bluffing.
Player Alice(16481) takes the pile.
You misjudged: 2H 2C AS 2D AH
Players: Charlie(16480)[17], Alice(16481)[20], Bob(16479)[15]
Hand: 7S TC 5S JS JC 3C 8H 9D 5D 7C 6C 4D KC KH KS 2H 2C AS 2D AH
 .
 .
 .
Players: Alice(16481)[3], Bob(16479)[41], Charlie(16480)[8]
Hand: KC KH KS
Your turn: K
> Play: KC KH KS
Called BS: Charlie(16480), Bob(16479)
Player Alice(16481) was not bluffing.
Player Bob(16479) receives the pile.
Player Alice(16481) won!

Your implementation may be written in any language, provided that you, upon request, provide a link to a suitable free-as-in-freedom compiler or interpreter that I can download and run at no cost. You also need to provide a UNIX command that can start your program.

Sandbox Questions

I want to gauge the community's interest in my problem before finalizing the spec and writing the control program.

I also need to get some idea of what sort of time-limiting scheme would be reasonable. In order to be able to to a lot of runs, I will need to be able to ensure that each AI doesn't take too much time to make its decisions, or prevent a stuck AI from holding up a game. I also need to be able to ensure that there is no motivation to deliberately stall a game. For example, if an AI determines that it is very unlikely to win, it might stall in order to prevent the game from finishing.

I would also like feedback on the messaging protocol:

  • Are there any additional messages that you think should be passed?
  • Would it be more convenient/clear if one or more of them were formatted differently?
    • Would it be better to use a different format for the plays message?
    • Would it be better to use different words to help distinguish the plays and played messages?
\$\endgroup\$
  • \$\begingroup\$ It looks like quite a tough challenge, but should be enjoyable! \$\endgroup\$ – Alexander Craggs Sep 4 '14 at 16:54
  • \$\begingroup\$ @PopeyGilbert By the way, there was one thing I accidentally left out that I need feedback on. Specifically, time limits - to deal with intentional stalling, getting stuck, or taking too long to decide. \$\endgroup\$ – AJMansfield Sep 4 '14 at 17:05
  • 1
    \$\begingroup\$ A question and a feedback. Does our program run as "stop and run" or must receive feedback continuously? And for feedback. I honestly think that the whole username things is kinda confusing. Maybe if you just use only unique id? (Like just simple 0,1,2,3 instead of username) \$\endgroup\$ – Realdeo Sep 5 '14 at 8:33
  • \$\begingroup\$ Oh! More things! I also realize that suit doesn't really matter, right? (We only use suit for deciding who goes first), so fmpov, you can ditch the communication protocol for the suit. (No need for S,C,D,H) We can just use simple random from the computer. Question: What will happened if everybody make infinity loop of pass. For time limit, I prefer 1 second. If no response, make it auto pass. (KOTH chess time limit is 2 seconds. That's why 1 second is good enough) \$\endgroup\$ – Realdeo Sep 5 '14 at 8:38
  • \$\begingroup\$ @Realdeo Card suit is also used to distinguish between separate instances of a card. If Alice plays 3x2 (2S 2D 2C), is not revealed, and Bob gets the pile later, and then Bob plays 3x2 (2S 2C 2H), and this is revealed, it is important for Alice that she knows all four Twoes have passed through Bob's hand. There are other ways that can be used as well. \$\endgroup\$ – AJMansfield Sep 5 '14 at 13:29
  • \$\begingroup\$ @Realdeo I am not sure what you mean by "Does our program run as "stop and run" or must receive feedback continuously?". If you mean, "Does an AI program halt in the periods where no response is expected from it?" the answer is no. \$\endgroup\$ – AJMansfield Sep 5 '14 at 13:32
  • \$\begingroup\$ @Realdeo If everybody makes an infinity loop of pass, then eventually someone will run out of cards, since you are required to play at least one card each turn. \$\endgroup\$ – AJMansfield Sep 5 '14 at 13:33
  • \$\begingroup\$ @Realdeo Which is why making a automatic pass after a timeout not work when waiting for a player to decide their play. Perhaps a simple rule like 'if you take more than 1 second to decide what to play, four cards are selected at random from your hand'. \$\endgroup\$ – AJMansfield Sep 5 '14 at 13:36
  • \$\begingroup\$ And if a player has less then 4 cards? I think in some AI website, like aigames.com, they're like forced to give up that hand? You really want to test your entry before put them in the arena(like vsing a bot dummy?) Either way, this is a good challenge =) \$\endgroup\$ – Realdeo Sep 5 '14 at 13:40
  • \$\begingroup\$ @Realdeo Also note that you can actually play more than four cards in one play. A case where you might wish to do this is when: the next player is very close to winning and some other player is close to winning and you believe(all opponents believe(your next opponent will bluff) and the next opponent will not bluff and the next opponent believes(the other opponent close to winning will call BS against them)). A little convoluted, but could happen. \$\endgroup\$ – AJMansfield Sep 5 '14 at 13:42
  • \$\begingroup\$ @Realdeo Just to explain what I mean, is that there are two people close to winning, each of which would like to dump a large stack of cards on top of the other. Because of this, they both let your obvious bluff slide because they believe that will let them dump a large stack on the other. \$\endgroup\$ – AJMansfield Sep 5 '14 at 13:47
  • \$\begingroup\$ Don't worry I understand. This is a really famous high school game in my country. It just... a little bit too complex for CR. When I saw chess KOTH, I was kinda pessimist. This one? This may deserve it's own AI website. #seriously. I'm just trying to simplify this game =) \$\endgroup\$ – Realdeo Sep 5 '14 at 13:50
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – AJMansfield Sep 5 '14 at 13:50
  • \$\begingroup\$ RE the messaging service, I think the other players should be able to see how many cards the other players have. Also, card counting should be prohibited because that would make the game too easy. \$\endgroup\$ – Beta Decay Sep 10 '14 at 17:31
  • \$\begingroup\$ @BetaDecay First off, according to the protocol, every player is informed of every other player's hand size at the beginning of every round. \$\endgroup\$ – AJMansfield Sep 10 '14 at 18:27
3
\$\begingroup\$

Let's talk about this...

I am planning on hosting a King of the Hill challenge in which bots will have to coordinate each other in order to be successful. The idea is to play a Diplomacy-like game between bots. The engine (still in development) will start the bots and communicate with them via stdin/stdout. There will be three phases:

0. Initialization

Well, this is not a recurring phase, it is just the engine telling each bot his id, the total number of bots participating and a seed, which can be used for generation of pseudo-random numbers (bots need to be deterministic).

1. Talking Phase (10s)

In the Talking phase, bots can send messages to each other (via engine) in order to coordinate their actions. To this end, a common language is necessary. This language should be able to express any ideas, plans and opinions a bot could have. However, not every bot is forced to be able to understand everything. Simpler bots might just ignore messages they do not understand.

Since I would like each player to be able to submit more than one bot, it is forbidden to implement a "secret handshake" by which bots recognize each other and from then on work together unconditionally.

2. Planning Phase (2s)

In this phase, bots submit what they want to do this turn. Each bot has a certain amount of supply (initially five), and can command one action per supply point. There are three possible actions:

  1. Attack another bot
  2. Support another bot's attack against a third bot
  3. Defend another bot

There are some restrictions:

  • Per opponent, you can either attack or defend them, and only once
  • You cannot support an attack against a bot you also defend
  • You cannot attack, defend, support yourself or a dead bot, and neither can you support attacks against yourself

3. Resolution Phase (as short as possible)

After all orders have been submitted, the engine will resolve them simultaneously in the following way:

The defending strength of each bot is the number of bots defending that bot. The attacking strength of each attack is the number of support orders for that attack. Each attack with an attacking strength greater than the defending strength of the attacked bot results in the supply counter of the attacked bot being reduced by one, and the supply counter of the attacker being increased by one.

Support orders which support a non-existent attack do nothing.

Then, all bots with supply of zero or less will be shut down by the engine: they died.

Afterwards, all remaining bots are informed about the decisions of other bots, and a new turn begins with its Talking Phase.

Further Rules

A game will consist of ten plus random number turns, so that "last turn betrayals" are not possible. The supply count of each bot will count towards their total score. I plan an ensemble of about 100 games. The bot with the highest total score wins. Tie-breaker will be the popularity (number of votes).

I am interested in your opinion: do you think that this challenge is too complex? I imagine that the code of a decent bot would be too long to fit in a post. So people would have to use github or pastebin or similar to submit their entries. The main problem imo is the interpretation of the (yet to be determined) common language.

\$\endgroup\$
  • \$\begingroup\$ I like it a lot. One possible variation would be to make the "secret handshakes" a feature. To do this, you could allow multiple instances of the same bot. Then part of the challenge is to recognise your own kin and mutually support them; and a viable strategy is to try and work out other players' secret handshakes and imitate them. If you're ok with emphasising this aspect of it, then you can make the shared language pretty unrestricted, e.g. bots can just send arbitrary strings to each other. (I realise this is not what you have in mind, I just thought I'd mention the idea.) \$\endgroup\$ – Nathaniel Oct 31 '14 at 15:13
  • \$\begingroup\$ @Nathaniel, what you propose is a battle of obfuscation/cryptography. What I would like to see is a battle of diplomacy. \$\endgroup\$ – M.Herzkamp Nov 2 '14 at 14:27
  • \$\begingroup\$ Fair enough - I just thought I'd say it in case it sparked any interesting thoughts for you, but I knew it was probably too different from what you want to see. If I have any other ideas about your challenge I'll let you know. Designing the language really seems to be the hard part. \$\endgroup\$ – Nathaniel Nov 3 '14 at 0:06
  • \$\begingroup\$ A diplomatic KOTH is something I've been wanting to see for a while. Working out the specifics of the "diplomatic language" is going to be the most difficult part. My proposal is that each message can either 1) state an intention to another bot, or 2) request an action from another bot. Each message would be formatted in a way similar to how a final command would be. \$\endgroup\$ – PhiNotPi Nov 9 '14 at 14:45
  • \$\begingroup\$ @PhiNotPhi: Thanks for the Feedback! I also imagined something similar with the ability to link atomic statements in a boolean fashion. \$\endgroup\$ – M.Herzkamp Nov 11 '14 at 9:23
3
\$\begingroup\$

Happy Holidays!

Introduction

With the holidays upon us, I decided to make an appropriately themed challenge. You are provided with a list of holidays and their respective date ranges, and given a date, you have to output a holiday greeting or the time remaining until the next holiday as appropriate.

Challenge

The list of holidays is below. You have to include it in your program (so no using a library or other external resource for this). Feel free to use any convenient format.

Start  | End    | Name
------ | ------ | -------------------
Dec 6  | Dec 7  | Saint Nicholas' Day
Dec 13 | Dec 14 | Saint Lucy's Day
Dec 24 | Dec 27 | Christmas
Jan 1  | Jan 2  | New Year
Jan 6  | Jan 7  | Epiphany
Feb 14 | Feb 15 | Valentine's Day

You are given a date as input (STDIN, function argument, or anything convenient) in YYYY-mm-dd HH:MM:SS format (e.g.: 2014-12-30 11:15:00).

You may assume that the time zone is either UTC or the system's time zone. The holiday lasts from 00:00:00 on the start date (inclusive) to 00:00:00 on the end date (exclusive).

If the date falls within the range of the holiday, you must output Happy <holiday>!, except if it's Christmas, in which case you must output Merry Christmas!.

If it doesn't, but another holiday is coming at most a week in the future, you must output:

<time> left until <holiday>.

where <time> is in the following format:

<days>d <hours>h <minutes>m <seconds>s

You can't use a library for converting the time to that format.

If there are no whole days, hours, minutes or seconds remaining, omit the number entirely. For example, 1d 0h 3m 4s should be printed as 1d 3m 4s.

If there are no upcoming holidays, you must output (no pun intended):

There are no upcoming holidays.

A trailing newline is optional, but be consistent in your program—don't add a trailing newline in one case and omit it in another.

Standard loopholes are obviously forbidden.

Test cases

Date                | Output
------------------- | ----------------------------------
2014-12-05 23:59:59 | 1s left until Saint Nicholas' Day.
2014-12-06 00:00:00 | Happy Saint Nicholas' Day!
2014-12-06 12:00:00 | Happy Saint Nicholas' Day!
2014-12-06 23:59:59 | Happy Saint Nicholas' Day!
2014-12-07 00:00:00 | 6d left until Saint Lucy's Day.
2014-12-14 00:00:00 | There are no upcoming holidays.
2014-12-24 00:00:00 | Merry Christmas!

Note that your program must work for any year, not just 2014.

Winner

This is code golf, so the submission with the fewest number of bytes wins. An answer will be accepted after a week, but I'll be happy to change the accepted answer if a new valid submission beats the previous high score.


\$\endgroup\$
  • \$\begingroup\$ How do you expect people to test the test cases? It would probably be better to take input than to use the current time, because then it actually makes sense to talk about test cases. You should check date for duplicates, and if there are none you should add that tag. \$\endgroup\$ – Peter Taylor Dec 29 '14 at 14:51
  • \$\begingroup\$ @PeterTaylor You're right, I'll do that. \$\endgroup\$ – nyuszika7h Dec 29 '14 at 15:37
  • \$\begingroup\$ @PeterTaylor I couldn't find any exact duplicates, only two holiday-themed questions, both of which ask for much less than my challenge. \$\endgroup\$ – nyuszika7h Dec 30 '14 at 11:28
3
\$\begingroup\$

Find the Minimum Width of a Set of Points

Given a set of points in 2D space, you're to find the direction along which those points occupy the shortest width.

More formally, consider a set of n points P = {p1, ..., pn}, where pi = (xi,yi), and a unit vector d = (xd, yd). Now K is the set of lengths obtained from orthogonal projection of P onto d. In particular, ki = xixd + yiyd. The width L of P along d is defined as max ki - min ki. Your task is to find the d along which L is minimal.

To keep things interesting, your algorithm's time complexity must not exceed O(n log n).

You may write a program or function, taking input via STDIN, command-line argument or function argument. The result may be printed to STDOUT or returned.

You can expect the input P to be in any convenient list or string format, but the input must not be pre-processed (e.g. sorted by coordinates). You may assume that the input contains at least 2 points and that no two points coincide.

The output must be correct to 10 significant (decimal) digits. Of course, d is only unique up to the relative sign of the coordinates, so there are two correct answers for each input. You may return either of those.

You must not use built-in functions related to this problem, like finding the minimum width of a polygon, or computing the convex hull of a set of points. You may use built-in vector/matrix types and operations.

Sandbox Notes

  • I'll write my own solution at some point next week, and use it to provide a number of test cases.
  • I'm also planning to add a handful of diagrams to clarify the definitions.
  • The challenge was inspired by this proposal from Calvin's Hobbies, I think they are sufficiently different, as this problem here is only one approach to tackling his challenge (and even then it's only a subproblem). But if people think, they are too similar, and posting this one would make his a duplicate in the future, I'll retract this challenge (as I'd really like to see his posted some time).
\$\endgroup\$
  • \$\begingroup\$ I hope you're still planning on posting this. Just a few notes: (a) The minimal direction is not generally unique (e.g., if we have a regular polygon, or just a single point). You'd might want to make the actual (scalar) width the output instead. (b) I assume the input is never empty? (c) Can it contain duplicates? \$\endgroup\$ – Ell Jan 3 '15 at 16:01
  • \$\begingroup\$ @Ell yes I still want to post this. Just didn't get around to writing the reference yet. a) good point. I'll think about asking for the width vs asking for any minimal direction. b) yes, will clarify. c) I'll think about that. Probably not. \$\endgroup\$ – Martin Ender Jan 3 '15 at 16:07
3
\$\begingroup\$

The Genetic Game of Life

In this game, you play as cells (as in cellular automata). Your goal is to reproduce and kill off other cells on the board.

At the beginning of the game, two distinct configurations will be randomly chosen, one for reproduction, one for killing. The configurations will consist of 3 squares in a 5 by 5 area, not including the center square. For example,

OOXOX
OOOOO
OO OO
OOOXO
OOOOO

is an example configuration, where X represents a cell, and O can either be empty or filled. The configurations do not work if rotated.

The cells will be placed randomly, but equidistant from each other in a toroidal board. Cells will be placed in a random turn order.

Each turn, each cell will move a square one at a time. If a cell's movement creates the reproduction configuration with cells of the same type, and the center square is empty, then a new cell will spawn. If a cell's movement creates the killing configuration with cells of any type, and the center square is filled, then the cell in the center square will die.

When a new cell spawns, its DNA will be conglomeration of the DNA of the bots in the configuration. It will take its first turn after all other cells have taken 1 turn.

A cell that has not been part of a killing configuration after 200 turns will die.

The cell type with the most cells after 100K turns wins.

IO

Each turn, you will be passed a string of 1s and 0s representing your DNA, and a list of 49 integers representing a 7x7 grid of the vision around the cell. Specimens of the same type will have the same integer, and 0 will represent an empty square.

You must return a single character (N, E, S, W or X) representing the direction that the cell will travel. Attempting to move into another cell will result in your cell not moving.

\$\endgroup\$
  • \$\begingroup\$ What size genome are you thinking? \$\endgroup\$ – trichoplax Jan 21 '15 at 15:18
  • \$\begingroup\$ When designing a bot, I think it would make a big difference if the total number of players was known. You could say "a game consists of 50 players competing on a board" and make up the numbers with a simple example bot if there are less than 50 answers. Obviously 50 is just an example - it could be 10 or 2 or 20 or whatever works best. \$\endgroup\$ – trichoplax Jan 21 '15 at 18:54
  • \$\begingroup\$ I say this because it means a bot writer will then know the maximum size of the 49 integers they need to process. \$\endgroup\$ – trichoplax Jan 21 '15 at 18:56
  • \$\begingroup\$ Could you specify whether a killing configuration can be made up using cells of different teams? \$\endgroup\$ – trichoplax Feb 5 '15 at 0:38
  • 2
    \$\begingroup\$ 1. The latest version of this question talks a lot about types, but doesn't define them. What is the type of a cell? Its genome? Its team? 2. What is meant by the "conglomeration" of the genomes of the bots in the spawning configuration? Is it the concatenation? Some kind of bit-by-bit random selection between the three parents' genomes? 3. What's the initial setup? How many cells do I get, and do they all have the same genome? \$\endgroup\$ – Peter Taylor Feb 5 '15 at 10:32
3
\$\begingroup\$

Convert a Finite State Machine to a Regular Expression

Anyone can make a finite state machine for matching a regular expression. But what about a regular expression that emulates a finite state machine? This inverse operation is much more confusing.

Input

  • A positive integer N, denoting the number of states in the machine. They are labeled 0 to N - 1.
  • A list of accepting states of the machine. A string is considered to be accepted by the machine if it ends in one of these when there are no characters left.
  • A list of triples (integer a, character b, integer c) representing the transition rules: when the machine is at state a and the current character in the string is b, then it may advance one character and move to state c.

You may specify the ordering and formatting of input.

Output

A regular expression that matches a string iff it is accepted by the finite state machine.

Additional Rules

  • An input for the state machine may contain only printable ASCII characters which are not in the set ^$()[]|+?*\..

  • The machine begins in state 0.

  • You should not use any regex features other than |, (), ?, *, +

  • You may not use libraries designed for this task (which apparently exist).

  • The regex should match full strings (assume it is surrounded by ^ and $).

  • An answer is either a program which prints the regex to stdout, or a function which returns the regex.

This is code golf: write your code in as few bytes as possible.

Sandbox Question

Should the FSM be deterministic or non?

\$\endgroup\$
  • \$\begingroup\$ Why not allow character classes? Alteration seems like an overkill alternative, and answers might like to detect parallel edges. \$\endgroup\$ – John Dvorak Feb 5 '15 at 14:38
  • \$\begingroup\$ "a function which returns the regex." - do we need to actually construct the regex object or are we allowed to return a string representation thereof? \$\endgroup\$ – John Dvorak Feb 5 '15 at 14:40
  • \$\begingroup\$ General FSMs tend to produce really big regexes. Not sure if allowing non-determinism inflates that even further, but I believe it actually does not. \$\endgroup\$ – John Dvorak Feb 5 '15 at 14:46
  • \$\begingroup\$ Are you sure you want to allow { and } in the input? Because we'd have to escape these... \$\endgroup\$ – John Dvorak Feb 5 '15 at 14:47
  • \$\begingroup\$ @JanDvorak Thanks. I'll allow character classes although I doubt they would be used in golf. I'm aware they will be big (like this question). \$\endgroup\$ – feersum Feb 5 '15 at 14:52
  • \$\begingroup\$ (a) Can we assume anything at all about the SM? Are all terminal states accepting? Are all states reachable? Can there be no reachable accepting states, and what would be the output in this case? (b) Are the blacklisted input chars also invalid as input for the regex? That is, can we use \* in our regex with the intention that it's never matched? (c) How liberal can we be with the input format? Can we take the transition table as, for example, {src_state: [(char1, dest_state1), (char2, dest_state2)], ... }, or must it be a list of triplets? \$\endgroup\$ – Ell Feb 8 '15 at 13:33
  • \$\begingroup\$ @Ell For (a) and (b), the metacharacters are not allowed in the input strings, so one way to match nothing would be using one of them literally. About (c), it must be a list of triples. \$\endgroup\$ – feersum Feb 13 '15 at 3:39
3
\$\begingroup\$

ASCII Robot Wars

This idea is based off of the game "Besiege" (which I've never played) and a previous sandboxed idea of mine called "Epic Customizable Tank Battle."

The main idea is that your program is the AI that controls a robot equipped with various weapons. In this challenge, however, you will also have the opportunity to design your robot

List of Parts

(completely arbitrary and subject to total replacement)

  • Wooden planks + and armored metal plates # make up the body of the robot.
  • Wheels @ allow your robot to move. TODO - turning
  • Most weapons are formed with two parts, a body and a pointer v^<> to denote the direction of aim.
  • Cannons have a body of %, ballistas have a body of (something), spikes and battering rams are (something).
  • Maybe helicopter blades can be X.
  • Banners, which serve no purpose but decoration, could be $.

Example 5x5 robot

This robot has four wheels, three cannons facing forward, armored sides, and a flag in the middle.

@^^^@
#%%%#
#+$+#
#+++#
@###@

Controlling the Bot

I think this would make a really cool Stack-Snippet KOTH, since it is "visually interesting" to watch robots blow each other into pieces. Writing the controller will be hard because this is a major deviation from previous pixel-based KOTHs.

\$\endgroup\$
3
\$\begingroup\$

Sorting Source Code

Your task in this challenge is to write a program that takes no input and outputs This program consists of followed by your program's source code characters, but in alphabetical order.

Details

  • You may only use printable ASCII characters and line breaks in your program.
  • When outputting all source code characters, ignore line breaks and sort all characters by their ASCII number from lowest to highest.
  • Reading your program's source code is not allowed.
  • This is , so the shortest valid submission (in bytes) wins.

Here is a correctly ordered list of all printable ASCII characters (mind the space at the very beginning):

 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

Example

If the source code for your program is

print 'This program consists of ';
print this.sort();

then output must be

This program consists of       ''().;;Tacfghhiiiiimnnnooooppprrrrrssssssttttt
\$\endgroup\$
  • 1
    \$\begingroup\$ You should probably add the quine tag to this. And you should also specify whether reading the source code is allowed. That said, I'm not sure how much it adds over existing (generalised) quine challenges. Ultimately, solutions will just be language's standard quine, followed by sorting the string and prepending This program consists of. \$\endgroup\$ – Martin Ender May 18 '15 at 17:33
  • \$\begingroup\$ Are submissions in which the original source code is already sorted, allowed? \$\endgroup\$ – ProgramFOX May 18 '15 at 17:34
  • \$\begingroup\$ @ProgramFOX: I don't see why they shouldn't be allowed. Is there any particular reason? \$\endgroup\$ – vauge May 18 '15 at 18:42
  • \$\begingroup\$ @MartinBüttner: Good point. I've added the quine tag, but probably there's no point in posting this challenge if there are already enough similar questions! \$\endgroup\$ – vauge May 18 '15 at 18:45
  • \$\begingroup\$ @vauge No, I missed that you had to print a sentence before the sorted characters. Initially I thought of a one-char solution like 1 which works in some languages (and which would pretty much miss the purpose of the challenge), but of course that doesn't print the sentence. \$\endgroup\$ – ProgramFOX May 18 '15 at 19:06
  • \$\begingroup\$ In addition to not reading the source code, you might want to link to these working definitions of what counts as a proper quine. With the requirement of printing the additional string it's not very likely that there are a lot of loopholes left, but better safe than sorry. \$\endgroup\$ – Martin Ender May 19 '15 at 7:04
  • \$\begingroup\$ The problem with quines is that there's a reusable technique to print any function of the source code, so twists like this don't actually change much. \$\endgroup\$ – xnor May 19 '15 at 7:20
3
\$\begingroup\$

Strange question about transit schematics (title tbd)

In this challenge, your goal is to produce a schematic diagram of a transit network, given a list of lines and a list of stations as input. This is a popularity-contest -- the program's goal is to maximize the readability of the diagram by carefully choosing where to draw the stations and lines.

Each line in the transit network is formatted as a list of strings. For instance:

"Peel Line", "Douglas", "Port Erin", "Braddan Halt", "Union Mill", "Crosby"

The first string on the list is the name of the line. The remaining strings are the stations that that particular line stops at. In this example the Peel Line stops at Douglas, Port Erin, Braddan Halt, Union Mill, and terminates at Crosby. The lines are bidirectional so the Peel Line would also go back the other way.

Of course, most transit networks will have more than one line. Each line of the transit network will have its own line in the input. For instance:

"Peel Line", "Douglas", "Port Erin", "Braddan Halt", "Union Mill", "Crosby"
"Foxdale Line", "Ramsey", "St. John's", "Union Mill", "Bishop", "Foxdale"

Notice how both lines stop at Union Mill. This means that Union Mill is an interchange station for those two lines. A station is an interchange station if more than one line stops at it. Here is an attempt at what the network might look like:

bad map

This map does some things well but fails at other things. The lines are coloured different colours which helps differentiate the lines. In addition, the interchange station is emphasised with the white dot to show it is an interchange station. However, it fails at other things, the most prominent being that the text "Union Mill" is overlapping the line, and there is a lack of a key showing which line is which. When we fix these elements the map looks like this:

another map!

Much better! (Another way I could have resolved the Union Mill overlapping issue was to change the paths of the lines.) In addition, we can also have lines being a loop. This is indicated by the first and last train stations being the same. For instance:

"Island Line", "Port Erin", "Kitterland", "Kalfr", "Ardglass", "Kearney", "Port Erin"

The Island Line in this case is a loop that goes from Port Erin to Kitterland to Kalfr, then to Ardglass and Kearney, before finally returning to Port Erin, completing the loop.

With more complicated train networks, it becomes more difficult to arrange the stations and lines in a readable manner. Here are some inputs of varying complexity and density to try your program on. Some of them are based of actual networks, while others are made up for this challenge.

Challenge Input 1: Oslo, Norway:

"1", "Frognerseteren", "Voksenkollen", "Lillevann", "Skogen", "Voksenlia", "Holmenkollen", "Besserud", "Midtstuen", "Skådalen", "Vettakollen", "Gulleråsen", "Gråkammen", "Slemdal", "Ris", "Gaustad", "Vinderen", "Steinerud", "Frøen", "Majorstuen", "Nationaltheatret", "Stortinget", "Jernbanetorget (Oslo S)", "Grønland", "Tøyen", "Ensjø", "Helsfyr", "Brynseng", "Hellerud", "Tveita", "Haugerud", "Trosterud", "Lindeberg", "Furuset", "Ellingsrudåsen"
"2", "Østerås", "Lijordet", "Eiksmarka", "Ekravein", "Røa", "Hovseter", "Holmen", "Makrellbekken", "Smestad", "Borgen", "Majorstuen", "Nationaltheatret", "Stortinget", "Jernbanetorget (Oslo S)", "Grønland", "Tøyen", "Ensjø", "Helsfyr", "Brynseng", "Hellerud", "Tveita", "Haugerud", "Trosterud", "Lindeberg", "Furuset", "Ellingsrudåsen"
"3", "Mortensrud", "Skullerud", "Bogerud", "Bøler", "Ulsrud", "Oppsal", "Skøyenåsen", "Godlia", "Hellerud", "Brynseng", "Helsfyr", "Ensjø", "Tøyen", "Grønland", "Jernbanetorget (Oslo S)", "Stortinget", "Nationaltheatret", "Majorstuen", "Blindern", "Forskningsparken", "Ullevål stadion", "Berg", "Tåsen", "Østhorn", "Holstein", "Kringsjå", "Sognsvann"
"4", "Storo", "Nydalen", "Ullevål stadion", "Forskningsparken", "Blindern", "Majorstuen", "Nationaltheatret", "Stortinget", "Jernbanetorget (Oslo S)", "Grønland", "Tøyen", "Ensjø", "Helsfyr", "Brynseng", "Høyenhall", "Manglerud", "Ryen", "Brattlikollen", "Karlsrud", "Lambertseter", "Munkelia", "Bergkrystallen"
"5", "Storo", "Nydalen", "Ullevål stadion", "Forskningsparken", "Blindern", "Majorstuen", "Nationaltheatret", "Stortinget", "Jernbanetorget (Oslo S)", "Grønland", "Tøyen", "Carl Berners plass", "Hasle", "Økern", "Risløkka", "Vollebekk", "Linderud", "Veitvet", "Rødtvet", "Kalbakken", "Ammerud", "Grorud", "Romsås", "Rommen", "Stovner", "Vestli"
"6", "Bekkestua", "Ringstabekk", "Jar", "Bjørnsletta", "Åsjordet", "Ullernåsen", "Montebello", "Smestad", "Borgen", "Majorstuen", "Nationaltheatret", "Stortinget", "Jernbanetorget (Oslo S)", "Grønland", "Tøyen", "Carl Berners plass", "Sinsen", "Storo"

Here's what the official map looks like for some inspiration (click to enlarge):

OSLO!!!

TODO: more challenge inputs coming!

Sandbox Notes

  • I've had this one sitting around for a while. I've wanted to try and make a that wasn't just about making the prettiest image. So instead it's about making the most functional image, which I'm not sure is any better than the art challenges...
  • Another thing I've been considering is changing it to a . I'd have minimum requirements for the final output (a key, coloured lines, distinguished interchange stations, etc.) and the shortest code that implemented all the requirements would win. I'd like your thoughts on whether this challenge would work better as code golf or popularity contest.
\$\endgroup\$
  • 3
    \$\begingroup\$ I like this concept, but I somewhat like it better as a popcon. As a golf, you will get the bare minimum requirements for sure, and it might not be very functional/readable at all. As a popcon, you'll probably get at least a couple platform-ready posters. I don't normally recommend popcon for things that could be golfed, but this feels like one them. \$\endgroup\$ – Geobits May 19 '15 at 16:37
  • \$\begingroup\$ For test cases, I think Tokyo would make for something nice and complicated. \$\endgroup\$ – Geobits May 19 '15 at 16:41
  • \$\begingroup\$ @Geobits That is a fantastically complicated network, but it's got all sorts of things that the input format can't handle -- if I'm reading it right, when the Yokosuka Line reaches Chiba and Soga it splits off into different paths with different terminus stations. \$\endgroup\$ – absinthe May 19 '15 at 22:18
  • \$\begingroup\$ Good point, I'm guessing many large cities have split lines like that. I suppose if you want a simple input format it'll have to be some boring old map ;) \$\endgroup\$ – Geobits May 20 '15 at 14:01
  • 2
    \$\begingroup\$ There doesn't seem to be an obvious reason for not using an input format which allows lines to fork and loops to encompass only part of a line. Why not take input in a subset of the .dot format? \$\endgroup\$ – Peter Taylor May 21 '15 at 19:23
3
\$\begingroup\$

Permutations of the Fifteen Puzzle

POSTED

\$\endgroup\$
3
\$\begingroup\$

How to Gossip Appropriately

We all know how important it is to get social arrangements right:

XKCD

You have a group of friends who love to gossip. However, gossip is notorious for changing as it gets spread from friend to friend, and if somebody hears two versions of the same gossip, it just ruins it for them.

Hence, you and all of your friends have agreed to gossip in an orderly manner, and it is your job to define who will gossip with who and for how long. Ideal gossiping must follow the following rules:

  1. Each friend must gossip for a specific amount of time. This time is different for each person.

  2. Any pair of friends will only spend so long gossiping. Any longer, and it will become dull. We will refer to this time as L. This time is the same for all friends.

  3. Gossipping only comes in minute increments. We have no idea why this is, but its true.

  4. Gossip must eventually reach everybody. If any given friend has new gossip, then all of your friends must eventually get that gossip.

  5. Proper gossipping never includes circles. If A gossips to B and C, and then B gossips to C, then C will hear the news from two different people, and therefore, two different stories.

As an example say you are given the following as input:

Graph

Let's start by looking at B. She prefers to gossip for only 1 minute, so she will only be able to gossip with one friend.

We know that she can't gossip with D, as that breaks rule #4

If we have B gossip with C, then C will have 1 minute of gossipping left, and A won't be able to fill his 2 minutes of gossipping needs.

Therefore, we know that B must gossip with A for 1 minute, and A must gossip for 1 minute with C. C and D each have 1 minute of gossipping remaining, so they must both gossip with E.

E needs 2 more minutes of gossip.

If E gossips with F for 2 minutes, then gossip can't ever reach G.

If E gossips with F for 1 minute and G for 1 minute, then F must gossip with H for 1 minute, and H will then gossip with G for 2 minutes. This will create a circle, breaking rule #5.

Therefore, we know that E gossips with G for 2 minutes, G gossips with H for 1 minute, and H gossips with F for 2 minutes.

Our final gossipping tree looks like:

Tree


Input will be in the following format, and will be passed to your program via STDIN (or closest alternative):

Max_Gossip_Time [Node0_Ideal_Gossip_Time, Node1_Ideal_Gossip_Time, ...] [[Node0, Node1], [Node0, Node1], ...]

The second array passed is the friend list, and are integers that refer to the positions in Ideal_Gossip_Time array.

The example above would be input as follows:

2 [2, 1, 2, 1, 4, 2, 3, 3] [[0, 1], [0, 2], [1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [4, 5], [4, 6], [5, 7], [6, 7]]

Output should be to STDIO (or closest alternative) in the following format:

[[Node0, Node1, Gossip_Time], [Node0, Node2, Gossip_Time], ...]

On the above example, the output should be similar to:

[[0, 1, 1], [0, 2, 1], [2, 4, 1], [3, 4, 1], [4, 6, 2], [5, 7, 2], [6, 7, 1]]

On both input and output, the friend list can be in any order.

\$\endgroup\$
  • \$\begingroup\$ I didn't notice that you state anywhere that the weights must be integers. Some more test cases would be good. Do you know anything about the complexity class of this problem? \$\endgroup\$ – Peter Taylor May 17 '15 at 16:07
  • \$\begingroup\$ @PeterTaylor I don't think the complexity is too crazy, but I don't know it. The hardest part of this challenge is actually ensuring that there are no cycles as min-maxing the edges will solve everything else. \$\endgroup\$ – Nathan Merrill May 17 '15 at 18:51
  • \$\begingroup\$ I can see a research paper coming out of this! \$\endgroup\$ – Optimizer May 27 '15 at 13:23
3
\$\begingroup\$

If it floats, it boats!

The goal of this challenge is to determine whether or not an ASCII-art shape will float. Like any other boat, ASCII boats obey the law of buoyancy: it will float if it displaces an equal mass of water.

ASCII boats are made out of O characters arranged in some contiguous shape (diagonals are connected). There may be trailing spaces, but the whole input is a rectangle (trailing newline optional). Example boat:

   O         O    
    O        O    
     OOOOOOOOO    

The material of the boat has twice the density of water. When a boat is floating, the number of displaced water characters is at least twice number of O character in the boat. Here is an artist's impression of a boat while floating.

   O         O    
~~~~O        O~~~~
~~~~~OOOOOOOOO~~~~
~~~~~~~~~~~~~~~~~~

This boat has 13 O characters, but displaces 19 water characters, so it floats.

The key to floating is the creation of an air pocket. Air pockets can be formed in two ways: either the water cannot reach the pocket (because the boat has walls keeping it out), or air is trapped in the pocket and cannot escape. Here's an example of a capsized boat which can still float (warning: do not attempt at home).

     OOOOOOOOO
~~~~O        O~~~~
~~~O         O~~~~
~~~~~~~~~~~~~~~~~~

The following shapes aren't boats because they can't float:

OOO
O  
O  
O  
OOO

   O         O    
    O        O    
     OOOOOOOOO    
             O    
         OOOOOOOOO
         OOOOOOOOO
         OOOOOOOOO

The Goal

Write a program that, when given an ASCII-art shape, outputs a truthy value if it boats, and a falsey value if it doesn't boat. This is code golf, fewest bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Do you want this to be the simple version (if it displaces enough water it floats) or a more complex version (some of the air spaces may be filled as it sinks, but remaining air spaces are sufficient to keep it afloat). I'm thinking of examples with multiple air spaces with different height walls, so at a certain depth the water can only fill some of them. That is, the weight of the boat is too great to keep all of the air spaces empty, but the remaining ones are sufficient to keep it from sinking any further. \$\endgroup\$ – trichoplax Jul 24 '15 at 21:58
  • \$\begingroup\$ 1. Bearing in mind the example of the capsized boat: are we supposed to test all possible rotations of the input, or just the orientation in which it's supplied? 2. It would be good to have test cases which are right on the edge (one which floats by displacing exactly its mass, and one which is one unit too heavy). 3. Another corner case which isn't mentioned is discontiguous boats. Should we assume that the input is fully connected? \$\endgroup\$ – Peter Taylor Jul 24 '15 at 22:04
  • 1
    \$\begingroup\$ @trichoplax I am leaning towards the more complex version, where the boat is "lowered into" the water, which may float various parts until the equilibrium is reached. PeterTaylor I'll say that only the given orientation should be tested. Also, boats will always be contiguous. \$\endgroup\$ – PhiNotPi Jul 24 '15 at 22:08
  • \$\begingroup\$ Why are the non-boat example not boats? Or do you mean they are boats that don't float? \$\endgroup\$ – xnor Jul 26 '15 at 7:41
  • \$\begingroup\$ @xnor They don't float. It was supposed to be an extension of "if it floats, it boats" so the ones that don't float aren't boats. \$\endgroup\$ – PhiNotPi Jul 26 '15 at 21:30
  • \$\begingroup\$ The boat has 13 O characters, and the material is twice the density of water. Doesn't it therefore need to displace 26 characters in order to float? Sure, this shape will float but it will sit lower in the water than you have drawn it. \$\endgroup\$ – Level River St Aug 4 '15 at 15:35
3
\$\begingroup\$

Multiples - a wrap battle


Overview

Change cells in multiples to wipe out your opponent, while avoiding being wiped out yourself.


This is a 2 player game, played on a linear string of cells of length L that wrap in a loop. Counting along the loop eventually brings you back to where you started (after L steps). L will be fixed across all battles, and will be a reasonably large prime.

Each cell is controlled by player 1, player 2, or is neutral. These will be indicated as 1, 2 and 0 respectively.

Starting position

Player 2 starts with a cell at position 0 (since all are equivalent).

Player 1 starts with a randomly chosen cell from 1 to floor(L/2).

Player 1 moves first, reflecting the fact that player 1 has further to go to catch player 2.

Taking a turn

Each player begins with a stockpile of 0, and at the start of each turn the player's stockpile is increased by the number of cells that they currently control. The player then takes their turn. They choose any cell they control and specify a number N, which can be any non-negative integer up to and including the size of the stockpile. The stockpile is reduced by this number, and N loop cells are affected as follows:

Starting with the chosen cell as cell 0, each of the cells N, 2N, 3N, ... N*N are changed.

  • Choosing 0 means nothing happens, at zero cost.
  • Choosing 1 means the cell immediately after the chosen cell is changed, at a cost of 1.
  • Choosing 2 means the cell 2 cells on and the cell 4 cells on are changed, at a cost of 2.
  • Choosing 3 means the cells 3, 6 and 9 cells on are changed, at a cost of 3.
  • In general, choosing N changes N cells at a cost of N.

When a cell is changed it follows the following rules:

  • A neutral cell becomes the player's.
  • An enemy cell becomes neutral.
  • A cell already owned by the player becomes the enemy's

Large N

I expect most moves will choose N considerably smaller, but saving up would allow choosing N considerably larger than L in theory.

Choosing N=L means that all of the changed cells will be the same - the chosen cell, and it will be changed L times.

Choosing N=L-1 means that the L-1 consecutive cells before the chosen cell will all be changed (that is, every cell except the chosen one will be changed).

Winning

If a move leaves no enemy cells remaining, that player wins.

After 1000 moves any player who has more cells than their enemy at the start of 2 consecutive turns in a row (one theirs, one their enemy's, in either order) wins.

After 2000 moves the game is a draw (tie).


Input and output

Input

At the start of a game the player's code will be called with a command line argument of 1 or 2 indicating which player they are (player 1 moves first and is represented by 1s in the loop string).

Each turn the player will be supplied with:

  • A string of 0s, 1s and 2s representing the loop.
  • An integer S representing the size of their stockpile.
  • An integer R representing the size of their opponent's stockpile.
  • An integer representing the number of turns taken so far (this will always be an even number for player 1).

Output

The player should output 2 integers:

  • The cell C to play from, in the range 0 <= C < L.
  • The number of cells to change N, in the range 0 <= N <= S (their current stockpile size).

Sandbox questions

  • I like the idea of this being a 1 dimensional game, but I can also see it working on a 2d grid, where each move is applied both horizontally and vertically (either on a square L by L, or with 2 distinct large primes as side lengths). Does anyone have anything for or against either 1d or 2d?

  • Any recommendations on what input to provide? I was thinking at least the values of all the cells, but would a history also be good, or better to make the players decide what history to track for themselves rather than providing it? Alternatively they could be memoryless and decide purely based on the current cell formation.

  • Is the random starting position a good idea? Would it be better to fix the starting position at floor(L/2), ensuring this number is prime, and let the players taking turns to be player 1 balance out any bias?

\$\endgroup\$
3
\$\begingroup\$

Help Indiana Jones and his crew cross the bridge!

This codegolf will solve the Bridge and Torch problem. In this problem, there are multiple people (I'm thinking four) who must all cross a weak bridge to escape an evil dragon as quickly as possible. Because the bridge is weak, only two people can cross the bridge at a time. The whole crew is armed with one torch, which is necessary for 1 or 2 people to cross the bridge. Furthermore, each person takes a certain, integral amount of time to cross the bridge. When two people cross together, they must run at the rate of the slower person. The whole crew needs to quickly figure out how to get all the people across the bridge in the least amount of time to maximize their chances of survival.

Input A list of names of the crew (one word, a-zA-Z) and how long they take to cross the bridge alone.

Output An explanation of who crosses the bridge in which order so that the total time is minimized, and the total time.

Example Input: Indiana 5 Jones 10

Output:

Indiana, Jones 10

Input: A 1 B 2 C 5 D 8

Output:

A, B A C, D B A, B 15

I'm thinking of either just solving this problem with any number of people, or another version in which anyone not at the end (ie. on the first side or on the bridge) after the time limit dies, and the goal is to minimize the number of deaths.

\$\endgroup\$
  • \$\begingroup\$ If it's code-golf it's easier for you as the question poster. If you put a time limit, then different computers will achieve different amounts in that time limit, so you would need to run all the answers on your own computer to give them an official score. \$\endgroup\$ – trichoplax Jul 3 '15 at 16:45
3
\$\begingroup\$

Bad Lip Reading Generator

A malapropism is the substitution of one word for another that sounds similar, often as a way to make something sound unintentionally humorous. For example, "He's a wolf in cheap clothing" is a malapropism, since the expected word, "sheep's", got replaced by "cheap", which sounds similar but means something different.

A modern version of malapropism is to take scenes from movies and redub the dialog with different words that match the actors mouth movements as a parody. There is a YouTube channel called "Bad Lip Reading" that uses this technique.

I would like to apply the process to some old videos with subtitle files, then watch the videos with the sound turned down to turn it into a long series of malapropisms.

Using mouth movements gives a more flexible range of malapropism so there is some flexibility between different sounds.

Challenge

Create a malapropism generator. I want to be able to feed text from subtitles into the generator and have text which is different, but still matches the mouth movements of the actors.

Input

A string of English words, (already processed to remove punctuation and forced to uppercase).

Output

A string of English words, (same format as input).

Notes

To simplify the challenge, all input words are in upper case, separated by whitespace, with all punctuation except apostrophes removed.

Lets agree to constraint what words "sound like", to be based on the CMUDICT. You may scrub the data so you don't have to worry about comments or special punctuation entries and remove stress numbers.

Lets also agree on the mouth-movements associated with the sounds, called "visemes". Here is a mapping used by Microsoft's SAPI library, which is itself based on Disney animation rules. Microsoft uses the same set of phonemes from ARPABet as CMUDict data.

#   ARPAbet Phoneme

1   AE AH
2   AA
3   AO
4   EH EY UH
5   ER
6   IH IY Y
7   UW W
8   OW
9   AW
10  OY
11  AY
12  HH
13  R
14  L
15  S  Z
16  CH JH SH ZH
17  DH TH
18  F  V
19  D  N  T
20  G  K  NG
21  B  M  P

You should be able to take each English word, convert to a set of phonemes, then to a set of visemes, then produce a list of words with matching visemes and randomly select one of the other words from the list. If a word doesn't match, or doesn't have any alternative, the original word should be copied to output.

Examples

  • "HELLO WORLD" "HALLOW WHIRLED"
  • "I SEE DEAD PEOPLE" "EYE SEA TED PEOPLE"
  • "I WILL BE BACK" "EYE WHEEL PEA BAG"
  • "IT WAS BEAUTY KILLED THE BEAST" "INN WAS PUNY GILT THE MIST"
  • "MAY THE FORCE BE WITH YOU" "MAY THE FOURS BEE WITH YEW"

Test Cases

Since the words are random, I have selected some pairs of words with unique pronunciation. Your function or program should always return one word when presented with the other:

Input            Output
"AMUSING"        "ABUSING"
"APOGEE"         "APACHE"
"BACKDATING"     "MAGNETIC"
"BALLOONING"     "POLLUTING"
"INVISIBLE"      "INFEASIBLE"
"LAMPS"          "LUMPS"
"SCORN"          "SCORED"
"WEPT"           "WEBBED"

Rules

  • You can write a full program or function.
  • Input should be taken from stdin or function parameters. Output should be printed through stdout or returned.

Scoring

This is [code-golf]. Submission with least number of bytes, (not including data file(s)) wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ Interesting challenge, but I have some small suggestions. 1. The example in the first paragraph (moths vs moss) is inconsistent with the definition which follows, and that could confuse. Maybe borrow one of the test cases, or mention The Importance of being Earnest? 2. Why not link to the YouTube channel? 3. For subheadings, ### is better than *. 4. Since the input is nicely cleaned, I can't see why you specify all input words are in the same case rather than all input words are in upper case. The latter would be more useful, since it matches the CMUDICT file. \$\endgroup\$ – Peter Taylor Aug 20 '15 at 17:22
  • \$\begingroup\$ 5. The mapping of ARPAbet to viseme ID is very long and offputting, and it's not really necessary. If you replace it by a list of groups (AE AH newline ... newline B M P) in preformatted text (indent by four spaces) then it will convey all the necessary information while taking a lot less space. 6. Talking of which, it might be worth mentioning ARPAbet to pre-empt questions in the comments. \$\endgroup\$ – Peter Taylor Aug 20 '15 at 17:22
  • \$\begingroup\$ 7. It's a good idea to be explicit that when you say randomly you mean with equal probability or (easier for those whose libraries give them random floats) with a difference between the greater and least probabilities of no more than 1%. 8. The test cases aren't very useful for testing. The most useful test cases will be where most of the words have one or two possible outputs. E.g. MINT CONDITION STAMPS becomes PINNED CONDITION STUMPS. CATERER is also a good test case because it has a repeated phoneme at the end of the word, which could catch some buggy regex-based approaches. \$\endgroup\$ – Peter Taylor Aug 20 '15 at 17:23
3
\$\begingroup\$

Cake


Concerns:

  • I'm not sure how well single language questions do. It automatically limits the question to those that already know the language, and those that are willing to learn just for this question. There's no need to limit to Chef with some of the magic this community can produce!

  • "selfish/demanding" sounds quite strong and could sound like a bit of a personal attack on Beta Decay. It certainly isn't intended like that, and I expect it will be accepted as intended, but is it better to err on the side of caution?

\$\endgroup\$
  • 4
    \$\begingroup\$ Is there any particular reason to limit the challenge to Chef? Writing code that mimics a real world cake recipe could be entertaining in other languages as well. \$\endgroup\$ – Dennis Sep 9 '15 at 18:36
  • 2
    \$\begingroup\$ @Dennis, I suppose not! I wouldn't have thought it possible, but I've seen some of the magic this community can produce! \$\endgroup\$ – James Webster Sep 10 '15 at 11:39
  • \$\begingroup\$ I feel like the best tasting submission might just be an actual cake recipe which acts as a no-op, with the actual printing merely tacked on somewhere (eg in Foo) \$\endgroup\$ – Sp3000 Sep 11 '15 at 4:12
  • \$\begingroup\$ @Sp3000, that's possible. I added that rule because with Chef, the ratios for ingredients are often way off. \$\endgroup\$ – James Webster Sep 11 '15 at 6:12
3
\$\begingroup\$

Source code ecological footprint

You've just been hired by a German car manufacturing company. Your first task, as an engineer, is to write a program that computes the ecological footprint of source code.

The ecological footprint of a character is computed as follows (you can assume the source code is ASCII-encoded):

Write the character's ASCII code in binary, and count the number of 1's.

For example, A has a footprint of 2, but O is dirtier with a footprint of 5.

The global footprint of a program is the sum of the footprints of its characters.

Your program must accept a string as parameter, compute its ecological footprint, and output it.

There is a subtlety though. As you wish to enter a new, more restrictive market, you need to tune your program so that it behaves differently in "test mode". Thus:

The program should output 0 when it receives the string test as parameter.

Scoring

The source code with the smaller ecological footprint wins (and yes, the answer test is forbidden!)

\$\endgroup\$
  • 2
    \$\begingroup\$ This anonymous company doesn't happen to be named Volt's Wagons, does it? \$\endgroup\$ – Geobits Sep 25 '15 at 3:20
  • \$\begingroup\$ @Zach Sorry, I rolled back your edits - the horizontal lines were really harming readability ? and the fact that we output 0 only when we receive test is important ? \$\endgroup\$ – Arnaud Sep 25 '15 at 3:33
  • \$\begingroup\$ You could have removed the hr tags.. Also, I added a lot of punctuation and grammar fixes.. I didn't removed the "output 0 only when we receive test" detail either? I only removed the redundant clause. \$\endgroup\$ – Zach Gates Sep 25 '15 at 3:35
  • 2
    \$\begingroup\$ What's the expected output for an empty input string? I'd normally say 0, but "(and only when)" seems to disqualify that. \$\endgroup\$ – Geobits Sep 25 '15 at 3:36
  • \$\begingroup\$ @Zach I've re-reported your changes. Thanks for your help! \$\endgroup\$ – Arnaud Sep 25 '15 at 3:45
  • \$\begingroup\$ Can we assume that the input will never be empty? \$\endgroup\$ – Zach Gates Sep 25 '15 at 6:08
  • \$\begingroup\$ @Zach I would accept empty input and output 0, as the footprint of an empty program is zero ? \$\endgroup\$ – Arnaud Sep 25 '15 at 6:50
3
\$\begingroup\$

Group Students Into Pairs

Synopsis: A graph theory matching problem. Given a list of which students like and dislike each other, pair the students up to maximise the overal happiness of the classroom.

Introduction

If you've ever been a teacher before, you've likely encountered the extremely frustrating experience that is getting students to do pair work. More often than not no one is happy with their partner, and the mood of the classroom suffers.

In this challenge, we're going to solve the enduring problem of pair work in classrooms. Here's how our system will work:

  1. Each student shall write down what students they are happy to work with, and which ones they are not happy to work with.
  2. We will take those lists, and generate student pairs such that the total happiness of the classroom is at its maximum.
  3. The students are now (mostly) happy!

So how is the happiness of the classroom calculated? For each student in each pair of students:

  • If a student's partner is in their "happy to work with" list, increase the happiness of the classroom by 1.
  • If a student's partner is in their "not happy to work with" list, decrease the happiness of the classroom by 1.
  • If a student is neutral towards their partner (not in either list), the happiness of the classroom does not change.

Here's a useful table that summarises the possible changes in the happiness with each pair of students:

+-------------------+-------------------+--------------------+
| Student 1 Feeling | Student 2 Feeling | Happiness Modifier |
+-------------------+-------------------+--------------------+
| Happy!            | Happy!            | +2                 |
| Happy!            | Neutral           | +1                 |
| Happy!            | Not happy...      | 0                  |
| Neutral           | Happy!            | +1                 |
| Neutral           | Neutral           | 0                  |
| Neutral           | Not happy...      | -1                 |
| Not happy...      | Happy!            | 0                  |
| Not happy...      | Neutral           | -1                 |
| Not happy...      | Not happy...      | -2                 |
+-------------------+-------------------+--------------------+

Input

First line of input is a positive integer n indicating the number of students to match up. n is always even. Following that are n lines, each line which has the format:

name likes dislikes

where name is the name of the student (which will only contain characters from [A-Za-z]), likes is a comma separated list of people he or she would be happy to work with, and dislikes is a comma separated list of people he or she would not be happy to work with. For instance:

Clarence Tiger,Anna,Jamal Amelia,James

This would indicate that Clarence is happy to work with Tiger, Anna, or Jamal; he is not happy to work with Amelia or James; and towards any other student he is neutral.

Another line:

Ilya Amelia,Clarence,Anna,Tiger,Jamal _

This would indicate that Ilya is happy to work with Amelia, Clarence, Anna, Tiger, and Jamal. For dislikes, we've used the special keyword _, which indicates that Ilya doesn't have anyone he is not happy to work with. Any remaining students Ilya would be neutral towards.

Output

Output space separated comma separated pairs of names, where each name corresponds to a pair of students. The pairs should be such that the happiness of the classroom is maximised. Every student should be in exactly one pair.

Example Inputs and Outputs

Writing reference implementation. This is one of those types of questions where you can't really judge the correct output for an input "by eye".

Sandbox Questions

  1. This problem is quite difficult compared to typical code-golf fare, requiring two different algorithms to solve the weighted maximum matching problem. Is it too difficult for a code-golf? And if it is, what could make a better winning criterion?
\$\endgroup\$
  • \$\begingroup\$ It's certainly not too difficult for a code golf at present, because there are no time constraints so I could brute-force it. With time constraints I'd have to do some research before tackling it, but it's good to have the occasional code golf problem which can't be solved in 30 characters. \$\endgroup\$ – Peter Taylor Jun 25 '15 at 17:32
  • \$\begingroup\$ I would think the challenge would actually do well with a loose time constraint to prevent brute force. While you'd definitely get fewer answers, those answers would definitely be more interesting \$\endgroup\$ – Nathan Merrill Jun 27 '15 at 1:55
  • \$\begingroup\$ "Jamal Amelia" -- Where is the comma? And I think that this would be fine for code-golf. BTW, add which all characters a name could have in the challenge. \$\endgroup\$ – Spikatrix Jun 27 '15 at 9:42
  • \$\begingroup\$ @CoolGuy There's no space because Jamal is the end of the likes and Amelia is the start of the dislikes. I added in which characters a name can contain. \$\endgroup\$ – absinthe Jun 27 '15 at 11:29
  • \$\begingroup\$ Cool Guy's question raises the point that you should be explicit about cases where a person has no likes, no dislikes, or neither. I.e. can trailing spaces be omitted? Can the entire line be omitted if the person has neither likes nor dislikes but is liked or disliked by someone else? \$\endgroup\$ – Peter Taylor Jun 27 '15 at 14:29
3
\$\begingroup\$

The /\/\aze of Mirrors

sniffs...something smells...fishy.

The reason being that there's actually a fish! But it's at the end of a maze of mirrors that you have control over. Your task is to rotate the mirrors until you can see that delicious-smelling ><>. Luckily, there are only nine mirrors, so it doesn't take you long to find a solution.

However, if you encounter this again in the future, you don't want to have to actually do the work yourself. Computers are so much better at it. So you decide to write some code to solve it for you. The shorter, the better, because you don't want that fish to rot!

The situation

Your program must accept a single positive integer n as input. It then has to find a solution for an n by n mirror maze with the following conditions:

  • You, the observer (>), is seated next to one corner.
  • The fish (F) is placed next to the opposite corner, on the adjacent wall if n is even and on the opposite wall if n is odd.
  • The maze is toroidal because its designers installed cameras and screens.
  • However, there is a wall behind the fish, so you can only see it from inside the maze.
  • You must use all of the mirrors. No shortcuts!
  • Bonus: take an additional non-negative integer x as input and solve the maze for when the fish is x spaces away from the corner (where x=0 is its usual place), flipping to the other wall if x is odd.

Example solutions

1
+-+
>/F
+-+

2
+--+
>/\|
|//|
+-F+

2 1
+--+
>/\F
|\/|
+--+

3
+---+
>\/\|
|//\|
|\/\F
+---+

4
+----+
>/\/\|
|//\\|
|\\//|
|//\\|
+---F+

Rules

  • No standard loopholes, as usual.
  • Your program must output the solution in ASCII like what I've shown above.
  • Scoring is in bytes, unless you have the bonus: multiply by 0.8.

I look forward to seeing all the amazeing solutions! Ha! Sorry, that was bad.

\$\endgroup\$
  • \$\begingroup\$ Can I adopt this abandoned proposal? \$\endgroup\$ – programmer5000 Jun 9 '17 at 12:20
  • \$\begingroup\$ @programmer5000: Yes, you may. \$\endgroup\$ – El'endia Starman Jun 10 '17 at 3:49
3
\$\begingroup\$

Approximate phi using Fibonacci numbers

As shown by Johannes Kepler, the quotient of successive Fibonacci numbers approaches phi.

Thanks, Wikipedia.

(where F(n) = the nth Fibonacci number)

The fine folks at Wikipedia also say that if you choose two different starting values for the Fibonacci sequence, this expression still holds.

Last, but not least, if you use a later number in the series in the numerator, you get some interesting properties:

Thanks again, wikipedia

The challenge

  • Create a full program or function that approximates phi using Fibonacci numbers.
  • The program or function will take a single integer, n (unless a bonus is applied). It will output to STDOUT as follows, stopping when it reaches n:

1/1=1 2/1=2 3/2=1.5 5/3=1.66666666 ... F(n+1)/F(n)=...

  • Fibonacci numbers must be calculated using iteration or recursion.
  • No built-ins / standard loopholes, and neither the square root function nor phi should appear in the source code.
  • It is OK if floating point limitation/integer overflow prevent accuracy beyond 4 or 5 digits, but you should use the most precise primitive data type (yes, double is one character longer than float).

There are two bonuses that you can earn, for a total of a 25% lower score:

  • Input two additional integers as starting values for the Fibonacci sequence. This will still converge on phi, though it may take a bit longer. Reward: -10%.
  • Input one additional integer for a in the above formula. This will result in the sequence converging to phi^a. Reward: -15%.

Scoring

Total score is the size of the program, in bytes, minus any bonuses. Since this is , lowest score wins.

(Insert leaderboard snippet) (Insert example snippet)

Example implementation snippet:

document.getElementById("button").addEventListener("click", process, false);

function process() {
  //Store field values to vars
  var itrNum = parseInt(document.getElementById("itrNum").value);
  var prevNum = parseInt(document.getElementById("start1").value);
  var curNum = parseInt(document.getElementById("start2").value);
  var aNum = parseInt(document.getElementById("aVal").value);
  document.write("(Click \"Run\" to reset)<br><br>");

  //Iterate through each fibbonacci number
  for (var i = 0; i < itrNum; i++) {

    dispNum = getFutureItr(prevNum, curNum, aNum);
    document.write(dispNum + " / " + prevNum + " = " + dispNum / prevNum + "<br>");
    //prepare numbers for next iteration
    var tempNum = curNum + prevNum;
    prevNum = curNum;
    curNum = tempNum;
  }
}

//Helper function for F(n+a)
function getFutureItr(prevNum,
  curNum,
  aNum) {
  var tempNum = curNum;
  for (var i = 1; i < aNum; i++) {
    tempNum = curNum + prevNum;
    prevNum = curNum;
    curNum = tempNum;
  }
  return curNum;
}
<!DOCTYPE html>
<html>

<body>
  Iteration number:
  <input type="number" min=0 id="itrNum" value=20>
  <hr>Starting value 1:
  <input type="number" min=1 id="start1" value=1>
  <br>
  <br>Starting value 2:
  <input type="number" min=1 id="start2" value=1>
  <hr>Value of a:
  <input type="number" min=1 id="aVal" value=1>
  <hr>
  <button id="button">Calculate</button>
</body>

</html>

\$\endgroup\$
  • \$\begingroup\$ There's a fibonacci tag. It's generally worth making it clear which of the two indexing conventions answers to use: F(0) = 0 or F(0) = 1? \$\endgroup\$ – Peter Taylor Nov 2 '15 at 14:37
  • \$\begingroup\$ Does the output need to be in the exact format 3/2=1.5? \$\endgroup\$ – xnor Nov 4 '15 at 21:54
3
\$\begingroup\$

Compete with awk

The goal of this challenge is to see if the assertion often see in question on SO is true:

This would be faster in whatever

Test Input

A 10 million lines file generated by this script line:

awk 'BEGIN{for (i=1;i<=10000000;i++) print (i%5?"miss":"hit"),i,"  third\t \tfourth"}' > file

Head of it:

$ head -10 file
miss 1   third          fourth
miss 2   third          fourth
miss 3   third          fourth
miss 4   third          fourth
hit 5   third           fourth
miss 6   third          fourth
miss 7   third          fourth
miss 8   third          fourth
miss 9   third          fourth
hit 10   third          fourth

Goal:

The main goal is to compete with awk, to benchmark it will be on this challenge description:

  • Split each line on any number of spaces (regex [ ]+)
  • If the line start by hit X with X being an even number
    • print fields: 4th 1st and 3rd (in this order)

Example output (first 5 lines):

fourth hit third
fourth hit third
fourth hit third
fourth hit third
fourth hit third

Restrictions:

The idea being to compete with awk, your program must behave on the same way:

  • The file must be read.
  • The match and output order must be modifiable as an awk program can be (Needing a simple code update is OK, it has not to be a command line parameter).
  • The number of line in input file should be considered unknown.
  • As long as your output can be piped to awk, the submission is valid.

Validation:

Pipe the output of your program to

awk '!seen[$0]++{unq++;r=$0} END{print ((unq==1) && (seen[r]==1000000) && (r=="fourth hit third")) ? "PASS" : "FAIL"}'

If it show PAST, you're in :)

Winner

The fastest code would win, to bench yourself here is a mawk version really competitive (which won't count toward answers as I think it's pretty hard to beat):

awk '/^hit +[0-9]*[02468] / { print $4, $1, $3 }' file

I've build a test suite on github here which build a result table here.

Answers will be integrated within it to bench all answer on the same machine, if there's a specific way to launch your program, make it appear in the answer so I don't penalize your answer by the way it is launched.

Side challenge:

If you wish to save me time and craft a pull request to include your code in the test system, you're welcome.

\$\endgroup\$
  • 2
    \$\begingroup\$ 1. "Split each line on spaces" would IMO split the line miss 1 third fourth into 15 fields. A possible rewording might be "split each line around the regex [ ]+" (where the otherwise unnecessary [] prevent MarkDown from trimming the space). 2. The question as worded is a bit too special-cased, as is the awk code you provide. If it's permissible to optimise the regex to /hit [0-9]*0/ because you know a priori the form of the input, why would it not be permissible to optimise further and write print "fourth hit third\n"*1E6? \$\endgroup\$ – Peter Taylor Nov 19 '15 at 21:02
  • \$\begingroup\$ @PeterTaylor Thanks for the feeback, I reworded a little to be more specific on restrictions and avoid too much test input optimizations. \$\endgroup\$ – Tensibai Nov 20 '15 at 10:20
  • \$\begingroup\$ I still think your reference answer is cheating with /hit [0-9]*0 /. To match the challenge description it should use /^hit +[0-9]*[02468] / \$\endgroup\$ – Peter Taylor Nov 20 '15 at 11:18
  • \$\begingroup\$ @Peter ok, it does no difference in timing at end anyway (at least nothing I've been able to see on slow machines when benchmarking the codes present on GH) \$\endgroup\$ – Tensibai Nov 20 '15 at 11:24
3
\$\begingroup\$

Comedy of exceptions

Your goal is to demonstrate the shortest program or function that can throw 10 different types of errors/exceptions (I use the two interchangeably here) at runtime.

This question is only open to languages which have an object-oriented type system for errors. Furthermore, in the case of each error, a message including a clear identification of the exception's type must be printed. Evidently, it must also have at least 10 error types. Other systems such as an integer error code identifying the error, or all errors represented by strings are not acceptable.

Input is an integer from 0 to 9 inclusive. The program should reliably throw a different type of error for each input.

Methods which allow exceptions of arbitrary type to be thrown may not be used. E.g, throw ....

Determining whether two errors are of different type (TODO: fill in detail of output)

Java: x and y print different stack traces, but are the same type, so they can't be used.

Python: UnboundLocalError ..... and NameError ....... would count as two types of error, since, although UnboundLocalError is a subclass of NameError, type() would give different results for the two.

C++: stoi("aaaa") printing ......... would be valid since the message gives std::invalid_argument. Integer division by zero would not since it crashes the program without a message informing of the error type

Sandbox

Please comment if you are aware of a language that is borderline on eligibility, blurs boundaries between error types, or has other loopholes.

\$\endgroup\$
  • \$\begingroup\$ Would exceptions from standard modules be allowed (e.g. from urllib.error import *)? How about third-party modules/libraries (e.g. django, boost)? Or even custom exception subclasses? \$\endgroup\$ – grc Nov 26 '15 at 11:17
  • 1
    \$\begingroup\$ I don't know if I can find 10 different ones, but CJam can print a number of errors. Some of these are CJam-specific errors (empty stack, type mismatch; these tend to be displayed as "RuntimeException" but with a distinguishing error message) and some of them, I think, are just crashes happening in the interpreter exiting with a Java exception. How would that be treated? (I think it's also different between the Java and the JavaScript interpreter.) \$\endgroup\$ – Martin Ender Nov 26 '15 at 15:01
  • 1
    \$\begingroup\$ To make this more specific, here are 11 different errors (with different error messages), but some are backed by the same exception type within the interpreter. Would these still count as different? pastebin.com/VJCiVYMf (Also note that CJam itself has no concept of exceptions... if there's an error it crashes... these are just the exceptions types used by the interpreter.) \$\endgroup\$ – Martin Ender Nov 26 '15 at 15:14
  • 2
    \$\begingroup\$ I can think of a language which has exceptions but not an object-oriented type system: SML. (Haskell almost certainly has some exception monad too...). \$\endgroup\$ – Peter Taylor Nov 26 '15 at 21:05
  • \$\begingroup\$ @grc I think I will allow standard libraries, but not 3rd-party ones. Any method of defining and throwing a custom exception type should fall under the rule "Methods which allow exceptions of arbitrary type to be thrown may not be used." \$\endgroup\$ – feersum Nov 27 '15 at 0:28
  • \$\begingroup\$ @MartinBüttner It appears that the are Java exceptions and that CJam does not have its own exception type system, meaning it cannot be used. \$\endgroup\$ – feersum Nov 27 '15 at 0:29
  • \$\begingroup\$ @PeterTaylor HM-based type systems should be OK. Maybe I can find a better description than "object-oriented". \$\endgroup\$ – feersum Nov 27 '15 at 0:31
  • 1
    \$\begingroup\$ @feersum Then you should probably clarify what you mean by "error" (because the first sentence says that both errors and exceptions are allowed... just because there's no way to catch the error doesn't mean that language doesn't have errors... and most of these errors are actually thrown by the interpreter on purpose, and not raised by Java due to the interpreter having a bug). \$\endgroup\$ – Martin Ender Nov 27 '15 at 14:18
  • \$\begingroup\$ @sysreq The input is a number when determines which type of exception you should throw. \$\endgroup\$ – feersum Dec 10 '15 at 23:24

You must log in to answer this question.

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