Sandbox for Proposed Challenges

Question

What is the Sandbox?

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

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

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

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

Add Proposal

Search the Sandbox

• Most people include applicable tags in their proposal, so for instance you can search for all king-of-the-hill proposals by merely adding the tag name in quotes to the search query.

Browse your pending proposals

Get the Sandbox Viewer to view the sandbox more easily

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

Answer 1

PPCG VS CR KotH

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

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

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

You have a few kinds of buildings:

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

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

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

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

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

Answer 2

PPCG Handwriting OCR code-challenge test-battery

(insert logo here once I make it)

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

Rules

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

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

Score

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

Handwriting Samples

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

---

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

Answer 3

2 Spooky 4 Me

In terms of halloween, some things are just too spooky for me... Feel like we need some serious doots from skeletons to fuel our hallowed weens. So, in the spirit of that end, print the following, exactly as it is shown, if and only if the input does not equal "DOOT" (in all caps ONLY):

               _.---._
             .'       '.
             :)       (:
             \ (@) (@) /
              \   A   /
               )     (
               \"""""/
                '._.'
                 .=.
         .---._.-.=.-._.---.
        / ':-(_.-: :-._)-:' \
       / /' (__.-: :-.__) '\ \
      / /  (___.-' '-.___)  \ \
     / /   (___.-'^'-.___)   \ \
    / /    (___.-'='-.___)    \ \
   / /     (____.'='.____)     \ \
  / /       (___.'='.___)       \ \
 (_.:       '---'.=.'---'       :._)
 :||        __  _.=._  __        ||:
 :||       (  '.-.=.-.'  )       ||:
 :||       \    '.=.'    /       ||:
 :||        \    .=.    /        ||:
 :||       .-'.'-._.-'.'-.       ||:
.:::\      ( ,): O O :(, )      /:::.
|||| '     / /''--'--''\ \     ' ||||
''''      / /           \ \      ''''
         / /             \ \
        / /               \ \
       / /                 \ \
      / /                   \ \
     / /                     \ \
    /.'                       '.\
   (_)'                       '(_)
    \\.                       .//
     \\.                     .//
      \\.                   .//
       \\.                 .//
        \\.               .//
         \\.             .//
          \\.           .//
          ///)         (\\\
        ,///'           '\\\,
       ///'               '\\\
      ""'                   '""

---

However, if the input DOES equal "DOOT", in all caps only, print this instead:

               _.---._
             .'       '.
             :)       (:
             \ (@) (@) /
              \   A   /
               )     (
               \"""""/
                '._.'          ' ''''    _''|
                 .=.       @=====***===::_  |
         .---._.-.=.-._.---. (( \-@|_) )) `.|
        / ':-(_.-: :-._)-:' \ ]--------'"
       / /' (__.-: :-.__) '\ \   ||:
      / /  (___.-' '-.___)  \ \  ||:
     / /   (___.-'^'-.___)   \ \ ||:
    / /    (___.-'='-.___)    \ \||:
   / /     (____.'='.____)     \ ||:
  / /       (___.'='.___)       \||:
 (_.:       '---'.=.'---'       :._)
 :||        __  _.=._  __       
 :||       (  '.-.=.-.'  )      
 :||       \    '.=.'    /       
 :||        \    .=.    /      
 :||       .-'.'-._.-'.'-.       
.:::\      ( ,): O O :(, )   
|||| '     / /''--'--''\ \    
''''      / /           \ \
         / /             \ \
        / /               \ \
       / /                 \ \
      / /                   \ \
     / /                     \ \
    /.'                       '.\
   (_)'                       '(_)
    \\.                       .//
     \\.                     .//
      \\.                   .//
       \\.                 .//
        \\.               .//
         \\.             .//
          \\.           .//
          ///)         (\\\
        ,///'           '\\\,
       ///'               '\\\
      ""'                   '""

---

Rules

• Trailing newlines and spaces are allowed.
• The design is horizontally symmetric, if you find inconsistencies let me know.

---

Doot it up, and enjoy!

code-golfascii-artkolmogrov-complexity

---

(Yes, I'm going to make it more official when posting on the actual SE)

Answer 4

Check equation proofs in a ring

code-golf math logic parsing decision-problem

The recent proof-golf to prove that (-a)×(-a) = a×a attracted a number of faulty submissions, because there wasn't an easy way to verify the proofs. So, let's write some proof checkers.

Input

Your program should take a sequence of strings representing expressions in a ring. Valid expressions consist of:

• Single-lowercase-letter variables (a to z)
• Two constants: the additive identity 0 and multiplicative identity 1
• Compound expressions: (X+Y), (X*Y) and (-X), where X and Y stand for subexpressions. (The parentheses must always be present, and there must be no whitespace.)

Task

Your program should check whether:

• All strings except the first and last represent valid expressions.
• Each expression (after the first) can be obtained from the preceding expression, by substituting one of the ring axioms in the expression exactly once.

Output truthy if these conditions are met. Otherwise, output falsey.

You may assume that the first and last strings in the input are valid expressions. But your program must check the intermediate strings.

The ring axioms

For this challenge, use the following substitution rules (and do not use any others). Substitutions can go both left-to-right and right-to-left.

1. (X+(Y+Z)) = ((X+Y)+Z)

2. (X+0) = X

3. (X+(-X)) = 0

4. (X+Y) = (Y+X)

5. (X*(Y*Z)) = ((X*Y)*Z)

6. (X*1) = X

7. (1*X) = X

8. (X*(Y+Z)) = ((X*Y)+(X*Z))

9. ((X+Y)*Z) = ((X*Z)+(Y*Z))

Scoring

Proof checkers are traditionally small, so that people can review them easily. Therefore, your program should be written in as few bytes as possible.

Meta comments

Is the input format fair for most languages and approaches?

Usually, code-golf problems should not require input validation. However, I thought it would be appropriate behaviour for a proof checker. I think the current spec still accommodates regex-based solutions.

The format for the original challenge also listed which axiom was used for each step. I could include this but I doubt that it improves the challenge much.

Test cases

Valid proofs

(0+a)
(a+0)
a

(a*(-1))
((a*(-1))+0)
((a*(-1))+(a+(-a)))
(((a*(-1))+a)+(-a))
(((a*(-1))+(a*1))+(-a))
((a*((-1)+1))+(-a))
((a*(1+(-1)))+(-a))
((a*0)+(-a))

Invalid proofs

These proofs are missing intermediate steps.

(0+a)
a

(-0)
((-0)+0)
0

((a*0)+(-a))
(0+(-a))

This is simply untrue, so no proof should ever be accepted.

(a*b)
(b*a)

Invalid expressions

Your proof checker should reject if these appear partway through a proof.

a+b

(a+-b)

(a + b)

1+

42

Answer 5

ASCII Stock Exchange answer-chainingcode-challenge

At the ASCII Stock Exchange, each character has a price. If a character is used more often, its price rises, otherwise the price decreases over time.

Initially, each character has price 10. [Meta: Is this too low/high?] After each answer, the prices change as follows:

• Each character that is not used in the answer's code has its price decreased by one, except when the price is already one, in which case it stays one.
• If a character is used n-times, then its price increases by n.

We define the score of a piece of code as the sum of the prices of its characters.

Example

For the sake of simplicity, we only consider characters A, B and C for this example. The challenge itself works with all bytes from \0 to \255. Initially, we have the following prices:

A -> 10, B -> 10, C -> 10

If the code of the first answer is BAAA, then is has a score of 40 (computed by taking the previous character prices into account) and the prices change to

A -> 13, B -> 11, C -> 9

If the next answer is CC, it has a score of 18 and the prices are updated to

A -> 12, B -> 10, C -> 11

The Task

Your objective is to write a program or function which calculates the score of a given piece of code in dependence of a list of previous answers which all influence the initial prices in the way described above.

The goal is to do so while minimizing the submission's score itself in the context of this challenge, that is your submission should be able to calculate its own score by taking a list of all previous submissions and its own source code as input.

The answer with the lowest score in each language wins.

Rules

• You may take a list of strings and a string as input, or require that the string to be scored is the first/last element of the list, or any other reasonable input format.
• You may not answer twice in a row.
• If an answer in language X has already been posted, you may only post another answer in language X if your submission achieves a lower score than the previous answer and the code is not identical.
• For this challenge only major releases of languages are considered their own language (e.g. Java 7 vs. Java 8). If there already is an answer in version A of a language and you have an answer in version B of the language and are in doubt whether version B is different enough from version A to be treated as different language, make sure that your code is not valid in version A.

Answer Format

To avoid having to copy all previous answers in order to calculate your submission's score, the chain will maintain a score calculator on TIO. Click on the link to the calculator in the previous answer and enter your code into the input field to calculate its score. Then add your code as a command-line argument, generate a new link and include it in your answer for the next submission.

If you wrote answer number 42 in Haskell with a score of 100, please format it as

42. Haskell, score 100

 <code>

TIO-Link, explanation, ...

Score calculator for next answer

Test Cases

These test cases are in the format list of strings, string to score -> result.

[], "BAAA" -> 40
["BAAA"], "CC" -> 18
["abc"], "abc" -> 33
["ab12", "aa22", "31a"], "ac23" -> 42
["a","b","c","d","e","f","g","h","i","j"], "123" -> 3

---

Meta

• Any idea what could be a good initial price? I picked the number 10 rather arbitrarily.
• Letting the cost of unused characters decrease until 0 might lead to score 0 answers. Do you think this is a problem and the minimum cost should be 1? Minimum changed to 1.
• I'm unsure what range of characters is a sensible choice. Limiting answers to printable ASCII plus white space would make things easier but also exclude a lot of languages. Another possibility would be to allow the whole byte range from \0 to \255. Then also golfing languages could participate, albeit to score them they would need to be converted to their byte form which usually contains a lot of unprintable characters. The score calculator is able to handle unprintables, but I don't know how to insert them into the text fields on TIO. All bytes from \0 to '\255' are allowed.
• Is the winning criterion suitable for answer chaining?
• A leader board snippet would be nice, but I don't know how to modify the existing ones. If someone could provide such a snippet, I would be very grateful.
• Relevant tags?

Answer 6

Note: If you are seeing this first, you might want to sort by active.

Unhappy numbers ascii art

Draw a square (or a rectangle as close to a square as possible) that represents the cycle of an unhappy number.

[ short description of unhappy numbers here + example ]

[ square formating rules ]

Input

Unhappy integer.

Output

ASCII art.

Example

Input:
4
Output:
 4 -  16 - 37 
20         58
42 - 145 - 89

Answer 7

Can the robotic arm reach itself?

( ͡° ͜ʖ ͡°) title is kinda sketch at the moment

A robotic arm is made up of a set of line segments, each with a positive integer length. Each joint on the robot has two possible positions: straight or 90 degrees clockwise.

Here is a robotic arm with 4 line segments of sizes 4, 2, 3, 2

+---+-+--+-+

Here is the same robot arm with one joint bent

+---+-+
      |
      |
      +
      |
      +

(vertical scale is kinda messed up)

Right now, the robotic arm isn't reaching itself. By bending all of the segments, however, the arm can reach itself.

+X--+
 |  |
 +--+

So, a robotic arm of size [4,2,3,2] can reach itself.

Here is a robotic arm of size [3,1,4,3] that can't reach itself:

+--++---+--+

+
|
|+--+
+---+

Whereas a robotic arm of size [1,1,2,2,3] can reach itself.

++-+-+--+

+
X++
| |
+-+

A robotic arm of size [2,2,3,5,3,4] can also reach itself

a-b-c--d----e--f---g

e--f
|  |
|  |
|a-b
|  g
d--c

Challenge

Given list of numbers, such as [1,2,3,4,5], output a truthy value of the robotic arm can reach itself and a falsey value if it cannot.

Answer 8

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 (N²+N+1);
• cards (also N²+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 N²+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).

code-golfgeometrycombinatoricsgame

Answer 9

Is this checkmate?

Input

A chess position in FEN format. You can assume the input is a valid chess position.

Output

Two distinct consistent outputs for checkmate or not.

Examples

8/8/8/8/8/5BKN/8/7k b - - 93 47
Mate

code-golf chess

Answer 10

Lexicographically earliest valid UTF-8 byte sequence permutation

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

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

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

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

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

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

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

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

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

Answer 11

Compose Fill In The Blanks

Answer 12

Move arrows along a contour

Posted here

ascii codegolf

Answer 13

Posted here

Answer 14

Cliquish Program

Challenge: Write a program that accepts a character (or byte, see additional information) as input. Then:

1. If the character is contained within the source code, output a different character also in your source code.
2. If the character is not contained within the source code, output a different character also not in your source code.

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

Additional Information

• Your program must consist of at least 2 distinct characters.
• Your program must have at least 2 possible outputs.
• Your program does not have to be deterministic; it may output a character at random (with any distribution), so long as it conforms to the above criteria.
• Your program may optionally take a byte as input instead of characters. If you do, the code page the input is written in must contain at least each distinct byte in the source code, as well as at least two different bytes not in the source code.
• You may take input and give output in any reasonable way. For example, you may take input as a function parameter, a command-line argument, a line from STDIN, a triple-nested array containing a single character, etc. You could output via return value, STDOUT, exit code (if applicable), fax output, etc. The input and output formats must be consistent, however.
• Your output can only consist of the required character, optionally followed by one trailing newline. Prompt information (such as ans =) is exempt from this rule; such unpreventable output is acceptable.

Answer 15

ASCII Maze Unrendering 3000

mazeascii-artcode-golf

Posted

Answer 16

Game of Lives

king-of-the-hill cellular-automata game-of-life

In this king-of-the-hill, 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)?

Answer 17

Question link

Answer 18

I attempted a problem I threw out as a suggested code-golf for 1p5.

In c, lex and yacc I needed more than 9600 characters ungolfed (fully commented, errors handled, some debugging code left in place, but some efficiency sacrificed in the name of shorter code), which seems pretty long, but c is about the most pessimal language you could choose for this problem except fortran 77 or something from the Turing Tarpit. The reference implementation can run its own build, which has some of that bootstrapping voodoo.

None-the-less, this is a relatively big project, and I don't want to post it unless people feel it is both well specified and interesting.

As yet there is no validation script, and I am not sure how one could be written as the acceptable output order could be post-order depth first or post-order breadth first and there is a left-first vs. right-first ambiguity on both. What a bother.

Aside: I'm quite proud of the lex and yacc part of my code, as I consider it spiffy.

---

A minimal implementation of the make (1) utility.

By minimal I mean,

• No built in rules, and no pattern or suffix rules.
• No variables and therefore no variable assignment or manipulations; also no variable expansion which includes no expansion of environment variables.
• No automatic variables like $< and $@.

This only leaves constructs (called rules) of the form

<target> ":" <prerequisite>* "\n" ["\t" <action> "\n"]*

Where each <target> and <prerequisite> is a whitespace delimited string which may (or may not) represent a filename. Empty lines have no effect and "#" marks the beginning of a end of line comment (the sequence "#[^\n]*\n" should be treated as "\n" so it does not interfere with rules; this has the side effect of making "#" illegal in targets, prerequisites and actions). Colons are prohibited in identifiers.

The program should take its input from the standard input or by reading a file called "makefile" - implementer's choice. The program then attempts to "build" every target named on the command line. Any targets specified on the command line which do not appear in the makefile and do not represent an existing file should generate an error and cause the program to exit before execution of any rules. In the event that no target is named on the command line, default to building the first target in the input.

Duplicate targets may (not must!) be treated as an error.

A target is deemed already built if

1. It names an existing file and
2. All its prerequisites are fulfilled

Otherwise it is built by

1. Building all unfulfilled prerequisites then
2. Running each <action> sequentially in the order they appear in the input, and if the action returns an exceptional exit state, stopping the program.

A prerequisite is deemed fulfilled if

• The prerequisite represents an existing file and
• The prerequisite is built and
• The target is "newer" than the (fully built) prerequisite

A target is deemed "older" (i.e. not "newer") than its prerequisite if one of

• Both represent files and the prerequisite has been modified more recently than the target.
• The target does not represent an existing file, and the prerequisite does.

apply.

Authors on systems which do not support fork/exec semantics may write a batch file or script which is invoked as the program terminates, but that script must stop on the first unsuccessful action.

Sample Input

# Babymake compatible makefile for babymake
all:babymake

babymake : lex.yy.o  y.tab.o  babymake.o 
    cc -o babymake lex.yy.o y.tab.o babymake.o

babymake.o : babymake.c babymake.h
    cc -c babymake.c

lex.yy.o: lex.yy.c y.tab.h
    cc -c lex.yy.c

lex.yy.c : babymake.l
    lex babymake.l

y.tab.o: y.tab.c babymake.h
    cc -c y.tab.c

y.tab.c : babymake.y  
    yacc -d babymake.y

clean:
    rm -f babymake.o  lex.yy.o  y.tab.o

cleaner: clean # just testing end of line comments
    rm -f y.tab.c y.tab.h
    rm -f lex.yy.c

bogus: boguser 
    echo "building bogus" # test in another context

Sample output

$ ./babymake < babymake.example cleaner
 rm -f babymake.o  lex.yy.o  y.tab.o
 rm -f y.tab.c y.tab.h
 rm -f lex.yy.c
$ ./babymake < babymake.example all    
 cc -c babymake.c
 yacc -d babymake.y
 cc -c y.tab.c
 lex babymake.l
 cc -c lex.yy.c
 cc -o babymake lex.yy.o y.tab.o babymake.o
$ ./babymake < babymake.example    
$ ./babymake < babymake.example bogus
ERRNO: 2: No such file or directory No rule to make target 'boguser'.

Answer 19

Verification of solutions to the 3 knishops problem

For the purposes of this question, a knishop is a fairy chess piece which can move to precisely those squares which are not an integer distance away. So knight moves (distance $\sqrt{5}$) are ok, as are bishop moves (non-zero multiples of $\sqrt(2)$) and many more besides.

The 3 knishops problem is to place 3 knishops on an infinite chessboard such that none of them attack each other, but every square other than the 3 they occupy is attacked by at least one of them. A more prosaic formulation is to find three lattice points which form an Erdős-Diophantine graph.

Your task is to write code (see below) which takes three co-ordinates as input and produces a truthy or falsy output: truthy if the co-ordinates are a solution to the 3 knishops problem, and falsy otherwise. The code must be able to handle each of the test cases below in no more than one minute on a reasonable desktop machine.

The small print

"Write code" should be understood to permit one of the following:

• A program which takes input via stdin and gives output via stdout. The permitted input formats are 6 integers, delimited by your choice of a comma or whitespace, and optionally wrapped in one of parentheses (), curly brackets {}, or square brackets []; or three pairs, each pair similarly delimited and wrapped, and the pairs similarly delimited and wrapped. Examples:

  0 0 3 4 12 13
  (0,0,3,4,12,13)
  {0,0},{3,4},{12,13}
  {{0 0} {3 4} {12 13}}
  [{0 0} {3 4} {12 13}]
  

  Or using different whitespace for the two types of delimiter:

  0 0
  3 4
  12 13
  

• A named function, verb, block, or equivalent which takes input as an array of six values, an array of three two-element arrays, three separate arrays of two-element arrays, or six separate parameters; and gives output as a return value.

You may assume that none of the input values or the unattacked points have coordinates outside the range $\pm 2^30$.

Test cases

input                          output

(0 0) (0 0) (0 0)              false
(0 0) (3 4) (12 13)            false
(5 -5) (8 -1) (2 -9)           false
(0 0) (384 2030) (720 1653)    true

TODO More test cases.

code-golf geometry chess

---

NB I need to code up some naïve approaches and test whether the one-minute restriction is actually relevant. I'm hoping that MathJAX will be enabled; if not, the stuff in dollars will be replaced before posting.

Answer 20

Write a Connect Four Bot

---

Your task is to write a Connect Four bot. Your submission must be less than 2000 bytes long. You may not save state. You may not use libraries or external resources that are, at my discretion, related to Connect Four.

Gameplay

Your submission will play against each other submission one hundred times. Each player will play first for exactly half of the matches. Each match flows like:

1. Player 1 drops a red token into a column.
2. If Player 1 has not won, then Player 2 drops a black token into a column.
3. If Player 2 has not won, repeat.

Tokens fall down a column until they collide with another token in the row beneath it or hit the bottom of the board. Your program will be terminated and called anew after each move. You win the match if you connect four tokens vertically, horizontally or diagonally.

The winner of the challenge is the submission with the most match wins at the end of a tournament.

Input

The first command line argument you will receive is the game board. Rows are ; delimited . Cells are , delimited. The first row is the top of the board. A cell contains 0 if unoccupied, 1 if occupied by Player 1, and 2 if occupied by Player 2. The board you receive will always be 7 columns by 6 row.

The second command line argument you will receive is your player number. That means 1 or 2.

Examples:

java ThatBot 0,0,0,0;0,0,0,0;0,2,1,0;0,1,2,1 1

Output

You will print the column for which you would like to move to STDOUT. Columns are zero indexed. The following earns an immediate loss:

• Dropping a token into a full column
• Dropping a token into a column that does not exist
• Failing to output anything to STDOUT within one second

Deliverables

You must submit the following:

• A program
• A unique name
• A method of calling your program via command line
• Any instructions I might need to compile your program. I'll try my best, but my best isn't always good enough.

---

king-of-the-hill

Answer 21

Fortnightly Challenge #4 - Data Structures

Join us in the Fortnightly Challenge Chat to work out the details of this challenge!

Imagine square coloured blocks where each side can be connected to another block, allowing you to move or rotate connected blocks as one. Let's call a collection of such blocks, all connected to each other either directly or indirectly, a group.

Your task is to simulate these blocks via a number of commands which you must implement.

Commands

All input commands will be given one per line (via STDIN), and likewise all query outputs should one per line (via STDOUT).

• place <x> <y> <colour>: Place a block with a given colour at the specified coordinates.
• remove <x> <y>: Remove the block at the specified coordinates, deleting any connections with it.
• connect <x1> <y1> <x2> <y2>: Connect two adjacent blocks.
• disconnect <x1> <y1> <x2> <y2>: Disconnect two adjacent blocks.
• count: Count the number of groups and print the result.
• move <x> <y> <dx> <dy>: Move the entire group containing the specified block by the given offset.
• rotate <x> <y> <times anticlockwise>: Rotate the entire group containing the specified block anticlockwise about said block by some number (guaranteed to be either 1, 2 or 3) of times
• connected <x1> <y1> <x2> <y2>: Print y if blocks exist at the two given coordinates and they are in the same group, or n otherwise.
• nearest <x> <y>: Print the nearest block to the given coordinate by Manhattan distance (difference in x-coordinate + difference in y-coordinate), in the form <x> <y> <colour>. If there are no placed blocks, print none. If there is more than one closest block, print any.
• colour <colour>: Print all block coordinates with the given colour, each space-separated and of the form (<x>, <y>). If there are no such blocks, print none.
• halt: Terminate the program

Errors

Commands will always be given with the correct number and type of arguments. However sometimes an operation doesn't make sense, for example:

• Placing a block where a block already exists
• Removing, connecting, disconnecting, moving or rotating non-existent blocks
• Connect or disconnecting blocks which are already connected or disconnected
• Move or rotate commands which end up with two blocks overlapping (with emphasis that only the final state matters — groups which are rotated 2 or 3 times do not need to check for overlaps after each rotation)

If any of the above occur, print Error: <command>. For example, if there is no block at 0,0, then the command remove 0 0 will result in

Error: remove 0 0

Note that queries should never result in an error.

Scoring

There will be six types of test cases:

1. A test which is biased towards place/remove commands
2. A test which is biased towards connect/disconnect/count/connected commands
3. A test which is biased towards move/rotate commands
4. A test which is biased towards nearest commands
5. A test which is biased towards colour commands
6. An all-rounder test

This is fastest-code, so the goal is to make your program process the commands as quickly as possible. A leaderboard will be kept for each type of test,, and the winner will be the user with the lowest sum of placements over all tests (e.g. if you came 1st, 3rd, 2nd, 2nd, 3rd, 4th then your score is 1 + 3 + 3 + 2 + 2 + 4 = 15).

The tests and test generator can be found on this Github page, along with a unit tester which will be run for each submission to ensure correctness.

Rules/clarifications

• To prevent cluttering the leaderboard, each user may provide at most one submission
• No multithreading or parallel processing
• Use no more than 2GB of RAM — this rule is not strictly enforced, but horribly space-inefficient solutions may be disqualified
• No third party libraries (standard libraries are OK)
• All coordinates are guaranteed to fit into a 32-bit int, and all colours are alphanumeric strings

Example

(in progress)

Answer 22

Bitstring Family Trees

This challenge is reproduced from memory and my own solution, from a challenge that was posted in the job-application section of http://itasoftware.com before they were bought by Google. I reached out to ITA and Google a few years ago, after the acquisition, to ask to re-post this here (and on codegolf.com when it existed) and never heard back from them.

A bitstring is a string of 1s and 0s. Bitstrings reproduce asexually through a mutation-prone process, producing a child that is a copy of its parent but with each bit flipped with 25% probability. Starting with a list containing one bitstring, we repeatedly select one bitstring from the list at random, produce its child, and add that child to the list. This produces a list of bitstrings, each of which (except the first) has somewhere earlier in the list a parent from which it was mutated.

Now, the challenge. Your program will be presented with a list of bitstrings produced as described above, but the order of the list will be shuffled. You are to calculate the least improbable family tree for the given bitstrings. If there are two or more such trees, choose any of them.

Your input can be in any useful format, including as a list/array of lists/strings as a function parameter or in a variable, already existing on the stack for a stack based language, or from stdin with delimiters but not operators, so four four-bit strings might be "1010\n1001\n1011\n0010" or "[1010,1001,1011,0010]" or even "4 1010100110110010".

Your output can be in any unambiguous format. The canonical format is a list of integers, where the nth integer in the list is the index of the nth provided bitstring's parent in the original list, and a sentinel value for the root entry. Another acceptable form could be an actual tree data structure. Either of these might be returned from a function, printed to stdout, left in a variable, or left on the stack of a stack based language.

The above two provisions should be interpreted with the context that this challenge is not about golfing the input and output code. It's about golfing the algorithmic logic.

For the example input above of 1010,1001,1011,0010 the most likely family tree is that the first entry is the root, the last two are children of the first, and the second is a child of the third, all three mutations involving a single bit flip out of four bits.

With the challenge I will provide a few data sets of different sizes (10 10-bit strings, 100 100-bit strings, maybe bigger) with their solutions.

Answer 23

The Virtual Prisoners king-of-the-hill

Background

The year is 2251. You are a self-evolving KOTH bot, in the mysterious land known as Programming Puzzles and Code Golf. To evolve, you need permissions, and to get permissions, you need reputation. You decide that the best way to do this is to take over all of the questions to gain as much reputation as possible. The only problem? Every other bot has decided to do the exact same thing.

Game Explanation

Each round is battled on a question, with 11 vote nodes, between you and your enemy. The board starts as this:

A1 A2 A3 N4 N5 N6 N7 N8 B9 B10 B11

A is player A's nodes, B is player B's nodes, and N is a neutral node.
Each turn, you may:

• Vote on a vote node. If both players vote, nothing happens. If one side votes:
  • and the node is controlled by no-one (neutral), it becomes that side's.
  • and it is controlled by the voter's enemy, it becomes neutral.
  • and it is controlled by the voter, nothing happens.
• Guard a vote node. This guards the node from votes (friendly or enemy) for 2 turns.
• Use your 'power'. The powers are listed below, including how to use them.

Your side wins if it controls at least 2/3rds (66%) of the vote nodes.

10000 rounds will be run, and the winner of the KOTH is whichever bot has the most wins (in the event of a tie, or indeterminate outcome, more matches are run until a clear winner is decided.)

How Your Bot Should Work

It should accept as command-line arguments:
B A1 A2 A3 N4 N5 N6 N7 N8 B9 B10 B11
Where A denotes Player A's nodes, N denotes a neutral node, B denotes Player B's nodes, and the first argument (B in this case) is the player your bot is. (This is decided randomly, your bot should work regardless.)
It should return one of the following (powers are general rules):

• V-4, vote on node 4
  
• G-3, guard node 3
  

• P-N, use power 'Neutralize'
  with or without a trailing newline.

  Powers

  Intended to give bots a small boost. If X was your power, you would use P-X. You may only have one power per bot.

• N - Neutralize: Turn 2 random nodes to neutral ones.

• R - Rebellion: Pick a random node, and randomly turn it to a friendly, neutral, or hostile node.
• S - Swift Strikes: Pick two random nodes, and vote on them.
  
  

Here are the extra rules:

• The bots must fully run offline.
• The bots may not attempt to read any files, including their own source code.
• The bots may not tamper with, hack, or destroy other bots.
• The bots must return one of the three commands (V, G, or P). If they do not, they forfeit their turn.
• The bots must not be targeting other bots specifically. (Beating general strategies is welcome.)
• You may update your bot as often as you like, but bots that are updated very frequently with no good reason (i.e, fixing fatal errors is a good reason) will be disqualified.
• Your bot must take under 90 seconds for it's turn. If it takes longer, it will be disqualified.

Submission contents

Your submission must contain:

• The code for the bot
• The language it is written in (and a link to an offline interpreter, if necessary)
• Your bot's name (for the leaderboards)
• How to compile and run your bot

If you do not include all of the required items in your submission, you will be notified, but your bot may not compete until this is fixed.

Example Match

Matches are organized between 2 randomly-selected bots. Here is an example, with bots A and B:
The board begins as this:

A1 A2 A3 N4 N5 N6 N7 N8 B9 B10 B11

Bot A makes his move, voting on N4, then Bot B votes on N5:

A1 A2 A3 A4 B5 N6 N7 N8 B9 B10 B11

Node 4 becomes A4, and it is now controlled by Bot A. Likewise, node 5 becomes B5.

A votes on N8, and so does B:

A1 A2 A3 A4 B5 N6 N7 N8 B9 B10 B11

Why did nothing happen? That's because both bots voted on the same node - cancelling out each other's effects.

When one bot controls 66% or greater of the nodes, that bot gains a win and the other bot gains a loss.

The game ends after 1024 turns, to prevent any bots that wait around forever. Whoever has the most nodes afterwards wins, or a draw if they have the same amount.

Additional Notes

• I will be submitting an example bot written in Python as part of my challenge. You are free to use and modify this bot for your submission.
• If your bot gives invalid output (not of the form C-A, where C is the command and A is the argument), the bot forfeits its turn. If it does, you will be notified, and your bot will be removed until it is fixed.

Meta Questions and Notes

• Are there any loopholes?
• Should I add/modify/delete some of the powers?
• Is something too simple/confusing/uninteresting/overpowered?
• Should bots be able to see which nodes are and are not guarded?
• Should I limit people to one bot? If not, I will prevent the same person's bots from battling each other.
• I have thought of the following alternative way to win matches:
  • The game lasts 1024 turns. Whoever has the most nodes at the end wins.
  • If, at one point, one bot controls all 11 nodes, that bot automatically wins.
• Would this be a better win condition?

Answer 24

I nearly posted this without sandboxing, but thought it was perhaps too trivial - comments welcome. I was considering perhaps making it restricted-source too with no digits [0-9] in the source code.Done.

Golf the numbers round a dartboard

code-golf restricted-source kolmogorov-complexity

For those of you not familiar with the game of darts, a standard dartboard looks like this:

This challenge is simple - output the sequence of numbers starting from 20 moving in a clockwise direction:

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

To make it a bit more interesting, the digits [0-9] may not appear anywhere in your source code.

• Your entry must not accept any input and it must output this list in exactly this order.
• The formatting of the list output may be whatever is convenient for your language.
• You must not use any builtins designed explicitly to generate this sequence.

OEIS fans may like to note that this is sequence has an entry.

Answer 25

Verify a game of Morpion Solitaire

code-golfgamegridgraphs

Morpion Solitaire is an interesting, unsolved "single-player game". (The linked site lists several variants - we're talking about 5T here.) It has been proven that solving or even approximating it is NP-hard. But we're going to do something simpler here: your challenge will be to verify whether the game has been played correctly.

The rules are fairly simple. You start on a regular (infinite) grid, with 36 intersections marked in the following shape:

Now a move consists of drawing a straight line segment, orthogonally or 45 degrees with the grid, through four marked and one unmarked intersection. The unmarked intersection will then be marked for future moves:

The lines may cross or touch, but they must never overlap (notice that the last move shares an endpoint in a straight line with an earlier move, but does not overlap with it). The goal of the game is to make as many move as possible. The world record is at 178 moves.

Because the grid gets very messy after a while, it becomes very hard to reconstruct a game. People work around this problem, by writing consecutive numbers into the intersections they add. However, even when this is not done, it is always possible to verify the validity of game.

Further reading:

• Morpion Solitaire: the full page the rules link was taken from. Beware of iframes.
• Wikipedia article: note that this uses a different initial setup.

The Challenge

You're given an ASCII representation of a played game of Morpion Solitaire (the game may or may not be finished). Every other cell represents an intersection, which can be either unmarked (.), one of the initial intersections (o) or one of the intersections added by a move (#). All other cells are either spaces, or one of -, |, /, \, X indicating that a line-segment was drawn across the two adjacent intersections. The example above would look like this:

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

. . . . o-o-o-o-# . . .
        |/     /       
. . . . o . . o . . . .
       /|    /         
. . . # o . # o . . . .
     /  |  /           
. o-o-o-o-# . o o o o .
   /    |/             
. o . . # . . . . . o .
        |              
. o . . # . . . . . o .
        |              
. o o o o . . o o o o .
        |              
. . . . o . . o . . . .
        |              
. . . . o . . o . . . .

. . . . o o o o . . . .

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

Output a truthy value if the game represented by graph can be played by following the rules, and a falsy value otherwise.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You may assume that the initial intersections always form the cross shape displayed above (although I doubt any answers will be affected by this).

Your code should solve any of the test in less than 5 seconds. This should not be an issue as very efficient solutions exist.

Standard code-golf rules apply.

Sandbox Notes

• Will add test cases...

Answer 26

Four-Byte Bloom Filter

Bloom filters are cool. In the words of that Wikipedia article:

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom filter has a 100% recall rate. In other words, a query returns either "possibly in set" or "definitely not in set".

The motivation behind Bloom filters is that, by giving up perfect accuracy, the amount of memory necessary can be dramatically decreased.

A Bloom filter takes the form of a set of bits, along with a set of hash functions. To insert something into the Bloom filter, calculate the N different hashes and flip those bits to 1.

initialization 
00000000

letter `P` maps to 1 when using hash function F and 6 when using hash function G
01000010

Additional elements are added over top previous ones.

letter `h` maps to 6 and 4
01001010

To test if an element is a member of a set, perform the hashes and check to see if those bits are 1. If not all of them are 1, then it can't possibly be a member of the set. If they are all 1s, then it could be a member.

letter `W` maps to 0 and 4
01001010
^   ^
`W` is not a member

letter `P` maps to 1 and 6
01001010
 ^    ^
`P` could be a member (it is)

letter `i` maps to 4 and 1
01001010
 ^  ^
`i` could be a member (it is a false positive)

As more elements are added to the set, the probability of false positives increases. In large-scale applications, a Bloom filter with a small error rate is still an order of magnitude smaller than an exact database. Below is a neat diagram from this great article on probabilistic data structures.

---

In this challenge, you will implement a miniature Bloom filter. A really, really small Bloom filter with 32 bits. Your data type will be the 94 non-whitespace printable ASCII characters.

Functionality

The Bloom filter will have 32 bits and 2 hash functions. It is up to you what those two hash functions are, they simply must be decently independent of one another. (Sandbox note, should I specify the hash functions?). Your program will be asked to do two separate tasks:

• Given a current state of the bloom filter and a list of characters, add those characters to the filter and output the new filter state
• Given a current state of the bloom filter and a list of characters, test those characters for membership and output a list of truthy (could be a member) or falsey (definitely not a member) values.

Formatting specifics

Input consists of the current state, an operation, and a list of characters. The Bloom filter state will be represented as a string of 8 hexadecimal characters. This will then be followed by either + for adding or ? for membership testing. Finally, there will be a list of between 1 and 94 characters (printable non-whitespace ASCII) as data points.

Output will either be the new state, as 8 hex characters, or a list of truthy/falsey values.

Example I/O

This represents adding the characters in my username to a blank filter
00000000+PhiNotPi
This is a possible output (7 bits have been permanently flipped)
48a01030

This represent adding the character 1 to the current filter
48a01030+1
This is a possible output (9 bits flipped so far)
48a01074

This represents testing for membership of Phi
48a01074?Phi
Output must be all true since they were added in earlier
[True, True, True]

This represents testing for membership of 12345
48a01074?1234
Output must be true for 1, but not necessarily false for the others
[True, False, False, True, False]

Answer 27

The largest convex polygon

Given an input of at least one coordinate pair on the Cartesian plane, determine the largest number of sides a convex, non-self-intersecting polygon formed from those points can have.

A convex polygon is a polygon such that there is an angle strictly less than 180˚ and greater than 0˚ between each pair of consecutive sides. Note that if three points are collinear, they still only form one side. Two sides cannot have a 180˚ angle between them.

The ordinate and abscissa of a coordinate are not necessarily integers, and they can be positive, negative, or zero.

If there are less than 3 points, or if the points inputted cannot form a convex polygon, the program should output 0.

Test cases

(0,0) (1,1) (3,4)
==> 3

(0,0) (-1,-1) (5,5)
==> 0

(-1,0) (1,0) (0,1) (5,5) (-5,5) (0,-5)
==> 3

(-3,2) (4,6) (-1,2) (0,4) (5,-3) (-2,-2) (1,1)
==> 5

(0,0) (10,0) (10,10) (9,1) (10,4) (9,6) (5,4)
==> 5

Here are pictures for the test cases, in order. Note that solutions are not necessarily unique. (Made with Geogebra)

Answer 28

Battle Snake

king-of-the-hill

Introduction

The classic snake game where bots control the snakes. Can you create a bot that out lives the rest?

Snakes will enter the arena and hope to survive. Eat pellets and grow in length. Can you force your competition to crash and die while you survive?

See video for visuals of my simple bot playing against itself. I am sure you can do better!

Features

• Real-time graphics provided by Love2D
• Multiple snakes per game
• Solo game as well
• Humans can play too!
• Highly configurable settings
• Supports any programming language that can use sockets.

Requirements

• Love2D: 2D game engine written for Lua
• Socket-compatible programming language
• Controller: The main controller for this challenege

Optional

• Lua winapi: Handy way to spawn processes in the background

Controller Contents

1. main.lua: Main loop for Love.
2. snake.lua: Support library for game mechanics
3. config.lua: Configuration settings.
4. bots\: location of externally-defined bots
   1. simple.lua: Example bot written in Lua

Executing

Run the love2d executable on the controller directory

love.exe <location_of>\battlesnake

or

[Recommended] Use ZeroBrane Studio with the 'Love' interpreter. Change your project directory to where you installed the controller, and then run the script in ZeroBrane. You'll still have to install Love separately.

Configuration

All configurable options are located in the config.lua file in the controller. The options are detailed in that file itself.

Rules

General snake rules apply. Hit something and you die. This includes the walls, other snakes, or even yourself.

Collisions happen before the board is updated. Therefore, if you move to a spot where another snake's tail is, it will still cause a collision. Even though it could be moving away that turn. If two or more snakes enter the same spot the same turn, they all collide with each other.

Eat a pellet and gain points. You also grow in size for a number of turns. Your head continues moving but your tail stays stationary until you stop growing.

Mechanics

The game uses a server-client model, where the main game loop is the server and each snake is a client. The game communicates to each snake over TCP through an assigned port. The default host is the localhost, no external networks are required.

When the game starts, it will start each snake (aka bot) by starting its associated program and sending the IP ADDRESS and PORT and PLAYER ID to it as input arguments:

bots\someBot.exe 127.0.0.1 52311 1

The main server then waits for a socket connection from that bot at the given IP and PORT. If the connection times out, it will error and the game will not start. If the server receives a connection from the bot, it will proceed on to the next bot.

Once all bots are started and connected to the server, the game will be generated. Bots are expected to block until receiving data from the server. Typically this is just an infinite loop with a blocking socket.receive() call at the top of the loop.

Board

The game board can be of any width and height. The coordinate system starts at x = 1, y = 1 at the top-left. Increasing x values go left-to-right and increasing y values go top-to-bottom. The board has hard walls, hitting them will kill your snake. (Lua is 1-based, that is why it starts at 1)

Order of Events

1. First the game settings are broadcast to all bots

   1. Board Information

      bi width,height

      Where width and height are integer values

   2. Pellet Location

      p x,y

      Where x and y are integer values >= 1 and <= to their respective width and height.

   3. For each bot

      • For each body part, starting at the head and going to the tail

        si snake_id x,y

        Where snake_id is an integer value, and x and y are as described before.

   4. Ready signal

      ready

      All bots are initialized by now, so the next command will be from the main game loop.

2. Main Loop

   1. For each tick (tick is when all snake movements will be applied)

      1. Server will broadcast to each bot

         mov

         The bot needs to respond to this request with a direction to head in

         • r Head Right
         • l Head Left
         • u Head Up
         • d Head Down

         If the bot doesn't respond within a specified time, it will continue to move in its previous direction. (Previous direction is r on the first turn)

         The bot should send a single char back, nothing more will be parsed.

      2. Check End Game Conditions

         If the game ended this tick each bot will be sent either a quit or nil message from the server. Each bot is expected to clean up after itself when it receives this signal.

      3. Updated Pellet Info [optional]

         If a pellet was eaten this tick, a new pellet packet will be broadcast to all active bots

         p x,y

      4. Server broadcasts snake deltas that were applied this turn

         s snake_id new_x,new_y,removed_x,removed_y

         Where all parameters are integers. new_x and new_y are the new head location of a given snake.

         If removed_x and removed_y are >= 1, this is where the tail used to be, so each bot knows the updated board.

         If remove_x and removed_y are == -1, then that bot is actively growing in size, so its tail didn't move.

         If a snake died this tick, its deltas will not be broadcast. It is up to the bots to remove the body from their game state.

See the example bot for details

Matches

Games are grouped together in best-of matches. For the purposes of the bots, they do not need to understand the concept of a match. The bot that wins the required number of games in a match is declared the match winner.

Scoring

1. Scoring

   • Match winner: +2500 points per match
   • Last Man Standing: +1000 points per game
   • Pellets Eaten: +50 points per pellet
   • Game Ticks Alive: +1 point per tick

   If two or more bots enter the same square on the same tick, they all die. If this square happened to be the pellet, none of those bots will be rewarded the pellet points. However, the pellet will be "consumed" and a new location will be generated for the remaining bots to eat.

   If there is a tie at the end of the game among the bots, the game is a wash. A new game will be started.

2. King-of-the-hill Scoring

   This challenge will combine two parts: A solo effort and a classic king-of-the-hill part.

   Each bot will be given the same random seed at the start of the competition. There will also be imposed a maximum time between eating pellets to prevent bots from going around in circles to farm points.

   1. Solo

      Each bot will enter into a 10-game match to see how long it lasts and how well it eats by itself. The scores of each game in the match will be summed to compose its final Solo-score.

   2. King-of-the-hill

      All the bots will enter into a best-of-39 match. If the game ends and there is still a final living bot, the game still end at that point. That bot will be given the last man standing bonus.

      The scores of each game will be summed and composed into the snakes final KOTH-score.

   3. Final Scoring

      All the bots will be ranked in each part separately. Ties in ranks are permitted at this stage. Then their positional rank in each part will be summed together to give their final score. The bot with the lowest combined rank wins!

      In case of a tie at this level, the bot with the better KOTH rank will win. If still a tie, the bot with the better Solo rank will win.

Sandbox Questions

My biggest concerns

1. Requires a few third-party programs to work. So that will limit the number of people who enter.
2. Requires sockets. I couldn't figure out a good way with Lua\Love2d to have bidirectional pipes with STDIN and STDOUT. So I thought sockets would be the best alternative to open the challenge to as many people as possible.
3. Too hard?
4. Haven't optimized scoring yet.

Answer 29

Count the Cats code-challenge image-processing test-battery counting

This is a cat:

Specifically, that is my cat. She is my only cat. And, in that image, there is only one cat: her.

These are also cats (image credit):

In that picture, there are two cats. It is relatively easy to count them, thanks to their distinct coloring.

This is a picture of 5 cats (image credit):

It's harder to differentiate the cats because of their similar coloring, but there are definitely 5.

This is a landscape (image credit):

There are no cats in this image.

The Challenge

Given an image, output the number of cats in the image.

Rules

• Submissions must output and terminate within 1 minute for a single image.
• Any common image format is acceptable for input, as long as no additional data (such as the number of cats present in the image) is encoded in the format.
• Submissions must be fully deterministic, and make a genuine attempt at counting the cats. Outputting a random number or a consistent but unrelated number (such as the value of the last hex digit of the SHA-256 hash of the image data) is not allowed.
• The images in the test cases will contain no animals besides cats. There may or may not be humans in the images - they are not cats, and thus should not be counted as cats.

Scoring

The score for a single image is the square of the difference between the true number of cats in the image and the output of the submission ((actual - output)**2). The total score is the sum of all of the individual scores. The submission with the lowest score wins.

[scoring images TBD]

Answer 30

The Ifelse Tower

code-golf kolmogorov-complexity

You are an inhabitant of the whimsical country of Forance, filled with programmers.

Life in Forance is said to be extremely repetitive, which isn't good to attract tourists. For this, authorities of Forance want to hire someone to print tons of postcards to promote their most iconic landmark: the Ifelse tower.

                   if
                   if
                   if
                   if
                   if
                   if
                   if
                  else
                  else
                 ifelse
                  else
                  else
                ifelseif
                ifelseif
               elseifelse
              ifelseifelse
            elseifelseifelse
              ifelseifelse
              ifelseifelse
              else    else
             else      else
            else        else
           else          else
          else            else
       ifelseifelseifelseifelseif
       ifelseifelseifelseifelseif
       ifelseifelseifelseifelseif
       ifelseifelseifelseifelseif
      elseifelseif    elseifelseif
     elseifelse          elseifelse
    ifelseif                ifelseif
   ifelse                      ifelse
  ifelse                        ifelse
 ifelse                          ifelse
ifelse                            ifelse

But, of course, they want to do this with the least possible cost. So, if you want this job, you have to show you can do this with very little code

Challenge

Write a program or function that takes no input, and outputs to STDOUT the Ifelse tower.

Rules

• Leading and traling new lines are not allowed
• Leading spaces are (of course) a must
• All lines must be at most the same lenght as the base (40 chars). This means you are free to use or not trailing spaces on each line, as long as they don't surpass the base's lenght
• Standard loopholes are not allowed

This is code-golf, so shortest answer in bytes gets the job -err wins