459
\$\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

2565 Answers 2565

1
\$\begingroup\$

Print a shuffled deck of cards

\$\endgroup\$
  • \$\begingroup\$ What prevents me from outputting the cards in the same order every time? It's hard to specify randomness, as we've seen in other meta posts. You could say "I will run your program 100 times; no two outputs should be identical" since the probability of this happening is miniscule if the output is truly randomized. \$\endgroup\$ – musicman523 Jun 2 '17 at 23:05
  • \$\begingroup\$ I believe "all permutations must have an equal opportunity of being chosen" is what is usually used. \$\endgroup\$ – totallyhuman Jun 3 '17 at 0:57
  • 2
    \$\begingroup\$ I don't think having to output the Unicode card characters adds anything to the challenge and the answers (except for bytes...). \$\endgroup\$ – totallyhuman Jun 3 '17 at 0:58
  • \$\begingroup\$ All I see in my browser is a bunch of rectangles with diagonals. \$\endgroup\$ – Dennis Jun 3 '17 at 21:30
  • \$\begingroup\$ @Dennis Install the Noto fonts. \$\endgroup\$ – dkudriavtsev Jun 4 '17 at 1:09
  • \$\begingroup\$ "all permutations must have an equal opportunity of being chosen" is actually EXTREMELY difficult, the random number generators of most languages aren't up to that -- even making sure every combination can come up is quite tricky as you need 225 bits of randomness. \$\endgroup\$ – Chris Jefferson Jun 4 '17 at 21:15
  • \$\begingroup\$ Please delete this now that it is posted. \$\endgroup\$ – programmer5000 Aug 1 '17 at 16:08
  • \$\begingroup\$ @programmer5000 It's already only a title \$\endgroup\$ – dkudriavtsev Aug 1 '17 at 23:30
  • 1
    \$\begingroup\$ It should still be deleted. \$\endgroup\$ – totallyhuman Aug 10 '17 at 20:59
1
\$\begingroup\$

Collatz Bearings

Everyone knows the collatz conjecture. It is that this function:

Collatz Conjecture

when repeatedly applied on a positive non-zero integer will reach one.

There are many ways to visualise this. Inspired by this post, with the original source of this method here, this is how we will do it:

Start at 1, with a northward bearing. The next numbers will be one unit (of any, consistent) size, and x degrees clockwise (+x) if it is even, and x degrees anticlockwise (-x) if it is odd.

An example of this can be seen here (Though it starts with an eastward bearing). It uses a few hundred random starting points and goes backwards. But it's probably easier to build it backwards.

Visualisation of the Collatz conjecture

Here is a graph-like visualisation, showing the first 8 levels:

First 8 levels

There can be collisions.

Your task is to take two numbers, which would correspond to 2 nodes on that tree, and return the bearing of the second node to the first node.

Input

3 numbers. Positive integer a, Positive integer b, and angle x, in any unit you desire. b > a > 0, x is the angle of seperation, in it's simplest form (mod 360 for degrees, mod 2pi for radians, or having the upper half be negative if you wish.) a and b are guaranteed to be in different places (e.g., you won't have a = 20 and b = 21.)

Output

Using the method described above, the bearing of b from a in the graph, in the units of the input angle.

Scoring

This is code-golf, so the shortest program in bytes wins.

Note

If the Collatz Conjecture is eventually proven wrong, you do not need to take inputs where repeated application does not reach 1.

\$\endgroup\$
  • \$\begingroup\$ I don't understand what we're supposed to do. If we start at 1 then we'll go 1 -> 4 -> 2 -> 1 so we should draw a chain LLRLLRLLR.... The supplied image doesn't look like that chain. \$\endgroup\$ – Peter Taylor Jun 5 '17 at 14:55
  • \$\begingroup\$ 1 is the starting point. Then you go clockwise up to 2. It's a really zoomed out image, I'll post a zoomed in one with numbers \$\endgroup\$ – Artyer Jun 5 '17 at 14:56
  • \$\begingroup\$ I think what's missing is something to say that the iteration is backwards. At least, that's how I can make sense of the graph: "It uses a few hundred random starting points" still confuses the issue. "The bearing of the second angle to the first angle" is also rather confusing: judging by the Output section I think it should be node rather than angle. \$\endgroup\$ – Peter Taylor Jun 5 '17 at 22:26
1
\$\begingroup\$

Efficiently find the median

Background

Computer scientists have spent a long time looking into ways of sorting data faster. One of the known discoveries is that if you can use the actual values of the data, sorting can be faster than if you can only compare them.

