# Sandbox for Proposed Challenges

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

Sandbox FAQ

## Posting

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

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

## Discussion

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

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

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

If you think one of your posts requires more feedback, but it's been ignored, you can ask for feedback in The Nineteenth Byte. It's not only allowed, but highly recommended! Be patient and try not to nag people though, you might have to ask multiple times.

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

## Other

Search the sandbox / Browse your pending proposals

The sandbox works best if you sort posts by active.

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

Get the Sandbox Viewer to view the sandbox more easily!

# Transport Tycoon [control program WIP] king-of-the-hillgame

The specification is now complete; the control program will now be written

Chatroom for this challenge

Your task is to create an AI which builds a profitable transport network to carry passengers. In each game, the first entry to have $262,144 or more in cash wins! Every entry must have a name and version numbering for each time it is altered. You may submit up to 8 entries, but they must not collaborate. ## Control Each round has four players. Each player has a number from 1 to 4. A simple map will be randomly generated by the control program for each game. This map will be stored in a file map.txt two directories above your program (i.e. ../../map.txt), and updated each game tick. Each player's bank balance (as a number without the$ symbol) will be in ../../account_<PLAYERNUMBER>.txt. Vehicle data will be in ../../vehicles_<PLAYERNUMBER>.txt. You may view other player's vehicle and account files.

