# Sandbox for Proposed Challenges

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

Sandbox FAQ

## Posting

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

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

## Discussion

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

• Parts of the challenge you found unclear
• Problems that could make the challenge uninteresting or unfit for the site

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

If you think one of your posts needs more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended!

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

## Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Get the Sandbox Viewer to view the sandbox more easily!

# But, Is It Art?

• I think it is clear, but the second example of "is not equivalent to" is a little unnecessary in my opinion. – Alex bries Jun 2 at 10:03

# Generalised multi-dimensional chess knight's moves code-golfcombinatoricschessarray-manipulation

Posted

• You know that the necessary conclusion is we do all the pieces - take my +1 and start the chain. – StackMeter Jun 14 at 6:26
• @StackMeter I don't think most of the pieces would be very interesting. Pawns in combination with details of what pieces are already on the board, maybe. Otherwise, it's just this challenge with some slightly simpler vectors – pxeger Jun 14 at 6:48

# Write a C++ demangler

• Is _ZN3foo3barE3baz -> foo(bar)::baz valid? – tsh Jun 7 at 8:39
• That would be foo::bar::baz. The base identifier is baz, and it is prefixed with the namespace foo::bar. – EasyasPi Jun 7 at 14:27
• Won't foo::bar::baz be _ZN3fooEN3barE3baz or _ZNN3fooE3barEbaz? – tsh Jun 8 at 6:14
• No, nested namespaces are placed together without a separator. – EasyasPi Jun 8 at 12:39
• Decided to remove the "if it doesn't start with _Z, then it is to be printed as-is" as that adds unnecessary complexity. – EasyasPi Jun 13 at 23:55
• I've edited this down to a stub now that it's been posted to save space – caird coinheringaahing Jun 17 at 20:30

# Draw an Ascii Grid

• You can use this to visualise a tictactoe game -- might just do that. – StackMeter Jun 16 at 7:32
• Looks great, just leave it for another 2 days before posting! – Recursive Co. Jun 16 at 15:56

# Create word lightning ascii-artstringtree

Posted

• Trees can be taken in different formats, right? – Wezl May 14 at 13:35
• yes, they can be taken in any suitable format. – Razetime May 14 at 13:47

# What's missing

• This is probably too easy – rak1507 Mar 22 at 12:14
• Some languages may have built-in Bag / MultiSet / Counter collection type. And a simple - operate or something similar may get correct result. Will you allow answers use such type of values as input / output? – tsh Mar 23 at 1:41
• @tsh I guess? It doesn't really make a difference for the languages that have creative solutions. It's code-golf, which means answers generally don't get accepted. – A username Mar 23 at 8:22
• ruby does have array-array, but it wont work for arrays with similar items missing. I feel this is easy, but it can work as a codegolf challenge – EliteDaMyth Jun 22 at 9:24
• @EliteDaMyth Honestly, I'm really surprised this doesn't already exist. – A username Jun 22 at 9:33

# On a Collapsing Platform

## Rules

In this KoTH, your task is to not die. It seems simple, right? Well, no.

You're on a platform. A giant platform, of size 100 * (entries) ^ 1.1 units across (this may change if we get a lot of entries). And every few turns, a random tile is removed. As well as this, you, not a small mass in the scale of things, can cause a tile to fall down. Let me explain how this works.

You (the entrant to this KoTH) control a certain number of bots. You (the bots) can then move around on the platform and try not to die. You (still the bots) can move up to 10 units away at base, and can see up to 100 units away (units will be called u from now). However, jumping over a hole costs 2u more, meaning that the largest gap you can clear is three units (3 * 3 for the gap and 1 to land). Do not try and clear 4u+ gaps; you will die. Going off the edge of the platform also is an unwise choice - you will die.

By "you - not a small mass in the scale of things", I mean to say that every step you take takes you closer to your inevitable death - each tile you step on has a hidden durability stat, that will not be revealed to you during the course of the round. When it hits 0, the unlucky bot (hopefully not you (the bot)) on it will be removed with the tile. Do not do this; you will die.

Your weight is a random stat that is decided at the start of your game, and is subtracted from a tile's durability each time you step on it (weights are 150 at base, and durability values in the range of 15000 - 45000 * (entrants) ^ 1/2, or 15000 * 1-3 * entrants ^ 1/2, so it only becomes an issue in the long term, or when a lot of players exist.) Do not forget about this and start camping on the same 10 tiles on the end; you will die.

Everything takes place on a tick system - every 10 ticks, you can do an action (subject to change to 20ish if this is exploitable) and this may well be the most important part of the game - reduce it at all costs - the fewer ticks you waste, the less durability you take off, and the longer you can thread the needle between life and death. Do NOT, and I mean NOT in caps, forget about this - you will die.

There are a few items that you can get that will improve your chances and delay your inevitable death represented by these characters:

-: Removes 1-7% of your weight (or 1-7, whichever is lesser)

=: Increases your speed by 1 (at 13, this will in fact, prove me wrong and let you clear 4u jumps - still not got the + though).

