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

2564 Answers 2564

4
\$\begingroup\$

Musical Washing Machine

I have a washing machine with a knob and several buttons. The knob selects the type of laundry and the buttons cycle through water temperature, etc. options. When pressed, these each create a musical note. There are five musical notes that can be made, in this ascending order: F A C D E

knob (K)
   When 360ed: play D and reset all other buttons
wash temp (T)
   1st press (cool -> warm): A
   2nd press (warm -> hot): F
   3rd press (hot -> cold): E
   4th press (cold -> cool): C
   (repeat)
spin speed (S)
   1st press (medium -> max extract): F
   2nd press (max extract -> no spin): E
   3rd press (no spin -> medium): A
   (repeat)
soil level (L)
   1st press (medium -> heavy): A
   2nd press (heavy -> extra heavy): F
   3rd press (extra heavy -> light): E
   4th press (light -> medium): C
   (repeat)

The Challenge

Given a series of notes, determine if if can be played on my washing machine, and, if so, output the series of moves to generate it.

I/O coming soon to a washing machine near you

\$\endgroup\$
  • \$\begingroup\$ As a side note, there is a washing machine that plays the New Zealand Athem \$\endgroup\$ – MickyT Aug 27 '15 at 21:02
  • \$\begingroup\$ I think I understand, but it looks a bit confusing. Maybe you should give an example with an explanation. \$\endgroup\$ – Beefster Feb 9 '18 at 17:18
4
\$\begingroup\$

Make a Sierpinski triangle

Your challenge is to output a n-th order right-angle Sierpinski triangle, similar to this (third-order):

#
# #
#   #
# # # #
#       #
# #     # #
#   #   #   #
# # # # # # # #

Input:

A number, n, and a character (in this example '#');

Output:

A 2**n (two to the n) line Sierpinski triangle, made of the given character. You could consider it a two-state cellular automaton: the cells are separated by a single spaaace; if it is on, it contains the given character; Otherwise is contains a spaaace.

Examples:

in:

0 *

out:

*

explanation:

2**0=1

in:

1 *

out:

*
* *

in:

2 *

out:

*
* *
*   *
* * * *

Winner:

this is codegolf so the winner is the answer with the least bytes. (NOTE: might add something tho do with triangles of the same character.)

Hint:

it might be helpful to know that the n-th line contains the previous line xor that line shifted right by one cell (x^(x>>1)).

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG and thanks for using the sandbox! There is a challenge to draw an Sierpinski Triangle which is broad enough to allow your format, so the challenge might be considered a duplicate. Then again I think the old challenge is no longer up to the current site standards and should probably be closed ... \$\endgroup\$ – Laikoni Mar 10 '18 at 10:08
  • 1
    \$\begingroup\$ This is also close enough to Generate Pascal's triangle that by the standards of this site (can answers be copied with trivial modifications?) I would consider it a duplicate. \$\endgroup\$ – Peter Taylor Mar 10 '18 at 19:42
4
\$\begingroup\$

King of the Hill: Avalon

Avalon is a semi-team-based strategy card game played with 5 - 10 players. The objective is simple but the gameplay is not as simple. The good people want to complete 3 quests while keeping Merlin alive, and the evil people want to fail 3 quests or assassinate Merlin.

Gameplay

Each player has a role, some of which have special abilities. All players need to contribute and use logic for that alignment to win. There are up to 5 day cycles which look like the following:

  1. The leader is the player to the right of the last leader. If this is the start of the game, choose a random player to start.
  2. The leader will select a specified number of players to form a Quest Team.
  3. Discussion Period will open. Everyone can post up to 50 messages to global chat.
  4. Everyone (including the leader) will vote Yes or No. If there is a majority, the Team will attempt the Quest (step 4). Otherwise, the Team is disbanded and another attempt is made (step 1).
  5. Discussion Period will open. Everyone can post up to 20 messages to global chat.
  6. Each player will perform the Quest Task (no actual task is required). Good people automatically perform the task. Evil people will be given the option whether or not to perform the task.
  7. If enough players perform the Task (all players for small quests, or at least #players-1 for larger quests in the end game), then the Quest is completed (progress for good). Otherwise, the Quest is failed (progress for evil).
  8. Final Discussion will happen. Everyone can post up to 10 messages to global chat.

If all players have been the leader in a single day cycle, the original leader will be given the choice of who the Quest Team is and there will be no vote; it will automatically pass.

If 3 quests pass, a 50-message Discussion Period will open for all players to discuss the Assassin's plans.

Roles

Good

  • Merlin - Merlin knows Good and Evil apart. At the beginning of the game, Merlin will be given a list of evil people.
  • Percival - Percival is the Protecter of Merlin. At the beginning of the game, Percival will be given the roster number of Merlin. However, if Merlin's shadow Morgana is present, Percival will be given two roster numbers, one of which is Merlin and the other which is Morgana (in no particular order or distinction)
  • Loyal Servant - The Loyal Servant has no special abilities but is good-aligned.

Evil

  • Assassin - The Assassin can lead evil to triumph even if 3 quests are completed. At the end of the game, if 3 quests are completed, the Assassin can choose a player to assassinate. If they are Merlin, evil is truimphant; otherwise, evil fails.
  • Morgana - Morgana is Merlin's shadow. Her ability is merely to confuse Percival, because Morgana also knows who evil is, just like Merlin.
  • Mordred - Mordred is the Leader of the Evil. Mordred doesnot reveal himself to Merlin.
  • Minion - The Minion has no special abilities but is evil-aligned.

At the beginning of the game, all evil people are given a list of all other evil people. This list does not tell evil who the Assassin is.

Controller and Bot Details

Bots may be written in any language as long as it can be run from the command line. Each bot must be a single file and take input from STDIN and output to STDOUT. In order to speed things up, your submission must be able to idle; that is, it will be started up and then given lines of input as the game progresses. If this inhibits too many people's ability to make a bot, I may change this rule.

At the start of the game, all of the bots will be started up. They should wait for input before doing anything. They will all be run in parallel and if any of them freeze, take too long to respond, or crash, they will be removed from the competition, so please make sure your bot runs correctly :P.

The first input will be given as a space-separated list of non-negative integers. The first integer represents the bot's role; 1 is Loyal Servant, 2 is Merlin, 3 is Percival, 4 is Minion, 5 is Assassin, 6 is Morgana, and 7 is Mordred. The second integer represents the number of players, n. The following n integers represent the roles that are in the game, in no particular order. The remaining integers represent a list of relevant characters; for Percival, this is a list of length 1 or 2 representing who Merlin is or who Merlin and Morgana are, and for Merlin and all evil roles, it is a list of all other evil players (except for Mordred in the case of Merlin). This input will be fed in followed by a newline ("\n") and the game will start immediately without waiting.

The following messages are valid for input with their meanings written beside (# represents any non-negative integer and #... represents a list of non-negative integers of any size). All messages are given as a space-separated list of non-negative integers (there will only be a single space between integers in the program input; the formatting below is just to make it look nice in the post).

0  # #... - Day # has begun and the day cycle begins. The players in this game are #...
1  #      - You are selected as the leader; please form a Quest Team of # people.
2  #      - Same as above, but there will be no vote for your final decision.
3  # #... - # selected the team #... has been selected. Discussion Period will start.
4  # #... - # posted the message #... in chat during pre-vote Discussion Period.
5  #      - Discussion Period is currently happening (pre-vote). You have # messages remaining. Please post a message.
6  # #... - # selected the team #... has been selected. Please vote.
7  # # #  - The final vote is # to # for yes. The Quest Team was # { 0 - disbanded ; 1 - accepted }. Discussion Period will start.
8  #...   - The quest team is #...
9  # #... - # posted the message #... in chat during pre-quest Discussion Period.
10 #      - Discussion Period is currently happening (pre-quest). You have # messages remaining. Please post a message.
11        - You are in the quest team and you are evil. Please choose whether or not to perform the Quest Task.
12 # # #  - # passes and # fails; the quest # { 0 - failed ; 1 - succeeded }.
13 # #    - Currently # quests have succeeded and # quests have failed. Discussion Period will start.
14 # #... - # posted the message #... in chat during final Discussion Period.
15 #      - Discussion Period is currently happening (final). You have # messages remaining. Please post a message.
16        - 3 quests have passed. Merlin must be killed for evil to win. Who do you choose to assassinate?
17 # #    - #-th game over; # won. Please reset the state of your bot. Please go back to the first step.

Each of the non-obvious inputs are explained below along with valid responses.

1

This one means that you are the current leader and you must choose # people for a Quest Team. If you are good, you should try to choose either all good people or choose evil people and hope to reveal them. If you are evil, you should try to choose at least one evil person so that the quest fails, but try not to choose one evil person along with all confirmed good people because then that will either cause the quest to pass or cause the evil person to be revealed.

One line of space-separated non-negative integers will be taken from the program. If the number of players chosen is wrong, the formatting is incorrect, or there are integers greater than the number of players, your program will be disqualified.

2

This one means that you are the current leader again and you must choose # people for a Quest Team, but this time your decision is final. The output format is the same.

6

This one means that a Quest Team is being proposed and you must vote. One line of output will be taken; if it is 0 exactly, then the vote is no. If it is 1 exactly, then the vote is yes. Otherwise, the bot is disqualified.

7

This one means that the vote has concluded with # people agreeing to the team and # people disagreeing with the team. The third argument is 0 if the vote failed or 1 if the vote passed (you can probably ignore this since greater-than and less-than comparison is trivial in almost all languages).

10

This one means that you were selected on a Quest Team that was approved, but you are an evil player. One line of output will be taken; if it is 0 exactly, then the action is not performed. If it is 1 exactly, then the action is performed. Otherwise, the bot is disqualified.

11

THis one means that the quest has finished with # people performing the task and # people not. The third argument is 0 if the quest failed and 1 if the quest succeeded (most of the time you can just check to see if the second argument is 0, but in late-game that doesn't always work for larger game sizes). No output will be taken.

14

This one means that 3 quests have succeeded and it is time for the Assassin to try to assassinate Merlin (this message is only given to the Assassin). One non-negative integer will be taken representing who to assassinate. If you try to assassinate any evil role who you know is evil (including yourself), you are disqualified for gamethrowing.

15

This one means that the #-th game has finished with # { 0 - evil ; 1 - good }. At this point, your bot should "restart". If your bot learns from past games, your bot can keep information around such as who won and different bots' strategies. You can't read other bots' files but you can try to remember how different bots play by preserving state between games.

Chat Message Format

Each message consists of up to 2 parts. The first part is optionally to state your role (this does not have to be truthful). The second part is to state something about either general observations or something about another player in particular.

First Part

The first part is a single integer representing which role you wish to claim. 1 is Loyal Servant, 2 is Merlin, 3 is Percival, 4 is Minion, 5 is Assassin, 6 is Morgana, and 7 is Mordred. Use 0 if you don't want to claim your role.

Second Part

The second part is a bit more complicated. Since there are three Discussion Periods that are used for different purposes, some of the messages are unique to certain discussion periods. All messages can be posted at any time, but if you post a message in a Discussion Period where it doesn't make sense to post it, other bots might think you're insane :P.

0       - I don't want to send a message.
1  #    - My decision on the Quest Team is # (only applicable for PRE-VOTE)
2  #    - I think # is evil
3  #    - I think # is good
4  #    - I trust # / I think # is telling the truth
5  #    - I don't trust # / I think # is lying
6  #    - I agree with #
7  #    - I disagree with #
8  #... - I think #... are working together
9  # #  - I think # has role # (see above for numbering of roles)
10 #    - I think the quest will # { 0 - fail ; 1 - pass } (only applicable for PRE-QUEST)

For example, if I wanted to say "I'm Percival and I think 3 and 7 are working together", I would send "3 8 3 7" as my message. If I just wanted to say "I don't trust 2", I'd send "0 5 2".

If you send anything that doesn't match one of the valid formats, it will skip your message for that turn.

Role Lists

The game looks slightly different depending on the number of players:

5  - Loyal, Loyal, Merlin, Minion, Assassin
6  - Loyal, Loyal, Loyal, Merlin, Minion, Assassin
7  - Loyal, Loyal, Percival, Merlin, Minion, Minion, Assassin
8  - Loyal, Loyal, Loyal, Percival, Merlin, Minion, Morgana, Assassin
9  - Loyal, Loyal, Loyal, Percival, Merlin, Minion, Mordred, Morgana, Assassin
10 - Loyal, Loyal, Loyal, Loyal, Percival, Merlin, Minion, Mordred, Morgana, Assassin

The game always has a good-majority with as little of a difference between faction sizes as possible. If there are 7 or more players, the second last quest requires 2 fails in order to fail.

Quest Team Sizes

5 - 2, 3, 2, 3, 3
6 - 2, 3, 4, 3, 4
7 - 2, 3, 3, 4, 4
8+- 3, 4, 4, 5, 5

Controller

Controller TIO link

Scoring

The game size will be max(players, 10). All combinations of players to roles will be run ten times. The player with the most total wins will win, tiebreak by whichever bot was submitted first. Scoring will not start until there are 5 players.

Rules

  • The game will only run once there are 5 submissions
  • You can name your bot anything because the name is not used in-game
  • Your bot does not have to be deterministic (because if they all were, then running the games ten times each would be pointless)
  • You may not read from or write to any external files, including other bots' files. If I remove the restriction about bots needing to run idly for the entire game, I will allow bots to write to an external file to store state.
  • You must use software that I can access for free on Fedora 27. Unfortunately, if the software is not available or not free, I will not be able to score your submission.
  • I reserve the right to disqualify any solutions that I believe to be malicious, including but not limited to taking excessive amounts of time or memory or otherwise attempting to harm my system. Also my computer is not very strong in terms of computing power so please make sure your bot doesn't require a supercomputer to run :P

motivation for this challenge and some of the wording and rules were taken from the Let's Play Mafia! king-of-the-hill challenge

\$\endgroup\$
4
\$\begingroup\$

-(-(--x)--))> Code Kebabs! <-(-(--x)--))