Your program will be invoked once, at the start of the game. When your program has finished initializing, it must output READY. If it takes more than 60 seconds to initialize, it will be terminated and disqualified from that game. It may keep files between rounds (for example, to predict an opponent's strategy after watching them for a few games). Other players may not view these files. The tournament will be re-run and the leaderboard updated every 2 days. Your program may not keep files between tournaments.

The control program will put the text WAITING-player_number (e.g. WAITING-4) and a newline to your program's standard input when each game tick begins. You will submit actions on standard output, separated by new lines, terminated by END. Actions that are invalid for whatever reason will be completely ignored. If your program takes longer than 1 second to output END, it will receive TIMEOUT on standard input and no action will be executed for this turn.

If no winner has been found after 30 minutes, the player with the most money wins.

## Map format

The map will be a two-dimensional ASCII grid where the top is north, the bottom is south, the left is west and the right is east. Example:

#/////////
######@@@*
/**@@#####
//@@1#@@@*
/@@##@**/#
~~~+~~~~~|
///#######


# represents a road. / represents empty land. * is for difficult terrain (e.g. hills, swamps, whatever) - more on that later. @ represents a house. ~ is a body of water. + is a completed bridge over water. | is a partially constructed bridge. The numbers 1 to 4 represent stations belonging to players (e.g.: if you are player 4, your stations will be marked as 4). 5 to 8 represent 'inactive' stations belonging to players 1 to 4 respectively.

The line endings in the file will be Windows-style CRLF.

The top left corner is (0,0). X is horizontal and Y is vertical.

## Construction

Each tick, a player can perform up to 4 construction actions. These are:

• replace a / with a # (build a road)
• replace a * with a / (prepare terrain)
• replace a # with an inactive station (build a station)
• replace a ~ with a | (start a bridge)
• replace a | with a + (finish a bridge)
• replace one of your stations with a # (demolish a station)

You may not perform more than one action on a tile in one turn (you cannot go from ~ to | and to + in a single turn).

You cannot demolish roads, bridges, water, houses or other players' stations.

Each action costs $512, and is sent to the control program on standard output in the following format (B is for Build): B-X-Y-tile  For example, this will build a road at (8,4): B-8-4-#  Invalid commands will be ignored. ## Vehicles Each player can own an unlimited number of vehicles. The basic bus has the following properties: • carries 32 passengers • travels 8 tiles per turn • consumes$8 per tile in running costs

Each vehicle can have up to 4 upgrades out of the following (but no more than 2 of each type):

• +16 capacity (denoted by C)
• +4 tiles/tick speed (S)
• -$2 running costs (R) At most one vehicle can be bought by each player per turn. The basic bus costs$4096 and each upgrade costs $1024; the maximum possible cost is therefore$8192 (all 4 upgrades). A bus can be sold at any time for half of its purchase price (including upgrades; a bus with 4 upgrades can be bought for $8192 and sold for$4096). At most one vehicle can be sold each turn.

The command for purchasing a vehicle is (P is for Purchase):

P-id-X-Y-upgrades


For example, this will buy a bus with no upgrades, assign it the ID 5, and place it at (7,7):

P-5-7-7-


The command for selling a vehicle is simply (V is for Vend)

V-id


Vehicles are stored in vehicles_N.txt in the following format, separated by newlines:

id-X-Y-passengers-upgrades-laststationX-laststationY


For example, this bus has ID 4, is at (5,5), contains 15 passengers, has two speed upgrades and one running cost upgrade, and last stopped at (3,4). If the bus has never run A before, use the coordinates where it was created for the "last station" coordinates. Update the coordinates every time A is run for that bus.

4-5-5-15-SSR-3-4


Vehicles can travel on roads (#), bridges (+) and station tiles (12345678). In the above example, it is possible to drive from the top left corner to the bottom right corner. However, the two road sections in the map below aren't connected, because they are only diagonally touching. Building a road on one of the * would solve this.

/////
##*//
/*###
/////


Vehicles can only stop to pick up and drop off passengers at stations belonging to their owner - player 3's bus can only stop at a 3 or a 7, but not at any of 124568#+.

Your AI has complete control over the movement of its buses. It will submit directions as commands. For example, the following command set will move bus 8 in a circle, then two spaces south, then make it offload 8 passengers, then make it wait for passengers (N, E, S and W are north, east, south and west; R is for Remove; A is for Acquire):

N-8
E-8
S-8
W-8
S-8
S-8
R-8
A-8


NB: Waiting at a station with A counts towards the limit of tiles that the bus can travel each turn, although it is not moving. While waiting, double running costs are charged. A bus may wait for multiple turns. If a bus moves fewer tiles than it is able to (e.g. can move 8 tiles per turn but chooses to move 5 times), halved running costs are charged for the unused turns.

## Passengers

Each time an R command is submitted for a bus that is at a station, the bus loses 8 of its passengers. The diagonal distance (using Pythagoras' theorem) between its current station and the previous one is calculated and rounded down (floored). Each passenger offloaded gives this amount of profits (e.g. if the previous station is 1.4 tiles away, each passenger gives $1; if it is 5.9 tiles away, each passenger gives$5).

Each time an A command is submitted for a bus that is at a station, the bus gains passengers. Each house in range of your station provides 1/number_of_active_stations_in_range_of_house passengers.

If there are three stops, A, B and C, and the bus has a route from A to B and then to C, but only picks up passengers at A, then passengers offloaded at B will pay the price for A to B, and passengers offloaded at C will pay for A to C. However, if any passengers are loaded at B, then all of the passengers offloaded at C, even if some of them boarded at A, will pay the fare for B to C.

In the map below, the tiles marked with @ and # are in range (4 tiles or less away), but not the tiles marked with /; the bus at 1 will gain 32 passengers because there are 32 houses in range and no other stations.

////@////
///@@@///
//@@@@@//
/@@@@@@@/
####1####
/@@@@@@@/
//@@@@@//
///@@@///
////@////


## Other

You will be charged $64 per turn for each station, active or not, that you own. Each turn, active stations have a 1 in 8 chance of becoming inactive. This is reverted when a bus runs A at the station. You will start with$32768.

You may not have a negative quantity of money.

When someone wins, all competing programs will receive GAMEEND on standard input. They may no longer submit commands after this happens, but they may read and write from files (to prepare for a subsequent game, for example). After 60 seconds, all competing programs will be killed.

The map will be 256*256 tiles.

## Todo

• Write control program
• Write map generator
• Plan tournament format
• check out dinopoloclub.com/minimetro for a minimalistic transport network game that might be amenable to computer solution Aug 11, 2014 at 13:39
• If a bus makes a journey from station X to station Y to station Z, and not all of the passengers picked up at X get off at Y, how much will they pay when they get off at Z? Will everyone who gets off at Z be charged as if they had travelled from Y? In order to charge the higher amount for a journey from X to Z, would the bus need to avoid stopping at Y? Aug 31, 2014 at 21:25
• @githubphagocyte Yes, it would need to avoid stopping at Y. I don't think there's a way to fix this without overcomplicating things. Alternatively the R command could be changed to drop off all the passengers; this would eliminate the option to only drop off some passengers. (This is what happens in OpenTTD - vehicles always drop off all their passengers at stations AFAIK)
– user16402
Sep 1, 2014 at 8:58
• @githubphagocyte which is better? just leaving it as it is or changing R?
– user16402
Sep 1, 2014 at 9:04
• I don't have a preference I just wanted to make sure the behaviour is unambiguous. You can model it in as much or as little detail as you like as long as there are no loopholes or unclear behaviour. Sep 1, 2014 at 13:30
• In real life the number of people who get on a bus depends on its announced destination rather than just its pick up point, but I don't think it's necessary to model that in order to have an interesting competition. There's already the potential for complex interaction between companies that can't prevent other companies from using roads they didn't pay for. Sep 1, 2014 at 13:35
• @githubphagocyte I've added a disambiguation: "If there are three stops, A, B and C, and the bus has a route from A to B and then to C, but only picks up passengers at A, then passengers offloaded at B will pay the price for A to B, and passengers offloaded at C will pay for A to C. However, if any passengers are loaded at B, then all of the passengers offloaded at C, even if some of them boarded at A, will pay the fare for B to C."
– user16402
Sep 1, 2014 at 13:45
• It's worth trying to think of winning strategies to see if that highlights any loopholes. The best return seems to be from journeys along a straight line a multiple of 8 squares long (or 12 or 16 squares with an upgraded bus). If there are a number of squares nearby where a rival could benefit from building a station, do you benefit from building stations there just to block? How do the costs compare under your current parameters? Sep 1, 2014 at 13:55
• @githubphagocyte I could partially prevent blocking by not allowing a player to build two of their own stations next to each other (but allow them to build next to a competitor). Would that work?
– user16402
Sep 1, 2014 at 17:09
• I suppose it depends whether the cost of building a number of unused stations just to block one rival station is worth it. As long as building a new station isn't too cheap it should sort itself out. I wasn't suggesting preventing people from blocking, just making sure it is sufficiently expensive that it doesn't happen too easily. Sep 1, 2014 at 17:35
• @githubphagocyte Currently the station costs $512 to build and$64 per turn (inc opponent's turns) to maintain. how much higher should the costs be? $1024 and$64 maybe?
– user16402
Sep 1, 2014 at 17:40
• The current figures may be fine. Just something to bear in mind during testing with example contestants. Sep 1, 2014 at 22:40
• Is any controller up for this? Sep 16, 2014 at 9:28
• @SohamChowdhury I'm working on it.... one day I'll finish it
– user16402
Sep 16, 2014 at 10:31
• @SohamChowdhury github.com/professorfish/ttkoth
– user16402
Sep 16, 2014 at 10:33

# Overhanded (Underhanded) Poker

Also if you make a thing I'll whack everyone involved with a large trout ~ Doorknob

You and your poker buddy are bored, and seeking to liven up the usual poker game. Playing one hand just isn't challenging any more, and you're looking to add a bit of depth. So, why not play with two?

### Overview

This is a round robin tournament of two-player poker. For each round, a player will need to make two hands of five cards each. To do this, each player will be dealt seven cards, with three community cards to fill out the hands. After receiving their seven cards, players will be allowed to exchange any number of them for new cards from the deck one time.

Once each player has exchanged cards, they will split the ten cards (7 in hand, 3 community) into two hands, Over and Under. The object for the Over hand is the highest ranked hand, while the object for Under is lowest.

### Scoring

In each round, a player will receive one point if:

• Their Over hand is higher than the opponent's Over hand and
• Their Under hand is lower than their opponent's Under hand

If one hand wins (Over beats Over or Under loses to Under) and the other ties, you get half a point.

If one player wins one and the other wins the other or both hands tie, no points are awarded.

### Rules

• Standard poker hand rankings apply (link chart or something here)
• Play fair! (will expand on this with the usual KotH stuff)

WIP

### Meta

Obviously this needs some more work. Initial thoughts, questions?

• I like this idea a lot (and you getting smacked with a trout is intriguing). One suggestion: it doesn't seem you make a mention of how many games each bot will play against each other bot. Since this problem is (presumably) dominated by the RNG gods, deciding how many rounds are necessary to ensure rewarding good programs instead of lucky programs may be tricky. (Relevant meta) Jul 8, 2015 at 19:03
• That's mainly because I haven't decided yet. I'll try to make it enough, but not too many ;) Jul 8, 2015 at 23:18
• Does the second player know how many cards the first one changed or are the changes simultaneous? Jul 11, 2015 at 10:03
• @randomra I think simultaneous is best here. Otherwise I'll have to alternate turns as P1/P2 due to the advantage. Jul 11, 2015 at 14:49

# I'm always right

Given the following input:

• A number consisting of decimal digits, the guess

• A number consisting of decimal digits, the answer

You are to output a single natural number, the base, such that when you interpret the guess as a number in the base base, the distance between guess and answer is smaller than for any other choice of base.

To be clear,

• answer is interpreted as base 10

• guess is interpreted as base base

• distance means absolute value

• The base must be greater than the largest digit used. I.e. if 6 appears in the guess, you cannot output a base smaller than 7 because any base smaller than 7 does not use the symbol 6.

Motivation and Example

Your friend asks you a question like "What's the population of New York City?"

You have no clue, so you make a guess "1,400,000 people", you say.

He says "You're an idiot, the population is 8,550,405. You were so far off."

You then do some quick math in your head and say, "I wasn't that far off, I didn't realize you wanted base 10. I was using base 14. In base 10, I said 9,680,832, which wasn't that bad of a guess"

In this example

guess  = 1400000
base   = 14


Test cases

Eventually maybe.

Edit: Posted.

# Output this string from the kolmogorov-complexity tag info page

• Perhaps reading from the kolmogorov-complexity tag page would actually be an interesting strategy. Mar 22 at 18:06
• Instead of discouraging the trivial print answers, you could make a community wiki answer listing them in various languages Mar 22 at 18:06
• @ophact That's a standard loophole though, unless OP specifically allows internet access Mar 22 at 18:07
• @ophact you know what, on second thought you are right, given that that would generally require a lot of boilerplate to access the plate, and then pull the requisite string out of it, if that can be golfed down to something interesting Mar 22 at 18:08
• actually upon several hours more thought on the subject @ophact, I am inclined to reverse my decision about allowing internet access to the kolmogorov-complexity info page, for two reasons: 1, because I feel it is not entirely in the real spirit of this question, which is to golfily produce a string that looks primarily like the result of a cat walking on your keyboard, and 2, because I also don't think that, with the boilerplate for fetching the page from the internet and parsing it, any solution doing that would be at all competitive. Mar 22 at 22:10

# Dividing Strings

Division with numbers is great: 6 / 3 = 2, but have you ever wanted to divide strings? In this challenge you will, given two strings (s and t) divide s by t

## Challenge

Given a string, s, find the substring in which t is repeated the most times (non-overlapping), return the amount of times t is repeated, example:

s = "HiFooFooFooFoo"
t = "Foo"
n = 4


Seems easy enough? Well if the substring ends with the first m characters of t, you should add what fraction of the string t was in the substring (m/t.len):

s = "12121"
t = "12"
n = 2.5


## Rules

• You only need to output to the precision your language supports. The minimum precision is two decimal places.

## Examples

First line is s, second line is m, last line is output. Examples are double-newline seperated

FooFooFoo
Foo
3

GoatGoatGoatGo
Goat
3.5

SheepSheepSheep
Goat
0

GoGoatGoatGoat
Goat
3

GoatGoGoatGo
Goat
1.5

ab111cd
1
3

PigPigPi
Pig
2.666666

aabaabaaaba
aaba
2

aabaaaabaaa
a
4

• Here's a nice testcase: "PigPigPi" / "Pig" Aug 8, 2016 at 19:20
• what should "GoGoatGoGoatGo"/"Goat" return? Aug 8, 2016 at 19:24
• "aabaabaaaba"/"aaba"-> 2 Aug 8, 2016 at 19:32
• Can the partial string at the end overlap with an occurrence of the complete string? (The intended answer seems obvious but it's not explicitly specified.) Aug 8, 2016 at 22:31
• @feersum Not sure what you mean, can you give an example? Aug 10, 2016 at 21:44
• related Oct 1, 2016 at 14:52
• @Downgoat feersum probably meant something like this: abaabaa/abaa -> aba|(a)|baa, where the middle a is used as both leading/trailing part and thus overlaps (which I personally wouldn't allow for this challenge). Suggested test cases: aabaabaaba/aaba -> 1.75 (...|aaba|aba) and 121141115217/1 -> 3 Feb 27, 2018 at 9:22
• What about wordwordstopwordwordwordword. Would that be 2, 3, 5, unhandled, or something else? Sep 25, 2020 at 23:16

# Make A Full Dobble™ Deck

Dobble (A.K.A. Spot It!) is a deck of (55) cards each of which has a set of (8) distinct symbols, such that every pair of cards matches on exactly one symbol and all symbols are members of pairs.

The base aim of any of the games one plays with a Dobble deck is to find the matching symbols between pairs of cards quicker than your competitors; if you've never played I recommend it.

The deck as sold contains 55 cards and uses 57 symbols, but it is actually a "Full Dobble Deck" of 57 cards with 2 missing. If the missing 2 cards were added there would be 8 distinct symbols on each card such that each symbol would appear 8 times across the deck. Here is a deck I've been playing with, each row being a card (with the 2 missing cards added and asterisked):

  Anchor     Apple      Bird       Dinosaur   Dolphin    Ghost      Ladybird   Turtle
Anchor     Bang       Car        Clef       Flower     Key        Lips       Lock
Anchor     Bolt       Clown      Glasses    No-entry   Snowman    Spider     Target
Anchor     Bomb       Bottle     Dog        Heart      Ice-cube   Moon       Zebra
Anchor     Bulb       Cactus     Dragon     Flame      Scissors   Sun        Tree
Anchor     Candle     Clover     Hand       Man        Skull      Snowflake  Splat
Anchor     Carrot     Cheese     Clock      Hammer     Knight     Maple      Web
Anchor     Cat        Drop       Eroteme    Eye        Igloo      Pencil     Yin-yang
Apple      Bang       Igloo      Maple      Moon       Scissors   Snowflake  Spider
Apple      Bolt       Cactus     Car        Carrot     Heart      Pencil     Skull
Apple      Bomb       Cat        Hand       Lock       Snowman    Tree       Web
Apple      Bottle     Clover     Dragon     Flower     Hammer     No-entry   Yin-yang
Apple      Bulb       Cheese     Clown      Drop       Key        Man        Zebra
Apple      Candle     Clef       Clock      Dog        Eroteme    Flame      Target
Apple      Eye        Glasses    Ice-cube   Knight     Lips       Splat      Sun
Bang       Bird       Flame      Glasses    Heart      Man        Web        Yin-yang
Bang       Bolt       Bottle     Clock      Dinosaur   Drop       Hand       Sun
Bang       Bomb       Carrot     Clown      Dragon     Eroteme    Ghost      Splat
* Bang       Bulb       Dog        Eye        Hammer     Ladybird   Skull      Snowman
Bang       Cactus     Candle     Cat        Dolphin    Knight     No-entry   Zebra
Bang       Cheese     Clover     Ice-cube   Pencil     Target     Tree       Turtle
Bird       Bolt       Bomb       Candle     Cheese     Eye        Flower     Scissors
Bird       Bottle     Eroteme    Key        Knight     Skull      Spider     Tree
Bird       Bulb       Carrot     Clef       Hand       Ice-cube   Igloo      No-entry
Bird       Cactus     Drop       Hammer     Lock       Moon       Splat      Target
Bird       Car        Cat        Clover     Clown      Dog        Maple      Sun
Bird       Clock      Dragon     Lips       Pencil     Snowflake  Snowman    Zebra
Bolt       Bulb       Clover     Dolphin    Eroteme    Lips       Moon       Web
Bolt       Cat        Flame      Ghost      Hammer     Ice-cube   Key        Snowflake
Bolt       Clef       Ladybird   Maple      Splat      Tree       Yin-yang   Zebra
Bolt       Dog        Dragon     Igloo      Knight     Lock       Man        Turtle
Bomb       Bulb       Car        Dinosaur   Knight     Snowflake  Target     Yin-yang
Bomb       Cactus     Clock      Clover     Glasses    Igloo      Key        Ladybird
Bomb       Clef       Dolphin    Hammer     Man        Pencil     Spider     Sun
Bomb       Drop       Flame      Lips       Maple      No-entry   Skull      Turtle
Bottle     Bulb       Candle     Ghost      Glasses    Lock       Maple      Pencil
Bottle     Cactus     Clef       Clown      Eye        Snowflake  Turtle     Web
Bottle     Car        Cheese     Dolphin    Flame      Igloo      Snowman    Splat
Bottle     Carrot     Cat        Ladybird   Lips       Man        Scissors   Target
Bulb       Cat        Clock      Flower     Heart      Spider     Splat      Turtle
Cactus     Cheese     Dog        Ghost      Hand       Lips       Spider     Yin-yang
* Cactus     Dinosaur   Eroteme    Flower     Ice-cube   Man        Maple      Snowman
Candle     Car        Dragon     Drop       Ice-cube   Ladybird   Spider     Web
Candle     Carrot     Key        Moon       Snowman    Sun        Turtle     Yin-yang
Candle     Clown      Dinosaur   Hammer     Heart      Igloo      Lips       Tree
Car        Clock      Eye        Ghost      Man        Moon       No-entry   Tree
Car        Eroteme    Glasses    Hammer     Hand       Scissors   Turtle     Zebra
Carrot     Clover     Dinosaur   Eye        Flame      Lock       Spider     Zebra
Carrot     Dog        Dolphin    Drop       Flower     Glasses    Snowflake  Tree
Cat        Cheese     Clef       Dinosaur   Dragon     Glasses    Moon       Skull
Cheese     Eroteme    Heart      Ladybird   Lock       No-entry   Snowflake  Sun
Clef       Clover     Drop       Ghost      Heart      Knight     Scissors   Snowman
Clock      Clown      Dolphin    Ice-cube   Lock       Scissors   Skull      Yin-yang
Clown      Flame      Flower     Hand       Knight     Ladybird   Moon       Pencil
Dinosaur   Dog        Key        No-entry   Pencil     Scissors   Splat      Web
Dolphin    Dragon     Eye        Hand       Heart      Key        Maple      Target
Flower     Ghost      Igloo      Skull      Sun        Target     Web        Zebra


This is actually a Full Dobble Deck of order N=7, where the order defines the number of :

• symbols (N2+N+1);
• cards (also N2+N+1);
• symbols per card (N+1); and
• cards containing any given symbol (also N+1)

A Full Dobble Deck is analogous to a finite projective plane with points and lines as cards and symbols (or as symbols and cards) and thus may be constructed for any prime-power order (it is an open question whether finite projective planes exist for any non-prime-power order). We shall restrict ourselves to prime orders (it is much simpler to implement).

For example here is a Full Dobble Deck of order 3 (PG(2,3)) using 13 objects/colours (lines) and 13 cards (points) with 4 colours per card (lines incident with each point):

...and here it is as a list of cards containing the objects [0,12]:

[[2,3,8,11],[2,5,6,7],[1,2,9,12],[4,7,8,9],[4,5,11,12],[1,3,4,6],[0,6,8,12],[0,3,5,9],[0,1,7,11],[1,5,8,10],[6,9,10,11],[0,2,4,10],[3,7,10,12]]


### The challenge

Given a prime (N) yield a Full Dobble Deck of that order in any convenient form.
One must be able to observe completion for N=11 (no brute forcing here)
For any other input undefined behaviour is acceptable.

* You may alternatively take as input N+1 or N2+N+1

Here is a Python program that validates a potential Full Dobble Deck (it must be given as a valid list of lists in Python syntax such as the "list of cards containing the objects [0,12]" example above).

• You might want to consider some performance constraint which eliminates brute force approaches and forces people to think about the mathematics. May 29, 2018 at 11:15
• @PeterTaylor Thanks for having a look at this. I was thinking of having a "one must be able to observe it complete successfully for N=11" but if you have a more concrete idea for a constraint do let me know (maybe it should simply be "N=11 in one minute"? I should probably code something up in a less efficient language to try...) On another note I am also wondering whether to restrict the input from prime-powers to just prime as supporting prime-powers as well as primes adds some complexity to the requirements on the implementation; still mulling, any further input very much appreciated. May 29, 2018 at 12:48
• Observing it complete is preferable to "in one minute" because it means that if I have a slower computer it doesn't invalidate my answer, but merely slows down when I can post it. Using just primes is certainly much easier because there's no need to build field towers with irreducible polynomials. I personally would be much more inclined to answer if it's primes only. May 29, 2018 at 14:03
• Related/dupe maybe? May 29, 2018 at 20:12
• @DomHastings weird I though, I'd searched both Dobble and Spot It, now I see two. The only things this would bring over the other code-golf question would be: (1) the alphabet there is bounded; and (2) implementing a constraint like Peter suggested. The current answer would need to iterate across (a least a large proportion of) the c(133,12) = 3.8*10^16 possible cards for N=11. I dont think (1) stops this being a dupe, but (2) might. Thoughts anyone? May 29, 2018 at 21:22
• @DomHastings Oh, and the brute-force solution there actually fails for N=4 (the first non-prime prime-power) even though I was planning on not requiring that to work the other (at present) does. May 29, 2018 at 22:33
• I only vaguely remembered it from when I first played Dobble too! Agree that the answer from the challenge I linked can't be copied over which I think is the main criteria for dupe, right? But the reverse might be true, all answers for your challenge should also solve the previous? So not sure if that make the older one a dupe, but that sounds too political for me! May 30, 2018 at 11:39
• If the input for this one is restricted to N being prime (or even prime-power) then answers to this would not necessarily solve the other. Furthermore while the other is limited to an alphabet of 62 (while I plan on an execution observation for N=11 which has an alphabet of size 133) answers to the other would not necessarily answer this one. Seems like maybe it's not a dupe after all, even though the premise is exactly the same! May 30, 2018 at 12:03

# 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?

(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]

• I look forward to the answers for this as I would like to have a generalized regex feature in Pytek. :D Feb 9, 2016 at 20:23
• [] is a match for "all members are odd". Feb 9, 2016 at 20:37
• @PeterTaylor Ah right, drinker's fallacy. Feb 9, 2016 at 22:22
• Can the input be in unary? Feb 9, 2016 at 23:33
• @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. Feb 9, 2016 at 23:34
• 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. Feb 11, 2016 at 16:06
• 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. Feb 11, 2016 at 20:52
• 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. Feb 11, 2016 at 21:11
• 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. Jun 22, 2016 at 18:05
• @Zgarb on the first half equals second half, do you mean arrays like [1, 2, 1, 2]? Jun 22, 2016 at 19:22
• @CᴏɴᴏʀO'Bʀɪᴇɴ Yes, exactly. Jun 22, 2016 at 20:58
• 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.
– xnor
Oct 4, 2016 at 1:22
• 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. Oct 4, 2016 at 7:48
• @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? Oct 5, 2016 at 2:49
• 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. Oct 5, 2016 at 4:41

# 🎲🎲Lucky Dice (KotH, WIP)🎲🎲

## 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...

## 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?

• Upvote this comment for MathJax tables. Apr 22, 2019 at 11:34
• Upvote this comment for Unicode art tables. Apr 22, 2019 at 11:35
• In your "Attacks" table, you want "halve their score" instead of "half their score." Apr 22, 2019 at 12:43
• I have given suggestions in the chat room Apr 22, 2019 at 17:28
• "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. Apr 22, 2019 at 17:29
• @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. Apr 25, 2019 at 14:31
• Why not just cut out the "way ahead" end condition and just make it a constant number of rounds? Apr 25, 2019 at 17:02
• @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. May 2, 2019 at 14:18

# 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

• 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. Aug 26, 2019 at 23:58
• 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. Aug 27, 2019 at 15:03
• @FryAmTheEggman Actually, that solution would give incorrect answers for all integers except 0.
– Joel
Aug 27, 2019 at 23:02
• 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].
– Joel
Aug 27, 2019 at 23:27
• @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. Aug 28, 2019 at 0:30
• @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 Aug 28, 2019 at 21:35
• @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.
– Joel
Aug 29, 2019 at 3:20
• 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. Aug 29, 2019 at 8:10
• @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. Aug 30, 2019 at 0:15
• You may add a note saying that the returned answer can be a float (like 5.0) or an integer.
– Joel
Aug 30, 2019 at 1:42
• @Joel good idea. Thanks for the tip Aug 30, 2019 at 2:02
• I just wonder, is it appropriate for me to post solutions after getting involved in improving the challenge?
– Joel
Aug 30, 2019 at 2:47
• @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... Aug 30, 2019 at 2:58
• Now that this has been posted, it would be best to delete it, to free up space Sep 4, 2019 at 9:07

# Win the competition king-of-the-hill

Write a Javascript anonymous function that, given two functions as strings, deterministically picks one as the winner and returns 1 if the first input wins and 2 if the second input wins. The choice must not depend on the order of inputs (that is, for any given input pair, the same program must always win no matter which one is first).

Every submission will be used to compare all unordered pairs of all solutions except self. Every time a program is chosen as the winner, it is assigned 1 point.

Submissions must not store any information between runs, interfere with the controller or somehow destroy my computer. There is no hard time limit, but intentionally creating an excessively slow solution counts as destroying my computer. Submissions must not duplicate other submissions or be longer than 200 KiB. Submissions must not rely on the input functions always halting (that is, they must not execute them or any parts of them).

You should give your submission a name (it should match the regex [A-Za-z ]+ and not coincide with any other solutions).

Controller in a snippet:

document.write(atob(PCFkb2N0eXBlIGh0bWw+CjxodG1sPgo8Ym9keT4KPHNjcmlwdD4KCWZ1bmN0aW9uIGFkZFByb2dy
YW0oKQoJewoJCWxldCBwcm9ncmFtc0xpc3QgPSBkb2N1bWVudC5nZXRFbGVtZW50QnlJZCgicHJv
Z3JhbXNMaXN0Iik7CgkJbGV0IHVsID0gZG9jdW1lbnQuZ2V0RWxlbWVudEJ5SWQoInByb2dyYW1z
TGlzdCIpOwoJCWxldCB0cGwgPSBkb2N1bWVudC5nZXRFbGVtZW50QnlJZCgicHJvZ3JhbVRlbXBs
YXRlIik7CgkJbGV0IG5ld05vZGUgPSBkb2N1bWVudC5pbXBvcnROb2RlKHRwbC5jb250ZW50LCB0
cnVlKTsKCQluZXdOb2RlLmNoaWxkcmVuWzBdLmNoaWxkcmVuWzFdLm9uY2xpY2sgPSByZW1vdmVQ
cm9ncmFtOwoJCXByb2dyYW1zTGlzdC5hcHBlbmRDaGlsZChuZXdOb2RlKTsKCX0KCWZ1bmN0aW9u
IHJlbW92ZVByb2dyYW0oZSkKCXsKCQlsZXQgcHJvZ3JhbXNMaXN0ID0gZG9jdW1lbnQuZ2V0RWxl
bWVudEJ5SWQoInByb2dyYW1zTGlzdCIpOwoJCWxldCBsaSA9IGUudGFyZ2V0LnBhcmVudEVsZW1l
bnQ7CgkJcHJvZ3JhbXNMaXN0LnJlbW92ZUNoaWxkKGxpKTsKCX0KCWZ1bmN0aW9uIHNpbXVsYXRl
KCkKCXsKCQlsZXQgcHJvZ3JhbXNMaXN0ID0gZG9jdW1lbnQuZ2V0RWxlbWVudEJ5SWQoInByb2dy
YW1zTGlzdCIpOwoJCWxldCBwcm9ncmFtcyA9IFtdOwoJCWxldCBuID0gcHJvZ3JhbXNMaXN0LmNo
ID0gcHJvZ3JhbXNMaXN0LmNoaWxkcmVuW2ldOwoJCQlsZXQgbmFtZSA9IGxpLmNoaWxkcmVuWzBd
LnZhbHVlOwoJCQlsZXQgc3JjID0gbGkuY2hpbGRyZW5bM10udmFsdWU7CgkJCXByb2dyYW1zW2ld
ID0ge25hbWU6IG5hbWUsIHNyYzogc3JjLCBzY29yZTogMH07CgkJfQoJCWxldCByZXN1bHRzTGlz
dCA9IGRvY3VtZW50LmdldEVsZW1lbnRCeUlkKCJyZXN1bHRzTGlzdCIpOwoJCXJlc3VsdHNMaXN0
LmlubmVySFRNTCA9ICcnOwoJCWZvcihsZXQgaSA9IDA7IGkgPCBuOyBpKyspCgkJewoJCQlsZXQg
bGkgPSBkb2N1bWVudC5jcmVhdGVFbGVtZW50KCJsaSIpOwoJCQlsaS5pbm5lckhUTUwgPSBgJHtw
cm9ncmFtc1tpXS5uYW1lfTogJHtwcm9ncmFtc1tpXS5zY29yZX1gOwoJCQlyZXN1bHRzTGlzdC5h
CgkJewoJCQlsZXQgY21wID0gZXZhbChwcm9ncmFtc1tjbXBpXS5zcmMpOwoJCQlmb3IobGV0IHAx
aSA9IDA7IHAxaSA8IG47IHAxaSsrKQoJCQlmb3IobGV0IHAyaSA9IHAxaSArIDE7IHAyaSA8IG47
CgkJCQlsZXQgcDEgPSBwcm9ncmFtc1twMWldLCBwMiA9IHByb2dyYW1zW3AyaV07CgkJCQlsZXQg
cmVzdWx0ID0gY21wKHAxLnNyYywgcDIuc3JjKTsKCQkJCWlmKHJlc3VsdCA9PT0gMSkKCQkJCQlw
MS5zY29yZSsrOwoJCQkJZWxzZSBpZihyZXN1bHQgPT09IDIpCgkJCQkJcDIuc2NvcmUrKzsKCQkJ
CWVsc2UgYWxlcnQoYHByb2dyYW0gJHtwcm9ncmFtc1tjbXBpXS5uYW1lfSByZXR1cm5lZCBpbnZh
bGlkIHJlc3VsdGApOwoJCQl9CgkJCWZvcihsZXQgaSA9IDA7IGkgPCBuOyBpKyspCgkJCQlyZXN1
bHRzTGlzdC5jaGlsZHJlbltpXS5pbm5lckhUTUwgPSBgJHtwcm9ncmFtc1tpXS5uYW1lfTogJHtw
cm9ncmFtc1tpXS5zY29yZX1gOwoJCX0KCX0KPC9zY3JpcHQ+Cjx0ZW1wbGF0ZSBpZD0icHJvZ3Jh
bVRlbXBsYXRlIj4KCTxsaT4KCQk8aW5wdXQgdHlwZT10ZXh0IHBsYWNlaG9sZGVyPSJuYW1lIi8+
CgkJPGlucHV0IHR5cGU9ImJ1dHRvbiIgdmFsdWU9InJlbW92ZSBwcm9ncmFtIj4KCQk8YnI+CgkJ
PHRleHRhcmVhIHBsYWNlaG9sZGVyPSJzb3VyY2UgY29kZSI+PC90ZXh0YXJlYT4KCTwvbGk+Cjwv
dGVtcGxhdGU+CjxzdHlsZT4KCS5jb2x1bW4geyBmbG9hdDogbGVmdDsgd2lkdGg6NTAlOyB9Cjwv
c3R5bGU+CjwvYm9keT4KPGhlYWQ+CjxkaXY+Cgk8ZGl2IGNsYXNzPSJjb2x1bW4iPgoJCTxpbnB1
dCB0eXBlPSJidXR0b24iIHZhbHVlPSJBZGQgcHJvZ3JhbSIgb25jbGljaz0iYWRkUHJvZ3JhbSgp
Ii8+CgkJPHVsIGlkPSJwcm9ncmFtc0xpc3QiPiA8L3VsPgoJPC9kaXY+Cgk8ZGl2IGNsYXNzPSJj
b2x1bW4iPgoJCTxpbnB1dCB0eXBlPSJidXR0b24iIHZhbHVlPSJSdW4gdGhlIGNvbXBldGl0aW9u
IiBvbmNsaWNrPSJzaW11bGF0ZSgpIi8+CgkJPGJyPgoJCUxhc3QgcnVuIHJlc3VsdHM6CgkJPGJy
PgoJCTx1bCBpZD0icmVzdWx0c0xpc3QiPiA8L3VsPgoJPC9kaXY+CjwvZGl2Pgo8L2hlYWQ+Cjwv
aHRtbD4K.split("\n").join))

This is tagged . Whoever wins the most wins!

After posting this, I will post two example (community wiki) answers: one that compares in lexicographic order, and another that compares first by byte count, then in lexicographic order (the reason for posting two is that at least 3 programs are needed for anyone to get any points).

# Sandbox stuff

• How can I prevent the last answer from always winning?
• Will that happen automatically, once enough answers are posted that it's nearly impossible to optimize for all of them?
• Would it be a good idea to introduce other requirements for the submissions, such as transitivity?
• Would it be a good idea to introduce a per-user submission limit (probably 1 or 2)?
• That is a really fun idea but probably more a social- than a programming challenge:) I guess one problem is that newer submissions can always be tuned to favor themselves against all the existing ones, so it is probably gonna end up as a "last submission wins" if you don't include any counter measures. Nov 26, 2019 at 9:06
• I suggest a rule against randomness (and probably a language restriction, too, those make it a lot easier) Nov 26, 2019 at 13:55
• @RedwolfPrograms I can see why is randomness bad, but why should I add the language restriction? I have thought about it, and know I will probably add it in the end (because I can write an automated tester only in some langauges), but does it actually improve anything? (I guess I'll restrict to one of Javascript, C# or Python; Javascript seems to be the most common so it is also the most likely) Nov 26, 2019 at 14:23
• @mypronounismonicareinstate No specific reason, but it tends to simplify things massively. It also allows the bots to more effectively read the source code Nov 26, 2019 at 14:48
• To minimise the problem flawr mentions you could consider only showing a "peek" of the programs to be judged, and then include a suitable upper bound on length. Of course, this has the problem of choosing that upper bound, but I think it may lead to a better back-and-forth? Posting will also still have a negative effect on your ability to win, however. Nov 26, 2019 at 19:34
• Some languages make extensive use of non-ascii characters, and some languages don't support non-ascii characters as input. Restricting the language is one way to solve this problem. Nov 29, 2019 at 17:13
• You should post it, just to see how it goes. Five upvotes just in the sandbox...if you added a language restriction and a few more rules to prevent the last answer from always winning, I think it'd be a popular challenge Dec 1, 2019 at 23:08
• Do we submit functions that take strings, programs that read from STDIN, or perhaps even functions that take functions?
– Jo King Mod
Dec 2, 2019 at 4:57
• I feel like the "no hashing" condition might be a bit problematic: For the last program submitted not to have an easy time with the rest, the scoring method of a program needs to be very hard to predict and game, and hashes are basically the optimal way about this. This then might end up with a challenge where people try to implement almost-but-not-quite hashing functions without upsetting you. Dec 14, 2019 at 9:22
• @AlienAtSystem I see your point; removed the hashing restriction and also a loophole (where a solution that is a few GiB large, but presumably full of comments so that it doesn't run too slowly, makes all others time out). Dec 14, 2019 at 12:09

# Pristine Polyglots

• Wow, pristine quines are already hard enough, and now you want it to be a polyglot too? Especially since polyglots often rely on one language ignoring the executing part of the other. Also, does it need to pristine in both languages, or both combined (i.e. removing a section can work in language A, as long as it errors in language B)?
– Jo King Mod
Nov 13, 2019 at 5:58
• @JoKing I have no issue with very difficult challenges :P Programs must be pristine in all languages used Sep 22, 2020 at 16:18
• Is an empty program a valid submission? Sep 22, 2020 at 17:16
• @thedefault. No, and in order to properly enforce the pristine requirement, I've made the minimum program length 2 bytes Sep 22, 2020 at 17:17
• Ok, so when removing any substring of length $n$, if the program does not do what it's supposed to do, does that count as a runtime error? Sep 24, 2020 at 14:06
• @Razetime I've edited the definition of an error, does it now answer your question? Sep 24, 2020 at 14:15
• Yep, clarified. Sep 24, 2020 at 14:17
• Won't the program "" be trivially pristine in a bunch of languages? Sep 25, 2020 at 1:59
• @Sisyphus Yes it will be, and I'm having trouble preventing something like that. I'm thinking requiring unaltered programs to produce a non-empty output, but I'm not too sure about that Sep 25, 2020 at 18:59
• Your rules say that a nonzero exit code is considered an "error", and a pristine program has to produce some output. Since an exit code is a valid form of output by default, would exit(12) be a pristine program? Removing the 2 and changing it to exit(1) would be an "error" by this definition, right? You might want to clarify that exit codes aren't a valid output. Sep 29, 2020 at 21:02
• You might also want to clarify whether an infinite loop that produces no output counts as an error or not. Sep 29, 2020 at 21:03
• @water_ghosts I think the definition of error in the post already covers infinite loops ("fail to terminate [...] within a finite amount of time"), and yeah, I suppose that would technically be a pristine program, so the output requirements have been updated to exclude output to STDERR (or nearest equivalent) Sep 29, 2020 at 21:28

# Inverted ragged list

• So, for [[1,2],3,4] is [1,2,[3],[4]] valid output?
– tsh
Jan 29 at 7:47
• Thanks @tsh, I added a rule against those kinds of lists Jan 29 at 8:17
• you can post alr 7 upvotes is plenty of community likes :) i like it tho anttiP gd job! Jan 31 at 5:38

# Add a hidden language to a polyglot

• "You can't reuse languages, but different versions of a language are considered different": How could someone reuse a language? It would have to have two separate behaviors on the same program, which is just impossible. What does this rule do? Why not just use the rules from the linked challenge?
– Wheat Wizard Mod
May 29 at 8:01
• @WheatWizard Oops May 29 at 9:13
• I'm a little concerned about someone using an obscure mixture of flags to hide from cops. Maybe a rule that the specific language (including flags and options) must have been used in a previous PPCG answer would solve this?
– Wheat Wizard Mod
May 29 at 9:17
• @WheatWizard On second thoughts, maybe you have to reveal the flag combinations, like the Programming Language Quiz. Otherwise people will do stuuff like this May 29 at 9:33

# Objection! code-golf

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).

No objections, Your Honor.


Examples

Input:

Evidence
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

• 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. Jun 4, 2014 at 16:59
• 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! Jun 4, 2014 at 17:09
• Wouldn't the Thinker Clock be the evidence being contradicted, then? There's more direct contradiction between the Thinker Clock and the last statement. Jun 4, 2014 at 17:14
• 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! Jun 4, 2014 at 17:21
• Ace Attorney strikes again! Jun 4, 2014 at 17:30
• 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. Jun 4, 2014 at 20:48
• @PeterTaylor I will figure out a way to formalize it better Jun 4, 2014 at 20:52
• @githubphagocyte Yep, my bad. That was a typo. Jun 4, 2014 at 20:53
• I feel like in many languages this scores for this will be dominated by string handling. Jun 5, 2014 at 15:57
• 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.
– user58826
Jun 9, 2017 at 16:48

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.

• 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. Oct 26, 2014 at 8:16
• I think this will be way too hard on the side of the cops to be feasible for PPCG. Oct 26, 2014 at 10:53
• @PeterTaylor I've fixed the first of those issues - do you have an intuition on how to deal with the second? Oct 26, 2014 at 13:38
• @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. Oct 26, 2014 at 13:40
• 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. Oct 26, 2014 at 15:30
• 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. Oct 26, 2014 at 17:40
• @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 :( Oct 27, 2014 at 0:36
• @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? Oct 27, 2014 at 0:55
• 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. Oct 27, 2014 at 12:16
• @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. Oct 29, 2014 at 10:27
• Looks like a restricted form of Minsky register machine. As a fan of MRMs, I approve. Oct 29, 2014 at 10:35
• @PeterTaylor yes, indeed, that's what I based it on. Oct 29, 2014 at 10:36
• 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. May 29, 2017 at 21:59
• In the non-preprocessed program, what whitespace is necessary? Is a+a+a+b+b+a{a-b+} valid? May 24, 2018 at 14:05
• @wastl not sure if I'll ever post this, but the preprocessor would ignore all whitespace, so that would be fine May 25, 2018 at 0:31

## 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:

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:

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]

• 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 Nov 15, 2015 at 16:38
• @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.
– user45941
Nov 15, 2015 at 16:43
• 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. Nov 15, 2015 at 16:52
• @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.
– user45941
Nov 15, 2015 at 17:01
• @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.
– Dair
Oct 21, 2016 at 22:02
• 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. May 25, 2018 at 23:52
• @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.
– user45941
May 26, 2018 at 6:46

## 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!

• 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. Feb 27, 2016 at 17:41
• 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. Feb 28, 2016 at 15:56

# 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?
• 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. Jan 3, 2016 at 15:41
• @TheNumberOne Could you put a link to / embed the controller? Or perhaps post this as an actual challenge? Jan 3, 2016 at 19:45
• @trichoplax Answered your questions in the post... though I am a little late :P Mar 15, 2016 at 20:45
• @BentNeeHumor Good to see we are both working at the same rate :) Mar 16, 2016 at 9:54
• 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? Jan 13, 2018 at 20:45
• (P.S. In case you hadn't seen it, mine finally made it to main after 2 years in the sandbox, back in July) Jan 13, 2018 at 20:46
• define "character" - is the memory ASCII-only? \00-\ff? any unicode character? Jan 13, 2018 at 21:31
• @trichoplax sorry, I haven't been active on here for a while. you can probably do whatever with it ;) Jan 13, 2018 at 23:43

# 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/

• Are the weights integers or floats? Oct 24, 2015 at 10:06
• 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? Oct 24, 2015 at 11:31
• 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. Oct 24, 2015 at 12:53
• 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. Jul 4, 2016 at 14:29
• 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? Jul 4, 2016 at 19:07

# Simulate Colorblindness code-challengetest-batteryoptical-char-recognitionimage-processing

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:

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.

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

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

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.

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?
• 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. Aug 24, 2016 at 10:03
• @PeterTaylor Thank you for reminding me to add the footnote. As for point 3, disallowing optimizing for the scoring cases takes care of that.
– user45941
Aug 24, 2016 at 10:11
• 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. Aug 24, 2016 at 12:03
• 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). Aug 24, 2016 at 15:32
• @Fatalize I wasn't sure about how people felt about the scoring set not being public, but I will go along with that suggestion.
– user45941
Aug 24, 2016 at 21:02

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:

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.

• 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. Dec 15, 2016 at 3:45
• 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. Dec 15, 2016 at 10:44
• Alright, thank you Mistah, and Peter, I'll be sure to remedy these qualms tonight! Dec 16, 2016 at 15:24
• 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? Dec 18, 2016 at 20:17
• @PeterTaylor spice is the framework for all modern advanced circuit simulators. Dec 18, 2016 at 20:19
• 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? Dec 18, 2016 at 20:29
• 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. Dec 18, 2016 at 23:21
• What's the distance from column a to power -?
– l4m2
Dec 31, 2017 at 14:49

# 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
– user45941
Sep 8, 2016 at 21:30
• @Mego my intention is to post these as distinct challenges and not a multipart challenge. Sep 8, 2016 at 21:54
• Then why is the multiple-holes tag present?
– user45941
Sep 8, 2016 at 21:57
• @Mego Oops, thanks for pointing that out Sep 9, 2016 at 1:19
• 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. Sep 13, 2016 at 14:16
• @PeterTaylor Good catch, I have specified an interval for the random numbers Sep 13, 2016 at 21:18
• 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. Sep 22, 2016 at 20:42
• @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, Sep 26, 2016 at 23:16

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.

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?]

• I still think this would be a fairly interesting problem. Any plans of still posting it at some point? Dec 12, 2014 at 22:49
• @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. Dec 13, 2014 at 6:15
• 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). Dec 13, 2014 at 12:03
• @programmer5000 Adopt it. That's fine. Jun 9, 2017 at 20:04

# Overview

While the ants of the highlands gather food and walk around each other, their distant cousins live in the forests below, growing fungus and aggressively raiding the ground and other nests for food. But like their highland counterparts, they want food, and they have armies of workers at their disposal to get at it.

## The Arena

The arena is a torodial 1000*2500 rectangular grid of cells. Each cell has one of eight colors, and at most one object at any one time. There are three types of objects of significance:

• Ants are either queens, which are spawned at the start of the game, or workers, which are spawned by queens.
• Food is a prized possession, and may be hoarded or consumed.
• Fungi are ant-placed objects which may be created at low cost and will grow slowly into food if left alone within the vicinity of food.

In this game, adjacency refers to being in the Moore Neighborhood unless otherwise specified. Some rules instead specify the von Neumann neighborhood.

## Game Overview

Each game, 16 submissions are put against each other in a game. If the competition has fewer than 16 submissions, all of them participate in a game, and if there are more, the 16 players are chosen randomly.

At the beginning of each game, each cell is reset to the color 0 (white), each submission used in the game has its corresponding submission object constructed, and 2500 food, and 16 queens are randomly scattered onto the map. Queens are very unlikely to be adjacent to food or other queens, but this is not a guarantee.

Then the game itself proceeds. The game lasts for 15000 turns, and each turn consists of the following phases, each of which is resolved concurrently in turn:

• Decide: Each ant's views are determined based on the current state of the arena and previous move history, and each ant's decision is determined and validated separately.
• Move: Each ant's decision is executed simultaneously, and the presence of multiple objects in a single cell resolved once all ants that decided to move into a cell have done so.
• Grow: Each object that can potentially change as a result of its surroundings has its neighborhood resolved, and the changes to the objects as a result happen simultaneously.

After the 15000 turns is up, the game ends. Submission objects are disposed of, caches trimmed down, food amounts logged, and the process started again if more scores need to be collected.

## Ant Senses

Each ant has a 5*5 area of sight centered on themselves. This area of sight is arranged to give the ants a relative sense of direction in the immediate term, but not innately in the long term. Ants can see the color of empty cells, and the properties of objects in filled cells, but not the color of filled cells.

Each ant also has an internal state that can take one of eight values. This state is internal to that ant, and to transfer information between herself and other ants or to remember more than this, she must position herself, drop payloads, or mark the ground below her, all which are subject to enemy interference.

## Ant Actions

Using their senses, ants can decide to move or drop payloads, and also color their current cell and change their current state simultaneously, once per turn. The coloring happens on the cell that the ant is currently in, before she moves.

Ants move orthogonally or diagonally one cell at a time. Worker ants are free to move into other cells at their own risk, but a queen may not move to a cell that her view shows is in the Moore neighborhood of a non-adjacent queen, nor to a cell that her view shows is in the von Neumann neighborhood of an adjacent queen. (However, it is legal for a queen to stay still on a cell adjacent to another queen.) Additionally, a queen without food may not move into a step into a cell already occupied by a laden worker, lest she step onto a laden worker that decides to stay still, which would without this restriction kill her.

Instead of moving, ants may instead drop a payload into an adjacent cell. Food payloads cost one food, and can only be performed if the ant is carrying food. Fungus payloads cost nothing, and may be freely placed. Ant payloads may be performed only by the queen, cost one food, and consistently result in a new loyal worker. It is legal to drop payloads on oneself, but this will usually result in the dropped object being picked back up or destroyed during collision resultion, to no substantive effect.

## Ant Lifecycle

Both queen and worker ants start in state 0. Worker ants are oriented such that their "from" cell is the cell the queen occupied when spawning the worker, while queen ants have a random initial orientation. From there, it is up to submissions to perform ant-specific initialization and differentiation if desired.

Once spawned, ants have an indefinite lifetime. Queen ants are guaranteed to live up to the end of the game, but worker ants may die by colliding with other ants.

## Ant Leeching

After movements and collisions are handled, a queen may neighbor one or more unladen enemy workers. If the number of such neighbors is equal to or less than the amount of food carried by that ant, then the queen loses food equal to the number of adjacent enemy workers. An unladen worker ant that neighbors one or more enemy queens that lose food this way gains one food. If a worker is next to multiple such enemy queens, she receives only one food, and one or more food is simply lost forever.

This transfer does not occur between allied ants. To perform such food transfers, you must command the laden ant to drop her food in an adjacent cell, and have another ally be in that cell to automatically pick it up.

## Fungi

Fungi are a means of spawning more food. Fungus farms may potentially lead to bountiful harvests for submissions that invest the resources to spawn, watch over, guard and harvest these fungi. They may also be strategically planted to obscure the ground or probe for food from a distance.

If food is within a 9 by 9 cell area centered around the fungus, then the fungus will grow. Internally, fungus takes 32768 steps to mature and spawn into food, and will gain 1 step per generation per piece of food placed in this vicinity. Therefore, placing more food in the vicinity of a fungus will speed up the fungus's growth, but will also make a nice feast for any ants that find it. If a fungus is not within the vicinity of food, it will not grow.

Growth stages are visible to all ants, and work as a coarse indicator of the age of the fungus. 0 means that the fungus has taken no steps toward maturity, 1 means the fungus has taken 1-7 steps toward maturity, 2 means the fungus has taken 8-63 steps toward maturity, 3 means the fungus has taken 64-511 steps toward maturity, 4 means the fungus has taken 512-4095 steps toward maturity, and 5 means the fungus has taken 4096-32767 steps toward maturity. (If a fungus completes all 32768 steps of growth, it matures into food in time for ants to see it as food the next turn.)

# Collision Resolution

As noted above, all decisions are executed at once, and collisions are resolved as they happen once surrounding ants have all their decisions executed.

## Ants

Collisions are an unavoidable consequence of multiple ants deciding to enter the same cell independently, or one or more ants entering a cell of an ant that decides not to move from it. Because ants may move only one cell at a time, up to 8 ants can move into the same cell at a time, and may run into an ant standing still in it. Queen-queen collisions are prevented by the rules restricting movement within the vicinity of other queens.

Collisions of ants are resolved depending on the ants involved. For the purposes of collision resolution, an ant is considered moving if and only if she spent her turn moving herself to a different cell. A newly spawned worker is treated like a moving worker.

• A queen, if involved in a collision, is always the only survivor. She loses one food if she moved to a cell containing a laden worker that stayed still. As stated previously, a queen without food may not move to a cell already occupied by a laden worker, preventing the case where an unladen queen would step on a laden worker staying still.
• The collision of more than one moving laden ants in a worker-only collision results in all involved workers dying, leaving food behind in the cell.
• If a still laden worker is in a worker-only collision with no more than one moving laden worker, she survives, but loses her food if there was a moving laden worker in the collision.
• If a single ant in a worker-only collision held food and she moved, then she alone is the survivor. She loses the food she carried if she moved onto a worker ant that stood still.
• If none of ants in a worker-only collision held food, then they all die.

## Food and Fungi

Fungi do not stack. If multiple fungi are placed into a cell at once, collision resolution proceeds as if only one were placed in. Putting fungus in a cell already containing fungus will destroy the old fungus and create a new one. Fungus is destroyed if it shares its cell with any other object.

A queen ant that stays or moves into a cell will pick up all contained and/or placed food in that cell. However, if a worker does the same, she can only pick up one of these pieces, and the rest are simply lost forever. If no ants are available to pick up the food, then only one food remains in the cell, with the rest lost forever.

# Submission

Each submission must be a Javascript class, with two methods holding special significance: a constructor, which is called once per game start to initialize each object before eachTurn is ever called, and an eachTurn method, which is called concurrently on all new ant views to determine what to do.

The constructor is given no arguments, while eachTurn is given to arguments, an integer corresponding to the current ant's state, and a 25-length view array.

A possible submission skeleton is as follows:

class MyAnt {

constructor() {
//TODO: You fill this in
}

eachTurn(state, view) {
//TODO: You also fill this in
}

}


## Input

The view array contains objects of the following form:

{
contents: Integer representing the contents of the cell, 0 for empty, 1 for food, 2 for fungus, 3 for ant
details: Object giving details about the cell contents
}


The details object yields further information about the object in the cell, and for each of the possible cell contents, it has the following forms:

• Empty Cell:

{
color: Integer from 0-7 inclusive representing color of the cell
}

• Cell with Food:

{} // Yes, an empty object

• Cell with Fungus:

{
stage: Integer from 0-5 representing fungus stage, a very coarse indicator of age and time to maturity
}

• Cell with Ant:

{
queen: Boolean representing whether the ant is a queen
friend: Boolean representing whether the ant is ally or enemy
food: Integer representing the current food stores of that ant
}


Each view object provided represents reflects the true state of a cell in the arena, albeit with incomplete information. The array itself always corresponds to a flattened 5*5 cell area of the arena centered on the ant, rotated 0, 90, 180, or 270 degrees such that:

• For ants that have moved since spawning, either the cell to the top or to the top left correspond to the cell that the ant was in before the one currently inhabited
• For worker ants that have not moved since spawning, either the cell to the top or to the top left correspond to the cell that the queen occupied the turn she spawned the worker
• For queen ants that have not moved since spawning, the orientation is randomly determined at the start of the game and remains until the queen moves

Indices in the view array correspond to cells in english reading order:

 0  1  2  3  4
5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24


There is no means of getting orientation information definitively either form inside or outside, and it must be inferred by current state and surroundings.

## Output

The output expected of the eachTurn method is an object with the following fields:

{
cell: (Mandatory) Integer in 0-8 inclusive, representing the cell to move to or to drop a payload to
spawn: (Optional) If present, 0 for no payload, or 1, 2, or 3 for a payload of food, fungus, or worker, respectively
state: (Optional) If present, an integer in 0-7 inclusive, representing the state to change to
color: (Optional) If present, an integer in 0-7 inclusive, representing the color to color the old cell with
}


The cell is interpreted with the same rotation as the view. Output cells 0-2 correspond to view indices 6-8, output cells 3-5 correspond to view indices 11-13, and output cells 6-8 correspond to view indices 16-18. If you compare this to the index chart above, this is in the same english reading order as the view array provided.

## No Side Effects

Submissions may not make state modifications except to themselves, and should take care so that internal state modifications from calls to eachTurn are not visible from outside. Debugging submissions using input and output is allowed, but once submitted as an answer, they are forbidden. Attempting to use input or output in a submission will result in an error and disqualification until edited out.

## Consistency

Submissions are expected to behave deterministically, and the eachTurn function is expected to be pure, returing the same decision object for a given combination of state and view, regardless of how eachTurn was previously called or is currently being called.

Built-in functions may be called, if they are similarly externally pure. Math.abs() is fine, but Date.getTime() is not, for some examples. In particular, you are not allowed to call Math.random(). Supply your own pseudorandom numbers from constants, ant states, and ant views.

Unless you have a good handle on javascript concurrency and are willing to stress-test the code for concurrency bugs, I recommend using well-tested concurrency patterns and performing only idempotent modifications of objects, or avoiding modification in the eachTurn object altogether.

## Resource Limits

Each game submission starts with 1 second of reserve time. Each call to the constructor and eachTurn add 1 millisecond to the reserve time, then decrement from the reserve time the time they took to execute. Calls are memoized, and don't count against a submission if they are found in cache. If a submission exhausts its reserve time, it is disqualified.

Submissions are also limited to 64 Megabytes of memory at any one time. Unlike the time limit, this limit is not enforced automatically, but if a submission turns out to consistently hog memory during games it participates in, I will use a memory profiler to determine if this limit is exceeded.

# After Submission

## Disqualification

To keep tournaments running smoothly, submissions are disqualified if their submission performs an invalid action. Disqualified submissions will be excluded from future games within a tournament after a disqualification, and will be kept out of future tournaments until the problem causing the disqualification is fixed.

The following conditions are detected automatically, and therefore result in disqualification immediately:

• Exhausting reserve time, as described above
• Returning an ill-formed or badly typed object from eachTurn
• Throwing an exception from the constructor or eachTurn
• Attempting to spawn food or workers with no food
• Attempting to spawn a worker with another worker
• Attempting to move a queen too close to another queen
• Attempting to move an unladen queen to a cell containing a laden worker
• Performing input/output from submitted answers

It might seem harsh to disqualify for a single wrong move or bug, rather than consider it "no move" or ignoring it, but by insisting on correctness from entries, I can focus my efforts on keeping tournaments running quickly and smoothly. This is not supposed to be an additional challenge, so a reason is given for any disqualification, and an explanation given, with specific input and output given to help solve the disqualifying problem.

You may provide multiple answers, provided that each one stands as a competitor in its own right, does not team up with other submissions, and at least in part is the product of your own substantive effort. You may take advantage of other submissions' weaknesses in an effort to achieve a higher score in comparison. Keep in mind that submissions come in, the chances of running into another particular submission will decrease.

You may also edit your submissions to tune them however you choose. There are no guidelines about whether to create a new post or edit a currently existing post; the choice is yours.

If you make a variation of another submission, remember to differentiate it, and if is derived from someone else's work, remeber to credit your sources.

## Scoring

At the end of a game, submissions are ranked on how much food their queens held at the end of the game. Submissions which score exactly equal to each other simply share the average of the ranks they would have if they scored differently from each other.

Submissions with the highest average rank over a multitude of games win. For this challenge, I will give out working first places from tournaments as scores accumulate enough significance that Dunn's test indicates that there is a single distinct first place with at least 98% confidence.

# Chat

For questions and extended discussion of this challenge, please use the chat room. Comments on this post are likely to be cleared up from time to time, while chat room text will be kept around permanently.

If you want to contribute to the specification itself, see the github repository hosting the latest changes to this specification, right here.

• Chat room for this contest: chat.stackexchange.com/rooms/77728/the-formic-forest May 18, 2018 at 23:53
• Part of the complexity is making sure that the queen can't become a wrecking ball, but has clearly-defined restrictions so she can't be disqualified by no fault of her own. Take it from me, there's been more than a bit of arguing about how much the queen can and can't do. May 21, 2018 at 22:13
• Why are submissions a JavaScript class? You have rules about side effects and consistency so why not just make a toy language that must be functionally pure to implement the ants? Since the ants have a very limited view of the world it could easily be done with a fall through pattern matching. This would have the added benefit that people wouldn't need to learn JavaScript to participate, they would need to learn the toy language but IMO the language could be simple enough that it could be completely understood from a short description.
– Wheat Wizard Mod
May 22, 2018 at 23:24
• I'm following the mold of the Formic Functions challenge. Javascript is a familiar language that has had thousands of dollars worth pumped into creating optimized implementations, and while it has its shares of impurities and quirks, it's old and widespread enough that its warts are well-known and well-documented. May 22, 2018 at 23:41
• @HatWizard If you have any suggestion you can make one, and then someone else may write a JS interpreter of that language. Or this... well, almost all of those are esolang, nevermind. May 24, 2018 at 11:52
• I think that the choice of JavaScript was one of the mistakes of the original formic functions challenge. The way I see it, it is like using a jackhammer to crack a nut, sure you can do it but Javascript is a lot of machinery for the task and some things you want like functional purity are lacking. I'm not even specifically opposed to Javascript, I think that any other production programming language would be overkill for the task even if it had functional purity. I'm suggesting a small language that could be programmed in about 30 min and learned in about 2 min.
– Wheat Wizard Mod
May 24, 2018 at 15:18
• @HatWizard I can't imagine a language that takes 2 minutes to learn to be nearly enough. I'm not against this idea in general, though. May 24, 2018 at 16:23
• @HatWizard a learning time of 2 minutes and a language powerful enough to have many approaches to the challenge (i.e. so not just specialized for pattern matching (even if that's the best option out there)) don't go together. Sure, >90% of my FF pattern matching code is just a ton of (nested) .maps and arrays but others might prefer different styles (e.g. Alions framework was class based, others just went linearly). For the original FF I thought of making a language specifically for my pattern matching ideology, but gave up as the requirements for me to consider it usable were too big. May 24, 2018 at 16:35

# Tower Defense (Abandoned)

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

# 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.

# 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

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.
• 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. Apr 19, 2018 at 18:59
• 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 Apr 19, 2018 at 19:01
• 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. Apr 19, 2018 at 19:07
• You should tag this with the language that submissions should be in. Apr 23, 2018 at 14:10
• 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. Apr 24, 2018 at 10:05
• You should specify the base of the logarithms used in your calculations. Apr 24, 2018 at 10:19
• "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. Apr 24, 2018 at 10:35
• 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. Apr 24, 2018 at 11:05
• Nitpick: a one-dimensional "grid" can be called a tape, for example. Apr 24, 2018 at 11:10
• Oh, I completely misunderstood the way invader stats work. I thought they were permanent buffs. I have removed the relevant comments. Apr 24, 2018 at 11:24
• 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? Apr 24, 2018 at 14:16
• For a similar challenge structure, see: codegolf.stackexchange.com/q/51029/31203 Apr 25, 2018 at 2:48
• 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? Apr 25, 2018 at 10:33
• @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 Apr 26, 2018 at 18:02
• 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. Jul 20, 2018 at 4:30

## Give numbers space number

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]

• [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.
– user62131
Nov 24, 2016 at 5:21
• Maybe this could be a decision problem then? Nov 24, 2016 at 8:28
• I think this is viable to post as is? May 7, 2021 at 5:20
• @Razetime Do you prefer the current version where impossible inputs aren't given to the decision problem or some other alternative?
– xnor
May 7, 2021 at 5:21
• I like the decision problem version more. Another idea would be the shortest combination of adjustments to reach the final array May 7, 2021 at 5:25

# Game of Lives

In this , your goal is to create a GOL (Game of Life) pattern that creates the most live cells after $$\n\$$ steps. The twist is, you will be competing against 3 other patterns on the same playing field at the same time.

Here are the rules of the Game of Life, with a couple of additions:

• Each player's starting living cells will be a specific colour.
• Any live cell with 2 or 3 live neighbours will stay alive, otherwise they'll die
• Note that 'neighbours' includes diagonals, so there are 8 possible neighbours for a cell.
• Any dead cell with exactly three neighbours will become a live cell with the colour of the most common neighbouring cell. If there is no majority, it will become a neutral colour, which won't count for further conversions.
• 2 Reds + 1 Blue = Red
• Red + Blue + Green = Neutral
• 2 Neutrals + Red = Red
• The playing field will be $$\x\$$ by $$\x\$$, where each quarter of the field is each player's starting configuration.
• Cells outside the playing field will always be considered as dead, and cannot be resurrected.
• Each starting configuration will be flipped and rotated so the right and bottom sides face the enemy.

For example, if your submission was:

And you plotted them against one another, the starting configuration could be:

Note how the bottom right isn't symmetrical, but still has the correct sides facing inwards.

Your submission should be a $$\x/2\$$ by $$\x/2\$$ GOL pattern that assumes it is in the top left corner.

Rounds will be run until only one competitor remains or the whole pattern repeats, where the competitor with the most cells when the pattern repeats is the winner.

### Sandbox:

• I haven't decided yet what sizes the playing field should be ($$\x\$$), nor how long each game should run ($$\n\$$).
• I was thinking about a 128 by 128 playing field, with 64 by 64 for each player. Is that too large or too small? For reference, the submission would be the size of: with some gliders and stuff for reference. Is that too many or too little? I haven't really got much reference.
• I am working on a visual controller like the Formic Functions question
• Overall winner? Check all combinations (way too much time as more submissions are added)? Tournament structure (multiple rounds per elimination)?
• So... where's the programming part? Nov 1, 2018 at 12:36
• @Alion Your submission is a GOL pattern. I guess you could say you're programming in GOL
– Jo King Mod
Nov 1, 2018 at 12:52
• Fairy enough. I just think it's a missed opportunity. You could easily make it into a JavaScript competition, where programs just run multiple rounds of the currently planned game, having access to what happened last round, and thus being able to iterate on their patterns. You don't exclude anything - at the start, you're just going to get a lot of static entries (and I don't think anyone's going to be discouraged by the fact the they have to write return before their pattern). Nov 1, 2018 at 13:03
• Unless you want to see the best static pattern, full stop. I can see that being fun as well - my comment was just a suggestion. Nov 1, 2018 at 13:04
• 1) Is it just me, or is the example picture screwed up? The distances to the dotted lines don't match up. 2) My computer would greatly appreciate it if the side length of the board was a power of 2 - the closest size to that is 128x128. 3) You could make the game last until the pattern settles down, i.e. starts being periodic. Nov 1, 2018 at 14:36
• I don't know if the challenge is interesting or not, mainly because it's very unintuitive to "program" in GoL. Nov 1, 2018 at 15:15
• @Alion "best" static pattern? I think how a pattern behaves also depends on its opponents. Nov 1, 2018 at 15:16
• @Alion I've fixed the image and changed the field size to 128, thanks.
– Jo King Mod
Nov 1, 2018 at 23:48
• @user202729 It might not be intuitive, but it is possible. Very possible.
– Jo King Mod
Nov 1, 2018 at 23:52
• We need to clarify the behavior on the borders outside of the whole playing field. Does the grid extend indefinitely? Or does it wrap around? Or maybe simply hard dead cells (cannot turn to alive whatsoever) outside the given area? Nov 2, 2018 at 5:32
• @Bubbler Cells outside the playing field will always be considered as dead, and cannot be resurrected. Though wrapping cells might be interesting...
– Jo King Mod
Nov 2, 2018 at 5:44
• Oops, I didn't notice that. Nov 2, 2018 at 6:04
• If they are all different colours, then the cell will be randomly picked from those colours. Given the nature of complex GoL patterns, I would suspect that one random cell choice can make a huge difference, so it might be nicer to keep the outcome deterministic and just kill such a cell. Nov 2, 2018 at 8:49
• @Laikoni For clarity: we're talking about cell colors being chosen randomly, right? While I agree that this could generate large bias within a single game, I don't think it matters in the grand scheme of things. As for the solution (if this is to be considered a problem) - breaking the GoL rules seems odd. For example, a 3-color blinker would just disappear. How about adding an additional, neutral color in that case? It would behave the same way that all the other colors behave, but wouldn't give any points to anyone. A 3-color blinker would lose its outer colors that way, but keep existing. Nov 2, 2018 at 10:29
• You should probably explicitly mention that GoL uses a Moore neighborhood (which includes diagonals), as opposed to a von Neumann neighborhood (which does not).
– user45941
Nov 2, 2018 at 23:12

# Possible binaries

This challenge is inspired by the AoC 2020, Day 14 - Part II, created by Eric Wastl and his team, which asks to output the possible binary values from a bitmask.

Let's say we've a bitmask like "10X0X0", then we've to find the possible binary values that can be generated by replacing an X with either 0 or 1.

So, the possible binaries are ["100000", "100010", "101000", "101010"].
When each of them are converted in decimal, then these are [32, 34, 40, 42] respectively.
And, finally the sum is 148.

# Test cases

INPUT: "X"
["0", "1"]
[0, 1]
OUTPUT: 1

INPUT: "0"
OUTPUT: 0

INPUT: "1"
OUTPUT: 1

INPUT: "1X0"
["100", "110"]
[4, 6]
OUTPUT: 10

INPUT: "1X0X1"
["10001", "10011", "11001", "11011"]
[17, 19, 25, 27]
OUTPUT: 88

INPUT: "X0X0X0X"
["0000000", "0000001", "0000100", "0000101", "0010000", "0010001", "0010100", "0010101",
"1000000", "1000001", "1000100", "1000101", "1010000", "1010001", "1010100", "1010101"]
[0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85]
OUTPUT: 680

INPUT: "1X1X1X1X1X1X1X1X1X1X1"
OUTPUT: 1789569024

INPUT: "1X01X01X01X01X01X01X01X01X01X01X01X0"
OUTPUT: 201053554790400

INPUT: "X000X000X000X000X000X000X000X000X000X000X000X000"
OUTPUT: 307445734561824768

INPUT: "101"
["101"]
[5]
OUTPUT: 5

INPUT: "XXX"
["000", "001", "010", "011", "100", "101", "110", "111"]
[0, 1, 2, 3, 4, 5, 6, 7]
OUTPUT: 28


# Rules

• It is guaranteed that $$\ 0 \leq \text{count}(X) \leq 12 \$$ and $$\ 1 \leq \text{length}(mask) \leq 48 \$$.
• Input can be either a string, or an array of chars (non-empty).
• Output will be the sum of the binaries in decimal.
• This is a , so fewest bytes will win!

## Meta

• Is the challenge's text clear enough?
• Is the constraint on count of X sufficient?
• Although I've tried a search, but is this a duplicate?
• Any suggestions/improvements in the attribution?
• Any tricky test case?
• Is there an upper bound on the size of an input bitmask? It would probably be good to provide one, but if there’s intentionally no upper bound, you should have a test case where the input is longer than 64 bits. Dec 14, 2020 at 18:54
• What about empty lists? (I'd like to have it as undefined, so we don't need to handle that special case). I believe the permutation tag doesn't apply here. And maybe an example for XXX`?
– xash
Dec 14, 2020 at 18:55
• @water_ghosts - Yes, there is an upper bound, I've edited that. Dec 15, 2020 at 2:51
• @xash - No, there will be no empty list/string. Added the example, and striked off the tag for now, but maybe it could be related somehow.. Dec 15, 2020 at 2:54

# Output a unique sign sequence

• Is shortness of the answer not supposed to be a factor at all? That is, we don't try to golf our answers? Even more, are voters supposed to consider just the sequence, or the code producing it? I'm not quite sure if "How clever is the implementation" is meant to apply to the code itself or just the general strategy.
– xnor
Sep 22, 2020 at 23:14
• @xnor No, golfing your answer is unimportant, but perfectly acceptable. Voters should consider both the code and the sequence, but primarily the sequence. The code should mainly be considered for how "elegant/clever/good" the vote perceives it to be. "How clever is the implementation" kinda applies to both the code and the strategy. Using language-specific tricks are a reason to consider code "clever" as is implemented a fully generalised method that any language to pick up and use with no trouble Sep 22, 2020 at 23:34
• I think this works much better as answer-chaining than as pop-con. As evidence I'd say that almost half of the challenge being devoted to explaining the voting rather than the challenge isn't a good sign. I think looking at recent successful pop-cons shows that pop-cons are generally only good if the task just won't lend itself at all to another scoring criterion. This, at least to me, seems like a great idea for answer-chaining. Sep 24, 2020 at 19:08
• @FryAmTheEggman I do dislike the fact that this is a pop-con, and the only reason it is, is because I couldn't find any other criteria which would inspire the creativity in sequences I'm looking for (e.g. the reductive attitude of code golf would make this very boring). The issue I see with making it answer chaining is that the winning criteria is a bit iffy. "Second-to-last" isn't the best winning criteria as already discussed on meta, but it gets even worse when new answers aren't more difficult than previous ones, as the challenge will continue ad infinitum until (cont) Sep 24, 2020 at 19:19
• (cont) people get bored and stop posting, rather than new answers are genuinely too difficult to make. There are an infinite number of sign sequences, so "running" out isn't an issue, and each new answer isn't more difficult because there are so many to choose from. Furthermore, I don't think it'd inspire the creativity I'm looking for. I don't think it'd be as bad as, say code golf, but I feel like people will resort to posting basic sequences in order to keep the chain from dying, thus extending it way beyond being fun Sep 24, 2020 at 19:20
• I had initially thought that preventing the obvious abuse cases was relatively simple (no prefix/suffixes and not periodic) but I've realised that it would actually be much more difficult than that. I still think this probably works better if massaged into something that works for answer-chaining, but you are probably right that it isn't as good a fit as my first impression was. Sep 24, 2020 at 20:36
• This might be interesting as a cops-and-robbers challenge, though it would have to be a finite slice of an infinite sequence in that case. Oct 2, 2020 at 19:21
• @Beefster I think the only (or maybe best) way this could work as a CnR is where the cops reveal their code+language (and maybe a few terms of the sequence) and the robbers have to find the generating function for that sequence, but that would almost definitely lead to obfuscated code, rather than „how is the sequence generated“ being the focal point for answerers, which pivots away from the main idea of the challenge being interesting sequences, not interesting code Oct 2, 2020 at 19:51