458
\$\begingroup\$

What is the Sandbox?

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

To post to the Sandbox, scroll to the bottom of this page or click on the "Add Proposal" link below, and click "Answer This Question". Click "OK" when it asks if you really want to add another answer. Write your challenge just as you would when actually posting it. You may also add some notes about specific things you would like to clarify before posting it. Other users will help you improve your challenge by rating and discussing it. When you think your challenge is ready for the public, go ahead and post it, replace the post here with a link to the challenge and delete it.

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

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

2559 Answers 2559

1
\$\begingroup\$

A Simple Card Game

Take 2 standard decks of cards, and 4 players. Shuffle the deck, and distribute the cards evenly among the 4 players. Each player will take one card in their hand (visible to only the player himself), and place the others on a stack in front of them.

Overview:
The goal is to collect all the cards. Taking turns, each player will play a card from either their hand, or hope for the best and play the first card from their stack. After all players have taken turns, the player with the highest card* will win that round and will collect the played cards. He will then start the next round.

Replenishing / losing / winning
If you play a card from your hand, you may draw the first card from your stack and place it in your hand. If you run out of cards on your stack, you may shuffle the cards you collected, and this will be your new stack. You will be removed from the game the moment you have played the last card (which is by definition from your hand) and do not win the consequent round. Last player standing wins the game.

*Highest card
The highest card is in principle determined by the standard sequence 2<3...<King. However, when someone plays an ace, the sequence becomes 4<...<Ace<2<3, i.e., 3 becomes the highest card. The winner is determined at the end of the round - the order of play is irrelevant.

If there's a tie, the 'winning' players do another round, and the final winning player will collect all the cards 'on the table', i.e., of all the tied rounds. Edge case: if you tie with your final card, you will lose after all, since you have no cards to play with after the tie.

Examples:
We have four players: Alice, Bob, Carol and Dave. Let's denote the cards by [1-12] where 1 is an ace.

A:  5, B: 9, C: 1, D: 8.   Winner: Carol.
C: 10  D: 4  A: 1, B: 2.   Winner: Bob (2 beats ace)
B: 11, C: 1, D: 4, A: 1.   Tie between Carol and Alice... (both aces)
C:  4, A: 3                Winner: Carol (she gets six cards).
C:  3, D: 2, A: 1, B: 6.   Winner: Carol (3 beats ace)

The challenge

Build a player that will win as many games as possible. You will receive 10 points for first place, 5 for second, 3 for third and 1 for last place. Your final score will be divided by the number of simulation runs I did, so you will score [1-10].

Your code must fit within [an amount of bytes to be determined; 1kiB?]

Sandbox questions:

  1. Would you consider participating? Why (not)? (challenge quality)
  2. What would be better?
    • A Java controller (each player extends the default Player class). Advantage: no I/O parsing required, just simple function calls. Disadvantage: excludes all other languages, lest a wrapper is made.
    • A STDIN/STDOUT controller (each player will receive input over STDIN, and return what they do on STDOUT). Advantage: virtually any language can compete. Disadvantage: possibly cumbersome I/O format to present the players with all relevant information.