Your goal is to parse Code Kebabs, they look like this:

-x--> 8
2 <-(-(--x)--))
-x-x-x--> -10
--x> 255

A Code Kebab is made up of 3 parts, the stick, the tip (< and >), and the stand (the number compared by)

stick tip stand 
--x-- >   -5

The stick


The stick contains 4 operators, and the variable (x) The operators are listed here, in order of precedence:

  1. ( ... ) | Brackets. They are the "veggies" on a code kebab. Everything inside them runs before the rest of the kebab, with the last, deepest pair going first. Brackets can be nested.

  2. v-- | Suffix decrementation. This is one of the 4 parts of the stick, and decrements the value supplied to it by one.

  3. v-v | Subtraction. This is the 2nd part of the stick, and subtracts the two values.

  4. --x | Prefix decrementation. This is the 3rd part of the stick, and decrements the value supplied to it by one.

  5. -v | Negation. This is the 4th and final part of the stick, and inverts the value supplied.

Each operator returns it's result, and can be used as input for other operators.

The Tip


The tip is one of two symbols: < or > When the tip is <, the stand must be left of it, with the tip being left of the stick. When it is >, the stand is to it's right, with the tip being on the right of the stick.

The Stand


The stand is any integer. That's all there really is to say about it.

Execution of the kebab


You can't execute a kebab without eating it!

Kebabs are executed in a loop until their condition (The result of the stick being less than the stand's value) is fulfilled. When execution is finished, the variable (x) is set to the result of the stick, X is printed, and execution resumes again unless the condition is fulfilled.

When execution starts for the first time, X is set to 10 beforehand.

TODO


  • Add test cases.

  • Clear a few things up.

  • Make the description of execution a bit clearer?

\$\endgroup\$
  • 1
    \$\begingroup\$ You should describe the difference between pre and post decrement. \$\endgroup\$ – Pavel Apr 30 '18 at 21:22
  • \$\begingroup\$ Also, how are the input variables initialized? \$\endgroup\$ – Pavel Apr 30 '18 at 21:22
  • \$\begingroup\$ A test case that has something like -x--5 to force parsing it as a subtraction and unary negation, rather than post-decrement x, would be very good. \$\endgroup\$ – AdmBorkBork May 1 '18 at 13:02
  • \$\begingroup\$ @AdmBorkBork Numbers aren't mentioned as a requirement for parsing, so -x--x would probably work better. But yea, good idea. \$\endgroup\$ – moonheart08 May 1 '18 at 13:48
  • \$\begingroup\$ @Pavel The input variable X is set to 10 beforehand, as mentioned in The execution of the kebab \$\endgroup\$ – moonheart08 May 1 '18 at 13:51
  • \$\begingroup\$ Is this correct? And if not, where is my flaw? The input is the Code Kebab (i.e. -x--> 8) with x=10 by default, and the output is the x once it fulfills the Kebab check. So for -x--> 8 with x=10 as start, it will do x-- first (so it becomes x=9), and then the -x negation (so it becomes x=-9), and then checks it with the tip (-9 > 8). This is false, so it continues with x now being -9? So then x-- again (x=-10), then -x again (x=10), and then the check again (10 > 8). Which is true, so it outputs 10 as result? I have the feeling I misunderstand it a bit.. \$\endgroup\$ – Kevin Cruijssen May 2 '18 at 11:08
  • \$\begingroup\$ Also, why is suffix decrementation before prefix? In most languages (Java, JS, C, etc.) it's usually the other way around. \$\endgroup\$ – Kevin Cruijssen May 2 '18 at 11:10
  • \$\begingroup\$ And one more question, is something like ---x (negation & prefix decrementation), or x---x (suffix decrementation & subtraction) a possible valid input? Or would these always be surrounded by parenthesis (---x would be -(--x) instead; x---x would be (x--)-x or x-(--x) instead). \$\endgroup\$ – Kevin Cruijssen May 2 '18 at 11:14
4
\$\begingroup\$

Nearest neighbors in a square lattice

Premise

Consider an infinite 2D square lattice. We can choose one point as the origin and label each point with a pair of integers that corresponds to points on the Euclidean plane:

enter image description here

Now consider the point at the origin, \$(0,0)\$. The set of lattice points closes to the origin (but not including the origin) is \$\{(1,0),(0,1),(-1,0),(0,-1)\}\$. We will call this set the \$1\$st nearest neighbors. The set of lattice points closest to the origin but not including the \$1\$st nearest neighbors is \$\{(1,1),(-1,1),(-1,-1),(1,-1)\}\$. We call this set the \$2\$nd nearest neighbors

Now we can define the \$k\$-th nearest neighbors as the set of points closest to the origin and not included in the union of the set of \$n\$-th nearest neighbors for \$n\in\{1,2,...k-1\}\$.

Define the sequence \$NN(k)\$ as the length of the set of \$k\$-th nearest neighbors.

Task

Given \$k\$, compute \$NN(k)\$. This is A105352 on OEIS without the first element.

Rules

  • You may use 0- or 1- based indexing.
  • Given \$k\$, you may either output the first \$k\$ elements of the sequence or the \$k\$-th element.
  • You may alternatively take no input and output the sequence indefinitely.
  • Standard loopholes disallowed.

Here are some 1-indexed test cases:

n   NN(k)
1   4
8   8
9   4
10  8
38  16
52  8
80  8
121 24
145 12
\$\endgroup\$
  • \$\begingroup\$ OEIS A105352. \$\endgroup\$ – Mr. Xcoder Sep 13 '18 at 20:47
  • \$\begingroup\$ @Mr.Xcoder Thanks \$\endgroup\$ – dylnan Sep 13 '18 at 20:58
  • \$\begingroup\$ Could you allow the infinite sequence \$\{NN(1),NN(2),NN(3),\ldots\}\$ as output (with no input)? \$\endgroup\$ – Delfad0r Sep 15 '18 at 8:34
  • \$\begingroup\$ @Delfad0r Sure. \$\endgroup\$ – dylnan Sep 15 '18 at 16:33
  • 1
    \$\begingroup\$ Very related. Just filter out zeroes. \$\endgroup\$ – user202729 Sep 15 '18 at 16:38
  • \$\begingroup\$ @user202729 Do you think it's a dupe? \$\endgroup\$ – dylnan Sep 15 '18 at 17:06
  • \$\begingroup\$ @dylnan I don't know... \$\endgroup\$ – user202729 Sep 17 '18 at 13:08
  • \$\begingroup\$ IMO it's a dupe: adding a loop and an if test is a pretty trivial modification. \$\endgroup\$ – Peter Taylor Sep 17 '18 at 14:34
4
\$\begingroup\$

Breaking into 3 Palindromes:

As discussed here and here, every positive integer can be written as the sum of 3 palindrome integers. Given a number "n", output these integers.

Challenge

  • This is a code golf challenge. The shortest functional solution wins.
  • The input number "n" will be any integer greater than 0 but less than 1,000,000,000.
  • The three output numbers must be palindromes. Their sum must be "n".
  • A palindrome number is a number which is the same forwards as backwards. It can have any number of digits.
  • To make this easier, I will allow positive or negative palindrome integers.
  • Output and input can be formatted in any what that is convenient as long as it can be readily understood.

Examples

input: 5
output: 0,0,5

input: 1234
output: 1001,222,11

input: 3141592
output: 2200022,926629,14941
\$\endgroup\$
  • 2
    \$\begingroup\$ This is actually a very interesting problem. The paper which proved that this would work for any base lists 40 different algorithms that are used to find these values depending on the value of "n". I suppose there should be a requirement to solve this in a reasonable about of time to avoid brute force but I don't know how I should phrase that. \$\endgroup\$ – kaine Sep 17 '18 at 21:18
  • \$\begingroup\$ It's up to you, but time limit requires a particular computer to test the solutions on. \$\endgroup\$ – user202729 Sep 18 '18 at 1:18
  • \$\begingroup\$ Maybe it would be a good idea to link that paper in the challenge. Also, I tried to bruteforce in 05AB1E, and the 1234 case already times out after 60 sec, so I won't even have to try 3141592.. It barely doesn't make it within the 60 sec, but does output most of the possible outputs. Maybe make this a [fastest-code] challenge instead of code-golf, so the goal is to solve it as fast as possible. Alternatively [fastest-algorithm] could be used as well, but usually when someone find one, others will copy it. \$\endgroup\$ – Kevin Cruijssen Sep 18 '18 at 6:41
  • 1
    \$\begingroup\$ Honestly, i don't think i am comfortable managing a fastest-algorithm challenge due to my own limited skill. I'm a pretty amateur programmer so if someone uses languages, libraries, etc. I'm unfamiliar with I won't be able to fairly judge them. This idea though (complicated but sounds simple) seems great for one of these challenges. \$\endgroup\$ – kaine Sep 18 '18 at 13:04
  • 1
    \$\begingroup\$ Would it be feasible to require the code to run within 20 minutes on Ideone? Is that linked to my computer's abilities? \$\endgroup\$ – kaine Sep 20 '18 at 13:39
  • \$\begingroup\$ I think if you keep this at base 10 (decimal only) it's not so bad. \$\endgroup\$ – ouflak Sep 21 '18 at 12:59
  • \$\begingroup\$ @ouflak I had no intention of leaving base 10. I'm really liking the Ideone idea but am not sure if people would be ok with that. \$\endgroup\$ – kaine Sep 21 '18 at 18:51
  • 1
    \$\begingroup\$ rnta.eu/cgi-bin/three_palindromes/pal3.py and somethingorotherwhatever.com/sum-of-3-palindromes The speeds for these are bad at all. One in python the other in Javascript. I'm doing a C++ version (completely ungolfed) as I'm at a bit of a lull at the moment. It's just a translation of the Javascript code with some tweaks. I'll post a link to that as well. I would forget the timings and go with the straight up challenge. \$\endgroup\$ – ouflak Sep 26 '18 at 9:22
  • 1
    \$\begingroup\$ I've done this up in non-golfed C++. Anybody know a site where I can put this online where people can run it? It's big, but fast. \$\endgroup\$ – ouflak Oct 3 '18 at 15:24
  • 1
    \$\begingroup\$ The non-golfed C++ is 36 kbytes. Maybe limiting this to just the 4 digit case might be OK. I might try that in LUA and see what it looks like. This is such a great idea. Unfortunate that the algorithms are so lengthy. \$\endgroup\$ – ouflak Oct 8 '18 at 13:56
  • \$\begingroup\$ @ouflak, the fact that the algorithms are lengthy is why I thought this would make a good challenge. It is ripe for optimization. I'm worried about posting this challenge though as I'm sure there are many algorithms that will give an answer eventually but are so slow they defeat the purpose of the challenge. \$\endgroup\$ – kaine Oct 8 '18 at 14:29
  • \$\begingroup\$ Ok, I've sorted out a much shorter algorithm in LUA for the three digit case, un-golfed. repl.it/repls/AchingEnchantedHack. This has given me an idea for how to sort out the general case, which I think now actually might not be so bad. \$\endgroup\$ – ouflak Oct 9 '18 at 7:43
  • \$\begingroup\$ Here is a solution that should work for any sized number. This is brutally un-golfed LUA. I haven't even taken the opportunity to use a recursive function where it obviously would apply. For 5 digit numbers and smaller, it's pretty quick, easily less than a second. For 6 digit numbers and above, it depends on how soon it finds the first set of palindromes. I had one number (390081) take a good five minutes on the test site. I'm sure it would be quicker on my machine. I'd like to think there are places for optimization for speed (as well as golfing). repl.it/repls/BlondWaryShareware \$\endgroup\$ – ouflak Oct 9 '18 at 11:59
  • \$\begingroup\$ Just one other comment on your constraints, I wouldn't allow negative palindromes as I'm not convinced this makes it 'easier'. Should I start golfing this thing? ;) \$\endgroup\$ – ouflak Oct 9 '18 at 12:10
  • \$\begingroup\$ @ouflak you can probably wait until i post it as a real question but your enthusiasm definitely implies I need to. \$\endgroup\$ – kaine Oct 9 '18 at 12:50
4
\$\begingroup\$

Classical construction golf: Wernick's list No. 47

Background