? Increases vision by 5 (allowing you to see 5 more blocks in either direction.

> Reduces your tick delay by 0.1 or 1% of your tick rate, should it drop below 5 (however, before that, you will die most likely.)

+ Duplicates the bot - you start with 10 bots, and each bot left over at the end is worth 10 000 points (1 per tick survived), so this can, effectively, give you 10 000 points free.

Every 10-25 turns, a random platform is removed - unless necessary, this will not drop any bots - the platform chosen will always be empty (just so people don't get unlucky and die at turn 85) unless it is forced not to be - for example, in the endgame, where there is only 10 tiles left. Do not forget this; you will die

## Input and Output

To begin with, you will get a string such as this

0, 111, 132, 122, 133, 211, 201, 212, 233, 310, 323, where:

The first number represents your unique player id, known as PID in the it gang. Then, you get 10 numbers, representing your bots' start positions.

Then, for each turn, for each bot that did not die, you (the player) get a string such as this (shortened to save space):

.___.+>-__u__...+>+-_._

representing the bot's vision.

You must then return an integer, representing how many units you wish to move forward (negative is backwards) (and do not forget that spaces take 2u more, or you will die.); do not try and move more than your speed, or it will be modulo-ed. Errors and invalid input return 0. Note, spaces are represented with ., in the examples and in game.

## Helper functions (to delay your death, hopefully until the end):

info(): gives you a chunk of info, in this format:

PID: 0
Bots: 11
Score: 10000
[
BID: 1
Weight: 97
Speed: 12
Tick Delay: 8.8
Vision: 110
Pos: -932
Score: 830
]

[
BID: 3
...
]


The string is format as such:

• Then, the number of bots you still have.

• Then, for each bot:

• Its bot ID (or BID for the it gang). (Note, BID are cannot be reassigned, so if Bot 2 dies, and then Bot 1 duplicates, it will have a BID of 10, not 2 (also we count from 0) as it would be if they were.)

• Its weight, speed, tick delay and vision, in that order.

• Its position on the platform, in that order.

• Its score.

position(): gives a position of every bot, ordered by their bot ID, or BID (again, only for the it gang).

position(ID): gives the x position for a bot with a specific ID. If that ID has died already, it will return "Dead" - plus the space where it died. If that bot never existed, it will return None.

tickdelay(), weight(), speed(), vision(), tickdelay(ID), weight(ID), speed(ID), vision(ID):

Does exactly what it says on the tin, returns that specific stat for all bots if no ID is given, or the one with that ID should it be given (again, if the bot is dead, it just returns its stats on the turn it died, and if it never existed, it returns None. Make of it what you will).

vision(ID) Gives a specific bot's vision - this is useful for sketching a map of the world in conjunction with position(ID). Note that other bots are represented as s, so if you're lucky enough to get your bot (u) in between two opposing bots (s), feel free to laugh.

You are allowed access to ALL the random functions (apart from random.seed(), however I will use a set of predetermined seeds in a random order to facilitate retesting. There will be a large number of trials done - this is just to aid improvements if you so desire to make them.

Bots can store variables and write to files, but ONLY in their directory. I will find any bot who does this and ban them.

## Scoring

Bots gain 1 point for each turn they survive, increasing by 1 every 100-200 turns. This will be notified with the string Score/turn increased by 1. Every powerup gives +500, except for +, which duplicates the bot, including its score, thus adding its score to your total. At the end, when there is three or fewer tiles left, you gain 10000 + the bot's current score for each bot left alive. This is done for every bot that lives, so people getting 2 or more bots through gain more than those getting 1, and two opposing bots can both get points for their team.

At least 10000 games will be run per round (subject to change), each time resetting all the stats to the base, rerolling RNG and restarting from the beginning.

After as many rounds as I can get through on my PC, the scores will be added up, and the winner gets an accept.

# Meta

Help with a Python controller would be appreciated.

Any specifications need to be made?

Should I edit any formulae?

# Reverse RegEx

Take a regex a as input, output a regex b such that, for each string x, x matches a iff x.reverse matches b.

Here, regex need to support such symbols:

• .(any character expect \n)
• [abc](any character in abc)
• [^abc](any character not in abc)
• x?(appears 0-1 times), x*(appears any amount of times), x+(appears any positive amount of times)
• x{n,m}(appears n to m times, m can be omitted to mean infinite)
• (abc) (?:abc)(group block, () can be referred while (?:) can't)
• \n(refer to the latest match of n-th group)
• ^(begin of string), $(end of string) (or begin/end of line, see flags/m) • |(or, choose one in some choices) • Letters, \n(this n is char rather than variable, line-feed) You need to handle flags i(ignore upper/lower case) and m(multiline, ^ and $ match begin/end of lines rather than string). You can also just pipe the flags and make the containment of regex work for all possible flags, aka. you can treat pipe free. (They refuse to allow or disallow)

Sample Input    Sample Output
/abcd/          /dcba/
/[abc]/         /a|c|b/
/[^abc]/        /[^abc]/
/(.)abc\1$/ /^(.)cba\1/ /$1/            /10% of $10/  Shortest code win • What's the regex flavor/set of allowed features/inputs? Is it for a full or partial match? – feersum May 10 '19 at 9:07 • @feersum Allowed features need discuss. To be a full match ^ and $ can be added – l4m2 May 10 '19 at 9:21
• Why is test case /[^abc]/ there twice? Or is it to give two different example outputs? Since just outputting /[^abc]/ for input /[^abc]/ would be fine. Also, I'm not too familiar with this Regex syntax, but how does /$1/ work, since $ is the end of the match? And why is it /10% of $10/ reversed? – Kevin Cruijssen May 10 '19 at 9:27 • @KevinCruijssen twice to show that same input may lead to different output. /$1/ and /10% of $10/ both match nothing – l4m2 May 10 '19 at 9:32 • "both match nothing" Ah ok.. I falsely assumed the regex would match something. So incorrect (but still valid) regexes are also allowed as input. Maybe it's a good idea to add some comments to the sample outputs, like /10% of$10/ can be anything as long as it doesn't match anything (and maybe put the /(?!a)[^bc]/ or /[^abc]/ for the same input on one line. – Kevin Cruijssen May 10 '19 at 9:37
• You should more rigorously explain what x.reverse means, from the examples it looks like you mean the order of letters is reversed, but some people might be confused. – FryAmTheEggman May 11 '19 at 21:28
• 1) I think x|y is missing in the list of symbols. 2) The behavior of each symbol is underspecified in so many ways. What does [a-z], [[\]], (ab+)*\1, or (((((((((((x)))))))))))\11 do? Do we need to handle any backslash escapes other than newline? 3) Are you sure this is possible? Can you reverse (a(bx*){0,2}c)*\2\1? – Bubbler Jun 22 at 23:38
• 4) Using such a complex flavor of regex is a parsing hell, which I don't recommend with the same reasons as parsing arithmetic. Good challenges about manipulating regexes include this and this. – Bubbler Jun 22 at 23:41
• @Bubbler I'll just don't care [[\]] and assume input only contain letters and \n. (a(bx*){2}c)+\2\1 reverses into (c(x*b)(?:x*b)a)\2\1(c(x*b)(?:x*b)a)*(Handcode, maybe wrong; need some OR to fit your original one) – l4m2 Jun 23 at 0:53
• I'll ask differently: 1) Should we support range notation [a-z] or not? I assume it's not a set of three chars a-z since - is not a letter. 2) I think you have the knowledge that (x)* only captures the last iteration and \1 fails if it is not actually captured. You need to include it in the post. 3) Should we support multi-digit backreference (like \11 being the eleventh)? – Bubbler Jun 23 at 2:06
• A note for the future: a regex with backreferences is no longer a regular expression in the CS sense, and any kind of manipulation on it can easily fall into an uncomputable problem. – Bubbler Jun 23 at 2:20
• Also, about the "pipe free" thing: you didn't define the term "pipe" anywhere, so it only makes the challenge more unclear. "They refuse to allow or disallow" seems like a misunderstanding on your side; see Jo King's comment there. Basically an I/O method is allowed only when the language or the answer format (function or full program) supports it. And regardless of what site policy says, you can allow anything you want as long as you make it explicit (you already did here, so no need to mention the meta post). – Bubbler Jun 23 at 3:41
• I'm pretty sure that the algorithm you have in mind does not handle ((x)|(y))+\2\3 (though it is reversible). I suspect it can be made irreversible if I replace x and y with something more dynamic. – Bubbler Jun 23 at 4:09

# Play Thud

Thud is a game described by Terry Pratchett in his novel, Thud!.

The game simulates a battle between the Dwarfs (in blue) and the Trolls (in green) on an octagonal board with the Thudstone (an impassable space) in the centre of the board.

I have created an environment to play the game and develop game playing code at: https://ajfaraday.github.io/Thud/dist/index.html

The challenge is to write the most successful dwarf or troll player of this game (these will be two separate challenges).

# Rules

Starting with the Dwarfs, players take it in turns to move.

## Dwarf Movement

On the Dwarf player's turn, they can move one dwarf piece either as a walk or a hurl.

Walk: Dwarfs can move as far as they like in any direction until they hit an obstacle (another dwarf, the edge of the board, or a troll). They can only kill a troll by walking if they are only one space away.

Hurl: If two or more dwarfs are in a line (horizontal, vertical or diagonal), they can hurl the dwarf on the end of the line, by the length of the line (e.g. in a line of 3, the dwarf on the end can be hurled 3 spaces). If a dwarf is hurled into a troll, the troll is killed, reducing the trolls score by 4 points.

## Troll Movement

On the Troll player's turn they can move one troll piece, either as a walk or a shove.

Walk: Trolls can move one space in any direction, unless a troll, dwarf or the edge of the board is in the way. Whenever a troll moves, it kills all dwarfs adjacent to it's destination space.

Shove: If two or more trolls are in a line (horizontal, vertical or diagonal) they can shove the troll at the end of the line that number of spaces away, but only if any of the target space's immediate
neighbours contain a dwarf. When a troll is shoved, it kills all dwarfs on or adjacent to it's destination space.

It is not permitted for a troll to land directly on a dwarf by either walk or shove moves.

Each dwarf killed reduces the dwarfs score by 1 point.

## Scores

The score is calculated thus:

• The dwarf player has one point for every dwarf remaining on the board.
• The troll player has four points for every troll remaining on the board.
• The key figure is the difference between these two. This will be used to calculate players' scores in the tournament.

## Ending the game

The game ends when any of these conditions is met:

• There are no dwarfs on the board.
• There are no trolls on the board.
• Both players have declared the game over.
• The game has reached it's cut-off length of 500 moves.

# How to manually play a game

• Hover the mouse over a piece to see it's available moves.
• Safe moves are outlined in green.
• Dangerous moves (which can be killed the next turn) are outlined in orange.
• Killing moves are highlighted in red when the mouse hovers over them.
• Click a piece to select it for the current move.
• Click one of the available moves to move the piece.
• (You can click the relevant 'Make Peace' button to declare the game over according to that player, during their turn)

# How to set up a local instance of the game

You don't have to clone the repository and use it locally to to create an entry, but it helps.

• git clone git@github.com:AJFaraday/Thud.git
• cd Thud
• npm install
• You can then run ./get_answers.sh to get the latest entries from Stack Exchange

If you prefer, you can use the github pages instance at https://ajfaraday.github.io/Thud/dist/index.html

# How to customize a game

• Open /dist/index.html in your browser
• Click 'Customize'
• Select troll and dwarf clients (manual allows direct control)
• Select a turn time in milliseconds (only relevant to non-manual players)
• Click 'Run Game' to see or play the game.
• (Clicking 'Close' will not enact any changes)

# Clients

The game is played by clients, which represent either a troll or a dwarf player. Each is a JavaScript class which must have these three functions:

• constructor(controller) - controller is an object which acts as your interface with the game (see below).
• turn() - This is called whenever it is your players turn to move.
• end_turn() - This is called after your player's turn is over. It can not move pieces, but can make decisions on whether or not to declare the game over.

## Controller

The controller object is your client's interface with the game itself. You can find full documentation for the controller class here: https://github.com/AJFaraday/Thud/blob/main/docs/controller_interface.md

It provides these methods to interrogate the state of the game:

• turn() - Current turn of the game

• scores() - The current score

• spaces() - Every space, and what's in it

• space_info(x, y) - Detailed information on any space on the board.

• dwarves() - The location of every dwarf

• trolls() - The location of every troll

• pieces() - All pieces belonging to the current player (equivalent of dwarves() or trolls())

• indexed_dwarves() - The location of every dwarf with a fixed index

• indexed_trolls() - The location of every troll with a fixed index