\$\endgroup\$
  • \$\begingroup\$ 1. Why use standard decks of cards? The mechanic would be identical if the deck has 8 copies each of the numbers 0 to 12, and the special-cased parsing would be eliminated. 2. The weird stuff with the ace isn't adequately explained. E.g. what happens if the four players play, in order, 3, A, 3, A? \$\endgroup\$ – Peter Taylor Apr 7 '16 at 13:40
  • \$\begingroup\$ @PeterTaylor Thanks for the feedback! 1) I did that to make it less abstract. Eventually, I will use 1-12 for coding the cards. 2) Is it better explained now? (in your case, the two players playing a '3' would tie and have another round) \$\endgroup\$ – Sanchises Apr 7 '16 at 14:48
  • \$\begingroup\$ Still not very clear, no. King < Ace when no-one plays an ace (and therefore it doesn't matter) and Ace < 2 when someone plays an ace, so that for all practical purposes Ace < 2 always? \$\endgroup\$ – Peter Taylor Apr 7 '16 at 15:17
  • \$\begingroup\$ @PeterTaylor Oh wait, I see where the confusion comes from, my bad. Yes, you are right, and the latest edit should reflect that. Any comments on whether to use a Java controller or a STDIN/STDOUT one? \$\endgroup\$ – Sanchises Apr 7 '16 at 15:22
  • \$\begingroup\$ A Java controller can easily wrap a stdin/stdout one. You should be able to steal a wrapper from some existing koth. I'm still not entirely clear what's going on with the ace: is the full post-ace-play order 4<5<6<7<8<9<10<J<Q<K<A<2<3 ? \$\endgroup\$ – Peter Taylor Apr 8 '16 at 7:20
  • \$\begingroup\$ @PeterTaylor Yes, exactly. I will try to make a wrapper then, thanks once again for the feedback. \$\endgroup\$ – Sanchises Apr 8 '16 at 7:44
  • \$\begingroup\$ Unless I'm wrong, it seems like you will never have more than one card in your hand, but the language you use implies that you can. Can you have more than one? If so, how? \$\endgroup\$ – Fricative Melon Apr 8 '16 at 12:52
  • \$\begingroup\$ You mean the moment you have played the last card from your hand and do not win the consequent round? I meant to say "The moment you have played the last card (which will by definition be your hand card), ...", I'll fix that phrasing. Or is any other part of the spec also confusing? \$\endgroup\$ – Sanchises Apr 8 '16 at 13:01
  • \$\begingroup\$ Also, you refer to playing "a" card from your hand, which makes it sound like a choice. I would replace "a" with "the" in those cases. The only thing besides that that you could add is how you will determine a winner if you have, for example, N bots submitted, given that the game takes exactly 4 players. \$\endgroup\$ – Fricative Melon Apr 8 '16 at 13:28
1
\$\begingroup\$

Find point on the Hilbert curve

The Hilbert curve space filling curve. It is a limit of recursive approximations. Being spacefilling means there is a parametrization of the curve which is continuous. So we can map the interval [0,1] continuously to the unit square [0,1]x[0,1]. Let us call this map h. (Note that the image of the [0,1] is not the complete [0,1]x[0,1] but rather a dense subset. E.g. (.5,.1) is obviously not in the Hilbert curve, as it is not in any of the approximations.)

Your task is now to write a progarm that given a value in [0,1] to return the corresponding value unit square [0,1]x[0,1], where h(0)=(0,0) and h(1)=(1,0), and h(.5) = (.5, .5)

Meta

  • This could also be done backwards.
  • Test cases to be added.
\$\endgroup\$
  • \$\begingroup\$ Are forwards and backwards sufficiently different tasks to make this two separate questions? \$\endgroup\$ – trichoplax Apr 11 '16 at 20:14
  • \$\begingroup\$ I just thought about this: the 'backwards' challenge would be relatively difficult, as h is continuous but only injective, but the inverse is not continuous anymore. So I think this direction is the better suited one for a challenge. \$\endgroup\$ – flawr Apr 11 '16 at 20:45
  • \$\begingroup\$ Yes the backwards challenge would have more than one valid output. Maybe 4? You could just ask for any 1, or all (4?) or as many as exist (I'm guessing the 4 corners have only one answer). Forwards seems more than enough of a challenge to start with though. \$\endgroup\$ – trichoplax Apr 11 '16 at 21:19
  • \$\begingroup\$ I'd recommend either a formula or a reference implementation to make the correct output explicit. The Hilbert curve is fairly easily confused with similar-but-not-quite-the-same curves. \$\endgroup\$ – trichoplax Apr 11 '16 at 21:21
  • \$\begingroup\$ @trichoplax Yes I'm certainly going to add a reference. What other curves do you have in mind? \$\endgroup\$ – flawr Apr 11 '16 at 21:32
  • \$\begingroup\$ I was thinking of curves like the Moore curve but now that I look it up, I see that answers using this would be ruled out by test cases using the end points (0 or 1). \$\endgroup\$ – trichoplax Apr 12 '16 at 0:05
  • \$\begingroup\$ Right, I was not aware of this curve and it certainly looks quite similar! \$\endgroup\$ – flawr Apr 12 '16 at 8:06
  • \$\begingroup\$ I really like it because its ends meet so it can form a closed loop. \$\endgroup\$ – trichoplax Apr 12 '16 at 12:55
1
\$\begingroup\$

Compute the size of a binary tree iteratively

Introduction

Binary trees are easy to manipulate using recursion. For example, here is Java code that declares a binary tree and determines its size (the number of nodes it contains) recursively:

public class BinaryTree
{
  private Node root;

  /**
   * Constructs a search tree with the given root.
   *
   * @param the root node
   */
  public BinaryTree(Node root)
  {
    this.root = root;
  }

  /**
   * Gets the number of nodes in this tree.
   */
  public int size()
  {
    return size(root);
  }

  // private helper function
  private int size(Node node)
  {
    if (node == null)
      return 0;
    else
      return 1 + size(node.getLeftChild()) + size(node.getRightChild());
  }

The definition of Node is not shown. As you would expect, it has methods getLeftChild() and getRightChild() that either return other instances of Node or null. A Node does not have backlinks to its parent.

Challenge

Write a non-recursive function to determine the number of nodes in a binary tree. You should not make any assumptions about the ordering of the nodes; however, you can assume that a reasonable hash function exists on nodes such that you can expect O(1) access time using a hash table.

In addition to not calling itself, your function should not simulate recursion through a stack-like data structure, and it should not call any recursive functions. You may use standard data structures, such as a set that uses hash codes to determine membership.

Solutions will be judged by their efficiency. Specifically, they will be judged by their time complexity, with space complexity used as a tie-breaker.

\$\endgroup\$
  • 2
    \$\begingroup\$ Hi, welcome to PPCG and thanks for using the Sandbox! :) fastest-algorithm challenges are hard to run because they are hard to score well, just as an FYI. Also probably worth noting is that not all languages will have the same definition of binary tree. In addition, I'm not certain this is possible without "simulating recursion", arguably, any looping construct at all is also solvable through recursion, so I don't think that's really a good way to word this restriction. \$\endgroup\$ – FryAmTheEggman Apr 15 '16 at 20:38
  • 1
    \$\begingroup\$ I think that by the standards of this site, this question should be considered a dupe of this one and therefore closed. (This is sad, because the older question is still semi-vandalised by its OP). \$\endgroup\$ – Peter Taylor Apr 15 '16 at 21:01
  • \$\begingroup\$ Thanks for the feedback. I'll be back with a different question some time. \$\endgroup\$ – Ellen Spertus Apr 15 '16 at 22:03
1
\$\begingroup\$

Decimal to Troll

Discworld Trolls have a unique number system. From Wikipedia:

Trolls have a numeral system of their own, based on powers of 4.

The base numerals are one (1), two (2), three (3), many (4) and lots (16), which can be combined to form higher numbers.

When combined, each numeral's value is added to those of the others. Higher-valued numerals take priority over lower-valued ones, so that 4 is written "many" and not "two-two" or "three-one" and 20 is written "lots many" rather than "many many many many many". If there are no ones, twos or threes, the number is written with spaces between the numerals; if any exist a hyphen replaces the space between every numeral.

The Challenge

The challenge is to write a program that accepts a positive integer and outputs the equivalent troll counting string, including the correct separator (hyphen or space) based on the above rules.

Examples (including those from Wikipedia):

Input   Output
-----   ------
   1      one
   2      two
   3      three
   4      many
   5      many-one
  10      many-many-two
  20      lots many
  32      lots lots
 126      lots-lots-lots-lots-lots-lots-lots-many-many-many-two

This is code-golf, shortest answer wins.

\$\endgroup\$
  • \$\begingroup\$ Nice challenge! \$\endgroup\$ – Leaky Nun Apr 18 '16 at 12:20
  • 1
    \$\begingroup\$ I feel like this is a dupe of this challenge about money. I think the greedy algorithm still works, the only differences that I see between these is the I/O formats and the amounts to use, which I'm afraid don't sufficiently differentiate them, in my opinion. \$\endgroup\$ – FryAmTheEggman Apr 18 '16 at 13:27
  • \$\begingroup\$ @FryAmTheEggman I can see the similarities, and yes, the repeating units in the output and separator are the main differences. But Discworld! :) Happy to withdraw it if consensus is it's too similar. \$\endgroup\$ – Liesel Apr 19 '16 at 1:48
1
\$\begingroup\$

Tron Bot Racing

It's time to begin annual Tron Racing Tournament. Create a bot that will steer your cycle to a victory!

Glossary

Board is a 100x100 square that wraps around its edges.

Game

Bots leave impassable trail. In the beginning of the game, all the bots participating (2 in case of a duel) are placed randomly thorough the map. Then, at the beginning of each turn, all bots must decide the direction they will chose next (Up, Down, Right, Left) based (or not) on the available data, which is the empty cells in each of the directions. If bot tries to move into an occupied cell, his turn is repeated until it makes a valid move. If after 10 tries bot still won't make a valid move, it dies. Game ends when all bots die. Score is the length of your trail.

Example:

. . . . . d . .
. . . b b b b .     Received data:
. . . b . u b .     L0 U3 R3 D3 T1
. . . b . u b .     
. . . b . u b .     Length of line of sight is `ceil(map_size/2) - 1`
r . . b b B r r     and it wraps around map edges.  
. . . . . d . .     u, r, d - lines of sight
. . . . . d . .     B - bot, b - bot's trail 

If bot decides to go Left (and will collide with his own trail), he is invoked one more time with Tries increased: `L0 U3 R3 D3 T2'.

Submissions

The engine is written in Node.js, so your bot should be a function in Javascript that accepts 1 argument (state array) and returns integer between 0 - 3 which corresponds to your chosen direction.

function RandomBot(state) {
  return Math.floor(Math.random() * 4);
}

0 - Left, 1 - Up, 2 - Right, 3 - Down

You can also write your bot in any other runnable language. It will be run every time a decision needs to be made, with data pushed into StdIn 3,3,0,2,1 and output (single integer) required at StdOut.

However, by using Javascript you have the advantage to use this to save data between runs.

Winner and conditions

Bots will be dueling with each other, each duel repeated 100 times. Standard loopholes apply.

Meta

How to create leaderboard? How to score wins and loses? Is there anything that can be improved? This is my first entry ever and I have already a working prototype. I have concerns with the data passed to bots. Maybe its too small? Anyway, let me know what do you think about it guys.

\$\endgroup\$
  • \$\begingroup\$ Similar \$\endgroup\$ – Peter Taylor Apr 20 '16 at 10:57
  • \$\begingroup\$ Even more similar. Except for limited data/sight, it's a duplicate. \$\endgroup\$ – Geobits Apr 20 '16 at 13:56
  • \$\begingroup\$ I think that if the match would consist of bigger board and all the bots at once, it would be different enough to not be a duplicate. \$\endgroup\$ – Are Wojciechowski Apr 20 '16 at 15:03
  • \$\begingroup\$ I agree that a free-for-all should be sufficiently different, especially given the limited sight. Then again, with that many walls floating around, it could end up being very hard to avoid an impossible trap. You might want to do some test runs with some naive bots to see what happens. \$\endgroup\$ – Geobits Apr 21 '16 at 2:29
1
\$\begingroup\$

Chopsticks

Overview (basically the wiki page)

Chopsticks is a game played with two hands and two people. Both start with one finger out on each hand, the finger count. On a player's turn, they must choose one of their opponent's hands. That opponent adds the player's finger count to the one on that hand (and extends that many fingers). Once a hand's finger count has reached five or more, that hand's finger count is reduced to 0 and can't be used. Once both hands are out, the opponent wins.

To make the game more interesting, there is a mechanic called splitting: A player may use his turn to divide both his hand counts differently than he/she already has. A valid move would be to split from a 2 and a 3 to a 4 and a 1. An invalid move would be to split from a 2 and a 3 to a 3 and a 2. It is illegal to bring a hand back to life like a bunch of my friends like to do, as in split from a 4 and a 0 (a hand that is out) to a 2 and a 2 (back in). I deem it legal (since the Wikipedia article didn't say anything about it) to get one of your hands out using splitting, such as going from 3 and 4 to 2 and 5 (out).

Challenge

Your task is to write a bot that will play chopsticks against another bot.

Input

Every time your bot takes a turn, it will be given its opponent's finger count and its own finger count in this format:

[opponent hand 1] [opponent hand 2] [own hand 1] [own hand 2]

There will be spaces in between each value as shown above. Each value will be an integer. The bot should remember the hand numbers, as it is important to the output.

Output

Your bot must take the data, decide what to do with it, and respond accordingly. Output is in this form:

[target hand] [attacking hand]

where [target] refers to the target opponent's hand and [hand] refers to the hand you are hitting the target with. A valid output would be 1, 2, which says that the bot wants to hit the opponent's first hand with its own second hand.

Problems and todo (sandbox)

  • I do not yet know how to make a program that handles all of this. I'll try to work on it.
  • There will be a bracket.
  • Should I make tweaks to the game to make it more suitable?
  • I may or may not follow through, but regardless I would like feedback.

Thanks.

\$\endgroup\$
  • 2
    \$\begingroup\$ If I understand correctly, this is an alternating turn game with about 6125 states. It's therefore very likely that every submission will play perfectly. \$\endgroup\$ – Peter Taylor Apr 27 '16 at 8:52
1
\$\begingroup\$

Visualize the Euclidean Algorithm by Tiling Rectangles

META: What's your opinion on moving this to a pop-con instead of a code-golf?


Suppose we have two positive integers, m and n. We can use Euclid's algorithm to calculate the greatest common divisor of these two numbers (the largest number that divides both numbers without a remainder). This is done by essentially taking successive subtractions of remainders until you reach zero. The linked Wikipedia article goes into much greater depth, and the mathematics behind it, for the curious.

Here, though, we're going to visualize the algorithm by taking a rectangle of size m x n and recursively tiling the rectangle with successively smaller and smaller squares until all space is consumed. The length of the side of the smallest square is thus the gcd(m,n).

Assuming m >= n, the first square is of size n x n, and is placed against the bottom edge. This repeats until a square does not fit, leaving a rectangle of size n x (m-kn) remaining, where k is how many n x n squares fit. That process then repeats on the newly-formed rectangle, starting on the left side, then the bottom, then the left, etc., until the original m x n rectangle is fully tiled.

Here's a beautifully done animated example, from that Wikipedia page, of 1071 and 462, showing the result to be 21.
By Proteins (Own work) CC BY-SA 3.0, via Wikimedia Commons.

Input

  • Two distinct positive integers, m and n, via any convenient input method. Without loss of generality, you can assume m > n (for example, if you take input as a tuple, your program can assume that the first element is always the larger of the two, and you don't need to test size).
  • Your implementation should be able to handle input up to your language's default int size (or equivalent).

Output

  • An image of at least 300px square, but no bigger than 1200px square, showing a rectangle of proportion m x n, tiled with successively smaller squares as described above. This means that for small inputs the rectangle will need to be stretched, and for large inputs the rectangle will need to be shrunk.
  • The image must be oriented so that m (the larger) is the vertical dimension and n is the horizontal.
  • Squares of the same size must be distinct. This could be done by coloring the squares differently from their neighbors, by enclosing each square in a border (as in the above animation), etc.
  • Output does not necessarily need to be in color, so long as the squares are distinct and understandable.
  • The image can be displayed on-screen or saved to a file.

Examples

[TODO]

\$\endgroup\$
1
\$\begingroup\$

How Many Colours?

Take a grid of ASCII art rectangles as input and output the minimum number of colours you would need to colour it in so that no two rectangles of the same colour are touching.

Rules

  • Input can be any type of grid format (multine string, array of strings, etc...).
  • Rectangles only count as touching if the inside is adjacent to the inside of another rectangle (see the bottom-left rectangle in the example).
  • You may use different characters to # and space, but if you do, please specify what you use in your answer.
  • The grid itself will always be rectangular.
  • Grid width and height will always be between 3 and 99.
  • Shortest code in bytes wins.

Example

The output for this input would be 3. An example arrangement of each colour 1 to 3 is labelled in the input below. Note how the bottom-left rectangle does not count as adjacent to the middle one.

#################
# 1  #      # 1 #
######      #   #
# 2  #  3   #####
#    #      #   #
######      # 2 #
# 3  ########   #
#    #  1   #   #
#################

Test Cases

TODO...

Links

Four Colour Theorem

Tags

\$\endgroup\$
1
\$\begingroup\$

Wheels on the Bus Go...

Scenario

There is a bus heading for an intersection. Usually that is when buses would stop and give way to traffic, but there's a bomb on the bus! The bomb blows up if the speed of the bus falls below 50 miles-per-hour. Find out what speed the bus needs to travel at to avoid crashing into the cars going through the intersection.

Input

  • Take a list of cars coming from the left and another list of cars coming from the right. The lists contain the distance of each car from the intersection as integers.
  • The distances will always be from 1 to 99 units.
  • There will always be 1 to 9 cars in either direction (2 to 18 total).

Output

  • The speed the bus must travel to make it through the intersection without hitting a car.
  • The speed can be an integer from 5 and to 9 which is the speed in miles-per-hour / 10.

Rules

  • Each iteration, every vehicle moves speed in mph / 10 units forwards. The "path" of a vehicle for each iteration includes it's position before the iteration, it's position after the iteration and every position in between.
  • The cars always travel at 40 mph.
  • A crash occurs when the path of the bus intersects the path of a car in the intersection.
  • The bus starts 20 units before the intersection.
  • Cars cannot crash into other cars.
  • The speed of each bus cannot change during the simulation. You can only give each bus one speed.
  • Only solvable inputs will be given.
  • Shortest code in bytes wins.

Example

TODO: Example doesn't make sense yet. Will complete later...

Here's an example using ASCII art to illustrate what would happen with this input and a bus speed of 6. Note: despite what it may look like, the intersection should behave as if it's size is only one unit.

  • B = Bus
  • . = Vehcile movement during iteration
  • C = Car

Input: [ ... ]

                  |     ^ |
                  |   | | |
------------------ ---     --------------
        <-                |    C . . . C
--  --  --  --  --         --  --  --  --
. C           C . |     .  . C     ->
------------------     --- --------------
                  |   |   |
                  |     B |
                  |   | . |
                  |     . |
                  |   | . |
                  |     . |
                  |   | . |
                  |     B |

Test Cases

TODO...

Tags

\$\endgroup\$
  • \$\begingroup\$ So a bus can never crash with another bus with a different unit digit in the distance, if they are moving from different roads? \$\endgroup\$ – Leaky Nun May 1 '16 at 15:16
  • \$\begingroup\$ @KennyLau There's only two roads, the sideways one and the up/down one. The only time buses from both roads will crash is if their paths overlap over the intersection. I'll try explaining it better when I edit it. \$\endgroup\$ – user81655 May 1 '16 at 15:19
1
\$\begingroup\$

From Smiles to Molecular formula!


SMILES is an algorithm to represent chemical molecules in one-line ASCII.

In this challenge, we will only be dealing with purely organic chemicals.

  • All the Hydrogens are not represented.
  • All single bonds not represented, double bond is =, triple bond is #. For example, ethane is CC, ethene is C=C, ethyne is C#C.
  • Branches are represented by (). For example, isobutane is CC(C)C, acetone is CC(=O)C.
  • Cycles are represented by numbers. For example, cyclohexane is C1CCCCC1.
  • All other things are ignored in this challenge.

Your task is to determine the molecular formula of a molecule, given its SMILES representation.

Specs

Any reasonable input/output format.

These are all accepted, for formaldehyde:

  • CH2O
  • C1H2O1
  • CxHxxOx (unary)
  • CHHO
  • OCHH
  • OHCH

Scoring

This is . Shortest solution in bytes wins.

Testcases

input       output
C=O         CH2O
O=C=O       CO2
C1C(=O)CC1  C4H6O
C#CCC       C4H6
\$\endgroup\$
  • \$\begingroup\$ I think you need to tighten up the specs. "Reasonable" is, of course, wide open to interpretation. For example, it's left unclear if the ordering in the output matters. Is it always carbon, hydrogen, oxygen, in that order (omitted if not present, naturally)? Is it "unreasonable" to say OCH2? \$\endgroup\$ – dcsohl May 2 '16 at 13:20
  • \$\begingroup\$ @dcsohl Thanks, edited to allow that. \$\endgroup\$ – Leaky Nun May 2 '16 at 13:28
  • \$\begingroup\$ Are you sure about your examples? My reading of the Wikipedia page is that cyclehexane's SMILES description should contain 6 Cs, but your example only has 5. \$\endgroup\$ – Peter Taylor May 3 '16 at 10:08
  • \$\begingroup\$ @PeterTaylor That was a typo, thanks. \$\endgroup\$ – Leaky Nun May 3 '16 at 14:16
  • \$\begingroup\$ Which elements do answers need to be able to handle? \$\endgroup\$ – Peter Taylor May 4 '16 at 6:28
  • \$\begingroup\$ Also, can we assume that we won't be given aromatics so complicated that the cycle indication numbers go up to 10? \$\endgroup\$ – Peter Taylor May 4 '16 at 7:16
1
\$\begingroup\$

Simulate a DNA Computer

DNA computers are very powerful computational models, theoretically able to solve NP-complete problems such as SAT deterministically in polynomial time. Your task in this challenge is to write a program/function that simulates the behaviour of a very simple DNA computer that accepts only four different kinds of commands.

DNA and Tubes

To make things a bit easier, we model DNA strands as non-empty words over {0,1}. So for our purpose, the following are all valid strands of DNA: 1, 010010, 01, 1100101.

Our DNA computer has access to an infinite number of (test) tubes T1,T2,T3,..., each of which contains a finite number of DNA strands. That is, Ti ⊂ {0,1}* for all i ∈ ℕ+. For example, T1 = {1,0100101,000} would be a valid tube. At the beginning of a simulation, all tubes are assumed to be empty (Ti = ∅ for all i ∈ ℕ+).


Commands

Our computer supports four different commands: Initialize (I), Merge (M), Filter (F), and Amplify (A). In the following, let the pairwise different numbers i, j, k ∈ ℕ+ denote indices of tubes Ti, Tj and Tk. Furthermore, let n ∈ ℕ+ and b ∈ {0,1}.

Initialize

  • Description: We take all possible DNA strands of length n and put them into tube i.
  • Syntax: i = I n
  • Semantics: Ti ← {0,1}n
  • Example: After the execution of 2 = I 3, we have T2 = {000, 001, 010, 011, 100, 101, 110, 111}.

Merge

  • Description: We mix the contents of tubes j and k and put them into tube i.
  • Syntax: i = M j k
  • Semantics: Ti ← Tj ∪ Tk ; Tj ← ∅ ; Tk ← ∅
  • Example: If T2 = {00, 111} and T3 = {1, 010, 00}, then after the execution of 1 = M 2 3, we have T1 = {00, 111, 1, 010} and T2 = T3 = ∅.

Filter

  • Description: We remove all DNA strands from tube j whose n-th bit is not equal to b. We put the remaining strands into tube i.
  • Syntax: i = F j n b
  • Semantics: Ti ← Tj ∩ {0,1}n-1∘{b}∘{0,1}* ; Tj ← ∅
  • Example: If T2 = {1010000, 111, 1, 0101}, then after the execution of 1 = F 2 3 1, we have T1 = {1010000, 111} and T2 = ∅

Amplify

  • Description: We put an exact copy of the contents of tube j into tube i.
  • Syntax: i = A j
  • Semantics: Ti ← Tj
  • Example: If T2 = {1010000, 111, 1, 0101}, then after the execution of 1 = A 2, we have both T1 = {1010000, 111, 1, 0101} and T2 = {1010000, 111, 1, 0101}.

Input

Input will be a DNA program, i.e. a sequence of these four commands, that can be read from STDIN, taken as a function argument or even be stored in a file. It's up to you whether you take them as a list or a string with some kind of separator. Also, you can choose a different separator for the parameters of the commands or encode each command as a list as long as you do so consistently. For example, instead of the command 1 = F 5 10 0, you may use [1,"F",5,10,0], 1;F/5/10/0, 1=F(5,10,0) or the like. You may assume that the input is always syntactically correct. For example input/output pairs, see below.


Output

You have to output a truthy value iff tube 1 is not empty (i.e. T1 ≠ ∅) after the execution of the DNA program specified in the input. Otherwise output a falsey value. Note that you are not actually required to simulate the DNA program step by step - if you find a more clever way to calculate the output of a given program, feel free to use it.


Examples

In the below examples, all commands are ;-separated and encoded as described in the "Commands" section.

Truthy

  • 1 = I 20
  • 2 = I 4; 1 = A 2
  • 3 = I 1; 1 = M 3 9
  • 1 = I 4; 2 = A 1; 3 = F 1 1 0; 4 = F 3 2 0; 5 = F 2 1 1; 5 = M 3 4; 1 = M 2 5
  • 1 = I 3; 2 = A 1; 3 = A 1; 4 = A 1; 5 = F 2 1 1; 6 = F 3 2 0; 7 = F 4 3 1; 2 = M 6 7; 1 = M 2 5; 2 = A 1; 3 = A 1; 4 = F 2 1 0; 5 = F 3 2 1; 1 = M 4 5 (1)

Falsey

  •  (the empty program)
  • 2 = I 5
  • 1 = I 2; 2 = A 1; 3 = F 1 2 0; 2 = A 3; 1 = F 2 2 1
  • 1 = I 1; 2 = I 1; 3 = M 1 2
  • 1 = M 2 3

Scoring

This is , so the shortest answer (in bytes) wins.


1 In case you are interested: this example evaluates the formula (x1 ∨ ¬x2 ∨ x3) ∧ (¬x1 ∨ x2), that is, the contents of T1 after execution of the program are exactly the assignments to (x1,x2,x3) that make this formula true. One can create similar such programs for any 3SAT formula. The number of commands needed is linear in the size of the given formula.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think this question would benefit from being written in a more layman-friendly and less symbolic way. While I might know that Ti ⊂ {0,1}* means that each test tube is a subset of the kleene star of the set {0, 1} I don't think every user of this site will. You also use things like ℕ+ instead of saying, say, "positive integers" and so on. This is just my personal opinion, but I think if you can explain something with words instead of symbols without compromising much in terms of length, you are more likely to be understood when using words. \$\endgroup\$ – FryAmTheEggman May 11 '16 at 18:47
1
\$\begingroup\$

Inspired by this, but also different. I need help phrasing things, putting them together coherently, etc.

Also, I can't decide on what the magic numbers (size, toggles per turn, etc.) should be.

Lastly, is this even winnable?

(oh, and if anyone wants to write a nice "backstory", that'd be much appreciated)

(also I have a couple of notes to myself in there so I remember what I was doing when I come back to this later)



Murderous Life

Overview

The game is played on a 100-cell-wide, 300-cell-long board. It's cylinder-shaped -- patterns will wrap around the long sides, but not the short ones. Attempts to toggle cells behind the short edges will fail, and all cells along the short edge are considered dead. The center 200x100 area (the "no man's land") is the focus of the game. The farthest left 50x100 area (next to the origin) is the Police Headquarters, and is where the police can send units from. The far right is the Robber Hideout, and is where they operate from.

Your program will communicate with the controller via standard input and output. Each message is terminated with a newline (\n, ASCII code 10). The code your program must exit when it receives Control+C (ASCII code 3). It doesn't have to stop immediately -- for example, if you have to close IO handles -- but it should take less than a second. It also doesn't have to end cleanly -- throwing an error is fine. As long as you've tidied up after yourself.

Immediately, both programs print to STDOUT their name and their author's name, with a hyphen in between, followed by a newline. This signals that they are ready to begin receiving input. After that, the turns will start immediately. The turns work like this:

  1. Both players are sent a string containing the current map through their STDIN. The format is detailed below.
  2. The desired moves are collected from each program in no particular order.
    • Note: If the moves are invalid for any reason -- they attempt to change a blocked square, too long, fail to precisely match the format, anything like that -- then the program is immediately ejected from the game, and I'll drop a comment on your post letting you know what happened.

  3. All of the moves are applied at once to the board
  4. One iteration of Conway's Game of Life (standard rules) is run on the map.
  5. The number of living cells in the No Man's Land is tallied.

The game runs for 5000 turns, after which the average number of living squares in the No Man's Land is calculated. This is the score of both the cop and the robber. Once three answers of each type have been submitted -- aside from the example ones -- I'll begin playing the answers against each other. The scoreboard will be updated daily until at least a week after the first answers have been submitted, or if it's later, three days after the last one has. The full score of any given program is the average of all of its scores.

Each program will be played against every other exactly once. Any attempts to communicate or disrupt the other AI -- except through the board -- are banned. If your bot doesn't respond to CTRL+D or CTRL+C, it will be banned.

Note that, if you have to do some cleanup before exiting, that's fine -- the "kill switches" don't have to work instantly. They do, however, have to work quickly. They can throw an error or something like that if you like.

You can always assume you'll get valid input.

In Cops version:

The point of the game, for the cops, is to keep the board as dead as possible. You can toggle up to 30 cells in the Police Headquarters per turn, creating or removing whatever patterns you like. At the end of the game, the Cop program with the lowest score wins.

In Robbers version:

The point of the game, for the robbers, is to make as many cells in the No Man's Land alive as possible. You can toggle up to 20 cells in the Robber Hideout per turn, in whatever arrangement you want. At the end of the game, the Robber program with the highest score wins.

[link to the opposite side's version]


Message format

Aside from the initial name string, all messages passed between programs will be like this:

1,4 12,0 9,125 299,6

Each pair is a coordinate pair, with the X values first and Y values second. The origin is at the top left of the board -- on the Police side of the board. The indexes are zero-based.

To be explicitly clear, the format is a space-delimited string of pairs. Each pair consists of two base-ten numbers, between 1 and 3 digits long, separated by a comma. The first number must not have a value greater than 299 or less than 0, and the second number must not have a value greater than 99 or less than 0. In addition, the first number must be between 0 and 49 (inclusive) if the player is a Cop, or between 250 and 299 (inclusive) if the player is a Robber.


I've written a basic example bot. To change what side it's on, simple change the comments on the lines indicated.

# Uncomment the part marked with the team this one should be on
#Cops
place_at = (0..47).to_a.product (0..97).to_a
glider = [[1, 0], [2, 1], [0, 2], [1, 2], [2, 2]]
toggles = 30
#Robbers
place_at = (0..47).to_a.product (0..97).to_a
glider = [[1, 0], [0, 1], [2, 2], [1, 2], [0, 2]]
toggles = 20

puts 'GliderLover-QPaysTaxes'

while gets
  # We don't care what the board is like in this dumb AI.
  puts toggles.times.map {
    loc = place_at.sample
    glider.map { |offset| loc.zip(offset).map { |(a, b)| a+b }.join ',' }.join ' '
  }.join ' '
end


Is there anything else I need to specify?

\$\endgroup\$
  • \$\begingroup\$ .. I think this is the first C&R with a controller we've had? \$\endgroup\$ – Rɪᴋᴇʀ May 10 '16 at 22:07
  • \$\begingroup\$ @EᴀsᴛᴇʀʟʏIʀᴋ Maybe! It fits CaR better than KOTH, though. \$\endgroup\$ – Nic Hartley May 10 '16 at 22:08
  • \$\begingroup\$ @QPaysUnicornTaxes yeah. \$\endgroup\$ – Rɪᴋᴇʀ May 10 '16 at 22:09
  • \$\begingroup\$ I think tagging this as KOTH is logical. The closest thing done before was: codegolf.stackexchange.com/q/51029/31203. Maybe putting both tags would be ideal. \$\endgroup\$ – MegaTom May 11 '16 at 19:17
  • \$\begingroup\$ @MegaTom Hm, probably. It's certainly got elements of both. I still haven't finished the controller though, so until then I can't post anything :) \$\endgroup\$ – Nic Hartley May 11 '16 at 19:38
1
\$\begingroup\$

An idea for a king-of-the-hill challenge:

You have a "memory arena" with a fixed size. You have several programs which "reside" in the memory arena (I mean you take the assembly and put it in the arena). The goal of the game is to get another program to access memory outside of this "arena" which then causes it to die because access outside of the memory arena is not defined. The last program standing wins.

You enter in assembly code (I have not determined which architecture yet). At the beginning of a round all of the entries get randomly placed in the memory arena. Each program will execute one instruction per turn.

It would be very similar to red code but in actual assembler.

Please feel free to post comments

\$\endgroup\$
1
\$\begingroup\$

Three Indistinguishable Dice

Given three dice rolls (integer values from 1-6) in sorted order (so as to be indistinguishable), write a program that converts them to the sum of two dice with an identical distribution.

Inspired by standupmath's The Three Indistinguishable Dice Puzzle. A follow-up "solution" video was also posted, but arguing about "elegance" of one way or another is a bit subjective. Counting characters isn't. :D

Details

  • Score is the length of the program in characters
  • The program can be a function that's called somehow, or executable script that reads from stdin, or whatever's convienent.
  • No "rerolling" by getting entropy from another source

Example Test Code

Rather than doing any sort of probabilistic testing, it's easy enough to rip through the 216 (63) cases of all the three dice and assert that your function returns each value as many times as it should. It will be called with identical parameters (e.g. the cases 1, 2, 3 and 3, 2, 1, ... are presumed indistinguishable and are (arbitrarily) converted to 1, 2, 3).

The below is in Python, written hopefully generically enough to be clear to port. If your language of choice uses stdin/stdout, it would be a bit different. The testing code is just for testing and not scored (though if you want to provide it for other users of your language or I/O method, that might be useful).

from thing import f

# this is the fair distribution of the sum of two dice, 
# multiplied by 6 (because each should be hit 6x more)
dist = {
    2: 6,   12: 6,
    3: 12,  11: 12,
    4: 18,  10: 18,
    5: 24,   9: 24,
    6: 30,   8: 30,
    7: 36,
}

d = [1, 2, 3, 4, 5, 6]
for i in d:
    for j in d:
        for k in d:
            ijk = sorted([i, j, k])
            result = f(ijk)
            dist[result] -= 1

for key in dist:
    assert dist[key] == 0
\$\endgroup\$
1
\$\begingroup\$

Collatz or Hailstone sequence efficiently

Sorry for everywhere I posted in the wrong place and thank you to all of the mods for helping me find the sandbox.


Winner is the shortest run time to check whether all numbers up to N will end in x=1 or goes 70 iterations without returning to the original number or without decreasing under a step over Log(N) steps in a row under iterating f(x)=x/2 if x is even and f(x)=(3x+1)/2 if x is odd.

Hint: all one needs to show is that for all x under iteration it hits another y in the sequence that has already been shown to hit 1.


Sandbox questions

  • How can I phrase the above challenge. I set it with parameters that halt for all natural numbers n. I care more about the speed of the program then the shortness of the program.
\$\endgroup\$
  • \$\begingroup\$ Glad to see you've found the Sandbox now. I know it's somewhat counterintuitive that these are posted as answers instead of questions, but it keeps them all in once place with more chance the people who are looking to give feedback will find them. \$\endgroup\$ – trichoplax May 18 '16 at 6:36
  • \$\begingroup\$ For code that is judged by its speed, rather than its length, we have the fastest-code tag. I've added this and a few other tags. You can click on the tags to see other questions of the same type, and a description of the tag. Feel free to use different tags - I've just added some as suggestions. \$\endgroup\$ – trichoplax May 18 '16 at 6:48
  • \$\begingroup\$ I've removed the $s since currently this site does not support MathJax or LaTeX. Your challenge seems to work without it, but if you ever need mathematical notation I've found mathurl.com can be used as a workaround (it's fiddly so I'd only recommend it where the mathematical notation is essential). \$\endgroup\$ – trichoplax May 18 '16 at 6:52
  • \$\begingroup\$ I've looked at the challenges containing the word Collatz and it seems they are mostly code-golf (shortest code) challenges and there have been no fastest-code challenges so far, so I expect this challenge will not be a duplicate. \$\endgroup\$ – trichoplax May 18 '16 at 7:02
  • \$\begingroup\$ What form should the output take? Just true or false? Or the number of cases that don't get to 1 in 70 steps? I guess the latter will prevent all cases above a certain N having identical output. \$\endgroup\$ – trichoplax May 18 '16 at 7:30
  • \$\begingroup\$ The biggest problem I see with this challenge being fastest-code is that I don't see any real optimisation potential beyond the "hinted" memoization. Do you believe anything other than actually including memoization will affect runtime significantly? If not then this feels very much like a chameleon challenge for "write an efficient memoization function" and most of the answers will probably have unappreciably different time taken. \$\endgroup\$ – FryAmTheEggman May 18 '16 at 13:23
  • 1
    \$\begingroup\$ there are a lot of shortcuts to the clever person for instance if x is of the form 2^k then we're done, similarly if x of form 2^k-1 it will ascend k times in. row, so there are number theoretical optimization other then the hint stated \$\endgroup\$ – shai horowitz May 18 '16 at 14:16
  • 1
    \$\begingroup\$ the output should be the numbers under n the fail conditions. i.e. n that doesn't hit one,doesn't cycle in 70 terms, doesn't run for more the Log (n)/Log (2). that is Log base 2 of N. \$\endgroup\$ – shai horowitz May 18 '16 at 14:19
  • \$\begingroup\$ Just so you know, you are getting notifications because this is your post. Other people won't be notified unless you put an @ symbol before their name in your post, like @FryAmTheEggman. \$\endgroup\$ – FryAmTheEggman May 18 '16 at 14:49
  • \$\begingroup\$ oh thank you, @trichoplax I responded what inputs should be \$\endgroup\$ – shai horowitz May 18 '16 at 14:56
  • \$\begingroup\$ Also note, neither of the optimisations you propose would actually improve the speed of a program that computes this. The Collatz operations are so trivial that calling them k times is faster than checking if a number is a natural power of 2. In addition, if you have memoisation you will only ever have to do each power of two once, rather than check each number for a non-trivial property. \$\endgroup\$ – FryAmTheEggman May 18 '16 at 14:57
  • \$\begingroup\$ @FryAmTheEggman Yes for those examples but this does not convince me that there are no shortcuts for the smart programmer hence the challanhe \$\endgroup\$ – shai horowitz May 18 '16 at 15:00
  • 1
    \$\begingroup\$ This site isn't quite like other SE sites, I don't believe you should post a challenge if you yourself are not certain that there actually is challenge. That said, I'd guess the actual best approach is to grow a collatz tree upwards and just report the number of nodes that satisfy your properties, but that has the same problems of it being pretty much optimal already: I feel like the differences between responses would be largely negligible. Someone may prove me wrong, but until you know the competition will be worthwhile, I'd recommend against posting on the main site. \$\endgroup\$ – FryAmTheEggman May 18 '16 at 15:14
  • \$\begingroup\$ @FryAmTheEggman Are there other SE you would recommend I ask? \$\endgroup\$ – shai horowitz May 18 '16 at 15:22
  • \$\begingroup\$ No this is the correct site for this question, I just don't think it would be particularly good. You have enough rep to chat by the way, it may be worth finding some other people's opinions; I am not the sole authority on the goodness of questions ;) \$\endgroup\$ – FryAmTheEggman May 18 '16 at 15:27
1
\$\begingroup\$

Scry sort

In Magic the Gathering, your library is a stack of cards, the effect Scry 2 causes you to take the top two cards of your library and arrange them as you choose on the top and/or bottom of your library.

enter image description here

You have six total choices:

  • Put both cards on top in either order
  • Put one cards on the bottom and one on top
  • Put both cards on the bottom in either order

If you are able to Scry 2 at will, you can repeatedly do so to arrange your library in any order. In this challenge, the cards of your library will be numbered from 1 to n, and your goal will be to arrange them in sorted order.


What should be the challenge here?

  • Code golf to find the minimum number of Scry 2's needed
  • Code golf to find any sequence that arranges your library, no matter how long
  • Fastest code or code challenge to sort in as few Scry 2's as possible.
\$\endgroup\$
  • \$\begingroup\$ I like the code challenge idea, but I think maybe it could be improved with Scry X instead of a constant 2. Given a nice range of cases to test, of course. \$\endgroup\$ – Geobits May 20 '16 at 13:23
  • \$\begingroup\$ I think this depends a lot on whether there's an efficient algorithm or not. If there is, then code golf for optimal solution with a time limit might be good. Otherwise, code golf for optimal solution will just be plain BFS or something. Likewise, if there is an efficient algorithm, then fastest code might not be so good. As long as you don't know how easily this can be solved optimally, I'd probably go with code golf without requiring optimality. \$\endgroup\$ – Martin Ender May 20 '16 at 14:12
  • \$\begingroup\$ Obviously in M:tG you don't generally know the order of your library, but it's not clear to me whether you're proposing that we would. \$\endgroup\$ – Peter Taylor May 20 '16 at 23:13
  • \$\begingroup\$ @PeterTaylor I was considering both for the code challenge. Finding out what cards are in your deck as you go and optimizing for expectation might be more interesting than trying to solve the whole configuration at once. \$\endgroup\$ – xnor May 21 '16 at 6:13
  • \$\begingroup\$ Funnily enough I was just thinking of posting this as a challenge (as a fastest-algorithm) \$\endgroup\$ – Blue May 24 '16 at 12:00
1
\$\begingroup\$

String covering

Given a target string and a list of fragment strings, determine whether the target string can be formed by concatenating fragments, allowing overlaps. Each fragment can be used any number of times.

Example:

cataract, [tar, car, tar, act, rat] -> True

cataract
cat
  tar
     act

Is this a dupe? It's hard to search for. Is it too similar to Imposters at the Zoo?

\$\endgroup\$
  • \$\begingroup\$ Related, related. \$\endgroup\$ – Leaky Nun May 22 '16 at 1:28
  • \$\begingroup\$ This challenge differs from zoo due to the fact that you can't "hide" mismatching parts, so I think it's fine. Not sure if there are any other potential dupes though. (also, I don't think Leaky's "related"s are that related) \$\endgroup\$ – Sp3000 May 22 '16 at 4:25
  • \$\begingroup\$ Just to double check, does "Each fragment can be used any number of times." mean that cancan, [can] -> True? \$\endgroup\$ – Sp3000 May 22 '16 at 6:45
  • \$\begingroup\$ I see a typo: "cat" isn't in the list but "tar" is twice \$\endgroup\$ – ev3commander May 22 '16 at 20:18
1
\$\begingroup\$

Version Comparator

Given two version strings, return a positive, negative or zero value depending on which one is earlier. Version strings consist of one or more non-negative integers separated by full stops, optionally suffixed by a lowercase letter and a final non-negative integer. Examples of versions:

1.5a2
1.5b1
1.5
2.19
2.20b
2.20 or 2.20.0 (these should compare equal)
8.1a
8.1
9
10

When comparing versions the integers should of course be compared numerically, not lexically. Missing components should compare as zero against numbers, but they compare after letters. You should then be able to recognise that the above versions are in version order, but you can choose whether this should be a positive or negative result. Reversing the parameters should obviously negate the sign of the result, but you can return a different absolute value if you prefer.

Builtins that compare versions are disallowed, but things like regexes are OK.

This is , so the shortest program or function wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ How do letters compare numerically? \$\endgroup\$ – Leaky Nun Jun 2 '16 at 12:40
  • \$\begingroup\$ It should never be necessary. \$\endgroup\$ – Neil Jun 2 '16 at 13:10
  • \$\begingroup\$ Test-cases please. Especially 1a1 vs 1a vs 1. \$\endgroup\$ – Leaky Nun Jun 2 '16 at 13:52
  • \$\begingroup\$ @LeakyNun Added some more examples. 1a should compare as if it was 1a0 so less than 1a1 which is less than 1. \$\endgroup\$ – Neil Jun 2 '16 at 15:49
  • \$\begingroup\$ How do 1a and 1b compare? \$\endgroup\$ – Leaky Nun Jun 2 '16 at 15:56
  • \$\begingroup\$ @LeakyNun Well, you already know that 1.5a2 compares before 1.5b1... \$\endgroup\$ – Neil Jun 2 '16 at 16:16
1
\$\begingroup\$

Maximal root multiplicity of integer polynomials

Given a non constant polynomial with integer coefficients, determine the maximal multiplicity of it's (perhaps complex) roots.

Definitions

Multiplicity: Let p be a polynomial with complex coefficients and x0 some complex number. If x0 is a root, it is said to have multiplicity n if p(x) = a(x) * (x-x0)^n where a is another (complex) polynomial such that (x-x0) does not divide a. If x0 is not a root it is defined to have multiplicity 0. Note that the polynomials we consider do only have integral coefficients (consider the integers as a subset of the complex numbers).

Maximal Multiplicity: Let x0,...,xk be the roots of of p,then the maximal multiplicity of p is defined as the maximal multiplicity of xi for i=0,...,k.

I/O

For the input and output, the polynomials can be written in any convenient format, e.g. also as a (variable length) list of coefficients.

Hints

A polynomial has a root of multiplicity greater than one if and only if it shares a root with it's derivative. This can e.g. be checked with the discriminant.

Examples

polynomial     maximal multiplicity
1              0
x^7-1          1
x^8-x^7-x-1    2
x^3-3x^2+3x-1  3
\$\endgroup\$
  • \$\begingroup\$ What sorts of builtins are allowed/banned? Root finding? Polynomial GCD? \$\endgroup\$ – Sp3000 Jun 7 '16 at 9:19
  • \$\begingroup\$ I did not plan to ban anything, would you suggest banning these? \$\endgroup\$ – flawr Jun 7 '16 at 9:22
  • \$\begingroup\$ Not really, it's fine if nothing's banned. Just making sure it was considered :) \$\endgroup\$ – Sp3000 Jun 7 '16 at 9:47
  • 1
    \$\begingroup\$ Do you have any test cases for roots which repeat in different irreducible factors and thus demonstrate that it can't be done by counting multiplicity of irreducible factors? \$\endgroup\$ – Peter Taylor Jun 7 '16 at 10:49
  • \$\begingroup\$ Answering my own question: it can be done by counting multiplicity of irreducible factors, because the minimal polynomial of an algebraic number is a factor of any polynomial of which that number is a root. So factor to irreducibles is worth mentioning as related, although it's far more than needed. \$\endgroup\$ – Peter Taylor Jun 7 '16 at 14:01
  • \$\begingroup\$ I considered factoring as the obvious approach but I think most languages do not have the means to calculate with exact complex numbers (except some CAS' like Mathematica), so the method via resultants/discriminants should just provide another way, which surprisingly only needs integer arithmetic. \$\endgroup\$ – flawr Jun 7 '16 at 14:31
  • \$\begingroup\$ The line on maximal multiplicity ends rather abruptly, I'd assume that that was an accident? Anyway, I'm not sure the terminology "does not divide" is correct here. It's been a while for me, but I think you should say something like: "does not divide a(x) such that the quotient is a polynomial"? \$\endgroup\$ – FryAmTheEggman Jun 7 '16 at 14:40
  • \$\begingroup\$ Right, I think I wanted to add something regarding the constant polynomials, but now I excluded those too for the sake of simplicity. Statements about divisibility usually only make sense in the context of rings, and is defined as: A divides B if there is a C such that B = AC. As soon as you consider a field (in your example the field of rational functions) the divisibility becomes trivial, as any nonzero element divides every element of the field. \$\endgroup\$ – flawr Jun 7 '16 at 14:59
  • \$\begingroup\$ The method via factoring only requires integer arithmetic. I don't find it at all surprising that an approach with resultants only needs integer arithmetic, because subresultants are the standard efficient way to do polynomial GCD. \$\endgroup\$ – Peter Taylor Jun 7 '16 at 16:12
  • \$\begingroup\$ @PeterTaylor I agree, the "surprisingness" is subjective, as far as I know the resultants are usually defined via the product of the differences of the zeros. From that perspective it isn't really obvious that this might result in something even real=) Regarding the factoring we probably did not have the same thing in mind or I do not understand what you mean. I thought about factoring into linear factors, which generally results in general algebraic numbers, far from integers. What did you have in mind? \$\endgroup\$ – flawr Jun 7 '16 at 16:38
  • \$\begingroup\$ Factoring to polynomials which are irreducible over the integers, as in the linked question. Equivalently, as I realised between my first and second comment, factoring to the minimal polynomials of the roots. Edit: ah, but wait. Can the minimal polynomial contain the root multiple times? \$\endgroup\$ – Peter Taylor Jun 7 '16 at 19:10
  • \$\begingroup\$ I'm not sure in general, I think this might fail for some fields with finite characteristic, but for algebraic numbers (=elements of finite field extensions of the rational numbers) the minimal polynomials have distinct roots in the corresponding splitting field. \$\endgroup\$ – flawr Jun 7 '16 at 20:11
1
\$\begingroup\$

Array of Integers to Array of Digits

Given an array of arbitrary length containing only integers, output an array of integers of each digit of each integer in the array.

Notes

  • The input array will only consist of integers in base 10

  • The integers will be in the range of [0, MAX_INT] where MAX_INT is the greatest value an integer can have in your language

  • Assume that all integers will be positive, however you can interpret the integers as signed or unsigned

  • String manipulation and the use of any regex is banned by default

  • The outputted array must be exactly 1 deep and contain only integers

  • The order of the digits in the outputted array must be exactly as they were in the inputted array

  • Leading zeros are to be stripped, as they should be when parsed as an integer

Examples

[2, 3, 5, 7, 11, 13] -> [2, 3, 5, 7, 1, 1, 1, 3]
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
[123, 456, 789, 101112] -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2]
[0, 000, 000123] -> [0, 0, 1, 2, 3] //'000' is treated as '0' and '000123' is treated as '123'
\$\endgroup\$
  • 1
    \$\begingroup\$ Seems pretty straightforward, but pretty trivial in most languages. (Trivial does not mean off topic, but you will likely get lots of answers, as well as some downvotes). You should specify that the integers are in base 10. \$\endgroup\$ – Nathan Merrill May 25 '16 at 14:19
  • 1
    \$\begingroup\$ Will the input array contain 0 or negative integers? \$\endgroup\$ – Leaky Nun May 25 '16 at 19:30
  • 1
    \$\begingroup\$ You say integers, but I take it you mean positive integers? \$\endgroup\$ – xnor May 25 '16 at 22:19
  • \$\begingroup\$ I updated the specification \$\endgroup\$ – Mr Public May 26 '16 at 12:22
  • \$\begingroup\$ You should clarify that leading zeros are stripped, so that people don't need to infer that from the last test case. \$\endgroup\$ – AdmBorkBork May 26 '16 at 18:51
  • \$\begingroup\$ What leading zeroes? Numbers can't have them if they are not strings. Is it an array of numbers or array of strings? \$\endgroup\$ – Qwertiy May 29 '16 at 23:12
  • \$\begingroup\$ It may be interesting to ban the use of string manipulation. This would change the challenge a lot, but it will force the answers to be less trivial. (also note that such a challenge may be frowned upon: meta.codegolf.stackexchange.com/a/8079/31203) \$\endgroup\$ – MegaTom Jun 1 '16 at 15:19
  • \$\begingroup\$ You mention signed integers, but none of your examples contain negative numbers. Do we only need to support non-negative numbers? If not you should specify how negative numbers should be handled and add an example to the test cases. \$\endgroup\$ – Martin Ender Jun 3 '16 at 11:33
  • \$\begingroup\$ Personally, I doubt that string manipulation is the easiest way to do this in most languages? I don't think banning it improves the question. It just seems to make a bunch of languages unusuable, and the rest just entirely ignore it? \$\endgroup\$ – FryAmTheEggman Jun 9 '16 at 20:08
1
\$\begingroup\$

Ping Pong

The Challenge

This challenge is to make a program that prints a text ping-pong animation. Your program is to display a string of tildes with a PING on it moving to the right. Each tick, the text PING moves one to the right one character, reducing the number of tildes on the right by one and increasing the amount on the left by one. Once the PING reaches the right side of the string, it changes to a PONG and the reverse happens (i.e it moves to the left instead).

Rules

  • The number of tildes must always be the same
  • The number of tildes must be at least 30
  • The number of milliseconds between ticks must be at least 10 ms and at most 1 s
  • The PING must start at the left hand of the string

Scoring

Your score is the number of bytes plus/minus the following (all that apply):

  • -10 bytes for browser implementation using the ping after the hash Example
  • +10 bytes if your implementation does not clear previously outputted frames
  • More suggestions welcome

Lowest score wins.

Example Implementation (JS, Ungolfed)

i=0;b=false;len=50;td=40;function urlPong(){location.hash=new Array(i+1).join("~")+(!b?"PING":"PONG")+new Array(len-4-i+1).join("~");if(!b){if(len-4-i<=0){b=true;}else{i++;}}else{if(i<=0){b=false;}else{i--;};}setTimeout(urlPong,td);}urlPong();
\$\endgroup\$
  • 1
    \$\begingroup\$ Why do you restrict this to be in a browser? That seems to add an unnecessary limitation on which languages can reasonably participate. \$\endgroup\$ – FryAmTheEggman Jun 9 '16 at 13:06
  • \$\begingroup\$ Okay, I made it less browser dependant \$\endgroup\$ – takra Jun 10 '16 at 0:57
1
\$\begingroup\$

Implement this cipher

(I'm not sure what to call this cipher)

Goal

Use the algorithm (explained in the Algorithm section) to implement a certain cipher.

The program must read input from STDIN or the closest available equivalent, use the algorithm to generate the ciphertext and a key.

The ciphertext and the key will be written to STDOUT or the closest available equivalent, preferably with the format (ciphertext)\n(key).

Algorithm

Convert the characters in the string into the respective ASCII values. For example:

Hello -> 72 101 108 108 111

Next, you will need to generate a key as long as the string with random numbers in the range of 0-9.

Hello -> 62841

Add the integers in the random number sequence to the ASCII values of the string. In the above examples, 72 would become 78, and 101 would become 104.

72 + 6 = 78, 101 + 2 = 104, 108 + 8 = 116, etc

Next, convert the new ASCII values back to characters. In the above examples, the text Hello has become Nhttp.

Examples

(These are simply examples of what the output might look like. The output can and will vary.)

Hello, World!

Hgqqu/$\\p{ni$
0255634519253

This will be encoded

Zhjs$~koo gj$iuhofgj
60104723305544750226

Rules

  • Submissions must be full programs.
  • Languages newer than the challenge are allowed.
  • Submissions will be scored in bytes.
  • Standard loopholes are forbidden.
  • This is code-golf, so the shortest code wins.

I'm sure this challenge needs a little tidying up and making it look and sound a bit nicer. I'm not very good at writing challenges, so I'd like some advice.

\$\endgroup\$
  • \$\begingroup\$ This is an actual cipher (though not usually with ASCII codes). I don't remember the name right now. But seeing that, it might be a dupe. \$\endgroup\$ – Rɪᴋᴇʀ Jun 12 '16 at 15:13
  • \$\begingroup\$ @EᴀsᴛᴇʀʟʏIʀᴋ Oh, I didn't know that. I thought it was original. \$\endgroup\$ – m654 Jun 12 '16 at 15:32
  • \$\begingroup\$ Yeah, it's called something like a key cipher. \$\endgroup\$ – Rɪᴋᴇʀ Jun 12 '16 at 15:34
  • \$\begingroup\$ @EᴀsᴛᴇʀʟʏIʀᴋ What do you think of this challenge? Do you have any advice for making it... better? \$\endgroup\$ – m654 Jun 12 '16 at 16:16
  • \$\begingroup\$ If properly implemented (i.e. with a pre-shared key which covers the full range of symbols rather than just 0-9) this would be a one-time pad, which is (in some sense) the limit case of the Vigenère cipher. It's not quite a dupe of the Caesar cipher question, but it's barely more complicated. \$\endgroup\$ – Peter Taylor Jun 12 '16 at 21:57
  • \$\begingroup\$ @PeterTaylor The Caesar cipher shifts the characters up the alphabet, but this one shifts the up the whole character range. \$\endgroup\$ – m654 Jun 13 '16 at 7:49
  • \$\begingroup\$ How does this handle overflow? It's easy to imagine a scenario where z (122) gets a number >=5 added to it. \$\endgroup\$ – AdmBorkBork Jun 14 '16 at 15:03
  • \$\begingroup\$ @TimmyD I hadn't thought about that... Maybe it could display an \x code? That's what my Python implementation does, but I'm not sure if that will work in some other languages. \$\endgroup\$ – m654 Jun 14 '16 at 15:07
1
\$\begingroup\$

Latin vs Greek vs Cyrillic / Battle of the Alphabets


Meta: This is just a rough draft, the challenge is still under development, feel free to add suggestions as comments or via chat pinging @flawr

Points that are unclear so far:

  • Is there one fixed typeface for all three?
  • Will the image always be provided in the exact horizontal orientation?
  • How long will the provided text be, just single words? A single line? A multiline piece of text?

These three alphabets are relatively similar and even have some letters in common, but also a lot of distinct letters. In this challenge, you have to write a classifier that can distinguish these three alphabets, when presented with a raster image of a corresponding text.

This is an image from Wikipedia that shows the differences in the capital letters:

enter image description here

This challenge was inspired by this message.

\$\endgroup\$
  • 2
    \$\begingroup\$ What about ambiguity? Expected output for POTATO, COMA, or TAXONOMY? \$\endgroup\$ – Geobits Jun 15 '16 at 14:03
  • \$\begingroup\$ Good point, then all outputs are correct. But I had longer pieces of texts in mind, like multiple lines, but now I'm thinking perhaps just single words would be easier. What would you say? \$\endgroup\$ – flawr Jun 15 '16 at 15:39
  • 1
    \$\begingroup\$ I'd prefer the input to be a single letter, and the correct output to list all alphabets where it belongs, with score being number of correctly classified letters in a test battery (secondary goal is byte count). That may be vulnerable to hashing tricks though. Maybe the letters could also be randomly scaled to, say, 90% to 110%? \$\endgroup\$ – Zgarb Jun 16 '16 at 7:53
  • 1
    \$\begingroup\$ @Zgarb it's still easy to get 100% with computer vision classifiers if there is only one nicely cropped letter as input and all test images have the same exact font as the one used in training \$\endgroup\$ – Fatalize Jun 17 '16 at 8:09
  • \$\begingroup\$ I agree, thats why I'd use at least full words or lines. \$\endgroup\$ – flawr Jun 17 '16 at 8:36
1
\$\begingroup\$

Don't let those functions get away

Introduction

My imaginary language, PremOpt discourages the use of functions. They are the source of every performance problem. Your task today is to fix beginner PremOpt programmer's code.

Every statement's and loop's (if, switch, while, for) content is enclosed in brackets:

<if/switch/while/for> <statement here> {
    <stuff>
}

Switch cases are one liners:

switch <value> {
    case <val1>: <statement1>;
    case <val2>: <statement2>;
    case <val2>: <statement2>;
}

Functions look like these:

function <name>(arg1, arg2, arg3) {
    // Stuff here
}

// Calling a function:
<name>(arg1, arg2, arg3);

Other lines end with a semi-colon.

Variables don't need to be declared, they're already initialized to null, you can set a variable to a value with

variableName = value;

Outputting a value is done by doing

out-><value>

Input

Your input is a string with a piece of code. Each row is separated with a line-feed. The input may or may not contain functions.

Output

You need to remove the functions from the code, and put their content to the where they were called.

Examples:

function hello() {
    sayHello1();
    sayHello2();
}
hello();

becomes

sayHello1();
sayHello2();

Multiple function calls:

function func() {
    doStuff1();
    doStuff2();
}
func();
func();

becomes

doStuff1();
doStuff2();
doStuff1();
doStuff2();

If the function takes in arguments:

function argFunc(arg1, arg2) {
    doStuffWithArg(arg1);
    doStuffWithArg2(arg2);
}
argFunc(myVar1, myVar2);
argFunc(myVar3, myVar4);

then you need to change the arguments inside the function to match with the calling arguments

doStuffWithArg(myVar1);
doStuffWithArg2(myVar2);
doStuffWithArg(myVar3);
doStuffWithArg2(myVar4);

Test cases

fibonacci sequence:

a = 1;
b = 1;
function getNextNumber(num1, num2) {
    return num1 + num2;
}

while(true) {
    a = getNextNumber(a, b);
    out->a;
    b = getNextNumber(a, b);
    out->b;
}

Should become

a = 1;
b = 1;

while(true) {
    a = a + b;
    out->a;
    b = a + b;
    out->b;
}

FizzBuzz:

for (counter = 0; counter <= 100; counter++) {
    checkNumber(counter);
}

function checkNumber(num) {
    if (num % 3 == 0  num % 5 == 0) {
        out->"Fizz Buzz";
    } else if (num % 3 == 0) {
        out->"Fizz"
    } else if (num % 5 == 0) {
        out->"Buzz"
    } else {
        out->num;
    }
    out->newLine;
}

Becomes:

for (counter = 0; counter <= 100; counter++) {
    if (counter % 3 == 0  counter % 5 == 0) {
        out->"Fizz Buzz";
    } else if (counter % 3 == 0) {
        out->"Fizz"
    } else if (counter % 5 == 0) {
        out->"Buzz"
    } else {
        out->counter;
    }
    out->newLine;
}

Rules

  • There'll be no recursive functions in the input
  • Standard loopholes are forbidden
\$\endgroup\$
  • \$\begingroup\$ This grammar doesn't seem to be well defined enough for this to not be too broad. What about functions in functions? What kinds of literals are expected to be supported? Can functions have the same name but different arguments? What operators have to be supported (specifically w.r.t. functions, like myFun(++foo)++)? What about functions that return things but have more than one operations, but are in a heavily nested statement? This is all just from the top of my head, there are likely more such problems. I think you would need to heavily simplify the language for this to be a good question. \$\endgroup\$ – FryAmTheEggman Jun 28 '16 at 12:58
1
\$\begingroup\$

fix show

Your task is given n, you must print first n character returned from Haskell expression fix show.

Let me explain how fix show produces the "magic" string.

show is just escaping the string and then add quote. Since the resulting string consists only double quotes and backslash, show then essentially just put backslash before every character then quote the resulting string.

show str = '"' : concat ( zipWith (\x y->[x,y]) (repeat '\\') str ) ++ "\"" -- Well, this is not what prelude give, but

fix is, well, fixpoint combinator. But thanks for laziness, it won't do a infinite loop first.

The string is equivalent to the string defined below:

Assuming there is a series of string. The first string is "" and the next series is just application of show to previous string:

"" "\"\"" "\"\\"\\"\"" "\"\\"\\\\"\\\\"\\"\"" "\"\\"\\\\"\\\\\\\\"\\\\\\\\"\\\\"\\"\""

For all n, there is k so that for all l above k, n-th character of l-th string from series is same. That character is the n-th character of fix show

TODO: I hate the sentence above, please fix it.

The first 100 character in resulting string

"\"\\\"\\\\\\\"\\\\\\\\\\\\\\\"\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

So, another implementation is

fixshow = '"' : zip (repeat '\') fixshow ++ "\""

Rules

  1. You are not allowed to use function fix, show, and the equivalent functions.
  2. Shortest answer wins.

Sandbox question

Is there another way to prevent answer like flip take$fix show, or without importing f k=k$f k;j n=take n$f show. And how about array programming language like APL, J and Jelly?

\$\endgroup\$
  • \$\begingroup\$ Your construction doesn't work because zip doesn't intersperse the characters, but creates a list of tuples. I think the backslashes also need escaping. It would be helpful to explain that the number of backslashes in sequence goes 1,3,7,15,... with numbers one less than powers of two. It would be a shame to eliminate all languages with lazy evaluation or generators. It's also vague. Python has generators but they are totally useless here. Even Haskell needs a costly import to get fix. \$\endgroup\$ – xnor Jun 1 '16 at 3:52
  • 1
    \$\begingroup\$ The output should start "\"\\\"\\\\\\\"\\\\\\\\\\\\\\\". \$\endgroup\$ – xnor Jun 1 '16 at 3:58
  • \$\begingroup\$ Language-specific questions are not likely to make much challenge acceptors. \$\endgroup\$ – Erik the Outgolfer Jun 3 '16 at 7:25
  • \$\begingroup\$ @EʀɪᴋᴛʜᴇGᴏʟғᴇʀ This question isn't language specific, it just involves implementing a particular Haskell program in any other language. That said, it was a bit hard to figure out what was going on as someone who doesn't really know Haskell. \$\endgroup\$ – FryAmTheEggman Jun 3 '16 at 13:18
  • \$\begingroup\$ @FryAmTheEggman This should be closed as "unclear what you're asking". \$\endgroup\$ – Erik the Outgolfer Jun 3 '16 at 13:55
  • \$\begingroup\$ seems like a cool challenge, but instead of trying to explain lazy evaluation, just define show rigorously, and then say the challenge is to output the limit of applying show n times on the empty string. also, your output is wrong. \$\endgroup\$ – proud haskeller Jun 3 '16 at 18:46
  • \$\begingroup\$ @proudhaskeller when you say the limit of applying show n times, do you mean result of applying show infinite times on ""? \$\endgroup\$ – Akangka Jun 4 '16 at 15:21
  • \$\begingroup\$ @xnor 1. I just hate the answer flip take$fix show. How do I avoid it? 2. Fixed. \$\endgroup\$ – Akangka Jun 4 '16 at 15:24
  • \$\begingroup\$ @ChristianIrwan no, because there is no such thing, applying infinite times. instead, if you have a series of strings, first the empty string, then applying once, then twice, and so on, and at each string look at the ith character, from some point on it will be identical in all the strings of the series, and the ith character of the limit will be this character. \$\endgroup\$ – proud haskeller Jun 4 '16 at 15:29
  • \$\begingroup\$ @proudhaskeller Oh, I see. Thanks. \$\endgroup\$ – Akangka Jun 4 '16 at 16:04
  • \$\begingroup\$ The implementation with zipWith. Maybe you could just ban the command show and equivalents? I think implementing it and a a pseudo-fix would be interesting and not definitely better than concatenating powers-of-2-sized blocks. \$\endgroup\$ – xnor Jun 5 '16 at 2:54
  • \$\begingroup\$ *The implementation with zipWith doesn't work. \$\endgroup\$ – xnor Jun 5 '16 at 21:58
1
\$\begingroup\$

Golfing with ultrasound

Within medical physics, the percentage of ultrasound reflected between material boundaries can be calculated using two pieces of data: the density(p) and the speed(c) at which sound travels through the material.

To calculated the percentage reflection the following equation can be used

(Z1-Z2)^2 / (Z1+Z2)^2

Where Z1 and Z2 are the acoustic impedances(Z) of the two materials. Z is calculated such that Z=pc That is density * speed of sound in the material

This is where the issue lies

I have two ways of asking the question

1:

Given the acoustic impedance for two materials, calculate the percentage reflection.

2:

Given the density and speed of sound in two materials, calculate the percentage reflection

Reason

The first method will be much simpler, in the way you are just plugging values into a formula. However I feel that method 2 is heavy on the inputs, and I understand that four inputs is a large number of inputs in golfing challenges

On posting the question I will also add a number of test cases

\$\endgroup\$
  • \$\begingroup\$ Firstly, I think you should add test cases while it's still in the sandbox. I find it's easy to miss important ones. In your formula you say Z=pc. What is c? I think you should add some formatting to your formulas, as they are a bit hard to read. You could also consider using some TeX service to generate an image of the formula for you. Also, density is usually denoted by ρ. \$\endgroup\$ – FryAmTheEggman Jun 29 '16 at 19:38
  • \$\begingroup\$ I was going to use rho, but I didn't know where to find one. In hind sight I could have copied and pasted from Wikipedia. Speed should have been given as c not v. But I will make clear what I mean by Z=pc. What is TeX? I've not heard of it before? \$\endgroup\$ – george Jun 29 '16 at 19:41
  • \$\begingroup\$ TeX is a very popular typesetting program, most of your textbooks were probably made using some variant of it. For example, go to this site and enter \frac{(Z_1-Z_2)^2}{(Z_1+Z_2)^2} as the text. You should see a much easier to read version of your formula as an image. \$\endgroup\$ – FryAmTheEggman Jun 29 '16 at 19:45
  • \$\begingroup\$ @FryAmTheEggman Wow that's a really cool website, thanks! I will edit the question soon and hopefully it will be better \$\endgroup\$ – george Jun 29 '16 at 19:50
  • 1
    \$\begingroup\$ With either option, it looks like there's a direct mathematical formula that leaves little to golf. \$\endgroup\$ – xnor Jun 29 '16 at 22:45
1
\$\begingroup\$

Write a BF to Hexagony Converter!



According to community moderator Martin Ender ♦:

Hexagony is Turing-complete as any brainfuck program can be translated to Hexagony with some effort. (Source)

Your program's job is simple: take a valid brainfuck program, and convert it to an equivalent Hexagony program. For completeness, here are all the relavant commands in both BrainFuck and Hexaongy (taken from esolangs.org).

brainfuck

brainfuck operates on an array of memory cells, also referred to as the tape, each initially set to zero. There is a pointer, initially pointing to the first memory cell. The commands are:

  • > Move the pointer to the right
  • < Move the pointer to the left
  • + Increment the memory cell under the pointer
  • - Decrement the memory cell under the pointer
  • . Output the character signified by the cell at the pointer
  • , Input a character and store it in the cell at the pointer (-1 for EOF)
  • [ Jump past the matching ] if the cell under the pointer is less than or equal to 0
  • ] Jump back to the matching [ if the cell under the pointer is nonzero

All characters other than ><+-.,[] should be considered comments and ignored.

Modifications:

  • Infinite tape in both directions
  • Arbitrary precision integers (like hexagony)
    • No overflow/underflow
  • [ acts the same for negative numbers as it does for 0

Hexagony

Source code

The source code consists of printable ASCII characters and line feeds and is interpreted as a pointy-topped hexagonal grid, where each cell holds a single-character command.

Because of this restriction, the number of commands in the source code will always be a centered hexagonal number. For reference, the first 10 centered hexagonal numbers are:

1, 7, 19, 37, 61, 91, 127, 169, 217, 271

When reading a source file, Hexagony first strips all whitespace characters. Then the remaining source code is padded to the next centered hexagonal number with no-ops and rearranged it into a regular hexagon. This means that the spaces in the examples above were only inserted for cosmetic reasons but don't have to be included in the source code. The following three programs are identical:

   a b c  
  d e f g 
 h . . . .  
  . . . .   
   . . . 

abcdefgh...........

abcdefgh

But note that

abcdefg

would instead be the short form of

   a b 
  c d e  
   f g

Control flow

Hexagony has 6 instruction pointers (IPs). They start out in the corners of the source code, pointing along the edge in the clockwise direction. Only one IP is active at any given time, initially the one in the top left corner (moving to the right). There are commands which let you switch to another IP, in which case the current IP will make another move (but not execute the next command), and then the new IP will start by executing its current command before making its first move. Each IP has an index from 0 to 5:

   0 . 1
  . . . .
 5 . . . 2
  . . . .
   4 . 3

The direction of an IP can be changed via several commands which resemble mirrors and branches.

The edges of the hexagon wrap around to the opposite edge. In all of the following grids, if an IP starts out on the a moving towards the b, the letters will be executed in order before returning to a:

   . . . .          . a . .          . . k .          . g . .   
  a b c d e        . . b . .        . . j . .        . h . . a  
 . . . . . .      g . . c . .      . . i . . e      . i . . b . 
. . . . . . .    . h . . d . .    . . h . . d .    . j . . c . .
 f g h i j k      . i . . e .      . g . . c .      k . . d . . 
  . . . . .        . j . . f        f . . b .        . . e . .  
   . . . .          . k . .          . . a .          . f . .   

If the IP leaves the grid through corner in the direction of the corner there are two possibilities:

-> . . . .   
  . . . . .  
 . . . . . . 
. . . . . . . ->
 . . . . . . 
  . . . . .  
-> . . . .  

If the current memory cell (see below) is positive, the IP will continue on the bottom row. If it's zero or negative, the IP will continue on the top row. For the other 5 corners, just rotate the picture. Note that if the IP leaves the grid in a corner but doesn't point at a corner, the wrapping happens normally. This means that there are two paths that lead to each corner:

      . . . . ->   
     . . . . .  
    . . . . . . 
-> . . . . . . .
    . . . . . . 
     . . . . .  
      . . . . ->

Special characters

. is a no-op: the IP will simply pass through.
@ terminates the program.

Arithmetic

) increments the current memory edge.
( decrements the current memory edge.

I/O

, reads a single byte from STDIN and sets the current memory edge to its value, or -1 if EOF is reached.
; takes the current memory edge modulo 256 (positive) and writes the corresponding byte to STDOUT.

Control flow

$ is a jump. When executed, the IP completely ignores the next command in its current direction. This is like Befunge's #.
_, |, /, \ are mirrors. They reflect the IP in the direction you'd expect. For completeness, the following table shows how they deflect an incoming IP. The top row corresponds to the current direction of the IP, the left column to the mirror, and the table cell shows the outgoing direction of the IP:

  cmd │  E SE SW  W NW NE
──────┼────────────────────
   /  │ NW  W SW SE  E NE
   \  │ SW SE  E NE NW  W
   _  │  E NE NW  W SW SE
   |  │  W SW SE  E NE NW

< and > act as either mirrors or branches, depending on the incoming direction. The cells indicated as ?? are where they act as branches. In these cases, if the current memory edge is positive, the IP takes a 60° right turn (e.g. < turns E into SE). If the current memory edge is zero or negative, the IP takes a 60° left turn (e.g. < turns E into NE).

  cmd │  E SE SW  W NW NE
──────┼────────────────────
   <  │ ?? NW  W  E  W SW 
   >  │  W  E NE ?? SE  E

[ switches to the previous IP (wrapping around from 0 to 5).
] switches to the next IP (wrapping around from 5 to 0).
# takes the current memory edge modulo 6 and switches to the IP with that index.

Memory manipulation

{ moves the MP to the left neighbour.
} moves the MP to the right neighbour.
" moves the MP backwards and to the left. This is equivalent to =}=.
' moves the MP backwards and to the right. This is equivalent to ={=.
= reverses the direction of the MP. (This doesn't affect the current memory edge, but changes which edges are considered the left and right neighbour.)

Some commands/description omitted for conciseness, full list here.

Other rules:

  • Input/Output may be done however is most natural for your language
    • Output does not have to be formatted like a hexagon
  • Must run in a reasonable amount of time
    • Minimal brute-force
    • No brute-forcing the entire program
  • You can only use Hexagony commands specified in this challenge.
  • This is , so shortest code wins
    • {META NOTE: I know this challenge is hard, is there a better way to score?}
  • As usual, standard loopholes are prohibited.

Test Cases:

Input: (cat)

,.[,.]

Output: (example)

   \ . .
  < _ . .
 . _ ; . .
  . . > ,
   . @ .

Input: ("123")

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

Output: (example)

     ) ) ) ) )
    ) ) ; ) ; /
   ) ) ) ) ) ) /
  ) ) ) ) ) ) ) /
 ) ) ) ) ) ) ) ) /
  ) ) ) ) ) ) ) )
   ) ) ) ) ) ) )
    ) ) ) ) ) )
     . . @ ; <

Input: (@primo's infinite Fibonacci)

+[[<+>->+>+<<]>]

Output: (example)

       ) \ . . . . |
      . | . / { } < .
     . . . . > [ . / >
    . . . . . . . . . .
   . . . . . . @ . . . .
  / . ] < . > < . ] . . .
 _ > " ' / | . > < . . . .
  _ / . . . / . . [ . . .
   . / . . . . . . ) . .
    . . . . . . . . ] .
     . . . [ . . . . |
      . . [ . . . . (
       . \ ) ] ) ] <
\$\endgroup\$
  • \$\begingroup\$ I am quite sure that the outputs are not unique, are they? \$\endgroup\$ – flawr Jul 4 '16 at 16:18
  • \$\begingroup\$ @flawr The outputs do not have to be unique as long as the inputted BF programs do the exact same thing, under all circumstances. \$\endgroup\$ – Blue Jul 4 '16 at 16:22
  • 1
    \$\begingroup\$ I think Hexagony's padding rules would be important, especially if you don't require the output to be formatted like a hexagon. I predict most answers to generate tons of no-ops at the end, which can't be omitted without messing up the layout. \$\endgroup\$ – Martin Ender Jul 4 '16 at 16:26
  • \$\begingroup\$ I don't think it's a good idea to mask brainfuck in the question body, since it hurts searchability. You're going to need the brainfuck tag anyway. \$\endgroup\$ – Dennis Jul 4 '16 at 16:36
  • \$\begingroup\$ @Dennis Should I change the title as well? \$\endgroup\$ – Blue Jul 4 '16 at 16:48
  • \$\begingroup\$ No, the title cannot contain fuck due to network-wide rules. \$\endgroup\$ – Dennis Jul 4 '16 at 16:51
  • \$\begingroup\$ I think this challenge is actually rather easy except for translating [] loops: everything else is a simple mapping. I think the most likely type of answer will just generate the code mostly linearly while keeping track of a "stack" of loops and then figuring out what size hexagon to put it in. \$\endgroup\$ – FryAmTheEggman Jul 4 '16 at 18:34
  • \$\begingroup\$ @FryAmTheEggman Should I make this challenge metagolf to encourage less linear output? \$\endgroup\$ – Blue Jul 4 '16 at 20:29
  • \$\begingroup\$ @Blue That would certainly be interesting, but I have doubts you'd get a lot of participation in that case. \$\endgroup\$ – Martin Ender Jul 4 '16 at 20:41
  • \$\begingroup\$ I agree with Martin, I may not have worded my last comment very well, as the [] translations will actually be rather time consuming, if not difficult. Further increasing the complexity of the challenge will make it more interesting, but it might be too much to expect more than an answer or two at that point. \$\endgroup\$ – FryAmTheEggman Jul 4 '16 at 21:11
1
\$\begingroup\$

Platformer game

Write a platformer game.

Rules:

  • Keyboard input, minimum three commands: left, right and jump;
  • Real-time. Screen should update (and the game iterate) on timer. Update speed should not depend on CPU speed. FPS should be between 2 and 120;
  • It should be possible both to win and to lose (the game can although be very hard and require preparing a special bot to win or to lose);
  • Playing field should have at lest 64 positions, minimum width is 6, minimum height is 5.
  • Player may move left, right or jump. Player moves down automatically unless on a platform. Jumping means moving up for some limited time (not higher than 67% of playing field's height), then falling down like usual.
  • Falling down outside playing field is losing the game. Stepping on 6 distinct platforms is a win.
  • Player, platforms and borders of area should be visible on playing field. If output method is ASCII art, it may looks like this:

    .....----...
    ............
    ...@....----
    ..---.......
    .......---..
    ............
    
  • Platforms may be horizontal, vertical, diagonal. Platforms should not overlap (except of differently oriented). Platform's projection to horizontal and vertical axes should not overlap for at least 4 platforms. Example of too projection-overlapping playing field:

    ............
    ....@.......
    .--.--..--..
    ............
    .--.--..--..
    ............
    
  • Platforms may move. Overlapping rules apply only to initial positions.

  • The game should track losing and winning conditions and stop the game, outputting distinct messages in case of lose or win.
\$\endgroup\$
  • 1
    \$\begingroup\$ I feel like this spec is much too broad. Different answers will vary so much that I don't think they will be comparable. I think you need to specify each interaction precisely. \$\endgroup\$ – FryAmTheEggman Jul 4 '16 at 19:43
  • \$\begingroup\$ @FryAmTheEggman, The idea was to just implement a platformer game, with rules only to prevent "degenerate", uninteresting cases (like 1x1 field with 0 platforms and unconditional lose in the first turn). Do you think it would be more interesting if each answer's game would basically be the same? \$\endgroup\$ – Vi. Jul 4 '16 at 21:06
  • \$\begingroup\$ I think it is a much more interesting golfing problem if all the games are the same, as otherwise what is the point of golfing? I don't think this is a good site to try to get interesting platforming games, as I don't think this will work with either a pop-con or code-challenge either. \$\endgroup\$ – FryAmTheEggman Jul 4 '16 at 21:09
  • \$\begingroup\$ I though it would be interesting if main point were to design the game to be compactly implementable, not just to implement already designed game in a compact way... \$\endgroup\$ – Vi. Jul 4 '16 at 21:22
1
\$\begingroup\$

Compute h-index of PPCG users

Thanks to @Suever for his help refining this challenge.

Background

The h-index is a commonly used metric that measures the amount and quality of publications of a given scholar or researcher. It is defined as follows:

A scholar with an h-index of n has published n papers each of which has been cited at least n times.

Adaptation for PPCG

In this challenge I propose to compute the h-index of PPCG users based on the analogy

  • paperanswer;
  • paper's citations → answer's vote count, defined as upvotes minus downvotes.

The following examples illustrate the computation of h-index. The array to the left is the vote count of answers in descending order for a hypothetical user, and the number to the right is the resulting h-index:

[5 3 2 1 1]    2
[1 1 1]        1
[]             0
[-1 -2]        0
[0]            0
[9 4 3 ...]    3

Referring to the last example, note that we don't need to know the array entries after the 3.

The challenge

Given a user identification, output their h-index.

Rules

User identification can be defined as anything reasonable, such as user number, user name, or user name without spaces.

The result must be based on actual data from the PPCG site. You may want to take a look at the StackExchange API, for example here.

Note that some users have a lot of answers. For one such user the API may not give all the results, or may only give them split across several chunks. However, if you ask the API to provide the results with an appropriate sorting you may not need all of them to compute the h-index (see last example above). Also, you may assume that the h-index of any user will be less than 100.

If the answer can't be tested in an online compiler (for example due to restrictions to read web content), you are encouraged (although not required) to post some evidence that the answer works, such as a screen capture.

This is code golf. Fewest bytes wins.

Table of h-indices

After submitting your answer, you may optionally edit the table below to include your own h-index, in the indicated format. Please keep the table in decreasing order, so that users with higher h-indices appear higher on the table. I will remove the dummy user names when the table has some actual content.

Example user name: 5
Another example: 3
Yet another user: 3
\$\endgroup\$
  • \$\begingroup\$ @FryAmTheEggman Having 1000 answers is irrelevant only if you ask the API for the answers in descending order of votes. The note is intended to make it clear that asking for the answers in that order is probably a good idea. I've rephrased a little, I hope it's clearer now. As for how many results the API provides in the same chunk, I think the limit is 100, but I'm not sure \$\endgroup\$ – Luis Mendo Jul 4 '16 at 23:45
  • \$\begingroup\$ Yes, I think that is much clearer now. Also, Yet another user? I hate that guy... \$\endgroup\$ – FryAmTheEggman Jul 5 '16 at 0:13
  • \$\begingroup\$ We've had a challenge to find the h index. With that done, this mostly looks like a question to query the SE API. \$\endgroup\$ – xnor Jul 5 '16 at 10:28
  • \$\begingroup\$ @xnor Oh. Pity. I didn't see that challenge. I guess this is mostly a duplicate then \$\endgroup\$ – Luis Mendo Jul 5 '16 at 11:11
1
\$\begingroup\$

What is closer?

Tags: ,


Inputs: a, b (Both integer and positive) .Output: Integer, in natural numbers sequence.

We have one single atom which has a electrons, we ionize the atom with b positive charges (take b electrons out).

The output is the sum of the orbital quantum numbers (n,l,ml) which is nearest to the atom shell.

EXAMPLE: We take 3 electrons from 26Fe, Now we have 26Fe3+. We need to get the sum of the nearest remained orbitals quantum numbers to the shell.

We have this configuration for Fe3+: [Ar], 3d3, 4s2

The nearest orbital to shell has these numbers:

n = 4
l = 0
ml = 0

In this case:

a => 26
b => 3
output => 4

My 3rd grade chemistry teacher asked me once to create such a program, but I didn't success, I found the paper that my teacher wrote these descriptions on it and I typed it here because I believe that someone might create an interesting code-golf for this.

\$\endgroup\$
  • \$\begingroup\$ You can't create the atoms and electrons tags right now (2/150 rep). Even then, we're not going to need them. \$\endgroup\$ – user48538 Jul 6 '16 at 9:03
  • \$\begingroup\$ This is a long way from being self-contained. I don't know whether someone who knows quantum chemistry would find the question clear, but I need a link to some background material to even start trying to work out what I'm supposed to do. \$\endgroup\$ – Peter Taylor Jul 6 '16 at 16:59

You must log in to answer this question.

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