Compass-and-straightedge construction, a.k.a. classical construction, is the construction of lengths, angles, and other geometric figures using only an idealized ruler and compass. A ruler can only be used to draw a straight line passing through two given points; a compass can only be used to draw a circle with two given points (a center, and a point on the circle).

All compass and straightedge constructions consist of repeated application of five basic constructions using the points, lines and circles that have already been constructed. These are:

  • Creating the line through two existing points
  • Creating the circle through one point, with another point as the center
  • Creating the point which is the intersection of two existing, non-parallel lines
  • Creating the one or two points in the intersection of a line and a circle (if they intersect)
  • Creating the one or two points in the intersection of two circles (if they intersect).

Five basic constructions

In addition to these listed on Wikipedia, we have the sixth basic construction:

  • Creating an arbitrary point on the plane, possibly with a constraint:
    • On a line ("line" includes straight lines and circles)
    • Not on a line
    • On a closed or open part of a line, bounded by existing points on it
    • Inside a closed or open region, bounded by existing lines

In any geometric problem, we have an initial set of symbols (points and lines), an algorithm, and some results. From this perspective, geometry is equivalent to an axiomatic algebra, replacing its elements by symbols.

This is the basis of the new kind of : classical construction golf.

Challenge

Wernick's list is a collection of construction problems. The common objective is to recover the three vertices of a triangle, given three of its 16 characteristic points. They include:

  • \$A, B, C, O\$: three vertices and circumcenter,
  • \$M_a, M_b, M_c, G\$: the side midpoints and centroid,
  • \$H_a, H_b, H_c, H\$: three feet of altitudes and orthocenter,
  • \$T_a, T_b, T_c, I\$: three feet of internal angle bisectors and incenter.

Out of the 139 problems, some are solvable by construction, but some are not. The problem we'll tackle here is problem 47, where the given points are:

  • \$A\$: a vertex.
  • \$H_a\$: the foot of the altitude on side \$a\$; that is, the opposite side of the vertex \$A\$.
  • \$T_b\$: the foot of the bisector of angle \$B\$.

Given these three points, recover the other vertices \$B\$ and \$C\$.

enter image description here

Scoring & Winning criterion

Every usage of the six basic constructions (shown above) counts. For the line intersections, creating each point adds 1 score, e.g. if you need both intersections of two circles, you get 2 score from the step.

The solution with the lowest score wins.

Scoring example

Task: Construct the midpoint of two points \$A\$ and \$B\$.

Solution:

  • Draw circle \$C_1\$ with center \$A\$ going through \$B\$. (+1)
  • Draw circle \$C_2\$ with center \$B\$ going through \$A\$. (+1)
  • Draw two intersections \$X, Y\$ of two circles \$C_1\$ and \$C_2\$. (+2)
  • Draw line \$f\$ going through the two intersections. (+1)
  • Draw line \$g\$ going through the two given points. (+1)
  • Draw the intersection \$M\$ of \$f\$ and \$g\$. (+1)

The score of this construction is 7.

Example task

Tools

GeoGebra is a free online geometry tool. In addition to basic and advanced constructions, it has construction protocol feature which clearly shows the steps used to create the final image. For the above example task, the construction protocol looks like this:

Example construction protocol

Out of 9 steps in total, the points \$A\$ and \$B\$ are given, so we can confirm that seven steps are taken for this particular construction.

It also supports scripting (in GGBScript and JS) for those who want to view this challenge as or . Among many geometry commands, the Prove and ProveDetails commands may help you identify if a particular construction is indeed correct.

Notes

I'm using a relatively easy problem here, in order to see how this new challenge type is received. If it goes well, I'll propose some harder and open-ended problems later.


Meta

  • Is this actually on-topic on PPCG? I'm asking this since this is the first challenge of its kind. I'll assume on-topic unless someone says otherwise on this meta question.
  • Maybe we need to tweak the difficulty of the challenge at hand. Is it too easy or too hard? Any other suggestions? I picked Wernick's list because it's not something you may see on Euclidea or similar, and the optimal (or elegant) solutions for many of the problems are not yet known. I'll go for the task this time, and try to ramp up in subsequent challenges.
