459
\$\begingroup\$

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

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

2565 Answers 2565

8
\$\begingroup\$

Array Pattern Matching Language

Everyone is (or should be) acquainted with the ways of the regular expression. At its core, a regex is made for matching strings. However, it's just matching something, right? Why not match arrays? That would be something!

Description

Your task now is to design and implement a new numeric array pattern-matching language. The only requirement is that your created language satisfies the mandatory tasks detailed below. However, this being a popularity contest, you may wish to opt for the bonus tasks and maybe even some competitive golfing value.

To be more precise, your language should be able to take patterns and match them against arbitrary arrays of integers. They should minimally be used to determine whether or not an array matches the pattern. This can be done by return a boolean, two different strings, etc.

Voting

As a voter, you should keep in mind the criteria mentioned, and ask yourselves these questions:

  1. Is the language trivial? That is, is there a lot that can be done other than the detailed tasks, or is the language minimally designed for these tasks?
  2. Is it well described? Does the author explain the solutions and the concept behind the language?

Tasks

(Thanks to Nathan Merrill for a lot of tasks!) Note that, for each task, the empty array can go in either category, unless otherwise stated.

1. That's odd!

Write a program in your language that will match the input array if all of its members are odd; otherwise, do not match.

MATCH
 [1, 3, 5, 11, -1]
 [5, 9, 1023, 3243]

NOT MATCH
 [2, 1, 3, 4]
 [0, 5, 6, 0]

2. Increasing in membership

Match an array that has each member more than the previous member.

MATCH
 [0,1,2,3]
 [2,5,100,203123]
 [-432,-421,123,322]

NOT MATCH
 [0,0,1,2]
 [-2,3,-3]
 [1,3,2]

3. Bodyguards

Match only arrays with a 0 on both sides.

MATCH
 [0, 1, 2, 0]
 [0, 5, 0]
 [0, 0]
 [0]

NOT MATCH
 [1, 2, 3]
 [4, 5]
 [99]

4. Mountain

Match all arrays of the form [1, 2, 3, ..., N-2, N-1, N, N-1, N-2, ..., 3, 2, 1], for any N.

MATCH
 [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]
 [1, 2, 3, 4, 3, 2, 1]
 [1, 2, 1]
 [1]

NOT MATCH
 [1, 2, 4, 8, 4, 2, 1]
 [3, 4, 5, 4, 3]
 [3, 2, 1, 2, 3]
 [2, 1, 1]

5. Shifting, 1 to 5

Match only arrays that consist of the numbers 1, 2, 3, 4, 5, 4, 3, 2 "in order", where the elements can be rotated around the array.

MATCH
 [1, 2, 3, 4, 5, 4, 3, 2]
 [2, 3, 4, 5, 4, 3, 2, 1]
 [5, 4, 3, 2, 1, 2, 3, 4]

NOT MATCH
 [1, 2, 3, 4, 5, 3, 2, 4]
 [2, 3, 4, 5, 2, 3, 4, 1]
 [1, 2, 3, 4, 5, 2, 3, 4]
 [1, 2, 3]
 [2]
 []

6. Not in my prime

Match an array if and only if all of it's members are not prime.

MATCH
 [4, 6, 8, 9, 24]
 [20, 40, 42, 45]
 [1, 10, 100]
 []

NOT MATCH
 [1, 100, 200, 300, 400, 401]
 [2, 3, 4]
 [2, 4, 8]
 [3, 5, 7]
 [2]

7. Unique

Match only arrays that contain no duplicates.

MATCH
 [1, 2, 3, 4]
 [5, 15, 25]
 [21]
 []

NOT MATCH
 [3, 4, 5, 3]
 [10, 11, 10, 13]
 [2, 2]

8. Not close

Match only arrays that, for each member N, do not also have a member N+1.

MATCH
 [1, 3, 45, 30]
 [20, 23, 26]
 []

NOT MATCH
 [200, 201, 202]
 [3, 9, 100, 4]
 [2, 4, 5]
 [0, 1]

9. Arithmetic Progression

Match only arrays that are arithmetic progressions; i.e. there elements increase by a constant factor. (Singletons may go either way.)

MATCH
 [2, 6, 10, 14]
 [5, 10, 15, 20]
 [20, 19, 18]
 [1, 2, 3]
 [5, 6, 7, 8]

NOT MATCH
 [5, 25, 125]
 [2, 6, 5]

10. Fibonacci-esque

Match only arrays (of length greater than 2) where each element is the sum of the previous two (not counting the first 2), and match all arrays of length 2.

MATCH
 [100, 1, 101, 102, 203, 305, 508, 813]
 [-5, 5, 0, 5, 5, 10, 15, 25, 40]
 [2, 1, 3, 4, 7, 11]
 [0, 0, 0, 0, 0, 0]
 [1, 0, 1, 1, 2]
 [1, 2, 3, 5]
 [10, 2]

NOT MATCH
 [5, 10, 15, 20, 25]
 [91, 32, 32]
 [5, 5, 5]
 [2]
 []

11. Self-descriptive

Match arrays that contain their lengths.

MATCH
 [1]
 [12, 2]
 [4, 3, 2]

NOT MATCH
 [0]
 []
 [123, 122, 121]
 [0, 2, 4, 6, 8]

12. Palindrome

Match all palindromic arrays. That is, arrays that are the same when reversed.

MATCH
 [1]
 []
 [2, 3, 4, 3, 2]
 [-1, -1]

NOT MATCH
 [3, 4, 2, 0]
 [0, 0, 0, 1]
 [1, 11]

13. Kth element at most K

(You can use 1-based or 0-based indexing. I will give test cases for 0-based indexing.)

Match all arrays whose Kth element is at most K.

MATCH
 [0, 0, 2]
 [0, 0, 0, 1]
 [-4, -1, 0]

NOT MATCH
 [2, 42]
 [-4, -92, 4]

14. Twins

Match all arrays of even length whose first half is equal to the second half.

MATCH
 [1, 2, 3, 1, 2, 3]
 [4, 4]
 [0, 0, 0, 0]

NOT MATCH
 [4, 9, 9, 4]
 [9, 2, 13, 2, 9]
 [1, 2, 3, 1, 2]

15. A simplified date

Match all 3-element arrays which constitute a valid date. The array will be [year, month, day]. That is, year >= 0, 1 <= month <= 12, and 1 <= day <= 31.

MATCH
 [2018, 6, 16]
 [1990, 1, 1]
 [0, 6, 31]
 [3014, 7, 13]
 [1293, 9, 9]
 [12, 12, 12]

NOT MATCH
 [-4, 12, 9]
 [100, 100, 4]
 [1929, 13, 31]
 [4102, 12, 32]
\$\endgroup\$
  • \$\begingroup\$ I look forward to the answers for this as I would like to have a generalized regex feature in Pytek. :D \$\endgroup\$ – El'endia Starman Feb 9 '16 at 20:23
  • \$\begingroup\$ [] is a match for "all members are odd". \$\endgroup\$ – Peter Taylor Feb 9 '16 at 20:37
  • \$\begingroup\$ @PeterTaylor Ah right, drinker's fallacy. \$\endgroup\$ – Conor O'Brien Feb 9 '16 at 22:22
  • \$\begingroup\$ Can the input be in unary? \$\endgroup\$ – Downgoat Feb 9 '16 at 23:33
  • \$\begingroup\$ @Downgoat That would hardly be interesting, I don't see why not, but it'd be hardly useful and largely unable to compensate for negative numbers. \$\endgroup\$ – Conor O'Brien Feb 9 '16 at 23:34
  • \$\begingroup\$ Some of the tasks seem to use matching in the sense of a regex: the array as a whole either matches or does. Others seem to describe a filter, where the individual elements of the array are matched or not and the matched ones are output. If this is intentional, it would be good to mention it in the Description section. \$\endgroup\$ – Peter Taylor Feb 11 '16 at 16:06
  • \$\begingroup\$ I really like the concept of this challenge. However, I'd recommend standardizing your test cases: 1. Make your regex an all/nothing match (as Peter Taylor explained). 2. Ensure that your array only contains integers (no matrices). Then, adding more test cases would be fantastic. \$\endgroup\$ – Nathan Merrill Feb 11 '16 at 20:52
  • 2
    \$\begingroup\$ Possible test cases: Match if each 0 has a positive integer on both sides. Match the array [1,2,3,...N-1, N, N-1, N-2...3,2,1]. Match the array [1,2,3,4,5,4,3,2] and [2,3,4,5,4,3,2,1] and [3,4,5,4,3,2,1,2] and so on. Match an array with only unique elements. Match an array that doesn't contain both an N and an N+1. Match the fibonacci sequence with an arbitrary first two numbers. Match if all of the numbers aren't prime. \$\endgroup\$ – Nathan Merrill Feb 11 '16 at 21:11
  • \$\begingroup\$ Some task ideas (although you seem to have quite many already): Palindromic arrays. Even-length arrays whose first half equals second half. Arrays whose kth element is at most k. Arrays that contain their length as an element. \$\endgroup\$ – Zgarb Jun 22 '16 at 18:05
  • \$\begingroup\$ @Zgarb on the first half equals second half, do you mean arrays like [1, 2, 1, 2]? \$\endgroup\$ – Conor O'Brien Jun 22 '16 at 19:22
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ Yes, exactly. \$\endgroup\$ – Zgarb Jun 22 '16 at 20:58
  • \$\begingroup\$ It seems all the elements are integers and not floats. If that's the case,, you should say so. I think "Is the language trivial?" would be better stated positively, saying that the language constructs are powerful in general, not just tailored to the examples given. \$\endgroup\$ – xnor Oct 4 '16 at 1:22
  • 1
    \$\begingroup\$ It seems to me that such a language already exists--it's called Jelly. ;) (And APL, and J.) Wisecracking aside, there are two serious points I want to make: 1) What do you expect submissions to bring to the table that existing languages don't have? Why design a language for this set of tasks when it's essentially already been done? 2) In any case, you should stipulate in the question that submissions must be new languages created specifically for this challenge. \$\endgroup\$ – DLosc Oct 4 '16 at 7:48
  • \$\begingroup\$ @DLosc I'm thinking of a regular expression language, so it should be somewhat similar to regex. How might I define that in a strict sense? \$\endgroup\$ – Conor O'Brien Oct 5 '16 at 2:49
  • \$\begingroup\$ Well, you could read up on regular languages, but I suspect that isn't what you want, since several of your tasks can't be matched by a regular language. (Unique, self-descriptive, and twins, e.g.) Instead, you may be looking for a declarative language, though that still isn't a really "strict" category and you'd have to further specify what you mean by declarative. \$\endgroup\$ – DLosc Oct 5 '16 at 4:41
8
\$\begingroup\$

🎲🎲Lucky Dice (KotH, WIP)🎲🎲

CHATCONTROLLER

You have recently taken a job at Lucky & Co, as a professional dice roller, and need to make as much money as you can! (of course). You will be paid exactly what you roll, $1 for a 1, $2 for a 2 etc. Where's the fun in that? Well, these aren't ordinary dice: starting with $5 in your bank, you must purchase new dice, which will all be rolled each turn. There are many different types of dice, all with different probabilities of rolling the different numbers. Every turn, you take a look at what the dices have done for you, then decide what to invest in. But beware! You have many rivals, all with the same aim in mind, and there are only so many dice in the shop...

The Dice (StC)

There are many types of dice, which can be split into the following categories:

Basic Earners

20 of each are available, they are simply rolled and their value is added to the total points:

╔════╦═════════════════════╦═══════╦═════╦════╦════╦════╦════╦═════╗
║ ID ║     Description     ║ Price ║  1  ║ 2  ║ 3  ║ 4  ║ 5  ║  6  ║
╠════╬═════════════════════╬═══════╬═════╬════╬════╬════╬════╬═════╣
║  0 ║ Rolls a 1           ║     1 ║ 100 ║  0 ║  0 ║  0 ║  0 ║   0 ║
║  1 ║ Likely to be low    ║     3 ║  50 ║ 25 ║ 13 ║  7 ║  3 ║   2 ║
║  2 ║ Unlikely to be high ║     6 ║  22 ║ 22 ║ 22 ║ 11 ║ 11 ║  11 ║
║  3 ║ Even chances        ║     9 ║  17 ║ 17 ║ 17 ║ 17 ║ 17 ║  17 ║
║  4 ║ Unlikely to be low  ║    12 ║  11 ║ 11 ║ 11 ║ 22 ║ 22 ║  22 ║
║  5 ║ Likely to be high   ║    16 ║   2 ║  3 ║  7 ║ 13 ║ 25 ║  50 ║
║  6 ║ Rolls a 6           ║    21 ║   0 ║  0 ║  0 ║  0 ║  0 ║ 100 ║
╚════╩═════════════════════╩═══════╩═════╩════╩════╩════╩════╩═════╝

Multipliers

These multiply the points gained by the basic dice by something between 0.33 and 18... 10 of each are available. r represents what it rolled, each outcome (1-6) is equally likely:

╔════╦═════════════════╦═══════╗
║ ID ║   Description   ║ Price ║
╠════╬═════════════════╬═══════╣
║  7 ║ Multiply by r/3 ║    10 ║
║  8 ║ Multiply by r/2 ║    13 ║
║  9 ║ Multiply by r   ║    22 ║
║ 10 ║ Multiply by r*2 ║    34 ║
║ 11 ║ Multiply by r*3 ║    50 ║
╚════╩═════════════════╩═══════╝

Attacks

These dice, with 10 of each available, are what makes the game truly interesting. They handle user interaction: each has a set action that it applies to one other random player (except 16):

╔════╦══════════════════════════════════╦═══════╗
║ ID ║              Action              ║ Price ║
╠════╬══════════════════════════════════╬═══════╣
║ 12 ║ See below (too long)             ║    35 ║
║ 13 ║ They get 10 less (not below 0)   ║    45 ║
║ 14 ║ Like 12, but you get the points  ║    60 ║
║ 15 ║ They get 25 less (not below 0)   ║    60 ║
║ 16 ║ Like 14, but you get the points  ║    90 ║
╚════╩══════════════════════════════════╩═══════╝

12: A fair dice, the value of which is subtracted from every other users' basic dice roll (not below 0).

Coins

Miscellaneous other bonuses and actions, each with a 50% chance of happening. There are only 3 of each available:

╔════╦═══════════════════════════════════════════╦═══════╗
║ ID ║                Description                ║ Price ║
╠════╬═══════════════════════════════════════════╬═══════╣
║ 17 ║ Protects you from attacks                 ║    65 ║
║ 18 ║ Roll every basic die again                ║    90 ║
║ 19 ║ Roll every basic and multiplier die again ║   110 ║
║ 20 ║ Square your score                         ║   120 ║
║ 21 ║ Cube your score                           ║   170 ║
╚════╩═══════════════════════════════════════════╩═══════╝

How the dice fall

When working out the points for a round:

  • Every players' coins are flipped. The results are remembered.
  • Every players' basic dice are rolled (as many times as specified by coins). The total of the results for each player is that players' points for this round
  • Every players' multiplier dice are rolled (with extra rolls). Each multiplication is applied on top of the previous one.
  • Any squaring or cubing is applied.
  • For every players' attack dice, a random other player is chosen for each. Unless that player had a shield, the appropriate action is taken.

A game

A game lasts until first place is 200 points ahead of second place, or until 500 rounds have been played. There are 7 people in each game, who each start with just $5. Every round, each player submits a list of dice that they want to buy. If they ask for a dice that isn't there, ask to pay more than they have, or returns an otherwise invalid move, they do not buy anything that round. If more people ask for a dice than there are of that dice, no-one gets it. After every bot has given their move, and all orders have been resolved, the points for the round are calculated as above, and then added to the total score of each bot. At this point, the win condition is tested. 1st place gets 7 points, second gets 6 and so on. If two players are joined in, for example, 3rd place, they both get 5 points, but the next bot/s get only 3.

A tournament

In a tournament:

  1. If there are more than 7 bots, the bots will be divided into groups of 7 to play until every bot has played an equal number of games, and there are 7 bots which have a higher total score than the rest.
  2. The top 7 bots play games until one has 50 more points than second place.
  3. 2 is repeated for all the other groups of seven, and then the leftover bots. Now every bot knows its rightful place!

I will run a tournament every day if possible, which it hopefully will be.

Coding