• previous_move() - What got moved to where last turn

• killing_moves() - All moves which can kill one or more opponent

• current_space - Currently selected space (not a function)

• clear_space() - Empties currently selected space These methods are used to actually make your move:

• check_space(x, y)- Find out what moves are available from a given space

• select_space(x, y) - The player decides to move a piece at space.

• check_move(x, y) - Find out what will happen if you move to a place

• move(x, y) - The player moves the current piece to the selected space.

These are concerned with ending the game:

• declare(game_over) - Say whether or not your player thinks the game is over.
• opponent_declared() - Has the opponent declared the game over?

# How to write a client

Warning: There is an issue with the project on Firefox (https://github.com/AJFaraday/Thud/issues/3) which prevents editing the code in the browser. This has been confirmed to work in Chrome.

• Open 'dist/index.html' in your browser.
• Click 'Customize'.
• Select 'dwarf/template' as the Dwarf player (or use another client as a starting point).
• Click 'Edit' beside the Dwarf player select.
• Write your client code in the text box provided.
• The Validate button will change colour based on whether or not the client is passes validations (see below).
• When you're happy with it, click 'Apply' (This can be done before it passes validation, but it may not actually work).
• Select a worthy opponent and click 'Run Game' to see the game.

## Validations

In order for a client to work, and therefore be enterable in the challenge, it has to pass these validations:

• It must evaluate as Javascript code.
• The code must return a class, with a constructor which accepts one argument.
• Instances of this class should have functions named turn() and end_turn()
• The client must play a game until it is over (i.e. it must call a valid move during every turn call). The validator will run games against default opponents to determine if this happens.
• Does not have any forbidden terms ** game. - Only interact with the game via controller ** Math.random - Please keep it deterministic ** setTimeout or setInterval - Keep it sequential
** eval, require or import - Just don't

You can open the developer console (F12) to see more detailed information on your client's validation process.

## How to save a client

If you have cloned the git repository, you can save your entry for future tinkering. This step is not required for entry in the challenge, but it may be helpful.

• Edit a client, as above.
• When you're happy with it (preferably if it's passing validation, too), click 'Copy' from the edit interface.
• Create a .js file in /src/clients/dwarf/entry with the name of your entry e.g. /src/clients/dwarf/entrygreat_dwarf_player.js. (This folder will not be wiped by get_clients.js)
• Run node script/get_clients.js from the Thud directory to make your entry available from the Dwarf player select. You only need to do this once to make it avilable.
• npm run build - this will keep watching for changes in your entry and updating the package.

## How to enter your client in the competition

• Decide on the name of your client, your client_name must only have alpha characters and underscores.
• The first line of your answer should be your client's name as a title (with = characters under it on the second line)
• There should be a code block containing the class for your entry (with or without the preceeding module.exports =)
• After that please include a brief explanation of your client's behaviour, and any other information you'd like to include.

Once this is in place, anyone running ./get_answers.sh will see your client available under your username.

The GitHub Pages instance will also be updated periodically. So by making an entry, your code will be added to the repo.

# Tournament rules

The tournament will pit every available dwarf client (in /src/clients/dwarf/) against every available troll client (in /src/clients/troll/), and each pairing will play exactly one game.

The difference between the two players' scores will then update a running total for each client. The winner will gain the difference, and the loser will lose the difference.

There are two winners in the tournament, the most successful troll player and the most successful dwarf player.

According to the rules, after playing a game, the players swap sides, so please also write an entry on the Troll challenge.

This is now nearly complete (apart from some UI improvments and presenting the tournament results a bit more nicely). There's a working example of the code importer working against these two meta questions:

I could really use someone to attempt an end-to-end run at creating a client and adding it to one of these to check that my instructions are clear and everything works.

• Very well described challenge. Seems nice! – EliteDaMyth Jun 20 at 14:17
• @EliteDaMyth Thank you for taking a look. Glad it looks complete. – AJFaraday Jun 20 at 22:43
• Two rule questions: 1. in which direction can be hurled/shoved? 2. It is not permitted for a troll to land directly on a dwarf by either walk or shove moves. but both troll moves have lines like kills dwarfs on … destination/…only if the target space … contains a dwarf. – xash Jul 2 at 14:17
• @xash Good questions, I'll update to be clear. The answer is always 8 directions vertical, horizontal and diagonal. Also, I learned about the rule that trolls can't land on anything after writing the rules. I should have updated the steps too – AJFaraday Jul 2 at 14:31

# Print this sequence I just made up

• Your test cases are correct. (Confirmed with an ungolfed integer implementation.) – Arnauld Jun 27 at 0:05
• Your code must not fail due to floating point errors. If the language used doesn't have arbitrary-precision integers, an integer implementation may fail because of integer overflow before a floating point implementation fails. :-/ – Arnauld Jun 27 at 0:13
• @Arnauld Thanks for confirming my testcases. Would saying that you cannot use floats work? – A username Jun 27 at 0:34
• I think the current wording is fine. It's just weird that prohibiting floating point errors is likely to lead to integer implementations that are actually worse. – Arnauld Jun 27 at 0:41
• @Arnauld Oh well. – A username Jun 27 at 0:44

# Splinter metagolf

• An example for a short repetitive string would be nice – pxeger Jul 12 at 9:42
• @pxeger Ok, I'll have a look. – A username Jul 12 at 9:43

## Which character to change (Robbers)

• I think cops should definitely be able to choose what strings they print (they obviously should reveal them to the robbers) – pxeger Jul 13 at 8:30
• @pxeger that's a good idea – math Jul 14 at 13:45
• Minor suggestion: Move the expected outputs to the start, because you have to scroll all the way to the end to see them. – user Jul 19 at 23:59
• @user Done, thanks. – EphraimRuttenberg Jul 21 at 4:36

# Solve the halting problem for \c^/a*b*/a*b*/[ab]*$ccode-golfhalting-problem ///, a.k.a. Slashes is an esoteric programming language with simple two operations. One is to output its source to remove from it. The other is to substitute itself. For simplicity I am assuming the case when the program matches \c^/[^/\\]*/[^/\\]*/[^/\\]*$c, which is /pattern/replacement/rest but no more special characters than two slashes.

Given pattern, replacement, and rest of the program, determine whether the program halt or not.

Assume that pattern and replacement are already escaped. Also your program/function/snippet must distinguish two or more characters.

# Examples

pattern,replacment,rest: Does it halt?
"","","": No
"foo","foobar","foo": No
"1","0*","110010": Yes


# Meta

• Were similar things ever done before?
• /// is turing-complete, so this is not possible – pxeger Apr 25 at 12:33
• Should we simplify it more? – tail spark rabbit ear Apr 25 at 20:23

# Quantum quine

• when you say different, do you mean in a different position, or a different character, for example when removing the first character of aba, does an output of ab work? – Jo King Mod 2 days ago
• @JoKing Different character altogether, so no, it doesn't. – A username 2 days ago

# Metagolf: Catlike Piet