\$\endgroup\$
  • 2
    \$\begingroup\$ I think it would be a stretch to consider this on-topic: proofs in logic can be argued to be as good as programs by reference to the Curry-Howard correspondence, but I don't really see extending that to proofs in general. It might be more interesting to instead ask for a program which generates proofs and score by the length of the generated proofs (although since the linked paper talks about a 6000-line program to search for them, that may be outside the scope of a reasonable PPCG challenge). \$\endgroup\$ – Peter Taylor Jul 23 '18 at 11:35
  • \$\begingroup\$ On the difficulty of the given theorem: without much effort (5 minutes maximum) I have a solution scoring 16. It's certainly much easier than the existing proof-golf questions to get an answer, although I can believe that there may still be room to golf my solution. \$\endgroup\$ – Peter Taylor Jul 23 '18 at 11:38
  • \$\begingroup\$ (In fact I've spotted one unnecessary intersection, so 15). \$\endgroup\$ – Peter Taylor Jul 23 '18 at 11:49
  • \$\begingroup\$ Do you think this would be better here or on Puzzling? \$\endgroup\$ – user202729 Sep 30 '18 at 12:02
4
\$\begingroup\$

The max() is not enough

The max() is not enough

\$\endgroup\$
  • \$\begingroup\$ This could do with a better title, any suggestions? \$\endgroup\$ – ElectricWarr Oct 2 '18 at 22:14
  • \$\begingroup\$ "Max is only half the story" \$\endgroup\$ – Quintec Oct 3 '18 at 2:06
  • \$\begingroup\$ What if the largest integer in the list is not unique, do we output the second largest? I.e., with the list [1,8,4,8] do we output nothing because the 8 is duplicated, or do we output 4 instead being the largest unique integer? EDIT: Scratch the italic part before. Also, I assume we can take the input in any reasonable format? As an integer list, integer-array, integer-stream, comma-separated string, newline- or space-delimited STDIN, etc? Or is it mandatory to input it in a comma-separated string format? \$\endgroup\$ – Kevin Cruijssen Oct 3 '18 at 8:24
  • \$\begingroup\$ Ignore the first question. Just noticed it's either nothing if all values in the list are unique, or the max otherwise (even if the largest is not unique). In that case: Can the list contain negative integers or zero? And are we allowed to output another falsey value instead of an empty output? \$\endgroup\$ – Kevin Cruijssen Oct 3 '18 at 8:25
  • 1
    \$\begingroup\$ Can we have more test cases with all elements equal \$\endgroup\$ – Jo King Oct 3 '18 at 10:05
  • \$\begingroup\$ I have a 5-byter ready, it's a great challenge if it isn't a duplicate! \$\endgroup\$ – maxb Oct 3 '18 at 12:40
  • \$\begingroup\$ @Quintec Great suggestion to focus on "max" - definitely inspired the new title! \$\endgroup\$ – ElectricWarr Oct 4 '18 at 13:13
  • \$\begingroup\$ @KevinCruijssen / Anyone: I think failing to follow the rules to the letter should be permissible BUT carry some level of bytes as a penalty. I'm not sure what the usual is here - how about 15 bytes each for either using some other input format and for outputting garbage instead of no output? \$\endgroup\$ – ElectricWarr Oct 4 '18 at 13:13
  • \$\begingroup\$ @JoKing Of course, although I'm curious to know - is this somehow non-trivial to infer from the existing cases? What's the catch? :P \$\endgroup\$ – ElectricWarr Oct 4 '18 at 13:13
  • \$\begingroup\$ @maxb This will like be up "for real" sometime tomorrow UK time. Good luck! \$\endgroup\$ – ElectricWarr Oct 4 '18 at 13:13
  • \$\begingroup\$ Nah, but it would help people catch if their solutions are invalid. Also, I would discourage byte bonuses/penalties, and just let solutions take input how they like rather than overriding the site defaults \$\endgroup\$ – Jo King Oct 4 '18 at 13:28
  • 1
    \$\begingroup\$ @ElectricWarr The default is usually to have a flexible input and output formats. But if you insist on having a string comma-separated input, then I will use a split by comma instead to make it into a list in my program itself instead of taking the 15 bytes penalty, considering my full program with list input is just 5 bytes, and changing the comma-separated string to a list is +4 bytes (way below 15 ;p). I would advice to don't use penalties or bonusses at all for challenges btw (and use flexible I/O, but the I/O choice is still up to you of course if you insist on comma-separated strings). \$\endgroup\$ – Kevin Cruijssen Oct 4 '18 at 13:31
  • \$\begingroup\$ Btw, about "Assume input integers may be more than one digit but no larger than 4 bytes", your last test case has 6-byte numbers? \$\endgroup\$ – Kevin Cruijssen Oct 4 '18 at 13:36
  • 1
    \$\begingroup\$ @KevinCruijssen I figure I'll try strict requirements this time around and if it's a problem I'll avoid them in future. On 6-byte numbers - ha! - good point, I'll reword that. Of course I should have foreseen that here of all places "bytes" is a measure of length first and as a quantity of information second! \$\endgroup\$ – ElectricWarr Oct 4 '18 at 13:46
  • 3
    \$\begingroup\$ Polyglot, 30 bytes Takes +15 for not taking any input and +15 for not outputting anything \$\endgroup\$ – Jo King Oct 5 '18 at 1:54
4
\$\begingroup\$

Formulize the sum: Faulhaber's formula

Sums of the form Σkⁿ over k in 1..x can be turned into a polynomial of x whenever n is a natural number.

Examples

Σ1 = x
Σk = (1/2)x²+(1/2)x
Σk²= (1/3)x³+(1/2)x²+(1/6)x

Criteria

You will take n as a non-negative integer input and output the coefficients in reduced fraction form of the resulting polynomial from leading coefficient down to the last non-zero coefficient.

This is code-golf, shortest code wins.

Test cases

0 #=> 1
1 #=> 1/2 1/2
2 #=> 1/3 1/2 1/6
3 #=> 1/4 1/2 1/4  0
4 #=> 1/5 1/2 1/3  0 -1/30
5 #=> 1/6 1/2 5/12 0 -1/12

(extra spacing here is just for clarity and is not necessary.)

\$\endgroup\$
  • \$\begingroup\$ 0 is positive? non-negative is better. \$\endgroup\$ – user202729 Nov 23 '17 at 13:40
  • \$\begingroup\$ Fixed @user202729 \$\endgroup\$ – Simply Beautiful Art Nov 23 '17 at 13:41
  • \$\begingroup\$ Is outputting floating point coefficient allowed? Is errors from floating point imprecision allowed? \$\endgroup\$ – user202729 Nov 23 '17 at 13:43
  • \$\begingroup\$ @user202729 No, because you get some fractions like 5/12 or 1/3 with non-terminating decimal expansions. \$\endgroup\$ – Simply Beautiful Art Nov 23 '17 at 13:45
  • \$\begingroup\$ What about the latter question? / Is errors from integer overflow (for large arguments) allowed? \$\endgroup\$ – user202729 Nov 23 '17 at 13:47
  • \$\begingroup\$ @user202729 Yes, though you program should be able to handle up to, say, n = 20. \$\endgroup\$ – Simply Beautiful Art Nov 23 '17 at 13:48
  • \$\begingroup\$ I think the answer for 3 should be 1/4 1/2 1/4. \$\endgroup\$ – alephalpha Nov 20 '18 at 17:03
  • \$\begingroup\$ @alephalpha thanks \$\endgroup\$ – Simply Beautiful Art Nov 21 '18 at 18:31
  • \$\begingroup\$ Don't we already have a Bernoulli numbers challenge? \$\endgroup\$ – lirtosiast Nov 26 '18 at 19:45
4
\$\begingroup\$

The Hungry Moose

Inspiration.

Moose face harsh conditions during the winter. According to one source:

Their winter foods are lower quality than what they eat in summer and provides less energy, consequently, they need to eat more of it. During harsh winters, having both extreme cold temperatures and deep snow, moose expend more energy than they take in and many can starve.

Challenge

At noon on day 1, a hungry moose starts at a food source (the top left corner). Each morning, the moose may either walk to any 8-adjacent square or stay in place. Each evening, the moose clears the food and snow from its location (adding its net nutritional value to its calorie store and setting that value in the array to 0), and before the end of the day loses 1 calorie to the extreme cold.

The moose dies when its calorie store falls to 0 or below at the end of a day. In particular, if the value at the upper-left corner is 1, 0, or negative, the moose dies on day 1.

Input

A 2D array of integers. Negative numbers represent calorie-negative deep snow.

Output

The maximum number of days the moose can survive (counting day 1 as a full day).

Test cases (add)

6 0 -2 3
0 0 -5 -5
0 0 -1 3
8

42 -100 1
-100 -100 2
3 4 5
42

5 -3 1
1 -9 9
12
\$\endgroup\$
  • \$\begingroup\$ What happens if all the array values are all negative? Does the moose survive a single day or none at all? \$\endgroup\$ – Belhenix Nov 22 '18 at 20:21
  • 1
    \$\begingroup\$ A worked example would be useful. You also need to clarify if we can wrap around the array. \$\endgroup\$ – Shaggy Nov 25 '18 at 14:28
4
\$\begingroup\$

Extremely small data compressor

In 2014 Jarek Duda at Purdue University wrote a paper containing several ideas for encoding computer data, entitled “Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding". The paper is available at Cornell University Library’s ArXiv project: https://arxiv.org/abs/1311.2540

One of the many fascinating things about this paper is that it begins by describing an extremely simple data compression algorithm, using the concept of the "Uniform asymmetric binary systems (uABS)". In fact, it is so simple, that you can implement it in only a few lines of code! Basically it attempts to interpret a sequence of input bits as a single integer - but by interpreting that integer using an alternative to our place-value binary number system, one can "shrink" the size of the input data. In other words, more 'likely' sequences of data will tend to map to 'smaller' integers.

Challenge

You will implement the simple uABS compression algorithm, so that given a sequence of 0s and 1s, your program will compress them into a (usually) smaller sequence of 0s and 1s.

Pseudocode

The algorithm in psuedocode is as follows:

   Begin with an integer X, and set it to 1
   The input data is a sequence of symbols, each 0 or 1, called Input
   Find the probability P that any given symbol in Input is 1
   For each symbol S in Input,
      set X to the output of the function Encode( X, S, P )
   Output the final integer X as a sequence of symbols, 0s and 1s
   End

The Encode function itself can be described as follows:

$$ C(x,s,p)= \left\{ \begin{array}{11} \big\lceil\frac{x+1}{1-p}\big\rceil-1 & \mbox{if } s = 0 \\ \big\lfloor\frac{x}{p}\big\rfloor & \mbox{if } s = 1 \end{array} \right. $$

Where

$$ \begin{array}{11} C \text{ is the encoding function} \\ s \text{ is a symbol, either 0 or 1} \\ x \text{ is an integer} \\ p \text{ is the probability that any symbol in the Input data is 1 } \\ \text{ (the number of 1s divided by the total number of symbols)} \\ \lceil \rceil \text{ is the mathematical ceiling function } \\ \lfloor \rfloor \text{ is the mathematical floor function } \end{array} $$

Input and output format, notes, goofs and gaffes

  • The input is a sequence of symbols, each symbol being 0 or 1, in any method that is available in your chosen language. Examples include a sequence of ascii characters '0' '1', an array of integers, etc.

  • The output will be a sequence of symbols in the same format as the input sequence. The output sequence represents the compressed version of the input data.

  • Empty input data has undefined behavior.

  • Input data containing only 0s has undefined behavior.

  • When testing, note that some times input data may not be shrunk, and sometimes will grow. This typically happens when the number of 1s and 0s is relatively even. Data with an unbalanced number of 0s and 1s results in better compression.

  • You may assume that the number of symbols in the output is less than or equal to the number of bits in your language's largest integer type. The test cases outside this range can be ignored for your language.

  • Note that if you are trying to test this by 'decoding' or 'decompressing' the compressed data, and compare it to the original, one would have to store additional information, such as the length of input and probability P, but for simplicity this has been left out of the challenge.

Example Input and Output

Short examples:

Input             Output    
10                101
10010100000       1011101001
1111              1
11111111111       1
10000000          11011
10011111010101    10110000100101    

Longer examples:

Input  11111110110111110111111111011111
Output 11111000011110110

Input  000000000001000000010000000000001100000000001
Output 1110000101100111000011111

Input  000000000001000000010000000000001100000000001000000000000000000000000000000000000000000000000000000000000000001
Output 1010100110111110010111011110110101010

Scoring

  • Have fun!

  • The program with the fewest number of characters wins!

\$\endgroup\$
  • \$\begingroup\$ 1. IMO the pseudocode could be made clearer by firstly explaining what "machine integer" means (does it mean "unbounded integer" aka "big integer"?) and secondly golfing it a bit: using a "foreach" loop notation for S and eliminating the variable X'. 2. I think it would be helpful to be explicit about how p should be derived from the input. I presume that it means looping over the input twice, once to count and once to compress. 3. IMO restricting the input format to strings of ASCII 0 and 1 detracts from the core challenge. Why not allow arrays/lists of integers? \$\endgroup\$ – Peter Taylor Jul 7 '18 at 12:13
  • \$\begingroup\$ Thanks, i have revised. \$\endgroup\$ – don bright Jul 7 '18 at 14:08
  • \$\begingroup\$ I really like this one. Something quasi-practical, and yet simple and small enough to be fun. Just to be clear, the output is the binary representation fo the integer X, without any leading zeros, correct? \$\endgroup\$ – sundar Jul 8 '18 at 19:02
  • \$\begingroup\$ Also, you mention "input size of at least 128 symbols", but it might be more important to specify output size limit, since many languages have hard bounds on maximum integer size. Since output size varies for the same input length, it might have to be something like "you may assume that the number of symbols in the output is less than or equal to the number of bits in your language's largest integer type". (The last test case would then be optional in languages that can handle only up to 32 bit integers). \$\endgroup\$ – sundar Jul 8 '18 at 19:12
  • \$\begingroup\$ yes the output is the binary representation of the final integer X, i believe the leading zeros is correct. do you think 32 bit is the good limit or 64, since modern machines tend to be 64 bit? thanks \$\endgroup\$ – don bright Jul 8 '18 at 20:05
  • \$\begingroup\$ 32 is probably a reasonable limit, one that most languages can handle without need for external libraries. \$\endgroup\$ – sundar Jul 14 '18 at 14:22
  • \$\begingroup\$ @sunar thanks, i have updated. \$\endgroup\$ – don bright Dec 29 '18 at 14:21
  • \$\begingroup\$ I assume the intent is for P to be calculated as # of '1' in the input / # of symbols in the input? That seems like it would match the definition given, but it would be helpful if it's described explicitly. \$\endgroup\$ – Kamil Drakari Jan 3 at 22:24
  • \$\begingroup\$ Done, thanks.... \$\endgroup\$ – don bright Jan 3 at 23:32
4
\$\begingroup\$

Inscriptio Labyrinthica

In the burial place of King Silo of Asturias there is an inscription that reads SILO PRINCEPS FECIT (King Silo made this).

SILO PRINCEPS FECIT

The first letter is found in the very middle, and from there one reads by going in any non-diagonal direction radiating outward. The final letter is found on all four corners. In this challenge, you'll generalize the process to make them.

Input

A string (or equivalent), and an integer. You may make the following assumptions about the input:

  • The string will have an odd length.
  • The integer will be an odd number between 1 and one less than twice the length of the string.

Output

An inscriptio labyrinthica for the string, using the integer for the height (see models). Output should be each letter with no spaces, line break as default to your system/language.

Test cases

Note that an input of 1 or (length * 2 - 1) will result in a horizontal or vertical palindrome.

 Input: FOO, 3    Input: BAR, 1    Input: BAR, 3    Input: BAR, 5

Output: OOO      Output: RABAR    Output: RAR       Output: R
        OFO                               ABA               A
        OOO                               RAR               B
                                                            A
                                                            R

 Input: ABCDE, 5   Input: ABCDE, 3   Input: *<>v^, 3

Output: EDCDE     Output: EDCBCDE           ^v>v^
        DCBCD             DCBABCD           v><>v
        CBABC             EDCBCDE           ><*<>
        DCBCD                               v><>v
        EDCDE                               ^v>v^

Scoring

This is so shortest answer in bytes wins. Standard loopholes forbidden.

(I feel like I've seen one similar, but searching around I couldn't find it, and I happened to be reading about this king when I got the idea).

Questions

In my original proposal, I had listed as a bonus to draw reading lines, but feedback was bonuses in code golf are discouraged. I still like that idea and am thinking about integrating it as a a main part of the challenge, but don't know if that would over complicate it or actually make it more interesting. The output for REI, 3 in such a case would be

I←E→I
↑ ↑ ↑
E←R→E
↓ ↓ ↓
I←E→I

The idea is that it would prevent simple flipping of data after calculating a quarter or half of the but still perhaps allow for some creative ways (I can think of some creative ways to do it shortly in some languages, but maybe it'll be overly complicated for others).

\$\endgroup\$
  • \$\begingroup\$ @trichoplax I've updated the challenge based on your feedback, let me know what you think. \$\endgroup\$ – user0721090601 Jun 30 at 17:20
  • \$\begingroup\$ Looks good to me. +1 \$\endgroup\$ – trichoplax Jun 30 at 18:24
  • \$\begingroup\$ you should now edit this to a link to the post and delete it. Thanks! \$\endgroup\$ – Giuseppe Jul 24 at 19:11
4
\$\begingroup\$

Golf the truth and null values

In many programming languages there is a null and/or other special values. Sometimes they don't follow the normal rules of boolean operations. They may not even agree with the values of the same name in other languages.

Here are some different kinds of the "extended" boolean values, either borrowed from some languages or invented myself:

  • False.
  • True.
  • Absent. All operations between absent and another operand return the other operand.
  • Whatever. All operations between whatever and another operand returns whatever (itself).
  • Partial. If the result can be decided using the other operand, return that. Otherwise return partial (itself).
  • Error. An error as the first operand works like whatever, and an error as the second operand works like partial, except that "itself" means error. It has higher precedence than whatever and partial.

Your task is to define all these values in your language, and the 2 operations and or.

To be clear, the 2 operations should work exactly as in the following tables. The left column represents the first operand, and the top row the second operand.

and F T A W P E       or F T A W P E
  F F F F W F F        F F T F W P E
  T F T T W P E        T T T T W T T
  A F T A W P E        A F T A W P E
  W W W W W W W        W W W W W W W
  P F P P W P E        P P T P W P E
  E E E E E E E        E E E E E E E

Rules

You could use anything distinct and consistent to represent these values. You don't have to use a truthy value to represent true, or a falsy value to represent false. You are allowed and encouraged to use values that contain useful code, i.e. this loophole is not forbidden.

You are allowed to use actual errors or exceptions to represent some of the values. In this case the definition of that value should throw the same error, instead of represent the caught error. But the caught errors or the output messages should be distinct and consistent. Alternatively, you may choose to include STDERR in the output of your code, and use the printed message string as a normal value.

You may choose to pass functions generating and returning the values but doing nothing else to your code as input, in place of the values themselves, without counting the extra code.

You may use different ways of input/output for different values, as long as it is consistent for each kind of value, and it is possible to tell apart the first and the second operand.

You are allowed to use builtin functions and operators without boilerplate, in any argument order, even if you cannot save them in something callable in your language.

There could be some common code shared by all the 8 definitions and appear only once as header/footer. Other than that, the 8 definitions of operations and values must work independently from each other. The only way you can call something defined in the values in the operations is through a valid input method (e.g. you cannot set a variable in a value and read it in an operation).

Your score is the length of common code * 12 + the total length of the 2 operations * 6 + the total length of the values. Smallest score wins. The length of a value is either the length of the code generating it, or the length of itself unquoted if all the values are strings and you choose this way.


Abandoned rules

You are allowed to use operators, or chains of operators and values to represent the 2 operations, even if you cannot save them in something callable in your language. You may require the operands to appear at specific positions, but each operand must appear exactly once and be grouped together. You may choose whether to save operands in variables previously, and don't count the assignment if it doesn't add new information in the assignment (e.g. by changing its type). This makes it possible to use the built-in operators with short-circuit evaluation in languages that don't allow redefining them and preserve this characteristic, and may also make it shorter in some other languages.

Previous scoring: total length of the 2 operations * 50 + the total length of the values.

Possible follow-up

Original title: All the weirdness about the nulls

Extended tables including Valid in a previous version, Reverse aka Opposite by Zgarb, and Possible.

and T F N O W E V R P     or T F N O W E V R P
  T T F T O W E ? F T      T T T T T W T T T T
  F F F F F W F F F F      F T F F O W E ? T F
  N T F N O W E ? ? ?      N T F N O W E ? ? ?
  O O F O O W E ? O O      O T O O O W E ? O T
  W W W W W W W ? W W      W W W W W W W ? W W
  E E E E E E E ? E E      E E E E E E E ? E E
  V T F ? O F F ? ? ?      V T T ? T F F ? T ?
  R F F ? O W ? ? ? ?      R T T ? O W ? ? ? ?
  P T F ? O W ? ? ? ?      P T F ? T W ? ? ? ?

Other potential additions:

  • Default, that is opposite to Opposite.
  • Merge Possible with Valid.

Sandbox questions

  1. Will this be too easy in some languages that already have all of them?

    In languages that has True defined to be -1 and unifies bitwise and logical operations, most integers would works as Partial. GCD/LCM in APL is similar to this. SQL null is Whatever Partial. Most languages that has shortcut evaluation has errors as Error. Not sure about Absent, though.

    (Maybe the easiest way to find out is to post this question. It doesn't make the answer bad. But it's just some consideration in the sandbox for me to decide whether I'll post a stronger version.)

  2. Allowing "operators and chains of operators" seems to open a can of worms. Should I just remove this rule?

\$\endgroup\$
  • \$\begingroup\$ How about Opposite that behaves like the negation of the other operand? \$\endgroup\$ – Zgarb Dec 11 '16 at 19:10
  • \$\begingroup\$ @Zgarb Too similar to Other. For the "2 more to be added", I intended to make it possible to write expressions to 1) decide whether a variable is a specific value, and 2) return a specific value if a variable is true, or false otherwise. This may make the list more useful later. \$\endgroup\$ – jimmy23013 Dec 11 '16 at 19:42
  • \$\begingroup\$ @Zgarb I gave up and even removed one, to make hardcoding the tables less likely to be the optimal way. \$\endgroup\$ – jimmy23013 Dec 13 '16 at 17:56
  • \$\begingroup\$ if(whatever){/*???*/} \$\endgroup\$ – Pavel Dec 13 '16 at 20:23
  • \$\begingroup\$ @Zgarb I forgot this post for some reasons. Now I found your idea quite interesting. But I'll post the first version without it, and may add a stronger version if it worked well or is too easy, and may name it Degenerate to make most of the other results from operations make sense. \$\endgroup\$ – jimmy23013 Apr 30 at 8:40
4
\$\begingroup\$

Knight's tour


A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. For those who are not aware of how knights in chess work, knights are capable of moving in an L shape:

knight's moves

Tours generally apply to a regular chessboard of size \$8\$ however, it can be calculated for other sizes. For example, for a chessboard of size \$5\$, a possible knight's tour is:

5×5 knight's tour

Each grid size has quite a few combinations, for example, when \$n = 5\$, there are \$1728\$ possible tours and for a regular chessboard (where \$n = 8\$), there are \$19591828170979904\$. This is OEIS A165134.

Challenge

Write a program/function that takes a grid size \$n\$ and outputs a possible valid board of integers.

Specifications

  • Standard I/O rules apply.
  • Standard loopholes are forbidden.
  • \$n > 4\$
  • This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
  • Built-in functions that compute this sequence are allowed but including a solution that doesn't rely on a built-in is encouraged.
  • Explanations, even for "practical" languages, are encouraged.

Test cases

Yet to come.

\$\endgroup\$
  • 5
    \$\begingroup\$ "Your code will be scored in bytes, usually in the encoding UTF-8, unless specified otherwise.": So a Jelly answer will need to specify "Jelly (Jelly codepage)" or else it needs to count bytes of a unicode encoded source? Why not leave it out and let the tag code-golf handle the rules. And instead of generating test-cases, you could just add a program that validates the result as there are a lot of possible answers . \$\endgroup\$ – ბიმო Sep 22 '18 at 14:19
  • 1
    \$\begingroup\$ @ბიმო Heh, I did this back with all my challenges when I was obsessed with creating "the perfect challenge template." I'll remove it. As for the test cases/validation program, I'll probably do both. \$\endgroup\$ – totallyhuman Jul 12 at 1:55
  • \$\begingroup\$ @lirtosiast Oops, turns out I had mistaken the meaning of the Wikipedia section I just linked. I'll specify that a submission is not required to work on any \$n < 4\$. \$\endgroup\$ – totallyhuman Jul 12 at 2:00
  • \$\begingroup\$ Another Mathematica built-in is coming~ \$\endgroup\$ – tsh Jul 12 at 7:27
  • \$\begingroup\$ Can output be a list of coordinates? \$\endgroup\$ – tsh Jul 12 at 7:29
  • \$\begingroup\$ Having both test cases and a validator sounds good to me too \$\endgroup\$ – trichoplax Jul 14 at 7:59
4
\$\begingroup\$

Babel on and on (working title...)

Background

Babel is a cornerstone of modern web development. It takes Javascript using new or proposed ECMAscript features and "transpiles" it into an older language version, so that browsers can run it without updates. In order to do this it inserts its own shim methods, and own custom transforms.

The Challenge

Your objective is to write the Javascript code which produces the largest babel output in characters. Your code must be less than or equal to 128 bytes in length

Babel has an online, interactive compiler which you can access HERE. It's highly recommended that you use this to form your answer. If you work locally, you are restricted to modifying only the settings that the babel website allows you to modify.. There is a guide on installing babel at the end of the question.

Rules

  • For consistency, you may use a Babel version between 7, but not above 8.* (when it eventually comes).
  • You may change the interactive REPL's settings, source type, presets, options, and env-presets. You may change these settings locally if you are using a local installation of babel.
  • You may only provide one input file.
  • You may not exceed 128 bytes in your input file.
  • You may not add your own plugins.
  • You may not use the loophole listed below, or any of the standard loopholes.
  • You may not use error output as a result. babel must transpile the code successfully under one of the allowed configurations.
  • Neither your input or output need to run, or halt. The compilation just needs to output something.

Examples

41 in, 1075 out

{t: [...(function*(){let [a,b]=[1,2]})]}

32 in, 1101 out

export class b{d=function*(){}}

125 in, 7336 out

const b = function*(){return function*(){return function*(){return function*(){return function*(){return function*(){}}}}}};

Scoring

You must provide both the code and the settings you are using. For users of the online REPL, a link with the settings set in the URL suffices. The answer with the largest output with an input less than or equal to 128 bytes wins. Unlike many challenges of this nature, settings do not cost any bytes of input.

Setting up a local environment (OPTIONAL)

Most of the people doing this challenge will probably use babel's online transpiler to complete it. In the event that the website is taken down in the future or made inadequate for the challenge, it can be completed locally. Make a folder for the challenge, and in a shell in that folder, try something like the following:

Install Babel (globally - you could do it locally)
sudo npm install -g @babel/core @babel/cli
Set your .babelrc with a preset (in this case env)
echo '{"presets": ["@babel/preset-env"]}' > .babelrc
Install babel's dependencies
npm install --save-dev @babel/preset-env @babel/core

Then, given an input file test.js, you can figure out your output score with

babel test.js | wc -c

Happy Hunting!

Questions

This is my first time ever posting one of these. Does everything look on the up-and-up?

Also, should this incorporate "the less characters of input, the better?". I kept trying to think of ways to reward a large output for a small input, but every way I considered changed the tone of the challenge significantly.

Also also, I know that codegolf users don't like being constrained to one language. Is this bound to be an exception or will that stop the question in its tracks?

Proposed Tags: [BUSY BEAVER], [Javascript], [CODE CHALLENGE]

\$\endgroup\$
  • 2
    \$\begingroup\$ Hi and thanks for using the sandbox! I'll start right off by saying I don't know enough about babel to particularly talk about if this will be interesting. I think this kind of challenge is fine, just like regex-golf. This should probably be tagged code-challenge and shouldn't be tagged compiler. I am concerned that you tie everything to an external site. While I doubt the site will go down, what happens when they update babel? Will it break the challenge? Since this is a bit abnormal, you may want to ask on meta (specifically about the online scoring) or in chat for more feedback. \$\endgroup\$ – FryAmTheEggman Jul 1 at 21:56
  • 2
    \$\begingroup\$ @FryAmTheEggman thanks for the tags and pointing me to meta for this, I think I'll wind up clarifying things over there. And also, about the foreign site - it's not required, but makes it far, far easier. That's why I edited in the clause about being able to do it locally. If the site is used, the settings are query parameters in the URL (but could be interpreted even if it went down). And contestants can do it locally, provided they post the settings they use, and use the same version. So I'm not too worried about tying it to a site, since it's just for convenience. \$\endgroup\$ – Nathaniel Pisarski Jul 2 at 12:52
  • 1
    \$\begingroup\$ We discourage language specific challenges when there is no reason for it, but here it is clearly part of the challenge so I see no problem at all. \$\endgroup\$ – trichoplax Jul 16 at 20:42
  • 1
    \$\begingroup\$ Having a fixed number of input bytes to work with can be awkward in language agnostic challenges as it's difficult to choose a suitable number that doesn't make it too difficult / too easy for some languages. Since everyone is using the same language here a fixed 128 bytes seems reasonable. Your examples already show it doesn't need to be higher. You could consider lower, depending on how you want the challenge to go. With 128 bytes there's a good chance some outputs will be too large to fit in the 65536 character answer length limit, but I don't see that as a problem either. Looks good to me \$\endgroup\$ – trichoplax Jul 16 at 20:47
4
\$\begingroup\$

Castilian Numerals

A little known (but actually real) number system are the Castilian numerals. They were an odd mix of a digital and positional counting system used in Spain in the late middle ages. There are certain qualities about them, however, that make them not entirely straight forward to generate when you have lots of them in a group, in particular the fact they would be aligned by thousands places. Your challenge will be to print a vertical list of numbers, correctly spaced.

Description of the Numerals

A Castilian numeral is, in effect, a Roman numeral, but only uses 1-999, uses additives for 4 (IIIJ), 9 (VIIIJ), and 900 (DCCCC), and subtractives for 90 (XC) and 400 (CD). Both methods were commonly used for 40 (XL, XXXX). Additionally, final Is were written as Js, such that the sequence 1-6 goes J, IJ, IIJ, IIIJ, V, VJ. (This means standard Roman numeral generators will likely not be much help.) They were generally written lowercase, but for this challenge we'll use all uppercase.

For values under between 1-999, the fact that the letters indicated numerals was made clear by the presence of a symbol that looks like a U. Generally the numerals themselves were right aligned:

1          U           J
2          U          IJ
999        U DCCCXCVIIIJ

For values between 1000-999999, everything we would place to the left of the comma would be rendered as if it were its own independent 3-digit number and romanized, and the reminder placed to the right, such that

  1,000    J U
  1,001    J U          J
 21,030  XXJ U        XXX
500,444    D U CDXXXXIIIJ

For values 1,000,000-999,999,999, an additional separator was used, Qto, but for our purposes, we'll just use Q. It would only be used if the number was over 1,000,000, unlike the U that always separated it.

  1,000,000       J Q       U
  1,000,001       J Q       U            J
  1,001,000       J Q     J U
  1,001,001       J Q     J U            J
123,456,789  CXXIIJ Q CDLVJ U DCCLXXXVIIIJ

As should be noticed, within each grouping of three (arabic) digits, everything is right aligned, with the thousands/million separators all in alignment. Because 0 didn't exist, it would just be left blank.

Input

A sequence of integers in whatever format you feel gives you the best advantage (a list, an array, a series, etc). You may assume that the integers are between 1 and 999,999,999.

Output

A printed list of Castilian numerals, properly aligned on different lines. Note the restrictions on 4/9: mandatory additives are 4,9,900; mandatory subtractives are 90 and 400; 40 is valid either way. The numerals for 1-999 should be right aligned, with a single space on either side of Q or U (there may be padding spaces, but the single longest numeral in each grouping will have the single space). Newlines may be whatever is native to your system/language.

Rules

This is code golf. Fewest bytes wins. Standard loopholes forbidden.

Test cases

Comments/observations are given after # and not part of the output.

Given: 1,2,3
U   J   
U  IJ
U IIJ   # one space between U and I

Given: 1,1000,10,100
  U J
J U     # trailing space not required
  U X
  U C

Given: 123,4,5678,111111111,90,12345,6789012
                U    CXXIIJ
                U        IV
              V U DCLXXVIIJ   # single space between U and the longest numeral
CXJ Q       CXJ U       CXJ   # Q only appears if >= 10^7
                U        XC
            XIJ U  CCCXXXXV   # also valid CCCXLV 
 VJ Q DCCLXXXIX U       XIJ   # single space between Q and the longest numeral
\$\endgroup\$
4
\$\begingroup\$

Character Frequency in a String

Tags:

Posted here.

\$\endgroup\$
  • 3
    \$\begingroup\$ i dislike the special case of space \$\endgroup\$ – Jo King Jul 21 at 1:25
  • \$\begingroup\$ @JoKing If there was no special case for space, a string like 1 a would look something like 1 1; 1;a 1. Also, it's for the challenge. \$\endgroup\$ – bigyihsuan Jul 21 at 3:19
  • \$\begingroup\$ I'm with @JoKing on this; nothing is added to the challenge by special-casing spaces. \$\endgroup\$ – Shaggy Jul 21 at 21:08
  • \$\begingroup\$ I'd like to further say that restricting the output this much doesn't seem to add much to this challenge. Why isn't, for example, a list of pairs acceptable? I can't find any justification for your output rules. That's not to say you can't do it, but I have a hard time imagining it will be popular. \$\endgroup\$ – FryAmTheEggman Jul 22 at 18:58
  • \$\begingroup\$ Related. \$\endgroup\$ – AdmBorkBork Jul 23 at 20:15
  • \$\begingroup\$ @AdmBorkBork, having since given it a try in JS, I'm pretty sure there's a closer (potential) dupe target than that. \$\endgroup\$ – Shaggy Jul 23 at 22:12
  • 3
    \$\begingroup\$ Having posted this, you should delete the sandbox post. \$\endgroup\$ – Adám Jul 24 at 6:29
4
\$\begingroup\$

Golf range minimum queries of a list

, , and

Looks like this post hasn't gotten any problems called out, but also not that much support. If you could leave even a brief comment if you don't like it, that would be much appreciated.

(Inspired by the first problem solved in Stanford’s advanced data structures course.)

Despite the academicese-heavy name, the problem we're going to solve is almost unbearably simple.

We have a list of numbers.

[31, 41, 59, 26, 53, 58, 97]

We're going to cut some contiguous snippet out of that list of numbers.

[31, 41, 59, 26, 53, 58, 97]
    |41, 59, 26, 53|

And then we're going to find the minimum of that snippet. In this case, that's quite obviously 26. That's all.

And the obvious solution is pretty fast, too, with O(n) time and O(1) space in the size of the list:

minval = arbitrarily large value
for (i=first snippet index, i<last snippet index, i++)
  if (list[i]<minval) minval = list[i]

So what's with the ?

Where it gets interesting is when you try to see how efficient you can make it when you have a fixed list but a large number of range minimum queries -- snippets to find the minimum of. This version of the problem is useful, for example, if you have a huge time series you want to load only once, but you want to find the minimum of many different subintervals of that time series.

In such a scenario, it would actually be faster in practice to literally precompute all n**2/2 queries, store it in a table, and then just retrieve data from that table for an O(1) time and O(n**2) space solution. Dynamic programming solution from the Stanford slides ^dynamic programming solution taken from the Stanford slides

And then if you're clever enough, you realize that you only have to store each query with size that's a power of two -- you can just combine those power-of-two minima to sum to an arbitrarily sized query, and achieve the same results with constant time and linearithmic rather than quadratic space.

Interestingly, if you keep optimizing, you can get to an O(1) time and O(n) space solution using a sort of augmented list known as a Fischer-Heun structure. I'd love to go into the details of the structure here, but explaining how it weaves into Cartesian tree building on fixed-size snippets would make this question about 50 pages long. It's explained in the Wikipedia page linked in the title (which I've copied here), however, along with several faster-than-linear intermediate structures.

(If you can get past a research paywall, here's the original Fischer & Heun 2011 paper. And if you’d prefer the much more verbose but much more hand-holdy Stanford lecture style, here are the follow-up slides that goes into this solution, including lots of intermediates.)


The challenge

You can either write a full program or a function that calculates the result of a series of range minimum queries given a fixed list. Scoring is set up such that in general, the shortest and most-efficient-over-lots-of-queries code wins.

Input:

A list of integers xs, followed by a series of i, j pairs denoting the start and end of the snippet, inclusive (so the 26 example above uses indices i=1 and j=4). The list of integers is guaranteed to have at least one integer, and 0 <= i <= j < len(xs). This can be taken in any format that works best for your language — for example, one list for xs and one list of tuples for the i, j pairs; or maybe all the different pairs as a variable number of arguments. For a full program that takes in input from stdin, I’ll fix a format for the input:

xs[0] xs[1] xs[2] xs[3] ...
i1 j1
i2 j2
i3 j3
...

Output:

An ordered collection of the range minima for each i, j query, in the same order that they were given. In case an unordered map (such as a Python dictionary) from each i, j query to its range minimum works better for your language, that will also be allowed as an output; as long as it's obvious which minimum is related to which query.

Once again, for a full program that prints to stdout or a file, I’ll fix the format to have each range minimum on each newline (trailing newlines permitted).

Scoring:

Lower score is better; score is determined by

at(b)^2+as(b)

Where b is the byte count of your code, at is the asymptotic runtime Ө(n) of the algorithm in the size of xs interpreted as a function of n, and as is the asymptotic space usage Ө(n) in the size of xs interpreted as a function of n.( All constant coefficients in such Ө(n) expressions must be 1, and only the fastest growing term may be kept in expressions, as is standard.)

Therefore, the above pseudocode solution, which uses Ө(n) time and Ө(1) space, and is 126 characters, would have a score of (b => b**2 + 1)(126)=15876+1=15877. (Of course, the pseudocode isn't really valid since it's missing a construct to deal with multiple queries, and also because it's uncompilable pseudocode...)

Test cases:

Input:

31 41 59 26 53 58 97
1 4
0 2
5 6

Output:

26
31
58

Input:

1
0 0
0 0

Output:

1
1

Input:

-4 28 31 -54
0 0
0 1
0 2
0 3
1 1
1 2
1 3
2 2
2 3
3 3

Output:

-4
-4
-4
-4
28
28
-54
31
-54
-54

Sandbox Questions:

  • Would the asymptotic runtime count as a non-observable requirement?

  • is this too long and/or abstruse lol

  • I’m not sure how to word the scoring section to narrow down the most obvious, basic O(n) expression — an algorithm that’s Ө(n) is also Ө(n/16384-50000) by definition. Is what I have clear enough? Have I left any loopholes?

  • I kind of wanted to encourage people to try to implement Fischer-Heun or one of the more time-efficient intermediates in the slides, without restricting them to one particular algorithm (e.g. challenge: you have to make a Fischer-Heun structure). Does the scoring system make sense for this? Is it fair to have, for example, a Jelly answer using the naive algorithm in 3 bytes (score 10) compete with a Jelly answer using the Fischer-Heun structure in 30 bytes (score 31); but a naive Python answer with score 3000+ compete against with a Python Fischer-Heun with score 300?

\$\endgroup\$
  • 3
    \$\begingroup\$ [tag:tag-name] \$\endgroup\$ – Adám Jul 30 at 19:06
4
\$\begingroup\$

Game of Game of Life

Conway's Game of Life is a 0-player game. But that's okay! We can make it a multi-player game.

This game is played on the smallest square grid that will accommodate a 6x6 square for each player (12x12 for 2-4 players, 18x18 for 5-9 players, etc). This grid is actually a torus, so it wraps in both directions. The rules of Life are:

  • If a cell has exactly 3 neighbours, it comes to life (or remains alive) in the next generation.
  • If a cell has exactly 2 neighbours, it does not change in the next generation.
  • If it does not have 2 or 3 neighbours, it dies in the next generation.

A cell's neighbours are those cells adjacent to it orthogonally or diagonally; each cell has 8 neighbours. In this game, there are only a few differences from the standard Game of Life:

  • Each player has a different colour of life, with dead cells being white and neutral living cells being black.
  • When a cell becomes alive, it takes on the colour of its most common neighbour, or black (no player) if there are three different colours. Cells do not change colour as long as they are alive.
  • Each generation, each bot can cause one nearby cell to come alive in their colour or one of their own cells to die. This happens before a generation is processed; a cell that is killed may come back to life and a cell brought to life may die in the subsequent generation.

Winning the game

The game lasts 1000 generations, or until there is only one colour of living cells remaining. If all coloured cells die on the same generation, the game is a draw, and no bot receives points. Each bot scores points equal to the percentage of living coloured cells it has at that time (out of the total number of coloured cells). 1000 games will be run, and the winner is the bot with the highest average score. Ties are broken with a 1v1 cage match.

Starting conditions

Each bot will start with the following layout of living cells:

......
......
..##..
..##..
......
......

These will be randomly arranged into the square playing area. Each 6x6 area without a bot will have the same configuration, but with black living cells.

Bot parameters

Your bot will be written in Javascript, and will not have an average call time of over 50ms (bots that do may be disqualified, but bots may use performance.now() to police their own time). It will accept as parameters:

grid - The grid on which the game is played.  This should not be modified.
botId - The bot's ID, corresponding to the colour on the grid.
lastMoves - An array of each bot's most recent move, as it's (usually) possible but computationally intensive to get this information otherwise.

Your bot will return an array with two elements, x and y. This is the cell that your bot wishes to play. It must be within 2 cells of one of your living cells. If the selected cell is alive and not one of your cells, it does nothing unless the bot whose colour it is removes it on the same generation, in which case it causes it to be your colour. If it is alive and one of your cells, that cell is killed before the next generation. If it is a dead cell, it comes alive before the next generation (it comes alive as your bot's colour unless some other bot also picks it, in which case it comes alive black).

A play too far away from one of your cells is a pass. Alternately, [-1,-1] is an explicit pass. A play off of the board in any other way is illegal and grounds for disqualification.

Other Restrictions

  • You may make a maximum of 3 bots.
  • If your bots uses random numbers you can use Math.random.
  • Your bot may, if it wishes, store data on this. It will be cleared between games.
  • You may not make a bot which targets a single, prechosen bot. Your bot may target the tactics of a class of bots.
  • Cooperation is legal between bots, but communication is not - you can cooperate with a strategy, but not attempt to make a specific sequence of moves which identifies your bot. For example, identifying a bot based on specific starting sequence is not allowed, but knowing "target bot prefers moving up and left, all else equal" is okay. IDs are randomized and bots will not know in advance what other bots' IDs are.

Controller

Not built yet.

Sandbox Questions

  • Is this clear?
  • Have I missed any common loopholes I should really close?
\$\endgroup\$
  • \$\begingroup\$ The initial set of squares should have a guaranteed distance from each other set of squares. grid needs better specification. What does "nearby square" mean? Other than that, solid spec. \$\endgroup\$ – Nathan Merrill Oct 31 '18 at 13:12
  • 2
    \$\begingroup\$ 1) The wording is weird on the Game of Life rule explanation. Please take a look at the Wikipedia page and clarify them. Currently, I'm not sure if a cell can change color if it's surrounded by more opponents than allies. Also, it seems to be implied that a live cell surrounded by 3 neighbors dies (which I'm pretty sure wasn't your intention). 2) What happens when no colors remain on the board? 3) Nitpick: the "this" in "it has at this time" threw me off - "that" instead, perhaps? \$\endgroup\$ – Alion Oct 31 '18 at 13:18
  • 2
    \$\begingroup\$ 4a) Since there's no explicit ban on cooperation, it's allowed by default. Was this your intention? 4b) Can bots communicate with each other? 5) Can bots store data across games? 6) Can we get a more easy-to-use system of storing data within one game? Scopes are useful for this: function externalFunc() { /* Storage */ return function gameLoopFunc(args) { /* Code */ }; } 7) next is not very robust. Some people (including myself) will remake the game simulation to gain access to more advanced functionality. 8) What happens if the returned value isn't within 2 cells of one of my own cells? \$\endgroup\$ – Alion Oct 31 '18 at 13:30
  • 1
    \$\begingroup\$ 9a) Why is selecting a live cell that is not your own a legal move, despite not doing anything? 9b) Is it legal to pass a move always? If so, what should we return if we want to pass a turn? 9b2) If it's not legal to pass a turn... why? It sounds pretty useful and makes sense. Please consider it. \$\endgroup\$ – Alion Oct 31 '18 at 13:33
  • \$\begingroup\$ @NathanMerrill Thanks, I've clarified that now. \$\endgroup\$ – Spitemaster Oct 31 '18 at 13:46
  • \$\begingroup\$ @Alion I've fixed 1, 3. I've removed next - good point (7). I've changed access to localStorage to access to this, clears between games (5,6). I've changed the scoring to a percentage and clarified draws (2). I've clarified that passing values out of bounds is illegal (8) and what (9a) does. I've also made passing legal (9b/c). (4) I did intend for cooperation (but not communication) to be legal; I've clarified that. Thanks for all the help! \$\endgroup\$ – Spitemaster Oct 31 '18 at 14:02
  • 2
    \$\begingroup\$ Splendid work. That being said, I'm not done yet. 10) Typos: id > it (line 2 of rule explanation), bot's > bots' (last restriction). 11) Can bots modify the grid passed to them (in the non-malicious sense)? 12) Black doesn't immediately strike me as a living cell. I'd recommend specifying that there exist neutral living cells (I only realized this during my 4th reading). 13) What format should submissions be? Template and example submissions both work. 14) Controller: If you haven't already, you should check out Dave's JS KotH framework. \$\endgroup\$ – Alion Oct 31 '18 at 15:21
  • \$\begingroup\$ 15) You've opened Pandora's Box with cooperation restriction. I'll illustrate what I mean with several abstract examples. GrudgeBot and PassiveBot: GrudgeBot will not attack PassiveBot, because PassiveBot doesn't bother GrudgeBot. FriendlyBot: Attempts to make friends with bots that it comes into contact with by testing if they will attack it. 2 instances would quickly team up after meeting each other. AlgoBot: Runs simulations and tests how well other bots play according to its idea of "optimal". 2 instances quickly realize that the other is playing optimal or near-optimal moves and team up. \$\endgroup\$ – Alion Oct 31 '18 at 15:40
  • \$\begingroup\$ 15 cont.) So, where do you draw the line? 16) performance.now() for timing purposes. Introduces unpredictability, but lets bots police their own time instead of their creators having to wildly guess the right values. Allowed or not? 17) cellular-automata, game, grid (maybe). \$\endgroup\$ – Alion Oct 31 '18 at 15:44
  • \$\begingroup\$ Whew, what a rampage. Despite all of that, I'm impatiently looking forward to this hitting main. Expect to see me there immediately. Keep up the good work! \$\endgroup\$ – Alion Oct 31 '18 at 15:47
  • 1
    \$\begingroup\$ Thank you very much! I've fixed (10)-(12). I'll add an example submission when I'm finished the controller - and I will definitely check out that framework! (15) - Good point, but I don't want to give an advantage to people who build multiple bots. I've added a clarification that a test for "too much cooperation" is preset move sequences and the like - identifying a bot by its strategy is okay. There's room for interpretation, but I trust that non-malicious entries will be reasonable. All of your examples I'm okay with. :) I will add some tags. \$\endgroup\$ – Spitemaster Oct 31 '18 at 15:58