You will write a Python class that inherits from Bot, and implements get_orders, which must accept the following parameters:

  • money - how much money each player has (a tuple of ints)
  • dice - what dices each player has (a tuple of tuples of ints)
  • index - your index in the money and dice tuples (an int)`
  • shop - how many of each dice the shop has (a dict of int: int pairs)

Dice are represented in the above by their ID. You may also implement __init__ (self, random), where random is a random.Random object, which is the only access to randomness that you are allowed, that is, if I were to run your code again with the same argument to random and the same calls to get_orders, I would receive the same results. You may also implement any other utility functions you wish. You may not store information between games (already banned but let's do it explicitly), and you may not mess with the controller. You may not team up (how could you?) or use any other competitor's code without significant changes without their permission. You may not programmatically invoke another competitor's code, because that could get circular...

Controller

WIP

Results

None yet ;P

Sandbox

  • Any thoughts?
  • What should I clarify, I feel like I've missed everything...
  • Do you like the idea?
  • Have you spotted a perfect and unbeatable strategy?
  • Any suggestions for new dice/dice types?
  • Any suggestions for changes to the game/tournament system?
  • Are all the tags appropriate?

    Unicode Art Table

╔════╦═══════════════════════════════════════════╦═══════╗
║ ID ║                Description                ║ Price ║
╠════╬═══════════════════════════════════════════╬═══════╣
║ 16 ║ Protects you from attacks                 ║    65 ║
║ 17 ║ Roll every basic die again                ║    90 ║
║ 18 ║ Roll every basic and multiplier die again ║   110 ║
║ 19 ║ square your score                         ║   120 ║
║ 20 ║ cube your score                           ║   170 ║
╚════╩═══════════════════════════════════════════╩═══════╝

MathJax Table

\begin{array} {|r|r|} \hline \text{ID} &\text{Description} &\text{Price} \\ \hline \text{16} &\text{Protects you from attacks} &\text{65} \\ \text{17} &\text{Roll every basic die again} &\text{90} \\ \text{18} &\text{Roll every basic and multiplier die again} &\text{110} \\ \text{19} &\text{Square your score} &\text{120} \\ \text{20} &\text{Cube your score} &\text{170} \\ \hline \end{array}

Which is better?

\$\endgroup\$
  • 1
    \$\begingroup\$ Upvote this comment for MathJax tables. \$\endgroup\$ – Artemis Fowl Apr 22 at 11:34
  • 5
    \$\begingroup\$ Upvote this comment for Unicode art tables. \$\endgroup\$ – Artemis Fowl Apr 22 at 11:35
  • \$\begingroup\$ In your "Attacks" table, you want "halve their score" instead of "half their score." \$\endgroup\$ – AdmBorkBork Apr 22 at 12:43
  • \$\begingroup\$ I have given suggestions in the chat room \$\endgroup\$ – Beefster Apr 22 at 17:28
  • \$\begingroup\$ "A game lasts until first place is 50 points ahead of second place, or until 200 rounds have been played." Nobody will ever buy the big dice with this rule in play. \$\endgroup\$ – Beefster Apr 22 at 17:29
  • \$\begingroup\$ @Beefster Been running a few tests... I bot that just buys all the ID: 0 (roll-a-one) dice gets 20 per turn, and over 200 turns that's 4000 points. A few less to allow for the time it takes to buy them, and of course other bots will be playing, but still... I'll be thinking about it, and the "first place is 50 points ahead of second place" is definitely wrong. \$\endgroup\$ – Artemis Fowl Apr 25 at 14:31
  • \$\begingroup\$ Why not just cut out the "way ahead" end condition and just make it a constant number of rounds? \$\endgroup\$ – Beefster Apr 25 at 17:02
  • \$\begingroup\$ @Beefster The idea was that it should end with the way ahead condition, but the round limit prevents it from going on forever. I'm not sure about that anymore though. \$\endgroup\$ – Artemis Fowl May 2 at 14:18
8
\$\begingroup\$

Round away from zero

Submitted.

Inspired by Round towards zero.

Given a number input via any reasonable method, round the number "away from zero" - positive numbers round up, and negative numbers round down.

You can output a floating-point number with the decimal point (e.g. 42.0) if desired.

why did i think this was a good idea

Test cases

-99.9 => -100
-33.5 => -34
-7    => -7
-1.1  => -2
0     => 0
2.3   => 3
8     => 8
99.9  => 100
\$\endgroup\$
  • \$\begingroup\$ It's a great idea, because truncation-based methods from the original won't work quite as well, but there's still plenty of room to be clever. \$\endgroup\$ – Unrelated String Aug 26 at 23:58
  • 2
    \$\begingroup\$ I'm not certain if this is a dupe, since most answers to this can be an answer from the inspiration but with +sign(input) tacked on. I think that may be competitive in too many languages. \$\endgroup\$ – FryAmTheEggman Aug 27 at 15:03
  • 3
    \$\begingroup\$ @FryAmTheEggman Actually, that solution would give incorrect answers for all integers except 0. \$\endgroup\$ – Joel Aug 27 at 23:02
  • \$\begingroup\$ The test case inputs may have a better coverage for all cases: [-99.9, -5, -2.0, -1.1, 0, 0.0, 1.1, 2.0, 5, 99.9]. \$\endgroup\$ – Joel Aug 27 at 23:27
  • \$\begingroup\$ @Joel That is true, and I guess also adding a check for being an integer is probably different enough in most languages? I'll leave my comment in case another similar problem emerges but it is likely that someone will make the same mistake I do, so it may be a good idea to specifically say this won't work in the challenge. \$\endgroup\$ – FryAmTheEggman Aug 28 at 0:30
  • \$\begingroup\$ @FryAmTheEggman brings up a good point though, what's stopping people from doing something like +sign(input%1) to trivialize the challenge? Maybe I shouldn't post this after all \$\endgroup\$ – Value Ink Aug 28 at 21:35
  • \$\begingroup\$ @Value Ink The outcome of the modulo operation varies in different programming languages when a negative number is involved (see the big table at the right side of the wiki page). Your solution can only give correct answers in some languages. This is actually a good task to make people aware of that. By the way, the first and third test cases yield wrong results. \$\endgroup\$ – Joel Aug 29 at 3:20
  • 1
    \$\begingroup\$ I really like this challenge. It is very easy to understand and the implementation is not as trivial as it initially seems. I do think that you should include some non-decimal test cases like @Joel suggested, such as -5 and 5. \$\endgroup\$ – Jitse Aug 29 at 8:10
  • \$\begingroup\$ @Jitse won't that be hard for people whose languages are strongly typed or something? Although I guess they can just do -5.0 anyways. Ok, I've changed them. \$\endgroup\$ – Value Ink Aug 30 at 0:15
  • \$\begingroup\$ You may add a note saying that the returned answer can be a float (like 5.0) or an integer. \$\endgroup\$ – Joel Aug 30 at 1:42
  • \$\begingroup\$ @Joel good idea. Thanks for the tip \$\endgroup\$ – Value Ink Aug 30 at 2:02
  • \$\begingroup\$ I just wonder, is it appropriate for me to post solutions after getting involved in improving the challenge? \$\endgroup\$ – Joel Aug 30 at 2:47
  • 2
    \$\begingroup\$ @Joel I'm not sure (I assume it's fine), but if the dilemma is nagging you I think it's best if asked as a separate meta post and not as a comment in here... \$\endgroup\$ – Value Ink Aug 30 at 2:58
  • \$\begingroup\$ Now that this has been posted, it would be best to delete it, to free up space \$\endgroup\$ – caird coinheringaahing Sep 4 at 9:07
7
\$\begingroup\$

Objection!


In the near future, the legal world is crumbling. If a case lasts longer than three days, the defendant is assumed to be guilty. Prosecutors create false evidence to get their guilty verdict or flawless record. Defense attorneys are forced to retaliate, claiming that the ends justify the means. In the trials and tribulations of the courtrooms of tomorrow, how will we ever get justice for all? This truly is the dark age of the law.

Luckily, the world has you. Just 11 short years ago, you were a ragtag rookie lawyer in a world of big fish, but you had potential and it showed. You always trusted your client, no matter how bad things looked. You were able to cut through the deception and reach the truth. When times got hard, you forced your biggest smiles. Of course, it was only 3 years before a little misunderstanding cost you your badge, but that's all cleared up now. You're back, ready to protect those no one else will and make miracles happen.

Except... You're pretty sick. For some reason you can't quite remember, you've got a crippling fear of cold medicine. Clearly, you're in no position to stand at the bench. If you can't be there to clear your client's name, you'll have to write a program to do it for you!


For this challenge, you'll be writing a program that can take your place in a cross-examination. There are three different things you need to keep track of: Facts, Evidence, and Statements.

  • Facts
    • There are 26 Facts, named A, B, C... Y, Z. Usually, only a small number of them will be relevant, but you must be able to handle all of them if necessary. Contrary to their name, a Fact can be either True or False.   You are never told the Facts, but you can figure them out from your...
  • Evidence

    • Evidence is the most important thing for you to have, because it's how you know the Facts. You could make the case* that Evidence is everything in court. Pieces of Evidence have a name and a description of their relevance to the Facts. Evidence comes in two flavours: Direct and Circumstantial. Direct Evidence proves a Fact, while Circumstantial Evidence proves a fact if and only if a condition is met.   You get your Evidence as input in this format:

      Direct Evidence
      Name of evidence: [Fact] is <true/false>.
      
      Circumstantial Evidence
      Name of evidence: If [Fact] is <true/false>, then [Fact] is <true/false>.
      
  • Statement

    • A Statement is a declaration of Fact by a witness. There are also two kinds of Statements: Absolute and Conditional. An Absolute Statement claims a Fact, while a Conditional Statement claims a Fact if and only if a condition is met. Statements are taken as input in the same format as the second half of a piece of Evidence.

Your job is to analyze your Evidence to determine the Facts, then try to find contradictions in the Statements.

A Statement can contradict either an earlier Statement or a piece of Evidence. If a Fact is proven to be True or False and the witness claims the opposite, that is a contradiction. Note that If A is true, then B is true. and If A is true, then B is false. do not contradict unless A is true.

Input

Input comes from either stdin or a file, in exactly this format:

Evidence
<One or more pieces of Evidence on their own lines>
Testimony
<One or more Statements on their own lines>

Output

If there is a contradiction between a proven fact and something the witness claims, you must find the first Statement that contains the contradiction. If it contradicts the Evidence, output this:

Objection! Statement n contradicts this piece of evidence:

followed by a space and the name of the contradicted Evidence. n is replaced with the number of the contradicting Statement (starting at 1). If, instead, the witness contradicts themselves, output this:

Objection! Statement n contradicts statement m.

n is replaced with the number of the contradicting Statement and m is the number of the contradicted Statement (both starting at 1. m < n).

If there are no contradictions, output this instead:

No objections, Your Honor.

Examples

Input:

Evidence
My badge: L is true.
Thinker Clock: C is true.
Receipt: If C is true, then W is false.
Testimony
A is true.
B is false.
If A is true, then W is true.
H is true.
C is false.

Output:

Objection! Statement 3 contradicts this piece of evidence: Receipt

Input:

Evidence
Metal detector: B is true.
Testimony
If B is true, then A is true.
A is false.

Output:

Objection! Statement 2 contradicts statement 1.

Input:

Evidence
Stuffed animal tail: N is false
Testimony
A is true.
N is false.

Output:

No objections, your honor.

Assumptions

  • The Evidence will never contradict itself. Evidence is infallible.
  • There will never be a logic loop (e.g. If A is true, then B is true., If B is true, then A is true.)

* If you know what I mean

\$\endgroup\$
  • \$\begingroup\$ Objection! According to the first example, If A is true, then B is false is equivalent to If A is false, then B is true, however this would cause the statement about contradictions incorrect. More detail on the first example: C is false, so the assertion from the Receipt doesn't apply; W is true, since A is true. \$\endgroup\$ – cjfaure Jun 4 '14 at 16:59
  • \$\begingroup\$ Hold it! The Thinker Clock found at the scene proves that C is true! Since we know C is true, the Receipt shows that W is false! The witness claims that A is true in the first line of their testimony, but then says that if A is true, W has to be true! By indirectly claiming that W is true, their testimony contradicts the evidence! \$\endgroup\$ – undergroundmonorail Jun 4 '14 at 17:09
  • 1
    \$\begingroup\$ Wouldn't the Thinker Clock be the evidence being contradicted, then? There's more direct contradiction between the Thinker Clock and the last statement. \$\endgroup\$ – cjfaure Jun 4 '14 at 17:14
  • \$\begingroup\$ Of course, saying that C is False is a contradiction... *desk slam* but the challenge requires you to find the first statement to contain a contradiction! [Present -> Challenge Spec] It reads, and I quote, "...you must find the first Statement that contains the contradiction". Take that! \$\endgroup\$ – undergroundmonorail Jun 4 '14 at 17:21
  • \$\begingroup\$ Ace Attorney strikes again! \$\endgroup\$ – cjfaure Jun 4 '14 at 17:30
  • 1
    \$\begingroup\$ So basically this is a presentation of 2-SAT. The third example is wrong: statement 2 contradicts stuffed animal tail. And I agree with Trimsty that where you have a chain of reasoning there isn't a unique "contradicted Evidence", so I think that you should make it clearer what you mean by that. \$\endgroup\$ – Peter Taylor Jun 4 '14 at 20:48
  • \$\begingroup\$ @PeterTaylor I will figure out a way to formalize it better \$\endgroup\$ – undergroundmonorail Jun 4 '14 at 20:52
  • \$\begingroup\$ @githubphagocyte Yep, my bad. That was a typo. \$\endgroup\$ – undergroundmonorail Jun 4 '14 at 20:53
  • \$\begingroup\$ I feel like in many languages this scores for this will be dominated by string handling. \$\endgroup\$ – Martin Ender Jun 5 '14 at 15: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:48
7
\$\begingroup\$

Sandbox note: This is an idea for a challenge based on the halting problem. As it is, it's hard to imagine it being popular on PPCG, but I'd really like to make it into something people would actually participate in. The reason is that it's really interesting from a theoretical point of view, as a fundamentally open-ended challenge. The beautiful mathematics of Turing and Gödel gurantees that there's always a new innovation that the cops could make, and there's always a way for the robbers to exploit it. So any ideas on how to turn this into something fun would be greatly appreciated.

HALT in the name of the law

The robbers are getting away, and the cops have to decide whether to wait for them to stop and arrest them, or set up a road block at the state boundary. They do this by trying to predict whether the robbers' program will halt. Please note that this challenge is hard, especially for the cops.

Robbers are represented by programs written in a language called "w", which I invented for this challenge, and which I describe below. w is easy to implement and relatively easy to reason about. I will provide a reference implementation and a macro preprocessor that allows it to be written in a somewhat human-readable form.

Cops must provide a program (in any language) that takes a robber's w program as input, and tries to decide whether it halts or not. A cop submission is invalidated by a robber program for which it returns the wrong answer or fails to terminate.

Cops

You must write a program that takes as input programs in the (pre-processd) w language. It should attempt to output a truthy value if its input program ever halts, and a falsy value if it doesn't. Your submission should be written in a "real" programming language rather than w. In addition to your program, you should provide a clear English explanation of how it works.

Robbers

You must "crack" cops' submissions by providing one of the following three things:

  • A program written in w that halts, but for which the cop program does not return a truthy value. (The cops waited at the roadblock while you stopped, changed your identities and went underground.) You must demonstrate that the program halts, either by running it in the reference implementation of W or by proving that it has to halt eventually.

  • A program written in w for which the cop's program returns a truthy value, together with a proof that your program does not halt. (The cops gave chase, but you kept going until you reached the state border, infinitely far away.)

  • A program written in w for which the cop program itself doesn't halt, together with an argument showing that it doesn't halt. (The cops just gave up and got some donuts, hoping nobody would notice.)

Other rules

If the cops' program is nondeterministic (e.g. because it's doing some kind of stochastic search for halting conditions) then it suffices to show that there is some non-zero probability that it will return the wrong answer or fail to halt.

This is for the cops - the uncracked submission with the most votes wins.

The w language

Syntax and semantics

w is a very simple structured programming language whose variables can only be incremented and decremented, and whose only control structure is the while loop. The syntax is designed to be as easy to parse as possible. Here is an example w program. Below I'll describe what it does.

a+ a+ a+
b+ b+
a{
  a-
  b+
}

There is a preprocessor [to be provided] that, among other things, standardises the whitespace, so that the code above will be formatted like this:

a b
a+ a+ a+ b+ b+ a{ a- b+ }

The first line (provided by the preprocessor) is a list of all the variable names that appear in the program. All variables in w are unsigned infinite-precision integers. (Infinite precision means that they will never overflow. This is very important for Turing-completeness.) A variable name is any combination of the characters a-z, A-Z, 0-9 and _. All variables initially hold the value 0.

The second line is a list of expressions. There are three kinds of expression. The first two are <variablename>+, which increments a variable by 1, and <variablename>-, which decrements it by 1. (For C programmers, think of these as the postfix ++ and -- operators.) Since the variables are unsigned, it is an error to decrement a variable whose value is zero. This will halt the program immediately. (Note that errors are counted as halting for the sake of this challenge.)

The third type of expression is a while loop. Its syntax takes the form {<variable_name>,<expression_list>}. If the variable has value 0, the expression list is skipped. Otherwise, the expression list is executed repeatedly until the variable becomes zero. (If the variable never becomes zero, the program fails to halt.) That's it - there's nothing more to the language than that.

Note that if you split the second line of the preprocessed program at the spaces, each item will either be } or a variable name followed by a symbol, so you can easily pop off the last character to see what kind of expression you're dealing with.

Looking back at the example program, the first line, a+ a+ a+ increments a three times, setting it equal to 3, and the second line sets b to three. The while loop decrements a while incrementing b until a is zero. So the value of a is added to b, and at the end of the program, a is zero and b is equal to five.

Alternative syntax

Optionally, the preprocessor can output w programs as a string representing a Python list. The example program would appear as follows. The first sublist is the list of variables, and the second is a list of lists representing the parse tree.

[["a", "b"], ["a+", "a+", "a+", "b+", "b+", "a{", ["a-", "b+"]]]

Input and output

For the sake of this challenge, we only care whether a program halts or not when given no input, so there is no input or output in the w language as described here. However, if we wanted we could say that a special variable (let's say _) is initialised with the program's input, and the value of the last expression evaluated is the output. If we do this, the language becomes Turing complete in the classical sense. (The proof is left as an exercise to the reader.)

Implementation notes

Implementing W correctly requires the use of infinite-precision integers. However, the only operations these need to support are incrementing and decrementing, which makes them much easier to implement. The reference implementation uses Python's unlimited precision integers.

\$\endgroup\$
  • \$\begingroup\$ As written this seems to allow P to fail to halt if the supplied program fails to halt. "Completely define its syntax and semantics" could lead to disputes, especially if someone chooses to use an obscure semantic model or to define their L in terms of an existing language which doesn't have formally defined semantics. \$\endgroup\$ – Peter Taylor Oct 26 '14 at 8:16
  • \$\begingroup\$ I think this will be way too hard on the side of the cops to be feasible for PPCG. \$\endgroup\$ – Martin Ender Oct 26 '14 at 10:53
  • \$\begingroup\$ @PeterTaylor I've fixed the first of those issues - do you have an intuition on how to deal with the second? \$\endgroup\$ – Nathaniel Oct 26 '14 at 13:38
  • \$\begingroup\$ @MartinBüttner I like hard challenges, and by posting them I hope to attract other users who feel the same way. I think "this challenge is too hard" is not a thing that should be said here; it might seem hard to some people (especially before a solution has been posted) but one shouldn't underestimate how clever people can be. I'm not sure but I think being hard for the cops rather than the robbers is a good thing in this type of challenge. \$\endgroup\$ – Nathaniel Oct 26 '14 at 13:40
  • \$\begingroup\$ I see this as much too easy for the cops, who can simply use a tedious integer factorization or similar task as always. Define L as follows: after performing trial division on a hard-coded integer, execute a Brainfuck program if it has a 200-digit prime factor, terminate without executing those instructions if it has a 201-digit prime factor, or otherwise go into an infinite loop. P simply prints 1. \$\endgroup\$ – feersum Oct 26 '14 at 15:30
  • \$\begingroup\$ Not really. You could pick a semantic model and require people to use it, but then you exclude people who don't know it and don't want to learn it just for this challenge. You could pick an L and require everyone to use it, but I expect you to say that that would take away a lot of the fun. \$\endgroup\$ – Peter Taylor Oct 26 '14 at 17:40
  • \$\begingroup\$ @feersum ah, you're right, this challenge can be gamed in that way. Even worse, you could use something like the twin primes conjecture instead of prime factorisation, and nobody could crack your entry without collecting a Fields medal. I'm not sure if there's a way to fix that :( \$\endgroup\$ – Nathaniel Oct 27 '14 at 0:36
  • \$\begingroup\$ @PeterTaylor I'd be quite happy to pick an L for everyone - that would also solve the problem feersum pointed out - but the question is, what should it be? It needs to be Turing complete and simple enough to analyse programmatically, and I guess it would help a lot if it was also fairly human-readable and intuitive. (That pretty much rules out lambda calculus, which is the obvious choice, though it's actually already a bit fiddly to deal with lambda expressions programmatically because of having to track free variables and do alpha-conversions all the time.) Do you have any thoughts? \$\endgroup\$ – Nathaniel Oct 27 '14 at 0:55
  • \$\begingroup\$ If you want to take a functional approach then pick a universal set of combinators (e.g. SK or Iota). If you want an imperative language, either a well-specified BF or a "toy" language like IMP (as in the one described in Winskel's book on semantics, not the one described in the Wikipedia page - which might confuse people too much). Or pick something interesting from esolangs.org. \$\endgroup\$ – Peter Taylor Oct 27 '14 at 12:16
  • \$\begingroup\$ @PeterTaylor in case you're interested, I invented my own Turing-complete language (imperative but much more minimal and easier to parse than IMP) and added its spec to the draft. \$\endgroup\$ – Nathaniel Oct 29 '14 at 10:27
  • \$\begingroup\$ Looks like a restricted form of Minsky register machine. As a fan of MRMs, I approve. \$\endgroup\$ – Peter Taylor Oct 29 '14 at 10:35
  • \$\begingroup\$ @PeterTaylor yes, indeed, that's what I based it on. \$\endgroup\$ – Nathaniel Oct 29 '14 at 10:36
  • \$\begingroup\$ A potential loophole for cops: The cops' program searches for a string that has a certain hash. If the string's length is more than 400, it outputs true, otherwise it outputs false. It would be very difficult for the cops to prove that the program generates an incorrect result. \$\endgroup\$ – Esolanging Fruit May 29 '17 at 21:59
  • \$\begingroup\$ In the non-preprocessed program, what whitespace is necessary? Is a+a+a+b+b+a{a-b+} valid? \$\endgroup\$ – wastl May 24 '18 at 14:05
  • 1
    \$\begingroup\$ @wastl not sure if I'll ever post this, but the preprocessor would ignore all whitespace, so that would be fine \$\endgroup\$ – Nathaniel May 25 '18 at 0:31
7
\$\begingroup\$

King Me - Draughts King of the Hill

Note: I made this CW so someone else can take it over, because I have no desire to make the controller and run the tournament anymore.

Draughts (or checkers, as it is known in the United States) is a well-known international game. I was surprised that we have not had a draughts King of the Hill yet, so here's one! In case you're unfamiliar with the rules (or perhaps you need a refresher), here are the rules for English draughts, the version we will be playing.

Draughts is played on a checkerboard that looks like this:

draughts board

There are two players, white and red, who sit on the side of the board closest to their pieces' starting position. White moves first. Normal pieces (men) may move forward (from the perspective of the player; towards the other player) one space along diagonals, or jump over diagonally-adjacent pieces that are in front of them to capture them and remove them from the game. Because pieces can only move diagonally, they will always be on the dark squares of the board.

For example, the following move is permitted, and would result in the red piece being captured:

jumping

Players may jump as many pieces in a row as possible when making their move, which results in all jumped pieces being removed. Normally in draughts, jumping is not optional - if you can jump, you must jump, and you must make the longest jump possible. However, for this game, jumping is optional, and you do not have to make the longest jump possible if you do not wish to.

Additionally, when a man reaches the furthest row (the row closest to their opponent), it is promoted to a "king", which confers the ability to move (and capture) backwards along diagonals.

A game is ended when a player's pieces have all been captured or the player cannot make a valid move. The player who cannot move due to being trapped or having no pieces is the loser. To prevent games from going indefinitely, I am adding the additional condition that, if a capture has not happened in 10 turns (a turn being defined as ending after the red player has made their move), the game is ended and declared a draw.

The Tournament

Submissions will be accepted for seven days following the posting of this question. At 11:59 PM UTC on the seventh day, registration will close, and the tournament will be run soon after.

Submissions will compete in a round-robin tournament. 5 points will be awarded for a win, 2 points for a draw, and 0 points for a loss. 10 games will be played per match, for each pair of contestants. The submission with the highest score at the end of the tournament will be declared the winner and chosen as the accepted answer. In the event of a tie, total number of wins will be used to decide the winner.

If a bot makes an invalid move or takes longer than 1 second (judged using Java's Timer class), it will be ruled as a forfeit for that game.

To make things simple for me, all submissions must be in Java, and will be classes that inherit from a common Bot interface. The Bot code and Controller class are provided below:

[todo: bot and controller code]

\$\endgroup\$
  • 2
    \$\begingroup\$ Maybe as a note you should put that Draughts (Checkers) has been solved, and is in fact the largest game to ever be solved: en.wikipedia.org/wiki/Solved_game#Solved_games \$\endgroup\$ – geokavel Nov 15 '15 at 16:38
  • \$\begingroup\$ @geokavel Good point. Since it has only been weakly solved (meaning perfect play can only prevent a loss, rather than force a win), I'm going to compensate for that by increasing the number of points for a win. That should incentivize players to go for wins, rather than forcing draws. \$\endgroup\$ – Mego Nov 15 '15 at 16:43
  • \$\begingroup\$ I still think that the bot that plays perfectly (no loss) will end up the winner of this KoTH, unless you make the win points really high (like 10), so that 1 win amounts to 5 draws. \$\endgroup\$ – Nathan Merrill Nov 15 '15 at 16:52
  • \$\begingroup\$ @NathanMerrill I want to incentivize winning, but not to the point where perfect play is disincentivized. The winning bot should be one that uses perfect play to avoid losses, but deviates to try to force wins when it can. Besides, the end-game conditions are different here from the style that was solved, so perfect play may not be so perfect here. \$\endgroup\$ – Mego Nov 15 '15 at 17:01
  • 1
    \$\begingroup\$ @Mego: I don't think that is what "weakly solved" means. The game if played perfectly results in a draw. It is weakly solved because some positions were proven suboptimal. As a result traversing those parts of the game tree never happened. A computer cannot play this game perfectly as a human could decide to take a suboptimal path but the computer would have no idea what to do. Strongly solving means (roughly) a computer knows what to do at every point. \$\endgroup\$ – Dair Oct 21 '16 at 22:02
  • \$\begingroup\$ Do you intend to post this at some point? I might be interested to write a challenge and a language-agnostic controller (using STDIO and/or argv for I/O), but apparently you and another user have both created a sandbox post on the same topic. \$\endgroup\$ – PurkkaKoodari May 25 '18 at 23:52
  • \$\begingroup\$ @Pietu1998 I posted this in the Secret Santa's Sandbox post a while back - it's fair game for anyone who wants to complete it. \$\endgroup\$ – Mego May 26 '18 at 6:46
7
\$\begingroup\$

Count the cubes

Here is a picture of a diamond tiling shamelessly stolen from Random ASCII Art of the Day #5: Diamond Tilings:

However it also has the property of representing a 3D isometric view of a 5×5×5 cube with 59 cubes removed, leaving 66 behind. (Cubes obscured by other cubes are assumed to exist.)

Your task is, given an ASCII art representation of a diamond tiling, is to output both the number of cubes removed and remaining. For example (some shamelessly stolen from Scale up a Diamond Tiling):

  ____
 /   /\
/___/  \ -> 1 0 or 0 1
\   \  /
 \___\/
  ________
 /   /\   \
/___/  \___\ -> 1 1
\   \  /   /
 \___\/___/
  ____________
 /   /\   \   \
/___/  \___\___\ -> 2 1 or 1 2
\   \  /   /   /
 \___\/___/___/
  ________________
 /   /\   \   \   \
/___/  \___\___\___\ -> 3 1 or 1 3
\   \  /   /   /   /
 \___\/___/___/___/
  ________
 /\   \   \
/  \___\___\
\  /   /\   \
 \/___/  \___\ -> 3 1 or 1 3
  \   \  /   /
   \___\/___/
    ________
   /   /\   \
  /___/  \___\ -> 3 1 or 1 3
 /\   \  /   /
/  \___\/___/
\  /   /   /
 \/___/___/
    ____
   /   /\
  /___/  \
 /\   \  /\
/  \___\/  \ -> 3 1 or 1 3
\  /   /\  /
 \/___/  \/
  \   \  /
   \___\/
    ________
   /   /\   \
  /___/  \___\
 /\   \  /   /\
/  \___\/___/  \ -> 4 4
\  /   /\   \  /
 \/___/  \___\/
  \   \  /   /
   \___\/___/
      ____________
     /   /   /\   \
    /___/___/  \___\
   /   /\   \  /\   \
  /___/  \___\/  \___\
 /\   \  /   /\  /   /\
/  \___\/___/  \/___/  \ -> 16 11 or 11 16
\  /   /\   \  /   /\  /
 \/___/  \___\/___/  \/
  \   \  /   /\   \  /
   \___\/___/  \___\/
    \   \   \  /   /
     \___\___\/___/
      ____________________
     /   /\   \   \   \   \
    /___/  \___\___\___\___\
   /\   \  /\   \   \   \   \
  /  \___\/  \___\___\___\___\
 /\  /   /\  /   /   /   /\   \
/  \/___/  \/___/___/___/  \___\
\  /\   \  /   /\   \   \  /   /\
 \/  \___\/___/  \___\___\/___/  \ -> 40 20 or 20 40
  \  /   /\   \  /   /\   \   \  /
   \/___/  \___\/___/  \___\___\/
    \   \  /   /\   \  /   /   /
     \___\/___/  \___\/___/___/
      \   \   \  /   /   /   /
       \___\___\/___/___/___/
        ________________
       /   /\   \   \   \
      /___/  \___\___\___\
     /\   \  /\   \   \   \
    /  \___\/  \___\___\___\
   /\  /   /\  /   /   /\   \
  /  \/___/  \/___/___/  \___\
 /\  /\   \  /   /   /\  /\   \
/  \/  \___\/___/___/  \/  \___\ -> 46 18 or 18 46
\  /\  /   /\   \   \  /\  /   /
 \/  \/___/  \___\___\/  \/___/
  \  /\   \  /   /\   \  /   /
   \/  \___\/___/  \___\/___/
    \  /\   \   \  /   /   /
     \/  \___\___\/___/___/
      \  /   /   /   /   /
       \/___/___/___/___/

The output can be in any reasonable format, e.g. an array return value or a string with whitespace, but it must contains both values, even if they are the same, however the order of the two values does not matter in any way; you could even reverse the order on subsequent runs if you wanted to.

This is , so the shortest solution wins!

\$\endgroup\$
  • \$\begingroup\$ One more maybe? Also meta.codegolf.stackexchange.com/a/8101/8478 ... I'd just put all test cases in one code block and the result for each on the next line. \$\endgroup\$ – Martin Ender Feb 27 '16 at 17:41
  • 2
    \$\begingroup\$ Much better. I'd still put the results of the test cases on the next line though to make it easier to process them all automatically. \$\endgroup\$ – Martin Ender Feb 28 '16 at 15:56
7
\$\begingroup\$

Ant Wars

Parts of this challenge are based off of Ant Queen of the Hill Contest.


Objective

Your objective is to conquer the ants of the world ... or have the biggest army of ants. To do this, you start with a single queen. The queen can create worker ants by using food gathered by itself or other worker ants. Your worker ants can kill other ants by attacking them. You win if you have the only queen left, or if you have the biggest army of ants.


Board

The board will be a square with wraparound borders. The length of each edge is determined by sqrt(1000*n)1. Before the game fierce battle for domination starts, 100*n pieces of food will be distributed semi-randomly on the board . n queens, 1 for each player, will also be randomly distributed on the board.

1: n is the number of starting players


Ants

Sight and Smell

Ants are usually near-sighted and have somewhat short antenna. Because of this, ants in this simulation can only see and smell ants, food, and pheromone in its 3 by 3 neighborhood. They can also tell the difference between ants of different species.

Memory

Because of limited brain space, every ant has a memory of up to 5 characters long. The starting memory for queens is 5 spaces.

Orientation

Every ant is oriented in the direction that it last moved. Queens start out oriented in a random direction.

Food

Each worker ants can carry up to 1 unit of food. A queen ant can carry an unlimited amount (so that's what her body is for). Every ant picks up as much food on its current square as possible. A queen ant takes all the food from adjacent squares including that carried by workers of any player.


Moves

Every turn, every ant is given a view of the local surroundings and then decides to move. Ants are given priority in their movement with those that are oldest moving first. The initial order for the starting queens is random.

Attacking

An ant attacks by attempting to move onto another ant. Worker ants require two ants attacking them in order to be killed. Queen ants require eight ants attacking it in order to be killed. Queen ants cannot attack. An ant after being killed drops all food it is carrying and one additional unit of food.

Moving

An ant can move to any of the 8 surrounding squares. This changes the orientation of the ant to the direction it is moving. If it tries to move to a square with an ant already on it, it is assumed to be attacking that ant, no matter if friendly or not.

Dropping Pheromone

An ant can optionally increase the value of 4 different pheromones on the cell it is on, 1 of which can only be seen by ants of that particular colony. Pheromone has a value of a double-precision float and decreases by 1% every game tick. An ant can increase pheromone by up to 10.

Creating Workers

A queen ant may create a worker and spawn it in any of the surrounding cells. The queen ant also chooses the memory of the new worker.


Winning

A game ends after there is only one queen left or after 10000 turns. The winner is one of the players with a queen with the most workers. I will determine the winner after playing a number of games ... depending on the amount of time it takes to play each game.


Coding

You can implement a program or a java class that takes in an ant input and gives an ant output for that ant.

Input:

Input contains your player id, your ant's memory, if your ant is a queen, and then the contents of the cells surrounding it. The cells are given from the top left to the top right in this order:

0 | 1 | 2
3 | 4 | 5
6 | 7 | 8

Input is format thus:

player_id;ant_memory;is_queen;cell_0_info;cell_1_info...

Cell info is formated like this:

pheromone_0,pheromone_1,pheromone_2,pheromone_3,ant_type,ant_owner

player_id and ant_owner are positive integers.
ant_memory is a 5-character long string.
is_queen is one of true or false.
The pheromones are double-precision (64-bit) floats.
ant_type is one of W (for worker ants) and Q (for queen ants).
If there is no ant on a cell, ant_type and ant_owner will be omitted from the input.

Output:

You have to output the cell you want to move to, the pheromone you wish to add to your current cell, and whether the ant would like to create an ant instead of moving (only works for queens :P).

It should be formatted thus: next_memory;cell;pheromone_0;pheromone_1;pheromone_2;pheromone_3;create_ant;created_ants_memory

The controller is rather flexible and should be able to understand what you write if you use different delimiters or leave out some of the information. Make sure that next_memory comes first in your programs output and that it is exactly 5 characters long. If creating an ant, created_ants_memory needs to be the last 5 characters in the input.

cell has to be an integer in the range [0, 8] (defaults to 4).
pheromone_n has to be a positive float (defaults to 0).
create_ant needs to be one of: true, false, yes, no, 1, or 0 (defaults to false).

How to create a bot:

You have 3 options for this. You can:

  1. Implement the Ant interface with a java class. (Very fast)
  2. Communicate to the controller via I/O streams. (Fast (I think))
  3. Be called via command arguments and output via STDOUT (Slow depending on OS and programming language)

Note: Your bot must be completely deterministic. Given the same input, your bot should always return the same output.

Method 1:

Ant interface:

interface Ant {
    String move(String input);
}

Implement this interface for your ants :)

Method 2:

Every time it is one of your ants' turns, your program will receive a line of input through STDIN followed by a newline. After receiving the input, your program is expected to output a line through STDOUT followed by a newline.

Method 3:

Your program will be executed with the input line as its first argument. Your program is expected to output through STDOUT.

Time limit

Each time your program is called, it should return within 5 milliseconds. Since the time limit may be exceeded due to fluctuations outside your control, an average will be calculated. If at any point the average is above 5 milliseconds and the total time taken by your program across all calls so far is more than 10 seconds, the relevant player will be disqualified. This means they will not be eligible to win, their ant function will not be called again during that game, and all ants of that player will instantaneously perish.



Questions

  1. How can I improve this to look prettier?
  2. Any typos or formatting issues?
  3. Any other ways I can improve this challenge?
\$\endgroup\$
  • \$\begingroup\$ What is n? Where do queens start? Go through everything as if you were writing the underlying code, and ask yourself "How would that be implemented?". It's a good way of making sure all the info is in there. \$\endgroup\$ – wizzwizz4 Jan 3 '16 at 15:41
  • \$\begingroup\$ @TheNumberOne Could you put a link to / embed the controller? Or perhaps post this as an actual challenge? \$\endgroup\$ – wizzwizz4 Jan 3 '16 at 19:45
  • \$\begingroup\$ @trichoplax Answered your questions in the post... though I am a little late :P \$\endgroup\$ – TheNumberOne Mar 15 '16 at 20:45
  • \$\begingroup\$ @BentNeeHumor Good to see we are both working at the same rate :) \$\endgroup\$ – trichoplax Mar 16 '16 at 9:54
  • 1
    \$\begingroup\$ In chatting about my ant KotH in the dedicated chat room I remembered this version with pheremones that fade over time. I'd love to see this posted to main. Is there anything that needs to be addressed or anything we can help with? \$\endgroup\$ – trichoplax Jan 13 '18 at 20:45
  • \$\begingroup\$ (P.S. In case you hadn't seen it, mine finally made it to main after 2 years in the sandbox, back in July) \$\endgroup\$ – trichoplax Jan 13 '18 at 20:46
  • \$\begingroup\$ define "character" - is the memory ASCII-only? \00-\ff? any unicode character? \$\endgroup\$ – dzaima Jan 13 '18 at 21:31
  • \$\begingroup\$ @trichoplax sorry, I haven't been active on here for a while. you can probably do whatever with it ;) \$\endgroup\$ – TheNumberOne Jan 13 '18 at 23:43
7
\$\begingroup\$

Let's Play Unikong

In honor of April Fool's day, we shall have an epic battle to see who can play Unikong best. Or, rather, whose program can play it best.

Goal

Write a program in any language to play the game Unikong. It should seek to try and score as high as possible.

Scoring

Whomever's program has the highest average score, over 10 games wins.

Rules

Standard rules apply. Additionally, your program must actually play the game, not change the score variable by some other means, and you can read the variables from the game to avoid trolls and downvotes, but not modify any variables to make it easier. I will run the tests myself and will use the first 10 runs to calculate the score. Please include any specific instructions needed to run your program.

Notes: This would be my first question, so hopefully I got the format right. Are the rules clear enough? Do I need to clarify anything?

\$\endgroup\$
  • 2
    \$\begingroup\$ Do not require a video, run the programs yourself and see how far they get without your input. No pressing continue. \$\endgroup\$ – Bald Bantha Apr 1 '16 at 17:09
  • \$\begingroup\$ Uh, will that link exist beyond today? If not then I think you'd need to find a way to replicate it (not sure about copyright here...). Anyway, I'm not really sure what counts as cheating. I think it will be hard to ban everything that's bad, so it might be better to write a controller that only allows looking at certain variables and only allows the basic player input. \$\endgroup\$ – FryAmTheEggman Apr 1 '16 at 17:09
  • \$\begingroup\$ @FryAmTheEggman I've changed the link to something that will remain after April Fool's. \$\endgroup\$ – Addison Crump Apr 1 '16 at 22:02
7
\$\begingroup\$

King of the Sausage

This is just a draft.

I saw this (slightly altered) 'game' in a tv show once: Two competitors are each given a sausage of equal weight. Then they each have to cut pieces from this sausage (without seeing how much the oponent cut off) which then are weighted against each other. The player that has the heavier piece gets a point. Then the weighted sausage pieces are discarted and the process is repeated. After 5 rounds the one who got the heavier piece more often wins.

A win results in 3 points, a loss in 0, a tie in 1 for.

Details

Here the saussage weight is given as an integer totalWeight. You can only cut off pieces of integer size.

Each submission should write a JavaScript function that takes these arguments:

  • totalWeight: The units of the total weight of the sausage at the beginning as an integer between 5 and 2^31-1.
  • round: An integer between 0 and 4 that indicates the current round.
  • ownPieces: An array of size 0 upto 4, each element is the size of the piece you cut of in the previous round.
  • opponentPieces: The same, but with the pieces of the oponent.
  • memory: A variable that allows you to store information between the rounds. It can contain any kind of structure. It is initialized with 0 before the first game with an new oponent and it can store information between those games.

Each time it is called, it has to return an integer between 0 and the weight of the remaining sausage (= totalWeight minus the sum of the entries in ownPieces). If it does return anything else, the submission will be disqualified. The function may not access any global variables and may not try to influece the game in any other way. It cannot take more than 100ms per round.

Each pair of oponents will play this game a certain number (to be determined ) of times against each other.

Feel free to share your thoughts / suggestions!

Meta:

How should the initial sausage weight be determined?

Possible controller inspiration: https://jsfiddle.net/CalvinsHobbies/ave6ejyd/

\$\endgroup\$
  • \$\begingroup\$ Are the weights integers or floats? \$\endgroup\$ – Peter Taylor Oct 24 '15 at 10:06
  • \$\begingroup\$ That is a crucial point thanks! The original game would obviously lead to using floats, but now that you ask, I think the integer problem would be even more interesting, don't you think? \$\endgroup\$ – flawr Oct 24 '15 at 11:31
  • \$\begingroup\$ I think using integers is good because it avoids discrepancies over parsing and rounding, but using small integers would allow a lot of pre-analysis to be done. I suggest starting at a random integer between 1000000000 and 2000000000 (within the range of signed 32-bit ints, but too large and variable to be easily pre-analysed). Oh, and if both run out of sausage then the remaining rounds should be ties. Allow a match to be tied, and score 3 points for a win and 1 point for a tie. \$\endgroup\$ – Peter Taylor Oct 24 '15 at 12:53
  • \$\begingroup\$ The clearest thing to me when competitors have no sausage is for them to tie the remaining rounds. I'm not sure if there is some other constraint you are thinking of, though. I also think I like Peter's idea of using a slightly random but guaranteed to be large sausage instead of a constant one. I don't think you would have any real problems given the size, but I think it would highlight the more interesting parts of the challenge. \$\endgroup\$ – FryAmTheEggman Jul 4 '16 at 14:29
  • \$\begingroup\$ If we have a variable saussage size, does anything prevent us to also throw in small numbers (at least the number of rounds)? As the competitors do not exactly know what numbers there will be, it seems it does not matter? \$\endgroup\$ – flawr Jul 4 '16 at 19:07
7
\$\begingroup\$

Simulate Colorblindness

As some of you might know, I am colorblind. Specifically, I have moderate deuteranopia. This means that I have difficulty distinguishing between red, green, and yellow colors, as well as various shades of purple and blue, due to not having green cones in my eyes.

The most common way to diagnose colorblindness is through the use of the Ishihara test. In this test, various image plates are shown to the individual. These plates are comprised of dots of several shades of the same color, where certain shades are grouped together to form numbers. The shades are chosen so that, based on the set of plates on which the individual fails to recognize the number, the type of colorblindess can be determined.

Here are a few samples of Ishihara plates:

plate 1

This plate (plate #1 in the Ishihara 24-plate test) is a control plate - everyone should be able to see the number 12 clearly, regardless of whether or not they are colorblind. This is the only plate on which an individual with total colorblindness (monochromacy) can read the number.

plate 2

This plate (plate #2) has an 8 inscribed on it, but individuals with red-green deficiencies see it as a 3 (myself included).

plate 8

This plate (plate #8) has a 6 inscribed on it, but individuals with any type of colorblindness cannot see any number.

plate 14

This plate (plate #14) will be seen as having a 5 on it by individuals with red-green deficiencies, but others will not see any number.

plate 16

This plate (plate #16) has the number 26 on it. Individuals with protanopia will only see the 6, and individuals with deuteranopia will only see the 2.

The Challenge

Given a set of Ishihara plates, output the number that an individual with each type of colorblindness (none, protanopia, deuteranopia, and monochromacy)1 would see on the plate. Your score will be the number of correct outputs your program gives for each plate in the scoring battery (up to 4 points per plate).

For testing purposes, here is an Imgur gallery containing the first 17 original Ishihara plates. The correct outputs for each plate are as follows:

X means that no number can be read
Plate #: Normal, Protanopia, Deuteranopia, Monochromacy
1: 12, 12, 12, 12
2: 8, 3, 3, X
3: 29, 70, 70, X
4: 5, 2, 2, X
5: 3, 5, 5, X
6: 15, 17, 17, X
7: 74, 21, 21, X
8: 6, X, X, X
9: 45, X, X, X
10: 5, X, X, X
11: 7, X, X, X
12: 16, X, X, X
13: 73, X, X, X
14: X, 5, 5, X
15: X, 45, 45, X
16: 26, 6, 2, X
17: 42, 2, 4, X

The scoring battery will be a unique set of Ishihara plates, created for the purpose of this challenge.

Specifications

  • Input and output may be in any reasonable manner and format, so long as no extra information (such as the number that should be seen on the plate) is conveyed in the input other than the image data.
  • Builtins which trivialize this challenge (such as an optical character recognizition library like Tesseract) are forbidden. Though I highly doubt that any programming language or library has this functionality built-in, Mathematica and its ilk continue to surprise me.
  • The scoring set of plates will not be disclosed, to prevent optimizing for that specific set.

1: There are actually a few other variations of colorblindess, but Ishihara plates are not effective at diagnosing them.

Sandbox Questions

  • Did I mess up any of the plate images? Being colorblind myself, picking out the proper plate images is rather difficult.
  • Is there anything that needs further specification?
\$\endgroup\$
  • 1
    \$\begingroup\$ 1. There seems to be a reference to a footnote, but I don't see the footnote. 2. The descriptions of the plates seem to me ("normal") to match the images. 3. You do realise that the golfiest approach is likely to be to find a single pixel which differs in all the images in the test battery? I'd be rather surprised if any answer actually does OCR. \$\endgroup\$ – Peter Taylor Aug 24 '16 at 10:03
  • \$\begingroup\$ @PeterTaylor Thank you for reminding me to add the footnote. As for point 3, disallowing optimizing for the scoring cases takes care of that. \$\endgroup\$ – Mego Aug 24 '16 at 10:11
  • 2
    \$\begingroup\$ As usual with those kinds of classification challenge, the optimal way to provide data should be: a training set, a validation set, and a test set. You only provide the training and validation set, so that people can use the training set to build their algorithms and the validation set to check that they generalize properly. You keep the test set to yourself and use it to give a score to each answer, as such no one can optimize their algorithm to get the best score. \$\endgroup\$ – Fatalize Aug 24 '16 at 12:03
  • \$\begingroup\$ I agree with Fatalize regarding the hidden test set. Also, that plate #14 is blowing my mind (since I have no problems with vision, I've never experienced the "other" side of these sorts of tests). \$\endgroup\$ – AdmBorkBork Aug 24 '16 at 15:32
  • \$\begingroup\$ @Fatalize I wasn't sure about how people felt about the scoring set not being public, but I will go along with that suggestion. \$\endgroup\$ – Mego Aug 24 '16 at 21:02
7
\$\begingroup\$

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

The Best Way to Rake Leaves

[This is just a little problem I thought up while doing yard work today. It is not fully specified and I may not finish it if some simple optimal solution is found.]

Suppose some 2D grid represents the area of a lawn. A number of leaves are strewn over the lawn and they are modeled as single grid points. You have a rake that is modeled as a line segment of length L.

example

To start you can rotate the rake in any way and put it anywhere on the grid.

When the rake is moved some distance d along its perpendicular, all the leaves in its path are caught in it. They stay on the rake line until the rake stops (as with normal raking).

You repeat this process (moving the rake different distances every time) until all the leaves all lie on one singular point.

The question is: what is the minimum distance the rake has to move to make this happen?
(i.e. what is the minimum sum of the d's from each move?)

Challenge Spec (details incomplete)

Write a program that takes in a list of (x, y) leaf points and the length L of the rake (all floats).

The program should output a sequence of rake moves in the form of ((x1, y1), (x2, y2)) line segments that the rake travels perpendicularly down the center of. This sequence must bring all the leaves to the same exact point when they are "moved" by the rake

The challenge is to make an algorithm that does this with the least possible sum of sqrt((x1-x2)^2 + (y1-y2)^2) over all points.

[At this point several test cases would be given, with different L values and different leaf distributions. The submission that minimizes the total distance wins (assuming they do not hard code the answer).]

[This optimization problem does not seem to have any trivial solutions or even a clear optimal solution. Can anyone else poke holes in it?]

\$\endgroup\$
  • \$\begingroup\$ I still think this would be a fairly interesting problem. Any plans of still posting it at some point? \$\endgroup\$ – Martin Ender Dec 12 '14 at 22:49
  • \$\begingroup\$ @MartinBüttner Yes, I have been trying to get around to it. If I don't in a week or so feel free to post it yourself. \$\endgroup\$ – Calvin's Hobbies Dec 13 '14 at 6:15
  • \$\begingroup\$ No rush. I'd probably rather try to participate than post it myself. ;) I am considering posting something related though (it wouldn't be an optimisation problem, but it might be reusable as a substep for this challenge, although I'm not even sure it's anywhere near an optimal approach to this). \$\endgroup\$ – Martin Ender Dec 13 '14 at 12:03
  • \$\begingroup\$ Hello! This looks like a good but abandoned meta post, would you be willing to offer it for adoption or post it to main? \$\endgroup\$ – programmer5000 Jun 9 '17 at 18:39
  • \$\begingroup\$ @programmer5000 Adopt it. That's fine. \$\endgroup\$ – Calvin's Hobbies Jun 9 '17 at 20:04
7
\$\begingroup\$

Tower Defense (Abandoned)

Anyone is free to take over this challenge and fork as necessary. Just give me credit ;)


Tower Defense Example

View it here | Chat

Tower Defense is a format for casual games that was popularized in the Flash era. The player places towers that shoot down invaders moving along a predefined path.

Overview

Two submissions will compete against each other to invade the other player's village without being invaded themselves. They will have the ability to place towers, upgrade them, and spawn invaders to attack the enemy village. The game will be simulated deterministically in a turn based fashion, with each player being able to do one action each turn.

The game board is made up of two paths, each 100 spaces long. Each player begins with 500 gold, which is used for building towers and spawning invaders; and 100 life. Your objective is to bring your opponent's life down to 0. If neither player has been defeated after 100000 turns, the winner will be the player with the most life at that point, with ties being broken by who has the most gold at that point. If, somehow, there is still a tie, the match will be considered a tie.

Income

Every 10 turns, players will receive gold. Initially, they receive 10 gold, but this amount increases by 3 every 100 turns.

Each time you successfully get an invader through your opponent's defenses, your income increases by 1 and you receive a portion of your income proportional to how much HP the invader had left.

Each time one of your towers defeats an invader, you receive gold. (More on that below)

Towers

Each space on the path can house one tower. There are 3 types of towers, which have a range and a power. It takes 10 turns for a tower to be ready after it is built. Towers can be upgraded either with a wider range or an increased power, in increments of 1. There is no hard limit to how many times a tower can be upgraded.

Range refers to how many spaces away from the tower that can be reached by the tower's abilities. A range of 0 means that only the space that the tower is on is affected by the tower's attacks.

Power has a different meaning depending on the kind of tower.

Turrets

Each turn, turrets fire at the invader within range that is farthest along the path to your village. They deal damage equal to the tower's power.

Turrets begin with a range of 1 and a power of 1.

Stunners

Stunners fire at the invader within range that is farthest along the path to your village. However, instead of dealing damage, they stun the invader for a number of turns equal to the tower's power. After firing, stunners cannot fire again for their power + 1 turns. Stunners will not fire at invaders that are already stunned.

Stunners begin with a range of 0 and a power of 3

Bombs

When an invader is on the same space as the bomb tower, it triggers and deals damage equal to its power to all invaders within its range. After being triggered, it cannot fire again for another 5 turns.

Bombs begin with a range of 2 and a power of 2

Invaders

Each turn, you may spawn an invader. At minimum, it costs 10 gold and has a base HP of 10. You can spend additional gold to increase its power:

  • (1G) +1 HP
  • (10G) +1 Defense (reduce damage taken by 1, but not lower than 1)
  • (10G) +1 Stun resistance (reduces stun time by 1 turn)

You are limited on the maximum stats. You start off unable to boost stats, but every 100 turns, the maximum increases by 5

There can only be one invader on each space of the board and invaders cannot pass through each other. You cannot spawn an invader if there is already an invader on the first space of the board. Therefore, a potential counterplay from defenders to prevent massive hordes of invaders is to put stunners on the first few spaces.

Coding

The main game / AI driver is here (still a work in progress)

Submission logistics TBD

Both players will have complete knowledge about the state of the game and will be allowed to maintain state from the beginning of the game. They may not directly modify the game state. Any attempts to do so will be disqualified as will any attempt to obfuscate such an attempt.

(api description will go here)

Defenders should return an object with an action property that is either 'build', 'upgrade', or 'destroy'. Each requires some additional properties to be set: (will add later)

Invaders should return an object which contains any stat boosts desired: hp, defense, and stunRes.

Both defenders or invaders may also return undefined or null to indicate not taking an action.

AIs must return their desired action in less than 10 milliseconds, averaged over 100 turns. Invalid actions returned by the AI will be ignored.

Scoring

All submissions will compete against all other submissions in a round-robin tournament. The bot that wins the most matches is declared the winner. In the event of a tie, the number of turns it took to win will be totaled for all winning matches with the smallest cumulative turn count to victory wins. In the unlikely event of a further tie, the turns to loss will be totaled for all losing matches and the bot with the highest cumulative turn count to loss wins.

Only one submission per user can be scored in the round-robin tournament.

Rules

  • No abusing standard loopholes
  • No direct modification of the game state passed to you. It will not be defensively deep-copied. Don't obfuscate your code to try to hide state modification.
  • Any uncaught exceptions will result in disqualification.
  • Implementations must be totally deterministic, i.e. random number generators are only allowed if seeded consistently (either with a constant or with game state) and must use isolated random state which the other AI in play cannot access.
  • Submissions shall include an explanation of the AI's strategy.
\$\endgroup\$
  • 2
    \$\begingroup\$ The biggest issue you are going to have here is balance. Making sure that the towers are evenly balanced and that both sides have a decent chance at winning each wave (in order to discriminate who is better). It may be worth building an actual simulation and actually playing the game before making it a challenge. \$\endgroup\$ – Nathan Merrill Apr 19 '18 at 18:59
  • 1
    \$\begingroup\$ I'd argue that this is just a king-of-the-hill. Cops-and-robbers have a drastically different posting format that you don't want, and we've already had challenges where there are different types of submissions \$\endgroup\$ – Nathan Merrill Apr 19 '18 at 19:01
  • \$\begingroup\$ Why don't you allow towers to be adjacent? It's easy to check if they have blocked all paths to the exist. Modifying the number of turns between rounds is useless as far as I can tell. It's far more effective to have massive waves than trying to join waves together. \$\endgroup\$ – Nathan Merrill Apr 19 '18 at 19:07
  • \$\begingroup\$ You should tag this with the language that submissions should be in. \$\endgroup\$ – Nissa Apr 23 '18 at 14:10
  • \$\begingroup\$ What constitutes an "obfuscated submission"? This needs to be defined more clearly. Side note: some people tend to write (subjectively) obfuscated code in the first place. \$\endgroup\$ – Alion Apr 24 '18 at 10:05
  • 1
    \$\begingroup\$ You should specify the base of the logarithms used in your calculations. \$\endgroup\$ – Alion Apr 24 '18 at 10:19
  • \$\begingroup\$ "Each Defender will face off against each Invader (not including any submissions by him)" should probably be reworded into "Each Defender will face off against each Invader, excluding pairs with identical authors". I had a hard time understanding the sentence. Also, this rule will heavily influence the results. Someone might post multiple fantastic Defenders and a decent Invader, and their Invader will have an easier time than the rest because it doesn't have to compete against the state-of-the-art. I know what you were trying to achieve, but a simple "don't cooperate" would probably suffice. \$\endgroup\$ – Alion Apr 24 '18 at 10:35
  • \$\begingroup\$ How does the damage scale with the power, exactly? "Power affects damage for bombs and turrets" probably isn't clear enough. Also, what is the base power of the stunner? I'd recommend rethinking and rewording that section in general - it feels clunky to read. \$\endgroup\$ – Alion Apr 24 '18 at 11:05
  • \$\begingroup\$ Nitpick: a one-dimensional "grid" can be called a tape, for example. \$\endgroup\$ – Alion Apr 24 '18 at 11:10
  • \$\begingroup\$ Oh, I completely misunderstood the way invader stats work. I thought they were permanent buffs. I have removed the relevant comments. \$\endgroup\$ – Alion Apr 24 '18 at 11:24
  • \$\begingroup\$ Is the stat boost limit cumulative or per stat? If I have a stat boost limit of 5, am I allowed to spawn an invader with +5 HP, +5 Defense and +5 Stun Resistance? \$\endgroup\$ – Alion Apr 24 '18 at 14:16
  • \$\begingroup\$ For a similar challenge structure, see: codegolf.stackexchange.com/q/51029/31203 \$\endgroup\$ – MegaTom Apr 25 '18 at 2:48
  • \$\begingroup\$ 1. The symmetry could be restored by making each entry both an invader and an attacker, with the win going to the first to wipe the other out. That introduces the need to balance your gold between attack and defence. 2. I'm not seeing any money awarded for destroying an invader. That's somewhat unusual for tower defence games. 3. There are some ambiguities. Does "already-stunned invader" mean previously stunned or currently stunned? Does "an invader is immediately in front of them" mean on the same square or on a square numbered one less? \$\endgroup\$ – Peter Taylor Apr 25 '18 at 10:33
  • \$\begingroup\$ @Alion an obfuscated submission would be one that deliberately tries to hide implementation details- especially if it tries to sneak in direct game state modification. For example, if you implemented a bot in JSFuck, that would obviously be obfuscated \$\endgroup\$ – Beefster Apr 26 '18 at 18:02
  • 1
    \$\begingroup\$ I have been creating a KoTH tower defence challenge in the background for a while and was a little saddened that you have beaten me to the punch... however after reading your spec, I think the tower defence challenge I am working on will have sufficently different mechanics to allow for both challenges to exist without being duplicates. I just need to get it to the point where it can be presented here in the sand box. That being said, I look forward to participating in your challenge. \$\endgroup\$ – Moogie Jul 20 '18 at 4:30
7
\$\begingroup\$

Give numbers space

Given a list of integers, adjust each number by at most ±1 so that in the resulting list, each number is at least 2 apart from each of its neighbors. That each, each entry n can be replaced with n-1, n, or n+1, and any two adjacent entries x and y must have abs(x-y) ≥ 2. The output is a list of the same length as the input.

You will not get an input where this is impossible, such as [5, 4, 4, 5]. The input will have at least two elements.

Examples (other outputs are possible):

[-5, -6] -> [-5, -7]
[1, 1, 1] -> [2, 0, 2]
[2, 2, 3, 3] -> [3, 1, 4, 2]
[0, 5, -1] -> [0, 5, -1]
[4, 4, 4, 4, 4, 4, 4, 3, 3, 3] -> [5, 3, 5, 3, 5, 3, 5, 2, 4, 2]
[4, 4, 4, 4, 4, 4, 4, 5, 5, 5] -> [3, 5, 3, 5, 3, 5, 3, 6, 4, 6]
[1, 1, 2, 4, 6, 7, 7] -> [2, 0, 2, 4, 6, 8, 6]
\$\endgroup\$
  • 5
    \$\begingroup\$ [5,4,4,5] is impossible I think. The two 4s have to become a 3 and a 5 to not be close to each other, and then whichever one becomes a 5, you can't adjust the other 5 away from it. \$\endgroup\$ – user62131 Nov 24 '16 at 5:21
  • 4
    \$\begingroup\$ Maybe this could be a decision problem then? \$\endgroup\$ – Zgarb Nov 24 '16 at 8:28
7
\$\begingroup\$

Lexicographically earliest valid UTF-8 byte sequence permutation

There are currently 1,114,112 possible Unicode characters (code points). Each character has a unique valid byte sequence in the UTF-8 encoding. Different characters have different length encodings:

  • ASCII characters have a 1-byte encoding 00-7F.
  • The next 1920 characters have a 2-byte encoding C2 80-DF BF.
  • The rest of the BMP has a 3-byte encoding E0 A0 80-ED 9F BF and EE 80 80-EF BF BF.
  • The other planes have a 4-byte encoding F0 90 80 80-F4 8F BF BF.

It's possible for two strings (specific non-normalised sequences of Unicode code points) of Unicode to have byte sequences that are permutations of each other in a number of ways:

  • One string could simply be a permutation of the other at the Unicode level, e.g. ab (61 62) and ba (62 61).
  • UTF-8 continuation bytes could be switched between two characters, e.g. ¡â (C2 A1 C3 A2) and ¢á (C2 A2 C3 A1).
  • UTF-8 continuation bytes could be switched within a character, e.g. (E1 B4 B5) and (E1 B5 B4).

For this challenge I would like you to write a program or function that finds the string whose UTF-8 byte sequence is lexicographically earliest of all such sequences that are permutations of the UTF-8 byte sequence of a given Unicode string.

For example, if your input is ᵴ¢ába (E1 B5 B4 C2 A2 C3 A1 62 61) your output would be ab¡âᴵ (61 62 C2 A1 C3 A2 E1 B4 B5).

Note however that some byte sequences are not valid UTF-8 (e.g. E0 80 A0 which is an overlong encoding for a space) so you need to take care to avoid these.

It would be helpful if your "Try It Online" or similar link includes a footer that helps demonstrate the correctness of your output, where this is not obvious from the I/O format or code.

This is , so the shortest program or function that breaks no standard loopholes wins!

\$\endgroup\$
  • 3
    \$\begingroup\$ For test cases, it will probably be a good idea to provide both strings and hex since I'd guess many languages will have to try both. Also this probably needs at least a link to an explanation of UTF8 continuation bytes. \$\endgroup\$ – FryAmTheEggman Jun 29 at 16:57
  • 1
    \$\begingroup\$ "permutation of its canonical" should be "permutation of the input's canonical". \$\endgroup\$ – Erik the Outgolfer Jun 29 at 17:00
  • 1
    \$\begingroup\$ @FryAmTheEggman ... but I provided the hex? I'm not sure what I'm missing... \$\endgroup\$ – Neil Jun 29 at 23:24
  • 1
    \$\begingroup\$ @EriktheOutgolfer How about "I would like you to write a program or function that returns the Unicode string whose canonical UTF-8 byte sequence is the lexicographically earliest of all such sequences that are permutations of the canonical UTF-8 byte sequence of a given Unicode string"? \$\endgroup\$ – Neil Jun 29 at 23:27
  • 1
    \$\begingroup\$ I meant in the example that you actually had, and presumably some number of test cases. I only mentioned it because I thought it was odd that you did it in the explanation but not the example. \$\endgroup\$ – FryAmTheEggman Jun 29 at 23:54
  • \$\begingroup\$ @Neil Looks good. :) \$\endgroup\$ – Erik the Outgolfer Jun 30 at 16:34
  • \$\begingroup\$ I'm wary of the use of the word "canonical" in this question, because it raises issues in my mind about normalisation of Unicode strings. I think that the intended challenge is really about byte arrays with constraints on the most significant bits, and I think it would be better to make that explicit (and to make the constraints explicit). \$\endgroup\$ – Peter Taylor Jul 2 at 11:16
  • \$\begingroup\$ @PeterTaylor There is that, but I wanted to exclude sequences such as E0 80 A0. \$\endgroup\$ – Neil Jul 2 at 13:23
  • \$\begingroup\$ @Neil, I think there's a miscommunication here. I'm saying that instead of talking about Unicode strings the question should explicitly state the FSS-UTF constraints on byte sequences, and maybe rule out encoding UTF-16 surrogate codepoints and codepoints greater than 0x10FFFF. \$\endgroup\$ – Peter Taylor Jul 2 at 13:48
  • \$\begingroup\$ @PeterTaylor OK but I really wanted this to be a string question rather than a byte sequence question... \$\endgroup\$ – Neil Jul 2 at 16:20
  • \$\begingroup\$ The problem then is dealing with the lexicographically first rearrangement of C3 A9 (é in normal form C) being 65 CC 81 (é in normal form D). \$\endgroup\$ – Peter Taylor Jul 2 at 16:29
  • \$\begingroup\$ @PeterTaylor Is that possible to do just by permuting the byte sequence? \$\endgroup\$ – Neil Jul 2 at 16:34
  • \$\begingroup\$ No, and that's why I'm arguing that the question should be phrased in terms of byte sequences rather than strings. \$\endgroup\$ – Peter Taylor Jul 2 at 17:40
  • \$\begingroup\$ There’s a mistake in the example: á is C3A1 and ¡ is C2A1. Good challenge. From the sound of it I/O will be flexible; this seems sensible since it keeps it open to more languages. \$\endgroup\$ – Nick Kennedy Jul 2 at 17:54
  • \$\begingroup\$ @PeterTaylor I wanted it to be clear that these byte sequences must be a valid UTF-8 encoding of a Unicode string. I've tried rewriting the question a bit... \$\endgroup\$ – Neil Jul 2 at 23:55
7
\$\begingroup\$

Compose Fill In The Blanks

\$\endgroup\$
  • \$\begingroup\$ Can you add some test cases? \$\endgroup\$ – MilkyWay90 Jul 27 at 14:35
  • \$\begingroup\$ @MilkyWay90 Ok I added some \$\endgroup\$ – Sriotchilism O'Zaic Jul 27 at 14:47
  • \$\begingroup\$ Okay, I give /support (also, you may want to add disallowing standard loopholes and using any default io method to finish it up) \$\endgroup\$ – MilkyWay90 Jul 27 at 14:48
  • 3
    \$\begingroup\$ @MilkyWay90 Those are already standard I am not going to be making my post any more cluttered with stuff that adds nothing. \$\endgroup\$ – Sriotchilism O'Zaic Jul 27 at 14:53
7
\$\begingroup\$

Move arrows along a contour

Posted here

\$\endgroup\$
  • \$\begingroup\$ I've edited in a question since it needs 2D for clarity. \$\endgroup\$ – Adám Jul 26 at 8:48
  • \$\begingroup\$ @Adám Only the arrows move. "+-|" always stay in place, or are "hidden" behind an arrow. So, you second example is correct (I deleted the first one) \$\endgroup\$ – Galen Ivanov Jul 26 at 9:02
  • \$\begingroup\$ Continuing @Adám's question: Are shapes always separated by at least one space, or can they be next to each other like ++++\n++++, and we have to determine if it's a ++++\n++++ or +--+\n+--+ based on the directions the arrows are facing? I.e. is this a possible/valid input, and are those outputs correct? \$\endgroup\$ – Kevin Cruijssen Jul 26 at 11:26
  • \$\begingroup\$ @GalenIvanov I didn't have anything but arrows move, and not it doesn't follow, because you couldn't tell what was behind the arrows, -s or +s which is what would make the two possible answers. \$\endgroup\$ – Adám Jul 26 at 11:28
  • 1
    \$\begingroup\$ @KevinCruijssen Example 2 has two adjacent shapes with no (vertical) spacing. \$\endgroup\$ – Adám Jul 26 at 11:29
  • \$\begingroup\$ @Adám Ah, you're right. As for your question however, you'd still know +<<+\n+>>+ is +--+\n+--+ due to the directions of the arrows in combination with the rule "when an arrow is on a corner, it keeps its current direction and changes it only after the turn is taken". See the pastebin in my previous comment for some test cases where you do know it's ++++\n++++ instead, because of the arrow directions. +^<+\n+>v+ will be two ++++\n++++ boxes, but +<<+\n+>>+ will be one +--+\n+--+ box. \$\endgroup\$ – Kevin Cruijssen Jul 26 at 11:37
  • \$\begingroup\$ @KevinCruijssen Good point, but OP actually never says that the input is an obtainable state, though it does make sense. I still have a feeling that there could be ambiguous cases. \$\endgroup\$ – Adám Jul 26 at 11:41
  • 1
    \$\begingroup\$ @KevinCruijssen The shapes will always be separated by at least one space, I'll add it to the description. \$\endgroup\$ – Galen Ivanov Jul 26 at 11:44
  • \$\begingroup\$ @GalenIvanov Probably better indeed to not have to deal with confusing ambiguous cases. In that case I would also have at least a newline separation, so test case 2 should be slightly modified. :) \$\endgroup\$ – Kevin Cruijssen Jul 26 at 11:45
  • \$\begingroup\$ @Adám Oh, I see - indeed I need to correct the second case to have a vertical space between the shapes. \$\endgroup\$ – Galen Ivanov Jul 26 at 11:51
  • 2
    \$\begingroup\$ Even single tracks can be incredibly difficult: [" ++ ","++++","++^+"," ++ "] only has one possible output: [" ++ ","++++","+++>"," ++ "] \$\endgroup\$ – Adám Jul 26 at 11:55
  • 2
    \$\begingroup\$ @AdámYes, this is the only output. Do you think a condition that sharp turns are forbidden will help? (this means no two + can be adjacent) \$\endgroup\$ – Galen Ivanov Jul 26 at 12:21
  • 1
    \$\begingroup\$ @GalenIvanov Maybe that's indeed better to reduce confusion and make the challenge someone more manageable. Although you can still deduct the solution in Adam's comment above, having no spaces inside the space makes it rather difficult to parse correct. Always having at least one |/- between two + will always give the shapes always spaces, making it easier to parse individual shapes. In which case Adam's one would become [" +-+ "," | | ","+-+ +-+","| |","+-+ ^-+"," | | "," +-+ "] -> [" +-+ "," | | ","+-+ +-+","| |","+-+ +>+"," | | "," +-+ "] \$\endgroup\$ – Kevin Cruijssen Jul 26 at 13:55
  • \$\begingroup\$ @KevinCruijssen Thanks, I added clarification. \$\endgroup\$ – Galen Ivanov Jul 26 at 14:09
  • 1
    \$\begingroup\$ @GalenIvanov Maybe also change the one Adam edited in, since it's still with ++ below one-another. :) \$\endgroup\$ – Kevin Cruijssen Jul 26 at 15:08
6
\$\begingroup\$

Do-nothing Polyglot

This challenge requires you to write a polyglot which contains a comment in as many languages as possible.

The comment must say This is a polyglot comment.

The program must do nothing at all.

Besides comments, your code may contain no-ops from the language(s) you are using, if it helps incorporate more languages into your answers. For example in bash we could use :. Or in the family, something like the following may be used, as long as it compiles:

if (0) {
    statements with side effects
}

Since this is a challenge, the answer with the most languages wins, so I think this should also be tagged

\$\endgroup\$
  • \$\begingroup\$ I think it is funny that the content of the comment makes it so that H9+ cannot be included. Yes, tag it [code-challenge]. \$\endgroup\$ – Justin Mar 16 '14 at 2:27
  • \$\begingroup\$ Many languages use # or // to signify comments. Perhaps restricting the counting so that each type of comment is counted only once. In other words, //This is a polyglot comment would only count for 1 language, not fo C, C++, Java, ... \$\endgroup\$ – Justin Mar 16 '14 at 5:13
  • 4
    \$\begingroup\$ What is a "program" for the purposes of this question? In particular, are compiled languages going to be excluded because the compiler won't be able to find an entry point? \$\endgroup\$ – Peter Taylor Mar 16 '14 at 17:33
  • \$\begingroup\$ What does no-ops mean? \$\endgroup\$ – Mhmd Mar 18 '14 at 17:37
  • 2
    \$\begingroup\$ I think that in some esolangs it's not entirely decided what counts as a comment. Maybe you should say that the code must contain the text this is a polyglot comment. \$\endgroup\$ – Esolanging Fruit Mar 16 '17 at 4:24
  • \$\begingroup\$ Thanks! Posting this (after I edit it) \$\endgroup\$ – Christopher May 2 '17 at 20:40
  • \$\begingroup\$ Yeah I removed the post as it was horrible and not well recived \$\endgroup\$ – Christopher May 16 '17 at 15:17
  • 1
    \$\begingroup\$ FYI, this is rosetta-stone. \$\endgroup\$ – programmer5000 Aug 1 '17 at 11:01
6
\$\begingroup\$

You say goodbye, and I say hello

In this challenge, you have to make a program that outputs Hello, World!. That's not all though! When the program is reversed, it has to output Goodbye, World!.

Unfortunately, there are a few boring rules:

  • No using comments, i.e., the Python code print"Hello, World!"#"!dlroW ,eybdooG"tnirp is illegal

This is , so try to do it in the least number of bytes.

(Should the forwards/backwards tasks be changed? I think they are probably too easy. Let me know if you have any suggestions.)

\$\endgroup\$
  • 2
    \$\begingroup\$ You're missing a golden opportunity to make a Beatles reference. \$\endgroup\$ – a spaghetto Nov 4 '15 at 18:11
  • 2
    \$\begingroup\$ This is a good point. Typically in good palindrome challenges at least comments should be banned; you can take a look at this for some examples of good rules in a palindrome challenge. \$\endgroup\$ – a spaghetto Nov 5 '15 at 21:06
  • 1
    \$\begingroup\$ @quartata Thank you for the example! This is what the sandbox is good for. \$\endgroup\$ – DanTheMan Nov 6 '15 at 17:35
  • 1
    \$\begingroup\$ Your answer may...? :) \$\endgroup\$ – trichoplax Nov 8 '15 at 1:07
  • \$\begingroup\$ Do you think I can just go ahead and post this as a challenge? \$\endgroup\$ – DanTheMan Nov 9 '15 at 18:05
  • 2
    \$\begingroup\$ What counts as a comment? Unexecuted code? Strings which are pushed and never used? etc etc \$\endgroup\$ – Sp3000 Nov 10 '15 at 10:06
  • \$\begingroup\$ I don't think it's too easy. Easy questions get lots of answers and therefore plenty of upvotes for you. That said, there's probably a duplicate or near duplicate out there somewhere. \$\endgroup\$ – Level River St Nov 16 '15 at 10:43
  • \$\begingroup\$ it makes lots of language impossible. Maybe comment have penalty \$\endgroup\$ – l4m2 Dec 31 '17 at 14:43
6
\$\begingroup\$

What shape is that polygon?

Given an ASCII figure made of /, \, |, and _, write a program that determines (1) if the figure is a closed, non-self-intersecting polygon (meaning it has at least three sides that connect to form a loop), and if so, (2) how many sides the polygon has and (3) if the polygon is convex (all internal angles are less than 180˚) or concave (not convex, note that no polygons have 180˚ angles).

The multiline input is the ASCII figure. It can be assumed that the input only contains the four characters listed above.

If the figure is not closed or self-intersects (or has more than 2 sides connecting at the same point), the program should print Not a polygon.

The number of sides the polygon has is determined by the following chart.

Sides   Name
3       Triangle
4       Quadrilateral
5       Pentagon
6       Hexagon
7       Heptagon
8       Octagon
9       Nonagon
10      Decagon
11      Undecagon
12      Dodecagon
>12     n-gon (where n is the number of sides)

The output should be in the format <concavity> <polygon name> if (1) is satisfied.

Test cases

  __
 /  \__
/_____/

==> Concave hexagon


/\/\/\/\/\/\/\
|____________/

==> Concave 17-gon


 _____/
|_____|

==> Not a polygon


 _
/ \
| |
\_/

==> Convex octagon

I need a little assistance on getting stricter definitions of points intersecting, so help would be appreciated. Thanks!

\$\endgroup\$
  • 1
    \$\begingroup\$ I like the concept of this challenge. A good test case would be including a line that goes inside the polygon as well as lines that doesn't even touch the polygon (unless you are going to guarantee that they will touch) \$\endgroup\$ – Nathan Merrill Dec 6 '15 at 19:45
  • \$\begingroup\$ Your first two examples look wrong: those polygons are clearly concave. \$\endgroup\$ – Peter Taylor Dec 7 '15 at 9:45
6
\$\begingroup\$

Capsa, a card game KotH!

Capsa, known by many times, including the name Big Two in English, is a popular card game in East Asia and South East Asia, especially throughout China, Hong Kong, Indonesia, Macau, Malaysia, Singapore and Taiwan. There are many variations and house rules. The rules of this particular variation are thus:

  • This game will be played between exactly four bots. The cards are dealt between everyone, so that everyone has 13 cards.
  • Rank is ordered with 2s before As as follows: 2, A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, hence, the name Big Two.
  • Suits are ordered as follows: Spades, Hearts, Clubs, Diamonds
  • Ordering runs rank first then suit. Thus, 7 of Hearts > 7 of Diamonds > 6 of Hearts, the lowest card is the 3 of Diamonds, and the highest, the 2 of Spades

You can play cards in sets of one, two or five cards, (singles, pairs, or five-card poker hands). Each set must always be bigger than the one before.

With singles, play may proceed in this way: 1 3H, 2 4H, 3 5D, 4 5C, 1 10S, 2 Pass, 3 JD, 4 Pass, 1 2S, 3 Pass

Pairs are ordered by the higher suit in the pair. 6C6H is of a lower rank than 6D6S. Play may proceed in this way: 3 3D3C, 4 6D6H, 1 6D6S, 2 JHJS, 3 Pass, 4 ADAC, 1 Pass, 2 Pass

Poker hands are ordered in the following way, from lowest in rank to highest in rank:

  • Straight: Five cards that are consecutive in rank, e.g. 6H 7S 8D 9H 10C or JS QH KD AS 2C. Rank is determined by the highest card, with suit used as a tie-breaker.
  • Flush: Five cards with the same suit, e.g. 5H 7H 10H QH AH Rank is determined first by suit, then by highest card.
  • Full house: A three of a kind with a two of a kind, e.g. JD JS JH 3D 3S. Rank is determined by the triple, without regard for the pair.
  • Straight flush: Five cards that are consecutive in rank and are all of the same suit, e.g. 6H 7H 8H 9H 10H. Ranked the same as straights, with suit as a tie-breaker
  • Four-of-a-kind: Four cards of the same rank, with any 5th card, e.g. 9D 9C 9H 9S 4S This hand is known as the bomb. Wins any round of poker hands it is played in, unless someone else plays their own bomb.

Any five-card hand that is higher than the previous five-card hand played is eligible. For example, you can play a full house on a straight.

Rules of play:

  • At the beginning of the game, the cards are dealt between everyone, so that everyone has 13 cards. The first player is the one that holds the 3 of Diamonds and they must play this card first, whether singly, with another 3 in a pair, or in a poker hand.
  • A round begins with the first player playing a single card, a pair or a poker hand. Every other player either respond with the same number of cards (you must play singles on singles, never a pair or a poker hand), or that player passes for that round.
  • A player may pass even when they have a playable card, but they must pass if none of their cards are high enough in rank, that is, if they have no playable cards. For example, in a round of poker hands, if you only have a flush as a five-card set, but another player has already played a full house, you must pass, as your flush is too low.
  • The round ends when all but one player passes. That last player wins the round and starts the next round.
  • The game ends when one player has played all of their cards.

Possible scoring systems:

  • Bots are judged by the number of games they win over (TBD) games that they play. So if we have seven bots to test, we'll play them until every bot has played more than (TBD) games.
  • Bots are judged by the number of cards they have left at the end of the game. (The winner will obviously have 0 cards at the end of the game).

Here is the link to a preliminary controller and two bots to test against.

\$\endgroup\$
  • 1
    \$\begingroup\$ "The cards are dealt between everyone, so that everyone has 13 cards" belongs in the "rules of play" section, even if that means having to repeat it. \$\endgroup\$ – Peter Taylor Dec 30 '15 at 11:09
  • \$\begingroup\$ @PeterTaylor Done. If you have any comments on the controller linked at the bottom of this post, I'd love to hear them. Thanks \$\endgroup\$ – Sherlock9 Dec 30 '15 at 11:27
6
\$\begingroup\$

Reverse the lengths


Specification

In this challenge, your task is to reverse the lengths of an array-of-arrays, while keeping its concatenation intact.

More explicitly, your input is an array of arrays of nonnegative integers, which you may assume to fit in the native int type of your language. The input may be an empty array or an array of empty arrays, or it may contain arrays of different lengths. You can take the input in any reasonable format.

Your output shall be another array of arrays, again in any reasonable format. The concatenation of the output shall be equal to the concatenation of the input, so it contains the same integers in the same order. However, the sequence of lengths in the output shall be the reverse of that of the input.

Example

Consider the input array

A = [[4,10],[0],[],[3,3,2],[1]]

The concatenation of A is

B = [4,10,0,3,3,2,1]

and its length sequence is

C = [2,1,0,3,1]

The correct output is

[[4],[10,0,3],[],[3],[2,1]]

since it's the unique array with concatenation B and length sequence reverse(C).

Rules and scoring

You con write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test cases

TODO: make more

[] -> []
[[]] -> [[]]
[[],[],[1]] -> [[1],[],[]]
[[1,2],[4,5,6]] -> [[1,2,4],[5,6]]
[[4,10],[0],[],[3,3,2],[1]] -> [[4],[10,0,3],[],[3],[2,1]]

Sandbox comments

I'm debating whether I should guarantee that the input is non-empty, and/or only contains non-empty arrays. In some languages (like J), empty arrays make the challenge significantly harder, but on the other hand, I don't want it to be too easy either.

\$\endgroup\$
  • \$\begingroup\$ Just an FYI "reshape" operations pretty heavily trivialise this. I don't think it would be crazy to ban them, but it's probably fine with them also. \$\endgroup\$ – FryAmTheEggman Jun 7 '16 at 17:12
  • \$\begingroup\$ I'd prefer the more general challenge of splitting an array the same way as another array of arrays with equally many elements. \$\endgroup\$ – xnor Jun 8 '16 at 0:28
  • \$\begingroup\$ @FryAmTheEggman I'd prefer not to explicitly ban any builtins. If that leads to 3-byte Jelly answers, so be it. :P I also suspect Jelly would win anyway... \$\endgroup\$ – Zgarb Jun 8 '16 at 14:35
  • \$\begingroup\$ @xnor That would be essentially be this challenge, but with only arrays-of-arrays. Do you think they would be different enough not to be duplicates? \$\endgroup\$ – Zgarb Jun 8 '16 at 14:39
  • \$\begingroup\$ Even if the depth is fixed at 2, the shortest approach would most likely still be the be the same in many languages. It's a borderline dupe, and since it takes only one gold badge user to close a duplicate, it will probably end up closed. \$\endgroup\$ – Dennis Jun 8 '16 at 17:23
  • \$\begingroup\$ @Zgarb I'm not sure if I'd count it as a dupe, but I think reversed input vs general array wouldn't make much difference there. I expect most solutions would just work with the reversed input as if it were a general array. \$\endgroup\$ – xnor Jun 8 '16 at 20:50
  • \$\begingroup\$ @xnor Reversed input has the added complexity that the same array must be used for content and shape. That's not a big problem for some languages, but I'd expect another approach to outgolf the pop/map approach with the added overhead of creating a second reference for the reversed array in, e.g., Python. I admit I haven't tried it yet though. \$\endgroup\$ – Dennis Jun 9 '16 at 0:24
  • \$\begingroup\$ I think what you call "concatenation" of the array is called "flattening". \$\endgroup\$ – Erik the Outgolfer Oct 13 '16 at 18:24
6
\$\begingroup\$

The Secret Handshake

This is based off of this sandbox comment.


This is a challenge of secrecy.

The goal of this KOTH is to write a program that is capable of identifying itself amongst a crowd of other programs. In order to do this, you must develop a secret handshake which will be recognized only by other copies of the same program.

A single game involves every program competing at once. There will be five instances of each program in the arena, and the winner will be the first program to correctly identify the four other copies. After a large number of games, the submission with the most victories will be the overall winner.

The Gameflow:

  1. Each program receives a number which tells the number of bots in the arena, which is five times the number of submissions. The bots are arranged in a circle, and they are each considered ID #0 from their own perspective, with N-1 being the maximum ID number.
  2. Then the game cycle starts. At this point, each bot will be awaiting input.
    1. Your bot will receive input consisting of an ID number and an optional message.
      • For example, 7 hi means that bot #7 said hi to you.
      • If the ID number is 0, then there will not be a message. This would occur if it is your turn but there is no message to receive.
    2. Now, your bot is allowed to output a guess consisting of four ID numbers.
      • If those four numbers are the IDs of your teammates, then your team will win that game.
      • You will receive no confirmation of an incorrect guess.
    3. Next, you must output a message to send. The message will be a destination ID number followed by up to 3* characters. Example messages: 7 4 w 12 #?Q.

*This number is subject to change. Larger messages make it harder to fake a secret handshake. I hope that a very short message forces people to use multi-step handshakes. It might also be interesting to limit it to 1-character messages.

Sandbox Notes

Something that I haven't quite figured out is how the controller program will determine which bot gets to move each turn. I suppose it would be simplest go in order: Each bot has an "unread message queue" and receives/sends one message each turn. The bot immediately after you (ID #1) then moves next.

Alternatively, there could be a set turn order which is unrelated to the ID order, simply to make it impossible for one bot to tell which bot moves next.

\$\endgroup\$
  • \$\begingroup\$ 1. I don't think it needs a turn order: the only problem with adding simultaneous moves would be the need to account for ties. (You are going to run it more than once to pick a winner, right?) 2. I would keep the guess per turn without penalty for guessing wrong. A good strategy will allow a team to win before anyone wins by blind guessing. Too harsh a penalty for bad guesses will bias the game too much in favour of the last person to update their bot so that it fakes the responses of other teams. \$\endgroup\$ – Peter Taylor Nov 11 '14 at 10:43
  • 3
    \$\begingroup\$ The idea is quite amusing, but something tells me there must exist a not too hard to find optimal strategy to maximize the chances of winning. The fight would likely occur around sending fake messages to the competitors. Second problem I see is, the first contestants will be at a huge disadvantage since the new players will see exactly how their code works. So much for secrecy. I think the challenge would be more interesting if the code was kept secret, but this is hardly compatible with the spirit of this site. \$\endgroup\$ – user16991 Jan 24 '15 at 6:48
  • \$\begingroup\$ @PhiNotPi are you still interested in this challenge? Would you be willing to allow me to implement this? \$\endgroup\$ – Rohan Jhunjhunwala Jul 29 '16 at 20:23
  • \$\begingroup\$ @RohanJhunjhunwala Sure, you can implement this. I don't think I ever started on a controller for it, mainly because I don't think this challenge will be as fun in practice as in theory. \$\endgroup\$ – PhiNotPi Jul 30 '16 at 13:17
6
\$\begingroup\$

There can be only 1!

Your task is, given a positive integer n, to generate an expression that equals to the number n.

The catch is: you're only allowed the number 1 in the output.

The operators at your disposal are:

  • +, -, * and /
  • sqrt (as s)
  • ceil and floor (as c and f respectively)
  • ! (factorial)
    • The factorial, in this case, only works for positive integers.

You are also allowed to stack 1's together, so something like 11 is acceptable in the output. However, they count as the same amount of 1's that's in the number (so 11 counts as 2 1's).

You must also include brackets in the output, so that the expression in the output, when executed through the order of operations, will result in the input.

Examples:

  • Input = 24, one possible output = (1+1+1+1)!
  • Input = 11, one possible output = 11
  • Input = 5, one possible output = c(s((1+1+1+1)!))
    • The ceiling of the square root of 24 is 5.

Rules:

  • You are guaranteed that the input is a positive integer from 1 to 2^31-1.
  • Your program must work for any positive integer up to 2^31-1, even if they are not tested.
  • Your program must finish processing all outputs for all numbers in the set in 1 hour.
  • The results for every run of the program must be exactly the same - also, no seeds.
  • You are not allowed to have imaginary numbers anywhere in the output (so no s(some negative number)).
  • You are also not allowed to have numbers larger than 2^31-1 anywhere in the output, even when they are sqrted or /ed (so no (((1+1+1)!)!)! or ((1+1+1+1)!)!).

Set of Numbers:

945536, 16878234, 32608778, 42017515, 48950830, 51483452, 52970263, 54278649, 63636656, 78817406, 89918907, 90757642, 95364861, 102706605, 113965374, 122448605, 126594161, 148064959, 150735075, 154382918, 172057472, 192280850, 194713795, 207721209, 220946392, 225230299, 227043979, 241011012, 248906099, 249796314, 250546528, 258452706, 276862988, 277140688, 280158490, 286074562, 308946627, 310972897, 322612091, 324445400, 336060042, 346729632, 349428326, 352769482, 363039453, 363851029, 392168304, 401975104, 407890409, 407971913, 425780757, 459441559, 465592122, 475898732, 482826596, 484263150, 506235403, 548951531, 554295842, 580536366, 587051904, 588265985, 588298051, 590968352, 601194306, 607771869, 618578932, 626776380, 667919873, 681786366, 689854904, 692055400, 697665495, 711608194, 734027104, 750869335, 757710567, 759967747, 777616154, 830071127, 833809927, 835873060, 836438554, 836945593, 863728236, 864158514, 871273503, 881615667, 891619600, 897181691, 918159061, 920521050, 924502226, 929983535, 943162304, 950210939, 950214176, 962610357, 974842859, 988572832

(These are 100 random numbers from 1 to 1 billion.)

Scoring System:

Your score is determined like so:

  • Your program will be tested against the random numbers in the set.
    • You must provide the output generated using the numbers random numbers in the set (either inside your answer or as a pastebin link).
  • Your then have two "scores": A primary score and a secondary score.
    • Your primary score is (no. of 1's in output)*(no. of operators in output). If your primary score is the lowest, you win.
    • Your secondary score is your byte-count, and is only used in the case of a tie-breaker - the person with the lowest byte-count wins.

Meta:

  • Anything that I need to clear up?
  • Is this challenge a dupe?
\$\endgroup\$
  • \$\begingroup\$ Is implicit multiplication allowed? \$\endgroup\$ – LegionMammal978 Sep 11 '16 at 1:23
  • \$\begingroup\$ @LegionMammal978 No, it is not allowed. You must use *. \$\endgroup\$ – Qwerp-Derp Sep 11 '16 at 1:43
  • \$\begingroup\$ For the tiebreak, do parentheses contribute to the operator count? \$\endgroup\$ – trichoplax Sep 11 '16 at 1:49
  • \$\begingroup\$ Does the code need to be deterministic (that is, do random algorithms need to set the PRNG seed to ensure the same results each time)? \$\endgroup\$ – trichoplax Sep 11 '16 at 1:51
  • \$\begingroup\$ Surely at least one output must be hardcoded? \$\endgroup\$ – Jonathan Allan Sep 11 '16 at 4:45
  • \$\begingroup\$ Related, though I don't believe it's a dupe. \$\endgroup\$ – ETHproductions Sep 11 '16 at 8:47
  • \$\begingroup\$ code-challenge can't be used along with other scoring tags. \$\endgroup\$ – Erik the Outgolfer Sep 11 '16 at 11:18
6
\$\begingroup\$

Telegraphy Golf: Decode Baudot Code

Background

In 1870 Émile Baudot invented Baudot Code, a fixed-length character encoding for telegraphy. He designed the code to be entered from a manual keyboard with just five keys; two operated with the left hand and three with the right:

Baudot 5-key keyboard

The right index, middle and ring fingers operate the I, II, and III keys, respectively, and the left index and middle fingers operate IV and . (Henceforth I'll use their Western Arabic numerals, i.e. 1, through 5.) Characters are entered as chords. To enter the letter "C," for example, the operator presses the 1, 3, and 4 keys simultaneously, whereupon a rotating brush arm reads each key in sequence and transmits a current or, for keys not depressed, no current. The result is, in modern terms, a 5-bit least-significant-bit-first binary encoding, in which our example, "C," is encoded as 10110.

5 bits??

You might be thinking that 5 bits, which can express at most 32 unique symbols, isn't enough for even all of the English letters and numerals, to say nothing of punctuation. Baudot had a trick up his sleeve, though: His character set is actually two distinct sets: Letters and Figures, and he defined two special codes to switch between them. Letter Shift, which switches to Letters mode, is activated by pressing the 5 key alone (00001), and Figure Shift is activated with the 4 key (00010).

Challenge

Your challenge is to write a program or function that decodes Baudot Code transmissions.

A real transmission would begin with some initialization bits, plus a start and stop bit before and after each character, but we're going to skip those and only worry about the 5 unique bits for each character. Input and output formats are discussed below.

Baudot's Code

There are two different versions of Baudot Code: Continental and U.K. We're going use the U.K. version, which doesn't include characters like "É" from Baudot's native French. We're also going to leave out all of the symbols in the U.K. version that aren't among the printable ASCII characters. You will only have to decode the characters in the table below, all of which are printable ASCII characters except the final three control characters that are explained below the table.

The "Ltr" column shows the characters in Letter mode and "Fig" shows the Figure mode characters:

        Encoding             Encoding
Ltr Fig  12345       Ltr Fig  12345
--- --- --------     --- --- --------
 A   1   10000        P   +   11111
 B   8   00110        Q   /   10111
 C   9   10110        R   -   00111
 D   0   11110        S       00101
 E   2   01000        T       10101
 F       01110        U   4   10100
 G   7   01010        V   '   11101
 H       11010        W   ?   01101
 I       01100        X       01001
 J   6   10010        Y   3   00100
 K   (   10011        Z   :   11001
 L   =   11011        -   .   10001
 M   )   01011        ER  ER  00011
 N       01111        SP  FS  00010
 O   5   11100        LS  SP  00001
 /       11000

The last three rows in the right column are control characters:

  • ER is Erasure. Baudot's telegraphy machines would print an asterisk-like symbol for this character to tell the reader that the preceding character should be ignored, but we're going to be even nicer to the reader and actually omit (do not print) the preceding character. It acts the same in both Letter and Figure mode.

  • FS is Figure Shift. This switches the character set from Letters to Figures. If the decoder is already in Figure mode, FS is treated as a Space (ergo SP in the "Ltr" column). When the decoder is in Figure mode it stays in Figure mode until an LS character is received.

  • LS is Letter Shift. It switches the character set from Figures to Letters. If the decoder is already in Letter mode, LS is treated as a Space. When in Letter mode the decoder stays in Letter mode until an FS character is received.

The decoder always starts in Letter mode.

Here's an example with Figure Shift, Letter Shift, and Space:

01011 10000 00100 00001 00010 10000 11100 00001 10101 11010
  M     A     Y   LS/SP FS/SP   1     5   LS/SP   T     H

This yields the message MAY 15TH. As you can see, the first 00001 (Letter Shift/Space) character acts as a space, because the decoder is already in Letter mode. The next character, 00010 (Figure Shift/Space) switches the decoder to Figure mode to print 15. Then 00001 appears again, but this time it acts as Letter Shift to put the decoder back in Letter mode.

For your convenience, here are the characters in a format that's perhaps easier to digest in an editor, sorted by code:

A,1,10000|E,2,01000|/,,11000|Y,3,00100|U,4,10100|I,,01100|O,5,11100|SP,FS,00010|J,6,10010|G,7,01010|H,,11010|B,8,00110|C,9,10110|F,,01110|D,0,11110|LS,SP,00001|-,.,10001|X,,01001|Z,:,11001|S,,00101|T,,10101|W,?,01101|V,',11101|ER,ER,00011|K,(,10011|M,),01011|L,=,11011|R,-,00111|Q,/,10111|N,,01111|P,+,11111

Input

Input will be a string, array, or list of bits in least-significant-bit-first order. Each character will be represented by a quintet of 5 bits. Bits may be in any reasonable format, e.g. a binary string, an array of 0s and 1s, a string of "0" and "1" characters, a single very large number, etc., as long as it maps directly to the bits of the transmission.

Every transmission will have at least one printable quintet and at most 255 quintets (printable or otherwise), i.e. 5–1,275 bits inclusive.

The input can contain only the bits of the transmission, with two allowed exceptions: Any number of leading or trailing 0 bits and/or, for string input, a single trailing newline may be added to the transmission. Leading or trailing bits or characters cannot be added before or after each quintet, i.e. you cannot pad each quintet to 8 bits or separate quintets with any additional bits, e.g. "01111\n11100".

Notes & edge cases
  1. The transmission will contain only the characters in the "Ltr" and "Fig" columns in the table above. You will never receive e.g. 01110 in Figure mode, because it is absent from the "Fig" column.

  2. It is assumed that the decoder will always be in Letter mode at the beginning of a transmission. However, the first character may be an FS character to switch to Figure mode immediately.

  3. When the decoder is in Letter mode, it may receive an LS character, and when it is in Figure mode it may receive an FS character. In either event a Space character must be printed (see Output).

  4. The ER character will never be the first character in a transmission, nor will it ever immediately follow an LS, FS, or another ER.

  5. An FS character may immediately follow an LS character and vice versa.

  6. Neither the LS nor FS character will be the last character in any transmission.

  7. The / and - characters may be received in either Letter mode (codes 11000 and 10001, respectively) or Figure mode (10111 and 00111).

Output

Output may be in any reasonable format, the most reasonable being ASCII (or UTF-8, for which all of the represented characters are the same as ASCII). Please indicate in your answer if your output is in another encoding or format.

Notes
  • The space character (see 3. above) should be an ASCII space (0x20) or your encoding's equivalent, i.e. what you get when you press the space bar.

Winning

This is code golf. The shortest code in bytes wins.

Restrictions

  • Standard loopholes are forbidden.

  • Trailing spaces and/or a single trailing newline are allowed. Leading spaces or other characters (that are not part of the transmission) are disallowed.

  • You may not use any built-in or library functions that decode Baudot Code (or any of its descendants, e.g. Murray Code, ITA-1, etc.).

Test Cases

Input: 001101000010100111101110010101
Output: BAUDOT
Input: 11010010001001100011110111101111100
Output: HELLO
Input: 01011100000010000001000101000011100000011010111010
Output: MAY 15TH
Input: 00010001000001000001011101110011100101010010110101010001111100101
Output: 32 FOOTSTEPS
Input: 10110000110101011100111100001111011010000001101110
Output: GOLF
Input: 000100011000001111100000100010110111001100010110010000111111
Output: 8D =( :P
Input: 0000100001000010000100010001111011111011000011100010001
Output (4 leading spaces):     -/=/-
\$\endgroup\$
  • \$\begingroup\$ This is quite similar to the Morse decoding question. The main thing it adds is the three control characters. It might be worth adding a cross-reference in a comment after posting the question. \$\endgroup\$ – Peter Taylor Sep 19 '16 at 21:56
  • 1
    \$\begingroup\$ Can the transmission start with erasure? \$\endgroup\$ – Sp3000 Sep 20 '16 at 1:00
  • \$\begingroup\$ @Sp3000 No. Good catch. I had a note to that effect but apparently accidentally deleted it. \$\endgroup\$ – Jordan Sep 20 '16 at 1:07
  • \$\begingroup\$ Can an erasure follow a shift that is acting as a space? \$\endgroup\$ – Phlarx Sep 20 '16 at 14:16
  • \$\begingroup\$ @Phlarx Nope. ER will never follow LS or FS. \$\endgroup\$ – Jordan Sep 20 '16 at 14:17
  • \$\begingroup\$ Thank you for your feedback, all. I've posted the challenge: codegolf.stackexchange.com/questions/94056/… \$\endgroup\$ – Jordan Sep 21 '16 at 13:23
  • \$\begingroup\$ Don't forget to take of this answer in the Sandbox. " 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. " \$\endgroup\$ – Linus Sep 22 '16 at 19:29
6
\$\begingroup\$

my first post on here, be gentle ;)


Find all anagrams within a text

Somehow I stumbled upon an implementation of a school assignment from about a year ago, and after having seen many amazing and mindblowing code-golf solutions on here, I thought it's time I bring my own challenge and see how much you guys can blow my mind again ;)

The assignment

Given a text, find all words that have at least one other word in the text as an anagram (case insensitive). Multiple occurrences of the same word are not counted.

The output shall be grouped by words that are an anagram of each other.

Rules

  • How you handle input/output is up to you. Function-parameters, file-io, standard in/out, whatever works the best for you.
  • You must be able handle any non-empty input as long as you don't run into language or memory limitations.
  • The output does not have any fixed formatting. That means you may put them each group at a line, or put them all at one line but use different delimiters, a 2d array, some other exotic data-structure your language of choice happens to have, as long as it makes reasonable sense, it is considered correct. (This means that for example if you are just writing a function, that function does not need to display the output, it could just provide it as a return-value.) Just keep in mind the requirement that the words that are an anagram of each other should be grouped together.
  • The order in which the output appears does not matter. That applies to the order of the groups as well as the order of the words within the group.
  • A group of only one word is invalid, since that fails the "have at least one other word in the text as an anagram" requirement. (just omit them from your output ^^)
  • Each word should only appear once in the output
  • All interpunction characters are stripped away from the word before checking for anagrams. That means that "it's" and "its" are the same word (and thus both are an anagram of "sit"). My sample program at the bottom uses http://en.cppreference.com/w/cpp/string/byte/ispunct as check if a character is an interpuntion character. If your language has such a method, you may use it. Otherwise take the characters from the default C locale as specified on there:

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

  • All other characters are part of the word and treated as is, so "a" and "á" are not the same.

Example

Given the following input text (the actual text I was given as example by school :P, no idea where this text is coming from...)

Parts of the world have sunlight for close to 24 hours during summer. Dan went to the north pole to lead an expedition during summer. He had a strap on his head to identify himself as the leader. Dan had to deal with the sun never going down for 42 consecutive days and his leadership strap soon became a blindfold. He wondered what kind of traps lay ahead of him.

the following output would be correct:

  • 24, 42
  • deal, lead
  • and, dan
  • parts, strap, traps

Or this would also be correct:

24, 42 | deal, lead | and, dan | parts, strap, traps

This one would not

24, 42 , deal, lead , and, dan , parts, strap, traps

(since the groups are not obvious)

My own (non golfed) version to check

The is the exact program I submitted to school back then. You may use it to check your own results.

Added bonus: If it happens to be that this program has a bug (I haven't found them yet) your submission is allowed to have it as well, since it is used to check the result. (In that case you are of course not required to have said bugs)

#include <string>
#include <iostream>
#include <fstream>
#include <map>
#include <set>
#include <algorithm>
#include <cstring>

void stringRemoveInterpunction(std::string& string);
void stringToLower(std::string& string);
std::string stringToAnagramIdentifier(std::string word);

/**
 * due to use of std::ispunct and std::tolower it may not work for text with non-ascii characters??!
 */
int main(int argc, char* argv[]) {
    if (argc < 2) {
        std::cerr << "usage: " << argv[0] << " <filename>" << std::endl;
        return 1;
    }

    std::ifstream fileStream(argv[1]);
    if (!fileStream) {
        std::cerr << "Could not open file " << argv[1] << std::endl;
        return 2;
    }

    // map to store the anagrams, key is so called "anagram identifier", value is a list of the words.
    std::map<std::string, std::set<std::string>> anagrams;

    // read words separated by whitespace from the file
    for (std::string word; fileStream >> word;) {
        // remove interpunction & convert to lowercase, since casing should be ignored
        stringRemoveInterpunction(word); stringToLower(word);

        // add to anagrams-store
        anagrams[stringToAnagramIdentifier(word)].insert(word);
    }

    // display all the anagrams
    for (auto anagram : anagrams) {
        // skip entries which contains only one item, no anagrams found
        if (anagram.second.size() <= 1) {
            continue;
        }

        // output a comma-separated list of the anagrams
        auto anagramIterator = anagram.second.begin();
        std::cout << *anagramIterator++;
        while (anagramIterator != anagram.second.end()) {
            std::cout << ", " << *anagramIterator++;
        }
        std::cout << std::endl;
    }

    return 0;
}

void stringRemoveInterpunction(std::string& string) {
    string.erase(std::remove_if(string.begin(), string.end(), std::ptr_fun<int, int>(&ispunct)), string.end());
}

void stringToLower(std::string& string) {
    std::transform(string.begin(), string.end(), string.begin(), std::ptr_fun<int, int>(&std::tolower));
}

std::string stringToAnagramIdentifier(std::string word) {
    // sort the characters
    std::sort(word.begin(), word.end());
    return word;
}

Sandbox Questions

  • Do i need to add other tags, or is just code-golf enough?
  • I'm not completely sure about the upper-limit of the input text. My idea was that the code should be able to handle any size input as long as its within the memory-limits of the language. Like you don't have to write "memory optimal code" or something, but also shouldn't asume it is smaller than X. I could also just pick an upper limit of "1 kilobyte" or something to avoid any uncertainty about the requirements I think this is fine now as it is.
  • Someone in the comments below asked how to handle special characters like $?() so I took a look at how my "check program" handled that and it strips them away before doing the anagram check. So I added a rule for that, but while writing that I felt it makes it needlessly complicated and I'm considering ditching that rule and altering my check-program to reflect that (but then I cant claim its the exact same anymore :( )
  • Any other parts that are not clear?
\$\endgroup\$
  • \$\begingroup\$ What happens if there are 3 that are anagrams, such as eat ate tea? Are they all printed in one line / group? \$\endgroup\$ – FlipTack Dec 19 '16 at 17:27
  • \$\begingroup\$ @Flp.Tkc yes, like "parts, strap, traps" in the example \$\endgroup\$ – Olle Kelderman Dec 19 '16 at 17:29
  • \$\begingroup\$ I suggest you remove the grouping rule, since it's not really the interesting part of the challenge. It just adds code and limits the solutions. It's apparent which of the words that are together anyway. I do suggest they have to be grouped though, but without the need for delimiters. \$\endgroup\$ – Stewie Griffin Dec 20 '16 at 23:24
  • \$\begingroup\$ I think the memory rule is fine. I'm quite sure people will write a script that in theory would work for any input length if it wasn't for language or memory limitations. I also suggest you guarantee at least one character in the input. Otherwise people would need to add code just to handle empty input and that's not the interesting part of the challenge. \$\endgroup\$ – Stewie Griffin Dec 20 '16 at 23:29
  • \$\begingroup\$ You should add rules regarding special characters. Are it's, sit and its anagrams? What about hyphens? Can there be any special characters such as $?() etc? How are they treated? \$\endgroup\$ – Stewie Griffin Dec 20 '16 at 23:31
  • \$\begingroup\$ @StewieGriffin The grouping thing is a natural result of my solution to the problem back then, and imo its a fun part of the challenge, so I'm not totally sure about removing it. About the memory limit: I'm totally fine with the guarantee of at least one character if you think empty input needs special handling (i didnt think it would, but I dont really care :P) And yes, you are correct about special characters. I'd say "it's" is two words: "it" and "s". All special characters are ignored, so essentially regarded as whitespace between words. I'll add that \$\endgroup\$ – Olle Kelderman Dec 20 '16 at 23:35
  • \$\begingroup\$ welp, turns out I handled special characters differently, I strip them away from the word, so "it's" becomes "its", guess that'll be the rule then since I want to keep as close as possible to the original program \$\endgroup\$ – Olle Kelderman Dec 20 '16 at 23:48
  • \$\begingroup\$ @StewieGriffin I added a rule about special character handling, but I'm not completely sure about it, thoughts? (see my added "sandbox question") \$\endgroup\$ – Olle Kelderman Dec 21 '16 at 0:05
  • \$\begingroup\$ parsing and anagrams are relevant tags, maybe strings too, but I'm not sure about that one. \$\endgroup\$ – Stewie Griffin Dec 21 '16 at 7:43
  • \$\begingroup\$ !"#$%&'()*+,-./:;<=>?@[]^_{|}~ are all the non-alphanumeric ASCII-characters, except \` . I suggest you include the missing two symbols in the list to ignore, and say: "All non-alphanumeric characters (except spaces and newlines) must be trimmed away. So, it's and its are the same word." (You might want to rephrase that since my English isn't perfect, but something along those lines. If this is the rule then R2D2 and dr.22 will be anagrams, I'm not sure if that the desired behavior..? \$\endgroup\$ – Stewie Griffin Dec 21 '16 at 10:17
  • \$\begingroup\$ PS! I don't mean to be difficult, it's just that in my experience you'll get these questions sooner or later. So it's a good thing to sort it out while it's still in the Sandbox :) \$\endgroup\$ – Stewie Griffin Dec 21 '16 at 10:20
  • \$\begingroup\$ @StewieGriffin those two characters should have been included, look at the list from en.cppreference.com/w/cpp/string/byte/ispunct where I got it from, somehow I messed up the copy-paste :( And about "what is desired behaviour?" Im honestly not sure, I never really thought about it before you mentioned it and then I looked at how my sample program handled it. I remember putting in the ispunct-trim for stuff like commas after a word, im not sure about characters within the word... \$\endgroup\$ – Olle Kelderman Dec 21 '16 at 10:26
  • \$\begingroup\$ You can say that the input will not have any special characters except ' and -. Those two must be trimmed away. I think you must include those two, since these can be found in many texts. \$\endgroup\$ – Stewie Griffin Dec 21 '16 at 10:34
6
\$\begingroup\$

WHAT IS THIS DOING HERE?

How low can you go? - Signal Limbo.

Sometimes we need a low voltage, sometimes we need a high voltage. Let's design a VDC power supply!

The challenge is simple, with 2 lines (+5V and GND), Create a Variable DC power supply on a standard breadboard that ranges from +12V (+/-0.1) to 0V.

INPUT: 5VDC (power rail +), 0VDC (power rail -), 5K, OR 10K potentiometer

OUTPUT: 12-0VDC depending linearly on potentiometer. There is no lower limit to the ammount of current that this circuit needs to be able to supply.

Rules:

enter image description here

this is a standard breadboard. Image courtesy of SparkFun's breadboard tutorial.

A standard breadboard consists of 2 power rails, 2 colums of 5 general pins, and 30 rows.

  • All pins on one row (a,b,c,d, and e are all a single row) are connected.
  • All pins on separate rows are Separate.
  • The opposite is true for power lines. (columns are connected, but not rows)

Electrical components are restricted as follows.

  • All electrical products which have a public datasheet are valid in this challenge, EXCEPT
    • Those without DIP Packaging XOR Those without through hole packaging
    • Those with PCBs
  • All Non-Passive components used in your entry must have a part number, or spec sheet.
  • All passive components (except wire) must have a value, given in Ohms, Henries, or Farads.
  • No pin may be left floating. All pins must be connected to somewhere on the bread board.

Scoring:

You will be scored based on the area that your entry spans. Do Not Score with the power rails, only components within the labelled grid shall be scored.

The area (measured in pin spaces) will be taken by the smallest rectangle that can be drawn around all of the breadboard connections.

this is a , so the entry with the least area consumed wins! good luck!

Tools

Circuits.IO Will be a great standard for this challenge. I ask that you consider this before any other simulator, it's simple, and easy to share. I am not requiring that you use it.

\$\endgroup\$
  • 2
    \$\begingroup\$ To one who doesn't have experience with a standard breadboard, the "column" of 5 would better be described as a row, given the picture. This goes for everything in the first set of bullets - switch "row" with "column" and vice versa. \$\endgroup\$ – MildlyMilquetoast Dec 15 '16 at 3:45
  • 4
    \$\begingroup\$ The description of how the breadboard is internally wired is not very clear, but seems to be saying the opposite of how every breadboard I've ever used was wired. \$\endgroup\$ – Peter Taylor Dec 15 '16 at 10:44
  • \$\begingroup\$ Alright, thank you Mistah, and Peter, I'll be sure to remedy these qualms tonight! \$\endgroup\$ – tuskiomi Dec 16 '16 at 15:24
  • \$\begingroup\$ 1. "that ranges from +12V (+/-0.1) to 0V". Is the +/- there to allow for tolerances in component manufacture, to allow for smoothed oscillations in the output, or both? 2. The wiring explanation is still not very clear IMO. How about "All pins on one row (e.g. 23a-23b-23c-23d-23e) are connected"? 3. In the other meta question, validation was mooted as via Spice. I'm not familiar enough with it: is it capable of emulating any product with a public datasheet, or is there a conflict there? \$\endgroup\$ – Peter Taylor Dec 18 '16 at 20:17
  • \$\begingroup\$ @PeterTaylor spice is the framework for all modern advanced circuit simulators. \$\endgroup\$ – tuskiomi Dec 18 '16 at 20:19
  • \$\begingroup\$ Let me rephrase that. In your answer to the other meta question, you said "provided that each challenge specifies a freely available digital testing environment". I don't see such a specification in this challenge, and it's not obvious that "All electrical products which have a public datasheet are valid in this challenge" is compatible with it. Does this question meet your own criteria for acceptability? \$\endgroup\$ – Peter Taylor Dec 18 '16 at 20:29
  • \$\begingroup\$ My bad: I mixed up two usernames starting with t. I think you still need to answer the question of how answers are verified, though. \$\endgroup\$ – Peter Taylor Dec 18 '16 at 23:21
  • \$\begingroup\$ What's the distance from column a to power -? \$\endgroup\$ – l4m2 Dec 31 '17 at 14:49
6
\$\begingroup\$

Natural Pi - The Front Nine W.I.P.

## Meta ## 
    - 4 more ways to calculate pi with nature?

Introduction

These challenges are simulations of algorithms that only require nature and your brain (and maybe some re-usable resources) to approximate Pi. If you really need Pi during the zombie apocalypse, these methods don't waste ammo! There are nine challenges total.

Each challenge will give an algorithm for approximating Pi with nature. Then it will walk through how the computer simulation should work. Next comes the Specification to clear up details and finally there are some test cases.


Natural Pi #0 - Rock

  • Coprime Probability

Natural Pi #1 - Sand

  • Buffon's Needle

Natural Pi #2 - River

  • Curvy-ness of a River

Natural Pi #3 - Books

  • E's in a circle

Natural Pi #4 - Sun Flower

  • Ratio of Area to Diameter

Natural Pi #5 - Vine

  • Period of a Pendulum

Natural Pi #6 - Fire

  • Ratio of Circumference to Diameter

\$\endgroup\$
  • 1
    \$\begingroup\$ Please read meta.codegolf.stackexchange.com/a/8464/45941 \$\endgroup\$ – Mego Sep 8 '16 at 21:30
  • \$\begingroup\$ @Mego my intention is to post these as distinct challenges and not a multipart challenge. \$\endgroup\$ – NonlinearFruit Sep 8 '16 at 21:54
  • \$\begingroup\$ Then why is the multiple-holes tag present? \$\endgroup\$ – Mego Sep 8 '16 at 21:57
  • \$\begingroup\$ @Mego Oops, thanks for pointing that out \$\endgroup\$ – NonlinearFruit Sep 9 '16 at 1:19
  • 3
    \$\begingroup\$ The "probability that two random integers are relatively prime" isn't well defined. You can't talk about a "random integer" without defining a probability distribution, and you can't uniformly select a random integer because there's an infinite number of them. \$\endgroup\$ – Peter Taylor Sep 13 '16 at 14:16
  • \$\begingroup\$ @PeterTaylor Good catch, I have specified an interval for the random numbers \$\endgroup\$ – NonlinearFruit Sep 13 '16 at 21:18
  • 2
    \$\begingroup\$ Reusing sandbox posts like this doesn't really work. There are already 2988 answers in the sandbox: it won't harm to have one more, and it means that the new question can be commented on, voted ready, etc. independently of the previous one. \$\endgroup\$ – Peter Taylor Sep 22 '16 at 20:42
  • 1
    \$\begingroup\$ @PeterTaylor Good point, I was originally tracking my ideas and hoping for recommendations on the set as a whole, but I'll migrate this to individual posts, \$\endgroup\$ – NonlinearFruit Sep 26 '16 at 23:16
6
\$\begingroup\$

PPCG VS CR KotH

I am working as fast as I can to get this ready. Please be patient. I have a real job and will attempt to work on this on vacation to the northern states using mobile. I give no promises.

I challenged CR to a KotH challenge. So here is the specs.

Two sides in a arena. 1000x1000. Resources scattered about. A giant area in the center filled with resources. You must build a base and defend your ancient.

You have a few kinds of buildings:

  1. Wall: a simple wall that must be broken before walking through. It has 1/2/4/8 health (upgrades). It can be changed into a gate.
  2. Gate: a gate that lets the side that made it walk through. Health: 1/2/2/4
  3. Turret: Deals 1/1/2/4 damage to the lowest health enemy within a 1/2/4/4 block radius and has 1/1/4/8 health.
  4. Resource drop: a place that you can drop resources. Has 2/2/4/6 health.
  5. Tower of vision. Gives 10 sight radius with health of five. Costs two resources to build.

Upgrades are 1/2/3/4. The first upgrade is just buying the building.

Gates when transformed stay the same level as the wall they started as, can still be upgraded.

Every bot starts with five health, one damage, and three sight radius. They can upgrade each by four for the cost of 1/2/2/2.

All upgrades take one bot. It takes 1/2/2/3 turns to upgrade an item. The bot must upgrade the item all at once or it must restart and repay the cost. Building a item takes one resource.

\$\endgroup\$
  • 2
    \$\begingroup\$ so, how does turn order work? is there a way to attack excluding turrets? \$\endgroup\$ – Destructible Lemon Jul 29 '17 at 2:54
  • 1
    \$\begingroup\$ Will the bots have knowledge of the entire 1000x1000 area or what is the line of sight? \$\endgroup\$ – Simon Forsberg Jul 29 '17 at 8:48
  • 2
    \$\begingroup\$ I'd recommend not making the challenge too complicated/complex. I'm not sure that skill points are necessary. \$\endgroup\$ – Simon Forsberg Jul 29 '17 at 8:49
  • \$\begingroup\$ How does it work with the Q&A site format? Or is it an off-site challenge? \$\endgroup\$ – ugoren Jul 29 '17 at 19:10
  • 2
    \$\begingroup\$ @ugoren King of the Hill challenges like this one are very much on-topic on PPCG, and in fact we even have a tag for challenges like these: koth. \$\endgroup\$ – Kritixi Lithos Jul 29 '17 at 19:53
  • \$\begingroup\$ @Cowsquack, You're right, it's OK. A bit strange for my taste, since the war happens off-site, but never mind. \$\endgroup\$ – ugoren Jul 29 '17 at 20:16
  • \$\begingroup\$ @SimonForsberg good point \$\endgroup\$ – Christopher Jul 29 '17 at 23:26
  • \$\begingroup\$ This will not be a challenge between PPCG and CR. Challenge declined \$\endgroup\$ – Simon Forsberg Aug 4 '17 at 18:50
  • \$\begingroup\$ Since this idea is dead now, consider developing it further as a normal KoTH or deleting and editing it down to a stub. \$\endgroup\$ – HyperNeutrino Oct 30 '17 at 2:24
6
\$\begingroup\$

PPCG Handwriting OCR

(insert logo here once I make it)

Given an image consisting of handwritten text, output the text that is written. The image of the handwritten text will be generated by taking characters from one or more handwriting samples given by PPCG users.

Rules

  • You may not hardcode your program to only recognize the samples in the corpus.
  • There will be sufficient spacing between characters to avoid ambiguity.
  • Only ASCII alphanumeric characters (those matching the regex [A-Za-z0-9], i.e. uppercase and lowercase English letters and digits) will be present in the input.
  • Inputs will be formed by concatenating individual characters from the handwriting samples.
  • The test cases used for scoring may be modified at any point if I feel it is necessary to do so. Reasons may include but are not limited to: needing more test cases to have a single winner, removing problematic test cases, and fixing errors in test cases.

Aside from the above considerations, there are no guarantees on the appearance of the handwriting, as these are actual handwriting samples and thus can have drastic variances.

Score

Your score will be the number of test cases that are correctly recognized, divided by the total number of test cases. The highest score wins. In the event of a tie, the first submission to reach the high score wins. Additional test cases may be added to break ties.

Handwriting Samples

This Imgur album contains the handwriting samples, as well as the names of the users who contributed them.


I've made a chat room for submitting handwriting samples. The more samples I get, the better this challenge will be, so please take a few minutes and submit a sample!

\$\endgroup\$
  • \$\begingroup\$ You may not hardcode your program to only recognize the samples in the corpus.: Can we tailor our code to be better for the samples than other inputs though? \$\endgroup\$ – TheLethalCoder Aug 2 '17 at 16:08
  • \$\begingroup\$ The test cases used for scoring may be modified at any point: Will current answers be modified? \$\endgroup\$ – TheLethalCoder Aug 2 '17 at 16:09
  • 1
    \$\begingroup\$ @TheLethalCoder 1) No. 2) Answers will be run on the test cases any time the answer or the test cases change, and the scores will be updated accordingly. \$\endgroup\$ – Mego Aug 2 '17 at 16:11
  • \$\begingroup\$ Hadn't seen that loophole before :) \$\endgroup\$ – TheLethalCoder Aug 2 '17 at 16:13
  • \$\begingroup\$ Can I nitpick again and say handwriting OCR is called ICR? :P \$\endgroup\$ – TheLethalCoder Aug 3 '17 at 9:06
  • \$\begingroup\$ Can you add an example input as well? \$\endgroup\$ – TheLethalCoder Aug 3 '17 at 9:07
  • 2
    \$\begingroup\$ @TheLethalCoder 1) ICR is when a program tries to learn what handwriting looks like via machine learning. OCR is just parsing written/text input into data. This is OCR, not ICR. 2) I'll add some examples once I get more samples and finish writing my generator. \$\endgroup\$ – Mego Aug 3 '17 at 9:08
  • \$\begingroup\$ Can you assume a minimum height for the characters? \$\endgroup\$ – TheLethalCoder Aug 3 '17 at 9:28
  • \$\begingroup\$ @TheLethalCoder Aside from the above considerations, there are no guarantees on the appearance of the handwriting, as these are actual handwriting samples and thus can have drastic variances. \$\endgroup\$ – Mego Aug 3 '17 at 9:29
  • \$\begingroup\$ To be honest with no restrictions this is going to be very hard, Do you lose points for returning extra information? Assume the input Hello if I return H.e.l.l.o. is that 100% for that test case or do I lose and get something like 50%? \$\endgroup\$ – TheLethalCoder Aug 3 '17 at 9:31
  • \$\begingroup\$ And does the output have to be in the correct order? \$\endgroup\$ – TheLethalCoder Aug 3 '17 at 9:58
  • \$\begingroup\$ @TheLethalCoder It's all or nothing. Getting 100% on a test battery challenge should be hard. \$\endgroup\$ – Mego Aug 3 '17 at 9:58
  • \$\begingroup\$ Please update imgur album \$\endgroup\$ – Pavel Sep 18 '17 at 4:28
  • \$\begingroup\$ @Pavel I will once I finish cutting up the images. My free time has been limited these past few weeks. \$\endgroup\$ – Mego Sep 18 '17 at 4:29

You must log in to answer this question.

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