The goal of this is to write a catlike program, which would be executed (in a Unix environment, though you needn't stick to that) by the following:

yourprogram < file > output
piet output


where piet output writes the contents of file to stdout. That is, you're to generate a Piet program which prints the input to yourprogram.

One-liners

Straight line programs can be written in Piet... in straight lines. If you're willing to take a hit to your score, your output can take the form of a string of commands:

=  none (continue color block)
|  push
^  pop
-  subtract
*  multiply
/  divide
%  mod
~  not
>  greater
.  pointer
\  switch
:  duplicate
@  roll
$input number ? input character # output number ! output character  which is trivial to convert to a Piet program with the following (partially golfed) Python code: def P(s): h=v=0;l=len(s)+1;R="P3 %i 2 255 192 0 0 "%(l+2) C=[1,3,2,6,4,5];V=[0,192,192,255,0,255] for x in map("=|^+-*/%~>.,:@$?#!".find,s):
C=C[x//3:]+C[:x//3];V=V[x%3*2:]+V[:x%3*2]
for i in [1,2,4]:R+="%i "%V[(C[0]//i)%2]
return R+"255 "*4+"0 0 "+"255 "*l*3+"255 0 0 "*2


The dimension of said program is (n+3) x 2 if there are n characters in the string.

Scoring

Your code will be judged on the maximum dimension of the images that it outputs.

• Part 1: Take the maximum score taken over all ascii codes (that is, single-character inputs), discounting EOF.

• Part 2: Take the score for the input "Hello. My name is Inigo Montoya. You killed my father. Prepare to die."

Your score is the product of the scores in part 1 and part 2.

Punishment: Double your score if you write one-liners as above (that is, if you don't output an image).

Bonus: If your program is written in Piet, take the square root of your score above.

• It took me a while to understand the task as "Write a program taking INPUT which produces as output a piet program that takes no input but produces INPUT." I think it is a interesting and challenging, but it's reception will depend entirely on how many people are willing to learn/futz-around-in/deal-with piet. And I have no feel for how many that is. – dmckee --- ex-moderator kitten Jul 7 '11 at 3:12
• @dmckee; would it be better if I just used a reduced instruction set, and only ask for the instruction stream? I think this is still challenging with {push 1,duplicate,add,subtract,multiply,output}. Come to think of it, if I restrict to {push 1,duplicate,add,output}, there's a reduction to some awesome algorithms. – boothby Jul 7 '11 at 4:48
• I did this in piet some time ago: craigoclock.blogspot.com/2011/05/metaprogramming-in-piet.html – captncraig May 21 '12 at 18:31
• 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.) – user58826 Jun 9 '17 at 15:22

## Play Simple 2-Dimensional Minecraft

Recently I found this video of "HansLemurson" showing a computer that was built in minecraft, which runs minecraft. He is playing minecraft on a computer that was built in minecraft that is running on his computer. To be specific, it is a two dimensional version with an 8x8 grid of cells. There is gravity, block placement, and even jumping. It is worth noting that the computer is single purpose. The same person has built programmable computers, but making them single purpose allows the computer to be much smaller.

## Details

The minecraft world is an 8x8 grid (one horizontal and one vertical dimension). The grid is comprised of either Xs (representing blocks) or empty spaces. The player is an X that is blinking on and off about once every second.

There are two modes in the game, controlled by a toggle switch. The first mode is movement. This is controlled by a WASD-like button arrangement. If the player chooses to move left/right/down, the computer checks to see if the space immediately in that direction is empty. If so, then the player moves into that space.

If the player chooses to move up, then the computer checks that the block underneath the player is solid. If so, then the player moves upward two units. Notice that this can propel the player into a solid block. If this happens, the player is obscured by the solid block, but can still move to an empty block next to him. When the player is inside on a solid block, the game continues as if the block isn't there, although the block is still there once the player leaves it.

After each move, the player falls down one unit if there is empty space there. This simulates gravity. This is also why moving up moves up two units, so that the gravity makes a net movement of up one unit. Gravity does not cause the player to fall all of the way to the ground, just one unit.

The second mode is block placement. In this mode, the same exact WASD buttons are used. Instead of moving the player, they toggle the state of the block in that direction. If the player presses "left" and there is a block there, then the block is destroyed. If there is not a block there, then a block is placed. Again after this move, the player is again subject to gravity. The blocks are not subject to falling.

Toggling the toggle switch does not count as a move, and does not invoke gravity.

The game board is a torus, so all actions (movement, block creation) can wrap around the board. The board does not scroll with the player. The player moves, and the blocks stay in the same place.

## The challenge

You challenge is to write the shortest program that simulates this game. Your program should display and update the map correctly (with Xs as blocks, and with the blinking player). It should accept input from a button that toggles the state and four buttons for movement and actions. This is code golf.

There are imaginary bonus points for adding more features (block types, game size, etc) to your game.

## Suggestions?

• With more complicated challenges I find that it helps to do a reference implementation so that you have a very concrete idea of how much work is involved. Aside from that, I like it. – dmckee --- ex-moderator kitten Jun 3 '12 at 20:11
• Is the blink rate selected to fit with the ANSI escape sequence? Either way I would explicitly allow that, because it's the obvious way to do it on compatible terminals. – Peter Taylor Jun 5 '12 at 7:14
• The blink rate wasn't selected to be anything specific. I think that I will broaden the restriction. Maybe any blink rate between 3 blinks per second to 1 blink every 2 seconds. – PhiNotPi Jun 5 '12 at 20:21
• @programmer5000 No, for two main reasons: First, challenges can go extended periods of time in the sandbox before they are posted and/or adopted. In the past I've posted challenges after not touching them for 4 years. Second, deleting this answer will not reduce lag, as deleted answers are still present, simply not visible. Users with sufficient rep will see all 4040 answers in the sandbox, and you will too once you earn the "view deleted answers" privilege. – PhiNotPi Apr 13 '17 at 18:15

Overview:

Let's say you've decided to operate your computer using voice recognition software, but unfortunately you did a horrible job researching the various products out there and chose a package that does not recognize numbers as numerals, only words. (i.e. "one" (spoken) == "one" (typed), not "1".) Rather than spend more money to get another option, you decide to make do. Now you want to use the computer's calculator, but this poses a problem, since your machine doesn't know how to add "one plus one".

Objective:

Implement a basic calculator that will read in a string of the written-out equation, perform the correct calculations, then return the result in its text form. Your code should be as short as possible; this is code golf.

Rules/Constraints:

• Input/output will be using your preferred method (STDIN, ARGV, etc.).
• Your calculator must be able to handle input and output within the billions (non-inclusive) -1,000,000,000 < i < 1,000,000,000, but you may expand to more if you wish.
• Decimal values and/or parts must be accepted (0 < i < 1) up to 3 places/digits.
• When calculating answers, proper rounding must be used, so "three point one four one five nine two six" must be returned as "three point one four two".
• Basic calculator functions required:
• "Add"/"Plus"/"Sum"/"And" (+)
• "Subtract"/"Minus"/"Remove" (-)
• "Multiply"/"Times" (*)
• "Divide"/"Divided"/"Divide by"/"Divided by" (/)
• "Raise"/"Exponent"/"Power"/"To the power of" (^)
• "<Base>Root"/"<Base>Radical" (√)
• "Point"/"Decimal" (.)
• "Pi" (π)
• All strings in the list above must be accounted for in your code, capitalization does not matter.
• Numbers may be presented as their full value ("one thousand") or by digit (one zero zero zero).
• Negative numbers may be assigned using "Minus" or "Negative".
• The string "Minus" bust be accounted for as an operator and identifier. (see example)
• "And" is only acceptable as an operator, not as part of a named number.
• "one hundred and one"
• "one hundred one"
• "a" or the absence of a number does not equate to any number; all numbers will be explicitly accounted for in the program input.
• "a hundred" does not equate to "one hundred" and is not a valid input.
• No more than 2 terms will be used.
• "one plus one minus one" will not be implemented.
• If an invalid input is supplied, your function/program should handle the error and exit gracefully with an error description.

Example I/O:

• "one add one" --> "two"
• "five thousand thirty four subtract ten thousand six hundred" --> "negative five thousand five hundred sixty six"
• Alternatively: "five zero three four subtract one zero six zero zero"
• "three root twenty seven" --> "three"
• "ten minus minus ten" --> "twenty"
• Alternatively: "ten subtract negative ten"

## Sandbox Questions:

1. Is this too basic/complicated? (I'm assuming some languages will handle this much more simply than the method I have in my head...)
2. Does the title fit?
3. Are there any constraints that should be added/lifted?
4. Are any more examples needed for clarification?

• Not everyone says numbers the same way. Does the parser have to treat the following as equivalent? "negative one hundred five", "minus one hundred five", "negative one hundred and five", "minus one hundred and five", "negative a hundred five", "negative a hundred and five", ...? – Peter Taylor Jun 15 '12 at 15:12
• @PeterTaylor I had had a similar thought re: operators. ("plus" versus "add", etc.) I think it would be more interesting to account for all, but given the wide variety of possible inputs, it may generally be better to limit the options to a specifically defined set (which I have yet to define). – Gaffi Jun 15 '12 at 15:18
• @PeterTaylor I've added some of these details. Please let me know if there's anything unclear about them. – Gaffi Jun 15 '12 at 16:10
• I don't spot any ambiguities in the parser. There is still an ambiguity relating to decimals, though. What precision should be used? Also, I notice now that there's no winning condition. Is this intended to be code-golf? (Ugh - tons of strings which will have to be hard-coded in most languages. I expect Perl has a suitable parser already in CPAN, though...) – Peter Taylor Jun 19 '12 at 9:03
• @PeterTaylor I don't know where I went... I've updated the spec. re: decimal places and objective. – Gaffi Jun 29 '12 at 13:24
• @PeterTaylor metacpan.org/pod/Lingua::EN::Words2Nums – msh210 Apr 27 '16 at 20:37

# Huffman Decoding

Write a programm which takes two strings as input and prints a text.

The first argument is a Huffman Tree, serialized in the following format:

• every ascii character except ~ is always a leaf, if ~ is the first characater it is also a leaf.
• <tree0><tree1>~ is a tree where <tree0> is the left subtree and <tree1> is the right subtree.

Example: ab~cde~~~ generates this tree:

 ┌─┴─┐
┌┴┐ ┌┴─┐
a b c ┌┴┐
d e


where a would have the key 00, b 01, c 10, d 110 and e the key 111.

The second argument is a text that has been compressed with with the Huffman code that is defined by the first parameter. This bit-string can contain any bit sequence (also null-bytes and non-printable characters) and is not byte aligned, therefore it has been encoded with a variation of the standard Base64 encoding:

• the characters used for the encoding are the standard base64 characters: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
• the bitstring is broken up into 6-bit chunks and mapped to this characters
• if the last chunk is smaller than 6 bits, a character with this prefix is used, and padding characters are added to the string:
• - : the last chunk was five bits long
• = : the last chunk was four bits long
• =- : the last chunk was three bits long
• == : the last chunk was two bits long
• ==- : the last chunk was one bit long

Example:

bits:       1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 1
chunks:    |1 1 1 1 0 1|1 0 1 0 0 1|1 1 0 1 0 1|0 0 0 1 1 0|1[0 0 0 0 0]|
characters:       9           p           1           G           g
base64:     9p1Gg==-


Your programm has to decode the text encoded in the second parameter and print it to stdout.

You have to provide your source code encoded in the way described above. The length of your encoded source code + the length of your serialized huffman tree will be the winning criterion.

TODO: example input

• It would be helpful to explicitly state the 64 characters used in the encoding. I presume they're A-Za-z0-9+/ but (especially if you're expecting people to implement that part explicitly) it's best to make the problem self-contained. – Peter Taylor Oct 8 '12 at 16:23
• 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.) – user58826 Jun 9 '17 at 15:30

## Code golfing problem: Surface classification

The task: Given a surface-word reply with the classification of what surface it is.

Example 1: Input: aba'b' ----> Output: 1T

Example 2: Input: aabcb'c' ----> Output: 3P

Bounds on the problem: Since there are only 26 letters, there will never be more than that many labels. Additionally output should be in the form S,nT,mP for n,m positive integers.

Background: In the study of algebraic topology students are often presented with diagrams such as the one below. The represent instructions for how to assemble a surface. The assembly is prescribed as: if there are two edges labeled with the letter x then glue them together so that the arrows point the same direction. To make our job easy, topologists have discovered an algorithmic way to classify surfaces using 'words' assembled from these 'plane gluing-diagrams'.

Choosing a corner arbitrarily (top right) and orientation (ccw) we read off the labels on the edges where an inverse appears wherever the arrow points against the orientation. In this case the 'word' that represents this plane model is given as abab.

A surface word is a string that contains the letters a,b,...,@ up to some letter @ and each letter is contained in it exactly twice. In the two occurrences of each letter: 0, 1, or 2 of them may be postfixed by a ' which I am considering using to represent 'inverse' (opposite orientation).

If in a surface word all letters appear twice: once without the ' and once with it (f.ex. ba'b'a) then we say that the surface the word represents is orientable. If a surface is orientable then it is necessarily the direct sum of n Tori for some non-negative integer n. If this condition doesn't hold (like in aab'b) then the surface represented is non-orientable: in this case it is the direct sum of m Projective Planes for some positive integer m.

Once you have found out if the reduced word is orientable or not, the final answer is given as follows. If orientable and number of unique letters in the reduced word is 1 then output should be S. Otherwise if the number of unique letters in an orientable word is n (it will be even) then the output should be sT where s = n/2. If the word is non-orientable then the output should be mP where m is the number of distinct letters in the reduced word.

The goal is to take as input some surface word, reduce it via reduction rules 1-6 and then classify it as a sphere, some number of connected tori, or some number of connected projective planes. Here are the 6 reduction rules where ~ represents 'reduces to':

Let M,A,B,C,D be surface words, x be a single letter, and juxtaposition represents concatenation:

1. Cycle Rule: If M = AB then M ~ BA
2. Flip Rule: M ~ M'
3. Sphere Rule: Axx'B ~ AB
4. Block Rule: ABC ~ ADC if B is a surface word and B ~ D by 1 or 2
5. Cylinder Rule: If M = AxBCx'D, then M ~ AxCBx'D
6. Möbius Rule: If M = AxBxC then M ~ AxxB'C ~ AB'xxC

I am looking for input on:

• should this be code-golf or programming-challenge?
• how would scoring work?
• ???

If I feel satisfied with the question in a few days I'll post it to the site.

• If, for each input, there is only one correct output, then it should probably be code-golf. The scoring criteria would then be source code length. – PhiNotPi Jun 8 '13 at 14:33
• Yes, this is the case. In general however there is not a unique series of applications of the reduction rules for any given instance. – Kaya Jun 8 '13 at 16:21
• I don't think the order of explanation is correct. You should explain reduction before talking about "the reduced word". And "reduce it via reduction rules" doesn't entirely make sense, because the rules are presented as equivalences rather than reductions, and most of them don't have a "natural" direction. – Peter Taylor Jun 10 '13 at 8:49
• It's also occurred to me that you haven't defined the notation M'. Does it just consist of toggling the orientation of each token, or does it also reverse the entire string? And do you have test cases which between them force implementation of all of the reduction rules? – Peter Taylor Jun 11 '13 at 8:32
• Good call on the string inverse, yes you have the right idea and I will make it clear. I have a lot of test cases from when I did a number of these computations by hand in a university course and (anecdotal experience) I am pretty sure that it is possible to force the use of all the reduction rules (except maybe 4 which is really just a meta-rule for convenience when doing proofs). Additionally you have alerted me to some concerns regarding the form of the proper output: it's definitely underspecified. I'll put some work into this today. – Kaya Jun 11 '13 at 14:04

I have no idea how to create a good code golf question!

See this description of a ray tracer with source code that fits on a business card. The author stopped when the code size was 1337 bytes.

Achieving identical output, optimise for minimum code size. Execution time is not relevant.

• I think what you have here is a straight ahead golf. All languages. You need only define the requirements. Do you want identical output or do you want "good output encompassing <list of features>"? – dmckee --- ex-moderator kitten Oct 6 '13 at 17:22
• For a minimum feature list I'd suggest something like (1) it is ray tracer (2) supports point-like lights and shadow + ambient light (3) supports mirrored (implies reflection) and matte surfaces (3) all objects are sphere and overlaps are allowed. With no requirement for (a) anti-aliasing; (2) finite sized light sources; (c) atmosphere effect or (d) depth of field; or (e) tiling and gradients. Notice however, that the example supports at least (b), (d) and (e). – dmckee --- ex-moderator kitten Oct 6 '13 at 17:29
• BTW--The one you linked can get a little bit more with #define Q return (R was already taken for the rand wrapper) and #define O operator. – dmckee --- ex-moderator kitten Oct 6 '13 at 17:33
• I suggest reading the Teapot question in the sandbox Mk IV and the comments - it's not the same question, but some of the same issues are relevant, and it might give you ideas for improvements to the spec. – Peter Taylor Oct 6 '13 at 22:48
• Yes. Read the teapot question for guidance. Ultimately I decided that one was too big, but we did get into some pertinent details. – luser droog Dec 1 '13 at 9:48
• This sandbox post has had little activity in a while and little positive reception from the community. Please improve / edit it or delete it to help us clean up the sandbox. – user58826 Jun 9 '17 at 15:32

# Count unique characters in text.

Given a string for input, output the unique non-whitespace characters in that string along with a count of their occurrences. The list should be sorted in ascending order of ASCII code.

Examples

Input:

Hello, World!


Output:

Character    Count
!            1
,            1
H            1
W            1
d            1
e            1
l            3
o            2
r            1


Input:

The quick brown fox jumps over the lazy dog.


Output:

Character    Count
.            1
T            1
a            1
b            1
c            1
d            1
e            3
f            1
g            1
h            2
i            1
j            1
k            1
l            1
m            1
n            1
o            4
p            1
q            1
r            1
s            1
t            1
u            1
v            1
w            1
x            1
y            1
z            1


The actual formatting (headers, spacing, etc) of the on-screen output is up to you. The only conditions are that it must be sorted in ascending order by ASCII code, and it must be easy to tell what represents a character from the string and what represents a count of a given character. (For example, given a string of 99999999, the output should be explicit so that it is not confused as saying I have 9 8s.)

Ultimate challenge (taken from here):

JKqdJg+oJgiowgyIJgkS+gyxJdeS+gyxJ4yoJdybJdioJdqIJ4kS+KwFJ4QS+gzYJg+ow4vIJ4yxvd+IJgy=+dv=JdQx+gzbJrzx24zYJgkxJ4qLJKQxJ4yxJKqx+KqdJKqdJg+oJgiowgyIJgkS+gyxJdeo24yxJm+xJdybJdioJdqIJKi=J4wF+dvS+gzYJg+ow4zYJ4yxvdy=J4i=+Kv=JdQo+KqxJrzdJKzYJgkxJ4qLJgkxJ4yxJKvSJ4qbJKqdJg+oJgiowgyIJgkdJgyxJdeo24yxJm+xJdybJd+oJd+S+dz=J4wF+dvS+g+SJg+ow4vIJ4yxJ4voJgy=+dv=+dzdJgqxJrzdJKzYJgkS+dweJKQxJ4yxJKvSJ4qbJKq=24yYJgiowgyIJgkdJgzdJryo24yxJm+d24zxJd+oJdqIJ4kS+KwFJ4QS+gzYJ4y=2gzYJ4yxJ4voJgy=+dv=+dzdJgqxJrzx24zYJgkS+dweJKQxJ4fK+dQSJ4qbJKq=24yYJgiowgyIJgkS+gzdJryS+gyxJ4yoJdybJd+oJd+S+dz=J4wF+dvS+gzYJ4y=2gvIJ4yxJ4voJgy=+dv=JdQo+KqxJrzx24zY+dzS+dweJKQxJ4yxJKqx+KqbJKq=24vbJdyowgyIJgkdJgzdJryS+gyxJm+d24zxJdioJd+S+dz=J4wF+dvS+gzYJg+ow4vIJ4yxJ4voJgy=+Kv=JdQx+gzbJrzx24zYJgkS+dweJgkxJ4yxJKvSJ4qdJKq=24yYJgiowgyIJgkdJgzdJryS+gyxJ4yoJdybJd+oJdqIJKi=J4wF+dvS+gzYJg+ow4vIJ4yxJ4v=J4i=+Kv=+dzdJgqxJrzx24zYJgkS+dweJgkxJ4fKJ4qx+KqdJKqdJg+SJdyowg+oJgkS+gyxJdeS+gyxJ4yoJdybJd+oJdqIJ4kS+KwFJ4QS+g+SJ4y=2gzYJ4yxJ4v=J4i=+Kv=JdQo+KqxJrzx24zY+dzS+dweJKQxJ4yxJKvSJ4qbJKqdJg+oJgiowg+oJgkS+gzdJryo24yxJ4yoJdybJdioJdqIJ4kS+KwFJ4QS+g+SJg+ow4vIJ4yxvd+IJgy=+dv=JdQo+KqxJrzdJKzY+dzxJ4qLJKQxJ4yxJKqx+KqdJKq=24vbJdyowg+oJgkS+gzdJryo24yxJ4yoJdybJdioJd+S+dz=J4wFJ4QS+gzYJg+ow4zYJ4yxvd+IJgy=+Kv=+dzdJgqxJrzdJKzYJgkxJ4qLJgkxJ4yxJKvSJ4qbJKq=24vbJdyowgyIJgkdJgyxJdeo24yxJm+xJdybJd+oJdqIJKi=J4wF+dvS+g+SJ4y=2gvIJ4yxvd+IJgy=+dv=+dzdJKzbJrzdJKzY+dzS+dweJgkxJ4yxJKvSJ4qbJKq=24yYJgiowg+oJgkS+gyxJdeo24yxJ4yoJKzxJd+oJdqIJKi=J4wF+dvS+gzYJg+ow4vIJ4yxJ4v=J4i=+dv=+dzdJgqxJrzx24zYJgkxJ4qLJKQxJ4fKJ4qx+KqdJKqdJg+oJgiowgyIJgkS+gzdJryS+gyxJm+d24zxJd+oJdqIJKi=J4wFJ4QS+gzYJ4y=2gzYJ4yxvdy=J4i=+Kv=+dzdJKzbJrzx24zY+dzxJ4qLJKQxJ4yxJKqx+KqdJKqdJg+SJdyowg+oJgkdJgzdJryo24yxJm+d24zxJd+5


• This isn't really an interesting problem. The shortest answer is almost certainly going to be fewer than 10 characters. – Peter Taylor Dec 11 '13 at 12:19
• @PeterTaylor While I mostly agree with your comment - already the header line may contain more than 10 characters. – Howard Dec 12 '13 at 6:15
• "The quick brown fox jumps over the lazy dog." contains "e" three times. – Howard Dec 12 '13 at 6:16
• @Howard Thanks. I must be blind - it took me about five times of reading your comment to find it. Also, do remember that the header is optional to a certain degree - you just need to make sure the output is unambiguous as to which items are characters from the string, and which are character counts. – Iszi Dec 12 '13 at 7:02
• My brain instantly went into bash mode. wc and uniq practically solve half of this, but not in any particularly short manner. – Rob Dec 17 '13 at 20:31

This is my first try at writing a challenge. Please let me know how I can improve it.

# Roman Calculator

Create a basic calculator for Roman numerals.

### Requirements

• Supports +,-,*,/
• Input and output should expect only one prefix per symbol (i.e. 3 can't be IIV because there is two I's before V)
• Input and output should be left to right in order of value, starting with the largest (i.e. 19 = XIX not IXX, 10 is larger than 9)
• Left to right, no operator precedence, as if you were using a hand calculator.
• Supports whole positive numbers input/output between 1-4999 (no need for V̅)
• No libraries that do roman numeral conversion for you

### For you to decide

• Case sensitivity
• Spaces or no spaces on input
• What happens if you get a decimal output. Truncate, no answer, error, etc..
• What to do for output that you can't handle. Negatives or numbers to large to be printed.

### Extra Credit

• -20 - Handle up to 99999 or larger (numbers with a vinculum)

Sample input/output

XIX + LXXX                 (19+80)
XCIX

XCIX + I / L * D + IV      (99+1/50*500+7)
MIV


The shortest code wins.

• You might want to be explicit about which variants of Roman numerals need to be supported. For example, do I have to understand IV as 4, or can I require that it be written as IIII? And what about, say, writing 8 as IIX instead of VIII, 19 as IXX or XVIV instead of XIX, or 99 as IC instead of XCIX? (All these variants have, AFAIK, been used classically.) – Ilmari Karonen Feb 9 '14 at 22:36
• @IlmariKaronen thanks. I modified the question to be slightly more specific about that. – Danny Feb 10 '14 at 14:09
• I think that using IV, IX, IC, XC, etc. should be alright, but only allow one prefix. Also, 19 should be written XIX, not IXX. One other thing, can we assume that the operators will be separated by a space, or no? – user10766 Feb 12 '14 at 0:32
• 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.) – user58826 Jun 9 '17 at 16:06
• 1. I don't need to handle I/III but need to handle I/III+II/III? 2. For the extra can I output maybe [V] for 5000? – l4m2 Apr 12 '18 at 15:05
• @programmer5000 it was posted to main awhile ago. codegolf.stackexchange.com/questions/20670/… – Danny Apr 26 '18 at 11:58

## Golf a random Human Genome fragment with non-random features

A totally random genome fragment is easy enough: just spit out the letters ATCG in random order, and you're done. So let's try something a little less random and more useful to science.

• Accept an argument from the user for number of base pairs (20bp-10000bp must be supported, more if you wish)

• Accept an argument from the user for GC content. This indicates how frequently the generated sequence should contain the G and C bases as a percentage of total sequence length.

• Include at least one complete gene in every request of 500bp or more, where a gene is defined as an otherwise random sequence that begins with a start codon triplet (ATG) and ends with the first stop codon triplet it encounters (TAG, TGA, or TAA). The distance between the start codon and the stop codon does not have to be a multiple of 3.

• Vary gene content (the portion of the fragment that is "gene", inclusive of the gene's start and stop codons) linearly with respect to GC content (when sequence >= 500bp). At the extremes, when GC content is 0%, gene content is 10%; when GC content is 100%, gene content is 60%.

• Output a single-strand sequence that complies with the above specs and the user's given parameters. (i.e. a single row of letters will suffice since it is trivial to deduce the complementary strand of the DNA given the sequence of one strand)

• Calculate the actual GC content %, actual number of genes, and actual gene content % in the resulting fragment, and output a status line below the sequence conforming to the example format below. Percentages may be rounded to one decimal place. Actual values may deviate by +/- 3% from the expected outcome based on user's input.

GC content: 42.1% | Genes: 3 | Gene content: 32.1%

• Use any Internet, library, or built-in gene sequence generation functions or databases. Roll your own.

Sufficient randomness:

• For the purposes of this challenge, any built-in random/pseudo-random number generator function, GUID generator, well-seeded cryptographic hash function, etc. is considered an acceptable source of randomness.

What-ifs:

• What if another start codon occurs before the stop codon? E.g. ATGXXXATGXXXXXXXXXXXXTAG. This is acceptable, but the "gene" length in this case is calculated from the most proximal start codon to the stop codon.
• What if another stop codon occurs after a stop codon? E.g. ATGXXXXXXXXXXXXXTAGXXXXXXTAG This is also acceptable, but likewise the "gene" length is calculated from the start to the most proximal stop.
• What if both of these things happen? E.g. ATGXXXATGXXXXXXXXXXXXTAGXXXTGA. Here again, the "most proximal" principle applies and the gene content is demarcated by the innermost start and the innermost stop.
• Do "orphaned" start and stop codons that do not demarcate a gene count as gene content? No.

This challenge is code golf, so shortest valid code wins.

Post example output from a 500-bp request with GC content between 35% and 65%, and have fun!

• "Use hardcoded fragments for anything other than the start and stop codons." - why not? Specifying criteria for what counts as enough randomness should make these useless in any case. Speaking of which, you need to specify criteria for what counts as enough randomness. – John Dvorak Feb 28 '14 at 5:54
• The only partial output example given flagrantly violates the spec. If the GC content is 42.1%, the gene content should be 31.05%, not 22.0%. The definition of "gene" is also imprecise: in the sequence AUGCCAUGCCUAGCUAA, which is the gene? – Peter Taylor Feb 28 '14 at 12:02
• @PeterTaylor AUG starts the gene, then come the CCA, UGC, CUA and GCU triplets, none of which terminate the gene. Now if there were three C's instead of two, then UAA would be the terminating triplet and the whole sequence would form a gene. I agree the definition is imprecise, though. – John Dvorak Feb 28 '14 at 12:11
• @JanDvorak, (part of) the point of that example is that there are two AUG substrings. – Peter Taylor Feb 28 '14 at 12:30
• Good points. I was hoping to avoid having too much text, but that came at the expense of less clarity than the challenge demands. Edit forthcoming. – Jonathan Van Matre Feb 28 '14 at 13:58
• Also, I've muddied the waters with RNA encoding and DNA encoding, (U vs T), which we can chalk up to a late night. – Jonathan Van Matre Feb 28 '14 at 14:00
• Revised accordingly, although I remain open to suggestions on how best to frame the standards for acceptable randomness. I want something that won't be exploited by answers making no effort at randomness, but that doesn't have the pain-in-the-butt factor of generating 10mb+ of data and running a Diehard test battery. – Jonathan Van Matre Feb 28 '14 at 17:20
• " This is acceptable, but the "gene" length in this case is calculated from the most proximal start codon to the stop codon. " - wait, what? In nature, the first one is the start codon, and the rest encode methionine. Under your scheme, methionine (which is an essential amino-acid) would be impossible to include into proteins. Your scheme would also be much harder to splice. Also, what happens to AUG substrings that are not triplet-aligned to previous AUG substrings? – John Dvorak Mar 1 '14 at 9:25
• In nature, the first ATG encodes the start of a protein coding region and defines a reading frame (triplet boundary), the rest encode methionine and the first triplet aligned stop codon encodes the end of the protein coding region (and no amino-acid). – John Dvorak Mar 1 '14 at 9:29
• As for the randomness, I'm not worried about the source of randomness (whatever native library is available is assumed to be good enough) but rather how the source of randomness is used (can we just start the sequence with a start codon and insert an end codon at just the right spot if it doesn't occur naturally sooner, then fill in with more random codons while avoiding ATG subsequences? Your "sufficient randomness" places constraints on the RNG (useless) but no constraints on how it's used (or that it needs to be used at all) – John Dvorak Mar 1 '14 at 9:34
• My true random number sequence generator was sitting there watching silently as I typed away the sequence ACACACACACACAC.... It's all okay. The TRNG was capable of producing something better - it just didn't really get to it. – John Dvorak Mar 1 '14 at 9:38
• In fact, the 3% tolerance for the CG content leaves no room for randomness when there are only 20 base pairs. I can shuffle the pairs and turn some A<->T or C<->G, but that's it. In fact, if the CG content is set to zero, the task is impossible: we want a gene content of 2 base pairs (which is itself impossible), but the start codon contains a G, and a single G in a 2bp sequence means a 5% CG content, 2% than is the limit. Not including a gene means that we are 7% under the gene content lower limit. Similarly, it's not possible to start or stop a gene with nothing but Cs and Gs. – John Dvorak Mar 1 '14 at 9:45
• Yeah, the 20bp starting point is a bad idea. The problem with start codons is that I considered introducing the idea of promoters and decided that would make the whole thing too complex. So in the absence of promoters there has to be some way to determine which Met is the start codon vs an amino acid and the easiest simplification is to have no Mets in the gene. Likewise, for "not triplet aligned", I'm trying to avoid having to go into explanations of frameshift mutations (even though a Frameshift% would be a cool parameter). – Jonathan Van Matre Mar 1 '14 at 14:29
• I am starting to think that all of these complexities should be included (this proposal stems from me noticing that most of the extant random DNA generators are pretty weak) and this should just be a popularity contest instead of a golf. Link a couple of good articles on the structure of the genetic code and let people add as many features as they wish. Making it a golf seems to be a catch-22 between too many compromises or a too-impenetrable wall of rules and conditions that will dissuade participation. – Jonathan Van Matre Mar 1 '14 at 14:33
• Perhaps a code-challenge where people earn x points for each complexity implemented? – user10766 Mar 2 '14 at 5:52

## DIM, the DIM Integer Machine

The DIM Integer Machine is an engine for producing integer sequences.

It has one major problem: To put it mildly, it's kind of...dim.

After producing a single number, it immediately forgets what sequence it was working on. The only thing it remembers is the last number it produced and the current direction of the search, either ascending or descending. (And of course, it remembers the methodology for finding numbers according to the commands it understands).

Consequently, the user is free to change their mind after each number by issuing a new command.

Suppose the DIM has just produced an integer square: 81

• User inputs P and submits the input.
• DIM understands that P is requesting the next prime number after 81
• DIM computes and returns 83.
• DIM forgets what it was doing.
• User inputs O.
• DIM understands that O is requesting the next odious number and returns 84.
• DIM forgets what it was doing.

The DIM functions only for numbers between 1 and 1,000,000. If the DIM reaches either extreme while performing a search it will reverse direction and continue searching.

(For example: If searching in ascending order for a prime when the last number was 999,999, it will encounter 1,000,000 which is not a prime, then switch to descending order and continue searching for the "next" prime by moving downward - 999,999...999,998, etc.)

The DIM remembers the last number as 1 when it is first activated for a searching session.

This is the full list of commands that the DIM understands:

• P - Next prime number
• S - Next square number
• F - Next Fibonacci number
• O - Next odious number
• W - Next wasteful number
• U - Next undulating number
• K - Next katadrome
• R - Reverse direction immediately; the next command will proceed in the new direction

Because the DIM is so...dim, it absolutely DOES NOT precompute lookup tables of numbers in these sequences. It is far too forgetful for that to work. The DIM also has no Internet connection, so it is unable to consult the Online Encyclopedia of Integer Sequences or other such sites. It also has a sense of pride, so it does not make use of built-in Fibonacci functions or NextPrime / PrimeIndex / PrimeTest type functions.

Given the parameters it knows - a starting number, a search direction, the type of number to find - it simply computes the next number by some means other than mere data retrieval.

The DIM may accept input interactively, or from a newline-terminated text file, or from a pre-initialized array. You may not pack extraneous data other than the command sequence into the input - play fair!

This is a code golf, so least number of bytes wins. Submit your program with output results for the following search sessions:

1. P O U R F O R U S O U R P R O W S
2. W O R K F O R P O O R F O R K S K O O P S R O O K S F O U R W O W S
3. P O O P O O P O O P P O O P P R O P S P R O W S P O R K S

It is assumed that you know what prime, square, and Fibonacci numbers are. A brief explanation of the other integer sequences follows.

Odious - a nonnegative number which has an odd number of 1s in its binary expansion. The first few odious numbers are 1, 2, 4, 7, 8, 11, 13, 14, 16, 19

Wasteful - a natural number that has fewer digits than the number of digits in its prime factorization (including the exponents). The first few are 4, 6, 8, 9, 12, 18, 20, 22

Undulating - has alternating digits of the form aba, abab, ababa, etc. Assume all U numbers are non-trivial, i.e. 3 digits or more. The first few: 101, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212

Katadrome - A number whose hexadecimal digits are in strict descending order. The first few are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 32, 33, 48, 49

• When I post the question, I'll also include external links to MathWorld or OEIS for those who need more detail on the less familiar sequences, but the explanations above should be sufficient for most, I think. – Jonathan Van Matre Mar 6 '14 at 23:28
• Your definition of "undulating" isn't the one I'm familiar with, which just requires that the digits alternately increase and decrease. Also, it would be better to include expected answers for the test cases, so that submitters can use them as test cases rather than them serving just for you to say "No, this is buggy". – Peter Taylor Mar 6 '14 at 23:57
• Yes, that's my plan, I just haven't finished double checking my results for the test cases yet. OEIS and Mathworld have the strict 2-digit definition of undulating, but I'll make sure to make the definition here more prominent so it is clear which interpretation is meant. – Jonathan Van Matre Mar 7 '14 at 0:04
• 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.) – user58826 Jun 9 '17 at 16:09

# Unified format patcher

Write the shortest program that will take a patch file in the unified format from stdin and apply that patch. No external tools that do the process for you can be used.

### Clarifications

• Extra documentation about the unified format can be found here
• All file paths will be relative
• Only one file will be modified per patch
• Timestamps can be ignored
• The patch file will be valid and will apply cleanly to the file specified (it will not lie about line numbers, etc..)
• Assume all files being patched already exist, you don't need to create/delete files

### Extra

• -35 - Take an argument that allows you to unpatch a patch

### Example

/test/a.cpp

#include <iostream>
using namespace std;

int main() {
cout << "Hello world!";
return 0;
}


patch.txt

--- a/test/a.cpp
+++ b/test/a.cpp
@@ -1,7 +1,8 @@
#include <iostream>
+#include <vector>
using namespace std;

int main() {
-    cout << "Hello world!";
+    cout << "Goodbye world!";
return 0;
}


Run patch

patch.exe patch.txt


/test/a.cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
cout << "Goodbye world!";
return 0;
}

• Can the program assume that the @@ lines contain the correct line numbers? – ugoren Mar 6 '14 at 17:52
• A good explanation of the patch file format is needed. If not too long, include it in the question. Else, provide a link. – ugoren Mar 6 '14 at 17:53
• You forgot the obvious "no external tools" disclaimer. You don't want the patch \$1 answer. – ugoren Mar 6 '14 at 17:55
• @ugoren thanks for the comments, I added some further clarifications. – Danny Mar 6 '14 at 18:38
• Does "The patch file will be valid (it will not lie about line numbers)" also mean that it will apply cleanly? – Peter Taylor Mar 6 '14 at 19:24
• @PeterTaylor yes, updated question. – Danny Mar 6 '14 at 19:51
• "The shorted program" should say "the shortest program", but other than that I think it's ready to go. Of course, no-one's actually going to do more than filter out the lines starting -, remove the first char from each line, and parse the line-numbers to work out how to splice the resulting text in. – Peter Taylor Mar 7 '14 at 0:01
• This sandbox post has had little activity in a while. Please improve / edit it or delete it to help us clean up the sandbox. Due to community guidelines, if you don't respond to this comment in 7 days I have permission to vote to delete this. – user58826 Jun 9 '17 at 16:10

# Efficient Testing for Armstrong Numbers

An Armstrong Number (also known by different names, including Narcissistic Number; see Wikipedia for more information) is a non-negative number (for our purposes represented in base 10) that is equal to the sum of the individual digits of the number each raised to the power of the number of digits. For example:

2. The individual digits are 4, 0, & 7.
3. Since it is a three digit number, we raise each digit to the third power: 64 (4^3), 0 (0^3), & 343 (7^3).
4. The sum of those values is 407 (64 + 0 + 343).
5. Because the final sum is equal to the original number, it is an Armstrong Number.

By contrast:

2. The individual digits are 4 & 7.
3. A two digit number, so raise each digit to the second power: 16 (4^2) & 49 (7^2).
4. The sum of those values is 65 (16 + 49).
5. The final sum of 65 is not the original number, so it is not an Armstrong Number.

Your mission, should you decide to accept it: Write a program in any programming language (using only standard language features and libraries) implementing the most efficient algorithm possible to test the numbers from 1 through 18,446,744,073,709,551,615 (264-1) inclusive for "Armstrongness", generating a list of Armstrong Numbers, and only Armstrong Numbers, as output.

While any language is acceptable, it should be obvious that interpreted scripting languages will be at a disadvantage in the efficiency department. That being said, a superior algorithm in an interpreted scripting language can beat the pants off an inefficient algorithm in hand tuned assembly language.

## Winning Criteria

The algorithm that can check all possible candidate numbers for "Armstrongness" in the least amount of time on a reference computer will be the winner. The reference computer will have the following specifications: {approximately an AMD Phenom class computer with 8 GB RAM running Windows 7 Ultimate 64 bit}

• I don't know that this would belong in the (already very long, maybe too long) problem statement above, but other historical background. The class was for Fortran 77, and I was in a friendly competition with my TA to write the shortest version. I never could win that one, so I decided to write the most efficient version instead. Hence: I prefer efficiency puzzles to code golf (though code golf is fun too). – CasaDeRobison Feb 20 '14 at 8:30
• This doesn't seem to have an objective winning criterion. You do list "criteria I'll be using to judge this", but a) it mixes specification with winning criteria; b) it combines factors without indicating their weight. – Peter Taylor Feb 20 '14 at 11:51
• The question also seems to be about twice as long as it needs to be. If you use the [link text](url) link notation you can shorten it slightly; you can also lose paragraphs by cutting the worked example and brute-force code (link to the existing question on narcissistic numbers instead); cutting the waffling about which languages you think have advantages; and simplifying the motivation. – Peter Taylor Feb 20 '14 at 11:57
• I think efficiency problems are not well suited to code-golf. The efficiency of an algorithm depends on too many factors. You could perhaps require the lowest number of power operations. – ugoren Feb 20 '14 at 12:43
• @ugoren, 0 is easily obtained. – Peter Taylor Feb 20 '14 at 12:57
• @PeterTaylor, You're right. Still, trying to replace a time measurement with the number of operations of a certain type sometimes helps define the problem better. – ugoren Feb 20 '14 at 15:12
• @PeterTaylor: I agree it is quite long, and will consider revisions to it. – CasaDeRobison Feb 20 '14 at 21:43
• @PeterTaylor: I'm open to better phrasing of the "objective winning criteria" but really, it is pretty objective already. One, no wrong answers allowed in the winner. Two, how efficient is the algorithm (based on the range of numbers tested and time taken to test them). For example, an algorithm that tests all numbers through 9 digits in 100 seconds is faster than an algorithm that takes 20 seconds to test all numbers through 8 digits (10 times larger interval in only 5 times the time). How might you suggest integration of this with the problem statement? – CasaDeRobison Feb 20 '14 at 21:48
• @PeterTaylor: Glad I included the disclaimer about failing eyesight, given that I searched for narcissistic numbers and came up with nothing. I either searched the wrong portion of PCG (meta) or I made a typo when spelling narcissistic. – CasaDeRobison Feb 20 '14 at 21:49
• @ugoren: efficiency may not be suited to code golf, but my understanding was that this 'forum' was about "programming puzzles" and "code golf". I certainly would consider finding a more efficient algorithm to be like solving a puzzle, though maybe I'm alone in that, in which case no biggie. – CasaDeRobison Feb 20 '14 at 21:51
• Edited the problem statement (which is still admittedly quite long, still considering other edits) by removing the final PPS paragraph and replacing the existing links as suggested. – CasaDeRobison Feb 20 '14 at 21:59
• The winning criterion is still too imprecise IMO. (NB Of the judging criteria you list, the first is part of the spec, so it's an acceptability criterion rather than a winning criterion). A genuinely objective winning criterion allows me to calculate my score before I submit my answer. – Peter Taylor Mar 12 '14 at 8:47
• It should be much shorter in order to not discourage people from approaching your challenge. Almost all the text after the definition doesn't add anything to the challenge - beside "don't print wrong numbers" which is of course relevant. I also think that a more precise criterion should be given instead. – Howard Mar 12 '14 at 9:03
• I've posted a "radical" update to it. I suspect the new winning criteria will not be acceptable either, since it involves a "reference computer" for final timing. Very open to suggestions on how to restate it so that a crappy algorithm on fast hardware doesn't beat an efficient algorithm on slow hardware. – CasaDeRobison Mar 12 '14 at 20:17
• The possibility that processor architecture or available memory affects the results is a tricky issue with fastest-code questions, but there isn't really a better way of comparing speed of programs than measuring on a large test case. I can at least measure how my program compares to someone else's on my computer, and know whether it's close or not. – Peter Taylor Mar 12 '14 at 21:23

## Amino Acids Matcher

In genetics, a codon is a set of three nucleotides, the most basic form of nucleic acids. A codon "codes" (no pun intended, that's the actual term used) for a specific amino acid. Given a string of DNA, it is converted into RNA form by taking the opposite complementary pair.

DNA    RNA
A      U (T changes to U)
T      A
C      G
G      C


You will be given a String of unknown length that contains multiple codons. You must convert them to RNA form and print out the amino acid for each. See here for a chart: http://en.wikipedia.org/wiki/RNA_codon_table#RNA_codon_table

## Sample Input

TACTCGGATACT

Is split into

TAC, TCG, GAT, ACT

We now change each letter to its reciprocal

AUG, AGC, CUA, UGA

And print out the amino acids

Methionine, Serine, Leucine, Stop

This would probably be

I know that this is most likely not sufficiently explained and might be too complicated. Additional, tell me if there is any incorrect information above.

• So basically this is a challenge to compress a lookup table. You should probably specify that the string will be a multiple of three characters (or specify what to do otherwise); and it would seem sensible to inline the lookup table so that a) the question doesn't rely on the external page remaining intact; b) you save everyone who wants to answer the question the hassle of calculating it. – Peter Taylor Mar 17 '14 at 12:42
• Thanks for the feedback. I'll update accordingly later today. – nrubin29 Mar 17 '14 at 15:48