4
\$\begingroup\$

Polyglot wrappers

Many polyglots are a disastrous mess of unmaintainable code. Let's make this different.

Challenge

Make a polyglot "wrapper" such that code from two or more languages may be embedded in the file without modification.

Example

Consider the following polyglot wrapper for Bash and Python:

'''true'
B
exit 0
#'''
P

This wrapper can be used such that B can be replaced by an arbitrary bash script, and P can be replaced by an arbitrary python script.

After the scripts have been injected into the wrapper, running the resulting polyglot via either interpreter (bash or python) will result in functionally identical behavior as the original input scripts.

Rules

  1. Your wrapper must support the injection of 2 or more languages
  2. Your wrapper can use arbitrary markers for the string->script replacement
  3. The markers must be at least 1 byte in size (no line number tricks)
  4. Assume the replacement will be done by first replacing all markers with sufficiently long and random data, such that conflicts between the marker literals and contents of the input code cannot exist. However, your markers cannot conflict with the contents of the wrapper itself.
  5. The behavior of the original input programs must not be altered by the wrapper. Ex: an input program that returns 0 must return 0 when run from your wrapper. An input program that crashes must still crash.
  6. The winner is the polyglot wrapper that supports the most languages, with a tie breaker of smallest size (in bytes).
  7. Allowances shall be made for a program that accesses itself on disk. Obviously no polyglot wrapper could correctly return identical output for a script that outputs its own file size.