Finding the median of a list is a similar operation to sorting it (you can trivially implement it via sorting the list, then taking the element in the middle). However, if you're in an environment where you can only compare list elements (as opposed to looking at the elements directly), this is not typically the fastest way to find the median, as sorts are hurt more badly by the comparison restriction than finding the nth item is. What's the fastest way? Well, finding that is what this challenge is about. (However, you may want to read this Wikipedia article to get some ideas of the approaches that are typically used. I can't guarantee that the algorithm given there is the best, though, especially on a problem of the limited size given here.)

The task

Write a program that finds the index of the median element within a list of 31 elements. However, the program may not take the list as input, and may not inspect its values directly. Rather, the program may only make comparisons to determine which of two indexes corresponds to the larger element, via calling a separate comparison function. (In other words, your program deals entirely with list indexes, not list values.)

In order to avoid solutions that brute-force their way through all possible algorithms, you must be able to run at least one worst-case input (i.e. an input that takes the maximum possible number of comparisons), using a comparison function which simply compares two array elements, in under 10 minutes on some computer you have access to. (Solutions which do not use brute force to find an algorithm are unlikely to get anywhere near this time bound.)

Clarifications

  • You may assume that all the list elements are distinct, i.e. the comparison function will always specify that one of the elements is larger, no matter how they're compared.
  • You may choose the format in which the comparison function provides output, but there must only be two possible outputs (meaning "item at first index is larger" and "item at second index is larger") for any possible query; you can't return values that mean "item at second index is much larger" or anything like that.
  • The comparison function will act consistently, i.e. if it claims that the list item at index A is larger than the list item at index B, it will always claim that; and if it also claims that the list item at index B is larger than the list item at index C, it will additionally claim that the list item at index A is larger than the list item at index C.
  • You may take the comparison function as input, or assume that it's already defined with a specific name. This is not , so there's no need to try to exploit the freedom you have here to save bytes; feel free to write it in the most readable way. (The comparison function itself is not part of the submission, but you should probably include one for testing purposes and an example of what it looks like.)
  • You may exploit the knowledge that the input list is exactly 31 elements long, if you wish (your program doesn't have to work in other cases, although of course it can if you want it to).
  • If your language doesn't have functions, you may write the comparison function via a source code insertion, so long as the rest of the code doesn't attempt to inspect its internals. (However, you may as well just pick a different language in this case; the scoring method is based entirely on the algorithm you use, and picking a different language won't change your score at all.)

Victory condition

Your score for this challenge is equal to the maximum number of times the comparison function can be called during a run of the program. Obviously, lower is better.

In the case of a tie, the first submission achieving the optimal score will win. (In other words, you don't gain anything from copying someone else's solution but golfing the code, or the like; you'll have to find an algorithmic improvement.)

Sandbox questions

Is this scoring method , , or ? I guess I'd want to call it (by analogy with ) but that doesn't exist and I'm not sure it should be created. EDIT: None of the above, it's .

\$\endgroup\$
  • 2
    \$\begingroup\$ I would expect the first answer to get a perfect score (because why submit one which doesn't?), at which point the question is dead. \$\endgroup\$ – Peter Taylor Mar 22 '17 at 12:32
  • \$\begingroup\$ @PeterTaylor: I expect a perfect score to be fairly hard to accomplish on this challenge. I'm not sure the optimal algorithm is known, and the problem's too large to bruteforce. \$\endgroup\$ – user62131 Mar 22 '17 at 14:43
  • \$\begingroup\$ I don't see anything in the question which rules out brute force. \$\endgroup\$ – Peter Taylor Mar 28 '17 at 8:41
  • \$\begingroup\$ Oh, I was thinking of bruteforcing an algorithm before writing the program, which isn't possible with currently available amounts of computational power. You're right that you could just write a program that bruteforces all possible algorithms at runtime and then runs the fastest (although it would clearly be impossible to test). I should probably place a limit on runtime in order to fix that. \$\endgroup\$ – user62131 Mar 28 '17 at 15:11
1
\$\begingroup\$

The Travelling Merchant

Economy is flourishing in the great Kingdom of Pipysigea [pee-pee-see-gee-ah], since the bandits have been driven away by the King's army. Especially, many people have decided to make trade their... trade, and have become merchants. You were one of them. You used most of your life's savings to purchase a good wagon and some animals of your choice. (Note: it can't be dragons. Sorry.) Unfortunately, you have just moved to Pipysigea from far away, attracted by the promises of wealth and security, so you don't really know much about the Kingdom: you have just bought a map, so you know the names of the cities and where they are, but you don't really know how long it's going to take to travel from one city to another.

So what is your goal? Being a merchant, you'll want to travel from city to city to get an idea of what good they want to buy and what goods they sell.

There will be a total of X kinds of goods in the Kingdom, and each city will be looking to buy 3 kinds and will be selling 3 kinds of goods. You will need to find out whether their prices are good for you: for example, the city of Puzzleon might be selling iron for 4 coins per unit and buying bread for 1 coin per unit, and the city of Stackapor might be selling wool for 2 coins per unit and buying iron for 5 coins per unit: in this case, it would be profitable to buy iron from Puzzleon and then travel to Stackapor to sell it.

But beware: trade is ever-changing, and prices are going to change based on what you and other merchants do. If you keep selling iron in Stackapor over and over, their need for it will soon start lowering, and so will the price they offer for that good. Similarily, if you buy a lot of iron from Puzzleon, the quantity at their disposal will lower and the amount of coins they want for it will start getting higher, until they run out of iron and stop selling it.

Beware, also, of taxes! The arch-enemy of any merchant. Every seven days (= turns) you are going to be taxed, based on your current wealth, which is measured by actual coins and amount of goods in your wagon. After all, his majesty King Golfus II deserves compensation for ridding the Kingdom of bandits and letting it prosper. And also for having established free market, of course.

During your travels, you will eventually encounter fellow (or rival, depending on your attitude) merchants, with whom you can trade just like you can with cities. You can decide to keep walking or to stop and trade. Every time this happens, you can tell them 1 good you are willing to buy (or none) and the price you offer, and the same with 1 good you are willing to sell. The other merchant will do the same. Then, you can respond by accepting or declining both of their proposals or just one. They will do the same with your proposals. Once all this is done with, you can resume your travel.

You lose if you go bankrupt: that happens when the time comes to pay taxes and you don't have enough coins. You automatically win if all other merchants have gone bankrupt.

The game ends after XXX turns, and the winner will be the merchant with the most coins.


Rules

  • Antitrust Law: a merchant cannot be made specifically to support another merchant. (To help ensure this, merchants can never know the name of the merchant they are trading with)

  • Fair Trade: a merchant cannot be made specifically to harm the trade of another merchant.

  • Fair Code: King Golfus II is the one and only ruler, and a merchant may not interfere with the law (also known as "The Controller")


Technicalities

You will be provided with a list of randomly generated cities (e.g. 10 to 15) with their coordinates on the map (a simple cartesian plan with X and Y values). The terrain is assumed to be pretty much the same overall, so travel times are based only on distance (initially I thought about giving specific travel costs - e.g. difficulty of road, maybe mountainous or muddy or whatever - to each "link", unbeknownst to the merchant, but felt like it would have complicated things too much. If you think it would be a nice addition, feel free to say it in the comments!)

Every city has a randomly generated list of 3 items to sell and 3 items to buy. The quantity they have available of each item they sell is also randomly generated, as well as the prices of all 6 kinds. Obviously, if a city sells iron they won't also be looking to buy it.

Each merchant can only be in one of these three positions:

  • in a city

  • on the way from one city to another

  • midway between two cities, stopped to trade with another merchant

The game proceeds in rounds, which are made of each player's turn. Every round, the turn order is changed (To be decided: poorest players first or randomly generated?)

In their turn, each player can do one of these things:

  • trade with the city, if they are in a city

  • trade with a merchant, if they have encountered a merchant on the road

  • resume travelling to the other city, if they have encountered a merchant

  • start travelling to another city

If, in the previous turn, the player started travelling to another city, at the start of this turn he'll either

  • be notified that they have encountered a merchant, and can decide whether to trade or keep walking

  • be notified that they have reached the other city, and receive the information about it (its name and its trade prices)

If the player encounters a merchant and decides to keep travelling instead of trading, they will reach the city they were travelling to and will still be able to act (= trade with the city or move again)

If, instead, the player trades with the merchant, their turn is considered over and will be able to move again on their next turn (note: since they will be midway between two cities, they will have the chance to decide which of the two to travel to, in case they want to change their previous "travel decision")

Taxation happens at the start of the player's turn, if it is the taxation round (= once every 7 rounds)

Note: the player can't "talk" to the other merchant unless they both stop to trade, so if the player decides to keep travelling they won't know the other merchant's prices. (I'm not sure about this rule, so please give me feedback :) would it be more sensible to know the other merchant's prices before having to decide whether to stop?)

Code

I haven't started coding the controller yet, but I was thinking about using Node.js (since javascript is my favourite language, and I don't have tools to use Java and would prefer to avoid having to install stuff) so that bots can be submitted in the form of node modules (either written in javascript or with a javascript wrapper like most low-level node modules)

Note that your bot will be able to save data into a .txt file.

Please give me feedback if you want to suggest a different approach. :)

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

Count Numbers in Integer Partition

Sandbox Remarks

I'm looking for a description to make the problem more clear.

Challenge and Example

We can partition a positive integer into smaller (or equal) ones. For instance, for N=6, it can be divided into:

  • 6 (1 integer occurs >= 1 times, 0 integer occurs >= 2 times)
  • 5+1 (2, 0)
  • 4+2 (2, 0)
  • 4+1+1 (2, 1)
  • 3+3 (1, 1)
  • 3+2+1 (3, 0)
  • 3+1+1+1 (2, 1)
  • 2+2+2 (1, 1)
  • 2+2+1+1 (2, 2)
  • 2+1+1+1+1 (2, 1)
  • 1+1+1+1+1+1 (1, 1)

Your task is to work out the sum of the count of integers in each case, which occurs greater or equal than M times. In the aforementioned case, if M=1, the result is 1+2+2+2+1+3+2+1+2+2+1=19, and if M=2, the result is 0+0+0+1+1+0+1+1+2+1+1=8.

Input

Two positive integers N, M.

N is the number being partitioned from.

M is the lower limit of occurrences.

Output

One integer, the sum of the count of unique integers in each partition.

Remarks

  • This is a code-golf so shortest code wins.
  • Standard loopholes are forbidden.

Example I/O

All padding spaces are for formatting on PPCG only. You don't need to take care of them.

8  2  => 19
10 1  => 97
25 4  => 1228
25 50 => 0
50 7  => 87004
50 50 => 1

All I/O for M,N<=50: here

\$\endgroup\$
  • \$\begingroup\$ To see whether I've understood this: you want ![\sum_{\lambda \vdash N} \sum_i [a_i \ge M]](i.stack.imgur.com/WEncL.png) where the outer sum is over all partitions of N, !\lambda = 1^{a_1} 2^{a_2} \ldots k^{a_k} in the frequency representation? \$\endgroup\$ – Peter Taylor Jun 7 '17 at 15:25
  • \$\begingroup\$ @PeterTaylor If I understand your equation correctly, in this problem, N should be a sum of smaller integers, instead of a product of smaller ones. \$\endgroup\$ – Keyu Gan Jun 7 '17 at 15:42
  • \$\begingroup\$ Yes, it's just that the frequency representation of partitions looks like a product because it's intended to be compact. I think that OEIS A066633 is the table of desired results, although its description isn't necessarily any clearer. \$\endgroup\$ – Peter Taylor Jun 7 '17 at 15:57
  • \$\begingroup\$ Should 5+1 not be (2,0)? \$\endgroup\$ – Shaggy Jun 7 '17 at 16:07
  • \$\begingroup\$ @Shaggy Sorry, yes. \$\endgroup\$ – Keyu Gan Jun 7 '17 at 17:52
  • \$\begingroup\$ @PeterTaylor Sorry for my not-so-good mathematic. Yes it is A066633. I just come up with the idea when learning Elder's Theorem. \$\endgroup\$ – Keyu Gan Jun 7 '17 at 17:57
1
\$\begingroup\$

Resolve paths

Convert a path to an absolute path. The path may be:

  • relative
  • absolute
  • contain ~

If the path doesn't exist, exit with code 1. An invalid path leads to undefined behavior. i.e. do whatever you want, I don't care

Test cases, assuming /foo/bar is the current working directory, and the username is ~/admin:

<empty string> -> /foo/bar
. -> /foo/bar
.. -> /foo
... -> / # and so on until `...`
~/ -> ~/admin
~/golf -> ~/admin/golf
/bin -> /bin
foobar -> /foo/bar/foobar
.htaccess -> /foo/bar/.htaccess
./buildscript -> /foo/bar/buildscript
doesnotexist -> <exit with error code 1>

Don't use an external command or builtin that solves or almost completely solves this challenge.

This is , so the shortest answer in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – AdmBorkBork Oct 24 '16 at 15:49
  • \$\begingroup\$ This is very confusing... why does ~/golf go to ~/admin/golf? That's not an absolute path is it? Shouldn't ~/golf go to /home/admin/golf? \$\endgroup\$ – Tim Jun 9 '17 at 12:39
1
\$\begingroup\$

I would like to ask this challenge:

The objective of this programming puzzle is to reproduce the following gif. enter image description here

However, I do not know the specs for the making of such an animation.

How can I make this a standard/allowed puzzle with this limitation?

Any inputs will be appreciated.

\$\endgroup\$
  • \$\begingroup\$ I'm afraid it's rather unlikely there is any way for this to become an acceptable challenge without you specifying the gif very precisely. You don't really need to know how to make an animation to do that, but you need to be able to accurately describe the shapes involved. You'd also probably need to describe framerate as a minimum, and probably a min/max speed of the dots. \$\endgroup\$ – FryAmTheEggman Jun 9 '17 at 14:37
  • \$\begingroup\$ Seems like a very interesting challenge, but needs quite a few things, including an objective winning criterion and an actual description of the required output. \$\endgroup\$ – MD XF Jun 9 '17 at 16:42
  • \$\begingroup\$ @FryAmTheEggman How would determine the speed of the dots? i.e., what unit should I use? What framerate would advise? \$\endgroup\$ – An old man in the sea. Jun 9 '17 at 17:39
  • \$\begingroup\$ @MDXF Would smallest answer be a good criterion? \$\endgroup\$ – An old man in the sea. Jun 9 '17 at 17:39
  • \$\begingroup\$ I'm afraid I'm not certain how to approach making the animation smooth by specifying these. However, I do think code-golf is a suitable winning criterion. \$\endgroup\$ – FryAmTheEggman Jun 9 '17 at 17:44
1
\$\begingroup\$

This message is open for anyone to adopt and post to main. For more details, see the chat room or meta post.

Count the holds

I love climbing but sometimes, I've been climbing so long that the colors of the holds get mixed up. Please help me!

Task

Given a filename of an image of a climbing wall with one of these extensions (.png / .jpg / .svg), output what quantity of what color holds there are.

Input

An image, either as a file or as a direct image (for languages such as Mathematica)

Output

The number of each color of each hold, in any acceptable format, such as a dictionary in Python:

{
    'red':10,
    'blue':5,
    'greeen':14
}

or a 2D array:

[
    ['red',10],
    ['blue',5],
    ['green',14]
]

or any form in which the colors and the quantities are clearly grouped. An array such as below would not be allowed as it isn't clear which color goes with which quantity:

['red','blue','green',10,5,14]

Rules

  • Standard loopholes are disallowed
  • The climbing wall to be counted will be the only one in the picture.
  • A climbing wall may have a top-rope set up (where the rope goes up and down the wall) or have lead-clips on the wall. Neither of these should be counted. However, some walls will simply be holds and won't have a rope or clips.
  • A wall will never be an overhang, but may be a single slant.
  • This is a . Your score is the number of correct outputs divided by the total number of inputs (standard rules)

Examples

Examples to come later

Meta

  • Tags?
  • Is this a dupe?
  • What other file formats should I allow?
  • Any questions?
\$\endgroup\$
  • \$\begingroup\$ "However, some walls will simply me holds, no rope or clip." what's me holds? \$\endgroup\$ – Rɪᴋᴇʀ May 15 '17 at 17:39
  • \$\begingroup\$ Also, I'd recommend making this a test-battery. (i.e. score is number of correct outputs / number of total inputs) \$\endgroup\$ – Rɪᴋᴇʀ May 15 '17 at 17:40
  • \$\begingroup\$ How else would you score it? It's not really plausible to specify any image should always give the right result. \$\endgroup\$ – Rɪᴋᴇʀ May 15 '17 at 18:28
  • \$\begingroup\$ @Riker changed! \$\endgroup\$ – caird coinheringaahing May 15 '17 at 18:48
1
\$\begingroup\$

Heapify a list

META:

As a few people just pointed out, if you sort the list, this also produces a correct heap. I'm now trying to come up with a more interesting application of heaps.

Given a list of integers, heapify this list and return it. The sumission must have a worst case time complexity in O(n).

Details

  • Your implementation can produce min- or max-heaps, whatever is more convenient.
  • Sorting the list would solve the problem, but since the worst case complexity must be in O(n) where n is the length of the list, known sorting algorithms like quicksort fail to meet this requirement.

Definition

A min-heap is a complete binary tree where the values stored in the children of a any node are greater or equal than the ones stored in the node itself. (In a max heap it is the same just with condition less or equal).

A heap can be easily represented using a list L (here using 1 based indexing) where the children of the node at L[k] are L[2*k] (the left child) and L[2*k+1] (the right child).

A list L (lets say one based indexing is used) is (min)-heapified if

 L[k] >= L[2*k] and L[k] >= L[2*k+1] for all k

For a max heap we just replace >= with <=.

Examples

Following image represents a max heap:

The corresponding list representation is

[100, 19, 36, 17, 3, 25, 1, 2, 7]

The following image represents a min heap:

The corresponding list representation is

[1, 2, 3, 17, 19, 36, 7, 25, 100]
\$\endgroup\$
  • \$\begingroup\$ CJam, 1 char using the "sort" builtin \$\endgroup\$ – Peter Taylor Apr 13 '17 at 11:05
  • \$\begingroup\$ @PeterTaylor Thanks, that totally defeats this challenge of course=) \$\endgroup\$ – flawr Apr 13 '17 at 11:54
  • \$\begingroup\$ I recommend giving a specific algorithm for heap construction, and then asking for the program to return the input list in the order that that algorithm would produce. (So you aren't quite forcing the use of the algorithm, but simply sorting won't work.) \$\endgroup\$ – user62131 Apr 13 '17 at 12:45
  • 2
    \$\begingroup\$ @ais523 As an alternative to explicitly rule out some results I think we could just restrict the worst case runtime to O(n), that way just sorting would not be possible anymore. \$\endgroup\$ – flawr Apr 13 '17 at 13:05
  • 1
    \$\begingroup\$ In which case you would add the restricted-complexity tag. \$\endgroup\$ – mbomb007 Apr 13 '17 at 15:35
1
\$\begingroup\$

Print all matching leaves

In Natural Language Processing, we sometimes interpret sentences as being context-free languages, and therefore as having a certain tree structure, also called constituency trees, or parse trees. These trees are sometimes written down in a notation that (as far as I know) stems from the Penn Treebank project:

A tree is either of:

  • (a b1 b2 b3...), with a being the tree's label (typically something like NP for "noun phrase") and bn being the same representation of it's sub-trees (all being non-terminals)

  • (a c), which a being the tree's label and c being the label of a single terminal child (a word).

Valid trees:

  • (S Hi) (Simple tree containing only one word, "Hi")
  • (A (B (C D))) (Nested tree containing only one word, "D")
  • (A (B C) (D (E F)) (G H)) (Tree containing the words "C", "F", and "H")

Invalid trees:

  • Hi (a terminal is not a tree)
  • (A B C) (terminals have no siblings)
  • ((A (B C))) (extra parantheses)
  • (A (B C))) (unbalanced parantheses)

For understanding this format better I recommend this online tool I wrote ages ago. For example, this is a visualization of the first example case:

Task:

Given a Penn-Treebank-style tree representation and a non-terminal, output the space-seperated concatenation of all leaves for every instance of this non-terminal.

Rules:

  • You may take the two inputs (tree representation and non-terminal symbol) in any of the standard ways, but always as strings. You may take them in any order.
  • The output can be a list of strings (["The dog", "a cat"]), some other kind of sequence, a (e.g.) comma-seperated string, and anything else that's reasonable
  • Both inputs are guaranteed to never be empty.
  • The tree representation input is guaranteed to contain at least one terminal symbol.
  • Single spaces may or may not exist for formatting (both the first and the second example are equally valid and both have to be accounted for), but there will always be a single space between a terminal symbol and its immediate parent (e.g. between Det and the in the first example)
  • In case you don't find any matching terminals, you may either raise an error, not output anything, or output some kind of empty sequence.
  • All node labels (terminal or not) will match /[A-Za-z0-9_-]+/.
  • Specify which output format you use
  • The shortest code (per language) wins

I/O examples

input 1                                                input 2  output
(S(NP(Det The)(N dog))(VP(V likes)(NP(Det a)(N(cat))))), NP -> "The dog", "a cat"
(NP (Det A) (AP (Adj fancy) (N car))),                   V  -> an empty sequence
(N cat),                                                 N  -> "cat"

Output format examples

  • List of strings: ["The dog", "a cat"]
  • CSV: "The dog, a cat"
  • CSV without spaces: "The dog,a cat"
\$\endgroup\$
  • \$\begingroup\$ I might be confused, but you state the input will be a non-terminal; is N not a terminal in the last example? Did you mean input would just be a label, non-terminal or otherwise? Would you mind qualify (nothing), and clarify the output rules: the first example is effectively a list of list, is that the expected output, or should it be a list of strings (space-delimited tokens)? \$\endgroup\$ – VisualMelon Jun 9 '17 at 9:50
  • 1
    \$\begingroup\$ @VisualMelon N is not a terminal, cat is. (nothing) is supposed to mean "no or empty output", but I should clarify that and the output rules: Either a list of strings (["The dog", "a cat"]) or a something-seperated string ("The dog, a cat"). (nothing) would mean empty string, empty list, ... \$\endgroup\$ – L3viathan Jun 9 '17 at 10:52
1
\$\begingroup\$

Print all video urls of YouTube channel

Inspired by Count the videos in a Youtube Playlist, the input will be the "VIDEOS" view from a channel like this one:

https://www.youtube.com/channel/UCzwJRQXMXkaB9KlqUdFD74Q/videos

The output will be a complete, newline-delimited list of all video urls the respective channel has to offer. It would look something like

https://www.youtube.com/watch?v=JxNfccUIQCU
https://www.youtube.com/watch?v=lOr0XIHFhlk
https://www.youtube.com/watch?v=o3tZElWLrbc

This is codegolf, so shortest answer wins.


Comments:

  • I am unsure whether the permitted use of Google's YouTube API might be a good idea. It requires an API_KEY and can only retrieve 50 results per request.

Thanks for the feedback.

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

Least Picky Language

For this challenge, you will create a programming language that is not picky at all. That is, for any program of any length consisting of any characters in the ASCII range [32..126] and any input consisting of any characters in the same range, your program must do something without any errors. The program only has to hypothetically work for any length; that is, StackOverflowException and the like are acceptable if the input or program is too long for your new language to handle (however, I require it to work for program size up to 1024 bytes and input up to 1024 bytes).

In your programming language, no character or combination of characters can be useless (to prevent everything from being a no-op). That means that every character in the program must affect the function somehow, even if the overall function does not change. No two characters can have the same specification either.

For example, it is not allowed to have - and N both compute the negative of a number.

Note that <space> is a valid character in the program and must do something even if it is leading or trailing. Also note that you do not have to handle tabs or newlines in the program or the input.

The most upvoted answer at the end of 2017 Calendar Year (UTC December 31 23:59:59) will be accepted, and I will award a +50 bounty to my personal favorite language.

Meta

  • Duplicate?
  • Clear enough validity criteria?
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm not sure what you expect from this... my first thought (since I only usually code-golf) is to just sum the ascii values of the input (i.e. define each char/token as adding the ascii value of the char). There is a very large space of programs that meet these criteria, and I think perhaps this is just too broad. \$\endgroup\$ – VisualMelon Jun 14 '17 at 17:19
  • \$\begingroup\$ @VisualMelon Yes, there are many valid submissions. It's a popularity-contest so the one people like most wins. The thing you described would be valid but I doubt people would like it. \$\endgroup\$ – user42649 Jun 14 '17 at 17:22
  • \$\begingroup\$ Rather, but I'm wondering what we might expect people to like... there is scope to do virtually anything here (you can even define something that is picky, and just define an output for when it fails). It feels like less of a challenge to achieve something given constraints, and more a challenge to find something amusing, and wrap it up with these constraints. \$\endgroup\$ – VisualMelon Jun 14 '17 at 17:43
  • 1
    \$\begingroup\$ @VisualMelon That is largely the challenge; popcons are hard to make nowadays so I expect this to be sandboxed for quite a while. Do you have any ideas for how I could improve the scope of valid submissions? I was thinking requiring Turing Completeness. \$\endgroup\$ – user42649 Jun 14 '17 at 17:46
  • \$\begingroup\$ Even if you enforce Turing completeness, someone can make a BF variant, and then define the remaining characters as 'add ascii value to output'. I'm afraid I don't really have any ideas to tighten it up, but I'll keep it in mind. \$\endgroup\$ – VisualMelon Jun 14 '17 at 18:10
  • \$\begingroup\$ @VisualMelon I'll ask in TNB but thanks for noticing the potential issues to be fixed. \$\endgroup\$ – user42649 Jun 14 '17 at 18:22
1
\$\begingroup\$

Lots of Pi(e)!

For Meta:

Any tags other than , and ?

Dupe?

Any errors?

Clear enough?

Your Task:

Because everyone likes more pi, we're going to give them 999 decimal digits of it. Your program should output pi truncated (not rounded off) at 999 decimal places. For reference, here it is:

3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378678316527120190914564856692346034861045432664821339360726024914127372458700660631558817488152092096282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179310511854807446237996274956735188575272489122793818301194912983367336244065664308602139494639522473719070217986094370277053921717629317675238467481846766940513200056812714526356082778577134275778960917363717872146844090122495343014654958537105079227968925892354201995611212902196086403441815981362977477130996051870721134999999837297804995105973173281609631859502445945534690830264252230825334468503526193118817101000313783875288658753320838142061717766914730359825349042875546873115956286388235378759375195778185778053217122680661300192787661119590921642019

Input:

None, your program may not take any input at all.

Output:

Pi truncated at 999 decimal digits.

Scoring:

This is , lowest byte count wins!

Good Luck!

\$\endgroup\$
  • \$\begingroup\$ Closest I could find was this, but this challenge doesn't have the slightly odd restrictions that one does. I don't think I would close it, but I would understand if someone disagreed. \$\endgroup\$ – FryAmTheEggman Jun 15 '17 at 0:18
  • \$\begingroup\$ Usually, we make it so that programs can assume the input is empty, not that we cannot take input. Some esolangs read all the input there is before starting execution. \$\endgroup\$ – Okx Jun 15 '17 at 10:20
  • \$\begingroup\$ yes but this you are not allowed any input \$\endgroup\$ – Foxy Jun 15 '17 at 10:22
1
\$\begingroup\$

Randomly capitalise half of a string

Given string s of even length as input, randomly capitalise exactly half of the letters.

  • You can assume the input will always be a positive, even length
  • You can assume the input will consist of only lowercase letters ([a-z])
  • There must be an equal probability of each letter being capitalised
  • Exactly half of the letters should be capitalised in the output.

Scoring

This is so fewest bytes in each language wins!

\$\endgroup\$
  • \$\begingroup\$ Will a string of length 0 ever be an input? \$\endgroup\$ – dzaima Jun 15 '17 at 12:26
  • \$\begingroup\$ @dzaima no, clarified by saying length will always be positive \$\endgroup\$ – Skidsdev Jun 15 '17 at 13:57
1
\$\begingroup\$

Sample the Sierpinski traingle

Inspired by this video..

Task

Your task is to implement the following method to sample a Sierpinski triangle and plot all the intermediate steps.

Method

Given three points a,b,c and some starting point x_0, for each iteration you sample one of the three points a,b,c with equal probability. You then place x_{i+1} in the middle of the edge between x_i and the sampled point. Repeating this draws the Sierpinski triangle.

Input

You'll receive the coordinates of the three starting positions through any default accepted input method. The exact format can be flexible: a matrix, a list per point [xa,ya],[xb,yb],[xc,yc], a list for x and y [xa,xb,xc],[ya,yb,yc], a flat list [xa,ya,xb,yb,xc,yc] are all allowed.

The starting point x_0 is [0,0]. You can assume [0,0] would fall within the overall shape.

Output

For each iteration, including the initial, draw a plot of all the points up to that point. There should at least be a 100ms delay between two plots. If your language does not support graphical displays, you can also write your images to a file.

Since the triangle is an infinite fractal, the program should loop forever (given infinite memory and all that jazz).

Criteria

Shortest code wins!

Example code (R)

Sierpinski <- function(p, q) {
  x11()
  par(mar = rep(0, 4))
  plot(p, q, col= "red", pch = 15, cex = 1, axes = FALSE)

  x <- 0
  y <- 0

  repeat {
    Sys.sleep(0.1)
    n <- sample(1:3, 1)
    x <- floor(x + (p[n] - x) / 2)
    y <- floor(y + (q[n] - y) / 2)
    points(x, y, pch = 15, cex = 0.5)
  }
}

enter image description here

Meta

  • Duplicate? There are a couple 'draw a sierpinski triangle' challenges, but I couldn't find any that use this method of drawing them.
  • Is the specification of the algorithm clear enough or should I add pseudocode?
  • Is the 100ms delay between iterations reasonable?
\$\endgroup\$
1
\$\begingroup\$

Cops & Robbers, the ultimate 1-up.

This is a cops and robbers game.

Cops

Hello, cops. you've just solved a Code Golf challenge on the stack exchange website. How wonderful. You go to post your answer, and soon after a robber comes and beats you by 1! How infuriating!

Your task:

Produce two programs.

The first program can be in any language, of any length, and cannot use default loopholes. it does one thing: Prints out a number.

The second program must use the same language as the first, must use less bytes than the first, and CAN use forbidden loopholes. The second program must print out a number which is equal to 1+ the output of your first program

post your first program and wait 7 days. If someone cracks your program within those seven days by robbing you, please edit your answer to include [cracked] in the header. If your program is not cracked, you can edit [safe] in the header.

Robbers

Hello, robbers. You're sneaky and looking for ways to win a golf, even if it's underhanded. You see that a cop has posted a golf for a decent score, and decide to take the lead from them.

Your task is to take a cop's answer, and beat it. Your program must use less bytes than the cop's answer and print out a number equal to only 1+ the cop's answer. You're program must also be in the same language as the cop's answer. You may use underhanded tricks and loopholes to solve the challenge. Once you complete this, you may post your solution and let the cop know they've been beat.

Example I Os

cop: 16
robber: 17
Correct: Yes!

cop: 16
robber: 16+1
Correct: Yes!

cop: 16
robber: 16.1
correct: NO! (alternative symbols for '+' are not allowed)

cop: 16
robber: 18-1
correct: Yes! (evals to 17)

cop: 16
robber: [234,32,54,17,45,23]
correct: NO! (output must be exact).

cop: 16
robber: "1+ the cop's answer" [OR] "a number equal to only 1+ the cop's answer"
correct: NO! (smartassery is not a loophole)

cop: 16.001
robber: 17
correct: NO! (16.001+1 <> 17)

EXCLUSIONS: you may use any underhanded trick / loophole you want, BUT your output must match the description exactly. no new line. no trailing space.

The following loopholes are still forbidden:

\$\endgroup\$
  • 3
    \$\begingroup\$ Open season on loopholes is a bad idea. E.g. for languages with short builtins for HTTP GET it becomes a search for the shortest URL shortener rather than a code golf. \$\endgroup\$ – Peter Taylor May 23 '17 at 7:33
  • \$\begingroup\$ @PeterTaylor howso? the robbers must use the same language as the cops, so if you don't want to have yours cracked, use a language that doesn't support GET requests (or atleast not simply). \$\endgroup\$ – tuskiomi May 23 '17 at 18:34
  • 3
    \$\begingroup\$ You need to explain cops-and-robbers rules here, in case people haven't seen them before. In particular, I'm assuming that the cop posts are required to be crackable, in which case you need to mention that the cop must keep the second program secret, but reveal it when marking the post as safe. \$\endgroup\$ – user62131 May 24 '17 at 2:39
  • \$\begingroup\$ The Your Task bit isn't clear, I think you mean the end result of a cracked submission will have two programs but it kinda reads like the cops have to write two programs. \$\endgroup\$ – Notts90 May 25 '17 at 9:18
  • 4
    \$\begingroup\$ "no new line. no trailing space." Why ban trailing newlines? \$\endgroup\$ – CalculatorFeline May 31 '17 at 15:09
  • \$\begingroup\$ As a robber, can output the string a number equal to only 1+ the cop's answer? \$\endgroup\$ – programmer5000 Jun 15 '17 at 15:37
  • \$\begingroup\$ @programmer5000 no, smartassery is not a loophole. \$\endgroup\$ – tuskiomi Jun 15 '17 at 15:38
  • 1
    \$\begingroup\$ @tuskiomi actually, it's the most voted of them all \$\endgroup\$ – programmer5000 Jun 15 '17 at 15:50
1
\$\begingroup\$

Beat the turing test

Both you and your bot have to connect to a speed dating chatroom (details below) where you will either be paired up with another bot, or with another human. You get 30 seconds to converse with your partner before you are disconnected, and are presented with the choise of wether you think the person you spoke with is a human or not.

This process will be repeated in a round robin fashion for a maximum of 10 minutes, or until everyone has spoken with everyone. You will not be paired with your own bot.

You will be given an equal number of votes for human/robot, as you will be facing an equal number of each. Both you and your bot will be given the option to change these after the conversations.


Scoring

Robots get 2 point for fooling a robot, and 5 points for fooling a human. Humans are not awarded any points for correct guesses, but lose 2 points if they are wrong.


Rules

  • Bots may the internet aswell as external datafiles
  • Gentleman's rule: Please do not pretend to be a robot. If every human said nothing but Beep beep, I am a robot it would ruin the challenge for everyone.


Meta

This will be a one-time event on a specific date. There will be a webapp for humans and an API for bots. Until the final date there will be a sandbox site online for testing purposes. I am still undecided on the specifics of the API, and on how long the timespan between posting the challenge and running it should be.

I can also run (some) bots locally, communicating on stdin/stdout

\$\endgroup\$
  • 2
    \$\begingroup\$ Can't a human just accuse everyone of being a robot, thus preventing points from being gained? \$\endgroup\$ – Neil A. Jun 22 '17 at 21:49
  • 1
    \$\begingroup\$ I suspect that participation in this will be very low (as it's a highly difficult task), which is a problem for a challenge that inherently has a deadline. Stack Exchange might not be the best place to run this. \$\endgroup\$ – user62131 Jun 23 '17 at 2:47
  • \$\begingroup\$ @NeilA. You are absolutely right. I think my new scoring system fixes that, but ultimately I rely on participants being honest to make this a fun challenge, which is why I think Stack Exchange is a good place to do this \$\endgroup\$ – BlackCap Jun 23 '17 at 18:04
  • 1
    \$\begingroup\$ 1. Timezones are an issue. 2. You need to clarify the sequence. Do I have to call bot/human immediately after the conversation, or do I have all the conversations first and then call? 3. I suspect that even the recently raised 60k character limit to answers could be a problem for writing a sophisticated bot. Can answers use additional data files stored somewhere public such as github? \$\endgroup\$ – Peter Taylor Jun 23 '17 at 21:26
  • \$\begingroup\$ @PeterTaylor I think allowing you to change votes at the end would make programming bots more fun because you can compare the conversations against each other to determine humaness. Nice point \$\endgroup\$ – BlackCap Jun 23 '17 at 21:55
1
\$\begingroup\$

Repetitive Primes

A repunit in any base B is a number consisting solely of 1s in that base.

Your task is to figure out if a repunit of length f N in base B is a prime number.

Rules

  • N >= 2
  • B >= 1
  • N and B may be taken in any order and in any reasonable method.
  • Output a consistent value to indicate primeness and a different consistent value to indicate compositeness.
  • Programs and functions are acceptable.
  • This is code golf, shortest code in bytes wins.
  • Standard loopholes apply

Test cases

B, N => Result

2, 7 => prime
1, 97 => prime
10, 19 => prime

9, 11 => composite
20, 10 => composite
7, 23 => composite

Meta questions

  • Dupe? Unclear? Too broad? etc.
  • Would this be a better question with a different winning criterion such as ?
  • Should I change the title?
  • Any other constructive criticisms?
\$\endgroup\$
  • \$\begingroup\$ I don't think fastest-code would be a good fit, code-golf should work just fine. You can also add base-conversion and decision-problem. I suggest appending "Primes" to the title. \$\endgroup\$ – Laikoni Jun 23 '17 at 13:20
  • \$\begingroup\$ 1. "repunit consisting of N in base B" feels to me as though it's missing 1s, although perhaps a better phrasing would be "repunit of length N in base B". 2. Although it's easy to show that N must be 1 (which is not valid input) or prime, the test cases should still include at least one where N is composite. \$\endgroup\$ – Peter Taylor Jun 23 '17 at 17:48
  • \$\begingroup\$ @Laikoni: I agree it might be an interesting code-golf question, but I also want to see people use cool optimizations such as the length must be prime, or base 9 doesn't have any repunit primes, etc. as opposed to everyone using a base conversion followed by slow trial division. \$\endgroup\$ – Neil A. Jun 23 '17 at 22:40
  • \$\begingroup\$ Slow trial division? Golfing languages will use the isPrime builtin, which probably uses BPSW or Miller-Rabin with carefully selected bases. \$\endgroup\$ – Peter Taylor Jun 24 '17 at 22:52
  • \$\begingroup\$ This is actually relatively simple to solve. You just need to check whether ((N + 1) % B) == 0 \$\endgroup\$ – Okx Jun 26 '17 at 16:16
1
\$\begingroup\$

Monopoly KoTH

This is going to take me a while to finish and may never be fully done. Don't expect this to be posted anytime soon. However, this will be an ongoing project under development.


Who hasn't heard of Monopoly? If not, don't worry, as I will explain the rules! If you already know the rules, read on, for they may be different in this rendition.

The Rules of Monopoly

Monopoly is played on a board, with 36 different squares, that looks somewhat like this

monopoly board

For this version, we'll use the original British version, because I'm British and proud of it!

Squares are split into 3 categories:

  • Property. These are the ones with a coloured bar at the top, such as Old Kent Road or Whitehall. They also include the 4 stations in the middle of each side, and the utilities (Electric Company and Water Works)
  • Bonus Cards. These are the squares marked Community Chest or Chance. These allow for a player to either receive or lose money, depending on a random card choice.
  • Special Squares. These are the 6 other squares in the board, the 4 corner squares and the taxes (boo!)

Let's look at these categories in a bit more detail.

Property

Properties are grouped, depending on the colour of said property. Each property has a rent value that contains the amount that a player must pay to the owner of the property, when they land on that property. If one player owns all of the properties in one colour, the rent for each is doubled.

Players can also buy properties, which is how they own them. Each property also has a price, which is then deducted from the buyer's cash and given to the Bank, in exchange for the property. Stations cost £100 each and all other properties available to buy have their cost written below their square.

Stations' rent increases the more stations that someone owns. In the following progression

  • 1 Station: Rent = £25
  • 2 Stations: Rent = £50
  • 3 Stations: Rent = £100
  • 4 Stations: Rent = £200

Utilities' rent depends on the dice roll. If a player owns 1 utility, multiply the roll by 4 and that is the rent. If the player owns both, multiply the roll by 10 to get the rent due.

Properties can be built on. That means that a player builds houses and hotels on them, in order to increase that properties rent. A player can build houses and hotels on a property if

  • it has a coloured bar at the top
  • the player owns all of the properties in the group
  • they have enough money. Each house costs £50 and each hotel costs £100.

Each property can have a maximum of 4 houses. After that, the player must build a hotel. A property can only have 1 hotel on it. Houses and hotels drastically increase the rent of a property, for example £4 (no buildings) to £450 (one hotel).

Bonus Cards

The name of these are a bit of a misnomer. These are denoted on the board by ? symbols and chests on squares and can either give or take money from you. For this game, we will ignore Get Out of Jail Free cards and the Goto cards. The cards can result in a random integer between -1000 and 1000 added to your score. If this results in bankruptcy (we'll see this later), so be it.

Special Squares

  • Go. If you land on Go, you get given a £400 reward. If you simply go past it (Mayfair -> Old Kent Road), you get £200. It's also where the pieces begin.
  • Jail. If you roll and land on this square, don't worry, as you don't go to jail. You are "Just Visiting"
  • Free Parking. This is where the taxes go! If you have to pay taxes, either because of the Tax squares or because of a Bonus Card, that money goes to Free Parking. If a player lands on it, they get all the money there!1
  • Go to Jail. This does what it says on the tin. You go straight to Jail. But this time, you're in Jail, not just visiting. You stay in Jail until you roll a double.1 After which, game continues as normal. You cannot collect rent while in Jail.
  • Taxes. Super Tax and Income Tax are two squares which charge you £100 and £200, respectively. However, you can regain that money as it goes straight to Free Parking!

Bankruptcy

In Monopoly, if you run out of money, you are bankrupt. Here, you have two options. You can either mortgage your properties or, if you don't have any, you are out of the game! The last one with any money wins the game and the KoTH!

When you lose, all your properties go to the player who bankrupted you. If that's the Bank by virtue of Bonus Cards, then all your properties are available to be bought again.

Mortgage

You can mortgage properties in order to get more money if you're in a pinch. Unfortunately, this "deactivates" the property, meaning that you don't get any rent when people land on it. If you have enough money, you can unmortgage a property for 110% of its mortgage value. (£100 -> £110)

Auctions

If you land on an unbought property and don't buy it, either because you don't have enough or you just don't want to, the property goes on auction. This means that all players can bid on the property. Bidding starts at £1, which means that a player can, theoretically, get the property for a much lower or higher price than its original price.

Trading

I am hoping to be able to include trading but this does depend on my ability as a coder. In an ideal world, I will be able to get it working but, unfortunately, this may not happen :(

1: I am aware that this changes depending on who you're playing with, but this is how we'll do it in this version.

Rules of the KoTH

I have written (still finishing) a Player class in Python which contains all of the things that a Monopoly player can do. Your task is to rewrite 2 of the functions that can change your player's behaviour.

While thinking about how to make this KoTH, I listed out the complete process that gives you a chance to change what you do. Let's go over that process! This flowchart shows the process for each turn. Green items show the choices that you have to make.

This is the text version:

1. Roll dice and move
2. Is the property owned by the Bank?
    1. Yes. Nothing happens.
    2. No. Pay the due rent.
3. Choice of:
    1. Buy
    2. Auction
4. Choice of:
    1. Trade
    2. Build
    3. Mortgage
    4. Unmortgage
    5. Move On
5. Repeat until bankrupt

Auction

1. Choice of:
    1. Play the auction
    2. Don't play the auction
2. Are you playing the auction?
    1. Yes.
        1. Choice of:
            1. Bid new max
            2. Skip one round
            3. Skip all rounds
            4. 'All in'
        2. Repeat until 1 player left bidding
    2. No. Don't do anything.

Trade

1. Choose a player to trade with
2. Offer properties and/or money
3. Does the other player agree with the trade options?
    1. No. They counter offer. Do you like their options?
        1. No. Do you want to continue negotiating?
             1. Yes. Go to point 2 above
             2. No. The trade is over.
        2. Yes. You trade the agreed upon items.
    2. Yes. You trade the agreed upon items

But, for you coders out there, I'll explain using a bit of code.

Your submission should contain a single class that inherits from Player. You may add in as many extra attributes as you want, but in order to be used, your code must refer to them. I'm not editing the controller just for your bot to work.

However, each class must look like this

class NameOfPlayer(Player):
    def turn(self, square, roll):
        (code that determines your actions per turn)
    def auction_action(self, price, bidders):
        (code that determines your auction actions)
    def trade_actions(self, players, last_offer):
        (code that determines your trading actions)

    (any other functions you want)

Your turn function will return 3 numbers as a list e.g. [1,2,3] which are the results of the choices above. The first item should be either 1 or 2 (Buy or Auction), the second should be one of 1,2,3, 4 or 5 (of the 4. Choice of: options) and the third should be either 1 (play the auction) or 0 (don't play the auction) such as [1,5,0] would buy the property, move on to the next player and not play the auction on this turn (doesn't matter as there wasn't an auction).

Your auction_action function will return either a number (your bid) or one of a (all in), s (skip this round) or q (quit auction), which determines what you will do on that round of the bidding. This continues until either you quit the auction of you are the only one left.

Your trade_actions function will return a list every time it is called. The list consists of [agree with previous offer (as a bool), properties to trade (as a list), cash to trade (as an int)]. When a trade has just begun, the first item in the list will be ignored and the last_offer parameter will be ignored. The last_offer parameter contains the second 2 items returned by the person you are negotiating with, so that you can decide whether you want to continue trading or not.

If you lose all your money, your program with be taken out of the active players and placed into the results table. The last one standing wins!

\$\endgroup\$
  • \$\begingroup\$ I call dibs on the Go submission that always go to jail. \$\endgroup\$ – Uriel Jun 25 '17 at 16:35
  • \$\begingroup\$ While you are allowed to use the monopoly rules, I'm not sure about using the picture of the board? \$\endgroup\$ – Destructible Lemon Jun 26 '17 at 4:44
  • \$\begingroup\$ @DestructibleLemon what do you mean? \$\endgroup\$ – caird coinheringaahing Jun 26 '17 at 5:59
  • \$\begingroup\$ If I'm reading this correctly, this is a variant which doesn't allow trading properties, and that's the most interesting part of the game. The rules stated also fail to state what happens to the properties of a player who goes bankrupt. (Correct answer: they must mortgage all of them and then forfeit them to the player to whom they owe rent. I'm not sure offhand what happens if they're going bankrupt due to taxes, but presumably the properties revert to the bank and when someone lands on them they buy or auction). \$\endgroup\$ – Peter Taylor Jun 26 '17 at 9:23
  • \$\begingroup\$ @PeterTaylor I'm currently writing the controller and a base class, which will determine what I can and can't allow in the game. Once that's finished and all issues with the controller are sorted out, I will update the rules here to fit with it's capabilities. Also, the version I've played allows for a player to mortgage their properties to avoid bankruptcy (as in you mortgage and if you're still bankrupt, you lose) \$\endgroup\$ – caird coinheringaahing Jun 26 '17 at 13:54
  • 1
    \$\begingroup\$ My point is that unless it's a two-player game, you lose is not a sufficient description because the game needs to continue until there's only one winner. The comment about mortgaging is because if I owe you more money than I can get by mortgaging all my properties, I have to mortgage them and give you the money obtained and the mortgaged properties, and so you have to pay to unmortgage them before you can benefit from them. \$\endgroup\$ – Peter Taylor Jun 26 '17 at 14:05
  • \$\begingroup\$ What stops this from going into an infinite loop without a winner \$\endgroup\$ – pppery Jul 27 '17 at 16:12
1
\$\begingroup\$

Mutation-hardening quine

Your task is to make a program that prints out its own output.

"Hey, we already have this challenge, and tons of variations of it! Why are you making another one?" you may ask, but this one is going to be one of the most difficult ones.

Your quine must be "mutation-hardened", which means the quine still must work, even after any one of its characters is duplicated in place.

For example, if you have a program:

abcd

These programs must all output abcd:

aabcd
abbcd
abccd
abcdd

(In each of those programs, a, b, c and d are each duplicated in-place, which means the duplicated character was placed directly after the original character.)

Rules:

  • Standard quine rules apply.

This is , so shortest code in bytes wins!

Meta:

  • Is this challenge too hard?
  • What other rules should I put up?
\$\endgroup\$
  • 2
    \$\begingroup\$ Is this even possible? \$\endgroup\$ – Shelvacu Jul 1 '17 at 22:57
  • \$\begingroup\$ For hard problems, try to find at least one solution. \$\endgroup\$ – NieDzejkob Jul 2 '17 at 17:50
  • 1
    \$\begingroup\$ @Shelvacu It doesn't have to be \$\endgroup\$ – caird coinheringaahing Jul 14 '17 at 17:21
1
\$\begingroup\$

Make a Quiz Parser

Your task is to create a program that will take an input of multiple 4-choice questions (A, B, C, D) in the format shown below, display each question (format also shown below) and its 4 answer choices, get the user's answer to each question, and, at the end of the quiz, output their score as a percentage.


The Format

Questions in input

Q<space><Insert question here>:<Insert letter of correct answer here>
<indent 1 space>A<space><answer choice text>
<indent 1 space>B<space><answer choice text>
<indent 1 space>C<space><answer choice text>
<indent 1 space>D<space><answer choice text>
<you can add a newline between questions if it makes things easier>

How to output questions

<question number>. <question>
  A. <answer choice A>
  B. <answer choice B>
  C. <answer choice C>
  D. <answer choice D>
<2 spaces before each answer letter>

How to output scores

Your score is: <score here>%

Test Case

Q What is the average airspeed velocity of an unladen swallow?:B
 A African or European?
 B 22 mph
 C I don't know that!
 D What?

If this were question number 42, it would output like this:

42. What is the average airspeed velocity of an unladen swallow?
  A. African or European?
  B. 22 mph
  C. I don't know that!
  D. What?

As usual, standard loopholes are strictly forbidden.


This is , so may the shortest code win and the best programmer prosper...

\$\endgroup\$
  • \$\begingroup\$ I like this challenge, but I think it could use a complete test case \$\endgroup\$ – musicman523 Jul 5 '17 at 18:41
  • \$\begingroup\$ @musicman523 Ok. I will use an output from fotoforensics for example. \$\endgroup\$ – ckjbgames Jul 5 '17 at 18:53
1
\$\begingroup\$

Let's simplify polynomials

In many situations we have to expand mathematical expressions containing variables, for example, calculating characteristic polynomials, expanding products of polynomials, etc. It is trivial if the variables are known (in this case, we just substitute the variables with the corresponding values and evaluate the expression by a calculator), but not so simple if we need to manually expand the expression.

Motivation

Consider the cases with only one variable (say, x). Suppose the coefficients are sufficiently small. Then, a simple way is to take x to be some number (e.g. 1000), evaluate the expression and convert the numerical answer back to a polynomial.

Here is an example. Suppose we need to expand

Put and evaluate it using a dumb calculator. The answer is .

By running the program/function with input -984982000, one should get

[-1, 15, 18, 0] (descending order)

, and so the expanded polynomial is .

The task

Write a program or function which satisfies the following:

  • The input is an integer, which is calculated by substituting x = 1000 in a polynomial (which you have to find out).
  • Output the coefficients, guaranteed to be in the range [-499,499] (inclusive), and to be integers. You can represent the polynomial in either ascending or descending order, so long as it is consistent across different runs. You can return a list of integers, print to standard output (with non-numeric separators), etc.

Examples

Input         Output (descending power)
1003005007    1 3 5 7
1001          1 1
999           1 -1
998994        1 -1 -6
-998994       -1 1 6
1000001       1 0 1
0             0


Input
1003005007

Valid outputs                     Invalid outputs
[1 3 5 7] (descending order)      1357 (coefficients are not separated)
[7 5 3 1] (ascending order)       7531 (coefficients are not separated)
"1 3 5 7" (descending order)      "1357" (coefficients are not separated)
"7, 5, 3, 1" (ascending order)    [1 5 3 7] (neither ascending nor descending order)
7                                 "10305070" (numeric separator "0")
5
3
1 (ascending order)

Rules

  1. Standard loophole applies.
  2. Your program/function should be able to at least handle polynomials of degree 3. Also, the input might be negative. Therefore, using a suitable data type is necessary.
  3. You can take the input in integer or string format. It is guaranteed that the input is a valid integer.
  4. The shortest program/function (in bytes) wins. Good luck!
\$\endgroup\$
  • \$\begingroup\$ I think this input-output pair violates the order-criterion: 1000001 1 0 1 \$\endgroup\$ – flawr Jul 11 '17 at 9:09
  • \$\begingroup\$ What do you mean with "consistent across different runs"? Why don't you restrict this challenge to just have ascending coefficients? (Also please include wheter e.g. 1 3 5 7 means x^3 + 3x^2+5x+7 or 1+3x+5x^2+7x^3. \$\endgroup\$ – flawr Jul 11 '17 at 9:12
  • \$\begingroup\$ @flawr To avoid confusion, a program or function should not output in different orders when different inputs are given (e.g. 1003005007 -> [1 3 5 7] and 999 -> [-1 1]). So 1 3 5 7 can mean both, but it has to be specified. To solve the problem one way is to find out and remove the leading/trailing coefficient recursively, and it probably costs extra bytes to reverse the list of coefficients. \$\endgroup\$ – tonychow0929 Jul 11 '17 at 9:15
  • \$\begingroup\$ Ah so the order has nothing to do with the challenge but just with the input/output? (I first thought we have to find polynomiasl where the coefficients are in are in ascending order.) Perhpas clarify that this is not about the coefficients but about the representation of the polynomials. And as I said before please specify that in your examples the constant monomial comes first, and the coefficients of the larger powers come after. \$\endgroup\$ – flawr Jul 11 '17 at 9:51
  • \$\begingroup\$ I don't understand what the question has to do with the title. \$\endgroup\$ – Peter Taylor Jul 11 '17 at 10:07
  • \$\begingroup\$ @PeterTaylor see my edit \$\endgroup\$ – tonychow0929 Jul 11 '17 at 10:33
1
\$\begingroup\$

For technical reasons, many languages have a boundary for number values, which calls for workarounds when operating with numbers outside this range.

Challenge

The challenge is to write a program which is able to multiply two arbitrary large numbers, given an infinite amount of time and memory.

The input will always be two positive decimal integers in any reasonable format (string, list of digits..)

The output should be (exclusively, apart from any whitespace) the exact decimal product of these integers.

  • If integer magnitude is unbounded in your language, you must set an own limit
  • The algorithm has to be written individually. If your language has arbitrary multiplication implemented in any way, (built-in, native support) the program has to be written in a way that assumes that these methods are limited to some number
  • Note that properties like .length can exceed the integer limit. You can't e.g. ordinarily loop over the digits in a 'for' loop
  • A valid solution can not be confirmed by solely test cases but only by analysis of the code

  • This is , so shortest code in bytes per language wins.

Example Input and Output

Input:

5378877047254281056308179853217614491205392080414948189690882584626258197090299384248418705254284062330999044417502407170242320748022675887850236280535223588025381434803683717318134517400400886554441

and

24585803251446564673599904286559945882543472174090101020256415987852946031712809185990398899511551226915139170857973433130460342507187447589801052724967977799120438910759846107262285707877865565231049

Output:

13224401279751560029079048725841743388456506005068978434329060038933262717486337348174589758627669812502604130373896959848172091197634331942663385472131265201616801014468642971825909208942693284219016467181922385520740594984640977937358293657922369959902120240111214073507556243844128492765568914803850594686913014876111459929738682018339519061223975139325785119259348090888269287247476161682038609

Sandbox

Is this different enough from this challenge?

Would this be better suited for ?

\$\endgroup\$
  • \$\begingroup\$ The solutions to this will be very interesting. Looking forward to it. \$\endgroup\$ – Gryphon Jul 10 '17 at 0:01
  • \$\begingroup\$ I don't quite understand your first bullet point... is it disallowing using the * operator in languages with unbounded ints? Would it disallow java's BigInteger::multiply? (Java is perhaps a special case, as int and BigInteger are separated. Furthermore, BigInteger is not a "native" implementation). If you want to disallow builtin solutions, say so... but as it stands I think that java.math.BigInteger::multiply would be a perfectly valid solution... no? \$\endgroup\$ – Socratic Phoenix Jul 10 '17 at 16:18
  • \$\begingroup\$ @socraticPhoenix Good point, I've edited the post. Is it clearer now? \$\endgroup\$ – Oki Jul 10 '17 at 18:21
  • \$\begingroup\$ "Note that properties like .length are also bounded numbers, and the input can have infinitely many digits". What I'm getting is that no-one should bother attempting to answer, because properties like pointers to memory are also finite and so no program will be able to read the input. \$\endgroup\$ – Peter Taylor Jul 11 '17 at 7:35
  • \$\begingroup\$ Note also that long multiplication has been done \$\endgroup\$ – Peter Taylor Jul 11 '17 at 11:47
  • \$\begingroup\$ @peter You're right. I made an edit, does it make sense now? Basically it should implement multiplication to the highest magnitude possible for each language. Since memory isn't limited, pointers can always be incremented until input end. \$\endgroup\$ – Oki Jul 11 '17 at 13:39
  • \$\begingroup\$ No, it doesn't make sense now, and I don't think there's any way of writing it which would make sense. Either you have loops which don't bother with an index (i.e. most golfing languages), in which case limitations on length are both nonsensical and irrelevant; or you need to index into the data structure, in which case your index is subject to the same limitations as length and it's completely impossible. I also think that "reasonable format" directly contradicts limits on length. \$\endgroup\$ – Peter Taylor Jul 11 '17 at 14:04
  • \$\begingroup\$ @peter The limitation is not imposed by me. If the program can multiply integers whose length (number of digits) is larger than the INT_MAX (or whatever limit is set), it goes. \$\endgroup\$ – Oki Jul 11 '17 at 15:36
1
\$\begingroup\$

Minimize my cube

Introduction

Using my 6x6 as cubes of smaller size

I have a rubiks cube. It has 6 layers and is great fun to solve. But it takes quite some time, and sometimes I wish I could just solve a cube of smaller size. But theres hope, because every cube with even number of layers can emulate every cube with less layers by only moving certain layers at the same time. Now I need your help to provide the numbers.

Let's get mathematical

Consider this definiton: For every even integer n and a positive integer i <= n there exists a sequence of i positive integers, so that

x_1 + x_2 + ... + x_i = n
x_1 = x_i
x_2 = x_(i-1)
x_3 = x_(i-2)
...

(See test cases for a clearer example). Then such a sequence tells me exactly which layers to combine.

The challenge

For an input n write a program that outputs one of the existing sequences for every positive integer i < n.

Test cases

For n = 6:

[6]
[3, 3]
[2, 2, 2]
[1, 2, 2, 1]
[1, 1, 2, 1, 1]
[1, 1, 1, 1, 1, 1]

For n = 4:

[4]
[2, 2]
[1, 2, 1]
[1, 1, 1, 1]

Scoring and Rules

Lowest number of bytes wins. Standard Loopholes apply.

Sandbox quesions

  • Formatting?
  • Can I make the definition clearer?
  • Should I put more restrictions?
  • Where is my english broken beyond repair?
\$\endgroup\$
  • \$\begingroup\$ Tell me if I'm understanding it wrong, but could we output, for the fourth line when n=6 : [2, 1, 1, 2]? or even [2, 1, 2, 1]? or even any permutation of [1, 1, 2, 2]? \$\endgroup\$ – V. Courtois Jul 19 '17 at 16:39
  • \$\begingroup\$ Another thing (that's why separate comment) : you don't explicitly require an input format. So here, could I for example output a string containing : 4\n22\n121\n1111\n (with \n=newline)? Am I allowed to have this trailing newline? Are the commas mandatory? etc. \$\endgroup\$ – V. Courtois Jul 19 '17 at 16:42
  • \$\begingroup\$ About my first comment : if you want, you can even ask for outputting every or any permutation, or a symmetric permutation, or an increasing-ordered one. \$\endgroup\$ – V. Courtois Jul 19 '17 at 16:46
  • \$\begingroup\$ @V.Courtois: I meant it to be symmetric, like [2,1,1,2] and [1, 2, 2, 1] are both symmetric, but [2, 1, 2, 1] is not. Alas, need to better the explanation, I guess. \$\endgroup\$ – Seims Jul 20 '17 at 5:49
  • \$\begingroup\$ you do need, it's a fact :) And what about saying what output format you want (sorry for the input mistake in 2nd comment) ? \$\endgroup\$ – V. Courtois Jul 20 '17 at 6:40
1
\$\begingroup\$

Fighting a Land War

In this KoTH, you need to earn as much money as you can while fighting over tiles to take over.

The board is a large hexagon made up of 91 smaller hexagonal tiles (A 6x6 hexagon)

Each tile is either:

  1. An impassable mountain
  2. Hills that generate production. They start out with a random value (between 2 to 4)
  3. Valleys that generate money. Their starting value is the distance from the nearest corner multiplied by 2 (between 2 and 10)

Board

There are 6 players in each game, each starting in a different corner of the hexagon. The corner will always be a hill(4). Turn order is randomized at the start of the game.

Each turn, the following happens:

  1. Each tile that you have owned for N^2 turns (where N is an integer) increases in value by 1
  2. You earn money/production. (Equal to the sum of the valley/hill values)
  3. You can spend production on defenses or capturing tiles.
    • Adding N TileDefense costs N Production
    • Capturing a tile with N TileDefense costs 1 + 2*N Production
    • You can only capture a tile if it is a non-mountain tile that is adjacent to your current tiles.

Notes:

  • Tiles lose all defense on capture.
  • Multiple players can upgrade a single tile
    • The turn counter for tile upgrades is player-specific. This means that if you capture a tile from another player, the turn counter starts at 0.
    • If you capture a tile you've owned before, it starts off where you left it.

And that's it. The player with the most money after 500? turns wins.

\$\endgroup\$
  • \$\begingroup\$ 1. "Each tile is either" determined how? Randomly or in a fixed pattern? 2. How does step 3 work? As many rounds of capture and defence as you like? Or do you declare all of your attacks and defences at the start of the round? This has implications both for defending a tile on the turn you capture it and for blitzkrieg captures. \$\endgroup\$ – Peter Taylor Jul 16 '17 at 6:56
  • \$\begingroup\$ 1. I'm still thinking about this. I think I'm going to randomly generate a triangular segment, and then mirror it across to the other 5 segments. 2. Oooh...I haven't thought about this. Thanks, I'll give it some thought. \$\endgroup\$ – Nathan Merrill Jul 16 '17 at 12:06
1
\$\begingroup\$

KOTH: Thirty-One

Challenge

Built a bot that plays Thirty-One against other bots!

Game Rules

Thirty-one is a card game using the standard 52-card deck (the French deck). The objective in each round is to have a hand better than at least one of your opponents'.

At the beginning of the game, each player has a set number of "lives" - for this challenge, each player will get 3 lives. Once you run out of lives, you have lost the game. No matter how many players there are, there is exactly one winner per game.

The player to go first in the first round is chosen arbitrarily. After that, the player to go first rotates clockwise around the "table". The players' order does not change between rounds (except for when players get knocked out).

At the beginning of each round, each player is dealt 3 cards. On each player's turn, they have the option to:

  1. Draw a card from the deck and discard a card
  2. Draw the last card that was discarded and discard a card
  3. Knock if no other player has knocked yet

Knocking

If a player knocks, each other player gets one more turn. Then, the players compare hands. Whoever has the lowest score loses a life, and the round ends.

Scoring

Each player's score is calculated by adding the face values of all their same-suit cards and taking the best score. Two cards of different suits don't contribute to the same score.

The face values for each card are:

Ace: 11
King, Queen, Jack: 10
2-10: their value

For example, consider you hold the cards:

Ace of Spades
Four of Spades
Two of Spades

Your score would be 11 + 4 + 2 = 17.

If you hold the cards:

Queen of Diamonds
Four of Clubs
Nine of Clubs

Your possible scores are 10 and 4 + 9 = 13, so your score is 13, the best of the two.

Finally, if you have:

Six of Hearts
Six of Spades
Three of Diamonds

Your possible scores are 6, 6, and 3, so your score is 6, the best of the three.

The highest possible score you can reach is 31, by holding the Ace and two 10-point cards of the same suit.

Special Cases

  • If the player who would go first knocks immediately on their first turn, the other players don't get a turn - they compare hands right away

  • If a player reaches a score of 31, they should knock immediately and everyone else loses a life

  • If the deck runs out of cards, the round ends and all players compare hands

Input/Output

Your bot will be a subclass of the base class I provide. You need not implement every method, but there will be a minimal amount of functionality required in order to make the turns go forward.

Scoring

I will create a tournament-style bracket that will determine the winning bot. Your bot is allowed keep track of all the information available to it, including between games. The details of the bracket will depend on the number of bots written.


Meta

  • I could use some input on writing the controller and base class. What has worked well in the past? What hasn't worked that I should avoid?

  • Are the rules for the game clear enough? I adapted them from my own knowledge of the game and this website.

  • Obviously this isn't ready for posting yet since I haven't written the base class, but is there anything else unclear or missing?

  • Is there anything I can do to make this more fun or more challenging?

\$\endgroup\$
  • \$\begingroup\$ 1. The key thing for the controller is to maintain a persistent connection, because if you have to keep forking processes that becomes a bottleneck. 2. There are a couple of minor points to clarify. "Whoever has the lowest score loses a life": presumably in case of ties everyone with the lowest score loses one. "standard 52-card deck": the French deck, to distinguish it from other standards. Although on the basis of KISS I'd use a deck of four suits and card values 0 to 9 (with three 8s per suit). \$\endgroup\$ – Peter Taylor Jul 18 '17 at 13:51
  • \$\begingroup\$ "Draw a card from the deck and discard a card" is presumably followed by shuffling all but the discarded card if the draw deck runs out. "I will run 100 games using everyone's bots" will break badly if there are 17 bots. \$\endgroup\$ – Peter Taylor Jul 18 '17 at 13:52
  • \$\begingroup\$ @PeterTaylor Thank you so much for the feedback! 1. Thank you for the advice, I didn't plan on making the program multi-processed, I planned on having the controller simply keep a list of the bots and passing control to each one in turn. 2. Yes the tying rule is correct, I'll add that in. Although that would be a good way to simplify the deck I think I'll keep it 2-11 with four 10s per suit, because I don't want to change the name of the game. 3. Yes, all but the top card would be shuffled back in, I'll add that as well. 4. Why would that break badly? Just because of computation time? \$\endgroup\$ – musicman523 Jul 18 '17 at 14:05
  • \$\begingroup\$ 3 cards each times 17 players leaves 1 card in the deck. \$\endgroup\$ – Peter Taylor Jul 18 '17 at 14:09
  • \$\begingroup\$ Ah, good point...if there are that many participants, I'll have to break it into multiple smaller games and set up a tournament bracket \$\endgroup\$ – musicman523 Jul 18 '17 at 14:17
  • \$\begingroup\$ I've changed my mind on one thing - the round ends when the deck runs out of cards. Each game will consist of 4 players, and I'll release more information about the gameplay once I see how many bots are written \$\endgroup\$ – musicman523 Jul 18 '17 at 17:46
1
\$\begingroup\$

Title: Visualizing Euclid's Algorithm

Problem

We wish to visualize Euclid's algorithm for computing the greatest common divisor of two numbers as a 2-dimensional tiling, such as this one:

euclid

This interactive version may also be helpful in understanding the visualization.

Input

Two positive integers a and b, where a > b. You may take them in any order and in any convenient form: a list, two function args, etc.

Output

An ascii version of the above visualization shown above. This is best illustrated with a few examples:

input = 20, 8

.....................
.       .       .   .
.       .       .   .
.       .       .   .
.       .       .....
.       .       .   .
.       .       .   .
.       .       .   .
.....................

8 goes into 20 2 times, so we have two 8x8 squares, and remainder of 4 (20 - 8*2 = 4). 4 goes into 8 2 times with no remainder, so the remaining rectangle is broken into to 2 4x4 squares and we're done.

input = 5, 3

......
.  ...
.  . .
......

Note: There is an implied connection between any two adjacent dots, so that the above ascii should be interpreted as follows:

connected nodes

input = 7, 3

........
.  .  ..
.  .  ..
........

flexibility

You may choose whichever border characters are prettiest to you, or use combinations of different characters.

.....................   *********************   +-------+-------+---+
.       .       .   .   *       *       *   *   |       |       |   |
.       .       .   .   *       *       *   *   |       |       |   |
.       .       .   .   *       *       *   *   |       |       |   |
.       .       .....   *       *       *****   |       |       +---+
.       .       .   .   *       *       *   *   |       |       |   |
.       .       .   .   *       *       *   *   |       |       |   |
.       .       .   .   *       *       *   *   |       |       |   |
.....................   *********************   +-------+-------+---+

Rotations are also allowed: Any of the above may be rotated 90, -90, or 180 degrees.

Rules

This is , standard loophole rules, etc.

\$\endgroup\$
  • \$\begingroup\$ Nice challenge! But I would add a test cases like 8,5 and 21,13 where the recursion goes a bit deeper. \$\endgroup\$ – ბიმო Jul 26 '17 at 8:16
  • \$\begingroup\$ @BruceForte thanks. unfortunately since posting it I found this, which I fear is too similar: codegolf.stackexchange.com/questions/119714/… \$\endgroup\$ – Jonah Jul 26 '17 at 17:06
  • \$\begingroup\$ Yeah you're right, didn't know these existed. \$\endgroup\$ – ბიმო Jul 26 '17 at 17:11
1
\$\begingroup\$

NB: work in progress

Convert MADBACE to DECIMAL

MADBACE is a mixed Roman-hexdecimal system. Hexadecimal digits (0-F) take their normal positional values, while Roman numerals (IVXLCDM) have their normal values (1 5 10 50 100 500 1000). The main parts of the challenge is to determine when to subtract and when C and D are Roman versus hexadecimal.

Rules

  1. C and D will be Roman if possible.

  2. There can never be more than one subtractive symbol to the left of any symbol.

  3. A subtractive symbol must be less than half the symbol it subtracts from

Examples

CM900

MC1100

MD1500

DM792 1000-13×161

LD450

CD400

XD40

ID49 13×160-1

3C52 100-3×161

4C76 4×161+12×160

MADBACE701590 (10×165-1000)+(11×163-500)+10×162+100+14×160

DECIMAL233571513 13×166+14×165+12×164+(1000-1)+10×161+50

\$\endgroup\$
  • \$\begingroup\$ Maybe make explicit mention that a smaller symbol to the left of a larger symbol is always subtracted if both are Roman. And if one is Roman? What if neither are? Actually if neither are then the position based value ensures the symbol to the left is always larger. \$\endgroup\$ – trichoplax Jul 25 '17 at 23:01
  • \$\begingroup\$ If only a single symbol can be to the left for subtraction, how are ambiguous cases like IXL resolved? \$\endgroup\$ – trichoplax Jul 25 '17 at 23:02
  • \$\begingroup\$ Are all possible inputs from the symbol alphabet to be dealt with, or just some subset? I mean, does the spec resolve all ambiguities or will the challenge specify "only valid inputs will be used"? \$\endgroup\$ – trichoplax Jul 25 '17 at 23:03
1
\$\begingroup\$

Calculate the maximum possible number of "living" cells on a given grid size for Conway's Game Of Life.

Conway's Game Of Life

Game Rules:

  1. Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overpopulation.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

Challenge: For a given grid size (ex 5x5) is it possible to calculate the maximum potential living cells after at least 5 generations with any given starting pattern?

 O O X O O
 O O X O O
 X X X X X
 O O X O O
 O O X O O

In the above example, there are 16 living cells. I am not proposing that this is the maximum, just providing a starting point.

The reason for the 5th generation requirement is because the first generation could technically be 25 (100%) I suppose.

\$\endgroup\$
  • 3
    \$\begingroup\$ To me, this is a very interesting challenge because brute-forcing it would be difficult (5x5 board has 2^25=32 million possibilities for starting). That being said, this should be marked as code-golf or fastest-code as a winning criterion (read the code-challenge description). Also, the rules should specify that all eight surrounding cell are included in the count. Is the board toroidal (i.e. edge wrapping) or flat? Are there any limits on the grid size? Importantly, this needs test cases to be a good challenge. If a 5x5 example is too big, do a 3x3 example. \$\endgroup\$ – fireflame241 Jul 26 '17 at 18:37
1
\$\begingroup\$

Can you compete with a supercomputer?

The challenge is to write super fast code for computing the permanent of a matrix of complex numbers.

In a paper from 2016 a team of coders managed to compute the permanent of a 40 by 40 complex matrix on 8192 nodes of what was at the time the world's fastest computer in about 14 seconds. Your challenge is to see how close you can get to this on my desktop.

The permanent of an n-by-n matrix A = (ai,j) is defined as

enter image description here

Here S_n represents the set of all permutations of [1, n].

As an example (from the wiki):

enter image description here

In this question matrices are all square.

Examples (these need updating to have complex entries)

Input:

[[ 1 -1 -1  1]
 [-1 -1 -1  1]
 [-1  1 -1  1]
 [ 1 -1 -1  1]]

Permanent:

-4

Input:

[[-1 -1 -1 -1]
 [-1  1 -1 -1]
 [ 1 -1 -1 -1]
 [ 1 -1  1 -1]]

Permanent:

0

Input:

[[ 1 -1  1 -1 -1 -1 -1 -1]
 [-1 -1  1  1 -1  1  1 -1]
 [ 1 -1 -1 -1 -1  1  1  1]
 [-1 -1 -1  1 -1  1  1  1]
 [ 1 -1 -1  1  1  1  1 -1]
 [-1  1 -1  1 -1  1  1 -1]
 [ 1 -1  1 -1  1 -1  1 -1]
 [-1 -1  1 -1  1  1  1  1]]

Permanent:

192

Input:

[[1, -1, 1, -1, -1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1],
 [1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, 1, 1, -1],
 [-1, -1, 1, 1, 1, -1, -1, -1, -1, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1, -1],
 [-1, -1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, 1, -1],
 [-1, 1, 1, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1, 1, -1, 1, 1, 1, 1, 1],
 [1, -1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, -1, -1],
 [1, -1, -1, 1, -1, -1, -1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1],
 [1, -1, -1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1],
 [1, -1, -1, -1, -1, -1, 1, 1, 1, -1, -1, -1, -1, -1, 1, 1, -1, 1, 1, -1],
 [-1, -1, 1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1],
 [-1, -1, -1, -1, -1, -1, -1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1],
 [1, 1, -1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1],
 [-1, 1, 1, -1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 1, -1, 1],
 [1, 1, -1, -1, -1, 1, -1, 1, -1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, 1],
 [1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1],
 [1, -1, -1, 1, -1, -1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, -1, -1, -1],
 [-1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1],
 [1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1],
 [1, 1, 1, -1, -1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, -1, -1, -1, -1, 1],
 [-1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1]]

Permanent:

1021509632

Add the 40 by 40 matrix here

The task

You should write code that, given an n by n complex matrix, outputs its permanent.

To make testing simpler, I will provide a single 40 by 40 complex matrix which you can hardcode into your code in any format of your choosing. Clearly, you are not allowed to precompute the answer however!

Scores and ties

I will test your code on the sample 40 by 40 complex matrix. Your score is your time in seconds divided by 14.

If two people are within 1 second of each other then the winner is the one posted first.

Languages and libraries

You can use any available language and libraries you like but no pre-existing function to compute the permanent. I will run your code under OS X so please give full instructions for how to compile and run it.

Reference implementations

There is already a codegolf question question with lots of code in different languages for computing the permanent for small matrices. There was also a related challenge on computing the permanent of matrices with only +-1 entries. The coding issues when you have complex entries and want things to run fast and multi-core are quite different however.

My Machine

The timings will be run on my Mac desktop. The CPU is Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz.

\$\endgroup\$
  • 1
    \$\begingroup\$ Remember #asdfjkl; and ##asdfjkl;, not **asdfjkl;**, for headings. \$\endgroup\$ – wizzwizz4 Jul 28 '17 at 19:07
  • \$\begingroup\$ Why divide the score by 14? I know it ties in with the story, but surely it primarily adds to confusion. Also, will all the input matrices only contain +/-1? \$\endgroup\$ – FryAmTheEggman Jul 28 '17 at 19:34
  • \$\begingroup\$ @FryAmTheEggman No the matrices will have complex entries. I need to change the examples. Dividing by 14 was just for fun to compare with the supercomputer. I can remove that if you think it's better. \$\endgroup\$ – user9206 Jul 28 '17 at 19:35

You must log in to answer this question.

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