Question for the sandbox

Is this sufficiently unique and understandable? Are there any loopholes I haven't covered?

\$\endgroup\$
  • 1
    \$\begingroup\$ What if, for example the bash script contains '''? Is that what rule 4 is talking about, since I don't really understand that rule. \$\endgroup\$ – Jo King Sep 2 at 5:51
  • \$\begingroup\$ I'm indeed wondering the same as @JoKing. What if the content of the code we'd potentially insert into the wrapper contains something that could break the wrapper or other program itself? For example, let's say I submit 0W, where 0 is a wrapper for a 05AB1E program, and W for a Whitespace program. 05AB1E in general ignores all whitespaces between commands and Whitespace ignores all characters except for spaces/tabs/newlines. But what happens if the potential 05AB1E program contains a string with a space/tab/newline in it, which would interfere with the Whitespace program? \$\endgroup\$ – Kevin Cruijssen Sep 2 at 9:25
  • \$\begingroup\$ Perhaps make it such that the inner programs are a turing complete subset of the parent language, such that the overall program will always run correctly. Answers would have to make a list of restrictions placed on the language subsets, as well as prove that they are still turing complete, and can't 'break out' of their wrappers, nor have effects on other sections of the program \$\endgroup\$ – Jo King Sep 2 at 12:08
  • 1
    \$\begingroup\$ Would this work as a cops and robbers? Cops provide wrappers and robbers provide code that breaks the wrappers? \$\endgroup\$ – trichoplax Sep 3 at 11:49
  • 1
    \$\begingroup\$ Good catch, everyone! I'll have to think about this some more. Cops and robbers sounds like a good way to make that problem into a feature, @trichoplax \$\endgroup\$ – BLuFeNiX Sep 3 at 14:16
  • \$\begingroup\$ Your example can break in a different way too. An unterminated here-doc in bash will continue until the end of the script: B = cat << EOF \$\endgroup\$ – GammaFunction Sep 8 at 6:29
3
\$\begingroup\$

Metagolf: Catlike Piet

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

yourprogram < file > output
piet output

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

One-liners

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

=  none (continue color block)
|  push
^  pop
+  add
-  subtract
*  multiply
/  divide
%  mod
~  not
>  greater
.  pointer
\  switch
:  duplicate
@  roll
$  input number
?  input character
#  output number
!  output character

which is trivial to convert to a Piet program with the following (partially golfed) Python code:

def P(s):
 h=v=0;l=len(s)+1;R="P3 %i 2 255 192 0 0 "%(l+2)
 C=[1,3,2,6,4,5];V=[0,192,192,255,0,255]
 for x in map("=|^+-*/%~>.,:@$?#!".find,s):
  C=C[x//3:]+C[:x//3];V=V[x%3*2:]+V[:x%3*2]
  for i in [1,2,4]:R+="%i "%V[(C[0]//i)%2]
 return R+"255 "*4+"0 0 "+"255 "*l*3+"255 0 0 "*2

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

Scoring

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

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

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

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

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

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

\$\endgroup\$
  • 1
    \$\begingroup\$ It took me a while to understand the task as "Write a program taking INPUT which produces as output a piet program that takes no input but produces INPUT." I think it is a interesting and challenging, but it's reception will depend entirely on how many people are willing to learn/futz-around-in/deal-with piet. And I have no feel for how many that is. \$\endgroup\$ – dmckee Jul 7 '11 at 3:12
  • \$\begingroup\$ @dmckee; would it be better if I just used a reduced instruction set, and only ask for the instruction stream? I think this is still challenging with {push 1,duplicate,add,subtract,multiply,output}. Come to think of it, if I restrict to {push 1,duplicate,add,output}, there's a reduction to some awesome algorithms. \$\endgroup\$ – boothby Jul 7 '11 at 4:48
  • \$\begingroup\$ I did this in piet some time ago: craigoclock.blogspot.com/2011/05/metaprogramming-in-piet.html \$\endgroup\$ – captncraig May 21 '12 at 18:31
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) \$\endgroup\$ – programmer5000 Jun 9 '17 at 15:22
3
\$\begingroup\$

Chess move

The Challenge

Write a program that gets a string containing a chessmove and a chessboard as input, and then outputs the chessboard.

Requirements

The chess move will have this format:

<from square><to square>[<promoted to>]

Examples:

d2d4
f8g7
a7a8R

The chessboard format is not fixed, but there must be a 1 to 1 relation between the board and the string to represent the board. Also the format of the input must bet the same as the format of the output. Two suggestions of what it could look like:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR

rnbqkbnr pppppppp 00000000 00000000  00000000  00000000 PPPPPPPP RNBQKBNR

It is not required to store anything except the location of the pieces, and validity of moves can be assumed.

Scoring

Base score is character count (assuming your program can move pieces for all moves)

Bonus multipliers:

  • If the program updates the promoted piece, divide by 2
  • If the program also moves the rook when castling, divide by 2
  • If the program also removes the pawn when capturing en passent, divide by 2

The moves, and castling & en passent in particular are explaned on Wikipedia.

So basically writing a 100 character solution for the base problem gives the same score as an 800 character solution with all bonus multipliers.

Examples

If you would choose to use one of the board formats above, your input would look like one of these strings:

e2e4 rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR

e2e4 rnbqkbnr pppppppp 00000000 00000000  00000000  00000000 PPPPPPPP RNBQKBNR

Your corresponding output string would then be one of these:

rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR

rnbqkbnr pppppppp 00000000 00000000  0000P000  00000000 PPPP0PPP RNBQKBNR
\$\endgroup\$
  • 1
    \$\begingroup\$ Before I get on to more specific criticisms: as presented, without the bonus this is too trivial to be interesting. I suggest removing some flexibility: require Fen notation for the board position and algebraic notation for the move, and making the current bonus options mandatory. On specifics: it's not clear why you talk about storage; and the board position notations you suggest don't include enough information to know whether en passant is possible. \$\endgroup\$ – Peter Taylor Dec 22 '13 at 23:56
  • \$\begingroup\$ @PeterTaylor I agree that compared to chess programs this may be trivial, but I would like to make it a golf challenge. Compared to the hot code golf questions this is quite elaborate already in its basic form. (For a good solution the board design may need to be changed drastically). It is true that there is no attention to the legality of moves (whether it is possible to capture en passent) but for a mere viewer this is not required so I am not too worried about this. So far the chess questions seem to get very few answers as they tend to be complex and I hope to offer relatively easy entry. \$\endgroup\$ – Dennis Jaheruddin Dec 30 '13 at 11:02
  • 2
    \$\begingroup\$ Your point about en passant is valid - you had said in the spec to not worry about legality. I'll try to convince you of my first point: without the bonus, this reduces to: a) parse first four characters into (col 1, row 1, col 2, row 2); b) take board as a 64-char string; c) board[8*row_2+col_2] := board[8*row_1+col_1]; board[8*row_1+col_1] := ' '; print board. This is trivial compared to any good golf question. (Note that the hot questions at the moment are neither golf questions nor good questions). \$\endgroup\$ – Peter Taylor Dec 30 '13 at 12:14
  • \$\begingroup\$ This sandbox post has had little activity in a while. Please improve / edit it or delete it to help us clean up the sandbox. Due to community guidelines, if you don't respond to this comment in 7 days I have permission to vote to delete this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 15:40
3
\$\begingroup\$

Black Box

Your task is to analyze a given situation for the game Black Box. Given a sequence of guesses and answers, your program is to either print the solution or suggest the next move.

The game

The board consists of 8×8 cells, with edges labeled like this:

I'll probably create nice images here, particularly to make sure that the squares of the board are really square.

 abcdefgh
i        I
j        J
k        K
l        L
m        M
n        N
o        O
p        P
 ABCDEFGH

The player shoots rays into the interior of the box, where they might get deflected, reflected or absorbed. He is told the position where the ray leaves the black box again, and from that has to deduce the positions of 4 atoms inside the black box.

I'll have to include more of the game rules here, but for now see Wikipedia.

Input and output

Input is a sequence of line, each consisting of two characters. The first denotes the point where the ray of light enters the black box, the second the place where it comes out again. In the case of a reflection, both characters will be equal. In the case of a hit, the second character will be -.

If the input is enough to fully determine the locations of the atoms, then output should be four lines giving the coordinates of each atom. The lines should be two lower case characters each, the first giving the row and the second giving the column of the found solution. The atom positions must be printed in lexicographical order.

If the input is consistent with more than one set of atom positions, then the output should consist of a single line containing a single character, which is the location where the next ray should be shot. That location has to be chosen in such a way that it can help find the solution. This is the case unless all of the atom positions consistent with the input so far would produce the same output for this next ray as well.

Your output has to be terminated by a newline character.

Examples

Let's take the atom configuration the Wikipedia article uses as an example as well:

 abcdefgh
i        I
j        J
k O    O K
l        L
m        M
n   O    N
o        O
p      O P
 ABCDEFGH

If the input were

cf
D-
Em
HH
Co

then the output should be

kb
kg
nd
pg

but if the input were only

Em
HH

then the output might be for example

K

Scoring

This is code golf, so shortest answer wins. However, I'll only accept answers which are practical in so far as they compute their result in reasonable time. I'd say no more than five minutes on my system where I'll evaluate the answers, and I'll simply hope that correct solutions will be much faster and incorrect ones much slower, so that the speed of my system doesn't make a difference. A submission which gives a wrong answer for one of my test cases will be disqualified until it gets fixed. I will probably point out the problem in a comment to that post.

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

Create a program with "exact repetition" in its source code

The task is to create a program, with the following restrictions placed on the printable ASCII characters in the source code: choose some k > 0.

  • Every non-alphabetic character has to appear exactly k times.
  • Every alphabetic character has to appear at most k times.
    • This rule differs from the former in order to avoid boring dummy identifiers while still making it a challenge to choose good library functions to call.

Character set definitions used:

  • Non-alphabetic characters are !"#$%&'()*+,-./0123456789:;<=>?@[\]^_{|}~ and '`' (backtick).
  • Alphabetic characters are ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.

Note that no restriction is placed on characters outside of the range of printable ASCII characters (including control codes, tabs, newlines, higher unicode codepoints, etc).

What the program does is up to you; be creative. Some general guidelines:

  • Programs that do something interesting might have better chances, although more impressive code structure (i.e. fewer comments) is also beneficial.
  • Stuffing excess characters in comments is boring, and should be avoided/is discouraged.
  • Dead/no-op code isn't terribly interesting either, but is probably unavoidable and at least has to conform to the language's grammar.

This is : whatever has the most upvotes at Feb 1, 2014 gets accepted as the winner.


Example answer (C)

#
#
/*$$@``*/_[]={9.};main() {printf("He%clo \
world!%c\
",2^7&!8.&~1|~-1?4|5?0x6C:48:6<3>2>=3<++_[0],'@'^79-5);}

Prints "Hello world!" (adapted from an answer to another question). Probably wouldn't score a lot (since what it does isn't terribly interesting). Each of the non-alphabetic characters appear exactly twice, and no alphabetic character appears more than twice.


For meta: I want to post this, but I'm worrying that "do something interesting" might give too little guidance and the question won't receive many answers.. thoughts? Is it good as-is, or should I come up with some task that one should be required to implement (and possibly change the ruling to code-challenge, with length + 2^(characters-in-comments) as the score)?

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

DIM, the DIM Integer Machine

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

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

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

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

Suppose the DIM has just produced an integer square: 81

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Efficient Testing for Armstrong Numbers

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

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

By contrast:

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

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

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

Winning Criteria

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

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

Amino Acids Matcher

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

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

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


Sample Input

TACTCGGATACT

Is split into

TAC, TCG, GAT, ACT

We now change each letter to its reciprocal

AUG, AGC, CUA, UGA

And print out the amino acids

Methionine, Serine, Leucine, Stop


This would probably be

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

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

Create a calendar

We all know HDD-space is precious and bandwidth is expensive, therefore it is best to reduce the size of your executables. Let's start with your calendar:

Your task is to build a calendar app in at most 512 bytes. The calendar must at least support the following features, but additional features may gain you additional upvotes:

  • It must be able to show the current month with the current day highlighted
  • The user must be able to find out the week day of each day

Rules:

  • Maximum code length is 512 bytes (counted as UTF-8 without BOM)
  • You may subtract the bootstrapping code (i.e. int main(int argc, char **argv) in C or <?php in PHP) and imports from the final size to allow for more verbose languages to be in
  • You may use standard time / date functions of your programming language, as long as they don't allow you to output a ready to use calendar
  • No network access (I said bandwidth is expensive!)
  • Voters decide on the amount of features / look and feel / creativity

This needs a tag for the size restriction, any suggestions?

\$\endgroup\$
  • 1
    \$\begingroup\$ "bandwidth is expensive" <sup>[citation needed]</sup> \$\endgroup\$ – John Dvorak Mar 22 '14 at 5:27
  • 1
    \$\begingroup\$ Seems rather close to Output: Calendar Month \$\endgroup\$ – Peter Taylor Mar 22 '14 at 5:33
  • \$\begingroup\$ Who decides what counts as bootstrapping code? It seems odd to arbitrarily exclude code like that, and the examples you gave can be golfed a lot: they're more or less equivalent to main(){ and <? respectively. \$\endgroup\$ – Wander Nauta Mar 24 '14 at 20:49
  • \$\begingroup\$ @WanderNauta Bootstrapping code is the code that's essentiell to get a working noop program. \$\endgroup\$ – TimWolla Mar 24 '14 at 21:00
  • \$\begingroup\$ @TimWolla That definition won't fly. A zero-byte file is a working noop PHP script, for example. \$\endgroup\$ – Wander Nauta Mar 24 '14 at 21:01
  • 1
    \$\begingroup\$ @WanderNauta A zero byte file is a working noop in every language. \$\endgroup\$ – TimWolla Mar 24 '14 at 22:12
  • \$\begingroup\$ So what's bootstrapping code then? :) \$\endgroup\$ – Wander Nauta Mar 24 '14 at 22:53
  • 1
    \$\begingroup\$ for the limit I'd say code-shuffleboard or restricted-source \$\endgroup\$ – Einacio Mar 26 '14 at 15:57
  • \$\begingroup\$ This sandbox post has had little activity in a while. Please improve / edit it or delete it to help us clean up the sandbox. Due to community guidelines, if you don't respond to this comment in 7 days I have permission to vote to delete this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 16:28
3
\$\begingroup\$

ASCII ART edge detection

As the title says, I was thinking to contest in which one must detect edges of an ASCII art.

The code should accept a B/W ASCII art as input. A B/W ASCII art is defined as (by me) an ASCII art with only one kind of non-white-spaces character (in our case: an asteriks *). And as output produce a standard ASCII art (all ASCII characters are accepted) which should remember the contourn of the first.

The purpose of using more than one character in the output is to make some edges ssmoother. For instance, one could let this input

     *** 
   ****
 ******
******
****** 
 ******
   ****
     ***

could became:

      ___
    _/   ) 
  _/    /
 /      |
|      /
|      \
 \      |
  `\     |
     \___)

The input \n separated string as input. Each line has a maximum of 80 characters. The number of rows is not specified.

I'd put it as a popularity-contest since, beside my simple code, I'd like to see more "round" edge detections which use more than one character in smooth edges.

Also, I don't want to tag it as code-golf since I'm quite sure one can do this job using aplay (with ASCII art renderer) and command line GIMP (to apply edge detection).

As a popularity contest, there are no strict rules on how the output should be..just use your fantasy!

This is my sample program:

import fileinput as f
import re as r
import copy as c
a,s,p='*',' ','+'
def read(n):
    s=[list(' '*n)]
    for l in f.input():
        if(len(l)>n):l=l[:n]
        k=list(r.sub('[^ ^\%c]'%a,'',' '+l+' '))
        s.append(k+[' ']*(n-len(k)))
    s.append([' ']*n)
    return s
def np(s):
    s=c.deepcopy(s)
    for l in s[1:-1]:
        for w in l[1:-1]: print(w,end='')
        print()
def grow(i):
    o=c.deepcopy(i)
    for x in range(1,len(o)-1):
        for y in range(1,len(o[x])-1):
            if(i[x][y]==a): o[x-1][y-1]=o[x-1][y+1]=o[x-1][y]=o[x+1][y]=o[x+1][y-1]=o[x+1][y+1]=o[x][y+1]=o[x][y-1]=a

    return o
def diff(i,o):
    c=[]
    for x in range(0,len(i)):
        l=[]
        for y in range(0,len(i[x])):
            if(i[x][y]==a and o[x][y]==s): l.append(p)
            else: l.append(s)
        c.append(l)
    return c
I=read(80)
np(diff(grow(I),I))

Here below I put both input of the programs. It is an 80x70 ASCII ART. It means it has 70 lines of 80 characters, each separated by \n.

                                              *************
                                          *****          *****                   
                                     ******                  ***                 
                                    ***                         ****             
                             *********                             **            
                          ***********                               **           
                     ******   *******                                **          
                 *****       *******      ***                         **         
              ****          ********     *****                          *        
             **            *********     *****                    *****  *       
           ***            *********     *******                  ******  **      
          **             **********     *******                  ******   **     
         **              **********    *******                  ********   *     
        *               ***********   ******                    ********   *     
       **              ************   *****                     ********    *    
       *               ************    ***                       ********   *    
      *               *************                               ******    *    
     *                *************                                 ***     *    
    **                *************                                         *    
    *                **************                                         *    
   **                *************                                         **    
   *                 *************                                         **    
  **                *************                                          ***   
 ***                *************                                          ****  
 **                 ************                                           ****  
 **                *************                                           ****  
 **                *************           *****                           ****  
 **                *************          **   **          **              ****  
 **                 ************          *     *         ** **            ****  
 *                  ************          **   **        **   **           ****  
 *                  *************        *******         **   ***          ****  
 *                  ************          *****           *******          ****  
 *                   ************         ***               *****          ****  
**     *             *************                          ****          *****  
**    ***            **************                                      *****   
*    *****            *************                                     ******   
** *******             **************                                  *******   
**********             ***************              *                *********   
**********              *****************          ***             ***********   
***********              *******************                    **************   
***********               **********************            ******************   
************              *****************     **     ***********************   
*************             ******************      ****     *******************   
**************            ******************              ********************   
****************           ******************              *******************   
***************           *******************              *******************   
****************           ******************              ******************    
******************         ******************             *******************    
*******************         *****************             *******************    
*********************      ******************           ********************     
*********************************************          *********************     
**********************************************       ***********************     
************************     *****************      ************************     
 **********************       ******************* **************************     
 *********************        *********************************************      
 *********************        ****************************  ***************      
 ********************         **************************    ***************      
 ********************         *********************         ***************      
 *******************          ********************         ****************      
 ******************           *****************            ****************      
 *****************             ****************            ***************       
 *****************             ****************            ***************       
 *****************             *****************           ***************       
  ****************             *****************           ***************       
   **************              ******************          ***************       
                                 ****************          ****************      
                                  **************            ***************      
                                                             **************      
                                                              ************       

A possible output could be:

                                         +++++             ++++
                                    ++++++     ++++++++++     +++
                                   ++      +++++        +++++   +++++
                            ++++++++   +++++                ++++    ++
                         ++++         ++                       ++++  ++
                    ++++++           ++                           ++  ++
                +++++      +++       +   +++++                     ++  ++
             ++++     +++++++       ++  ++   ++                     ++  ++
            ++    +++++   ++        +   +     +                  +++++++ ++
          +++  ++++      ++         +  ++     ++                ++     ++ ++
         ++   ++        ++         ++  +       +                +      ++  ++
        ++  +++         +          +  ++       +               ++      +++  +
       ++  ++          ++          + ++       ++               +        +++ +
      ++ +++          ++           + +      +++                +        + + ++
      +  +            +            + +     ++                  +        ++++ +
     ++ ++           ++            + ++   ++                   ++        + + +
    ++ ++            +             +  +++++                     ++      ++ + +
   ++ ++             +             +                             +++   ++  + +
   +  +             ++             +                               +++++   + +
  ++ ++             +              +                                      ++ +
  +  +              +             ++                                      +  +
 ++ ++             ++             +                                       +  ++
++  +              +             ++                                       +   ++
+   +              +             +                                        +    +
+  ++             ++            ++                                        +    +
+  +              +             +         +++++++                         +    +
+  +              +             +        ++     ++        ++++            +    +
+  +              +             +        +  +++  +       ++  +++          +    +
+  +              ++            +        + ++ ++ +      ++  +  ++         +    +
+ ++               +            ++      ++  +++  +      +  +++  ++        +    +
+ +                +             +      +       ++      +  +++   +        +    +
+ +                +            ++      ++     ++       ++       +        +    +
+ +   +++          ++            ++      +   +++         +++     +       ++    +
  +  ++ ++          +             ++     +++++             +    ++      ++     +
  + ++   ++         +              +                       ++++++      ++     ++
 ++++     +         ++             +++                                ++      +
  +       +          ++              ++            +++              +++       +
          +           +               ++++        ++ ++           +++         +
          ++          ++                 ++++     +   +        ++++           +
           +           ++                   +++++ +++++    +++++              +
           ++           ++                      +++   ++++++                  +
            ++           +                 +++++  +++++                       +
             ++          +                  +  +++    +++++                   +
              +++        +                  ++   ++++++  +                    +
                +        ++                  +           ++                   +
               ++        +                   +            +                   +
                +++      ++                  +           ++                  ++
                  ++      +                  +           +                   +
                   +++    ++                 +         +++                   +
                     ++++++                  +        ++                    ++
                                             ++     +++                     +
                                              +    ++                       +
                        +++++                 ++++++                        +
+                      ++   ++                   +                          +
+                     ++     +                                             ++
+                     +      +                            ++               +
+                    ++      +                          ++++               +
+                    +       +                     ++++++ ++               +
+                   ++       +                    ++      +                +
+                  ++        +                 ++++       +                +
+                 ++         ++                +          +               ++
+                 +           +                ++         +               +
+                 +           +                 +         +               +
++                +           +                 ++        +               +
 ++              ++           +                  +        +               ++
  ++++++++++++++++            +++                +        +                +
                                ++              ++        ++               +
                                 ++++++++++++++++          ++              +
                                                            ++            ++
                                                             ++++++++++++++

This is also the output produced by the script above. Of course it is not the best output and I'm sure one can easily produce a smoother one.

\$\endgroup\$
  • 1
    \$\begingroup\$ It would be useful to be more precise about which characters should be non-blank in the output: characters which were non-blank in the input but adjacent to blanks, or characters which were blank in the input but adjacent to non-blanks? \$\endgroup\$ – Peter Taylor Apr 4 '14 at 9:50
  • \$\begingroup\$ Thanks for pointing. I re-written the phrase in the answer. You can use every ASCII character in the output (as usual ASCII art). E.g. I used only + symbol, but one could makes round edges using symbols like \ or / etc.. \$\endgroup\$ – Antonio Ragagnin Apr 4 '14 at 9:55
  • \$\begingroup\$ edited again... \$\endgroup\$ – Antonio Ragagnin Apr 4 '14 at 10:09
  • \$\begingroup\$ Can you define the input that will be used by all the participants? It's necessary to have only one input to compare the outputs of the different answers. The first example is too simple and the last one is too long. So I suggest to use something between these 2 examples. \$\endgroup\$ – A.L Apr 4 '14 at 17:29
  • \$\begingroup\$ Thanks, I chosen a cute panda as input. \$\endgroup\$ – Antonio Ragagnin Apr 6 '14 at 8:09
  • 1
    \$\begingroup\$ one could let this input (…) could became → try something like "this input (…) could become" outpuit → output \$\endgroup\$ – user2428118 Apr 7 '14 at 13:31
  • \$\begingroup\$ I edited it now, so do you people thinks it is a good question? \$\endgroup\$ – Antonio Ragagnin Apr 9 '14 at 17:15
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption? (If you want to, you can still post to main.) Due to community guidelines, if you don't respond to this comment in 7 days I have permission to adopt this. \$\endgroup\$ – programmer5000 Jun 9 '17 at 16:32
  • \$\begingroup\$ Hi @programmer5000 , I already asked such a question. Do you mean to re-use it again? See: codegolf.stackexchange.com/questions/26139/… \$\endgroup\$ – Antonio Ragagnin Jun 12 '17 at 13:39
3
\$\begingroup\$

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

Maths Trade Calculator

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

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

Input

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

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

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

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

Output

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

1->3->1
2

Participants for which no valid trade is possible are omitted.

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

Trade rules

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

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

Some more example inputs and possible outputs

1

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

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

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

2

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

0

3

1:5,9
5:1
9:1

1->5->1
2

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

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

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

You must log in to answer this question.

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